A Column-Generation Approach to Line Planning in Public Transport

Ralf Borndörfer (), Martin Grötschel () and Marc E. Pfetsch ()
Additional contact information
Ralf Borndörfer: Konrad-Zuse-Zentrum für Informationstechnik Berlin, Takustr. 7, 14195 Berlin, Germany
Martin Grötschel: Konrad-Zuse-Zentrum für Informationstechnik Berlin, Takustr. 7, 14195 Berlin, Germany
Marc E. Pfetsch: Konrad-Zuse-Zentrum für Informationstechnik Berlin, Takustr. 7, 14195 Berlin, Germany

Transportation Science, 2007, vol. 41, issue 1, 123-132

Abstract: 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.

Keywords: public transportation; line planning; column generation (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (57)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1060.0161 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:41:y:2007:i:1:p:123-132

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().