A Comparative Performance Analysis of Dijkstra and Metaheuristic Algorithms for the Shortest Path Problem in Inter-District Transportation Networks

Öz

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.

Anahtar Kelimeler

• Dijkstra algorithm
• Metaheuristic optimization
• Genetic algorithm
• Ant colony optimization
• Transportation networks
• Dijkstra-seeded hybrid algorithms

Kaynakça

1. Aarts, E., & Korst, J. (1989). Simulated annealing and Boltzmann machines: A stochastic approach to combinatorial optimization and neural computing. John Wiley and Sons.
2. Agushaka, J. O., Ezugwu, A. E., Abualigah, L., Alharbi, S. K., & Khalifa, H. A. E.-W. (2023). Efficient initialization methods for population-based metaheuristic algorithms: A comparative study. Archives of Computational Methods in Engineering, 30, 1727–1787. https://doi.org/10.1007/s11831-022-09850-4
3. Blum, C., & Roli, A. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, 35(3), 268–308. https://doi.org/10.1145/937503.937505
4. Bolotbekova, A., Hakli, H., & Beskirli, A. (2025). Trip route optimization based on bus transit using genetic algorithm with different crossover techniques: A case study in Konya/Türkiye. Scientific Reports, 15(1), Article 2491. https://doi.org/10.1038/s41598-025-86695-4
5. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). MIT Press.
6. Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269–271. https://doi.org/10.1007/BF01386390
7. Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53–66. https://doi.org/10.1109/4235.585892
8. Dorigo, M., & Stützle, T. (2004). Ant colony optimization. MIT Press.

9. Fang, W., Liao, Z., & Bai, Y. (2024). Improved ACO algorithm fused with improved Q-Learning algorithm for Bessel curve global path planning of search and rescue robots. Robotics and Autonomous Systems, 182, Article 104822. https://doi.org/10.1016/j.robot.2024.104822
10. Fredman, M. L., & Tarjan, R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3), 596–615. https://doi.org/10.1145/28869.28874
11. Gen, M., Cheng, R., & Lin, L. (2008). Network models and optimization: Multiobjective genetic algorithm approach. Springer. https://doi.org/10.1007/978-1-84800-181-7
12. Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley Professional.
13. Holland, J. H. (1975). Adaptation in natural and artificial systems. University of Michigan Press.
14. Kennedy, J., & Eberhart, R. C. (1997). A discrete binary version of the particle swarm algorithm. In Proceedings of IEEE International Conference on Systems, Man, and Cybernetics (Vol. 5, pp. 4104–4108). IEEE.
15. Kirkpatrick, S., Gelatt Jr, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671–680. https://doi.org/10.1126/science.220.4598.671
16. Korkmaz Tan, R., & Bora, Ş. (2017). Parameter tuning in modeling and simulations by using swarm intelligence optimization algorithms. International Journal of Computer and Information Engineering, 11(12), 1318–1323.
17. Korkmaz Tan, R., & Bora, Ş. (2019). Adaptive parameter tuning for agent-based modeling and simulation. Simulation, 95(10), 909–925. https://doi.org/10.1177/0037549719846366
18. Li, Y., Cui, C., & Zhao, Q. (2025). A comprehensive optimization for path planning: Combining improved ant colony optimization and smoothing techniques. Processes, 13(2), 555. https://doi.org/10.3390/pr13020555
19. Mohemmed, A. W., Sahoo, N. C., & Geok, T. K. (2008). Solving shortest path problem using particle swarm optimization. Applied Soft Computing, 8(4), 1643–1653. https://doi.org/10.1016/j.asoc.2008.01.002
20. Sharma, V., Nagpal, D., Monga, S., Almogren, A., Srivastava, D., Altameem, A., & Choi, J. (2024). Enhanced forest fire evacuation planning using real-time sensor and GPS algorithm. Scientific Reports, 14, Article 20091. https://doi.org/10.1038/s41598-024-71052-8
21. Stützle, T., & Hoos, H. H. (2000). MAX–MIN ant system. Future Generation Computer Systems, 16(8), 889–914. https://doi.org/10.1016/S0167-739X(00)00043-1
22. Sundarraj, S., Reddy, R. V. K., Basam, M. B., Lokesh, G. H., Flammini, F., & Natarajan, R. (2023). Route planning for an autonomous robotic vehicle employing a weight-controlled particle swarm-optimized Dijkstra algorithm. IEEE Access, 11, 92433–92442. https://doi.org/10.1109/ACCESS.2023.3302698
23. Zhang, J., He, J., Ren, S., Zhou, P., Guo, J., & Song, M. (2025). Research on vehicle scheduling for forest fires in the northern Greater Khingan Mountains. Scientific Reports, 15, Article 1725. https://doi.org/10.1038/s41598-025-85638-3