# The Cheapest Ticket Problem in Public Transport111Parts of the paper are
based on a preliminary version presented at ATMOS 2020 [SU20].

Anita Schöbel  Technische Universität Kaiserslautern, Germany  Fraunhofer-
Institute for Industrial Mathematics ITWM, Germany  Reena Urban  Technische
Universität Kaiserslautern, Germany

###### Abstract

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 system_ , e.g., it is easy if the ticket prices are proportional to the
distance traveled (as in distance tariff fare systems), but may become NP-
complete in zone tariff fare systems. We hence discuss the cheapest ticket
problem for different variations of distance- and zone-based fare systems. We
start by modeling the respective fare system 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 systems, which is often observed in practice.

##  1 Introduction

Fare systems may be very diverse, containing a lot of different rules and
regulations. Among them is the flat tariff in which all journeys cost the
same, no matter how long they are, or kilometer-based distance tariffs which
are used by most railway companies all over the world. Very popular in
metropolitan regions are zone tariffs (used in many German regional transport
networks and in many European cities, but also, e.g., in California) in which
the number of zones passed on a journey determines the ticket price. In most
regions, these fare systems come with special regulations: journeys with less
than a given number of stations may get a special price, there might be
network-wide tickets or stations belonging to more than one zone. The
underlying fare system is usually independent of the way tickets are bought:
they can be provided as paper tickets from ticket machines or from online
sales, by usage of smart cards in check-in-check-out systems, or by other
mobile devices. Recently, some public transport companies offer the simple
usage of a mobile device for charging the beeline tariff between the start
coordinates and the end coordinates of the journey. Sometimes these different
fare systems are combined.

The question which we pursue in our paper is how to find the cheapest
possibility to travel between two stations if the fare system is known. This
question is relevant for several reasons. First, the passengers would like to
minimize their ticket prices as one among other criteria when planning their
journeys. Second, a public transport company can only estimate its income if
ticket prices are known for the demand. Knowing the cheapest ticket prices for
the demand, hence, gives a lower bound on the expected income of the public
transport provider. Third, for designing and improving fare systems, it is
necessary to be able to compute (cheapest) ticket prices. Last, knowing about
the ticket prices and combining them with the expected travel time may help to
understand the passengers’ behavior better and hence may lead to more
realistic passenger assignment models.

In this paper, we discuss the following two properties:

No-stopover property:

Passengers cannot save money by splitting a journey into two (or more) parts
and buying separate tickets for each of these sub-journeys.

No-elongation property:

Passengers cannot save money by buying a ticket for a longer journey but only
using a part of it.

As will be shown, there is no relation between these two properties. They are
relevant from a real-world point of view since they ensure that a fare system
is consistent and does not trigger strange actions (e.g., buying a ticket for
a longer path than needed) as a legal way of saving money. In [MHS06], the
authors say that a fare system without the no-stopover property would be
“impractical and potentially confusing for the customer”. Still, this property
is not always satisfied in real-world fare systems, see [Urb20]. The no-
elongation property was taken into account in [OB17].

As already mentioned, the cheapest ticket problem depends crucially on the
underlying fare system. Literature on fare systems is scarce compared to
papers on timetabling or scheduling in public transport. Early papers deal
with the design of zone tariffs, see [HS95, HS04, BK03, BNP05]. The topic is
still ongoing using different types of objectives, e.g., the income of the
public transport company, as in [BKP12, GMS17, OB17]. Also the design of
distance tariffs from zone tariffs has been studied in [MS18]. The computation
of cheapest paths has been considered for distance tariffs in a railway
context in [MHS06], while [DPW15] and [DDP19] compute paths that visit the
smallest number of tariff zones. Recently, [EB19] have presented the so-called
ticket graph which models transitions between tickets via transition functions
over partially ordered monoids and allows the design of an algorithm for
finding cheapest paths in fare systems which do not have the subpath-
optimality property. However, the runtime of this approach need not be
polynomial.

The remainder of the paper is structured as follows: In Section 2, we start by
defining what a fare system is, and we define the no-stopover property and the
no-elongation property formally. We then discuss these properties for
different fare systems and develop algorithms and/or complexity results
regarding the cheapest ticket problem. This is done for distance tariffs,
beeline tariffs and flat tariffs in Section 3, for various zone tariff fare
systems in Section 4, and for the combination of different fare systems in
Section 5. We conclude in Section 6.

##  2 Fare Systems in Public Transport

We consider different types of fare systems which we define in their dedicated
sections. We first specify what a fare system is. We are not aware of such a
formal definition in the literature.

Let a _Public Transport Network (PTN)_ be given. A PTN $(V,E)$ is a graph with
a node set $V$ given by a set of stops or stations and an edge set $E$ of
direct connections between them. For simplicity, we assume the PTN to be an
undirected graph which is simple and connected. The PTN can be used to model
railway, tram, or bus networks. In the following, we call the nodes of the PTN
_stations_ also if bus networks with stops are under consideration. The price
of a journey through a PTN depends not only on the start station and the end
station of the journey, but also on the specific path and the tickets that
have been chosen.

######  Definition 1.

Let a PTN be given, and let $\mathcal{W}$ be the set of all paths in the PTN.
A _fare system_ is a function $p:\mathcal{W}\to\mathbb{R}_{\geq 0}$ that
assigns a price to every path in the PTN.

For a path $W=(x_{1},\ldots,x_{n})$, we denote a subpath
$(x_{i},\ldots,x_{j})$ with $1\leq i\leq j\leq n$ by $[x_{i},x_{j}]$. The
price of a subpath is hence given as $p([x_{i},x_{j}])$. The brackets
$[\cdot]$ emphasize that $[x_{i},x_{j}]$ describes a path and not only a pair
of stations. Furthermore, let $W_{1}+W_{2}$ denote the concatenation of paths
$W_{1}$ and $W_{2}$.

Next, we specify with which combinations of tickets a passenger can travel
(legally) along a given path $W$: The straightforward way is to pay for the
whole path $W$. But it may also be possible to pay for a longer path
$H_{1}\supseteq W$ and use the ticket only for the subpath $W$, or to split
$W$ into $W_{1}+W_{2}$ and use two tickets, namely for $W_{1}$ and for $W_{2}$
instead of one ticket for the whole path $W$. The general definition is the
following.

######  Definition 2.

A finite sequence of paths $T=(H_{1},\ldots,H_{t})$ with
$H_{j}\in\mathcal{W}$, $j\in\\{1,\ldots,t\\}$, is a _ticket_ of a path
$W\in\mathcal{W}$ if there is a partition of $W$ into subpaths
$W_{1},\ldots,W_{t}$ such that ${W=W_{1}+\ldots+W_{t}}$ and $W_{j}$ is a
subpath of $H_{j}$, $j\in\\{1\ldots,t\\}$. The _price_ of a ticket
$T=(H_{1},\ldots,H_{t})$ is given by
${p(T)\mathrel{\vcentcolon=}\sum_{j=1}^{t}p(H_{j})}$.

For a given path $W$, the ticket $T=(W)$ is the _standard ticket_ ,
$T=(H_{1})$ with $W\subseteq H_{1}$ is an _elongated ticket_ and
$T=(W_{1},W_{2})$ with $W_{1}+W_{2}=W$ is a _compound ticket_.

Our goal is to find cheapest tickets and cheapest standard tickets to travel
from a station $x$ to another station $y$. A path with a cheapest standard
ticket from $x$ to $y$ is called a _cheapest path_ between those stations.

######  Example 3.

In order to illustrate the previous definition, we consider the PTN depicted
in Figure 1. Let $W=(x_{1},x_{2},x_{3},x_{7},x_{6})$ (dashed) be the path
along which we travel. Then there are several feasible tickets. For example,
the standard ticket is given by $T_{1}=(W)$, the ticket
$T_{2}=(W+(x_{6},x_{5}))$ is an elongated ticket,
${T_{3}=((x_{1},x_{2},x_{3}),(x_{3},x_{7},x_{6}))}$ is a compound ticket, and
a combination of both is given by
$T_{4}=((x_{1},x_{2},x_{3},x_{4}),(x_{5},x_{3},x_{7}),(x_{7},x_{6}))$, where
$W_{1}=(x_{1},x_{2},x_{3})$, $W_{2}=(x_{3},x_{7})$ and $W_{3}=(x_{7},x_{6})$.
The last case could, for example, be relevant if $x_{5}-x_{3}-x_{7}$ is a
railway line with an especially cheap ticket.

Figure 1: PTN for Example 3.

Note that Definition 2 can be further generalized, e.g., by allowing
$W_{i},W_{j}\subseteq H_{k}$ for the same path $H_{k}$ (which then has to be
paid only once) or by switching the order of the $H_{k}$. It can be shown that
these relaxations can be neglected when searching for cheapest tickets between
two stations as long as the no-elongation property holds.

We now define the no-stopover property and the no-elongation property
formally. Let a fare system $p$ on a PTN $(V,E)$ be given.

######  Definition 4.

A fare system $p$ satisfies the no-stopover property if

$p([x_{1},x_{n}])\leq p([x_{1},x_{i}])+p([x_{i},x_{n}])$

for all paths $(x_{1},\ldots,x_{n})\in\mathcal{W}$, $n\geq 3$, and all
intermediate stations $x_{i}$ with ${i\in\\{2,\ldots,n-1\\}}$.

The no-stopover property says that a compound ticket
$([x_{1},x_{i}],[x_{i},x_{n}])$ is never preferable to the standard ticket
$([x_{1},x_{n}])$, i.e., splitting the ticket or making a stopover does never
decrease the ticket price. Also multiple stopovers of a single path are not
favorable, since for several stopovers at $x_{i_{1}},\ldots,x_{i_{k}}$, we
have that

$\underbrace{\underbrace{p([x_{1},x_{i_{1}}])+p([x_{i_{1}},x_{i_{2}}])}_{\geq
p([x_{1},x_{i_{2}}])}+p([x_{i_{2}},x_{i_{3}}])}_{\geq([x_{1},x_{i_{3}}])}+\cdots+p([x_{i_{k}},x_{n}])\geq
p([x_{1},x_{n}]).$

######  Definition 5.

A fare system $p$ satisfies the no-elongation property if
$p([x_{1},x_{n-1}])\leq p([x_{1},x_{n}])$ for all paths
$(x_{1},\ldots,x_{n})\in\mathcal{W}$, $n\geq 2$.

The no-elongation property says that, given a path, an elongated ticket is not
preferable to a standard ticket, i.e., $p(W)\leq p(H_{1})$ for $W\subseteq
H_{1}\in\mathcal{W}$. This is because for every path $(x_{1},\ldots,x_{n})$
with a subpath $[x_{i},x_{j}]$, $1\leq i\leq j\leq n$, we have
$p([x_{1},x_{n}])\geq p([x_{1},x_{n-1}])\geq\ldots\geq p([x_{1},x_{j}])$ and
${p([x_{1},x_{j}])\geq p([x_{2},x_{j}])\geq p([x_{i},x_{j}])}$ by considering
the reverse paths.

In Section 3, we will see that the no-stopover property does not imply the no-
elongation property, and Section 4.2 will show that the inverse implication
does also not hold.

Observe that the price of a cheapest ticket can be smaller than the price of a
cheapest standard ticket. However, if the no-stopover and the no-elongation
property both hold, both problems are equivalent in the following sense:

######  Theorem 6.

If a fare system satisfies the no-stopover and the no-elongation property,
then the standard ticket $T=(W)$ is a cheapest ticket for every path
$W\in\mathcal{W}$.

In particular, a cheapest standard ticket between two nodes is also a cheapest
ticket.

###### Proof.

Let a fare system $p$ be given for which the no-stopover and the no-elongation
property are satisfied. Further, let $T=(H_{1},\ldots,H_{t})$ be a ticket for
the path $W\in\mathcal{W}$. We show that the standard ticket of $W$ does not
cost more than $T$.

Let $W=W_{1}+\ldots+W_{t}$ be a decomposition such that $W_{j}$ is a subpath
of $H_{j}$, ${j\in\\{1,\ldots,n\\}}$. Due to the no-elongation property, we
have that $p(W_{j})\leq p(H_{j})$. The standard ticket of $W$ is
${T^{\prime}=(W)=(W_{1}+\ldots+W_{t})}$. Due to the no-stopover property, it
holds that

$p(T^{\prime})=p(W_{1}+\ldots+W_{t})\stackrel{{\scriptstyle\text{no-
stopover}}}{{\leq}}p(W_{1})+\ldots+p(W_{t})\stackrel{{\scriptstyle\text{no-
elongation}}}{{\leq}}p(H_{1})+\ldots p(H_{t})=p(T).$

Hence, the standard ticket $T^{\prime}$ of $W$ is at least as cheap as the
ticket $T$. ∎

In other words, if both the no-elongation and the no-stopover property hold,
there always exists a cheapest possibility to travel from $x$ to $y$ which can
be realized by a standard ticket, i.e., by a cheapest path $[x,y]$ for which
the passenger buys one single ticket with price $p([x,y])$. Consequently,
under the assumptions of the theorem, we only need to consider standard
tickets in order to determine a cheapest ticket. This will be used later on
and simplifies the situation.

