Highlights Introduce a robust traveling salesman problem with multiple drones, which is formulated as a second-order cone program. Reveal that robust (near-)optimal solutions can offer a large reduction of synchronization risk at a small price of makespan increase. Develop an empirical approach to determine the ideal number of drones deployed on a truck under uncertainty.

    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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

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


    Contributors:
    Zhao, Lei (author) / Bi, Xinhua (author) / Li, Gendao (author) / Dong, Zhaohui (author) / Xiao, Ni (author) / Zhao, Anni (author)


    Publication date :

    2022-11-12




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English





    Exact methods for the traveling salesman problem with multiple drones

    Cavani, Sara / Iori, Manuel / Roberti, Roberto | Elsevier | 2021




    The Multi-visit Traveling Salesman Problem with Multi-Drones

    Luo, Zhihao / Poon, Mark / Zhang, Zhenzhen et al. | Elsevier | 2021