Delivery drones have been attracting attention as a means of solving recent logistics issues, and many companies are focusing on their practical applications. Many research studies on delivery drones have been active for several decades. Among them, extended routing problems for drones have been proposed based on the Traveling Salesman Problem (TSP), which is used, for example, in truck vehicle routing problems. In parcel delivery by drones, additional constraints such as battery capacity, payload, and weather conditions need to be considered. This study addresses the routing problem for delivery drones. Most existing studies assume that the drone’s flight speed is constant regardless of the load. On the other hand, some studies assume that the flight speed varies with the load. This routing problem is called the Flight Speed-Aware Traveling Salesman Problem (FSTSP). The complexity of the drone flight speed function in this problem makes it difficult to solve the routing problem using general-purpose mathematical optimization solvers. In this study, the routing problem is reduced to an integer programming problem by using linear and quadratic approximations of the flight speed function. This enables us to solve the problem using general-purpose mathematical optimization solvers. In experiments, we compared the existing and proposed methods in terms of solving time and total flight time. The experimental results show that the proposed method with multiple threads has a shorter solving time than the state-of-the-art method when the number of customers is 17 or more. In terms of total flight time, the proposed methods deteriorate by an average of 0.4% for integer quadratic programming and an average of 1.9% for integer cubic programming compared to state-of-the-art methods. These experimental results show that the quadratic and cubic approximations of the problem have almost no degradation of the solution.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    An Integer Programming Based Approach to Delivery Drone Routing under Load-Dependent Flight Speed


    Beteiligte:
    Mao Nishira (Autor:in) / Satoshi Ito (Autor:in) / Hiroki Nishikawa (Autor:in) / Xiangbo Kong (Autor:in) / Hiroyuki Tomiyama (Autor:in)


    Erscheinungsdatum :

    2023




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Unbekannt




    Multi-Trip Routing of Delivery Drones with Load-Dependent Flight Speed

    Nishira, Mao / Nishikawa, Hiroki / Kong, Xiangbo et al. | IEEE | 2024


    Drone Delivery Vehicle Routing Problem with Multi-flight Level

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


    DRONE DELIVERY ROUTING AND COMMUNICATION

    BRIGGS BENJAMIN D / CLEVENGER LAWRENCE A / CLEVENGER LEIGH A et al. | Europäisches Patentamt | 2019

    Freier Zugriff

    DRONE FLIGHT PROGRAMMING METHOD AND SYSTEM

    BEATH JASON IAN NATHANIEL | Europäisches Patentamt | 2019

    Freier Zugriff

    DRONE DELIVERY MULTI-AGENT ROUTING OPTIMIZATION

    Gijseghem, Wouter Van / Agarwal, Umang | TIBKAT | 2020