Vehicle Routing Problems for Drone Delivery

Vehicle Routing Problems for Drone Delivery

2016 | Kevin Dorling, Student Member, IEEE, Jordan Heinrichs, Geoffrey G. Messier, Member, IEEE, Sebastian Magierowski, Member, IEEE
The paper addresses the challenges of optimizing drone delivery routes by proposing two multi-trip vehicle routing problems (MTVRPs) for drone delivery scenarios. These problems aim to minimize costs or delivery times while considering battery and payload weight, which are critical factors in drone operations. The authors derive a linear energy consumption model for multirotor drones, demonstrating that energy consumption varies approximately linearly with payload and battery weight. This model is used to develop mixed-integer linear programs (MILPs) for the MTVRPs, which optimize the number of drones, routes, and energy consumption. To handle large instances and find sub-optimal solutions within limited runtime, a simulated annealing (SA) heuristic is proposed. The SA heuristic is applied to show the importance of reusing drones and optimizing battery weight, and to demonstrate the inverse exponential relationship between minimum cost and delivery time, and between minimum delivery time and budget. Numerical results validate the effectiveness of the proposed models and heuristics, highlighting the benefits of reusing drones and optimizing battery size in drone delivery VRPs.The paper addresses the challenges of optimizing drone delivery routes by proposing two multi-trip vehicle routing problems (MTVRPs) for drone delivery scenarios. These problems aim to minimize costs or delivery times while considering battery and payload weight, which are critical factors in drone operations. The authors derive a linear energy consumption model for multirotor drones, demonstrating that energy consumption varies approximately linearly with payload and battery weight. This model is used to develop mixed-integer linear programs (MILPs) for the MTVRPs, which optimize the number of drones, routes, and energy consumption. To handle large instances and find sub-optimal solutions within limited runtime, a simulated annealing (SA) heuristic is proposed. The SA heuristic is applied to show the importance of reusing drones and optimizing battery weight, and to demonstrate the inverse exponential relationship between minimum cost and delivery time, and between minimum delivery time and budget. Numerical results validate the effectiveness of the proposed models and heuristics, highlighting the benefits of reusing drones and optimizing battery size in drone delivery VRPs.
Reach us at info@study.space