2016 | Kevin Dorling, Student Member, IEEE, Jordan Heinrichs, Geoffrey G. Messier, Member, IEEE, Sebastian Magierowski, Member, IEEE
This paper presents two multi-trip vehicle routing problems (MTVRPs) for drone delivery that address the limitations of existing VRPs. Existing VRPs either do not allow multiple trips to the depot, leading to excessive drone usage, or fail to account for the impact of battery and payload weight on energy consumption, resulting in costly or infeasible routes. The proposed MTVRPs minimize cost under a delivery time limit and minimize delivery time under a budget constraint. A mathematical energy consumption model for multirotor drones is derived and validated, showing that energy consumption increases linearly with battery and payload weight. This model is used to formulate mixed integer linear programs (MILPs) for the MTVRPs. A cost function incorporating energy consumption and drone reuse is applied in a simulated annealing (SA) heuristic to find sub-optimal solutions for practical scenarios. The SA heuristic demonstrates that minimum cost has an inverse exponential relationship with delivery time limit, and minimum delivery time has an inverse exponential relationship with budget. Numerical results confirm the importance of drone reuse and optimizing battery size in drone delivery VRPs. The paper also introduces a linear energy consumption model for multirotor drones, validated experimentally, showing that energy consumption is approximately linear with battery and payload weight. This model simplifies the MTVRPs by allowing linear energy consumption constraints. The paper discusses the assumptions and constraints of the drone delivery problems (DDPs), including route validity, reusability, timing, energy consumption, capacity, and cost. The DDPs are formulated as MILPs with linear constraints compatible with commercial solvers. The paper also proposes a simulated annealing heuristic for finding sub-optimal solutions within limited runtime. The SA heuristic is used to analyze the behavior of DDPs under different conditions, showing the importance of multiple trips and optimizing battery weight. The paper concludes that the proposed MTVRPs and energy consumption model provide a more accurate and efficient approach to drone delivery planning.This paper presents two multi-trip vehicle routing problems (MTVRPs) for drone delivery that address the limitations of existing VRPs. Existing VRPs either do not allow multiple trips to the depot, leading to excessive drone usage, or fail to account for the impact of battery and payload weight on energy consumption, resulting in costly or infeasible routes. The proposed MTVRPs minimize cost under a delivery time limit and minimize delivery time under a budget constraint. A mathematical energy consumption model for multirotor drones is derived and validated, showing that energy consumption increases linearly with battery and payload weight. This model is used to formulate mixed integer linear programs (MILPs) for the MTVRPs. A cost function incorporating energy consumption and drone reuse is applied in a simulated annealing (SA) heuristic to find sub-optimal solutions for practical scenarios. The SA heuristic demonstrates that minimum cost has an inverse exponential relationship with delivery time limit, and minimum delivery time has an inverse exponential relationship with budget. Numerical results confirm the importance of drone reuse and optimizing battery size in drone delivery VRPs. The paper also introduces a linear energy consumption model for multirotor drones, validated experimentally, showing that energy consumption is approximately linear with battery and payload weight. This model simplifies the MTVRPs by allowing linear energy consumption constraints. The paper discusses the assumptions and constraints of the drone delivery problems (DDPs), including route validity, reusability, timing, energy consumption, capacity, and cost. The DDPs are formulated as MILPs with linear constraints compatible with commercial solvers. The paper also proposes a simulated annealing heuristic for finding sub-optimal solutions within limited runtime. The SA heuristic is used to analyze the behavior of DDPs under different conditions, showing the importance of multiple trips and optimizing battery weight. The paper concludes that the proposed MTVRPs and energy consumption model provide a more accurate and efficient approach to drone delivery planning.