The vehicle routing problem with drones (VRP-D) is to determine the optimal routes of trucks and drones such that the total operational cost is minimized in a scenario where the trucks work in tandem with the drones to deliver parcels to customers. While various heuristic algorithms have been developed to address the problem, existing solutions are built based on simplistic cost models, overlooking the temporal dynamics of the costs, which fluctuate depending on the dynamically changing traffic conditions. In this paper, we present a novel problem called the vehicle routing problem with drones under dynamically changing traffic conditions (VRPD-DT) to address the limitation of existing VRP-D solutions. We design a novel cost model that factors in the actual travel distance and projected travel time, computed using a machine learning-driven travel time prediction algorithm. A variable neighborhood descent (VND) algorithm is developed to find the optimal truck-drone routes under the dynamics of traffic conditions through incorporation of the travel time prediction model. A simulation study was performed to evaluate the performance compared with a state-of-the-art VRP-D heuristic solution. The results demonstrate that the proposed algorithm outperforms the state-of-the-art algorithm in various delivery scenarios.


    Access

    Download


    Export, share and cite



    Title :

    VRPD-DT: Vehicle Routing Problem with Drones Under Dynamically Changing Traffic Conditions


    Contributors:

    Publication date :

    2024


    Type of media :

    Preprint


    Type of material :

    Electronic Resource


    Language :

    English




    Integration of Drones in Last-Mile Delivery: The Vehicle Routing Problem with Drones

    Schermer, Daniel | British Library Conference Proceedings | 2018


    Optimization of Vehicle Routing Problem with Drones in Rural Areas

    Chen, Haimei / Hu, Daiwei / Zhang, Tingting | ASCE | 2020


    Vehicle Routing Problem for an Integrated Electric Vehicles and Drones System

    Mara, Setyo Tri Windras / Elsayed, Saber / Essam, Daryl et al. | Springer Verlag | 2023


    An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones

    Sacramento, David / Pisinger, David / Røpke, Stefan | BASE | 2019

    Free access

    Predicting display visibility under dynamically changing lighting conditions

    Aydin, Tunc Ozan / Myszkowski, Karol / Seidel, Hans-Peter | Tema Archive | 2009