##  3 Distance-based Tariffs

For distance-based tariffs, the price of a journey depends on the kilometers
traveled. In a _distance tariff_ the length of the path is used, while in a
_beeline tariff_ the airline distance is the basis for the ticket price. We
use $l(W)$ to denote the length of a path $W=(x_{1},\ldots,x_{n})$ (in
kilometers), and $l_{2}(W)=\|x_{n}-x_{1}\|$ as its beeline distance. In order
to compute $l(W)$, we assume that each edge in the PTN has assigned its
physical length. For the beeline distance, we assume that the stations $V$ of
the PTN are embedded in the plane such that the Euclidean distance $l_{2}$
between every pair of stations can be computed.

######  Definition 7.

Let a PTN be given, and let $\mathcal{W}$ be the set of all paths in the PTN.
A fare system $p$ is a _distance tariff_ w.r.t. $\bar{p},f\geq 0$ if
$p(W)=f+\bar{p}\cdot l(W)$ for all $W\in\mathcal{W}$.

######  Definition 8.

Let a PTN be given, and let $\mathcal{W}$ be the set of all paths in the PTN.
A fare system $p$ is a _beeline tariff_ w.r.t. $\bar{p},f\geq 0$ if
$p(W)=f+\bar{p}\cdot l_{2}(W)$ for all $W\in\mathcal{W}$.

Note that in case of $\bar{p}=0$, both the distance tariff and the beeline
tariff become a _flat tariff_ (also called _unit tariff_), in which all paths
cost the same. Most railway systems rely on distance tariffs (or
modifications). Beeline tariffs are rather new and often used for mobile
tickets on mobile phones which track the journey of a passenger by using her
GPS coordinates and determining the price based on the beeline distance after
the journey is over.

We start by analyzing the distance tariff.

######  Theorem 9.

Let $p$ be a distance tariff w.r.t. $f,\bar{p}$. Then $p$ satisfies the no-
stopover and the no-elongation property.

###### Proof.

For the no-stopover property consider a path $W=(x_{1},\ldots,x_{n})$ with a
compound ticket $([x_{1},x_{i}],[x_{i},x_{n}])$, $i\in\\{2,\ldots,n-1\\}$.
Since $l(W)=l([x_{1},x_{i}])+l([x_{i},x_{n}])$, we know that
${p([x_{1},x_{i}])+p([x_{i},x_{n})]=2f+\bar{p}\cdot l([x_{1},x_{n}])\geq
p([x_{1},x_{n}])}$, hence the no-stopover property holds.

For the no-elongation property note that $l([x_{1},x_{n-1}])\leq
l([x_{1},x_{n}])$. Consequently, the inequality ${p([x_{1},x_{n-1}])\leq
p([x_{1},x_{n}])}$ is satisfied. ∎

For the distance tariff, we have for any pair of paths
$W_{1},W_{2}\in\mathcal{W}$ that $l(W_{1})\leq l(W_{2})$ is equivalent to
${p(W_{1})\leq p(W_{2})}$ by definition. Hence, a shortest path is always a
cheapest path and vice versa. Hence, we can use any shortest path algorithm in
order to find a cheapest path. By Theorems 6 and 9, cheapest standard tickets
are also cheapest tickets in a distance tariff. In particular, this is also
true for flat tariffs.

######  Corollary 10.

For a distance tariff, a cheapest standard ticket and a cheapest ticket can be
computed in polynomial time.

For the beeline tariff, we use the Euclidean (airline) distance to determine
the price of a ticket. This means that the ticket price is only dependent on
the location of the start and end station, but not on the specific path to
travel between them. Consequently, _all_ paths between two stations $x$ and
$y$ are cheapest paths and hence can be found in polynomial time, e.g., by
breadth-first search.

######  Lemma 11.

For a beeline tariff, a cheapest standard ticket can be found in polynomial
time.

A beeline tariff only satisfies the no-stopover property.

######  Theorem 12.

Let $p$ be a beeline tariff w.r.t. $f,\bar{p}$. Then $p$ satisfies the no-
stopover property.

###### Proof.

The no-stopover property holds since the Euclidean distance satisfies the
triangle inequality, and hence $p([x_{1},x_{n}])\leq
p([x_{1},x_{i}])+p([x_{i},x_{n}])$ for all
$x_{1},x_{i},x_{n}\in\mathbb{R}^{2}$ independent of the specific path
$W=(x_{1},\ldots,x_{n})$. ∎

However, the no-elongation property is _not_ satisfied for the beeline tariff
in general as the following small example demonstrates.

######  Example 13.

Figure 2: PTN in which the no-elongation property is not satisfied for the
beeline tariff.

Consider any beeline tariff with $\bar{p}>0$ regarding the PTN depicted in
Figure 2 and the path $W=(x_{1},x_{2})$. The standard ticket $T=(W)$ costs
$f+5\cdot\bar{p}$, which is more than the price $f+4\cdot\bar{p}$ of the
elongated ticket $T^{\prime}=((x_{1},x_{2},x_{3}))$. Hence, the no-elongation
property is not fulfilled, even if going back to the start station is not
allowed.

In our example, passengers would save money by buying the elongated ticket
$T^{\prime}$, but leaving the bus already at station $x_{2}$. This is avoided
in practice since passengers are tracked by their mobile devices and hence
need to checkout at a station which is really visited.

We remark that instead of the Euclidean distance also other metrics can be
used, see [Urb20].

##  4 Zone Tariffs

_Zone tariffs_ combine the ideas of flat and distance tariffs. The whole
region is divided into _tariff zones_ and the length of a journey is
approximated by the number of zones it visits. For all journeys crossing the
same number of zones, the same price is charged. A flat tariff is applied
within a zone. We analyze the basic zone tariff with and without double
counting zones as well as two particularities, namely metropolitan zones and
overlap areas. The modeling is a little different for each of these
particularities.

###  4.1 Basic Zone Tariff

For modeling a basic zone tariff, we use the PTN. The geographical zones imply
a zone partition ${\mathcal{Z}}=\\{Z_{1},\ldots,Z_{K}\\}$ of the set of
stations $V$, i.e., $V=\bigcup_{i=1,\ldots,K}Z_{i}$ and the $Z_{i}$ are
pairwise disjoint. It can happen that an edge $e$ between two stations crosses
a zone without having a station in it. We call such a situation an _empty zone
on edge $e$_. In this case, we add a virtual node which is not actual a
station on edge $e$. Put in other words, we assume that the PTN $(V,E)$ does
not have empty zones on the edges, but some of the nodes in $V$ might be
virtual nodes. For each node $v\in V$, let
$\textrm{zones}(v)\subseteq{\mathcal{Z}}$ denote the zones to which node $v$
belongs. In the basic zone tariff, $\textrm{zones}(v)$ is a singleton, i.e.,
$|\textrm{zones}(v)|=1$. This zone assignment yields the _zone border weight_

$b(e)=b(x,y)\mathrel{\vcentcolon=}\begin{cases}0&\text{if }x,y\text{ are in
the same zone, i.e., }\textrm{zones}(x)=\textrm{zones}(y),\\\ 1&\text{
otherwise}\end{cases}$

for all edges $e=\\{x,y\\}\in E$. From that, we can derive for a path
$W\in\mathcal{W}$ the _zone function_

$z(W)\mathrel{\vcentcolon=}1+b(W),\mbox{ where
}b(W)\mathrel{\vcentcolon=}\sum_{e\in E(W)}b(e),$ (1)

which determines the number of zones which are visited by the path $W$. We
illustrate the way to count zones in Example 14.

######  Example 14.

(a)

(b)

(c)

Figure 3: PTNs with zones for Example 14.

Figure 3 shows three different PTNs with zone partitions. In Figures 3(b) and
3(c), there is an empty zone on edge $\\{x_{1},x_{3}\\}$. Hence, we add a
virtual node represented by the diamond-shaped node. In all three PTNs, the
respective path $W$ from $x_{1}$ to $x_{3}$ crosses two zone borders, hence
$z(W)=3$. Note that this is even true for the PTN in Figure 3(c) although
${\textrm{zones}(x_{1})=\textrm{zones}(x_{3})}$.

Another approach to model empty zones on edges instead of virtual nodes are
zone border weights larger than 1. This approach can be found in [SU20,
Urb20].

The results that we derive in the following are the same for both modeling
approaches. We give sufficient conditions for a fare system to satisfy the no-
stopover and no-elongation property. However, for a given zone tariff, it may
make a difference to analyze the original PTN which may include empty zones or
the one with virtual nodes for the no-stopover and no-elongation property if
it is not forbidden to choose a virtual node as start or end node or to split
a ticket there.

We now have the preliminaries to define a basic zone tariff.

######  Definition 15.

Let a PTN together with a zone partition ${\mathcal{Z}}$ be given, and let
$\mathcal{W}$ be the set of all paths in the PTN. A fare system $p$ is a
_basic zone tariff_ w.r.t. the price function $P\colon\mathbb{N}_{\geq
1}\rightarrow\mathbb{R}_{\geq 0}$ if $p(W)=P(z(W))$ for all $W\in\mathcal{W}$
where $z$ is defined as in (1).

The price function $P$ assigns a ticket price to every number of visited
zones. If it is constant, the zone tariff simplifies to a flat tariff. As we
will see, the properties of a zone tariff depend crucially on the price
function $P$.

######  Theorem 16.

Let a price function $P\colon\mathbb{N}_{\geq 1}\rightarrow\mathbb{R}_{\geq
0}$ be given. All basic zone tariffs w.r.t. $P$ satisfy the no-stopover
property if and only if

$P(k)\leq P(i)+P(k-i+1)\mbox{ for all }k\in\mathbb{N}_{\geq
1},i\in\\{1,\ldots,k\\}.$ (2)

In particular, if all basic zone tariffs w.r.t. $P$ satisfy the no-stopover
property, then the increase of the price function is bounded by
$P(k)\leq(k-1)P(2)$ for $k\geq 2$.

###### Proof.

First, we assume that (2) does not hold for some $k$ and $i$. Note that
$i\notin\\{1,k\\}$ since ${P(k)\leq P(1)+P(k)}$ is always true. We consider
the basic zone tariff w.r.t. $P$ for the PTN depicted in Figure 4. In the
induced basic zone tariff, the standard ticket of the path
$(x_{1},\ldots,x_{k})$ costs $P(k)$, whereas the compound ticket
$([x_{1},x_{i}],[x_{i},x_{k}])$ costs $P(i)+P(k-i+1)$, which is cheaper by
assumption. Hence, the no-stopover property is not satisfied.

Figure 4: PTN with zones for Theorem 16.

Now, we suppose that (2) holds. Let $p$ be any basic zone tariff w.r.t. $P$.
For a path ${W\in\mathcal{W}}$, we define $k\mathrel{\vcentcolon=}z(W)$ and
let $(W_{1},W_{2})$ be a corresponding compound ticket. It holds that
${z(W_{1})+z(W_{2})=k+1}$, i.e., ${z(W_{2})=k-z(W_{1})+1}$. By assumption it
holds

$p(W)=P(k)\leq P(z(W_{1}))+P(k-z(W_{1})+1)=p(W_{1})+p(W_{2}).$

Thus, the no-stopover property is satisfied.

For the second part of the theorem, let the no-stopover property be satisfied
for all basic zone tariffs w.r.t. $P$. Due to the first part of this proof, we
know that (2) holds, in particular for $i=2$, i.e., we have $P(k)\leq
P(2)+P(k-1)$ for all $k\geq 2$. We prove the claim by induction over $k$. For
$k=2$, the inequality is clearly fulfilled. For $k\geq 3$, we have

$P(k)\leq P(2)+P(k-1)\leq P(2)+(k-2)P(2)=(k-1)P(2).$

This proves the claim. ∎

Theorem 16 has an interesting interpretation, mathematically and from a
transport point of view. Define the _zone border price function_
$\tilde{P}\colon\mathbb{N}_{\geq 1}\to\mathbb{R}_{\geq 0},\ k\mapsto P(k+1)$
as the function which maps the number of crossed zone borders to the price of
the path. Then we have the following corollary.

######  Corollary 17.

All basic zone tariffs w.r.t. $P$ satisfy the no-stopover property if and only
if the zone border price function $\tilde{P}$ is subadditive.

###### Proof.

The function $\tilde{P}$ is subadditive if and only if
$\tilde{P}(i+k)\leq\tilde{P}(i)+\tilde{P}(k)$ for all $i,k$ which is the case
if and only if $P(i+k-1)\leq P(i)+P(k)$ for all $k,i$ which in turn is
equivalent to (2). ∎

We also remark that (2) holds if and only if the condition is satisfied for
all $k\in\mathbb{N}_{\geq 3}$ and
${i\in\\{2,\ldots,\lfloor\frac{k+1}{2}\rfloor\\}}$, hence the number of cases
to be checked can be decreased.

######  Example 18.

We provide some examples:

  * •

In the unrealistic case that the price function $P$ is decreasing, every zone
tariff w.r.t. $P$ satisfies the no-stopover property.

  * •

For general increasing price functions, the no-stopover property need not be
satisfied. An example is a zone tariff in which a path passes through three
consecutive zones and in which the zone prices are $P(1)=1,P(2)=2$ and
$P(3)=5$.

  * •

