Design of Distance Tariffs in Public Transport

The choice of ticket prices for public transport usage is a crucial decision. Ticket prices are important for covering the costs of the public transport operator. Through price elasticities (see, e.g., [9, 2, 5]), they affect the number of people traveling by public transport. They also contribute to the passenger satisfaction, and they even may affect the routes passengers choose [3, 12]. A variety of fare strategies is implemented worldwide, each with a different focus and purpose. In the following we sketch three basic types which come with many variations in practice.

Informally speaking, a fare structure assigns a ticket price to every passengers’ journey. Hence, in order to define formally what a fare structure and a distance tariff are, we first need the network in which the passengers travel.

Let us define the public transport network PTN as a graph $\text{PTN}=(V,E)$ with $V$ being the stations and $E$ being the links between stations on which a regular service exists. A passengers’ journey is a path in the PTN. In order to reflect all possible passengers journeys through the network, we define $𝒥$ as the set of all paths in the PTN.

A fare structure assigns a ticket price to every path in the PTN, realizing a fare strategy, which may be a distance tariff, a zone tariff or a flat tariff. This paper deals with models to determine distance tariffs.

Given an org-dest-path $J$ in the PTN, we consider two common options to assign a distance (or length) $l(J)$ to path $J$:

Network distance:

In this case, $l(J)$ is the length of path $J$ in the PTN.

Beeline distance:

In this case, $l(J)$ is the beeline distance between the origin and the destination of path $J$. The path $J$ itself is not needed.

We assume that that all paths have positive lengths and that all distances are rounded up to full kilometers. The latter means that a distance tariff as described in the following requires passengers to pay the price per kilometer for every kilometer started on their journey. In small regions of operation a smaller unit might be used to round to. Note that, while network and beeline distance are the most common options, any other way to determine the length of a path $l(J)\in \mathbb{N}$ can be employed as well, where $\mathbb{N}=\{1,2,3,\mathrm{\dots }\}$ is the set of natural numbers starting from $1$.

The goal of this paper is to develop models for the transition from an existing tariff to a distance tariff as defined in Notation 1. Since neither the operator would like to have a (big) loss in its income nor the passengers would like to have a (large) increase in their ticket prices, the idea is to design the distance tariff such that the new prices are as close as possible to the current prices. This leads to the concept of reference prices, which may be the current ticket prices or other preferable prices that should be realized. The goal then is to minimize the deviation to the reference prices. This objective has been introduced in [7], and is followed in many other publications such as [1, 8, 14, 15, 4].

In order to model the deviations, let a set of passenger groups $𝒟$ be given. For each group $d\in 𝒟$ let $w_d\in \mathbb{N}$ be the number of passengers of group $d$, $J_d$ the path the passengers of group $d$ wish to travel, $l_d\in \mathbb{N}$ its length, and $r_d\in {ℝ}_{\ge 0}$ the reference price.

• $\mathrm{■}$

  The set $𝒟$ of passenger groups can for example be a set of origin-destination (OD) pairs $𝒟\subseteq V\times V$, which means to consider at most one passenger group (and hence one path) between each pair of an origin station and a destination station. We also can allow different passenger groups within the same OD pair, representing different paths between the same origin and destination.

• $\mathrm{■}$

  The distance $l_d$ can be derived as network or beeline distance of path $J_d$ of passenger group $d$, i.e., $l_d=l(J_d)>0$. Note that all paths with the same pair of origin and destination station are assigned the same distance $l_d$ if the beeline distance is applied, whereas the network distance may lead to passenger groups with the same pair of origin and destination station but with different distances because their paths differ.

• $\mathrm{■}$

  As the reference price $r_d$, we apply the current price to be paid by passenger group $d\in 𝒟$ for traveling along path $J_d$.

• $\mathrm{■}$

  Note that two passenger groups $d_1,d_2$ with $l_{d_1}=l_{d_2},r_{d_1}=r_{d_2}$ can be joined to a new passenger group $d$ with $l_d=l_{d_1}=l_{d_2},r_d=r_{d_1}=r_{d_2}$ and $w_d=w_{d_1}+w_{d_2}$. We hence may assume that passenger groups are pairwise disjoint regarding distance or reference price.

