Study on the K-Shortest Paths Searching Algorithm of Urban Mass Transit Network Based on the Network Characteristics

Abstract:

K-shortest path is of great significance for urban rail mass transit operation and management especially in large-scale network. The paper has analyzed composite structure characteristics and proposed the route features of the network. According to the former analyses, the author put forward a new method to build a double-layer network model based on the train operation with the corresponding double-layer searching algorithm to solve the model in order to obtain the k-shortest paths. Finally, the rationality and effectiveness of the algorithm had been verified through the examples, which prove that it could provide a new method to get the optimal k-shortest path between different O-D pairs in large scale network, and the search efficiency could be increased more than 13%. As a path searching algorithm based on the train running timetable, it demonstrate decision support for the operation of urban rail mass transit.

• Periodical: Applied Mechanics and Materials (Volumes 505-506)
• Pages: 689-697
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.505-506.689
• Online since: January 2014
• Authors: Wei Teng Zhou*, Bao Ming Han, Hao Dong Yin
• Keywords: Composite Network, K-Shortest Path, Path Searching, Urban Mass Transit

References

[1] 2012 Annual Report of China Urban Mass Transit(Research Report, ARUMT group). Beijing Jiaotong University Press, Beijing, (2013).

[2] Jumei Shen, Yongsheng Shen, Lin Xu. Research on urban rail transit resource allocation based on k-shortest paths algorithm[C]. 2013 4th International Conference on Material and Manufacturing Technology; 2013, 1285-1289.

DOI: 10.4028/www.scientific.net/amr.748.1285

[3] Xinqi Niu, Yinrong PAN． Study on algorithm of income distribution of the underground system [J]．Application Research of Computers，2005，(2): 17-18.

[4] Haodong Yin, Baoming Han, Dewei Li．Modeling and application Of urban rail transit Network for path finding problem[C]. Advances in Intelligent and Soft Computing, 2012, Volume 124/2012, 689-695.

DOI: 10.1007/978-3-642-25658-5_81

[5] Bingfeng Si, Haozhi Zhang, Zhiyou Gao. Improved Dial's algorithm for Logit-based stochastic traffic network assignment problem [J]. China Journal of Highway and Transport, 2009, Vol 22(1): 79-83.

[6] Baohua Wang, Shiwei He, Rui Song. Stochastic dependent-chance programming model and hybrid genetic algorithm for car flow routing plan[J]. Journal of the China Railway Society, 2007, Vol 29(4): 6-11.

DOI: 10.1109/soli.2008.4682927

[7] Xiaofei Zheng. Research and application of an improved multi-path searching algorithm on city public transportation network [D]. Shanghai: DongHua University.

[8] Xiaolei Ye, Yong Lei, Haijun Hou. Application of Ant Colony Algorithm in Global Optimal Path Searching[J]. Journal of System Simulation, 2007, 19(24): 5643-5647.

[9] Ruihua Xu, Qin Luo, Peng Gao. Passenger flow distribution model and algorithm for urban rail transit network based on multi-route choice[J]. Journal of the China Railway Society, 2009, Vol 31(2): 110-114.

[10] Yanfang Zhou. Study on integration train timetabling theories and method for urban mass transit network. Beijing: Beijing Jiaotong University, (2012).