Improved Yen’s Algorithm for 2nd-Shortest Path Problem

Authors

  • junlin Tian Lanzhou university

DOI:

https://doi.org/10.22399/ijcesen.3524

Keywords:

Path Optimization, Graph theory, k-shortest path problem, Yen’s algorithm, A star algorithm, multi-variable Optimization

Abstract

This paper introduces an algorithm designed to find the shortest and second shortest paths between two nodes in a network. Path optimization plays a crucial role in various fields, such as urban road management, network communication, and traffic planning. Numerous algorithms and insights inspired by machine learning have been developed, leading to valuable outcomes in these areas. However, many existing algorithms are mainly focused on minimizing path duration, and they often neglect other important factors such as cost, motor heating, and battery level, which can substantially affect the process. This study presents an enhancement to Yen’s algorithm with the A star algorithm, aiming not only to achieve a shorter time but also to reduce the associated costs. In many practical scenarios, algorithms that target the absolute shortest travel time often incur higher costs. Consequently, the second shortest path identified by Yen’s algorithm is valuable because it not only meets the requirement for a shorter travel time but also tends to incur lower costs compared to the shortest path. Then this work try to proof this model can be a reduction of Knapsack problem. This study uses the main roads in Lanzhou City as an example, using network topology to establish a coordinate system. By considering the time (t) and cost (c) associated with different transportation options, this study aims to develop a solution that more accurately reflects practical conditions and expected outcomes. The results indicate that the proposed algorithm is more effective at meeting the time and cost requirements compared to the original algorithm.

References

[1] Y. Ji and N. Geroliminis, “On the spatial partitioning of urban transportation networks,” Transportation Research Part B: Methodological, vol. 46, no. 10, pp. 1639–1656, 2012. [Online]. Available: https://www.sciencedirect. com/science/article/pii/S0191261512001099 I

[2] A. Sadeghi-Niaraki, M. Varshosaz, K. Kim, and J. J.Jung, “Real world representation of a road network for route planning in gis,” Expert Systems with Applications, vol. 38, no. 10, pp. 11 999–12 008, 2011. [Online]. Available: https://www.sciencedirect.com/science/article/ pii/S0957417410014867 I

[3] H. Jin, X. Zhu, and C. lin Zhao, “Computation offloading optimization based on probabilistic sfc for mobile online gaming in heterogeneous network,” IEEE Access, vol. 7, pp. 52 168–52 180, 2019. [Online]. Available: https://api.semanticscholar.org/CorpusID:139298407 I

[4] E. Galceran and M. Carreras, “A survey on coverage path planning for robotics,” Robotics and Autonomous Systems, vol. 61, no. 12, pp. 1258–1276, 2013. [Online]. Available: https://www.sciencedirect.com/science/article/ pii/S092188901300167X I

[5] Y. Zhang, D. wei Gong, and J. hua Zhang, “Robot path planning in uncertain environment using multi-objective particle swarm optimization,” Neurocomputing, vol. 103, pp. 172–185, 2013. [Online]. Available: https://www.sciencedirect.com/science/article/ pii/S0925231212007722 I

[6] X. Wang, X. Zhou, Z. Xia, and X. Gu, “A survey of welding robot intelligent path optimization,” Journal of Manufacturing Processes, vol. 63, pp. 14–23, 2021, trends in Intelligentizing Robotic Welding Processes. [Online]. Available: https://www.sciencedirect.com/ science/article/pii/S1526612520303078 I

[7] H. Bai, R. Cheng, D. Yazdani, K. C. Tan, and Y. Jin, “Evolutionary large-scale dynamic optimization using bilevel variable grouping,” IEEE Transactions on Cyber- netics, vol. 53, no. 11, pp. 6937–6950, 2023. I

[8] P. Zhao and J. Han, “On graph query optimization in large networks,” Proc. VLDB Endow., vol. 3, no. 1–2, p. 340–351, Sep. 2010. [Online]. Available: https://doi.org/10.14778/1920841.1920887 I

