An exact decomposition approach for the real-time train dispatching problem

Abstract

Trains movement on a railway network are regulated by the official timetables. Deviations and delays occur quite often in practice, asking for fast rescheduling and rerouting decisions in order to avoid conflicts and minimize overall delay. This is the real-time train dispatching problem. In contrast with the classic ""holistic"" approach, we show how to decompose the problem into smaller subproblems associated with the line and the stations. This decomposition allows for the application of suitable simplified models,  which in turn makes it possible to apply Mixed Integer Linear Programming to quickly find optimal or near-optimal solutions to a number of real-life instances from single-track lines in Italy.