Finally, the new price of the passenger group $d$ is denoted by ${\pi }_d$. If it is determined by a distance tariff $(p,f)$, we have ${\pi }_d=p\cdot l_d+f$. The vector ${({\pi }_d)}_{d\in D}$ contains all the new prices.

The basic distance tariff design model for a transition to a distance tariff can now be stated. It looks for a distance tariff $\pi$ with price per kilometer $p$ and base amount $f$, requiring $p,f\ge 0$, and minimizing the sum of absolute deviations between the new prices ${({\pi }_d)}_{d\in 𝒟}$ and the reference prices ${(r_d)}_{d\in 𝒟}$:

The variables ${\pi }_d$ with $d\in 𝒟$ can be replaced such that the program consists of only two variables, $p$ and $f$, and the absolute value can be replaced by a bottleneck variable $z_d$ for each $d\in 𝒟$ such that we equivalently obtain its linear version:

We illustrate an optimized distance tariff for Example 2 in Figure 1(a).

Recall that $l_d>0$ for all $d\in 𝒟$. We can add additional bounds to model (1):

A common practical requirement is to have integer values for the resulting ticket prices. Note that by scaling the reference prices, we can ensure integer multiples of 10ct, 50ct, etc. Here, we not only want to ensure this for the ticket prices ${\pi }_d$ of the actual set of passenger groups $d\in 𝒟$, but also for all potential journeys, i.e., for all paths $J\in 𝒥$ in the PTN. This can be guaranteed by requiring the integrality condition for the whole price list, i.e.,

These conditions may be added to the basis formulation (1):

We may replace $i\in \mathbb{N}$ by $i=\{1,2,\mathrm{\dots },i_{\max }\}$ for some sufficiently large $i_{\max }$, but it is computationally not advantageous to have so many integer variables. This number can be reduced since it is in fact equivalent to require integrality only for $p$ and $f$ as the next lemma shows.

Implementing a distance tariff as in Notation 1, the ticket price increases unlimitedly with the distance. In practice, public transport tariffs often have a cap on the maximum ticket price per journey. Consider a path $J\in 𝒥$. As long as the length of $J$ is small, the price function is an affine linear distance tariff $(p,f)$ that becomes constant if the length of the path exceeds a threshold distance $L_{\max }$. Formally, let the price cap be $p_{\max }$. Then the price $\pi (l)$ for a path with length $l$ is defined as a continuous piecewise linear function in $l$:

which results in a threshold distance $L_{\max }$ for which $p\cdot L_{\max }+f=p_{\max }$, i.e., the price stays at $p_{\max }$ for all passengers traveling further than $L_{\max }$. In the following we investigate distance tariffs with such a cap on the ticket prices.

Figure 2 shows an example of input data with an optimized capped distance tariff analogously to Figure 1. The horizontal part is the result of the upper price limit $p_{\max }$.

We can compute $p$, $f$ and $p_{\max }$ with the following model:

The additional variable $p_{\max }$ denotes the maximum price of the capped distance tariff, and the binary variables $x_d^{\max }$ indicate whether a passenger group $d\in 𝒟$ has to pay the maximum price, or not. The first two constraints ensure that ${\pi }_d$ is always smaller than the minimum of the affine distance tariff and the upper price limit. The next two constraints ensure that ${\pi }_d$ is not smaller, but equal to $p\cdot l_d+f$ if $x_d^{\max }=0$ and equal to $p_{\max }$ if $x_d^{\max }=1$. Finally, the last two constraints ensure the relation between $p_{\max }$ and $p\cdot l_d+f$: If $x_d^{\max }=0$, the constant part $p_{\max }$ must be larger than the affine part $p\cdot l_d+f$, and vice versa if $x_d^{\max }=1$.

In the following we first bound the optimal value for $p_{\max }$. This then enables us to determine a reasonable constant for the big $M$ parameter in model (5). Recall that $r_{\max }={\max }_{d\in 𝒟}{r}_d$.

