Railway systems are often affected by delays, disturbances or cancellations. These undesired events can be alleviated by suitably re-routing and re-scheduling trains, in real-time. Such task (train dispatching) is central in managing railway systems as it allows recovering from undesirable deviations from the timetable and better exploiting railway resources. With few exceptions, dispatching is still almost entirely in the hands of human operators, despite the problem amounts to solving a complex and large optimization problem. Dispatchers naturally decompose this problem into two separate sub-problems, by first deciding how trains should travel and meet along the line (macro problem), and then establishing the exact sequencing and platforms assignment in each station. Most heuristic approaches to the problem are based on the same macro/micro decomposition, with the micro problem solved only once the macro is fixed. This decomposition can be made exact by means of a classical tool from mixed integer linear programming, namely Benders' reformulation.
In this talk, we describe how integer programming can be exploited to find optimal solutions to large dispatching problems within the stringent time limit required by this application. In particular, we show how to decompose the problem into smaller sub-problems, associated with different parts of the network. 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. Interestingly, the slave problem further decompose into smaller sub-problems, each associated to a specific station. We show how the station sub-problem, under some assumptions which are often fulfilled in practice, can be solved in polynomial time. A decision support system based on this exact approach was put in operation in Norway in February 2014, representing one of the first operative applications of mathematical optimization to train dispatching. |