An evaluation of the fairness of railway timetable rescheduling in
the presence of competition between train operators

E. Reynolds , M. Ehrgott and J.Y.T. Wang
STOR-i, Lancaster University, Lancaster, United Kingdom
e.s.reynolds@lancaster.ac.uk
Lancaster University, Lancaster, United Kingdom
m.ehrgott@lancaster.ac.uk
University of Leeds, Leeds, United Kingdom
j.y.t.wang@leeds.ac.uk
Corresponding author
a

a

b,∗

c

b

c

∗

Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

Keywords: railway optimisation, fairness, timetable rescheduling
1

INTRODUCTION

Eective real-time management of railway trac is crucial to delivering good railway performance. In particular, making changes to the timetable in response to an initial delay can help
to reduce the amount of additional delay caused to other trains as a result of the initial incident. This practice is known as timetable rescheduling. The Train Timetable Rescheduling
Problem (TTRP) (Cacchiani et al., 2014) can be solved in order to determine the optimal way toreschedule the timetable. A large number of dierent TTRP problem variants, models, objectivefunctions and solution methods have been studied.
However, the implications for TTRP models of economic competition between railway operators has not been considered widely, see (Luan et al., 2017). In recent decades, dierent
forms of competition have been introduced in several European railway systems, such as thoseof Germany, Great Britain and Sweden (IBM, 2011). Where trains are operated by more than
one dierent company over the same tracks, timetable rescheduling has the potential to impact
these operators unequally. In order to be perceived as fair, a TTRP model must not systematically favour some operators over others. A perception of unfairness would be a serious barrier
to the practical deployment of TTRP models in competitive railway systems. Therefore, it isessential that the fairness characteristics of such models are understood. This study investigates
the fairness of solutions obtained from solving the TTRP.
This paper is organised as follows. We rst describe our methodology by dening our notionsof fairness and eciency and how to evaluate them. In our results section, we present an analysisof the fairness of eciency-maximising TTRP solutions. This is supplemented by an analysisof the interactions between pairs of operators, where we also consider the fairness-eciency
trade-o.
TRISTAN XI Symposium
An evaluation of the fairness of railway timetable rescheduling

E. Reynolds, M. Ehrgott and J.Y.T. Wang
2

2

METHODOLOGY

2.1 Eciency
Our measure of the overall system eciency was developed with Network Rail for our TTRP
system (see Reynolds (2020)). It is designed to model the utility of Network Rail, which
can be seen as the central decision maker for rescheduling decisions. It is designed to take into
account the overall quality of service provided to passengers.
Given a feasible solution x to a given instance, the eciency is dened asXX
U (x) =
U (x) + w
U (x),(1)
et al.

k

k

k∈K1

k∈K2

where K and K are sets containing the class 1 (express passenger) and class 2 (ordinary passenger) trains, respectively, U (x) is the utility accrued from train k, and w = 0.4 is a weightthat controls the priority given to class 1 trains in comparison to class 2 trains. The priority
given to class 1 trains by the value of w reects the fact that class 1 trains typically carry morepassengers. Furthermore, class 1 trains usually complete longer journeys and hence delays toclass 1 trains can have a greater impact in terms of reactionary delay outside the geographicalscope of the TTRP instance.
The utility U (x) accrued from train k is calculated as a weighted average across the set J
of timetabled events for train k within the area and time horizon modelled:
X
U (x) =β U (x).
(2)
1

2

k

k

k

j
k

k

j
k

j∈J k

Each event j ∈ J in the timetable for train k corresponds to a particular part of the track, anda time that train k is due to enter it. These can include arrival events at platforms and passing
events at junctions or key points along a route. The values of β ensure that more important
events, such as an arrival into a major station or exiting the modelled area, are weighted more
highly than events at minor stations. When alternative platforms are available, these are separate
events j ∈ J . For events j at platforms other than the originally scheduled platform, β is 0.9
times the weight at the originally scheduled platform. This discourages platform changes.
The eciency E(x) of a set of solutions x = (x : i ∈ I) to the whole set of instances I
can be calculated by summing the individual eciency of each solution. Denoting the eciency
function U when applied to each instance i as U , this can be written as
X
U (x ).
(3)
E(x) =
k

