Master's Thesis

Handling incidents in train scheduling with Satisfiability Modulo Theories

Tomás Marques Pina de Oliveira Duarte — 2025

Key information

Authors:

Tomás Marques Pina de Oliveira Duarte (Tomás Duarte)

Supervisors:

Maria Inês Camarate de Campos Lynce de Faria (Inês Lynce); João Filipe Rosado Gouveia

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:

Supervisors of this institution:

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