Vehicle Routing Problems for Drone Delivery

Задачи маршрутизации транспортных средств для доставки дронами
Kevin Dorling, Jordan Heinrichs, Geoffrey G. Messier, Sebastian Magierowski
2016-07-14

battery weight and payload energy consumptioncost vs delivery time trade-offdrone deliverymixed integer linear programmultitrip VRPsimulated annealing heuristicvehicle routing problem
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.
1
A cost function incorporating energy consumption and drone reuse is applied within a simulated annealing heuristic to find practical suboptimal solutions.
2
An experimentally validated energy consumption model for multirotor drones shows energy consumption varies approximately linearly with payload and battery weight.
3
Existing VRPs are inadequate for drone delivery because they either forbid multiple depot trips (causing excess drones) or ignore battery and payload effects on energy consumption.
4
Numerical experiments show minimum cost decreases with increasing delivery time limit following an inverse exponential relationship; similarly, minimum delivery time decreases with increasing budget following an inverse exponential relationship.
5
Results confirm the importance of reusing drones and optimizing battery size in drone delivery VRPs.
6
The authors propose two multitrip VRPs: one minimizing cost under a delivery time limit, and one minimizing overall delivery time under a budget constraint.
7
Using the linear approximation, the authors derive mixed integer linear programs for the proposed VRPs.

Vehicle routing problems (VRPs) for drone delivery

Optimal multitrip routing, cost–time trade-offs, and energy-aware drone reuse including battery and payload effects on energy consumption (modeled approximately linear) and associated mixed-integer linear program formulations and heuristic solutions

Publication Details
Publication Date
2016-07-14
Journal
Publisher
ISSN
Cited by
1351
Access Type
Author Information
Authors
Kevin Dorling
Jordan Heinrichs
Geoffrey G. Messier
Sebastian Magierowski
Explore further
Open the scid.ai AI chat with a ready-made request: it will find papers on a similar topic and help build a literature review.
Find similar papers in the chat →
Make a presentation
100%