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

Abstract

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.