A computation method on time-dependent accessibility of urban rail transit networks for the last service
Abstract
Urban rail transit networks seldom provide 24-hour service. The last train is the latest chance for passengers. If passengers arrive too late to catch the last train, the path becomes inaccessible. The network accessibility thus varies depending on the departure time of passenger trips. This paper focuses on the computation method on the time-dependent accessibility of urban rail transit networks in order to facilitate the itinerary planning of passengers. A label setting algorithm is first designed to calculate the latest possible times for Origin–Destination (O–D) pairs, which is the latest departure times of passengers from the origins such that the destinations can be reach successfully. A searching approach is then developed to find the shortest accessible path at any possible departure times. The method is applied in a real-world metro network. The results show that the method is a powerful tool in solving the service accessibility problem. It has the ability to allow passengers to plan an optimal itinerary. Comparison analysis indicates that the proposed method can provide exact solutions in much shorter time, compared with a path enumeration method. Extensive tests on a set of random networks indicate that the method is efficient enough in practical applications. The execution time for an O–D pair on a personal computer with 2.8 GHZ CPU and 4GB of RAM is only 1.2 s for urban rail transit networks with 100 transfer stations.
Keyword : urban rail transit network, accessibility, itinerary planning, last train, timetable, label setting algorithm
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
Brodal, G. S.; Jacob, R. 2004. Time-dependent networks as models to achieve fast exact time-table queries, Electronic Notes in Theoretical Computer Science 92: 3–15. https://doi.org/10.1016/j.entcs.2003.12.019
Cooke, K. L.; Halsey, E. 1966. The shortest route through a network with time-dependent internodal transit times, Journal of Mathematical Analysis and Applications 14(3): 493–498. https://doi.org/10.1016/0022-247X(66)90009-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
Eppstein, D. 1998. Finding the K shortest paths, SIAM Journal on Computing 28(2): 652–673. https://doi.org/10.1137/S0097539795290477
Fredman, M. L.; Tarjan, R. E. 1984. Fibonacci heaps and their uses in improved network optimization algorithms, in 25th Annual Symposium on Foundations of Computer Science, 24–26 October 1984, Singer Island, FL, US, 338–346. https://doi.org/10.1109/SFCS.1984.715934
Friedrich, M.; Hofsaess, I.; Wekeck, S. 2001. Timetable-based transit assignment using branch and bound techniques, Transportation Research Record: Journal of the Transportation Research Board 1752: 100–107. https://doi.org/10.3141/1752-14
Guo, J.-Y.; Jia, L.-M.; Qin, Y. 2015. Analyzing and computing dynamic accessibility with constraints of schedule, Journal of Transportation Systems Engineering and Information Technology 15(1): 118–122 (in Chinese).
Huang, R. 2007. A schedule-based pathfinding algorithm for transit networks using pattern first search, GeoInformatica 11(2): 269–285. https://doi.org/10.1007/s10707-006-0011-y
Huang, R.; Peng, Z.-R. 2002. Schedule-based path-finding algorithms for transit trip-planning systems, Transportation Research Record: Journal of the Transportation Research Board 1783: 142–148. https://doi.org/10.3141/1783-18
Kang, L.; Wu, J.; Sun, H.; Zhu, X.; Gao, Z. 2015. A case study on the coordination of last trains for the Beijing subway network, Transportation Research Part B: Methodological 72: 112–127. https://doi.org/10.1016/j.trb.2014.09.003
Luo, Q.; Xu, R.; Jiang, Z.; Chen, J. 2010. Dynamic accessibility of urban mass transit network based on train diagram, Journal of Tongji University (Natural Science) 38(1): 72–75. https://doi.org/10.3969/j.issn.0253-374x.2010.01.013 (in Chinese).
Martins, E. Q. V.; Pascoal, M. M. B. 2003. A new implementation of Yen’s ranking loopless paths algorithm, Quarterly Journal of the Belgian, French and Italian Operations Research Societies 1(2): 121–133. https://doi.org/10.1007/s10288-002-0010-2
Martins, E. Q. V.; Pascoal, M. M. B.; Santos, J. L. E. 1999. Deviation algorithms for ranking shortest paths, International Journal of Foundations of Computer Science 10(3): 247–261. https://doi.org/10.1142/S0129054199000186
Sanders, P.; Schultes, D. 2006. Engineering highway Hierarchies, Lecture Notes in Computer Science 4168: 804–816. https://doi.org/10.1007/11841036_71
Tong, C. O.; Richardson, A. J. 1984. A computer model for finding the time‐dependent minimum path in a transit system with fixed schedules, Journal of Advanced Transportation 18(2): 145–161. https://doi.org/10.1002/atr.5670180205
Van der Zijpp, N. J.; Catalano, S. F. 2005. Path enumeration by finding the constrained K-shortest paths, Transportation Research Part B: Methodological 39(6): 545–563. https://doi.org/10.1016/j.trb.2004.07.004
Wang, S.; Yang, Y.; Hu, X.; Li, J.; Xu, B. 2016. Solving the K-shortest paths problem in timetable-based public transportation systems, Journal of Intelligent Transportation Systems: Technology, Planning, and Operations 20(5): 413–427. https://doi.org/10.1080/15472450.2015.1082911
Xu, W.; He, S.; Song, R.; Chaudhry, S. S. 2012. Finding the K shortest paths in a schedule-based transit network, Computers & Operations Research 39(8): 1812–1826. https://doi.org/10.1016/j.cor.2010.02.005
Yen, J. Y. 1971. Finding the K shortest loopless paths in a network, Management Science 17(11): 712–716. https://doi.org/10.1287/mnsc.17.11.712
Zhan, F. B.; Noon, C. E. 1998. Shortest path algorithms: an evaluation using real road networks, Transportation Science 32(1): 65–73. https://doi.org/10.1287/trsc.32.1.65
Ziliaskopoulos, A. K.; Mahmassani, H. S. 1993. Time-dependent, shortest-path algorithm for real-time intelligent vehicle highway system applications, Transportation Research Record: Journal of the Transportation Research Board 1408: 94–100.
Ziliaskopoulos, A.; Wardell, W. 2000. An intermodal optimum path algorithm for multimodal networks with dynamic arc travel times and switching delays, European Journal of Operational Research 125(3): 486–502. https://doi.org/10.1016/S0377-2217(99)00388-4
Zografos, K. G.; Androutsopoulos, K. N. 2008. Algorithms for itinerary planning in multimodal transportation networks, IEEE Transactions on Intelligent Transportation Systems 9(1): 175–184. http://doi.org/10.1109/TITS.2008.915650