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

Master thesis (2020)

Authors

M.A.J. Vollebergh Electrical Engineering, Mathematics and Computer Science

Contributors

D. de Laat Discrete Mathematics and Optimization - EEMCS (supervisor 1)
Pieter-Jan Fioole Nederlandse Spoorwegen (supervisor 1)
K.I. Aardal Discrete Mathematics and Optimization - EEMCS (supervisor 2)
Dennis Huisman Erasmus Universiteit Rotterdam (supervisor 2)
Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright: © 2020 M.A.J. Vollebergh
More Info
expand_more

Published Date

25-09-2020

Language

English

Reuse Rights

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.

Faculty

Electrical Engineering, Mathematics and Computer Science

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.