License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2022.8
URN: urn:nbn:de:0030-drops-171124
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17112/
Go to the corresponding OASIcs Volume Portal

Heinrich, Irene ; Schiewe, Philine ; Seebach, Constantin

Algorithms and Hardness for Non-Pool-Based Line Planning

pdf-format:
OASIcs-ATMOS-2022-8.pdf (0.8 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{heinrich_et_al:OASIcs.ATMOS.2022.8,
  author =	{Heinrich, Irene and Schiewe, Philine and Seebach, Constantin},
  title =	{{Algorithms and Hardness for Non-Pool-Based Line Planning}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{8:1--8:21},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-259-4},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{106},
  editor =	{D'Emidio, Mattia and Lindner, Niels},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17112},
  URN =		{urn:nbn:de:0030-drops-171124},
  doi =		{10.4230/OASIcs.ATMOS.2022.8},
  annote =	{Keywords: line planning, public transport, discrete optimization, complexity, algorithm design}
}

Keywords: line planning, public transport, discrete optimization, complexity, algorithm design
Collection: 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)
Issue Date: 2022
Date of publication: 06.09.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI