A Comparative Performance Analysis of Dijkstra and Metaheuristic Algorithms for the Shortest Path Problem in Inter-District Transportation Networks
Black Sea Journal of Engineering and Science · 15.05.2026 · 9 (3) · 1048-1059
DOI: 10.34248/bsengineering.1802318 ↗Kurz gefasst
Fachartikel in der Zeitschrift Black Sea Journal of Engineering and Science, online erschienen am 15.05.2026. Verfasst von Rabia Korkmaz Tan und 3 weiteren Autor:innen. Die Arbeit nennt 23 Literaturangaben.
Abstract (Originalsprache)
This study addresses the classical shortest path problem, a fundamental challenge in graph theory with critical applications in transportation networks. Using real inter-district distance data from southwestern Türkiye, particularly covering 13 districts of Muğla province, the region frequently affected by forest fires during summer, this study also emphasizes the importance of shortest path analyses for routing firefighting vehicles and emergency logistics. We compare the deterministic Dijkstra algorithm with four metaheuristic approaches: Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Ant Colony Optimization (ACO), and Simulated Annealing (SA). The evaluation focuses on path length optimization, computational efficiency, and convergence behavior across multiple independent runs. Experimental findings confirm that Dijkstra consistently produces the optimal solution (200 km), while ACO achieves the same performance despite its stochastic nature. In contrast, GA (mean 621 km), PSO (mean 734 km), and SA (mean 759 km) exhibited significant deviations from the optimal solution, with varying convergence stability and computation times. These results highlight the robustness of Dijkstra in small-scale static problems, while also demonstrating the potential of ACO as a competitive metaheuristic for dynamic and large-scale applications. Furthermore, Dijkstra-Seeded (DS) hybrid variants of the three underperforming algorithms (DS-GA, DS-PSO, DS-SA) were developed to investigate whether informed initialization could improve solution quality. Experimental results revealed that Dijkstra-based seeding within a permutation-based encoding yielded mixed results, with DS-SA showing meaningful improvement (689 km mean, 9.22% better than original SA), while DS-GA (645 km mean, -3.86%) and DS-PSO (754 km mean, -2.72%) slightly deteriorated. These findings underscore the fundamental challenges of adapting continuous-space metaheuristics to discrete graph problems and highlight the importance of encoding-aware hybridization strategies.
Zitieren
APA
Tan, R. K., Coşkun, O. M., Demirel, Y., & Orhan, Ö. (2026). A Comparative Performance Analysis of Dijkstra and Metaheuristic Algorithms for the Shortest Path Problem in Inter-District Transportation Networks. Black Sea Journal of Engineering and Science, 9(3), 1048-1059. https://doi.org/10.34248/bsengineering.1802318
Vancouver
Tan RK, Coşkun OM, Demirel Y, Orhan Ö. A Comparative Performance Analysis of Dijkstra and Metaheuristic Algorithms for the Shortest Path Problem in Inter-District Transportation Networks. Black Sea Journal of Engineering and Science. 2026;9(3):1048-1059. doi:10.34248/bsengineering.1802318
BibTeX
@article{Tan2026,
author = {Tan, Rabia Korkmaz and Coşkun, Oya Mert and Demirel, Yasemin and Orhan, Özlem},
title = {A Comparative Performance Analysis of Dijkstra and Metaheuristic Algorithms for the Shortest Path Problem in Inter-District Transportation Networks},
journal = {Black Sea Journal of Engineering and Science},
year = {2026},
volume = {9},
number = {3},
pages = {1048--1059},
doi = {10.34248/bsengineering.1802318}
}
EUVIMED