Real-time Train Scheduling: reactive and proactive algorithms for safe and reliable railway networks

Train scheduling is a critical activity in rail traffic management, both off-line (timetabling) and on-line/in real-time (dispatching). This research aims at the design and development of advanced optimization models and methods for the real-time re-scheduling. The study covers two overlapping areas: managing the train service plans in an increasingly dynamic management scenario; and ensuring the safety and reliability of the railway system in case of major disruptions. Although the real-time re-scheduling problem is relatively easy to depict, due to the interdependent nature of trains moving along the networks lines, a huge challenge looms in the search for an optimal schedule. A great variety of approaches have been proposed over the years, but here we are interested in those based on Mixed Integer Linear Programming, which are the most widely adopted in the literature. The main issue that such approaches must face is how to represent the fact that two trains cannot occupy simultaneously the same track (or other pairs of incompatible railway resources). Typically, Time-Indexed (TI) formulations for scheduling problems are stronger than other classical formulations, like big-M models. Moreover, they can be easily adapted to cope with complicating constraints and non-linear objectives. Unfortunately, their size grows usually very large with the size of the scheduling instance. As a consequence, TI formulations are not suitable for attacking real-life instances, especially when fast, on-line responses are required. Further, the approximation introduced by time discretization often leads to solutions which cannot be realized in practice. The Dynamic Discretization Discovery (DDD), introduced by Boland for the continuous-time service network design problem, is a novel technique to keep at bay the growth of TI formulations (and thus their response times) and, at the same time, ensure the necessary modelling precision. Exploiting and extending the DDD paradigm, we develop a primal-dual exact approach to train dispatching. The result is a restricted TI formulation and a procedure with running times comparable with the best alternatives presented in the literature on our real-life instances of train dispatching. Furthermore, the method implemented does not suffer by the approximation error introduced by a standard time discretization. In our comparisons the big-M approach maintains the lead on average, but the distance is getting smaller. Even though the method developed in this research is at its early stage, it is very promising not only in a railway context but, more generally, for the broader field of job-shop scheduling. In addition, it offers many hints and opportunities for enhancements that will be investigated in future works. On the other hand, when major disruptions occur in a rail network a simple rescheduling is not sufficient to re-ensure the viability of the network. Indeed, parts of the network may become unavailable for inbound trains, and decisions must be taken to mitigate the impact on the overall traffic. Arguably the most critical point is to avoid creating deadlocks, a situation that arises when a group of trains is positioned in such a way that none can move due to other trains in the group blocking their path. The infrastructure manager and train operating companies in these cases may be forced to stop trains until the normal status is recovered. A crucial aspect is thus to identify, for each train, a location where the train can hold during the disruption, avoiding to disconnect the network and allowing for a quick recovering of the original plan, at restart. A good location for holding a train is called a safe place and it additionally serves the purpose of preventing trains to drive past the last location where they can be safely parked, which could otherwise lead to further blockages and deadlocks. We outline some necessary and sufficient conditions to achieve the desired safe places properties. We then translate such conditions into constraints for a binary formulation of the problem, which we named Safe Place Assignment Problem (SPAP). The SPAP finds an application in the current usage of Advanced Traffic Management Systems (ATMSs). This digital train management solutions are called to solve instances of a hard optimization problem in very limited computational time and they may fail to return a plan for different reasons. Finding a solution to the SPAP in these cases adds an additional level of safety, as dispatchers are provided with the last safe location for a train to drive within the plan's horizon. Computational results on a set of instances provided by a Class I U.S. railroad company show how the approach can be used effectively in the real-life setting that motivates the study, by returning optimal assignments in fractions of second. Both research outputs are very innovative and off the beaten track. The achievements regards both the theoretical and methodological point of view and present in addition a practical relevance.