j
k

j
k

k

i

i

i

i

i∈I

2.2 Fairness
For a given instance, let the set of operators be O, and let K ⊂ K be the set of trains that areoperated by operator o. The eciency function U (x) can be rewritten as
X
U (x) =
U (x),
(4)
where
X
X
U (x) =
U (x) + w
U (x)(5)
is the part of the eciency arising from trains operated by o. Since U (x) includes only trainsfrom operator o, it can be used to measure the utility of operator o.
The utilities U (x) are dicult to compare because there might be dierent numbers of trains
with dierent weights in the instance. For each operator o ∈ O, let x be an optimal solution
TRISTAN XI Symposium
An evaluation of the fairness of railway timetable rescheduling
o

o

o∈O

o

k

k

k∈K1 ∩Kok∈K2 ∩Ko

o

o

∗
o

E. Reynolds, M. Ehrgott and J.Y.T. Wang

3

when the objective is to maximise U (x), rather the total utility U (x) over all operators. Eachsolution x represents the best solution operator o can hope for, and U (x ) provides an upperbound for U (x). This allows us to calculate a normalised utility for each operator
U (x)Û (x) =.
(6)
U (x )
These values can be compared between operators. A value of Û (x) = 1 indicates that
operator o realises their maximum possible utility in the rescheduled solution x  all events for
all trains are due to be carried out on time and as planned. Conversely, Û (x) < 1 indicates that
one or more events have been cancelled or rescheduled to occur on a dierent platform, or late.
A social welfare function (such as α-fairness, Atkinson (1970)) could be applied to the set ofutilities {Û (x) : o ∈ O} to measure the fairness of the solution x for a single instance. This would
allow fairness to be formulated as an objective function so that fairness-maximising solutions to
individual instances could be computed to solve the TTRP. It would also open the possibilityof using multi-criteria methods to balance the objectives of maximising fairness and maximisingeciency within each instance.
However, when considering operator fairness for timetable rescheduling, it is problematic tofocus on single hour-long instances separately. This is because operators experience fairness andunfairness over a much longer period of time. The operation of a TTRP algorithm on a railway
is likely to involve solving hundreds of dierent instances, involving repeated allocations of track
capacity between the same sets of operators. Instead, it is much more appropriate to consider
many consecutive instances of the problem as a single, combined allocation problem. That is theapproach taken in this paper.
Considering fairness over a whole instance set rather than on an individual instance basis
has important implications for fairness. It means that each individual instance need not be fair,
provided any operators that loose out can be compensated in other instances. This is crucial
when one considers that a typical TTRP instance considers changes to the timetable over a time
horizon of only one hour. Many instances involve only a small number of decisions such as which
train should go ahead of the other out of a pair of conicting trains. It may be impossible toresolve such problems in a fair way, or doing so may require a large degradation in eciency.
Our approach of considering fairness over the whole instance set overcomes this issue.
Consider a set of solutions x = (x : i ∈ I) to a set of instances i ∈ I . We index theprevious notation by i so that O , U , Û and x correspond to the notation O, U , Û and x ,respectively, when applied to each instance i. Note that the set of operators O can be dierent
across instances.
The normalised aggregated utility for operator o over I can be calculated as
o

∗
o

∗
o

o

o

o

o

∗
o

o

o

o

o

i

i

i,o

i,o

i,∗
o

o

o

∗
o

i

X

Ûo (x) =Uo,i (xi )i∈I:o∈Oi

X

Uo,i (xi,∗
o )

.

(7)

i∈I:o∈Oi

These values are then used in the α-fairness welfare function to produce our measure of fairness:
X Ûo (x)1−α




1−α
o∈O
Fα (x) =Xlog Ûo (x)α ≥ 0, α ̸= 1
α = 1.

(8)

o∈O

3

