Model Graf Spasial Adaptif untuk Optimasi Jalur UAV pada Sistem Mitigasi Kebakaran Hutan

Adinda Salsa Leviona; Triyanna Widiyaningtyas

doi:10.29408/edumatic.v9i3.32609

Authors

Adinda Salsa Leviona Program Studi Teknik Informatika, Universitas Negeri Malang https://orcid.org/0009-0006-6514-6563
Triyanna Widiyaningtyas Program Studi Teknik Informatika, Universitas Negeri Malang https://orcid.org/0000-0001-6104-6692

DOI:

https://doi.org/10.29408/edumatic.v9i3.32609

Keywords:

a* algorithm, bidirectional search algorithm, dijkstra algorithm, unmanned aerial vehicle

Abstract

Dynamic wildfires require adaptive mitigation systems capable of responding in real time. Optimizing Unmanned Aerial Vehicle (UAV) routes is critical for effective fire mitigation. This study compares the efficiency of the Dijkstra, A*(star), and Bidirectional Dijkstra algorithms on spatial hotspots graph. The quantitative experimental design used data-driven simulation. Data were obtained from the Forest Fire Area dataset (Kaggle), containing 517 wildfires with (X, Y) coordinates in the Montesinho Natural Park, Portugal. Preprocessing involved analyzing spatial patterns using scatter plots and de-duplication of coordinates. These coordinates were then utilized as nodes to construct a graph using Triangulasi Delaunay. The algorithms were implemented using custom-coded. Performance was evaluated through repeated tests based on the metrics of execution time, memory usage, nodes explored, and path length. The results show that all three algorithms achieved identical optimal paths, however A* achieved the highest computational efficiency by balancing time and memory usage. The combination of the Delaunay spatial graph and the A* algorithm effectively reduces search complexity, it suitable for adaptive UAV navigation. This study provides an empirical comparison of algorithms on a spatial hot-spots graph using Triangulation Delaunay, a method rarely used to evaluate the efficiency of UAV path tracing in real spatial conditions.

References

Alizadeh, N., Mahdianpari, M., Hemmati, E., & Marjani, M. (2025). FusionFireNet: A CNN-LSTM model for short-term wildfire hotspot prediction utilizing spatio-temporal datasets. Remote Sensing Applications: Society and Environment, 37, 101436. https://doi.org/10.1016/j.rsase.2024.101436

Amine, O., & Mohammed, M. (2023). Generating A-Star Algorithm Admissible Heuristics Using a Dynamic Dataloader on Neural Networks, Enhanced With Genetic Algorithms, on a Distributed Architecture. IEEE Access, 11, 18356–18373. https://doi.org/10.1109/ACCESS.2023.3247773

Boroujeni, S. P. H., Razi, A., Khoshdel, S., Afghah, F., Coen, J. L., O’Neill, L., Fule, P., Watts, A., Kokolakis, N. M. T., & Vamvoudakis, K. G. (2024). A comprehensive survey of research toward AI-enabled unmanned aerial systems in pre-, active-, and post-wildfire management. Information Fusion, 108, 102369. https://doi.org/10.1016/j.inffus.2024.102369

Carta, F., Zidda, C., Putzu, M., Loru, D., Anedda, M., & Giusto, D. (2023). Advancements in forest fire prevention: A comprehensive survey. Sensors, 23(14), 6635. https://doi.org/10.3390/s23146635

Chen, X., Fang, J., & Zhai, Y. (2024). UAV path planning method considering safety and signal shielding risk. International Journal of Advanced Computer Science and Applications, 15(6), 415–424. http://www.ijacsa.thesai.org

Ferreira, C., Pinto, L. C., & Valente, M. (2024). Forest fire causes and prevention strategies in Portugal: Insights from stakeholder focus groups. Forest Policy and Economics, 169, 103330. https://doi.org/10.1016/j.forpol.2024.103330

Ilba, M. (2025). Spatial network in SQL databases for real-time multimodal emergency routing in wildland fires. ISPRS International Journal of Geo-Information, 14(3), 110. https://doi.org/10.3390/ijgi14030110

Liu, H., Li, X., Fan, M., Wu, G., Pedrycz, W., & Suganthan, P. N. (2022). An autonomous path planning method for UAV based on tangent intersection and target guidance strategy. IEEE Transactions on Intelligent Transportation Systems, 23, 3061–3073. https://doi.org/10.1109/TITS.2020.3030444

Meng, W., Zhang, X., Zhou, L., Guo, H., & Hu, X. (2025). Advances in UAV path planning: A comprehensive review of methods, challenges, and future directions. Drones, 9(5), 376. https://doi.org/10.3390/drones9050376

