Design of Robust Railway Timetables

Timetables in public transport are closely related to large complex networks: Each arrival and departure event is a vertex, and links between events model constraints (travel times, minimum headway, minimum transfer times and the like). In this talk, we will survey recent attempts to design delay resistant railway timetables by means of combinatorial optimization. We will also discuss several models and notions of robustness. While timetables can be made robust against small delays to a certain extent, daily operation has to cope with large delays and from time to time even with major disruptions. When connecting trains wait for each other, this can lead to a cascade of further train delays in remote parts of the network. This leads to a challenging online optimization problem: Given a stream of delay messages, decide which trains have to wait and for how long, such that a social system optimum is achieved from the passenger's point of view. We will report on first results of a joint project with Deutsche Bahn AG devoted to this train disposition problem.

Return