Research on Hyperpaths in the Urban Rail Transit Network

Abstract:

Hyperpaths enumeration is one of the basic procedures in many traffic planning issues. As a result of its distinctive structure, hyperpaths in Urban Rail Transit Network (URTN) are different from those in road network. Typically, one may never visit a station more than once and would never transfer from one line to another that has been visited in a loopless URTN, meaning that stations a hyperpath traversed cannot be repeated, neither do lines in loopless networks. This paper studies the relationships between feasible path and the shortest path in terms of travel costs. In this paper, a new definition of hyperpath in URTN is proposed and a new algorithm based on the breadth first searching (BFS) method is presented to enumerate the hyperpaths. The algorithm can safely avoid hyperpath omission and can even be applied in networks containing loops as well. The influence of parameters on hyperpaths is studied by experimentally finding hyperpaths in the subway network in Beijing. A group of suggested parameter pairs are then given. Finally, a numerical experiment is used to illustrate the validity of the proposed algorithm. The results imply the significance of the convergence of the BFS algorithm which can be used to search hyperpaths in large scale URTN even with loop.

• Periodical: Applied Mechanics and Materials (Volumes 488-489)
• Pages: 1439-1443
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.488-489.1439
• Online since: January 2014
• Authors: Jin Hai Li*, Jian Feng Liu
• Keywords: Algorithm (GA), Definition, Hyperpath, Parameter, Urban Rail Transit Network

References

[1] Dial R B. A probabilistic multipath traffic assignment model which obviates path enumeration [J], Transportation research part B. 1971 (5): 83-111.

DOI: 10.1016/0041-1647(71)90012-8

[2] Tobin, R.L. An extension of Dial's algorithm utilizing a model of tripmakers' perceptions. Transportation Research, 1977, 11(5), 337-342.

DOI: 10.1016/0041-1647(77)90043-0

[3] Li Zhichun, Huang Haijun. Determining the efficient paths in stochastic traffic assignment [J]. Journal of transportation systems engineering and information technology, 2003, 3(1): 28-31.

[4] Leurent F. Curbing the computational difficulty of Logit equilibrium assignment model [J]. Transportation research-B, 1997, 31: 315-326.

DOI: 10.1016/s0191-2615(96)00035-5

[5] Si Bingfeng, Mao Baohua, Liu Zhili. Passenger flow assignment model and algorithm for urban railway traffic network under the condition of seamless transfer [J]. Journal of the China railway society, 2007, 29(6): 12-17.

[6] Si Bingfeng, Zhang Haozhi, Gao Ziyou. Improved dial's algorithm for logit-based stochastic traffic network assignment problem [J] China Journal of Highway and Transport, 2009, 22(1): 78-83.

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

[8] He Shengxue, Fan Bingquan. A Tree-Efficient Path Searching Algorithm Based on Spatial Hierarchical Reasoning [J]. Journal of transportation systems engineering and information technology, 2006, 6(2): 66-71.

[9] Lars Relund Nielsen. Finding the K shortest hyperpaths [J]. Computers & Operations Research, 2005, 32: 1477-1497.

DOI: 10.1016/j.cor.2003.11.014

[10] N.J. van der Zijpp. Path enumeration by finding the constrained K-shortest paths [J]. Transportation Research Part B, 2005, 39: 545–563.

DOI: 10.1016/j.trb.2004.07.004