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 ().