direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 24-2006

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Delay Resistant Timetabling
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]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe