Integrated railway timetable rescheduling and dynamic passenger routing during a complete blockage

• Published in: Transportation research. Part B: methodological 2021-01, Vol.143, p.86-123
• Main Authors: Zhan, Shuguang, Wong, S.C., Shang, Pan, Peng, Qiyuan, Xie, Jiemin, Lo, S.M.
• Format: Article
• Language: English
• Subjects: Algorithms; Alternating direction method of multipliers; Decomposition; Dynamic programming; High speed rail; High-speed railway; Integer linear programming; Integer programming; Linear programming; Passengers; Rail transportation; Railroads; Railway networks; Rescheduling; Routing; Segments; Timetables; Track blockage; Train rescheduling
• ISSN: 0191-2615; 1879-2367
• DOI: 10.1016/j.trb.2020.11.006

•An integrated space-time network for both train rescheduling and passenger routing is developed for an incident of complete blockage.•A two-layer decomposition approach based on alternating direction method of multipliers (ADMM) algorithm is developed to solve the integrated model.•The model is tested for case studies of Chinese high-speed railway networks. Trains normally run as scheduled in a non-disrupted situation. However, due to external and/or internal factors, trains may deviate from their original timetable during daily operations. To this end, the involved dispatchers are required to reschedule disrupted trains to efficiently transport delayed passengers to their destinations as soon as possible. In this study, we focus on train rescheduling in a seriously disrupted situation where a track segment is completely blocked for a relatively long period of time, e.g., two hours. In this situation, trains cannot pass the disrupted segment, meaning that passengers will be unable to travel as scheduled. We simultaneously rescheduled trains and passenger routes from both the operator’s and passengers’ perspectives. This integrated train rescheduling and passenger rerouting problem was formulated with an Integer Linear Programming model based on a space-time network. We decomposed the integrated model into two subproblems, a train rescheduling problem and a passenger routing problem, using the alternating direction method of multipliers (ADMM) algorithm. Both subproblems could be further decomposed into a series of shortest path problems for trains or passengers, and solved by a dynamic programming algorithm. Finally, we tested our models and algorithms on both a small hypothetical railway network and a part of the Chinese high-speed railway network.