Vehicle Routing Problems for Drone Delivery
Задачи маршрутизации транспортных средств для доставки дронами
2016-07-14
SCID: 54.1/w9f37wvw
Discuss with AI
battery weight and payload energy consumptioncost vs delivery time trade-offdrone deliverymixed integer linear programmultitrip VRPsimulated annealing heuristicvehicle routing problem
Figures from the paper
Abstract (AI)
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.
Key Findings
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.
Research Object
Vehicle routing problems (VRPs) for drone delivery
Research Subject
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
Open access PDF
Access Type
Author Information
Download PDF
Subscribe to digest
References available in scid.ai1
Cited by3
Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey2018
Investigation of Autonomous Multi-UAV Systems for Target Detection in Distributed Environment: Current Developments and Open Challenges2023
Intelligent nanophotonics: when machine learning sheds light2025