Robust traveling salesman problem with multiple drones: Parcel delivery under uncertain navigation environments

The improved unmanned aerial vehicle (UAV, or drone) delivery systems allow an unattended truck to pair two or more drones to accelerate delivery. Although such systems have been addressed in the literature, the extent to which approach can design a robust truck-drone schedule under uncertainty is not yet understood. This paper introduces a robust traveling salesman problem with multiple drones (RTSP-mD), in which a truck coordinates with a heterogeneous fleet of drones to make deliveries under uncertain navigation environments. The RTSP-mD is first formulated as a second-order cone programming (SOCP) to minimize makespan and synchronization risk simultaneously. To solve this complex problem, a three-phased adaptive large neighborhood search (ALNS) algorithm is proposed. The experiment results show that nominal optimal solution generally has a lower expected makespan but rarely remains efficient or feasible under a small perturbation to schedules. About one-third of robust optimal solutions can be against a large reduction of synchronization risk at a negligible price in makespan. And we demonstrate that the drone number remains stable for robust (near-)optimal solutions rather than growing along with customer density increase.