Dynamic Energy And Cost Efficient Multi-UAV Routing Problem Using Enhanced Genetic Algorithm

Abstract

In this study we propose a novel method for capacitated multi-UAV multi-visit routing problem. Our main focus is on achieving energy and cost effectiveness by using an enhanced genetic algorithm. We delve into the adjustment of UAV speeds based on payloads and study how it impacts energy consumption and operational expenses. Our comprehensive model takes into account the relationships between payload mass, UAV velocity and power usage providing a roadmap for modern UAV delivery networks. Through testing we have demonstrated that our approach can handle the challenges posed by real world delivery scenarios showcasing its adaptability in managing various payload sizes and navigating complex routes. Our research not only confirms that our algorithm is flexible and capable of optimizing UAV delivery operations but also fills a research gap by incorporating speed variability and payload differences in the optimization process. This study marks progress, in enhancing the efficiency of UAV based logistics by reducing both energy requirements and costs.

Keywords

• Capacitated Multi-UAV Routing
• Energy Efficiency
• Enhanced Genetic Algorithm
• UAV Speed Dynamism

References

1. Bruni, M. E., Khodaparasti, S., & Perboli, G. (2023). Energy Efficient UAV-Based Last-Mile Delivery: A Tactical-Operational Model with Shared Depots and Non-Linear Energy Consumption. IEEE Access,11. https://doi.org/10.1109/access.2023.3247501
2. Claro, R. M., Pereira, M. I., Neves, F. S., & Pinto, A. M. (2023). Energy Efficient Path Planning for 3D Aerial Inspections. IEEE Access, 11, 32152–32166. IEEE Access. https://doi.org/10.1109/ACCESS.2023.3262837
3. Dorling, K., Heinrichs, J., Messier, G. G., & Magierowski, S. (2017). Vehicle Routing Problems for Drone Delivery. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 47(1). https://doi.org/10.1109/tsmc.2016.2582745 DroneEngr. (2024). Heavy load drone with 40KGS payload 20 minutes endurance. One-Stop Drone Parts Store. Save BIG. https://www.droneassemble.com/product/heavy-load-drone-with-40kgs-payload-20- minutes-endurance/
4. Huang, C., Lan, Y., Liu, Y., Zhou, W., Pei, H., Yang, L., Cheng, Y., Hao, Y., & Peng, Y. (2018). A New Dynamic Path Planning Approach for Unmanned Aerial Vehicles. Complexity, 2018, e8420294. https://doi.org/10.1155/2018/8420294
5. Huang, Y., Xu, J., Shi, M., & Liu, L. (2022). Time-Efficient Coverage Path Planning for Energy-Constrained UAV. Wireless Communications and Mobile Computing, 2022. https://doi.org/10.1155/2022/5905809
6. Khan, A., Zhang, J., Ahmad, S., Memon, S., Qureshi, H. A., & Ishfaq, M. (2022). Dynamic Positioning and Energy-Efficient Path Planning for Disaster Scenarios in 5G-Assisted Multi-UAV Environments. Electronics, 11(14), Article 14. https://doi.org/10.3390/electronics11142197
7. Kim, S., & Kim, S. (2022). VRP of Drones Considering Power Consumption Rate and Wind Effects. LOGI – Scientific Journal on Transport and Logistics, 13(1), 210–221. https://doi.org/10.2478/logi-2022-0019 Leishman, J. G. (2006). Principles of helicopter aerodynamics (2nd ed). Cambridge University Press. https://doi.org/ 10.1017/S0001924000087352
8. Li, J., Liu, H., Lai, K. K., & Ram, B. (2022). Vehicle and UAV Collaborative Delivery Path Optimization Model. Mathematics, 10(20), 3744. https://doi.org/10.3390/math10203744

