Revenue Maximizing Tariff Zone Planning for Public TransportCompanies
S. Müllera , K. Haaseb , L. Reyes-Rubianoa∗
a Chair of Operations Management, Otto von Guericke University Magdeburg, Magdeburg,

Germany{sven.mueller, lorena.reyes}@ovgu.deb Institute for Transport Economics, University of Hamburg, Hamburg, Germany
knut.haase@uni-hamburg.de
Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

March 27, 2022
Keywords: Public transportation, revenue management, contiguity, districting, mixed integer
programming1INTRODUCTION

Public transport companies are under pressure to reduce operational costs and increase thenumber of passengers and revenue. The design of the tariff system has been proven valuable toimpact revenues in public transportation. There exist different tariff systems in public transport(Schöbel & Urban, 2020). This paper studies the zoning and pricing problem to maximize
expected revenue (R) through a counting zones tariff system. The literature on combining zoning
and pricing problems is scarce. Thus, we contribute to this literature by a new mixed-integer
programming (MIP) model and a MIP-based heuristic method to solve the revenue maximizing
tariff zone problem (RMTZP), yielding a counting zones tariff system. It is assumed that (i) theprice per zone takes denumerable values, (ii) the number of public transport trips depends on
the price (system), and (iii) public transport passengers always choose the time-shortest path.
Our new model formulation is: (1) flexible to adjust to any objective function; (2) not limited toa predefined number of tariff zones; we impose contiguity of the tariff zones using the propertiesof primal and dual graphs, (3) coming with a new set of constraints that ensures contiguity
and forces tariff zones to a desired spatial pattern (rings or stripes) without altering the modelstructure; (4) able to optimally solve instances of up to 120 districts (stops) within reasonable
time using off-the-shelf solvers.

2Modeling

We consider a public transport graph G PT : (I, A, τij ) with nodes i ∈ I, arcs (i, j) ∈ A, andtravel time τij . The set of nodes I represents the public transport stops and the set of arcs Aindicates the public transport connections between adjacent nodes (gray arcs and nodes, Figure1). We impose contiguity of each tariff zone using the properties of primal and dual graphs(Validi et al., 2020). We assume that each stop is located in a unique (artificial) district. Let
G BO : (N , B) be the district border graph, with nodes N and arcs B. Here, we consider G BO
as the dual to G PT . The problem includes a set Sij that contains the arcs that belong to thetime-shortest path through G PT of each origin-destination (O-D) tuple from i ∈ I to j ∈ I. Dueto the properties of planar dual graphs, for each arc (i, j) ∈ A there exist two intersecting arcs((n, m), (m, n)) ∈ B. Let us define set Dij denoting the border arcs (n, m) corresponding toTRISTAN XI Symposium

Original abstract submittal

S. Müller, K. Haase, L. Reyes-Rubiano

2n7i4
n3n8i5n4i1

i6n5i2n1

n6i3
n2

Figure 1 – Graphs of the RMTZP. Note, G BO contains more nodes than necessary for a dual graph.
G BO is shown in blue while G PT is displayed in light gray. Shortest path from stop (district) i1 tostop (district) i6 is highlighted in green. Assume t=2 tariff zones are optimal for O-D tuple i1-i6(Xi1,i6,2 =1) and the tariff zone border is between node i2 and i5, then Yn4,n5 +Yn5,n4 =1. This inturn induces and artificial flow along the border arcs to ensure contiguous zones (red).
(i, j) ∈ A. Now, let us define the set ODij containing the border arcs along the time-shortest
path from i ∈ I to j ∈ I.
Following, we summarize the variables and constraints of our MIP model P1 to solve RMTZP:Parameters
Tij : Maximum number of tariff zones along the shortest path from i ∈ I to j ∈ I (Tij ≤| Sij |+1)
rijt (πpt ) : Expected revenue if t = 1, . . . , Tij tariff zones are visited on the shortest path from i ∈ I to j ∈ Iand given price per zone πpt .
an : Feasible node degree of the border node n ∈ N
bn : Amount of artificial outflow or inflow at border node n ∈ NPu : Total sum of outflows over all border nodes n ∈ N (u = n|bn ≥0 bn )Decision variables
Xijt = 1, if t = 1, . . . , Tij tariff zones are visited on the shortest path from i ∈ I to j ∈ I (0, otherwise),with Tij as the maximum number of tariff zones along the shortest path from i to j
Ynm = 1, if a tariff zone border is established along border arc (n, m)∈ B (0, otherwise)
Wnm = 1, if there is a flow along the border arc (n, m) ∈ B (0, otherwise)
Maximize R(p) =TijXXX

rijt (πpt ) · Xijt

(1)i∈I j∈I t=1

subject toTij
X

Xijt = 1∀ i ∈ I, j ∈ I(2)Yn,m = 1∀ i ∈ I, j ∈ I(3)∀ (n, m) ∈ B | n < m(4)

∀n∈N

(5)

Wmn ≤ an

∀n∈N

(6)

Xijt ∈ {0, 1}∀ i ∈ I, j ∈ I, t = 1, ..., Tij(7)

Ynm ∈ {0, 1}∀ (n, m) ∈ B(8)Wnm ∈ {0, 1}∀ (n, m) ∈ B

(9)

t=1
Tij
Xt · Xijt −t=1

X(n,m)∈OD ij

X

Wnm − Wmn = Ynm
XWnm −Wmn = bnm∈BXm∈B

Wnm +m∈BTRISTAN XI Symposium

Xm∈B

Original abstract submittal

S. Müller, K. Haase, L. Reyes-Rubiano

3

The objective (1) maximizes the total expected revenue in the service area for a given pricesystem p ∈ P. Constraints (2) select the number of tariff zones visited for each O-D tuple.
Constraints (3) couples the number of tariff zone t · Xijt and the number of tariff zone borders
Ynm along the shortest path from i ∈ I to j ∈ I. The number of tariff zones visited from stop
i to stop j is equal to 1 plus the number of tariff borders crossed along the shortest path fromi to j. Equations (4) couple of Ynm and Wnm . If a tariff zone border is established between
adjacent stops i and j, i.e., Ynm =1 with (n, m) ∈ Dij , then there is a flow Wnm ∈ {0, 1} along(n, m) ∈ B. Equations (5) are flow constraints that indicate outflow minus inflow must be equal
to bn at border node n ∈ N . Values of bn depend on the desired spatial pattern of the tariffzone. The ring pattern occurs when bn =0 and an =2, and a striped pattern bn ≥ 1 and an =2.
Additionally, the stripe pattern is enforced by establishing a set of nodes n ∈ N as the source
nodes of the artificial flow and another set of nodes n ∈ N as the sink nodes for the artificial flow.
The flow conservation constraints (5) ensure contiguous tariff zones. Constraints (6) control thenumber of adjacent tariff zones at node n. Finally, the domains of the variables are given by (7),(7), and (9).
Relaxation of RMTZP: The size of the RMTZP is mainly influenced by the number of O-Dtuples. The expected R for each O-D tuple can be computed given a pricing system and amaximum number of tariff zones. We declare a subset C which contains γ· | I | of O-D tuples
with highest R; where γ ≥ 1 and determines the size of the subset C. We propose a MIP-basedheuristic to find C. Then, the model P1 is solved by considering O-D tuples ∈ C instead of alli ∈ I and j ∈ I.
Price problem: The zone problem P1 depends on a given price system p ∈ P. The trip priceunder a counting zone tariff system depends on the visited zones along the trip and the price perzone. Let rijt (πpt ) represent the R on the shortest path from i ∈ I to j ∈ I given price systemp ∈ P, with πpt as the price per zone when visiting t zones under price system pt ∈ P. R in
P1 is given by Equation (1). Therefore, we solve | P | independent zoning problems, select thesolution with maximum R, and benchmark these solutions against the optimal solutions of theRMTZP.

3

Computational experiments

In this section, we present the design of computational experiments and results. We evaluate theperformance of the MIP model and our MIP-based heuristic under different problem sets. The
performance is evaluated in terms of R and CPU time. We generate a set of artificial instances
representing the service area of a city. Total demand depends on the number of inhabitants ateach zone i, defined as a uniform [10,000; 20,000]. The total number of trips from i to j follows
a gravity model, while public transport shares follow a multinomial logit model.

3.1

