  Route choice models in public transport have been discussed for a long time.
The main factor 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 since 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, e.g., it is easy if the ticket prices are
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, 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.
