Flexible Timetables for Railway Networks

Kaspar Schüpbach, Master Thesis, Summer 2007

Supervisors: Gabrio Caimi, Martin Fuchsberger

The problem of generating conflict-free periodic train schedules for large railway networks is here addressed. It follows a two level approach, where a simplified track topology is used to obtain a macro level schedule and the detailed topology is considered locally on the micro level.
This master thesis focuses on the macro level. It started with a literature study about macro timetable generation. In particular, the well-known Periodic Event Scheduling Problem (PESP) was studied in detail and all the relevant literature on the topic was collected. This know-how was used in order to develop in Matlab a timetable generation tool.

Following, in order to increase the solution space in the interface of the two levels, an extension of the PESP is proposed such that it allows to generate flexible time slots for the departure and arrival times instead of exact times. The model is closely related to the original PESP, such that future improvements in the area can probably be included. This Flexible Periodic Event Scheduling Problem (FPESP) formulation considerably increases the chance to obtain feasible solutions (exact train routings) subsequently on the micro level, in particular for stations with dense peak traffic. Total trip time and the time slot sizes are used as multiple objectives and weighted and/or constrained to allocate the flexibility where it is most useful.

Tests on different scenario inspired by the 2007 timetable in central Switzerland demonstrate the advantage of the FPESP model, while it only moderate increases its solution time in most cases.

In the last part of the work a further generalization of the FPESP was introduced, Flexboxes. They overcome the drawback of the strong restrictions on the time slot sizes, and could also be interesting for future applications in delay management. However, due to lack of time, only primary computation were done and further investigation is necessary to validate the model.