Algorithmic decision support for the construction of periodic railway timetables

Abstract

This thesis addresses the problem of solving large railway timetabling problems using algorithmic methods. With the increasing demand for better and more frequent services, for higher capacity utilization and for improved reliability, railway timetabling problems become more and more complex. Algorithmic decision support is one promising way to cope with this increasing complexity, and the continuous progress of operations research methods offers a significant potential for the railway industry. The approach of this thesis concentrates on algorithms for the construction of periodic railway timetables during long- and mid-term planning. As an input, functional requirements and restrictions of the infrastructure have to be described at a model granularity suitable for the given planning stage. The algorithmic approach then creates a periodic timetable with the same model granularity and optimizes the timetable according to a given objective. Compared to a manual timetable construction, the algorithmic approach allows to compare different timetable scenarios in a shorter time. Possible modifications of the infrastructure or the service intention and their influence on the overall timetable can therefore be tested and evaluated more efficiently and also in more detail.</br>The algorithms studied in this thesis are based on the so called Periodic Event Scheduling Problem (PESP), a mathematical model which proved to be suitable to automate the construction of periodic railway timetables already several times in research and practice. To solve the model there exist different mathematical methods. This thesis summarizes them and shows advantages of a method based on Mixed Integer Linear Programming (MILP). Compared to other solution methods it allows a direct optimization and with this several further advantages concerning a more efficient automation and a better solution quality. However there exists no practical experience of the method for larger timetabling problems and there even can be found the conjecture that the solution method is not suitable for large scale problems.</br>The algorithms developed in this thesis are based on the so-called Periodic Event Scheduling Problem (PESP), a mathematical model which has become the standard approach for algorithmic construction of periodic railway timetables and has been used successfully already several times in research and practice. Different mathematical methods have been proposed to solve timetabling problems formulated as a PESP. This thesis summarizes the different solution approaches and shows advantages of a method based on Mixed Integer Linear Programming (MILP). Compared to other solution methods, the MILP approach allows a direct optimization, and with this several further advantages concerning a more efficient automation and a better solution quality. However, there exists no practical experience of the method for larger timetabling problems and it has been an open question so far whether and to what extent it is suitable for large-scale problems.</br>In this thesis this gap is filled by providing the missing experience of applying the MILP solution approach for a set of increasingly large timetabling problems for parts of the Swiss railway network. To profit from the method’s advantages also for large-scale problems, an adaptation of the solution method is introduced. It allows to reduce computational complexity considerably, but still ensures good solution quality. To this end, the thesis provides three main contributions:</br>• Implementation of the defined algorithms including an automated model construction out of real data provided by Swiss Federal Railways (SBB).</br>• Extension of the models until a limit of computation time for the used algorithms is reached.</br>• Development of new methods for the acceleration of the given algorithms to solve and optimize also larger models.</br>To ensure operational feasibility for the given model granularity and a certain degree of timetable quality for our models, the resulting timetables are evaluated by the software OnTime. This way it can be ensured that the level of detail of our models is rich enough to represent realistic timetable scenarios. However, the models in this thesis are not constructed to study and evaluate a concrete timetable scenario but rather to represent different model sizes to study the computational performance of the proposed algorithms. After an evaluation of different parameters for the algorithm and the used MILP solver, the best parameter setting is used to determine a computational limit of the given solution strategy for larger model sizes. Although using strong computer servers and state-of-the-art commercial MILP solvers, this limit can be reached for our largest models.</br>To accelerate the algorithms, two decomposition methods are proposed and studied. The first one is motivated from optimization theory. The PESP-graph corresponding to a PESP model is split into different subgraphs and used to define independent MILPs. Two iterative methods are introduced to coordinate the subproblems in order to find feasible global solutions of sufficient quality. The decomposition approach is successfully applied to a smaller test model splitting it into two subproblems. However, the generalization of the method for a larger number of subproblems or larger model sizes leads to several difficulties.</br>