Projects per year
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 subnetwork 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 NPcomplete, even on orbwebs, 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 polynomialtime algorithm solving the GORGproblem. Concerning the fairnessaspect, we prove that light spanners are a strong concept for public transport optimization. We underpin our theoretical considerations with integer programmingbased experiments that allow us to compare the fairnessapproach with the routing costapproach as well as passenger assignment approaches from the literature.
Original language  English 

Title of host publication  23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2023 
Editors  Daniele Frigioni, Philine Schiewe 
Publisher  Schloss Dagstuhl  LeibnizZentrum für Informatik 
Chapter  2 
Pages  116 
Number of pages  16 
ISBN (Electronic)  9783959773027 
DOIs  
Publication status  Published  Sept 2023 
MoE publication type  A4 Conference publication 
Event  Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems  Amsterdam, Netherlands Duration: 7 Sept 2023 → 8 Sept 2023 Conference number: 23 
Publication series
Name  Open Access Series in Informatics (OASIcs) 

Publisher  Schloss Dagstuhl  LeibnizZentrum für Informatik 
Volume  115 
ISSN (Electronic)  21906807 
Conference
Conference  Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems 

Abbreviated title  ATMOS 
Country/Territory  Netherlands 
City  Amsterdam 
Period  07/09/2023 → 08/09/2023 
Fingerprint
Dive into the research topics of 'Using Light Spanning Graphs for Passenger Assignment in Public Transport'. Together they form a unique fingerprint.Projects
 1 Active

Oliveira_Fabricio_AoF_Project: Oliveira Fabricio AoF Project
Pinheiro de Oliveira, F., Andelmin, J., Weller, P., Herrala, O., Terho, T., Belyak, N., Hankimaa, H., Stinzendörfer, M. & Reijonen, E.
01/09/2020 → 31/08/2024
Project: Academy of Finland: Other research funding