However, if the price function $P$ is affine and increasing, i.e., if
$P(k)=f+k\cdot\bar{p}$ with $\bar{p}\geq 0$ and $f\geq-\overline{p}$, then
every zone tariff w.r.t. $P$ satisfies the no-stopover property. This is a
realistic choice of prices for a zone tariff.

For the no-elongation property, there is the following criterion.

######  Theorem 19.

Let a price function $P$ be given. All basic zone tariffs w.r.t. $P$ satisfy
the no-elongation property if and only if $P$ is increasing.

###### Proof.

Let $p$ be a basic zone tariff with respect to an increasing price function
$P$. Note that for a path ${W=(x_{1},\ldots,x_{n})\in\mathcal{W}}$, $n\geq 2$,
we have that $z([x_{1},x_{n-1}])\leq z(W)$. Since $P$ is increasing, we obtain
that $p([x_{1},x_{n-1}])=P(z([x_{1},x_{n-1}]))\leq P(z(W))=p(W)$.

If $P$ is not increasing, there is some $k\in\mathbb{N}_{\geq 2}$ such that
$P(k)<P(k-1)$. Consider a basic zone tariff w.r.t. $P$ in which there is a
path $(x_{1},\ldots,x_{k})$ with $z([x_{1},x_{k}])=k$ and
$z([x_{1},x_{k-1}])=k-1$. Then we have
$p([x_{1},x_{k}])=P(k)<P(k-1)=p([x_{1},x_{k-1}])$, and the no-elongation
property is not satisfied in this zone tariff. ∎

We now turn our attention to cheapest (standard) tickets. First, note that
cheapest paths need not exist in the case of a price function which contains a
strictly decreasing sequence of zone prices $P(i_{k})>P(i_{k+1})$,
$(i_{k})_{k\in N}\subseteq\mathbb{N}_{\geq 1}$, see [SU20]. If the price
function $P(k)$ becomes constant for $k\geq K$, then cheapest paths always
exist. Still, there might be cheapest standard tickets with large detours
compared to a shortest path. All these situations are avoided if the price
function is increasing. However, even then, a cheapest path need not be unique
and there might be two cheapest paths visiting different numbers of zones.

######  Theorem 20.

Let $p$ be a basic zone tariff with an increasing price function $P$, and let
$W$ be a path between $x,y\in V$.

  * •

If $W$ visits a minimum number of zones, it is a cheapest path from $x$ to
$y$.

  * •

If $P$ is strictly increasing, then $W$ is a cheapest path from $x$ to $y$ if
and only if $W$ visits a minimum number of zones.

In both cases, the corresponding cheapest standard ticket $T=(W)$ is also a
cheapest ticket if $p$ satisfies the no-stopover property.

###### Proof.

The first part is clear due to the monotonicity of $P$. For the second part,
we have ${P(k)<P(k+1)}$ for all $k\geq 1$. Hence, an $x$-$y$-path is cheapest
if and only if it visits a minimum number of zones. Lastly, the price function
is increasing, i.e., the no-elongation property holds by Theorem 19. If also
the no-stopover property is satisfied, then a cheapest standard ticket is a
cheapest ticket by Theorem 6. ∎

In the case of an increasing price function, we can hence find a cheapest path
by shortest path techniques in the PTN with zone border weights as described
in Algorithm 1.

1

Input : PTN $(V,E)$, two stations $x,y\in V$

Output : $x$-$y$-path $W$

2 Compute a shortest $x$-$y$-path $W$ in the PTN by applying a shortest path
algorithm using the zone border weight $b(e)$ as edge weight for $e\in E$.

return $W$

Algorithm 1 Basic zone tariff: finding a cheapest path.

######  Corollary 21.

Let $p$ be a basic zone tariff with an increasing price function.

  * •

Algorithm 1 finds a cheapest path and hence a cheapest standard ticket in
polynomial time.

  * •

If (2) holds, Algorithm 1 yields a cheapest ticket in polynomial time.

###### Proof.

The claim follows from Theorems 16 and 20 and from the fact that shortest path
algorithms, e.g., Dijkstra, run in polynomial time. ∎

We remark that the number of nodes and edges in the graph in Algorithm 1 can
be decreased by contracting edges with zone border weight $b(e)=0$ yielding
the so-called _zone graph_ , see [HS04, Urb20].

###  4.2 Zone Tariff with Metropolitan Zone

Many zone tariffs include particularities. A common one is the definition of
metropolitan zones in which a subset of zones
${\mathcal{Z}}_{M}\subseteq{\mathcal{Z}}$ is combined to a common zone
$Z_{M}=\bigcup_{Z\in{\mathcal{Z}}_{M}}Z$, the _metropolitan zone_. For
journeys which cross the metropolitan zone or start or end there, the zones
are counted as in the basic zone tariff. For journeys within the metropolitan
zone, a special price is fixed. A higher price might be charged if the
metropolitan zone has a well-developed public transport network or is much
larger than a usual zone. A lower price might be chosen in order to make
public transport more attractive, e.g., in city regions to reduce the car
traffic.

Again, we assume that there are no empty zones on edges, otherwise we add
virtual nodes in the same way as in Section 4.1. We say that a path
$W=(x_{1},\ldots,x_{n})\in\mathcal{W}$ is _included in the metropolitan zone
$Z_{M}$_ if $x_{i}\in Z_{M}$ for all $i\in\\{1,\ldots,n\\}$.

The formal definition of this fare system is as follows:

######  Definition 22.

Let a PTN with a zone partition ${\mathcal{Z}}$ and a metropolitan zone
$Z_{M}$ be given, and let $\mathcal{W}$ be the set of all paths in the PTN. A
fare system $p$ is a _zone tariff with metropolitan zone_ $Z_{M}$, a price
function $P\colon\mathbb{N}_{\geq 1}\rightarrow\mathbb{R}_{\geq 0}$ and a
metropolitan price $P_{M}\in\mathbb{R}_{\geq 0}$ if we have for every path
$W\in\mathcal{W}$ that

$p(W)=\begin{cases}P_{M}\qquad&\text{if $W$ is included in the metropolitan
zone $Z_{M}$,}\\\ P(z(W))\qquad&\text{otherwise (where $z$ is defined as
in\leavevmode\nobreak\ \eqref{eq-z})}.\end{cases}$

Note that zone tariffs with several metropolitan zones are also possible (and
can be defined as above). Paths traveling through a metropolitan zone may also
be treated in other ways, e.g., the metropolitan zone always counts as two
zones, see [Urb20].

In order to simplify our analysis, we make the following assumptions:

  * •

the price function $P\colon\mathbb{N}_{\geq 1}\rightarrow\mathbb{R}_{\geq 0}$
is increasing,

  * •

the underlying basic zone tariff satisfies the no-stopover property,

  * •

the metropolitan zone contains at least one station and is connected
(otherwise we could divide zones into their connected components and reproduce
the same setting just with several connected metropolitan zones instead of
one).

We first provide an example that the no-stopover property need not be
satisfied for zone tariffs with metropolitan zones although it is satisfied
for the underlying basic zone tariffs.

######  Example 23.

Figure 5: PTN with zones for Example 23.

Consider the PTN depicted in Figure 5. The zones highlighted in gray form a
metropolitan zone. Let $P\colon\mathbb{N}_{\geq 1}\rightarrow\mathbb{R}_{\geq
0},\ k\mapsto k$ be a linear price function, i.e., it satisfies the no-
stopover property, see Example 18. Let $P_{M}\mathrel{\vcentcolon=}P(2)=2$.
The path $(x_{1},x_{2},x_{3},x_{4},x_{5},x_{6})$ costs
$p([x_{1},x_{6}])=P(6)=6$ with a standard ticket, but only
${p([x_{1},x_{2}])+p([x_{2},x_{6}])=P(2)+P_{M}=4}$ with the compound ticket
$((x_{1},x_{2}),(x_{2},\ldots,x_{6}))$, which benefits from the metropolitan
zone.

Note that the situation described above occurs in real-world, e.g., in the
Verkehrsverbund Rhein-Neckar, see [Urb20]. In order to analyze in which cases
the no-stopover property nevertheless holds, we define the _maximum
metropolitan zone distance_ $D_{\max}$ by

$D_{\max}\mathrel{\vcentcolon=}\max_{x,y\in Z_{M}}\ \
\min_{x\text{-}y\text{-}\text{paths }W\text{ included in }Z_{M}}z(W).$

The value of $D_{\max}$ depends on the PTN (including the metropolitan zone)
and is always finite due to our assumption that $Z_{M}$ contains at least one
station and is connected. We remark that $D_{\max}$ can be larger than the
number of zones belonging to the metropolitan zone, see Figure 6, where three
zones belong to a metropolitan zone, but $D_{\max}=4$. Further, we assume that
every passenger who travels within the metropolitan zone $Z_{M}$ uses a path
with a minimum number of zones. This yields $z(W)\leq D_{\max}$ for every path
$W$ included in $Z_{M}$. With this notation we state the following result:

Figure 6: $D_{\max}$ is larger than the number of zones in
${\mathcal{Z}}_{M}$.

######  Theorem 24.

Let an increasing price function $P$, a metropolitan price $P_{M}$, and an
integer ${d\in\mathbb{N}_{\geq 1}}$ be given. All zone tariffs with
metropolitan zone w.r.t. $P$ and $P_{M}$ on a PTN with $D_{\max}=d$ satisfy
the no-stopover property if and only if ${P(d+k)\leq P_{M}+P(k+1)}$ for all
$k\in\mathbb{N}_{\geq 1}$.

###### Proof.

First, assume that there is some $k$ such that $P(d+k)>P_{M}+P(k+1)$. Consider
the PTN depicted in Figure 7, where $D_{\max}=d$. In the induced zone tariff
with metropolitan zone, the standard ticket of the path
$(x_{1},\ldots,x_{d+k})$, which costs $P(d+k)$, is more expensive than the
compound ticket $([x_{1},x_{d}],[x_{d},x_{d+k}])$, which costs $P_{M}+P(k+1)$.

Conversely, we suppose that the inequalities are satisfied. Let a PTN with
$D_{\max}=d$ be given. We show that the induced zone tariff with metropolitan
zone satisfies the no-stopover property. By our assumptions, the no-stopover
property is fulfilled for the basic zone tariff. Furthermore, it is satisfied
for paths included in $Z_{M}$. Hence, we consider paths $W\in\mathcal{W}$
which are not included in $Z_{M}$, but allow to apply the metropolitan price
for a subpath by making one stopover. Such a path must start or end in
$Z_{M}$. Let $W$ consist of the subpaths $W_{1}$ and $W_{2}$ where $W_{1}$ is
included in $Z_{M}$ without loss of generality. We have $z(W_{1})\leq
D_{\max}=d$. Hence, it holds

$\displaystyle p(W)$
$\displaystyle=P(z(W))=P(z(W_{1})+z(W_{2})-1)\stackrel{{\scriptstyle P\text{
incr.}}}{{\leq}}P(d+z(W_{2})-1)$ $\displaystyle\leq
P_{M}+P(z(W_{2}))=p(W_{1})+p(W_{2})$

and the no-stopover property is satisfied.

Figure 7: PTN with zones for Theorem 24.

∎

######  Theorem 25.

Let an increasing price function $P$ and a price $P_{M}$ be given. Then all
zone tariffs with metropolitan zone w.r.t. $P$ and $P_{M}$ satisfy the no-
elongation property if and only if $P_{M}\leq P(2)$.

###### Proof.

Let $p$ be a zone tariff with metropolitan zone $Z_{M}$ w.r.t. $P$ and
$P_{M}$, and let ${W=(x_{1},\ldots,x_{n})\in\mathcal{W}}$, $n\geq 2$. We
distinguish three cases.

  * •

If $W$ is included in $Z_{M}$, then $p([x_{1},x_{n-1}])=P_{M}=p(W)$.

  * •

If $[x_{1},x_{n-1}]$ is included in $Z_{M}$, but $W$ is not, then $W$ visits
at least two zones and ${p([x_{1},x_{n-1}])=P_{M}\leq P(2)\leq p(W)}$ by
assumption. On the other hand, if $P_{M}>P(2)$ and $W$ visits exactly two
zones, we obtain $p([x_{1},x_{n-1}])=P_{M}>P(2)=p(W)$ and the no-elongation
property does not hold.

  * •

If $[x_{1},x_{n-1}]$ is not included in $Z_{M}$, then the prices of $W$ and
its subpath $[x_{1},x_{n-1}]$ are computed as in the basic zone tariff. Hence,
we have $p([x_{1},x_{n-1}])\leq p(W)$ by monotonicity of $P$ and Theorem 19. ∎

We can make use of the following lemma to find a cheapest path.

######  Lemma 26.

Let $p$ be a zone tariff with metropolitan zone with an increasing price
function $P$ and $P_{M}\leq P(3)$, and let $W$ be a path between $x,y\in V$.

  * •

If $W$ is included in $P_{M}$, then it is a cheapest path from $x$ to $y$.

  * •

If there does not exist an $x$-$y$-path included in $Z_{M}$, then $W$ is a
cheapest path from $x$ to $y$ if $W$ visits a minimum number of zones.

  * •

If $P$ is strictly increasing and there does not exist an $x$-$y$-path
included in $Z_{M}$, then $W$ is a cheapest path from $x$ to $y$ if and only
if $W$ visits a minimum number of zones.

In all cases, the corresponding cheapest standard ticket $T=(W)$ is a cheapest
ticket if ${P_{M}\leq P(2)}$ and $p$ satisfies the no-stopover property.

###### Proof.

Consider the first case in which $W$ is an $x$-$y$-path which is included in
the metropolitan zone. It costs $p(W)=P_{M}$. Any $x$-$y$-path that leaves the
metropolitan zone visits at least three zones and thus costs at least
$P(3)\geq P_{M}$. Hence, $W$ is a cheapest path. If there is no path within
the metropolitan zone, the price of a path is computed as in the basic zone
tariff and Theorem 20 can be applied.

If $P_{M}\leq P(2)$, then the no-elongation property is satisfied by Theorem
25. If also the no-stopover property holds, then a cheapest standard ticket is
a cheapest ticket by Theorem 6. ∎

We conclude that we can compute a cheapest path in polynomial time in this
case by Algorithm 2.

1

Input : PTN $(V,E)$, two stations $x,y\in V$

Output : $x$-$y$-path $W$

2 For each edge $e=\\{v,w\\}\in E$, define the metropolitan weight $z_{M}(e)$
by
$z_{M}(e)\mathrel{\vcentcolon=}z_{M}(v,w)\mathrel{\vcentcolon=}\begin{cases}0&\text{if
}v,w\in Z_{M},\\\ 1&\text{otherwise,}\end{cases}$ and compute a shortest
$x$-$y$-path in the PTN with $z_{M}(e)$ as edge weights.

3 if $\sum_{e\in E(W)}z_{M}(e)=0$ then

4 return $W$

5else

6 Apply Algorithm 1 for finding a cheapest path regarding the basic zone
tariff.

Algorithm 2 Zone tariff with metropolitan zone: finding a cheapest path.

######  Corollary 27.

Let $p$ be a zone tariff with metropolitan zone with an increasing price
function $P$.

  * •

If $P_{M}\leq P(3)$, Algorithm 2 finds a cheapest path and hence a cheapest
standard ticket in polynomial time.

  * •

If $P_{M}\leq P(2)$ and $p$ satisfies the no-stopover property, then Algorithm
2 yields a cheapest ticket in polynomial time.

###### Proof.

The metropolitan weight $z_{M}$ is chosen such that a path $W$ is included in
the metropolitan zone if and only if $\sum_{e\in E(W)}z_{M}(e)=0$. Hence, the
correctness follows from Lemma 26 and Corollary 21. The runtime is polynomial
due to Corollary 21 and because shortest path algorithms, e.g., Dijkstra, run
in polynomial time. ∎

The case $P_{M}>P(3)$ remains: Here, a cheapest $x$-$y$-path might leave the
metropolitan zone $Z_{M}$ although a path included in $Z_{M}$ exists, e.g., if
there exists a path from $x$ to $y$ which leaves the metropolitan zone and
visits three zones in total. Such a path can be determined in polynomial time
by solving the single-source shortest path (SSSP) problem twice, namely from
$x$ and from $y$ to all other nodes, then iterating over all edges leaving the
metropolitan zone, i.e., edges between a node in $Z_{M}$ and a node not in
$Z_{M}$, and complementing them with shortest paths to $x$ and $y$ in order to
gain an $x$-$y$-path which leaves the metropolitan zone, and then choosing the
smallest of these paths. By comparing the price of this path with a path
included in $Z_{M}$, we determine a cheapest path. However, in this case, the
no-elongation property does not hold and an elongated ticket might be cheaper
than the cheapest standard ticket.

We finally remark that due to Theorem 25 already for $P_{M}>P(2)$ the no-
elongation property is usually not satisfied. It is hence possible that a
cheapest ticket between ${x,y\in{\mathcal{Z}}_{M}}$ is an elongated ticket.
Such an elongated ticket can also be found in polynomial time as follows: One
computes a path $W$ from $x$ to $y$ and outgoing paths from $x$ and from $y$
to all other zones, each minimizing the number of visited zones. Then $W$ is
elongated by the shortest outgoing path.

###  4.3 Zone Tariff with Overlap Areas

Overlap areas, which allow stations to belong to several zones, are common in
practice. They are in particular used for stations near zone borders in order
to make traveling in border regions more passenger-friendly. This can be seen
in Figure 8 where station $x_{2}$ is in an overlap area (depicted by the
striped area) between the left and the right zone. A traveler from $x_{1}$ to
$x_{2}$ or a traveler from $x_{2}$ to $x_{4}$ visits only one zone. However, a
traveler from $x_{1}$ via $x_{2}$ to $x_{4}$ visits two zones.

In this section, we relax the requirement that the zones form a partition and
allow a cover instead. In particular, we may have stations (in overlap areas)
which belong to more than one zone. When determining the number of zones a
path visits, the zones for the stations in overlap areas are chosen in such a
way that the total number of visited zones of the path becomes minimal. As
before, we assume that there is at least one station in every zone (and in
every overlap area). In the following, we model this setting mathematically.

Given a zone cover ${\mathcal{Z}}$, let
$\textrm{zones}(v)\subseteq{\mathcal{Z}}$ with $|\textrm{zones}(v)|\geq 1$ be
the set of zones to which station $v$ may be assigned. For a path
$W=(x_{1},\ldots,x_{n})$, let $h\colon\\{1,\ldots,n\\}\to{\mathcal{Z}}$ with
$h(i)\in\textrm{zones}(x_{i})$ be the function that assigns a zone to each
station in the path. This assignment determines the zone border weights for
any edge $\\{x_{i},x_{i+1}\\}$, $i\in\\{1,\ldots,n-1\\}$, on the path $W$ as
follows:

$b^{h}(x_{i},x_{i+1})\mathrel{\vcentcolon=}\begin{cases}0&\text{if
}h(i)=h(i+1),\\\ 1&\text{otherwise.}\end{cases}$

For the path $W$, we now choose the assignment $h$ which minimizes the number
of zones that are visited by $W$, i.e.,

$z(W):=\min_{h}b^{h}(W)=\min_{h}\sum_{i=1}^{n-1}b^{h}(x_{i},x_{i+1}).$ (3)

The assignment of a station to a zone depends on the path which is shown in
the next example.

######  Example 28.

Figure 8: PTN with zones for Example 28.

Consider the PTN shown in Figure 8 with
${\textrm{zones}(x_{1})=\textrm{zones}(x_{3})=\\{L\\}}$,
${\textrm{zones}(x_{4})=\textrm{zones}(x_{5})=\\{R\\}}$ and
$\textrm{zones}(x_{2})=\\{L,R\\}$. The choice to which zone $x_{2}$ is
assigned is made separately for every occurrence on every path.

  * •

For $W=(x_{1},x_{2},x_{3})$, we assign $h(2)=L$ and receive
$z(W)=b^{h}(x_{1},x_{2})+b^{h}(x_{2},x_{3})+1=1$.

  * •

For $W=(x_{4},x_{2},x_{5})$, we assign $h(2)=R$ and again receive $z(W)=1$.

  * •

For $W=(x_{1},x_{2},x_{5})$, both possible assignments, i.e., $x_{2}$ in the
left or in the right zone, yield $z(W)=2$.

  * •

Finally, if a path visits $x_{2}$ twice, we may assign $x_{2}$ even to two
different zones as done for the path
$W=(x_{1},x_{2},x_{3},x_{4},x_{2},x_{5})$, where we assign $x_{2}$ to the left
zone for the first visit, i.e., $h(2)=L$, and to the right zone for the second
visit, i.e., $h(5)=R$, to receive

$\displaystyle z(W)$
$\displaystyle=b^{h}(x_{1},x_{2})+b^{h}(x_{2},x_{3})+b^{h}(x_{3},x_{4})+b^{h}(x_{2},x_{4})+b^{h}(x_{2},x_{5})+1$
$\displaystyle=0+0+1+0+0+1=2.$

######  Definition 29.

Let a PTN together with a zone cover ${\mathcal{Z}}$ be given, and let
$\mathcal{W}$ be the set of all paths in the PTN. A fare system $p$ is a _zone
tariff with overlap areas (ZOA)_ with respect to an increasing price function
${P\colon\mathbb{N}_{\geq 1}\rightarrow\mathbb{R}_{\geq 0}}$ if $p(W)=P(z(W))$
for all paths $W\in\mathcal{W}$ where $z$ is defined as in (3).

Note that for each path $W$ the minimal assignment $h$ is fixed and the price
for $W$ is then computed as a basic zone tariff. The minimal assignment
$h^{\prime}$ of a subpath $W^{\prime}\subseteq W$ may differ from the
restriction $h|_{W^{\prime}}$. Therefore, properties of the basic zone tariff
cannot be transferred straightforwardly. Nevertheless, we always have
$z(W^{\prime})\leq z(W)$.

######  Theorem 30.

Let an increasing price function $P$ be given. All ZOAs w.r.t. $P$ satisfy the
no-stopover property if and only if $P$ is subadditive.

###### Proof.

Figure 9: PTN with zones for Theorem 30.

First assume that there are $k_{1},k_{2}\in\mathbb{N}_{\geq 1}$ such that
$P(k_{1}+k_{2})>P(k_{1})+P(k_{2})$. We define
${k\mathrel{\vcentcolon=}k_{1}+k_{2}}$ and consider the PTN depicted in Figure
9. The striped area is an overlap area so that station $v$ belongs to both
neighboring zones. In the induced ZOA, the path
${W=(x_{1},\ldots,x_{k_{1}},v,y_{1},\ldots,y_{k_{2}})}$ costs
$p(W)=P(z(W))=P(k)$ no matter if we assign $v$ to the left or to the right
zone. Regarding the two subpaths $W_{1}=(x_{1},\ldots,x_{k_{1}},v)$ and
$W_{2}=(v,y_{1},\ldots,y_{k_{2}})$, we assign $v$ to the left zone to
determine the number of zones for $W_{1}$ and to the right zone for $W_{2}$.
This means, the compound ticket $(W_{1},W_{2})$ costs
${p(W_{1})+p(W_{2})=P(z(W_{1}))+P(z(W_{2}))=P(k_{1})+P(k_{2})}$, which is
cheaper than the standard ticket. Therefore, the no-stopover property is not
satisfied.

Conversely, we suppose that $P$ is subadditive. Let $p$ be a ZOA w.r.t. $P$,
and let $W\in\mathcal{W}$ be a path with a corresponding compound ticket
$(W_{1},W_{2})$. We set $k\mathrel{\vcentcolon=}z(W)$,
$k_{1}\mathrel{\vcentcolon=}z(W_{1})$ and
$k_{2}\mathrel{\vcentcolon=}z(W_{2})$. Then we have that either
$k_{1}+k_{2}=k+1$ or $k_{1}+k_{2}=k$ because the minimal assignment for $W$
might only differ in stations in the end zone of $W_{1}$ or in the start zone
of $W_{2}$ from the minimal assignments for $W_{1}$ and $W_{2}$, and hence it
decreases the number of visited zones by at most 1. Due to minimality of the
assignments, the assignment of all other stations is not changed. In case that
$k_{1}+k_{2}=k$, it holds that

$p(W)=P(k)\stackrel{{\scriptstyle P\text{
subadd.}}}{{\leq}}P(k_{1})+P(k_{2})=p(W_{1})+p(W_{2}).$

Hence, consider the case that $k_{1}+k_{2}=k+1$. It holds that

$p(W)=P(k)\stackrel{{\scriptstyle P\text{
incr.}}}{{\leq}}P(k+1)\stackrel{{\scriptstyle P\text{
subadd.}}}{{\leq}}P(k_{1})+P(k_{2})=p(W_{1})+p(W_{2}).$

Therefore, the no-stopover property is satisfied. ∎

Analogously to Theorems 19 and 20 for the basic zone tariff, we get the
following results:

######  Theorem 31.

Let a price function $P$ be given. All ZOAs w.r.t. $P$ satisfy the no-
elongation property if and only if $P$ is increasing.

######  Lemma 32.

Let $p$ be a ZOA, and let $W$ be a path between $x,y\in V$.

  * •

If $W$ visits a minimum number of zones, i.e., it is an $x$-$y$-path which
minimizes $z(W)$, it is a cheapest path from $x$ to $y$.

  * •

If $P$ is strictly increasing, then $W$ is a cheapest path from $x$ to $y$ if
and only if $W$ visits a minimum number of zones.

In both cases, the corresponding cheapest standard ticket $T=(W)$ is also a
cheapest ticket if $p$ satisfies the no-stopover property.

In (3) and hence in Definition 29 a _minimal_ assignment is needed.
Enumerating all possible assignments would lead to an exponential search. In
the following, we show how such an assignment and even more a cheapest path
for a ZOA can be computed in polynomial time. To this end we construct a new
graph, namely the overlaps-resolved graph, in which we resolve the overlap
areas by creating new nodes and adding edge weights that represent the number
of crossed zone borders.

