An Efficient MaxSAT-DDD Approach for Train Rescheduling via Precedence Propagation and Hybrid AMO Encodings
For railway operations, this work provides a more efficient optimization method for real-time train rescheduling under delays.
The paper improves a MaxSAT-DDD model for train rescheduling by introducing hybrid at-most-one encodings and precedence propagation, achieving up to 79.6% runtime reduction on hard instances and solving stepwise instances in ~23 ms on average.
Train rescheduling repairs disturbed timetables while enforcing train-path precedence, resource capacity, and delay objectives. Dynamic Discretization Discovery (DDD) avoids full time discretization by refining only time points needed to certify feasibility and optimality. We strengthen a recent MaxSAT-DDD model through two encoding changes. First, resource conflicts are encoded as time-dependent at-most-one cliques, using pairwise clauses for small cliques and a sequential counter for large cliques. Second, earliest feasible times are propagated along train paths before the first DDD iteration. We evaluate four MaxSAT variants, two SAT optimization backends, Gurobi/CPLEX MILP models, and CPLEX CP on 72 instances and three delay objectives. MaxSAT-DDD solves all stepwise instances in about 23 ms on average. MaxSAT-Default reduces rounded-cost runtime from 794 to 479 ms, and the ablation study reports up to 79.6\% runtime reduction on the common-solved subset of hard continuous track instances.