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. We tested LR-H on railway networks of different sizes under several disruption scenarios: first, we compared the results obtained by LR-H on a small-size instance with those found by the general-purpose ILP solver GUROBI, showing that LR-H can find near-optimal solutions in significantly shorter computing times. Then, we applied LR-H to a real-world instance of a railway network in China with 350 trains in different disruption scenarios. The experimental results show that, LR-H can obtain near-optimal solutions with an average optimality gap of 2.27% in an average computing time of about 300 s.