Abstract This paper proposes a novel business model for on-demand package shipment services using drones, and evaluates different modeling and solution approaches for the drone routing problem that underpins the service operation. In the proposed service, customers’ shipment orders of arbitrary origins and destinations, payload weights and bid values are collected every five minutes, and available drones from multiple depots are then dispatched to fulfill a subset of these orders in a way to maximize profit. A drone path starts from a depot, serves one or more customer orders in sequence, and ends at a depot for battery recharging, which incurs a fixed cost. Two mixed integer programming (MIP) formulations are presented to model the drone dispatch and routing problem. To improve solution efficiency, three computational approaches, including two column generation based algorithms and a brute-force path enumeration algorithm, are developed and compared. Computational experiments suggest, somewhat surprisingly, that the brute-force approach is the most effective and most scalable one, outperforming other alternatives by a substantial margin in both computing time and solution quality. Furthermore, an optimization–simulation framework is proposed to assess the system performance over a long horizon that spans multiple dispatch periods without complicating the optimization model. Using the simulation framework, useful managerial insights including the effects of battery capacity, wind condition and computing capability on the fleet dispatch operation, are generated, which will guide real-world implementations of the new business model.

    Highlights Outlines a new business model for drone-based shipment service. Develops several algorithms for expediting the drone dispatch solution. Proposes an optimization–simulation framework for assessing multi-period operations. Shows that the exhaustive enumeration method works better than column generation.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Routing battery-constrained delivery drones in a depot network: A business model and its optimization–simulation assessment


    Contributors:


    Publication date :

    2023-04-18




    Type of media :

    Article (Journal)


    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


    Load and Wind Aware Routing of Delivery Drones

    Satoshi Ito / Keishi Akaiwa / Yusuke Funabashi et al. | DOAJ | 2022

    Free access

    Energy-Constrained Delivery of Goods With Drones Under Varying Wind Conditions

    Sorbelli, Francesco Betti / Coro, Federico / Das, Sajal K. et al. | IEEE | 2021


    Multiple-Drones-Multiple-Trucks Routing Problem for Disruption Assessment

    Ermagun, Alireza / Tajik, Nazanin | Transportation Research Record | 2022


    Drones Routing with Stochastic Demand

    Nan Yu / Bin Dong / Yuben Qu et al. | DOAJ | 2023

    Free access