Cheapest paths in public transport: Properties and algorithms - Schöbel, Anita; Urban, Reena (OpenAccess Series in Informatics, 2020)
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.
CRIS-Team Scopus Importer:2023-03-27
Keywords: Cheapest Paths; Fare Systems; Modeling; Public Transport