######  Definition 33.

Let a PTN $(V,E)$ together with a zone cover ${\mathcal{Z}}$ be given. The
_overlaps-resolved graph_ $G^{\prime}=(V^{\prime},E^{\prime})$ is defined by

$\displaystyle V^{\prime}$ $\displaystyle\mathrel{\vcentcolon=}V\cup V_{\cal
Z}\ \mbox{ with }\ V_{\cal Z}\mathrel{\vcentcolon=}\\{(x,Z)\in
V\times{\mathcal{Z}}:Z\in\textrm{zones}(x)\\},$ $\displaystyle E^{\prime}$
$\displaystyle\mathrel{\vcentcolon=}\underbrace{\\{\\{x,(x,Z)\\}:x\in
V,(x,Z)\in V_{\cal
Z}\\}}_{\mathrel{\vcentcolon=}E^{\prime}_{1}}\cup\underbrace{\\{\\{(x,Z_{1}),(y,Z_{2})\\}\in
V_{\cal Z}\times V_{\cal Z}:\\{x,y\\}\in
E\\}}_{\mathrel{\vcentcolon=}E^{\prime}_{2}}.$

with weights

$b^{\prime}(e)\mathrel{\vcentcolon=}\begin{cases}1&\text{if }e\in
E^{\prime}_{1},\\\ 0&\text{if }e=\\{(x,Z_{1}),(y,Z_{2})\\}\in
E^{\prime}_{2}\text{ and }Z_{1}=Z_{2}\\\ 1&\text{if
}e=\\{(x,Z_{1}),(y,Z_{2})\\}\in E^{\prime}_{2}\text{ and }Z_{1}\neq
Z_{2}.\end{cases}$

Note that for $e=\\{(x,Z_{1}),(y,Z_{2})\\}$ and an assignment $h$ with
$h(x)=Z_{1},h(y)=Z_{2}$, we have $b^{\prime}(e)=b^{h}(x,y)$.

With $k_{v}:=|\textrm{zones}(v)|$ for $v\in V$, the number of nodes and edges
in $G^{\prime}$ is $|V^{\prime}|=|V|+\sum_{v\in V}k_{v}$ and
$|E^{\prime}|=\sum_{v\in V}k_{v}+\sum_{(v,w)\in E}k_{v}\cdot k_{w}$. This
means they increase linearly and quadratically in the maximal number
$k_{\max}\mathrel{\vcentcolon=}\max_{v\in V}k_{v}$ of zones to which one
station $v$ may belong:
${|V^{\prime}|\in\mathcal{O}\bigl{(}|V|\cdot(k_{\max}+1)\bigr{)}}$ and
${|E^{\prime}|\in\mathcal{O}(k_{\max}\cdot|V|+k_{\max}^{2}|E|)}$. This is
polynomial in the input $(V,E,{\mathcal{Z}})$ since
$k_{\max}\leq|{\mathcal{Z}}|$. In practice, $k_{\max}$ is usually small, often
even $k_{\max}\leq 2$. Note that the number of nodes and edges can be
decreased by removing the node $v$ if $k_{v}=1$ which in practice happens in
most cases.

######  Example 34.

(a)

(b)

Figure 10: Construction of an overlaps-resolved graph for Example 34.

We have a look at the construction of an overlaps-resolved graph in the
example depicted in Figure 10. In 10(a) we have a PTN with
$\textrm{zones}(x)={L}$, ${\textrm{zones}(v)=\\{L,R\\}}$ and
${\textrm{zones}(y)={R}}$. In 10(b) the corresponding overlaps-resolved graph
is shown. The edges in $E^{\prime}_{1}$ are dashed and have weight 1. Since
$v$ belongs to two zones, it is represented by two nodes $(v,L),(v,R)$ in the
overlaps-resolved graph, where $(v,L)$ represents $v$ belonging to the left
zone and $(v,R)$ to the right zone. The node $v$ in $G^{\prime}$ allows us to
start or end a path in $v$ without considering each node $(v,Z)$,
$Z\in\textrm{zones}(v)$, as the start or end node or determining to which zone
$v$ should belong beforehand. The misuse of edges in $E^{\prime}_{1}$ is
prevented by their weight.

Now, we can apply any shortest path algorithm to the overlaps-resolved graph
$G^{\prime}$ corresponding to the PTN in order to compute paths that visit a
minimum number of zones for a ZOA as described in Algorithm 3. If the path is
already given and we are only interested in the minimal assignment, we can
also use Algorithm 3 where we reduce the PTN (and hence the overlaps-resolved
graph) to the given path $W$.

1

Input : overlaps-resolved graph $G^{\prime}=(V^{\prime},E^{\prime})$, two
stations $x,y\in V$

Output : $x$-$y$-path $W^{\prime}$ in $G^{\prime}$

2

3Compute a shortest $x$-$y$-path $W^{\prime}$ in $G^{\prime}$.

return $W^{\prime}$

Algorithm 3 ZOA: finding a cheapest path.

######  Lemma 35.

Let $p$ be a ZOA. Algorithm 3 yields a cheapest path $W$ from $x$ to $y$ in
polynomial time.

###### Proof.

Let $W^{\prime}=(x,v^{\prime}_{1},v^{\prime}_{2},\ldots,v^{\prime}_{K},y)$ be
the output of Algorithm 3. We first note that ${v^{\prime}_{i}\in V_{\cal Z}}$
for all $i\in\\{1,\ldots,K\\}$: Assume
$v\mathrel{\vcentcolon=}v^{\prime}_{i}\notin V_{\cal Z}$ for some $i$, so we
have $v\in V\setminus\\{x,y\\}$. Since the node $v$ is only incident to edges
in $E^{\prime}_{1}$, this means that $W^{\prime}$ contains a subpath
${W^{\prime\prime}\mathrel{\vcentcolon=}((w,Z_{1}),(v,Z_{2}),v,(v,Z_{3}))}$
with $\\{w,v\\}\in E^{\prime}_{2}$. Hence, also
$e^{\prime}:=\\{(w,Z_{1}),(v,Z_{3})\\}\in E^{\prime}_{2}$. Replacing the
subpath $W^{\prime\prime}$ in $W^{\prime}$ by $e^{\prime}$ leads to a new path
in $G^{\prime}$ with strictly smaller weight due to
$b^{\prime}(W^{\prime\prime})\geq 2>b^{\prime}(e^{\prime})$. This is a
contradiction to $W^{\prime}$ being a shortest path in $G^{\prime}$.

We now transfer $W^{\prime}$ to a path $W=(v_{1},\ldots,v_{K})$ in the PTN by
replacing $v^{\prime}=(v,Z)$ by the projection on its first component. This
yields $v_{1}=x,\ v_{K}=y$ and $\\{v_{i},v_{i+1}\\}\in E$ for all
${i\in\\{1,\ldots,K-1\\}}$ by definition of $E^{\prime}_{2}$. We hence receive
an $x$-$y$-path in the PTN together with an assignment $h_{1}$ which maps
$h_{1}(v)=Z$ if $v^{\prime}=(v,Z)\in W^{\prime}$. Due to the definition of the
edge weights in $G^{\prime}$, we get $b^{\prime}(W^{\prime})=b^{h_{1}}(W)+2$
adding the weights for the first and last edge in $W^{\prime}$, and $h_{1}$ is
a minimal assignment for $W$. It remains to show that it is a cheapest path.

Assume that $W^{*}=(w_{1},\ldots,w_{L})$ with $w_{1}=x$, $w_{2}=y$, is a
cheaper $x$-$y$-path in the PTN with the minimal assignment $h_{2}$, i.e.,
$b^{h_{2}}(W^{*})=z(W^{*})<z(W)=b^{h_{1}}(W)$. We lift $W^{*}$ to the path

${W^{*}}^{\prime}=\big{(}w_{1},(w_{1},h_{2}(w_{1})),(w_{2},h_{2}(w_{2})),\ldots,(w_{P},h_{2}(w_{L})),w_{L}\big{)}.$

Then $b^{\prime}({W^{*}}^{\prime})=b^{h_{2}}(W^{*})+2<b^{h_{1}}(W)+2$, a
contradiction to $W^{\prime}$ being a shortest path in $G^{\prime}$.

As shown above, the overlaps-resolved graph is polynomial in the input and
hence Algorithm 3 can be solved in polynomial time due to the polynomial
runtime of shortest path algorithms like Dijkstra. ∎

######  Corollary 36.

Let $p$ be a ZOA.

  * •

Algorithm 3 finds a cheapest path and hence a cheapest standard ticket in
polynomial time.

  * •

If $P$ is subadditive, then Algorithm 3 yields a cheapest ticket in polynomial
time.

###  4.4 Zone Tariff Without Double Counting

In this section, we study zone tariffs as they are usually implemented in
practice. In contrast to the basic zone tariff, each zone is only counted once
independent of how many times it is entered on a path. More precisely, the
price of a path is determined by the number of different zones visited along a
path. Again, we assume that there are no empty zones on edges, otherwise we
add virtual nodes in the same way as in Section 4.1.

As for the basic zone tariff, the set $\textrm{zones}(v)\subset Z$ with
$|\textrm{zones}(v)|=1$ denotes the zone to which station $v\in V$ belongs and
the set of resulting zones ${\mathcal{Z}}$ is a partition of $V$. However, in
a zone tariff without double counting, we need a different _zone function_
which we define for every path $W\in\mathcal{W}$ by counting the number of
_different_ zones which are visited by $W$, i.e.,

$\bar{z}(W):=|\bigcup_{x\in V(W)}\textrm{zones}(x)|.$ (4)

######  Definition 37.

Let a PTN together with a zone partition ${\mathcal{Z}}$ be given. Let
$\mathcal{W}$ be the set of all paths in the PTN. A fare system $p$ is a _zone
tariff without double counting_ w.r.t. a price function
$P\colon\mathbb{N}_{\geq 1}\rightarrow\mathbb{R}_{\geq 0}$ if
$p(W)=P(\bar{z}(W))$ for each path $W\in\mathcal{W}$ where $\bar{z}$ is
defined as in (4).

For a path that does not visit a zone more than once, the basic zone tariff
and the zone tariff without double counting coincide. Hence, many examples and
results from the basic zone tariff can be transferred to the zone tariff
without double counting. However, in contrast to the case for the basic zone
tariff, cheapest paths always exist for a zone tariff without double counting,
even if the price function is decreasing, as we show in the following lemma.

######  Lemma 38.

For a zone tariff without double counting, there always exist cheapest paths.

###### Proof.

Let $x,y\in V$ be stations in the PTN. Since we do not double count zones, the
number of visited zones of an $x$-$y$-path is bounded from above by the total
number of zones ${|{\mathcal{Z}}|\in\mathbb{N}_{\geq 1}}$ in the PTN. Let $M$
be the set of all prices that are possible for $x$-$y$-paths. We have
${M\subseteq\\{P(1),\ldots,P(|{\mathcal{Z}}|)\\}}$. Hence, $|M|<\infty$ and
$M$ admits a minimum. Therefore, there exists a cheapest $x$-$y$-path. ∎

Due to practical relevance, we again focus on increasing price functions.

######  Theorem 39.

Let an increasing price function $P$ be given. All zone tariffs without double
counting w.r.t. $P$ satisfy the no-stopover property if and only if (2) holds.

###### Proof.

If (2) does not hold for some k and i, then the no-stopover property does not
hold as shown in the proof of Theorem 16.

Conversely, let (2) hold. Let $p$ be any zone tariff without double counting
w.r.t. $P$. For a path $W\in\mathcal{W}$, we define
$k\mathrel{\vcentcolon=}\bar{z}(W)$ and let $(W_{1},W_{2})$ be a corresponding
compound ticket. Then $W_{1}$ and $W_{2}$ have at least one zone in common,
namely the zone in which we make the stopover. This is only counted once for
$W$. Therefore, we have $\bar{z}(W_{1})+\bar{z}(W_{2})\geq k+1$ which is
equivalent to $k-\bar{z}(W_{1})+1\leq\bar{z}(W_{2})$. With
$i\mathrel{\vcentcolon=}\bar{z}(W_{1})\leq k$, we conclude from (2) that

$p(W)=P(k)\leq P(i)+P(k-i+1)\leq
P(\bar{z}(W_{1}))+P(\bar{z}(W_{2}))=p(W_{1})+p(W_{2}).$

So the no-stopover property is satisfied. ∎

Theorems 19 and 20 about the no-elongation property and cheapest paths in the
basic zone tariff are analogously true for the zone tariff without double
counting, which yields the following results:

######  Theorem 40.

Let a price function $P$ be given. All zone tariffs without double counting
w.r.t. $P$ satisfy the no-elongation property if and only if $P$ is
increasing.

######  Lemma 41.

Let $p$ be a zone tariff without double counting with an increasing price
function $P$, and let $W$ be a path between $x,y\in V$.

  * •

If $W$ visits a minimum number of different zones, it is a cheapest path from
$x$ to $y$.

  * •

If $P$ is strictly increasing, then $W$ is a cheapest path from $x$ to $y$ if
and only if $W$ visits a minimum number of different zones.

