The Cheapest Ticket Problem in Public Transport
Anita Schöbel () and
Reena Urban ()
Additional contact information
Anita Schöbel: Department of Mathematics, Technische Universität Kaiserslautern, 67663 Kaiserslautern, Germany; Fraunhofer Institute for Industrial Mathematics, 67663 Kaiserslautern, Germany
Reena Urban: Department of Mathematics, Technische Universität Kaiserslautern, 67663 Kaiserslautern, Germany
Transportation Science, 2022, vol. 56, issue 6, 1432-1451
Abstract:
Route choice models in public transport have been discussed for a long time. The main reason why a passenger chooses a specific path is usually based on its length or travel time. However, also the ticket price that passengers have to pay may influence their decision because passengers prefer cheaper paths over more expensive ones. In this paper, we deal with the cheapest ticket problem , which asks for a cheapest ticket to travel between a pair of stations. The complexity and the algorithmic approach to solve this problem depend crucially on the underlying fare structure ; for example, it is easy if the ticket price is proportional to the distance traveled (as in distance tariff fare structures), but may become NP-complete in zone tariff fare structures. We hence discuss the cheapest ticket problem for different variations of distance- and zone-based fare structures. We start by modeling the respective fare structure mathematically, then identify its main properties, and finally provide a polynomial algorithm, or prove NP-completeness of the cheapest ticket problem. We also provide general results on the combination of two fare structures, which is often observed in practice.
Keywords: public transport; fare structures; modeling; cheapest tickets (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:
Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2022.1138 (application/pdf)
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:56:y:2022:i:6:p:1432-1451
Access Statistics for this article
More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().