[9] A. Nagurney, “Congested urban transportation networks and emission paradoxes,” Transportation Research Part D: Transport and Environment, vol. 5, no. 2, pp. 145–151, 2000. [Online]. Available: https://www.sciencedirect.com/science/article/ pii/S1361920999000310 I

[10] C. E. Mandl, “Evaluation and optimization of urban public transportation networks,” European Journal of Operational Research, vol. 5, no. 6, pp. 396–404,1980. [Online]. Availablehttps://www.sciencedirect. com/science/article/pii/0377221780901265 I

[11] L. Ferrari, M. Berlingerio, F. Calabrese, and J. Reades, “Improving the accessibility of urban transportation networks for people with disabilities,” Transportation Research Part C-emerging Technologies, vol. 45, pp. 27– 40, 2014. [Online]. Available: https://api.semanticscholar. org/CorpusID:54938827 I

[12] Y. zhou Chen, S. fei Shen, T. Chen, and R. Yang, “Path optimization study for vehicles evacuation based on dijkstra algorithm,” Procedia Engineering, vol. 71, pp. 159–165, 2014, 2013 International Conference on Performance-based Fireand Fire Protection Engineering, Wuhan (ICPFFPE 2013). [Online]. Available: https://www.sciencedirect. com/science/article/pii/S187770581400441X I

[13] L. R. Ford and D. R. Fulkerson, “A simple algorithm for finding maximal network flows and an application to the hitchcock problem,” Canadian Journal of Mathematics, vol. 9, p. 210–218, 1957. I

[14] P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100–107, 1968. I, III-A, 1, 2

[15] W. Hongbo, “Analysis of urban traffic vehicle routing based on dijkstra algorithm optimization,” Journal of Beijing Jiaotong University, vol. 43, no. 4, 2019. [Online]. Available: https://jdxb.bjtu.edu.cn/EN/ 10.11860/j.issn.1673-0291.20180109 I

[16] M. Z. Serdar, M. Koc¸, and S. G. Al-Ghamdi, “Urban transportation networks resilience: Indicators, disturbances, and assessment methods,” Sustainable Cities and Society, vol. 76, p. 103452, 2022. [Online]. Available: https://www.sciencedirect.com/science/article/ pii/S2210670721007253 I

[17] L. Dongxiang, “A survey of intelligent transportation path planning algorithms,” Electronic Science and Tech- nology, vol. 35, no. 07, pp. 22–26, 2022. I

[18] P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100–107, 1968. II

[19] W. Hoffman and R. Pavley, “A method for the solution of the nth best path problem,” J. ACM, vol. 6, no. 4, p. 506–514, Oct. 1959. [Online]. Available: https://doi.org/10.1145/320998.321004 II

[20] J. Y. Yen, “Finding the k shortest loopless paths in a network,” Management Science, vol. 17, pp. 712–716, 1971. [Online]. Available: https://api.semanticscholar. org/CorpusID:121444315 II, III-A

[21] H. Aljazzar and S. Leue, “K*: A heuristic search algorithm for finding the k shortest paths,” Artificial Intelligence, vol. 175, no. 18, pp. 2129–2154, 2011. [Online]. Available: https://www.sciencedirect. com/science/article/pii/S0004370211000865 II

[22] H. Jiuyuan and M. Yuyu. [On- line]. Available: http://www.ncdc.ac.cn/portal/metadata/ f5cc0627-50d2-4232-bfe2-b87d55086e54 V-A

[23] T. Guoan, “Digital elevation model of china (1km),” 5 2019. [Online]. Available: https://dx.doi.org/ V-A

Downloads

Published

2025-07-29

How to Cite

Tian, junlin. (2025). Improved Yen’s Algorithm for 2nd-Shortest Path Problem. International Journal of Computational and Experimental Science and Engineering, 11(3). https://doi.org/10.22399/ijcesen.3524

Issue

Section

Research Article