Real-time integrated train rescheduling and rolling stock circulation planning for a metro line under disruptions

More and more unexpected events occur in metro systems, which may cause serious disturbances and even disruptions for the operation of trains. This paper studies an integrated train rescheduling and rolling stock circulation planning problem for the complete blockage situations in a metro line. We consider several key practical train operation constraints, including the maximum number of available rolling stocks, the turnaround constraints, the service connection constraints. This problem is viewed as a complex multi-objective mixed integer linear programming (MILP) formulation, where the objectives involve the deviations with respect to the timetable, the (partial) cancellations, and the headway deviations of train services. A two-stage approach is also developed to enhance the computational efficiency, where a smaller-size optimization problem is solved in the first stage, by considering a set of key turnaround stations only, while the original MILP problem is solved in the second stage by fixing some binary variables according to the first stage solution. In addition, we propose a heuristic technique that is based on introducing a new set of constraints to reduce the search space without eliminating potentially good solutions. Comprehensive experiments are investigated based on the practical data of Beijing Subway Lines, where the proposed integrated models and approaches yield much better solutions when compared with a widely used strategy, i.e., holding (waiting at station) strategy and the sequential approach. Moreover, the impacts of the complete blockage locations/durations and the effects of different weight settings in the multi-objective optimization are deeply analyzed.