Train rescheduling for large-scale disruptions in a large-scale railway network

This paper studies the problem of rescheduling trains in a large-scale railway network with the characteristics of long distance, long time horizon and a large number of trains, where a disruption causes the paralysis of a significant part of the network for a long duration. As rescheduling measures we consider train reordering and retiming as well as the option of rerouting trains along alternative paths in the railway network. Although rerouting was not previously employed in large-scale long-distance networks, we show its benefit in reducing passenger delays. We formulate the problem as an integer linear programming (ILP) model on a space–time network with the goal of minimizing the total passenger delay and the number of passengers that could not reach their destination. In order to effectively solve the ILP model for real-world instances, we propose a heuristic algorithm (LR-H), based on the Lagrangian relaxation (LR) of a subset of constraints in the ILP model. LR allows decomposing the problem into a series of independent train-based subproblems which are easy to solve. Due to the large number of constraints and to cope with the real-time requirement, LR-H employs dynamic constraint-generation.