Cheapest paths in public transport: Properties and algorithms
Schöbel A, Urban R (2020)
Publication Type: Conference contribution
Publication year: 2020
Journal
Publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Book Volume: 85
Conference Proceedings Title: OpenAccess Series in Informatics
Event location: Virtual, Pisa, ITA
ISBN: 9783959771702
DOI: 10.4230/OASIcs.ATMOS.2020.13
Abstract
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 [6], 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.
Involved external institutions
Germany (DE)How to cite
APA:
Schöbel, A., & Urban, R. (2020). Cheapest paths in public transport: Properties and algorithms. In Dennis Huisman, Christos D. Zaroliagis (Eds.), OpenAccess Series in Informatics. Virtual, Pisa, ITA: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.
MLA:
Schöbel, Anita, and Reena Urban. "Cheapest paths in public transport: Properties and algorithms." Proceedings of the 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2020, Virtual, Pisa, ITA Ed. Dennis Huisman, Christos D. Zaroliagis, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2020.
BibTeX: Download