Milin, V., Stanivuk, T., Skoko, I., & Bulić, T. (2025). Dijkstra and A* algorithms for algorithmic optimization of maritime routes and logistics of offshore wind farms. Journal of Marine Science and Engineering, 13(10), 1863. https://doi.org/10.3390/jmse13101863

Mohapatra, A., & Trinh, T. (2022). Early wildfire detection technologies in practice A review. Sustainability, 14(19), 12270. https://doi.org/10.3390/su141912270

Oliveras Menor, I., Prat-Guitart, N., Spadoni, G. L., Hsu, A., Fernandes, P. M., et al. (2025). Integrated fire management as an adaptation and mitigation strategy to altered fire regimes. Communications Earth & Environment, 6(1), 271. https://doi.org/10.1038/s43247-025-02165-9

O’Mara, T., Meador, A. S., Colavito, M., Waltz, A., & Barton, E. (2024). Navigating the evolving landscape of wildfire management: A systematic review of decision support tools. Trees, Forests and People, 16, 100575. https://doi.org/10.1016/j.tfp.2024.100575

Pinandito, A., Kharisma, A. P., Akbar, M. A., & Saputra, M. C. (2024). Peningkatan performa komputasi sistem navigasi transportasi publik melalui kompresi data dan penyederhanaan graf. Jurnal Teknologi Informasi dan Ilmu Komputer, 11(6), 1185–1196. https://doi.org/10.25126/jtiik.2024118054

Potapov, P., Tyukavina, A., Turubanova, S., Hansen, M. C., Giglio, L., et al. (2025). Unprecedentedly high global forest disturbance due to fire in 2023–2024. PNAS, 122(30), e2505418122. https://doi.org/10.1073/pnas.2505418122

Rahayuda, I. G. S., & Santiari, N. P. L. (2021). Dijkstra and bidirectional Dijkstra on determining evacuation routes. Journal of Physics: Conference Series, 1803(1), 012018. https://doi.org/10.1088/1742-6596/1803/1/012018

Sriyanto, N. I., Maulana, F. A., Aprilian, R., Christian, E., & Pranatawijaya, V. H. (2024). Utilisation of A* algorithm in determining tourism routes in Palangka Raya City. Telekontran: Jurnal Ilmiah Telekomunikasi, Kendali dan Elektronika Terapan, 12(1), 23–37. https://doi.org/10.34010/telekontran.v12i1.12645

Sunardi, S., Azwar, M., Sofian, M. Z. D., Samsudin, A. R., & Rahman, F. (2025). Implementasi algoritma Dijkstra dan Bellman-Ford untuk optimasi rute pemadam kebakaran di Kota Praya. JTIM: Jurnal Teknologi Informasi dan Multimedia, 7(2), 398–407. https://doi.org/10.35746/jtim.v7i2.744

Tholo, H. M., Kadewa, W., Chisenga, C., Gondwe, S., Zuza, E., et al. (2025). Web-based spatial decision support system for optimum route to forest fires: A case of Viphya plantations. Trees, Forests and People, 19, 100740. https://doi.org/10.1016/j.tfp.2024.100740

Thomaz, E. L., & Pereira, P. (2021). Fire prevention, management and challenges. Current Opinion in Environmental Science & Health, 23, 100301. https://doi.org/10.1016/j.coesh.2021.100301

Wang, R., Lu, Z., Jin, Y., & Liang, C. (2022). Application of A* algorithm in intelligent vehicle path planning. Mathematical Models in Engineering, 8(3), 82–90. https://doi.org/10.21595/mme.2022.22828

Wayahdi, M. R., Ginting, S. H. N., & Syahputra, D. (2021). Greedy, A-Star, and Dijkstra’s algorithms in finding shortest path. International Journal of Advances in Data and Information Systems, 2(1), 45–52. https://doi.org/10.25008/ijadis.v2i1.1206

Xu, Y., Li, J., & Zhang, F. (2022). A UAV-based forest fire patrol path planning strategy. Forests, 13(11), 1912. https://doi.org/10.3390/f13111952

Zhang, W., Li, J., Yu, W., Ding, P., Wang, J., & Zhang, X. (2024). Algorithm for UAV path planning in high obstacle density environments: RFA-star. Frontiers in Plant Science, 15, 1391628. https://doi.org/10.3389/fpls.2024.1391628

Zhou, K., & Zhang, F. (2023). An event-response tree-based resource scheduling method for wildfire fighting. Forests, 14(1), 102. https://doi.org/10.3390/f14010102