Performance Analysis of Dijkstra and A-star Algorithm in Maritime Navigation Pathfinding
Abstract
This study explores various algorithms and methodologies for path planning and decision-making in diverse environments, including maritime distribution and logistics. The research highlights the importance of COLREG rules in designing collision avoidance algorithms for Maritime Autonomous Surface Ships (MASS), emphasizing the need for algorithms that adapt to specific maritime parameters. A Multiple-Criteria Decision-Making (MCDM) approach combined with Dijkstra’s algorithm is presented to optimize route distribution in logistics, taking into account parameters such as cost, distance, congestion, and risk. Experimental path planning methods using A-star and Dijkstra algorithms are discussed for navigating slag disposal sites that emit natural radiation, demonstrating the adaptability of these algorithms in hazardous environments. The study also investigates dynamic path planning algorithms, such as DAA-Star, which incorporate time and risk cost factors to enhance the safety and efficiency of navigation. Integrating various algorithms and considering specific environmental parameters can significantly improve path planning and decision-making processes in maritime and logistics contexts.
Keywords
Full Text:
PDFReferences
[1] H. Wang, W. Mao, and L. Eriksson, “A Three-Dimensional Dijkstra’s algorithm for multi-objective ship voyage optimization,” Ocean Engineering, vol. 186, Aug. 2019, doi: 10.1016/j.oceaneng.2019.106131.
[2] X. Zhu, H. Wang, Z. Shen, and H. Lv, “Ship weather routing based on modified Dijkstra algorithm,” 2016.
[3] Z. He, C. Liu, X. Chu, R. R. Negenborn, and Q. Wu, “Dynamic anti-collision A-star algorithm for multi-ship encounter situations,” Applied Ocean Research, vol. 118, Jan. 2022, doi: 10.1016/j.apor.2021.102995.
[4] A. C. Prasetyo, M. Prayoga Arnandi, H. S. Hudnanto, and B. Setiaji, “Perbandingan Algoritma Astar dan Dijkstra Dalam Menentukan Rute Terdekat 36 Jurnal Ilmiah SISFOTENIKAJuly201xIJCCS Perbandingan Algoritma Astar dan Dijkistra Dalam Menentukan Rute Terdekat Astar and Dijkistra Algorithm Comparison for Determining the Shortest Route.”
[5] M. Grifoll, C. Borén, and M. Castells-Sanabra, “A comprehensive ship weather routing system using CMEMS products and A* algorithm,” Jul. 01, 2022, Elsevier Ltd. doi: 10.1016/j.oceaneng.2022.111427.
[6] V. Novac and E. Rusu, “SHIP ROUTING USING A* ALGORITHM-A BLACK SEA CASE STUDY.”
[7] Jason, M. Siever, A. Valentino, K. M. Suryaningrum, and R. Yunanda, “Dijkstra’s algorithm to find the nearest vaccine location,” in Procedia Computer Science, Elsevier B.V., 2022, pp. 5–12. doi: 10.1016/j.procs.2022.12.105.
[8] S. Liu, H. Jiang, S. Chen, J. Ye, R. He, and Z. Sun, “Integrating Dijkstra’s algorithm into deep inverse reinforcement learning for food delivery route planning,” Transp Res E Logist Transp Rev, vol. 142, Oct. 2020, doi: 10.1016/j.tre.2020.102070.
[9] Y. D. Rosita, E. E. Rosyida, and M. A. Rudiyanto, “Implementation of dijkstra algorithm and multi-criteria decision-making for optimal route distribution,” in Procedia Computer Science, Elsevier B.V., 2019, pp. 378–385. doi: 10.1016/j.procs.2019.11.136.
[10] L. M. S. Bento, D. R. Boccardo, R. C. S. Machado, F. K. Miyazawa, V. G. Pereira de Sá, and J. L. Szwarcfiter, “Dijkstra graphs,” Discrete Appl Math (1979), vol. 261, pp. 52–62, May 2019, doi: 10.1016/j.dam.2017.07.033.
[11] M. E. Miyombo et al., “Optimal path planning in a real-world radioactive environment: A comparative study of A-star and Dijkstra algorithms,” Nuclear Engineering and Design, vol. 420, Apr. 2024, doi: 10.1016/j.nucengdes.2024.113039.
[12] S. Alshammrei, S. Boubaker, and L. Kolsi, “Improved Dijkstra Algorithm for Mobile Robot Path Planning and Obstacle Avoidance,” Computers, Materials and Continua, vol. 72, no. 3, pp. 5939–5954, 2022, doi: 10.32604/cmc.2022.028165.
[13] A. B. Ormevik, K. Fagerholt, F. Meisel, and E. Sandvik, “A high-fidelity approach to modeling weather-dependent fuel consumption on ship routes with speed optimization,” Maritime Transport Research, vol. 5, Dec. 2023, doi: 10.1016/j.martra.2023.100096.
[14] T. T. Tran, T. Browne, M. Musharraf, and B. Veitch, “Pathfinding and optimization for vessels in ice: A literature review,” Jul. 01, 2023, Elsevier B.V. doi: 10.1016/j.coldregions.2023.103876.
[15] D. Yu and M. Il Roh, “Method for anti-collision path planning using velocity obstacle and A* algorithms for maritime autonomous surface ship,” International Journal of Naval Architecture and Ocean Engineering, vol. 16, Jan. 2024, doi: 10.1016/j.ijnaoe.2024.100586.
[16] M. A. Hinostroza and C. Guedes Soares, “Global and local path-planning algorithm for marine autonomous surface ships including forecasting information,” pp. 187–196, May 2021, doi: 10.1201/9781003216599-21.
[17] Z. Guo, M. Hong, Y. Zhang, J. Shi, L. Qian, and H. Li, “Research on safety evaluation and weather routing optimization of ship based on roll dynamics and improved A* algorithm,” International Journal of Naval Architecture and Ocean Engineering, vol. 16, Jan. 2024, doi: 10.1016/j.ijnaoe.2024.100605.
[18] C. Seo, Y. Noh, M. Abebe, Y. J. Kang, S. Park, and C. Kwon, “Ship collision avoidance route planning using CRI-based A∗ algorithm,” International Journal of Naval Architecture and Ocean Engineering, vol. 15, Jan. 2023, doi: 10.1016/j.ijnaoe.2023.100551.
[19] Ü. Öztürk, M. Akdağ, and T. Ayabakan, “A review of path planning algorithms in maritime autonomous surface ships: Navigation safety perspective,” May 01, 2022, Elsevier Ltd. doi: 10.1016/j.oceaneng.2022.111010.
[20] Y. Zhu, G. Zhang, R. Chu, H. Xiao, Y. Yang, and X. Wu, “Research on escape route planning analysis in forest fire scenes based on the improved A* algorithm,” Ecol Indic, vol. 166, Sep. 2024, doi: 10.1016/j.ecolind.2024.112355.
DOI: https://doi.org/10.17509/jmai.v2i2.84983
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.