This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Liebchen, C. Search for Related Content

The First Optimized Railway Timetable in Practice

Kombinatorische Optimierung und Graphenalgorithmen, Technische Universität, D-10623 Berlin, Germany
liebchen{at}math.tu-berlin.de

A short time ago, decision support by operations research methods in railway companies was limited to operations planning (e.g., vehicle scheduling, duty scheduling, crew rostering). In effect since December 12, 2004, the 2005 timetable of the Berlin subway is based on the results of mathematical programming techniques. It is the first such service concept that has been put into daily operation. Profiting from these techniques, compared with the previous timetable, the Berlin subway today operates with a timetable that offers shorter passenger waiting times—both at stops and at transfers—and even saves one train.

The work is based on a well-established graph model, the periodic event-scheduling problem (PESP). This model was introduced as early as 1989. Besides describing in detail its first success story in practice, in this paper we also deepen a result on the asymptotic complexity of the PESP: we provide MAXSNP-hardness proofs of two natural optimization variants.

Key Words: timetabling; railways; public transport; integer programming
History: Received: November 2006; revised: March 2008; accepted: April 2008.