A Column-Generation Approach to Line Planning in Public Transport.(rev.Vers.NOV06)
Appeared in: Transportation Science 41 (2007) 123-132
| 05-18 | Ralf Borndörfer, Martin Grötschel, Marc E. Pfetsch
A Column-Generation Approach to Line Planning in Public Transport.(rev.Vers.NOV06) Appeared in: Transportation Science 41 (2007) 123-132 | |
Original Version: A Path-Based Model for Line Planning in Public Transport
Abstract: The line planning problem is one of the fundamental
problems in strategic planning of public and rail
transport. It consists in 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, the passengers want to minimize
travel times. We propose a n
ew multi-commodity flow model for line planning. Its main
features, in comparison to existing models, are that the
passenger paths can be freely routed and that the lines
are generated dynamically. We
discuss properties of this model and investigate its
complexity. Results with data for the city of Potsdam,
Germany, are reported.
Keywords: line planning,
column generation
MSC: 90B06, 90C27