RESULTSAn area of railway around Doncaster station has been used as a case study for evaluating fairness.
Denitions of any railway signalling terminology used below can be found in (Reynolds et al.,TRISTAN XI Symposium
An evaluation of the fairness of railway timetable rescheduling

E. Reynolds, M. Ehrgott and J.Y.T. Wang

42020). Doncaster station lies on the East Coast Main Line, a busy railway corridor connecting
London with Leeds, York, Newcastle and Edinburgh. The wider area covered also contains
portions of four double track lines that all begin at Doncaster and go towards Sheeld, Lincoln,
Leeds and Hull, respectively. The area lies within a single area of signalling control, and contains
225 berths with 313 valid berth transitions. The station itself has 9 platforms and 85 track
circuits. Doncaster station is an important interchange for a variety of inter-city and local
services operated by seven dierent operators. It is also a busy bottleneck, with over 30 trains
per hour at peak times. This makes it ideal for investigating the interactions between dierent
operators.
The data for the case study comes from January 2017. Seven dierent passenger operators run
services through the area during this month. Operators NT and LNER operate 41% respectively
35% of the 10,027 trains in the period. More than 80 % of NT's trains are class 2 and thesetrains make up 93% of all class 2 trains. All trains operated by LNER and four other operators
are class 1.
The month of January 2017 is split into 310 non-overlapping hour-long instances of the TTRP
(between 8am and 6pm each day, for 31 days). These instances are created from real historical
data about the timetable, and the trac perturbations that actually occurred. The number ofoperators running trains in each instance ranges from two to six, with the most common number
being ve. By using instances that cover a whole month, we are able to understand fairness over
the whole month, rather than on an instance-by-instance basis.
For each of the 310 instances, an eciency-maximising solution was calculated using a solving
time limit of 600 seconds. Only 12 instances were not solved to optimality within this time limit.
For these instances, the best solution found during the time limit was selected, which was lessthan 1% away from optimality in all cases.
The normed aggregated utility Û (x) ranged between 0.996 and 0.999. However, the proportion of instances, where Û (x ) = 1 was between 41.3 % and 88,9 %. In particular the value of
41.5% for one operator was considerably lower considerably lower than for all other operators,
so that there is inequality in these gures. We also observed that the α-fairness of the set of
instances is better than that of some individual instances, but on the whole fairer instances are
more numerous than less fair ones.
To understand sources of unfairness we further analysed the pairwise trade-os between
operators. We furthermore studied the inuence of parameter w = 0.4 (see Section 2.1) on
the computation of fairness. To this end, we re-solved all instances twicw, namely with values
w = 0.7 and w = 1 and observed that increasing w increases fairness and decreases eciency.
To conclude, we observed that there is unfairness in solutions to the TTRP problem,and thatthe value of w has a considerable inuence on the level of unfairness.
o

o,i

i

References
Atkinson, Anthony B. 1970. On the Measurement of Inequality. Journal of Economic Theory, 2, 244263.
Cacchiani, Valentina, Huisman, Dennis, Kidd, Martin P., Kroon, Leo G., Toth, Paolo, Veelenturf, Lucas P., & Wagenaar, Joris C. 2014. An overview of recovery models and algorithms for real-time railway
rescheduling. Transportation Research Part B: Methodological, 63, 1537.
IBM. 2011. Rail Liberalisation Index. http: // www. assorail. fr/ wp-content/ uploads/ 2015/ 08/
Rail_ Liberalisation_ Index_ 2011. pdf .
Luan, Xiaojie, Corman, Francesco, & Meng, Lingyun. 2017. Non-discriminatory train dispatching in a railtransport market with multiple competing and collaborative train operating companies. Transportation
Research Part C: Emerging Technologies, 80, 148174.
Reynolds, Edwin, Ehrgott, Matthias, Maher, Stephen J, Patman, Anthony, & Wang, Judith Y T. 2020. A
multicommodity ow model for rerouting and retiming trains in real-time to reduce reactionary delay incomplex station areas. http: // www. optimization-online. org/ DB_ HTML/ 2020/ 05/ 7816. html .

TRISTAN XI Symposium

An evaluation of the fairness of railway timetable rescheduling