Unmanned Aerial Vehicles (UAVs) are gaining momentum in many civil and military sectors. An example is represented by the logistics sector, where UAVs have been proven to be able to improve the efficiency of the process itself, as their cooperation with trucks can decrease the delivery time and reduce fuel consumption. In this paper, we first state a mathematical formulation of the Travelling Salesman Problem (TSP) applied to logistic routing, where a truck cooperates synchronously with multiple UAVs for parcel delivery. Then, we propose, implement, and compare different sub-optimal routing approaches to the formulated mFSTSP (multiple Flying Sidekick Travelling Salesman Problem) since the inherent combinatorial computational complexity of the problem makes it unattractable for commercial Mixed-Integer Linear Programming (MILP) solvers. A local search algorithm, two hybrid genetic algorithms that permutate feasible and infeasible solutions, and an alternative ad-hoc greedy method are evaluated in terms of the total delivery time of the output schedule. For the sake of the evaluation, the savings in terms of delivery time over the well-documented truck-only TSP solution are investigated for each proposed routing solution, and this is repeated for two different scenarios. Monte Carlo simulations corroborate the results.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Development of Heuristic Approaches for Last-Mile Delivery TSP with a Truck and Multiple Drones


    Beteiligte:
    Marco Rinaldi (Autor:in) / Stefano Primatesta (Autor:in) / Martin Bugaj (Autor:in) / Ján Rostáš (Autor:in) / Giorgio Guglieri (Autor:in)


    Erscheinungsdatum :

    2023




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Unbekannt




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

    Schermer, Daniel | British Library Conference Proceedings | 2018



    A Cyber-Physical System's Roadmap to Last-Mile Delivery Drones

    Faical, Bruno S. / Marcondes, Cesar A. C. / Loubach, Denis S. et al. | IEEE | 2023


    Potentialities of drones and ground autonomous delivery devices for last-mile logistics

    Lemardelé, Clément / Estrada, Miquel / Pagès, Laia et al. | Elsevier | 2021


    Drones in last-mile delivery: A systematic review on Efficiency, Accessibility, and Sustainability

    Garg, Vipul / Niranjan, Suman / Prybutok, Victor et al. | Elsevier | 2023