Search Results

Documents authored by Herrala, Olli


Document
Using Light Spanning Graphs for Passenger Assignment in Public Transport

Authors: Irene Heinrich, Olli Herrala, Philine Schiewe, and Topias Terho

Published in: OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)


Abstract
In a public transport network a passenger’s preferred route from a point x to another point y is usually the shortest path from x to y. However, it is simply impossible to provide all the shortest paths of a network via public transport. Hence, it is a natural question how a lighter sub-network should be designed in order to satisfy both the operator as well as the passengers. We provide a detailed analysis of the interplay of the following three quality measures of lighter public transport networks: - building cost: the sum of the costs of all edges remaining in the lighter network, - routing costs: the sum of all shortest paths costs weighted by the demands, - fairness: compared to the original network, for each two points the shortest path in the new network should cost at most a given multiple of the shortest path in the original network. We study the problem by generalizing the concepts of optimum communication spanning trees (Hu, 1974) and optimum requirement graphs (Wu, Chao, and Tang, 2002) to generalized optimum requirement graphs (GORGs), which are graphs achieving the social optimum amongst all subgraphs satisfying a given upper bound on the building cost. We prove that the corresponding decision problem is NP-complete, even on orb-webs, a variant of grids which serves as an important model of cities with a center. For the case that the given network is a parametric city (cf. Fielbaum et. al., 2017) with a heavy vertex we provide a polynomial-time algorithm solving the GORG-problem. Concerning the fairness-aspect, we prove that light spanners are a strong concept for public transport optimization. We underpin our theoretical considerations with integer programming-based experiments that allow us to compare the fairness-approach with the routing cost-approach as well as passenger assignment approaches from the literature.

Cite as

Irene Heinrich, Olli Herrala, Philine Schiewe, and Topias Terho. Using Light Spanning Graphs for Passenger Assignment in Public Transport. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{heinrich_et_al:OASIcs.ATMOS.2023.2,
  author =	{Heinrich, Irene and Herrala, Olli and Schiewe, Philine and Terho, Topias},
  title =	{{Using Light Spanning Graphs for Passenger Assignment in Public Transport}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{2:1--2:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.2},
  URN =		{urn:nbn:de:0030-drops-187637},
  doi =		{10.4230/OASIcs.ATMOS.2023.2},
  annote =	{Keywords: passenger assignment, line planning, public transport, discrete optimization, complexity, algorithm design}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail