Vehicle Routing Problems for Drone Delivery

TLDR

Unmanned aerial vehicles can cut last‑mile delivery cost and time, yet existing vehicle routing models fail to allow multiple depot trips or account for battery and payload energy use, limiting their applicability to drone logistics. We propose two multi‑trip vehicle routing problems for drone delivery that simultaneously address multi‑trip feasibility and energy‑aware cost or time optimization. The authors develop a linear energy‑consumption model for multirotor drones, embed it in mixed‑integer linear programs that minimize cost under a time limit or minimize time under a budget, and solve the resulting VRPs with a simulated‑annealing heuristic that incorporates drone reuse. Experimental results show that the minimum cost decreases exponentially with the delivery‑time limit and the minimum delivery time decreases exponentially with the budget, confirming that drone reuse and battery sizing are critical for efficient drone delivery.

Abstract

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 multi-trip 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 sub-optimal 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.