Once known to be used exclusively in military domain, unmanned aerial vehicles (drones) have stepped up to become a part of new logistic method in commercial sector called "last-mile delivery". In this novel approach, small unmanned aerial vehicles (UAV), also known as drones, are deployed alongside with trucks to deliver goods to customers in order to improve the service quality or reduce the transportation cost. It gives rise to a new variant of the traveling salesman problem (TSP), of which we call TSP with drone (TSP-D). In this article, we consider a variant of TSP-D where the main objective is to minimize the total transportation cost. We also propose two heuristics: "Drone First, Truck Second" (DFTS) and "Truck First, Drone Second" (TFDS), to effectively solve the problem. The former constructs route for drone first while the latter constructs route for truck first. We solve a TSP to generate route for truck and propose a mixed integer programming (MIP) formulation with different profit functions to build route for drone. Numerical results obtained on many instances with different sizes and characteristics are presented. Recommendations on promising algorithm choices are also provided.


    Access

    Download


    Export, share and cite



    Title :

    On the Min-cost Traveling Salesman Problem with Drone


    Contributors:

    Publication date :

    2015


    Remarks:

    We proposed arXiv:1509.08764 as the first report about our research on TSP-D. However due to a critical error in the experiment, we changed the research approach and method and propose arXiv:1512.01503. Now it seems arXiv:1509.08764 received new citations. we would like to withdraw arXiv:1512.01503 and replaced arXiv:1509.08764 with our latest work



    Type of media :

    Preprint


    Type of material :

    Electronic Resource


    Language :

    English




    Optimization Approaches for the Traveling Salesman Problem with Drone

    Agatz, Niels / Bouman, Paul / Schmidt, Marie | British Library Online Contents | 2018


    Plug-In Hybrid Electric Vehicle Traveling-Salesman Problem with Drone

    Zhu, Tengkuo / Boyles, Stephen D. / Unnikrishnan, Avinash | Transportation Research Record | 2024


    Optimizing the Hub-and-Spoke Network with Drone-Based Traveling Salesman Problem

    Chao-Feng Gao / Zhi-Hua Hu / Yao-Zong Wang | DOAJ | 2022

    Free access


    The Traveling Salesman Problem: Route Planning of Recharging Station-Assisted Drone Delivery

    Sun, Deguo / Peng, Xinying / Qiu, Rui et al. | Springer Verlag | 2020