Reducing train delays in a real-time context : a constraint programming approach using conditional time-interval variables

Details

Supervisors

Schaus, Pierre ; Cappart, Quentin

Faculty

Ecole polytechnique de Louvain

Degree label

Master [120] en sciences informatiques

Abstract

Railway traffic scheduling is a problem that affects a lot of people in their everyday life. While designing efficient train schedules is already a challenge in itself, it is already well solved. However, small perturbations in the traffic can have a big impact on the initial timetable and cause disproportionate delays. Rescheduling and rerouting trains in these situations help limiting the impact of the initial perturbations. Constraint programming is an efficient programming paradigm when it comes to scheduling problems. In this thesis, the focus is placed on rescheduling using constraint programming models built with conditional time-interval variables. Firstly, an implementation of these variables is given for OscaR, which yields promising results. Secondly, some additions are proposed to existing models that target this problem. Finally, the performances of the new model are assessed on fictive data using CP Optimizer and compared to classical approaches. The tests have been realised on multiple Belgian stations and with scenarios of different levels of complexity. The results show that the model gives better performances than greedy approaches (generally used by the railway operators) in almost all the situations.