2026-07-24T01:29:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2166 2024-03-06T11:08:49Z ddc:004 open_access

Line Planning and Connectivity Borndörfer, Ralf Neumann, Marika Pfetsch, Marc E. Steiner tree generalization paths The line planning problem in public transport deals with the construction of a system of lines that is both attractive for the passengers and of low costs for the operator. In general, the computed line system should be connected, i.e., for each two stations there have to be a path that is covered by the lines. This subproblem is a generalization of the well-known Steiner tree problem; we call it the Steiner connectivity Problem. We discuss complexity of this problem, generalize the so-called Steiner partition inequalities and give a transformation to the directed Steiner tree problem. We show that directed models provide tight formulations for the Steiner connectivity problem, similar as for the Steiner tree problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ralf Borndörfer and Marika Neumann and Marc E. Pfetsch 2009 Is Part Of Dagstuhl Seminar Proceedings, Volume 9261, Models and Algorithms for Optimization in Logistics (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.09261.15 urn:nbn:de:0030-drops-21661 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09261.15 eng https://creativecommons.org/licenses/by/4.0/legalcode