A constructive heuristic for the heterogeneous drone delivery problem that considers packages' setups and battery capacity with the aim of minimizing weighted total waiting times of customers

Abstract

This article considers the heterogeneous drone routing problem, which takes into account the setup times of customers’ packages and aims to minimize the weighted total waiting times of customers. Cases where drones differ from each other in terms of battery capacity, carrying capacity, speed and load capacity have been handled. The battery capacity has been associated with the payload carried by the drone as long as it stays in the air. A constructive heuristic has been suggested and many test instances have been used to show how the efficiency of the algorithm changes when different priority values are used. As a result, it has been seen that good solutions can be obtained by assigning the light customer packages to the fast drones for the given test instances by using the suggested constructive heuristic.

Keywords

• Drone delivery problem
• drone routing problem
• energy consumption
• unmanned aerial vehicles
• route planning

References

1. [1] M. Turgut, and B. Şeker, “An exploratory study on the use of unmanned aerial vehicles (UAVs) in transportation: drone transportation and its applications,” Journal of Intelligent Transportation Systems & Applications, vol. 5, no. 2, pp. 169-187, 2022.
2. [2] A. Thibbotuwawa, G. Bocewicz, P. Nielsen, and Z. Banaszak, Z. “Unmanned aerial vehicle routing problems: a literature review,” Applied sciences, vol. 10, no. 13, pp. 4504, 2020.
3. [3] G. Macrina, L. D. P. Pugliese, F. Guerriero, and G. “Laporte, Drone-aided routing: A literature review,” Transportation Research Part C: Emerging Technologies, vol. 120, 2020.
4. [4] N. B. Coelho, V. N. Coelho, I. M. Coelho, L. S. Ochi, R. Haghnazar, D. Zuidema, and A. R. da Costa, “A multi-objective green UAV routing problem,” Computers & Operations Research, vol. 88, pp. 306-315, 2017.
5. [5] K. Dorling, J. Heinrichs, G. G. Messier and S. Magierowski, “Vehicle routing problems for drone delivery”, IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 47, no. 1, pp. 70-85, 2016.
6. [6] Y. Yadav, and A. Narasimhamurthy, “Algorithms for solving the vehicle routing problem with drones”, presented at the 2017 Ninth International Conference on Advances in Pattern Recognition (ICAPR), IEEE, Bangalore, India, 2017.
7. [7] A. Troudi, S. A. Addouche, S. Dellagi and A. E. Mhamedi, “Sizing of the drone delivery fleet considering energy autonomy,” Sustainability, vol. 10, no. 9, 2018.
8. [8] Y., Liu, “An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery using drones,” Computers & Operations Research, vol. 111, pp. 1-20, 2019.

9. [9] M. Moshref-Javadi, A. Hemmati and M. Winkenbach, “A truck and drones model for last-mile delivery: A mathematical model and heuristic approach,” Applied Mathematical Modelling, vol. 80, pp. 290-318, 2020.
10. [10] M. Moshref-Javadi, S. Lee and M. Winkenbach, “Design and evaluation of a multi-trip delivery model with truck and drones,” Transportation Research Part E: Logistics and Transportation Review, vol. 136, pp. 101887, 2020.
11. [11] C. Cheng, Y. Adulyasak and L. M. Rousseau, “Drone routing with energy function: Formulation and exact algorithm,” Transportation Research Part B: Methodological, vol. 139, pp. 364-387, 2020.
12. [12] J. Zhang, J. F., Campbell, D. C. Sweeney and A. C. Hupman, “Energy consumption models for delivery drones: A comparison and assessment,” Transportation Research Part D: Transport and Environment, vol. 90, p. 102668, 2021.
13. [13] D. Viloria Rojas, E. L. Solano‐Charris., A. Muñoz‐Villamizar and J. R. Montoya‐Torres, “Unmanned aerial vehicles/drones in vehicle routing problems: a literature review,” International Transactions in Operational Research, vol. 28, no. 4 pp. 1626-1657, 2021.
14. [14] K. Phalapanyakoon and P. Siripongwutikorn, “Route Planning of Unmanned Aerial Vehicles under Recharging and Mission Time Constraints,” International Journal of Mathematical, Engineering and Management Sciences, vol. 6, no. 5, p. 1439, 2021.
15. [15] K. Phalapanyakoon and P. Siripongwutikorn, “Route planning of heterogeneous unmanned aerial vehicles under recharging and mission time with carrying payload constraints,” Journal of Industrial Engineering and Management, vol. 16, no. 2, pp. 215-235, 2023