2026-07-25T05:52:12Z https://drops.dagstuhl.de/oai

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

Cheapest Paths in Public Transport: Properties and Algorithms Schöbel, Anita Urban, Reena Public Transport Fare Systems Modeling Cheapest Paths When determining the paths of the passengers in public transport, the travel time is usually the main criterion. However, also the ticket price a passenger has to pay is a relevant factor for choosing the path. The ticket price is also relevant for simulating the minimum income a public transport company can expect. However, finding the correct price depends on the fare system used (e.g., distance tariff, zone tariff with different particularities, application of a short-distance tariff, etc.) and may be rather complicated even if the path is already fixed. An algorithm which finds a cheapest path in a very general case has been provided in [R. Euler and R. Borndörfer, 2019], but its running time is exponential. In this paper, we model and analyze different fare systems, identify important properties they may have and provide polynomial algorithms for computing a cheapest path. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anita Schöbel and Reena Urban 2020 Is Part Of OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2020.13 urn:nbn:de:0030-drops-131499 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.13 eng https://creativecommons.org/licenses/by/3.0/legalcode