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

Year 2024, Volume: 3 Issue: 2, 449 - 484, 31.12.2024

Alparslan Güzey , Mehmet Hakan Satman

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

• 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
• 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
• 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/
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• Poikonen, S., & Campbell, J. F. (2020). Future directions in drone routing research. Networks, 77(1). https://doi.org/10.1002/net.21982
• 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
• 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
• 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
• 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
• 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
• 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