Master's Thesis
Handling incidents in train scheduling with Satisfiability Modulo Theories
— 2025
Key information
Authors:
Supervisors:
Published in
November 10, 2025
Abstract
Railway operations rely on precise scheduling to ensure safety and efficiency, though incidents frequently disrupt planned timetables. Train rescheduling addresses this challenge by adjusting routes and timings based on ongoing incidents, with the goal of minimizing their impact on customers. Approaches like linear programming and tailored algorithms have seen extensive research, but Satisfiability Modulo Theories (SMT) remains underexplored despite its ability to combine Boolean logic with other types of constraints. This work proposes an SMT encoding for the train rescheduling problem, modeling times, routes and resource conflicts using linear integer arithmetic and Booleans. Starting with the infrastructure and planned timetables, the rescheduler precomputes routes and potential conflicts, producing a base encoding, which is then incrementally updated. Batched incidents are encoded on top and move the cutoff time used to prune finished lines. A binary meta-search algorithm minimizes cumulative delay (with cancellation penalties), more efficiently than Z3’s native optimizer. To improve reproducibility, we introduce the Common Railway Format (CRF) for networks, schedules, and incidents, implemented in a new open-source library, as well as a suite of problem instances based on data from Great Britain’s Network Rail. Evaluation on our instances demonstrates feasibility. We are able to solve 100-incident batches on networks with 11,000 links and 400 scheduled trains under 3 minutes throughout most of the day, with considerable decreases after peak-hours. Performance degrades on larger instances, where the solver cannot reach a solution within a tractable time, highlighting the need for further improvements.
Publication details
Authors in the community:
Tomás Duarte
ist1111002
Supervisors of this institution:
Inês Lynce
ist14029
Fields of Science and Technology (FOS)
electrical-engineering-electronic-engineering-information-engineering - Electrical engineering, electronic engineering, information engineering
Publication language (ISO code)
eng - English
Rights type:
Embargo lifted
Date available:
October 7, 2026
Institution name
Instituto Superior Técnico