Incorporating flexible track use in the SAT model of the Dutch railway timetabling problem

Incorporating flexible track use in the SAT model of the Dutch railway timetabling problem

Vollebergh, M.A.J. (TU Delft Electrical Engineering, Mathematics and Computer Science)

de Laat, D. (mentor)
Fioole, Pieter-Jan (mentor)
Aardal, K.I. (graduation committee)
Huisman, Dennis (graduation committee)

Delft University of Technology

2020-09-25

The construction of cyclic railway timetables is an important task for Netherlands Railways (NS).This construction can be formulated as a Periodic Event Scheduling Problem (PESP). The most powerful technique for solving cyclic railway timetabling problems is constraint programming, especially via SAT solvers when PESP instances are encoded as SAT instances. SAT solvers can determine the feasibility of problem instances of NS quickly and reliably. However, in previous implementations the problem specification must explicitly indicate the track use within stations and on four-track sections. As a result, the solver also reports infeasibility if a small adjustment of the track allocation could lead to a feasible timetable. In this thesis, the Open Periodic Event Scheduling Problem (OPESP) is introduced, which is used in a new method to incorporate flexible track use in the SAT formulation. This method yields promising results that could help improve the timetabling process at NS.

Flexible track use
SAT
PESP
Railways
Timetabling

http://resolver.tudelft.nl/uuid:37aaf584-8775-44d6-b3cb-e914f8a54b48

Student theses

master thesis

© 2020 M.A.J. Vollebergh