Delay Resistant Timetabling

Christian Liebchen and Sebastian Stiller

Accepted for publication in Public Transport.

timetabling, robust optimization, stochastic programming, public transport

The goal of this work is to support a management decision on how much prolongation of travel time one is willing to pay for delay resistance, and to ensure, that for a certain budget of buffer time the maximum resistance against delays is achieved.

Our analysis provides a theoretical explanation why buffer times should be distributed in an asymmetric way. We prove convergence and convergence speed of sampling average approximation methods for arbitrary directed acyclic graphs and show the convexity of the corresponding programs. To this end we first have to sharpen the notion of a buffer budget for arbitrary directed acyclic graphs which highlights a relevant anomaly in the UIC rules.

We also address explicitly the construction of periodic timetables, because most European railway companies are operating periodic timetables. There, the Periodic Event Scheduling Problem (PESP) is widely used as the model of choice, for its modeling features and several Integer Programming(IP) formulations. We propose two ways for incorporating a certain degree of robustness into the corresponding IP - with only a moderate loss in nominal quality.

Download as [PDF] [ps.gz]