Handling conflicts in microscopic railway timetabling at scale: A parallelized approach

This paper presents an optimization framework for microscopic railway timetabling that combines Logic-Based Benders Decomposition with Conflict Discovery (CD-LBBD) alongside a Soft-Conflict Mixed-Integer Programming (SC-MIP) formulation. The CD-LBBD method separates high-level coordination from microscopic feasibility, employing a subproblem based on satisfiability modulo theories to dynamically detect and resolve resource conflicts. The SC-MIP formulation relaxes disjunctive precedence constraints into soft penalties and iteratively minimizes conflict violations to obtain feasible schedules, which are subsequently refined to optimality. Both approaches operate on a strengthened continuous-time event-activity formulation. The framework runs CD-LBBD and SC-MIP in parallel and is evaluated on the complete DISPLIB 2025 benchmark set, comprising 112 real-world-based instances. Within a 10-minute competition limit per instance, CD-LBBD and SC-MIP jointly solve 65 instances to optimality, while the largest instances remain challenging for both methods. The parallelized solver achieves 91 best-known solutions approximately 81% of the benchmark and obtained the highest overall score in the DISPLIB 2025 competition. We evaluate the incremental contribution of the models strengthening techniques and show that they enable solving nearly four times as many instances to proven optimality. These results demonstrate that combining exact methods with complementary algorithmic structures provides strong and scalable performance for large-scale, microscopic railway timetabling.