A state-of-the-art realization of cyclic railway timetable computation
Document Type
Journal Article
Publication Date
2015
Subject Area
mode - rail, operations - scheduling
Keywords
Timetable optimization, PESP, Timetabling, SAT
Abstract
We describe the periodic event scheduling problem (PESP) based on periodic event networks and extend it by symmetry constraints. The modeling power of the PESP is discussed for automatic calculation of feasible periodic railway timetables. Including the described extensions, complete modeling of integrated regular-interval timetables is possible. Encoding the PESP to propositional logic enables the usage of efficient SAT solvers for solving the PESP. However, optimizing timetables by linear programming is possible, too. As almost all real-world timetable problems are heavily overconstrained, methods for automatic resolving of conflicts are described. Since there is still a lack of efficient conflict resolving algorithms for large-scale intermeshed railway networks, we introduce several strategies for efficiently resolving conflicts and intelligently decomposing timetable problems and discuss the trade-off between computation time and reduction of the solution space. These strategies allow quick adaption to small changes as well. The described methods are implemented in the software system TAKT. We apply the enhanced TAKT to a timetabling study and present some key figures and results.
Rights
Permission to publish the abstract has been given by SpringerLink, copyright remains with them.
Recommended Citation
Kümmling, M., Großmann, P., Nachtigall, K., Opitz, J., & Weiß, R. (2015). A state-of-the-art realization of cyclic railway timetable computation. Public Transport, Vol. 7, pp 281-293.