In both cases, the corresponding cheapest standard ticket $T=(W)$ is also a
cheapest ticket if $p$ satisfies the no-stopover property.

Due to Lemma 41, we are interested in an algorithm that computes a path which
visits a minimum number of different zones. Unfortunately, finding such a path
is NP-hard. Let us consider the decision version of this problem, which we
will call Minimum-Zone Path (MZP). It can be stated as follows:

Instance:

PTN $(V,E)$ involving a zone partition for the zone tariff without double
counting (without empty zones on edges), i.e., zone sets $\textrm{zones}(v)$
for all $v\in V$, stations $x,y\in V$ and an integer $K\in\mathbb{N}_{\geq
1}$.

Question:

Is there a path from $x$ to $y$ that visits at most $K$ different zones?

######  Theorem 42.

MZP is NP-complete.

###### Proof.

MZP is in NP, since given a path $W$, it can be checked in polynomial time
whether it visits at most $K$ different zones, i.e., if $\bar{z}(W)\leq K$.

For the polynomial reduction, we use Minimum-Color Single-Path (MCSiP), which
was introduced and shown to be NP-complete by [YVJ05]. Its decision version
can be stated as follows:

Instance:

Graph $G=(V,E)$, a finite set of colors $C$, a function $c\colon E\to C$ which
assigns a color to each edge, nodes $x,y\in V$ and an integer
$k\in\mathbb{N}$.

Question:

Is there a path from $x$ to $y$ that uses at most $k$ colors?

Let a graph $G=(V,E)$, a set of colors $C$ with the assignment function
$c\colon E\to C$, two nodes $x,y\in V$ (w.l.o.g. we assume $x\not=y$) and an
integer $k\in\mathbb{N}_{\geq 1}$ be given. We construct an instance for MZP.
In order to obtain a PTN for MZP, we add a node on each edge to represent the
color of the edge. Hence, we define the sets of nodes and edges by

$\displaystyle V^{\prime}\mathrel{\vcentcolon=}V\cup\\{v_{e}:e\in E\\},$
$\displaystyle
E^{\prime}\mathrel{\vcentcolon=}\\{\\{x,v_{e}\\},\\{v_{e},y\\}:\\{x,v\\}=e\in
E\\}.$

This is polynomial, since $|V^{\prime}|=|V|+|E|$ and $|E^{\prime}|=2|E|$.
Finally, we define the zone partition as follows by introducing a dummy zone
with the label Null which is not in $C$:

$\textrm{zones}(x)\mathrel{\vcentcolon=}\begin{cases}\\{\textup{Null}\\}&\text{if
}x\in V\\\ \\{c(e)\\}&\text{if }x\in V^{\prime}\setminus V.\end{cases}$

Thus, a path visits at most $K\mathrel{\vcentcolon=}k+1$ zones if and only if
it uses at most $k$ colors.

Figure 11: Construction of a zone partition in the proof of Theorem 42.

∎

######  Corollary 43.

The cheapest ticket problem is NP-hard for a zone tariff without double
counting, even if the price function is strictly increasing and the no-
stopover property is satisfied.

###### Proof.

Solving the cheapest ticket problem with a strictly increasing price function
that satisfies the no-stopover property is equivalent to finding a path which
visits a minimum number of zones (Lemma 41). Hence, the result follows from
Theorem 42. ∎

We now investigate special cases in which the problem can nevertheless be
solved in polynomial time.

######  Lemma 44.

Let a PTN with a zone partition $\cal Z$ be given. If all zones $Z\in\cal Z$
are connected, then MZP can be solved in polynomial time.

###### Proof.

Let the path $W$ be a solution to MZP. Assume there exists a zone $Z$ which is
visited twice by $W$, i.e., $W$ contains a subpath
$W^{\prime}=(x,y_{1},\ldots,y_{k},x^{\prime})$, $k\geq 1$, with
$x,x^{\prime}\in Z$ and $y_{i}\not\in Z$ for $i\in\\{1,\ldots,k\\}$. Since $Z$
is connected there exists a path $W^{\prime\prime}$ from $x$ to $x^{\prime}$
which does not leave $Z$. Replacing $W^{\prime}$ by $W^{\prime\prime}$ in $W$
hence visits at most as many different zones as $W$. Therefore, we do not need
to store the sets of visited zones in this case, but it is enough to find a
path crossing a minimal number of zone borders. This means, MZP can be solved
in polynomial time by a shortest path algorithm in the PTN with the zone
border weight $b$ from the basic zone tariff as edge weight (Algorithm 1). ∎

In the following we generalize this result and allow even one zone which is
not connected. More precisely, we consider a PTN with a zone tariff without
double counting with respect to an increasing price function $P$. Let $b$ be
the zone border weight as for the basic zone tariff. We suppose that at most
one zone $Z$ is disconnected and decomposes into $k$ components. In this case,
Algorithm 4 finds a cheapest path without double counting.

1

Input : PTN $(V,E)$ with a zone partition ${\mathcal{Z}}$, i.e., zone border
weights $b$, in which all zones but one zone $Z$ are connected and $Z$
decomposes into $k$ connected components, two stations $x,y\in V$

Output : $x$-$y$-path $W$

2

3Create a directed graph $G=(V,A)$ by replacing each edge in the PTN by two
directed arcs, one for each direction. For every arc $(v,w)\in A$, let the
weight $\bar{b}(v,w)$ be given by
$\bar{b}(v,w)\mathrel{\vcentcolon=}\begin{cases}\frac{1}{k}&\text{if }w\in
Z\text{ and }v\notin Z,\\\ b(v,w)&\text{otherwise.}\end{cases}$

4 Compute a shortest $x$-$y$-path $W$ in $G$.

return $W$

Algorithm 4 Special case of zone tariff without double counting: finding a
cheapest path.

######  Lemma 45.

Algorithm 4 yields a cheapest path, hence a cheapest standard ticket, in
polynomial time for the special case of an increasing price function and at
most one disconnected zone.

In particular, if (2) holds, then Algorithm 4 yields a cheapest ticket.

###### Proof.

Note that a path in $G$ can be understood as a path in the PTN and vice versa.
Let $W$ be a path from $x$ to $y$ computed by Algorithm 4. Since $W$ is a
shortest path regarding $\bar{b}$, it does not visit a zone in
${\mathcal{Z}}\setminus\\{Z\\}$ more than once due to connectedness as in the
proof of Lemma 44. Therefore, if $W$ has weight $\bar{b}(W)=m$ in $G$, it
holds that

$\bar{z}(W)=\begin{cases}\lceil m+1\rceil&\text{if }x\notin Z,\\\ \lceil
m+\frac{1}{k}\rceil&\text{if }x\in Z.\end{cases}$ (5)

From that, we can conclude that $W$ visits a minimum number of different
zones: Assume there is a path $W^{\prime}$ which visits fewer zones than $W$,
i.e., $\bar{z}(W^{\prime})<\bar{z}(W)$. Regarding the proof of Lemma 44, we
can assume that $W^{\prime}$ does not visit a zone in
${\mathcal{Z}}\setminus\\{Z\\}$ more than once, and hence (5) holds for
$W^{\prime}$. Since $W$ is a shortest path regarding $\bar{b}$, we have
$\bar{b}(W)\leq\bar{b}(W^{\prime})$. Because $W$ and $W^{\prime}$ have the
same start node and due to (5) and monotonicity of the ceiling function, this
is a contradiction to $W^{\prime}$ visiting less zones than $W$.

The graph $G$ can be constructed in polynomial time and the runtime of
shortest path algorithms, e.g., Dijkstra, is polynomial, hence the overall
runtime is polynomial as well.

If the price function is increasing and (2) holds, then the no-stopover and
no-elongation property are satisfied by Theorems 39 and 40. Hence, a cheapest
standard ticket is a cheapest ticket by Theorem 6. ∎

##  5 Combined Fare Systems

Real-world public transport fares are often very complex, and usually not only
one but several different fare systems are implemented within the same linked
transport system. Therefore, we have a look at combinations of two fare
systems. As in real world tariff systems, tickets from both fare systems are
available and a passenger can choose the cheapest available ticket. We start
with the definition and some general properties before we discuss two cases of
combined fare systems: the bounded distance tariff and a combination of a zone
tariff and a short-distance tariff.

###  5.1 General Properties of Combined Fare Systems

######  Definition 46.

Let a PTN be given, and let $p_{1}$ and $p_{2}$ be two fare systems. A
_combined fare system_ $p$ of $p_{1}$ and $p_{2}$ is defined by
$p(W)\mathrel{\vcentcolon=}\min\\{p_{1}(W),p_{2}(W)\\}$ for all
$W\in\mathcal{W}$.

One could think that if both fare systems satisfy a property, then so does
their combined fare system. While this is indeed true for the no-elongation
property, it is not true for the no-stopover property.

######  Example 47.

Figure 12: PTN with zones for Example 47. Table 1: Prices of the paths regarding the different fare systems from Example 47. | $W_{1}$ | $W_{2}$ | $W$
---|---|---|---
$p_{1}$ | 1 | 4 | 4
$p_{2}$ | 2 | 2 | 4
$p$ | 1 | 2 | 4

The no-stopover property does not transfer to the combined fare system. To see
this, we consider the PTN shown in Figure 12 with
$l(x_{1},x_{2})=l(x_{2},x_{3})=2$, where we omit virtual nodes to simplify
notation. Let $p_{1}$ be the basic zone tariff with respect to a linear price
function ${P\colon\mathbb{N}_{\geq 1}\to\mathbb{R}_{\geq 0}},\ k\mapsto k$,
and let $p_{2}$ be the distance tariff with $f=0$ and $\overline{p}=1$, i.e.,
for $W\in\mathcal{W}$ we have $p_{1}(W)=z(W)$ and $p_{2}(W)=l(W)$. By Theorem
9 and Example 18 both fare systems satisfy the no-stopover property. We define
the paths $W\mathrel{\vcentcolon=}(x_{1},x_{2},x_{3})$,
$W_{1}\mathrel{\vcentcolon=}(x_{1},x_{2})$ and
$W_{2}\mathrel{\vcentcolon=}(x_{2},x_{3})$. The resulting costs are presented
in Table 1. The no-stopover property is not satisfied for the combined fare
system because $p(W_{1})+p(W_{2})=3<4=p(W)$.

######  Theorem 48.

Let $p_{1}$ and $p_{2}$ be two fare systems which satisfy the no-elongation
property. Then their combined fare system $p$ satisfies the no-elongation
property as well.

###### Proof.

Let $W=(x_{1},\ldots,x_{n})\in\mathcal{W}$ with $n\geq 2$ be given and set
$W_{1}\mathrel{\vcentcolon=}[x_{1},x_{n-1}]$. Due to the no-elongation
property for $p_{1}$ and $p_{2}$, it holds that

$p(W_{1})=\min\\{p_{1}(W_{1}),p_{2}(W_{1})\\}\leq\begin{cases}p_{1}(W_{1})\leq
p_{1}(W),\\\ p_{2}(W_{1})\leq p_{2}(W).\end{cases}$

Hence, it holds that

$p(W_{1})=\min\\{p_{1}(W_{1}),p_{2}(W_{1})\\}\leq\min\\{p_{1}(W),p_{2}(W)\\}=p(W)$

and $p$ satisfies the no-elongation property. ∎

We end the section with the following simple, but algorithmically relevant
observation:

$\min_{x\text{-}y\text{-path }W}\,p(W)=\min_{x\text{-}y\text{-path
}W}\,\min_{p^{\prime}\in\\{p_{1},p_{2}\\}}p^{\prime}(W)=\min_{p^{\prime}\in\\{p_{1},p_{2}\\}}\,\min_{x\text{-}y\text{-path
}W}\,p^{\prime}(W).$ (6)

This means, we can find a cheapest path and hence a cheapest standard ticket
by comparing the cheapest path w.r.t. $p_{1}$ and the cheapest path w.r.t.
$p_{2}$ and choosing the better of the two. This is stated in Algorithm 5.

1

Input : PTN $(V,E)$, combined fare system $p$ of $p_{1}$ and $p_{2}$, two
stations $x,y\in V$

Output : $x$-$y$-path $W$

2

3Compute a cheapest path $W_{1}$ w.r.t. $p_{1}$.

4 Compute a cheapest path $W_{2}$ w.r.t. $p_{2}$.

5 if $p_{1}(W_{1})\leq p_{2}(W_{2})$ then

6 return $W_{1}$

7else

8 return $W_{2}$

Algorithm 5 Combined fare system: finding a cheapest path.

###  5.2 Bounded Distance Tariff

The price of a journey can usually not become arbitrarily large, i.e., there
is an upper bound on the price. This can be modeled as a combined fare system
with the help of unit tariffs. Consider, for example, a distance tariff
$p_{1}(W)=f+\overline{p}_{1}\cdot l(W)$ with $\overline{p}_{1}>0$ and a unit
tariff $p_{2}(W)=\overline{p}_{2}$ for $W\in\mathcal{W}$. The _bounded
distance tariff_ as the combined fare system of a distance tariff and a unit
tariff is then given by

