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 HighWire Citing Articles via Google Scholar Google Scholar Articles by Borndörfer, R. Articles by Pfetsch, M. E. Search for Related Content

A Column-Generation Approach to Line Planning in Public Transport

Konrad-Zuse-Zentrum für Informationstechnik Berlin, Takustr. 7, 14195 Berlin, Germany
Konrad-Zuse-Zentrum für Informationstechnik Berlin, Takustr. 7, 14195 Berlin, Germany
Konrad-Zuse-Zentrum für Informationstechnik Berlin, Takustr. 7, 14195 Berlin, Germany
borndoerfer{at}zib.de
groetschel{at}zib.de
pfetsch{at}zib.de

The line-planning problem is one of the fundamental problems in strategic planning of public and rail transport. It involves finding lines and corresponding frequencies in a transport network such that a given travel demand can be satisfied. There are (at least) two objectives: the transport company wishes to minimize operating costs, and the passengers want to minimize traveling times. We propose a new multicommodity flow model for line planning. Its main features, in comparison to existing models, are that the passenger paths can be freely routed and lines are generated dynamically. We discuss properties of this model, investigate its complexity, and present a column-generation algorithm for its solution. Computational results with data for the city of Potsdam, Germany, are reported.

Key Words: public transportation; line planning; column generation
History: Received: April 2005; revised: November 2005; accepted: April 2006.

This article has been cited by other articles:

				C. Liebchen The First Optimized Railway Timetable in Practice Transportation Science, November 1, 2008; 42(4): 420 - 435. [Abstract] [PDF]