Cooperated Unmanned Aerial Vehicle and Ground Vehicle in Humanitarian Operations: A Routing Problem
Article Sidebar
Main Article Content
Abstract
Disasters cause widespread destruction leading to significant loss of life and property. In such scenarios, timely and efficient disaster aid is crucial to reducing casualties and alleviating suffering. The delivery of aid and search for survivors in the aftermath of a disaster often face challenges such as damaged infrastructure and unsafe conditions, making it difficult for conventional rescue efforts. Unmanned aerial vehicle (UAV) is commonly used to solve this problem but as a disaster-prone country, Indonesian disaster relief and operations rarely use UAVs for assistance. However, due to their limited energy UAVs need to be supported by ground vehicles (GVs) to charge or replace batteries during missions. Thus, UAV and GV collaboration is necessary to perform this task. This research develops UAV and GV routing problem models using the depth-first search (DFS) method for pathfinding because it may search for feasible pathways and "backtrack" when nearby nodes are unavailable. This study represents the environment with a time-space network. The proposed model will be tested on a small-scale example and scaled up to a real-world disaster scenario, the 2010 Merapi eruption in Indonesia. The model demonstrates the effectiveness of UAV and GV collaboration in covering all target nodes with a limited of rendezvous points. The results of this study will contribute to the advancement of disaster relief efforts and provide valuable insights into the potential of UAV-GV collaboration for aid delivery in disaster scenarios.
Article Details
This work is licensed under a Creative Commons Attribution 4.0 International License.
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
Agatz, N., Bouman, P., & Schmidt, M. (2018). Optimization approaches for the traveling salesman problem with drone. Transportation Science, 52(4), 965-981.
American Red Cross. (2015). Drones for Disaster Response and Relief Operations. Retrieved Feb 1, 2019, from https://www.issuelab.org/resources/21683/21683.pdf
Badan Penanggulangan Bencana Daerah Kabupaten Sleman. (2012). Rencana Kontijensi Erupsi Gunung Merapi, BPBD Sleman, Yogyakarta.
Cahyono, A. B., & Zayd, R. A. (2018, March). Rapid mapping of landslide disaster using UAV-photogrammetry. In journal of physics: conference series (Vol. 974, No. 1, p. 012046). IOP Publishing.
Chowdhury, S., Emelogu, A., Marufuzzaman, M., Nurre, S. G., & Bian, L. (2017). Drones for disaster response and relief operations: A continuous approximation model. International Journal of Production Economics, 188, 167-184.
Duhamel, C., Lacomme, P., & Prodhon, C. (2011). Efficient frameworks for greedy split and new depth first search split procedures for routing problems. Computers & Operations Research, 38(4), 723-739.
Dorling, K., Heinrichs, J., Messier, G. G., & Magierowski, S. (2016). Vehicle routing problems for drone delivery. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 47(1), 70-85.
Gomez, C., & Purdie, H. (2016). UAV-based photogrammetry and geocomputing for hazards and disaster risk monitoring–a review. Geoenvironmental Disasters, 3, 1-11.
Ha, Q. M., Deville, Y., Pham, Q. D., & Ha, M. H. (2015). Heuristic methods for the traveling salesman problem with drone. arXiv preprint arXiv:1509.08764.
Ha, Q. M., Deville, Y., Pham, Q. D., & Hà, M. H. (2018). On the min-cost traveling salesman problem with drone. Transportation Research Part C: Emerging Technologies, 86, 597-621.
Hassan, Z., Ali Shah, S. I., & Sarwar Rana, A. (2022). Charging Station Distribution Optimization Using Drone Fleet in a Disaster. Journal of Robotics, 2022, 1-13.
Hua, C. S., Qi, J. T., Shang, H., Hu, W., & Han, J. (2016). Detection of collapsed buildings with the aerial images captured from UAV. Science China Information Sciences, 59(3), 1-15.
Iguchi, M., Ishihara, K., & Hendrasto, M. (2011). Learn from 2010 Eruptions at Merapi and Sinabung Volcanoes in Indonesia. Annuals of Disaster Prevention Research Institute, 54, 185-194.
de Oliveira Silva, L., de Mello Bandeira, R. A., & Campos, V. B. G. (2017). The use of UAV and geographic information systems for facility location in a post-disaster scenario. Transportation Research Procedia, 27, 1137-1145.
Półka, M., Ptak, S., & Kuziora, Ł. (2017). The use of UAV's for search and rescue operations. Procedia engineering, 192, 748-752.
Vaillancourt, A. (2016). A theoretical framework for consolidation in humanitarian logistics. Journal of Humanitarian Logistics and Supply Chain Management, 6(1), 2-23.
Volkmann, W. (2017). Small unmanned aerial system mapping versus conventional methods. CTA Working Paper 17/07, CTA.
Li, Z., & Garcia-Luna-Aceves, J. J. (2007). Finding multi-constrained feasible paths by using depth-first search. Wireless Networks, 13(3), 323-334.
Luo, Z., Liu, Z., Shi, J., Wang, Q., Zhou, T., & Liu, Y. (2018, June). The mathematical modeling of the two-echelon ground vehicle and its mounted unmanned aerial vehicle cooperated routing problem. In 2018 IEEE intelligent vehicles symposium (IV) (pp. 1163-1170). IEEE.
Luo, Z., Liu, Z., & Shi, J. (2017). A two-echelon cooperated routing problem for a ground vehicle and its carried unmanned aerial vehicle. Sensors, 17(5), 1144.
Python Software Foundation. (2019, 5 April). Python Patterns - Implementing Graphs, https://www.python.org/doc/essays/graphs/
Surono., Jousset, P., Pallister, J., Boichu, M., Buongiorno, M. F., Budisantoso, A., Costa, F., & Humaida, H. (2012). The 2010 explosive eruption of Java’s Merapi volcano – A ‘100-year’ event. Journal of Volcanology and Geothermal Research, 241-242, 121-135.
Wang, X., Poikonen, S., & Golden, B. (2017). The vehicle routing problem with drones: several worst-case results. Optimization Letters, 11, 679-697.
Wei, X., Qiu, H., Wang, D., Duan, J., Wang, Y., & Cheng, T. C. E. (2020). An integrated location-routing problem with post-disaster relief distribution. Computers & Industrial Engineering, 147, 106632.
Yu, K., Budhiraja, A. K., & Tokekar, P. (2018, May). Algorithms for routing of unmanned aerial vehicles with mobile recharging stations. In 2018 IEEE international conference on robotics and automation (ICRA) (pp. 5720-5725). IEEE.