9. Li, Y., Liu, L., Wu, J., Wang, M., Zhou, H., & Huang, H. (2022). Optimal Searching Time Allocation for Information Collection Under Cooperative Path Planning of Multiple UAVs. IEEE Transactions on Emerging Topics in Computational Intelligence, 6(5), 1030–1043. IEEE Transactions on Emerging Topics in Computational Intelligence. https://doi.org/10.1109/TETCI.2021.3107488
10. Melo, A. G., Pinto, M. F., Marcato, A. L. M., Honório, L. M., & Coelho, F. O. (2021). Dynamic Optimization and Heuristics Based Online Coverage Path Planning in 3D Environment for UAVs. Sensors, 21(4), Article 4. https://doi.org/10.3390/s21041108
11. Meng, S., Guo, X., Li, D., & Liu, G. (2023). The multi-visit drone routing problem for pickup and delivery services. Transportation Research Part E: Logistics and Transportation Review, 169, 102990. https://doi.org/10.1016/j.tre.2022.102990
12. Nikolić, M., Netjasov, F., Crnogorac, D., Milenković, M., & Glavić, D. (2023). Urban Air Mobility: Multi- objective Mixed Integer Programming Model for Solving the Drone Scheduling Problem. In O. Gervasi, B. Murgante, A. M. A. C. Rocha, C. Garau, F. Scorza, Y. Karaca, & C. M. Torre (Eds.), Computational Science and Its Applications – ICCSA 2023 Workshops (pp. 349–362). Springer Nature Switzerland. https://doi.org/10.1007/978-3-031-37111-0_25
13. Nuryanti, L. (2023). A Vehicle Routing Problem Optimization With Drone Using Tabu Search Algorithm and Analytical Hierarchy Process. Majalah Ilmiah Pengkajian Industri, 15(1). https://doi.org/10.29122/mipi.v15i1.4732
14. Otto, A., Agatz, N., Campbell, J. F., Golden, B. L., & Pesch, E. (2018). Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey. Networks, 72(4). https://doi.org/10.1002/net.21818
15. Pachayappan, M., & Sudhakar, V. (2021). A Solution to Drone Routing Problems using Docking Stations for Pickup and Delivery Services. Transportation Research Record, 2675(12), 1056–1074. https://doi.org/10.1177/03611981211032219
16. Poikonen, S., & Campbell, J. F. (2020). Future directions in drone routing research. Networks, 77(1). https://doi.org/10.1002/net.21982
17. Sacramento, D., Pisinger, D., & Ropke, S. (2019). An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones. Transportation Research Part C: Emerging Technologies, 102, 289–315. https://doi.org/10.1016/j.trc.2019.02.018
18. Sorbelli, F. B., Corò, F., Palazzetti, L., Pinotti, C. M., & Rigoni, G. (2023). How the Wind Can Be Leveraged for Saving Energy in a Truck-Drone Delivery System. IEEE Transactions on Intelligent Transportation Systems, 24(4), 4038–4049. IEEE Transactions on Intelligent Transportation Systems. https://doi.org/10.1109/TITS.2023.3234627
19. Thibbotuwawa, A., Nielsen, P., Zbigniew, B., & Bocewicz, G. (2019). Energy Consumption in Unmanned Aerial Vehicles: A Review of Energy Consumption Models and Their Relation to the UAV Routing. In J. Świątek, L. Borzemski, & Z. Wilimowska (Eds.), Information Systems Architecture and Technology: Proceedings of 39th International Conference on Information Systems Architecture and Technology – ISAT 2018 (pp. 173–184). Springer International Publishing. https://doi.org/10.1007/978-3-319-99996-8_16
20. Wu, G., Zhao, K., Cheng, J., & Ma, M. (2022). A Coordinated Vehicle–Drone Arc Routing Approach Based on Improved Adaptive Large Neighborhood Search. Sensors, 22(10). https://doi.org/10.3390/s22103702
21. Wu, Q., Zeng, Y., & Zhang, R. (2018). Joint Trajectory and Communication Design for Multi-UAV Enabled Wireless Networks. IEEE Transactions on Wireless Communications, 17(3), 2109–2121. IEEE Transactions on Wireless Communications. https://doi.org/10.1109/TWC.2017.2789293
22. Zudio, A., Coelho, I. M., & Ochi, L. S. (2021). Biased Random-key Genetic Algorithm for theHybrid Vehicle- drone Routing Problem for Pick-upand Delivery. Anais Do 15. Congresso Brasileiro de Inteligência Computacional, 1–6. https://doi.org/10.21528/CBIC2021-107