Highlights The first to formulate a multi-trip drone routing problem. Logical cuts and subgradient cuts for nonlinear energy function. 2-index formulation and branch-and-cut algorithm. Benchmark instance sets based on realistic parameters and known instance sets. Numerical tests demonstrate the effectiveness of modeling and solution schemes.

    Abstract Drone delivery is known as a potential contributor in improving efficiency and alleviating last-mile delivery problems. For this reason, drone routing and scheduling has become a highly active area of research in recent years. Unlike the vehicle routing problem, however, designing drones’ routes is challenging due to multiple operational characteristics including multi-trip operations, recharge planning, and energy consumption calculation. To fill some important gaps in the literature, this paper solves a multi-trip drone routing problem, where drones’ energy consumption is modeled as a nonlinear function of payload and travel distance. We propose adding logical cuts and subgradient cuts in the solution process to tackle the more complex nonlinear (convex) energy function, instead of using the linear approximation method as in the literature, which can fail to detect infeasible routes due to excess energy consumption. We use a 2-index formulation to model the problem and develop a branch-and-cut algorithm for the formulation. Benchmark instances are first generated for this problem. Numerical tests indicate that even though the original model is nonlinear, the proposed approach can solve large problems to optimality. In addition, in multiple instances, the linear approximation model yields routes that under the nonlinear energy model would be energy infeasible. Use of a linear approximation for drone energy leads to differences in energy consumption of about 9% on average compared to the nonlinear energy model.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Drone routing with energy function: Formulation and exact algorithm


    Beteiligte:


    Erscheinungsdatum :

    2020-06-30


    Format / Umfang :

    24 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    DRONE DELIVERY ROUTING AND COMMUNICATION

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

    Freier Zugriff

    DRONE DELIVERY MULTI-AGENT ROUTING OPTIMIZATION

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


    Drone Delivery Multi-Agent Routing Optimization

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


    Drone-aided routing: A literature review

    Macrina, Giusy / Di Puglia Pugliese, Luigi / Guerriero, Francesca et al. | Elsevier | 2020


    Drone with cooling function

    KAND EUI KYU / JANG JEONG IK / PARK HEE MIN et al. | Europäisches Patentamt | 2021

    Freier Zugriff