Comparison of the MIP-based heuristic against the MIP modelWe solve all problem sets to optimality and compare the MIP model against the MIP-basedheuristic, considering the constraints to enforce tariff zones to have a ring pattern. Problem setsconsider different realistic sizes of | I |= {49, 81, 121}, | Tij |=7, and | P |=10, and a network
connectivity level given by {0.25, 0.5, 0.75, 1}. The larger the network connectivity level thelarger is | A | for given | I |.
Table 1 shows R of the solution obtained with MIP model and MIP-based heuristic over 10
seeds, and γ over the values { 2, 4, 8, 10, 15, 20, 25, 30}. Our first results show that the MIP
model provides a solution with higher R than the MIP-based heuristic solution. On average, ourMIP-based heuristic under estimates the optimal R by 2.54% but it is faster by 42.97%.

3.2

Impact of enforcing a desired spatial patternThis section is devoted to determine the impact of enforced spatial patterns on R. This numerical
study is focused on the MIP model P1 and the instance with | I |= 49. We determine the solution
TRISTAN XI Symposium

Original abstract submittal

S. Müller, K. Haase, L. Reyes-Rubiano

MIP

4MIP-based heuristicI

Expected revenue
10000 monetary units(a)⋆CPU timeseconds(b)⋆

Expected revenue
10000 monetary units(c)⋆CPU time
seconds(d)Gap(a) vs (c)Gap(b) vs (d)

49
81
121

1855.93
1939.49
2012.58

104.414087.39386384.54

1846.85
1899.39
1911.02117.15570.80175053.97

0.48
2.06
5.08

-16.05
87.47
57.48

2.54

42.97

Average

Table 1 – Comparison of R and CPU time of the MIP-based heuristic with respect to the optimalsolution. All problems are solved to optimality. (⋆) Average values over all seeds and network
connectivity levels
Ring pattern

No patternanR(10000 monetary units)

CPU time(seconds)

R(10000 monetary units)

CPU time(seconds)

234

1965.36
1965.36
1989.42125.76
1639.02
3308.62

1977.92
1977.92
1992.0710559.98
9051.3512980.14

Table 2 – Average R of the MIP model varying: constraints to enforce a ring pattern, and valuesof an .
for different values of border node degree an given by {2, 3, 4}. The value of an indicates themaximum number of adjacent tariff zones that gather at a district border node n ∈ N . Table
2 shows the average R and CPU times of solutions with and without a ring pattern. Results
demonstrate that solutions with a lower R are obtained when constraints are included to enforce
a desired spatial pattern compared to cases with no desired pattern. Solutions without any
spatial pattern have an R that is on average 0.43% higher than solutions with a ring pattern.
The CPU time for the solutions with no spatial pattern is 85.12% higher than for solutions withthe ring pattern.

4Conclusion

In this paper, we investigate how to design a counting zones tariff system to maximize therevenues of public transportation service companies. The price for a trip depends on the priceper tariff zone and the number of visited zones. This approach is well-known and accepted bypassengers and practitioners. We design an MIP model and an MIP-based heuristic to design
an optimal counting zones tariff system and solve the price problem. Our approach is based on
the properties of dual and primal graphs enabling contiguity of tariff zones and enforce spatial
patterns of the zones. The proposed methods can solve instances of reasonable sizes. Our
approach is flexible enough to enforce the counting zones tariff system to any spatial pattern.
The results show that enforcing tariff zones to a specif spatial pattern reduces R and CPU time.
Currently, we are working on testing our MIP-based heuristic with real data from the San
Francisco Bay Area with 1,415 districts (i.e., stops). Due to the irregular shape of the San
Francisco Bay Area, we are interested in studying how to enforce tariff zones to follow a desired
spatial pattern. In addition, we plan to analyze price systems with discounts.

References
Schöbel, Anita, & Urban, Reena. 2020. Cheapest Paths in Public Transport: Properties and Algorithms. In: 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization,and Systems (ATMOS 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik.
Validi, Hamidreza, Buchanan, Austin, & Lykhovyd, Eugene. 2020. Imposing contiguity constraints in political districting models. Preprint, http://www. optimization-online. org/DB_HTML/2020/01/7582.
html.

TRISTAN XI Symposium

Original abstract submittal