Abstract

We address a pragmatic use case for cargo drones in last-mile delivery that exploits the benefits of this emerging technology while being cognizant of present-day safety and regulatory concerns around unmanned aerial freight movements. Specifically, we study the use of drones to resupply ground-based delivery vehicles en route with additional shipments via transshipment platforms located across the service area. Shipments may not be loaded onto delivery vehicles at the depot because they only become available after these vehicles have already started their delivery routes or because they cannot be accommodated due to limited vehicle capacities. We exploit the structure of the decision problem to formulate a two-stage deterministic mixed-integer linear program, where the first stage defines delivery vehicle routes and the second stage defines optimal resupply decisions (i.e., vehicle return trips to the depot or drone resupply trips to transshipment platforms). To solve the problem, we propose an exact solution approach based on logic-based Benders decomposition, which is enhanced with valid inequalities derived from partial routes. Notably, our exact solution approach can solve the problem both with and without utilizing the option of drone-based resupply. Through extensive numerical experiments, we show the effectiveness of the proposed exact solution approach and the benefits of our drone-based resupply strategy in reducing total delivery costs and the need for trucks to return to the depot to collect additional or newly released shipments.