New paths in solving train rescheduling problems: Dynamic Discretization Discovery models and MaxSAT approaches

Train scheduling is a critical activity in rail traffic management, both off-line (timetabling) and on-line (dispatching). Time-Indexed formulations for scheduling problems are stronger than other classical formulations, like Big-M. 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, Time-Indexed formulations are typically not fit to attack real-life instances of job-shop scheduling problems, especially when fast, online responses are required. Additionally, the approximation introduced by time discretization often leads to solutions which cannot be realized in practice. Dynamic Discretization Discovery (DDD), recently introduced by Boland for the continuous-time service network design problem, is a technique to keep at bay the growth of Time-Indexed formulations and their response times and at the same time ensure the necessary modelling precision. Exploiting and extending the DDD paradigm, we develop a primal-dual approach to train dispatching and, more in general, to job-shop scheduling. The result is a restricted Time-Indexed 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. The algorithm implemented represents the first application of a Maximum SATisfiability problem approach to train re-scheduling. In our comparisons, the discretization approach is faster on piece-wise constant objective functions, while the Big-M approach maintains the lead on linear continuous objectives. The method seems to be very promising not only in a railway context but, more generally, for the broader field of job-shop scheduling.