Incorporating flexible track use in the SAT model of the Dutch railway timetabling problem
M.A.J. Vollebergh (TU Delft - Electrical Engineering, Mathematics and Computer Science)
D. de Laat – Mentor (TU Delft - Discrete Mathematics and Optimization)
Pieter-Jan Fioole – Mentor (Nederlandse Spoorwegen)
Karen Aardal – Graduation committee member (TU Delft - Discrete Mathematics and Optimization)
Dennis Huisman – Graduation committee member ( Erasmus Universiteit Rotterdam)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
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.