An exact decomposition approach for the real-time Train Dispatching problem

Trains movements on a railway network are regulated by official timetables. Deviations and delays occur quite often in practice, demanding fast re-scheduling and re-routing 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 sub-problems associated with the line and the stations. This decomposition is the basis for a master-slave solution algorithm, in which the master problem is associated with the line and the slave problem is associated with the stations. The two sub-problems are modeled as mixed integer linear programs, with specific sets of variables and constraints. Similarly to the classical Benders' decomposition approach, slave and master communicate through suitable feasibility cuts in the variables of the master. Extensive tests on real-life instances from single and double-track lines in Italy showed significant improvements over current dispatching performances. A decision support system based on this exact approach has been in operation in Norway since February 2014, and represents one of the first operative applications of mathematical optimization to train dispatching.