Menu

News

Intranet

Login

Line planning and periodic timetabling in railway traffic

Project B5: Line planning and periodic timetabling in railway traffic
DFG Research Center Matheon Technische Universität Berlin


Duration: March 2003 - May 2006
As by June 01, 2006, this project was merged with the former MATHEON project B1 into the
new MATHEON project B15
Project head: Prof. Dr. Rolf H. Möhring
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
Germany
Tel: +49 (0)30 - 314 24594
email: moehring@math.tu-berlin.de
Researcher: Christian Liebchen
for address, see above
Tel: +49 (0)30 - 314 25791 
email: liebchen@math.tu-berlin.de
Support: DFG Research Center "Mathematics for Key Technologies" (Matheon)
Industrial Partners: see below
Quick Links: Publications
Industrial Partners
Neu! Media

Project description.

Background.

Line planning and periodic time tabling are tasks that occur on the strategic level in the railway traffic planning process and are typically done "once" per year. Starting from a network of stations and tracks, line planning chooses a set of lines with their frequencies in order to serve passenger demand and to optimize a given objective (e.g. operational cost, direct connections) on the basis of origin-destination data. Based on the chosen set of lines, timetabling then constructs a periodic timetable, again subject to different objectives such as total passenger travel time or rolling stock. Although there are obvious dependencies among these tasks, they are currently handled only sequentially, and mostly manually without the use of optimization tools.

Expertise.

Our group has obtained expert knowledge (see [4]) in a project with ptv traffic mobility logistics, Karlsruhe, on constructing periodic timetables for public transportation systems (our code is integrated into the 2001 release of their planning tool VISUM).

Research program.

The long term goal of this project is to develop optimization methods and algorithms for simultaneous line planning and periodic time tabling. Several mathematical models have been proposed and investigated for both tasks, separately [2]. Line planning is typically done in the context of network design for minimum cost multicommodity flows [1], while periodic timetabling is modeled via periodic potential constraints in a graph representing temporal events in a train schedule and leads to the so-called Periodical Event Scheduling Problem (PESP) [6]. Both lead to large integer programming models that can currently only be solved approximately. No models are available that study their interdependence or even aim at solving them simultaneously.

Example of the PESP model

Achievements.

We developed the concept of integral cycle bases of directed graphs and compared this with other subclasses of cycle bases. For a more detailed description, we refer to the project site Cycle Bases of (Directed) Graphs. Further, we proposed an integrated integer-linear model for periodic timetabling and aspects of line planning (CASPT 2004). Also, we draw a sharper picture of the complexity of the PESP (WEA 2005). Finally, the basic concept of the 2005 timetable of Berlin Underground has been computed by our group (HEUREKA '05). To the best of our knowledge this is the first timetable that has been computed with mathematical optimization techniques and finally got into daily operation.

Cooperation.

Within the center, the closest methodological connections exist with projects B1, B8, and B9. External cooperation takes place with Berliner Verkehrsbetriebe (BVG), ptv, DB, and the Dutch railway planning group around Leo Kroon (Rotterdam).

Relevant Literature (at Project Start).

[1] M. R. Bussieck, M. Krista, K.-D. Wiegand, and U. T. Zimmermann. Linienoptimierung - Modellierung und praktischer Einsatz. In K.-H. Hoffmann et al., editors, Mathematik -- Schlüsseltechnologie für die Zukunft, Springer-Verlag, Berlin, 1997.
[2] M. R. Bussieck, T. Winter, and U. T. Zimmermann. Discrete optimization in public rail transport. Mathematical Programming B, 79(1-3):415--444, 1997. (preprint)
[3] J.-F. Cordeau, P. Toth, and D. Vigo. A survey of optimization models for train routing and scheduling. Transportation Science 32(4):380--404, 1998.
[4] C. Liebchen and L. Peeters. Some Practical Aspects of Periodic Timetabling. In P. Chamoni et al: Operations Research 2001, Springer 2002.
[5] T. Lindner and K. Nachtigall. Periodical event scheduling. Technical report, DLR, Braunschweig, 2000.
[6] P. Serafini and W. Ukovich. A mathematical model for periodic scheduling problems. SIAM Journal on Discrete Mathematics, 2(4):550--581, 1989.

Project Output.