$p(W)=\min\\{p_{1}(W),p_{2}(W)\\}=\begin{cases}p_{1}(W)=f+\overline{p}_{1}\cdot
l(W)&\text{if }l(W)\leq\frac{\overline{p}_{2}-f}{\overline{p}_{1}},\\\
p_{2}(W)=\overline{p}_{2}&\text{otherwise.}\end{cases}$

For this combined fare system both the no-stopover and the no-elongation
property hold.

######  Theorem 49.

A bounded distance tariff satisfies the no-stopover and the no-elongation
property.

###### Proof.

Consider a path $W\in\mathcal{W}$, and let $(W_{1},W_{2})$ be a corresponding
compound ticket. If we have $p(W_{i})=p_{2}(W_{i})=\overline{p}_{2}$ for some
$i\in\\{1,2\\}$, then $p(W)=\overline{p}_{2}\leq p(W_{1})+p(W_{2})$.
Otherwise, if $p(W_{i})=p_{1}(W_{i})$ for all $i\in\\{1,2\\}$, then
$p(W)=\min\\{p_{1}(W),p_{2}(W)\\}\leq p_{1}(W)\leq p_{1}(W_{1})+p_{1}(W_{2})$
by Theorem 9. Hence, we have $p(W)\leq p(W_{1})+p(W_{2})$ and the no-stopover
property is satisfied. Also the no-elongation property is fulfilled by
Theorems 48 and 9. ∎

######  Corollary 50.

For a bounded distance tariff, Algorithm 5 finds a cheapest standard ticket
and a cheapest ticket in polynomial time.

###### Proof.

The correctness follows from (6) and Theorems 49 and 6. The runtime is
polynomial due to Corollary 10. ∎

###  5.3 Basic Zone Tariff Combined with a Short-distance Tariff

A ticket option that we have not studied yet and which is always only
implemented in combination with another fare system is the _short-distance
tariff_. Given a fare system, e.g., a unit tariff or a zone tariff, a short-
distance tariff adds a new ticket option for very short journeys with respect
to the length and the number of stations. It is designed to make such short
journeys more attractive. Since a short-distance ticket can only be bought for
a subset of all paths, we define the short-distance tariff as a formal fare
system, i.e., we allow an infinite price which is not possible in practice.

For the following definition, we denote by $s(W)$ the number of stations of a
path $W$ except the start station, i.e., its number of edges. As before,
$l(W)$ is the length of a path $W$.

######  Definition 51.

Let a PTN be given. A (formal) fare system $p$ is called a _short-distance
tariff_ with respect to a price $P_{S}\in\mathbb{R}_{\geq 0}$ and upper bounds
$S_{\max}\in\mathbb{N}_{\geq 1}\cup\\{\infty\\}$ and
$L_{\max}\in\mathbb{R}_{>0}\cup\\{\infty\\}$, where at least one is finite, if

$p(W)=\begin{cases}P_{S}&\text{if }s(W)\leq S_{\max}\text{ and }l(W)\leq
L_{\max},\\\ \infty&\text{if }s(W)>S_{\max}\text{ or
}l(W)>L_{\max}\end{cases}$

for all paths $W\in\mathcal{W}$.

Here, $S_{\max}$ is an upper bound on the number of stations and $L_{\max}$ is
an upper bound on the length of the path that are allowed for using the short-
distance tariff. We call a path $W$ a _short-distance path_ if $s(W)\leq
S_{\max}$ and $l(W)\leq L_{\max}$. This results in the reformulation

$p(W)=\begin{cases}P_{S}&\text{if }W\text{ is a short-distance path,}\\\
\infty&\text{otherwise.}\end{cases}$

We allow $S_{\max}=\infty$ or $L_{\max}=\infty$ in order to represent the
situation where a short-distance path is only restricted by the number of
stations or its length, but not by both. We first observe what cheapest paths
for a short-distance tariff look like.

######  Lemma 52.

Let $p$ be a short-distance tariff and $x,y\in V$. If there is a short-
distance path from $x$ to $y$, then this is a cheapest path. If there is none,
then any $x$-$y$-path is a cheapest path.

We next investigate the no-stopover and the no-elongation property.

######  Lemma 53.

For all bounds $S_{\max}$ and $L_{\max}$, there is a PTN so that the induced
short-distance tariff with respect to any price $P_{S}$ does not satisfy the
no-stopover property.

###### Proof.

Let $P_{S}$ be an arbitrary short-distance price. Consider a PTN with a path
$W$ with $s(W)>S_{\max}$ or $l(W)>L_{\max}$ that can be decomposed into two
short-distance paths $W_{1}$ and $W_{2}$, i.e., $s(W_{i})\leq S_{\max}$ and
$l(W_{i})\leq L_{\max}$ for all $i\in\\{1,2\\}$. Then the induced short-
distance tariff $p$ does not satisfy the no-stopover property since
$p(W)=\infty$, but $p(W_{1})+p(W_{2})=2P_{S}<\infty$. ∎

######  Theorem 54.

If $p$ is a short-distance tariff, then the no-elongation property is
fulfilled.

###### Proof.

Let $W=(x_{1},\ldots,x_{n})\in\mathcal{W}$, $n\geq 2$ be given. If $W$ is a
short-distance path, then its subpath $[x_{1},x_{n-1}]$ is also a short-
distance path because it holds that ${s([x_{1},x_{n-1}])<s([x_{1},x_{n}])}$
and $l([x_{1},x_{n-1}])<l([x_{1},x_{n}])$. Hence, we have that
${p([x_{1},x_{n-1}])\leq p([x_{1},x_{n}])}$. ∎

In order to compute a cheapest path, we need to identify if a short-distance
path between two stations exists, i.e., we look for a _shortest weight
constrained path_. This problem, also known as _restricted shortest path_ has
been studied extensively, e.g., [DB03, Jok66, Has92, LR01, Jaf84]. It is known
to be NP-complete [GJ79].

However, in our special case, the weight represents the number of stations on
a path, which coincides with the number of edges. Hence, we have a unit weight
for all edges $e\in E$. This is the crucial factor which allows a polynomial
time algorithm for checking if there is a path which satisfies the
requirements of the short-distance tariff by a modification of the Bellman-
Ford algorithm, as mentioned, e.g., in [AMP91]. Iteratively, we calculate the
distance from the start station to every other station in the graph using at
most $s\leq S_{\max}$ edges. Then we can check if there is a path with at most
$S_{\max}$ edges that has a length of at most $L_{\max}$. For the sake of
completeness, the algorithm can be found in the appendix.

We finally look at the combination of the basic zone tariff with a short-
distance tariff. The idea is to make traveling on short routes less expensive.
In combination with a basic zone tariff, the short-distance tariff is
especially relevant for short paths which cross zone borders.

For a given PTN, let a basic zone tariff $p_{1}$ with an increasing price
function $P$ and a short-distance tariff $p_{2}$ with a price
$P_{S}\in\mathbb{R}_{\geq 0}$ and bounds $S_{\max}\in\mathbb{N}_{\geq
1}\cup\\{\infty\\}$ and ${L_{\max}\in\mathbb{R}_{>0}\cup\\{\infty\\}}$ be
given. With these data, we construct the _combined fare system of a basic zone
tariff and a short-distance tariff (ZSD)_ $p$ as in Definition 46, given by
${p(W)=\min\\{p_{1}(W),p_{2}(W)\\}}$ for all $W\in\mathcal{W}$. In this case
$p$ resolves to

$p(W)=\begin{cases}\min\\{P_{S},P(z(W))\\}&\text{if }W\text{ is a short-
distance path,}\\\ P(z(W))&\text{otherwise.}\end{cases}$ (7)

For a ZSD, it is important how to choose $P_{S}$. If $P(k)\leq P_{S}$ for all
$k\in\mathbb{N}_{\geq 1}$, then the short-distance tariff would never be
applied and the ZSD is a basic zone tariff. Hence, from now on, we assume that
there is some $K\in\mathbb{N}_{\geq 1}$ such that $P_{S}<P(k)$ for all $k\geq
K$. If $P_{S}<P(1)$, then the short-distance tariff can be beneficial when
zone borders are crossed, but also for short trips within a single zone. On
the other hand, if $P_{S}>P(1)$, it will never be used within a single zone,
but only if sufficiently many zones are visited on a path. Therefore, by
choosing the price $P_{S}$, the options for use of the short-distance tariff
can be limited further. This can easily be seen by restating formula (7) for
$p$ in the following way:

Let $K\in\mathbb{N}$ such that $P(K)\leq P_{S}<P(K+1)$ where we define
$P(0)\mathrel{\vcentcolon=}0$ in order to formally cover the case $P_{S}\leq
P(1)$. Then

$p(W)=\begin{cases}P_{S}&\text{if }z(W)>K\text{ and }s(W)\leq S_{\max}\text{
and }l(W)\leq L_{\max},\\\ P(z(W))&\text{if }z(W)\leq K\text{ or
}s(W)>S_{\max}\text{ or }l(W)>L_{\max}\end{cases}$ (8)

is a reformulation of (7). In particular, it demonstrates that a path needs to
visit more than $K$ zones in order that it is beneficial to use the short-
distance tariff.

######  Theorem 55.

Let bounds $S_{\max}$ and $L_{\max}$, an increasing price function $P$ and a
price $P_{S}$ be given, and let $K$ be as in (8). All induced ZSDs satisfy the
no-stopover property if and only if the following conditions hold:

  1. 1.

$P(k)\leq P(i)+P(k-i+1)$ for all $k\geq 1$ and $i\in\\{1,\ldots,k\\}$,

  2. 2.

$P(k)\leq 2P_{S}$ for all $k\geq 2K+1$,

  3. 3.

$P(k)\leq P(i)+P_{S}$ for all $k\geq K+1$ and $i\in\\{1,\ldots,k-K\\}$,

  4. 4.

if $S_{\max}>1$, then $P_{S}\leq P(i)+P(k-i+1)$ for all
$k\in\\{K+1,\ldots,2K-1\\}$ and for all ${i\in\\{k-K+1,\ldots,K\\}}$ (note
that the condition is empty for $K\in\\{0,1\\}$).

###### Proof.

In this proof, we make use of the representation of the fare system $p$ as in
(8). First, we show that there is a PTN for which the induced ZSD does not
satisfy the no-stopover property if one of the conditions is not fulfilled.
For the following examples, we assume that $L_{\max}<\infty$. In each case we
consider the situation depicted in Figure 13 (again omitting virtual nodes)
with specific edge lengths so that the no-stopover property is not satisfied.
To this end, we show that the compound ticket $((x_{1},x_{2}),(x_{2},x_{3}))$
is cheaper than the standard ticket of the path $(x_{1},x_{2},x_{3})$.
However, the examples can be adapted to the case that $L_{\max}=\infty$, i.e.,
$S_{\max}<\infty$, by using unit lengths $l(x_{1},x_{2})=l(x_{2},x_{3})$ and
adding sufficiently many stations along both edges.

  1. 1.

Assume that condition 1 is not satisfied for some $k$ and $i$, which means
that we have ${P(k)>P(i)+P(k-i+1)}$. Let
$l(x_{1},x_{2})=l(x_{2},x_{3})=L_{\max}+1$. Then the zone tariff is used for
all three paths.

  2. 2.

Assume that condition 2 is not satisfied for some $k$, which means
$P(k)>2P_{S}$. Let ${l(x_{1},x_{2})=l(x_{2},x_{3})=L_{\max}}$, i.e.,
$l(x_{1},x_{2},x_{3})=2L_{\max}>L_{\max}$, and let $i=K+1$. Then we have
$z(x_{1},x_{2})=K+1$ and ${z(x_{2},x_{3})=k-i+1\geq(2K+1)-(K+1)+1=K+1}$. Also,
${s(x_{1},x_{2})=s(x_{2},x_{3})=1\leq S_{\max}}$. Hence, the zone price $P(k)$
is used for $(x_{1},x_{2},x_{3})$, but the short-distance price $P_{S}$ is
applied to both subpaths.

  3. 3.

Assume that condition 3 is not satisfied for some $k$ and $i$, i.e.,
$P(k)>P(i)+P_{S}$. Let ${l(x_{1},x_{2})=L_{\max}+1}$ and
$l(x_{2},x_{3})=L_{\max}$. Then we have
$z(x_{2},x_{3})=k-i+1\geq{k-(k-K)+1}=K+1$ and $s(x_{2},x_{3})=1\leq S_{\max}$.
Hence, the zone prices $P(k)$ and $P(i)$ are used for $(x_{1},x_{2},x_{3})$
and $(x_{1},x_{2})$, but the short-distance price $P_{S}$ is applied to
$(x_{2},x_{3})$.

  4. 4.

Assume that condition 4 is not satisfied for some $k$ and $i$, i.e.,
$P_{S}>P(i)+P(k-i+1)$. Let
$l(x_{1},x_{2})=l(x_{2},x_{3})=\frac{L_{\max}}{2}<L_{\max}$, which yields
$l(x_{1},x_{2},x_{3})\leq L_{\max}$. Then we have $z(x_{1},x_{2})=i\leq K$ and
$z(x_{2},x_{3})=k-i+1\leq k-(k-K+1)+1=K$. Also,
$s(x_{1},x_{2})=s(x_{2},x_{3})=1\leq S_{\max}$ and $s(x_{1},x_{2},x_{3})=2\leq
S_{\max}$ by assumption. Therefore, the short-distance price $P_{S}$ is used
for the path $(x_{1},x_{2},x_{3})$ because ${z(x_{1},x_{2},x_{3})=k>K}$ by
choice of $k$, but the zone prices $P(i)$ and $P(k-i+1)$ are applied to the
subpaths since they visit at most $K$ zones.

