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

Lei Zhao, Xinhua Bi, Gendao Li, Zhaohui Dong, Ni Xiao and Anni Zhao

Transportation Research Part E: Logistics and Transportation Review, 2022, vol. 168, issue C

Abstract: 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.

Keywords: Drone delivery; Traveling salesman problem; Uncertainty; Adaptive large neighborhood search (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S1366554522003441
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transe:v:168:y:2022:i:c:s1366554522003441

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/bibliographic
http://www.elsevier. ... 600244/bibliographic

DOI: 10.1016/j.tre.2022.102967

Access Statistics for this article

Transportation Research Part E: Logistics and Transportation Review is currently edited by W. Talley

More articles in Transportation Research Part E: Logistics and Transportation Review from Elsevier
Bibliographic data for series maintained by Catherine Liu ().