The First Optimized Railway Timetable in Practice

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.