Vehicle Routing Problems for Drone Delivery
Top Cited Papers
- 14 July 2016
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Systems, Man, and Cybernetics: Systems
- Vol. 47 (1), 70-85
- https://doi.org/10.1109/tsmc.2016.2582745
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 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.Keywords
Funding Information
- Natural Sciences and Engineering Research Council of Canada (PGSD3-443041-2013)
This publication has 26 references indexed in Scilit:
- Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windowsEuropean Journal of Operational Research, 2016
- UAV Control on the Basis of 3D Landmark Bearing-Only ObservationsSensors, 2015
- The load-dependent vehicle routing problem and its pick-up and delivery extensionTransportation Research Part B: Methodological, 2015
- A literature review on the vehicle routing problem with multiple depotsComputers & Industrial Engineering, 2015
- Dependable Low-altitude Obstacle Avoidance for Robotic Helicopters Operating in Rural AreasJournal of Field Robotics, 2013
- Energy Minimizing Vehicle Routing ProblemLecture Notes in Computer Science, 2007
- Knapsack ProblemsPublished by Springer Science and Business Media LLC ,2004
- The Deterministic Annealing Algorithms for Vehicle Routing ProblemsInternational Journal of Smart Engineering System Design, 2003
- Optimization by Simulated AnnealingScience, 1983
- Equation of State Calculations by Fast Computing MachinesThe Journal of Chemical Physics, 1953