Vehicle Routing Problems for Drone Delivery

By Kevin Dorling, Jordan Heinrichs, G. Messier, S. Magierowski. IEEE Transactions on Systems, Man & Cybernetics. Systems, 2016

1,095 citations recorded by the source corpus.

Unmanned aerial vehicles, or drones, have the potential to significantly reduce the cost and time of making last-mile deliveries and responding to emergencies. Despite this potential, little work has gone into developing vehicle routing problems (VRPs) specifically for drone delivery scenarios. Existing VRPs are insufficient for planning drone deliveries: either multiple trips to the depot are not permitted, leading to solutions with excess drones, or the effect of battery and payload weight on energy consumption is not considered, leading to costly or infeasible routes. We propose two multitrip VRPs for drone delivery that address both issues. One minimizes costs subject to a delivery time limit, while the other minimizes the overall delivery time subject to a budget constraint. We mathematically derive and experimentally validate an energy consumption model for multirotor drones, demonstrating that energy consumption varies approximately linearly with payload and battery weight. We use this approximation to derive mixed integer linear programs for our VRPs. We propose a cost function that considers our energy consumption model and drone reuse, and apply it in a simulated annealing (SA) heuristic for finding suboptimal solutions to practical scenarios. To assist drone delivery practitioners with balancing cost and delivery time, the SA heuristic is used to show that the minimum cost has an inverse exponential relationship with the delivery time limit, and the minimum overall delivery time has an inverse exponential relationship with the budget. Numerical results confirm the importance of reusing drones and optimizing battery size in drone delivery VRPs.

Subfields: Aerospace Engineering, Automotive Engineering, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/8273d145e6dbc16899ed55e23578cda5374ee1c7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Aerospace Engineering

In Automotive Engineering

In Industrial and Manufacturing Engineering

Citations in the corpus

The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones (2020, methodology): “We leverage the work of Dorling et al. (2017) to determine the energy consumed by drones as a linear function of parcel weight, speed, and operation time.”
Blockchain and Cryptocurrencies: Model, Techniques, and Applications (2018, background): “cars or drones, may become autonomous and adaptive agents that possess individual intelligence, and interact and trade with other devices without intermediation [26], [27].”
Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey (2018, background): “[55] M, P, H, Exp drone minimum turning radius general [68] M, MH, EmpCS, Exp several drones limited carrying capacity, energy consumption depends on the drone’s weight transport”
Wireless Communication Using Unmanned Aerial Vehicles (UAVs): Optimal Transport Theory for Hover Time Optimization (2017, background): “Indeed, the flight time duration of the UAVs presents a unique design challenge for UAVbased communication systems [19] and [20].”
Mobile Edge Computing via a UAV-Mounted Cloudlet: Optimization of Bit Allocation and Path Planning (2016, background): “As a result, recent research activity has focused on the problems of path planning and energy-aware deployment for UAV-based systems [8]–[18], as we briefly review below.”
Applications and Research avenues for drone-based models in logistics: A classification and review (2021, methodology): “Moreover, to realistically model the flight range limit, some articles consider the effect of payload on energy consumption to estimate it more accurately (see, e.g., Dorling et al., 2017; Song et al., 2018; Rabta et al., 2018; Torabbeigi et al., 2019; Murray and Raj, 2020).”