ISBN 9783843910620

978-3-8439-1062-0, Reihe Mathematik

Marika Karbstein
Line Planning and Connectivity

226 Seiten, Dissertation Technische Universität Berlin (2013), Softcover, B5

Zusammenfassung / Abstract

The first part of this thesis introduces the Steiner connectivity problem, a generalization of the well-known Steiner tree problem. The Steiner connectivity problem is a prototype model that has the same significance for line planning in public transport as the Steiner tree problem has for telecommunication network design. The author shows that main results about complexity, approximation, integer programming formulations, and polyhedra can be extended from the Steiner tree problem to the Steiner connectivity problem.

The second part of this thesis deals with the line planning application. The author proposes a new model for the integrated line planning and passenger routing problem that focuses on direct connections. In a project with the Verkehr in Potsdam GmbH to compute the line plan for 2010 the author shows that this approach is applicable in practice and can be used to solve real world problems.