Collaborative truck multi-drone routing and scheduling problem: Package delivery with flexible launch and recovery sites

This paper deals with the problem of coordinating a truck and multiple heterogeneous un-manned aerial vehicles (UAVs or drones) for last-mile package deliveries. Existing literature ontruck-drone tandems predominantly restricts the UAV launch and recovery operations (LARO)to customer locations. Such a constrained setting may not be able to fully exploit the capabilityof drones. Moreover, this assumption may not accurately reflect the actual delivery operations.In this research, we address these gaps and introduce a new variant of truck-drone tandemthat allows the truck to stop at non-customer locations (referred to as flexible sites) for droneLARO. The proposed variant also accounts for three key decisions - (i) assignment of eachcustomer location to a vehicle, (ii) routing of truck and UAVs, and (iii) scheduling drone LAROand truck operator activities at each stop, which are always not simultaneously considered inthe literature. A mixed integer linear programming model is formulated to jointly optimize thethree decisions with the objective of minimizing the delivery completion time (or makespan).To handle large problem instances, we develop an optimization-enabled two-phase searchalgorithm by hybridizing simulated annealing and variable neighborhood search. Numericalanalysis demonstrates substantial improvement in delivery efficiency of using flexible sites forLARO as opposed to the existing approach of restricting truck stop locations. Finally, severalinsights on drone utilization and flexible site selection are provided based on our findings

Automated summary

This paper addresses the coordination problem of a truck and multiple heterogeneous unmanned aerial vehicles (UAVs or drones) for last-mile package deliveries. It introduces a new variant of truck-drone tandem that allows the truck to stop at non-customer locations for drone launch and recovery operations. The paper formulates a mixed integer linear programming model to optimize three key decisions and proposes an optimization-enabled two-phase search algorithm. Numerical analysis shows significant improvement in delivery efficiency by using flexible sites for drone operations.