Train Rescheduling With Stochastic Recovery Time: A New Track-Backup Approach

Train rescheduling is an important decision process in railway management. It aims to minimize the negative effects arising from the disturbances via real-time traffic management. Two main challenges are how to formulate the dynamic and complex rescheduling problem as an optimization model, and how to obtain a good solution within a short time limit. Focusing on the stochastic capacity recovery times of blocked tracks, we propose a new track-backup rescheduling (TBR) approach which optimally assigns each affected train a backup track, based on the estimation of recovery time, the original timetable, and track changing cost. Then, we formulate a mixed integer programming (MIP) model to obtain a conflict-free timetable which minimizes the delay cost and the expected track changing cost. A greedy algorithm is designed to reorder trains and reschedule the arrival and departure times, and then we use an MIP algorithm to solve the optimal track backup strategy. Based on the Beijing-Shanghai high-speed railway line, we conduct extensive experimental studies which show that the TBR approach can reduce the rescheduling cost by an average of 10.17% compared with traditional approaches. More important, the greedy-based algorithm is shown to be able to obtain good solutions (with an average error of only 2.85%) within 1.5 s, which implies the high potential of our approach in a real-time traffic management system where fast response is critical.