A MaxSAT approach for solving a new Dynamic Discretization Discovery model for train rescheduling problems
针对列车调度问题，提出一种基于动态离散化发现（DDD）的MaxSAT方法，构建受限时间索引模型，在分段常数目标函数上求解速度优于Big-M方法，适用于实时调度场景。
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. Unfortunately, their size grows usually very large with the size of the scheduling instance, making even the linear relaxation hard to solve. Moreover, the approximation introduced by time discretization can lead to solutions which cannot be realized in practice. Dynamic Discretization Discovery (DDD), recently introduced by Boland et al. (2017) 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, ensures the necessary modelling precision. By exploiting the DDD paradigm, we develop a novel approach to train dispatching and, more in general, to job-shop scheduling. The algorithm implemented represents the first application of a Maximum SATisfiability problem approach to the field. In our comparisons on real-life instances of train dispatching, our restricted Time-Indexed formulation solves faster on piece-wise constant objective functions, while the Big-M approach maintains the lead on linear continuous objectives.