Highlights A new variant of multi-visit vehicle routing problem with drones. Considering load-dependent energy consumption in drone simultaneous pickup and delivery operations. An efficient two-stage heuristic algorithm and two feasibility test methods for trucks and drones. Evidencing the strong performance of the proposed algorithm over two benchmark approaches.

    Abstract Unmanned aerial vehicles, commonly known as drones, have gained wide attention in recent years due to their potential of revolutionizing logistics and transportation. In this paper, we consider a variant of the combined truck-drone routing problem, which allows drones to serve multiple customers and provide both pickup and delivery services in each flight. The problem concerns the deployment and routing of a fleet of trucks, each equipped with a supporting drone, to serve all the pickup and delivery demands of a set of customers with minimal total cost. We explicitly model the energy consumption of drones by their travel distance, curb weight and the carrying weight of parcels, develop a mixed-integer linear programming model (MILP) with problem-customized inequalities, and show a sufficient condition for the benefit of the combined truck-drone mode over the truck-only mode. Considering the complexity of the MILP model, we propose a novel two-stage heuristic algorithm in which a maximum payload method is developed to construct the initial solutions, followed by an improved simulated annealing algorithm with problem-specific neighborhood operators and tailored acceleration strategies. Furthermore, two methods are developed to test the feasibility for both trucks and drones in each solution. The proposed algorithm outperforms two benchmark heuristics in our numerical experiments, which also demonstrate the considerable benefit of allowing multiple visits and both pickup and delivery operations in each drone flight.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    The multi-visit drone routing problem for pickup and delivery services


    Beteiligte:
    Meng, Shanshan (Autor:in) / Guo, Xiuping (Autor:in) / Li, Dong (Autor:in) / Liu, Guoquan (Autor:in)


    Erscheinungsdatum :

    2022-12-05




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    An unpaired pickup and delivery vehicle routing problem with multi-visit

    Xu, Dongyang / Li, Kunpeng / Zou, Xuxia et al. | Elsevier | 2017


    A Solution to Drone Routing Problems using Docking Stations for Pickup and Delivery Services

    Pachayappan, Murugaiyan / Sudhakar, Vijayakumar | Transportation Research Record | 2021


    Heterogeneous multi-drone routing problem for parcel delivery

    Wen, Xupeng / Wu, Guohua | Elsevier | 2022


    Optimization of the drone-assisted pickup and delivery problem

    Mulumba, Timothy / Diabat, Ali | Elsevier | 2023


    Drone Delivery Vehicle Routing Problem with Multi-flight Level

    Kim, Yonggab / Jung, Hoyoung / Lee, Seokcheon | British Library Conference Proceedings | 2021