2026-08-16T18:39:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17112 2024-03-06T10:31:52Z ddc:004 open_access

Algorithms and Hardness for Non-Pool-Based Line Planning Heinrich, Irene Schiewe, Philine Seebach, Constantin line planning public transport discrete optimization complexity algorithm design Line planning, i.e. choosing paths which are operated by one vehicle end-to-end, is an important aspect of public transport planning. While there exist heuristic procedures for generating lines from scratch, most theoretical observations consider the problem of choosing lines from a predefined line pool. In this paper, we consider the complexity of the line planning problem when all simple paths can be used as lines. Depending on the cost structure, we show that the problem can be NP-hard even for paths and stars, and that no polynomial time approximation of sub-linear performance is possible. Additionally, we identify polynomially solvable cases and present a pseudo-polynomial solution approach for trees. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Irene Heinrich and Philine Schiewe and Constantin Seebach 2022 Is Part Of OASIcs, Volume 106, 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2022.8 urn:nbn:de:0030-drops-171124 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.8 eng https://creativecommons.org/licenses/by/4.0/legalcode