785 eng reportzib 0 2004-04-20 2004-04-20 -- The \emph{line planning problem} is one of the fundamental problems in strategic planning of public and rail transport. It consists of finding lines and corresponding frequencies in a public transport network such that a given travel demand can be satisfied. There are (at least) two objectives. The transport company wishes to minimize its operating cost; the passengers request short travel times. We propose two new multi-commodity flow models for line planning. Their main features, in comparison to existing models, are that the passenger paths can be freely routed and that the lines are generated dynamically. 04-10 786 urn:nbn:de:0297-zib-7854 10.1007/978-3-540-73312-6_18 Appeared in: Computer-aided Systems in Public Transport. Mark Hickman, Pitu Mirchandani, Stefan Voss (eds.) Lecture Notes in Economics and Mathematical Systems, 600, 2008, pp. 363-378 Ralf Borndörfer Martin Grötschel Marc Pfetsch 04-10 eng uncontrolled line planning eng uncontrolled column generation Informatik, Informationswissenschaft, allgemeine Werke Transportation, logistics Combinatorial optimization Mathematics of Transportation and Logistics Borndörfer, Ralf Grötschel, Martin MATHEON-B1 MATHEON-B15 Applied Optimization https://opus4.kobv.de/opus4-zib/files/785/ZR-04-10.ps https://opus4.kobv.de/opus4-zib/files/785/ZR-04-10.pdf