Optimal multi-class rescheduling of railway traffic

During real-time traffic management, the railway system suffers perturbations. The task of dispatchers is to monitor traffic flow and to compute feasible rescheduling solutions in case of perturbed operations. The main objective of the infrastructure manager is delay minimization, but the dispatchers also need to comply with the objectives of the train operating companies. This paper presents an innovative optimization framework in order to reschedule trains with different classes of priority, that can be computed statically or dynamically in order to include the needs of different stakeholders. An iterative train scheduling procedure is proposed in order to compute feasible train schedules for an ordered set of priority classes, from the highest one to the lowest one. At each step, the procedure focuses on the current priority class, preserving solution quality from the higher priority classes and neglecting lower priority classes in the optimization of train orders and times. The multi-class rescheduling problem is formulated via alternative graphs that are able to model precisely train movements at the microscopic level of block sections and block signals. Each step of the iterative train scheduling procedure is solved to optimality by a state-of-the-art branch and bound algorithm. The results show an interesting gap between single-class and multi-class rescheduling problems in terms of delay minimization. Each priority class is also evaluated in order to assess the performance of the different rescheduling solutions.