The objective function minimizing the sum of absolute deviations between reference prices and new prices implicitly controls the deviation of revenue and ticket price increases. However, in practice it may be required explicitly that the revenue is changed by a certain amount or that only a certain amount of passengers is affected by a high increase in the ticket price. These additional requirements are taken into consideration in Sections 5.1 and 5.2.

In order to discuss the differences of the models, we conduct an experimental evaluation. For the input data we consider the data set sioux_falls provided in the open source software library LinTim [18, 19], see Figure 4. We generate two sets of passenger groups ${𝒟}_1,{𝒟}_2$ where for ${𝒟}_1$ the reference prices $r_d$ are computed according to a zone tariff depicted in Figure 4(a) and for ${𝒟}_2$ the reference prices $r_d$ are computed based on a network distance tariff. Small perturbations are introduced by rounding the distances $l_d$ of the passenger groups. For $\text{ratio\_zone}\in \{0,0.25,0.5,0.75,1\}$, we create a set of passenger groups $𝒟=\{(l_d,r_d,\text{ratio\_zone}\cdot w_d):d\in {𝒟}_1)\}\cup \{(l_d,r_d,(1-\text{ratio\_zone})\cdot w_d):d\in {𝒟}_2\}$. Thus, the reference prices for $\text{ratio\_zone}=0$ represent a perturbed distance tariff and for $\text{ratio\_zone}=1$ a perturbed zone tariff. By using two distance functions to determine $l_d$, $d\in 𝒟$, in data set A and data set B, we get a total of 10 instances, detailed in Table 1. The models are implemented on a machine with Intel(R) Core(TM) i5-1335U CPU and 32GB RAM using Gurobi 12 [6].

We implement and test 12 models discussed in this paper, see Table 2. In particular, we consider the basic distance tariff design models (dist), models with integer prices (integer) as well as controlling the revenue (revenue) and the number of highly affected passengers (passengers). For each of these models, a version with capped prices (cap) is implemented, as well as alternative models and heuristic approaches marked by ^∗.

For controlling the revenue, we set $R=1\cdot {\sum }_{d\in 𝒟}{w}_d{r}_d$, i.e., the revenue of the new solution has to be at least as high as the revenue generated by the reference prices. For controlling the number of highly affected passengers, we choose ${\overline{r}}_d=1.1r_d$, i.e., all passengers that have to pay more than 110% of the reference price are highly affected. Additionally, we restrict the number of highly affected passengers to $W=0.1{\sum }_{d\in 𝒟}{w}_d$, i.e., at most 10% of the passengers may be highly affected. When integer prices are considered, we consider integer multiples of 10ct, both for the prices $\pi$ and the parameters $f,p$.

This paper provides models with several practically relevant specifications for changing a fare strategy to a distance tariff. In addition to a basic distance tariff composed of a price per kilometer and a base amount, also integrality requirements are discussed. A capped distance tariff additionally implements an upper price bound on the ticket prices. Furthermore, two constraints that can be added to the models and control the change in the revenue or the number of highly affected passengers, respectively, are suggested. The reported optimization models allow to explore and evaluate different options for distance tariffs with the possibility to add special requirements in the constraints. The experimental evaluation shows that practical constraints can be added when designing distance tariffs without sacrificing too much solution quality or revenue. In a confidential case study our partners found the results useful for their decisions on a distance tariff.

We anticipate further research in two different directions: First, the results are related to locating lines and other structures in computational geometry. In particular, for the capped distance tariff, we locate an “angled line” whose theoretical properties could be discussed along the lines of [25], not only for the median but also for the respective center problem.

Second, further research in tariff planning in public transport is interesting. We aim to strengthen the MIP formulations to solve large, realistic data sets by leveraging the structure of the reference prices. This is especially promising when the reference prices are derived from a zone tariff with few zones. Additionally, a bicriteria version as in [20] in which the revenue and the number of passengers using public transport are considered as two (conflicting) objective functions is a useful extension. Furthermore, passengers’ routes are influenced not only by their travel times but also by the tariff system. Since the routes of the passengers are crucial for planning lines and timetables, there is a need of integrating also tariff planning with these stages, and to discuss the differences between the sequential and the integrated approach [16, 17] also in this setting.