Figure 13: PTN with zones for Theorem 55.

Now we suppose that all the conditions hold and consider a ZSD $p$. Let
$W\in\mathcal{W}$ be a path with a corresponding compound ticket
$(W_{1},W_{2})$. We set $k\mathrel{\vcentcolon=}z(W)$,
$k_{1}\mathrel{\vcentcolon=}z(W_{1})$ and
$k_{2}\mathrel{\vcentcolon=}z(W_{2})$, so $k_{1}+k_{2}=k+1$. We make a case
distinction whether a path is a short-distance path and whether it is assigned
the short-distance price.

  1. 1.

If neither $W$ nor $W_{1},W_{2}$ are short-distance paths, then the zone
tariff is applied. The no-stopover property holds for $W$ by condition 1.

  2. 2.

If $W_{1}$ is a short-distance path, but $W_{2}$ and $W$ are not, then we
distinguish two cases:

     * •

$k_{1}\leq K$: Then $W_{1}$ is assigned the price of the zone tariff, and the
no-stopover property holds for $W$ by condition 1.

     * •

$k_{1}\geq K+1$: The short-distance tariff is applied for $W_{1}$. Also $k\geq
k_{1}\geq K+1$ and ${k_{2}=k-k_{1}+1\leq k-(K+1)+1=k-K}$. Thus, the no-
stopover property holds for $W$ by condition 3 with $i=k_{2}$.

For the cases where $W_{1}$ and $W_{2}$ or all paths are short-distance paths,
we proceed analogously. These remaining cases can be found in [Urb20]. This
shows that the no-stopover property is satisfied. ∎

######  Corollary 56.

If $p$ is a ZSD, then the no-elongation property is satisfied.

###### Proof.

Because basic zone tariffs with an increasing price function and short-
distance tariffs satisfy the no-elongation property by Theorems 19 and 54, it
is also satisfied for a ZSD by Theorem 48. ∎

For a ZSD, a cheapest path is either a cheapest path as in the basic zone
tariff or a short-distance path. In order to find one, we detail Algorithm 5
and apply the algorithms for the short-distance tariff and the one for the
basic zone tariff, and then we decide which path is cheaper.

1

Input : PTN $(V,E)$, finite upper bounds $S_{\max}$, $L_{\max}$, a price
function $P$, a short-distance price $P_{S}$, two stations $x,y\in V$

Output : $x$-$y$-path $W$

2

3Let $W_{1}$ be the result returned by Algorithm 7 for finding a short-
distance path.

4 Let $W_{2}$ be the result returned by Algorithm 1 for finding a cheapest
path regarding the basic zone tariff.

5 if $W_{1}$ $\neq$ None and $P_{S}<P(z(W_{2}))$ then

6 return $W_{1}$

7else

8 return $W_{2}$

Algorithm 6 ZSD: finding a cheapest path.

######  Corollary 57.

Let $p$ be a ZSD.

  * •

Algorithm 6 finds a cheapest path and hence a cheapest standard ticket in
polynomial time.

  * •

If $p$ satisfies the no-stopover property (Theorem 55), then Algorithm 6
yields a cheapest ticket in polynomial time.

###### Proof.

The claim follows from the correctness and runtime of Algorithms 5, 7, and 1.
The no-elongation property is satisfied by Corollary 56. If also the no-
stopover property holds, then a cheapest standard ticket is also a cheapest
ticket by Theorem 6. ∎

##  6 Conclusion

In this paper, we have provided models for many common fare systems, studied
their properties and provided polynomial algorithms for finding cheapest
standard tickets, all of them based on shortest paths. We also investigated in
which cases cheapest standard tickets provide cheapest tickets, i.e., in which
cases it is not possible to trick out the rules by misusing the bought
tickets. To this end, we defined and analyzed the no-stopover and the no-
elongation property and gave sufficient conditions for them to hold.

As a further step, we plan to investigate speed-up techniques for shortest
paths (e.g., in [WW07, BDG+16]) in order to make the computation of cheapest
paths more efficient and to evaluate these experimentally. Here it is
particularly interesting to use the embedding of the PTN in the plane,
bidirectional search and the structure of the zones (for zone tariffs). The
next step is to include the ticket price as one criterion besides other
criteria that passengers might apply to choose their routes. The most
important criterion for a passenger probably is the travel time, see, e.g.,
[BHK17], but also, for example, the robustness against delays of the path may
be important as shown in [GKMH+14]. Considering several criteria can be done
efficiently if ticket prices can be computed by common shortest path
algorithms in the same network as the travel time, but with adapted edge
weights, as in [GMHS07]. Also, planning fare systems under different criteria
(such as fairness, income, low transition costs) is an interesting topic for
further research as well as the integration of planning fare systems and
network design. For example, there is a strong relation between line planning
and the design of zone tariffs since the number of zones crossed on a path
depends on the line plan.

We finally plan to include the ticket prices in route choice models and
integrate them into planning lines and timetables along the lines of [SS20],
but with an underlying realistic passengers’ behavior.

## References

  * [AMP91] E.M. Arkin, J.S.B. Mitchell, and C.D. Piatko, _Bicriteria shortest path problems in the plane_ , Proceedings of the 3rd Canadian Conference on Computational Geometry (Vancouver, Canada), Simon Fraser University, 1991, pp. 153–156.
  * [BDG+16] H. Bast, D. Delling, A.V. Goldberg, M. Müller–Hannemann, T. Pajor, P. Sanders, D. Wagner, and R.F. Werneck, _Route planning in transportation networks_ , Algorithm Engineering: Selected Results and Surveys, Springer International Publishing, 2016, pp. 19–80.
  * [BHK17] R. Borndörfer, H. Hoppmann, and M. Karbstein, _Passenger routing for periodic timetable optimization_ , Public Transport 9 (2017), no. 1-2, 115–135.
  * [BK03] L. Babel and H. Kellerer, _Design of tariff zones in public transportation systems: Theoretical results and heuristics_ , Mathematical Methods of Operations Research (2003), 358–374.
  * [BKP12] R. Borndörfer, M. Karbstein, and M.E. Pfetsch, _Models for fare planning in public transport_ , Discrete Applied Mathematics 160 (2012), no. 18, 2591–2605.
  * [BNP05] R. Borndörfer, M. Neumann, and M.E. Pfetsch, _Models for fare planning in public transport_ , Tech. report, ZIB, 2005.
  * [DB03] I. Dumitrescu and N. Boland, _Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem_ , Networks 42 (2003), no. 3, 135–153.
  * [DDP19] D. Delling, J. Dibbelt, and T. Pajor, _Fast and exact public transit routing with restricted Pareto sets_ , Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX), 2019, pp. 54–65.
  * [DPW15] D. Delling, , T. Pajor, and R.F. Werneck, _Round-based public transit routing_ , Transportation Science 49 (2015), no. 3, 591–604.
  * [EB19] R. Euler and R. Borndörfer, _A Graph- and Monoid-Based Framework for Price-Sensitive Routing in Local Public Transportation Networks_ , 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019), OpenAccess Series in Informatics (OASIcs), vol. 75, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019, pp. 12:1–12:15.
  * [GJ79] M.R. Garey and D.S. Johnson, _Computers and intractability — a guide to the theory of np-completeness_ , H.W. Freeman and Company, San Francisco, 1979\.
  * [GKMH+14] M. Goerigk, M. Knoth, M. Müller-Hannemann, M. Schmidt, and A. Schöbel, _The Price of Strict and Light Robustness in Timetable Information_ , Transportation Science 48 (2014), 225–242.
  * [GMHS07] T. Gunkel, M. Müller-Hannemann, and M. Schnee, _16\. Improved search for night train connections_ , 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’07) (Dagstuhl, Germany), OpenAccess Series in Informatics (OASIcs), vol. 7, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2007.
  * [GMS17] A. Galligari, M. Maischberger, and F. Schoen, _Local search heuristics for the zone planning problem_ , Optimization Letters 11 (2017), 195–207.
  * [Has92] R. Hassin, _Approximation schemes for the restricted shortest path problem_ , Mathematics of Operations Research 17 (1992), no. 1, 36–42.
  * [HS95] H.W. Hamacher and A. Schöbel, _On fair zone design in public transportation_ , Computer-Aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, no. 430, Springer, Berlin, Heidelberg, 1995, pp. 8–22.
  * [HS04] , _Design of zone tariff systems in public transportation_ , OR 52 (2004), no. 6, 897–908.
  * [Jaf84] J.M. Jaffe, _Algorithms for finding paths with multiple constraints_ , Networks 14 (1984), no. 1, 95–116.
  * [Jok66] H.C. Joksch, _The shortest route problem with constraints_ , Journal of Mathematical Analysis and Applications 14 (1966), no. 2, 191 – 197\.
  * [LR01] D.H. Lorenz and D. Raz, _A simple efficient approximation scheme for the restricted shortest path problem_ , Operations Research Letters 28 (2001), no. 5, 213 – 219.
  * [MHS06] M. Müller-Hannemann and M. Schnee, _Paying less for train connections with MOTIS_ , 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS’05), OpenAccess Series in Informatics (OASIcs), vol. 2, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2006.
  * [MS18] S. Maadi and J.-D. Schmöcker, _Theoretical evaluation on the effects of changes from a zonal to a distance-based fare structure_ , Proceedings of CASPT’18, Brisbane, 2018.
  * [OB17] B. Otto and N. Boysen, _Zone-based tariff design in public transportation networks_ , Networks 69 (2017), no. 4, 349–366.
  * [SS20] P. Schiewe and A. Schöbel, _Periodic timetabling with integrated routing: Towards applicable approaches_ , Transportation Science 54 (2020), no. 6, 1714–1731.
  * [SU20] A. Schöbel and R. Urban, _Cheapest Paths in Public Transport: Properties and Algorithms_ , 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020), OpenAccess Series in Informatics (OASIcs), vol. 85, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020, pp. 13:1–13:16.
  * [Urb20] R. Urban, _Analysis and computation of cheapest paths in public transport_ , Master’s thesis, Technische Universität Kaiserslautern, 2020.
  * [WW07] D. Wagner and T. Willhalm, _Speed-up techniques for shortest-path computations_ , STACS 2007, 2007.
  * [YVJ05] S. Yuan, S. Varma, and J.P. Jue, _Minimum-color path problems for reliability in mesh networks_ , Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies., vol. 4, 2005, pp. 2658–2669.

## Appendix. Algorithm for Section 5.3

1

Input : PTN $(V,E)$, upper bounds $S_{\max}$, $L_{\max}$, two stations $x,y\in
V$

Output : shortest $x$-$y$-path $W$ with $s(W)\leq S_{\max}$ and $l(W)\leq
L_{\max}$ if one exists

2

// Initialization

3 $S_{\max}\mathrel{\vcentcolon=}\min\\{S_{\max},|V|-1\\}$,
$L_{\max}\mathrel{\vcentcolon=}\min\\{L_{\max},\max_{e\in E}l(e)\cdot|V|\\}$

4 for all $v\in V$ do

5 $d_{0}(v)\mathrel{\vcentcolon=}\infty$

6 $\pi_{0}(v)\mathrel{\vcentcolon=}\text{None}$

7$d_{0}(x)\mathrel{\vcentcolon=}0$

// Compute distances and predecessors (Bellman-Ford)

8 for $s=1,\ldots,S_{\max}$ do

9 for all $v\in V$ do

10 $d_{s}(v)\mathrel{\vcentcolon=}d_{s-1}(v)$

11 $\pi_{s}(v)\mathrel{\vcentcolon=}\pi_{s-1}(v)$

12 for all edges $(w,v)\in E$ do

13 if $d_{s}(v)>d_{s-1}(w)+l(w,v)$ then

14 $d_{s}(v)\mathrel{\vcentcolon=}d_{s-1}(w)+l(w,v)$

15 $\pi_{s}(v)\mathrel{\vcentcolon=}w$

16

17

18

// Check if a feasible $x$-$y$-path exists and compute it if necessary

19 if $d_{S_{\max}}(y)\leq L_{\max}$ then

// Determine the path $W$ from $x$ to $y$ by backtracking the predecessors

$W^{\prime}=[y]$ // list of all predecessors starting from $y$

20 current $\mathrel{\vcentcolon=}$ $y$

21 $s\mathrel{\vcentcolon=}S_{\max}$

22 while current $\neq$ $x$ do

23 current $\mathrel{\vcentcolon=}$ $\pi_{s}(\text{current})$

$W^{\prime}$.append(current) // add current to the end of $W^{\prime}$

24 $s\mathrel{\vcentcolon=}s-1$

25 Set $W\mathrel{\vcentcolon=}(W^{\prime})^{-1}$

26 return $W$

27else

28 return None

Algorithm 7 Short-distance tariff: finding a short-distance path.