A Model for Finding Recoverable Robust Periodic Timetables
V. Grafea,∗ , A. Schöbela,ba Department of Mathematics, Technische Universität Kaiserslautern, Kaiserslautern, Germany

grafe@mathematik.uni-kl.de, schoebel@mathematik.uni-kl.deb Fraunhofer-Institute for Industrial Mathematics ITWM, Kaiserslautern, Germany∗ Corresponding author

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

March 30, 2022
Keywords: Periodic Timetabling, Delay Management, Recoverable Robustness, Mixed IntegerProgramming

1

MOTIVATION

An important aspect of optimising public transport is finding a good timetable. Often a periodic
timetable is desirable, i.e. a timetable which repeats in a regular pattern (e.g. every hour). On theone hand, short travelling times are important from the passengers’ point of view. The problemof finding a periodic timetable with minimal travelling times is known as the Periodic Event
Scheduling Problem (PESP) and is well researched, see e.g. Liebchen (2006). On the other hand,tight timetables without buffer times are prone to delays, which are inevitable in practice andhighly dissatisfactory for the passengers. Hence, a good timetable should also have some degreeof delay resistance. Many concepts and ideas on how to increase the robustness of a timetableagainst delays exist, see e.g. Lusby et al. (2018). However, none of these approaches uses thepromising concept of recoverable robustness introduced by Liebchen et al. (2009), although theliterature on delay management is dedicated to recovering timetables.
In our work we combine timetabling and delay management to be able to find recoverable robusttimetables. We develop a mixed integer programming formulation for the Recoverable Robust
Periodic Timetabling Problem (RRPT). Furthermore, we identify similarities and differences tostrictly robust timetables and analyse the relation between the nominal travelling time and thedelays. We also tackle the challenge of finding heuristic solutions.

2PROBLEM DESCRIPTION

We are given a scenario set U, where every scenario r ∈ U is a set of source delays. A timetable π
is called (α, β)-recoverable-robust w.r.t. U if for every r ∈ U there is a disposition timetable suchthat the total delay and the number of missed transfers (both weighted with the number ofpassengers) are bounded by α respectively β. The Recoverable Robust Periodic Timetabling
Problem is the problem of finding a periodic timetable which is (α, β)-recoverable-robust andminimises the nominal travelling time summed over all passengers.
We briefly describe the PESP, which is a common model for periodic timetabling. In the PESP weare given a period T together with a set of events E. Each event corresponds to the arrival or thedeparture of a traffic line at some station. Furthermore, we have activities A = Atrain ∪ Atransfer
TRISTAN XI Symposium

Original abstract submittal

V. Grafe, A. Schöbeli

La = 15
Ua = 202

j(a) Periodic activity

8 : 00

8 : 17

8 : 50

8 : 07

i1

j1

i1

j1

9 : 17

9 : 07

j2

j2

i1

j1

j2

(b) Rolled out activity for (c) Rolled out activity for (d) Both possible rolled
one timetable
another timetable
out activities

Figure 1 – Problem of rolling out a periodic EAN without knowing the timetable
which represent driving and waiting of trains (between and in stations) and transfers of passengers. We obtain an event-activity-network (EAN) N = (E, A). Every activity has a lower
bound La and an upper bound Ua for its duration. Additionally, wa is the number of passengers
using activity a ∈ A and wi is the number of passengers arriving at their destination i ∈ E. A
timetable with period T assigns a time πi ∈ {0, . . . , T − 1} to every event. Events are repeatedevery T minutes. The objective is to minimise the total travelling time.
In practice, delays may occur and make a timetable infeasible. A set of source delays is calleda scenario. The Delay Management problem (DM) consists of two tasks: finding a disposition
timetable, i.e. a new timetable which respects the source delays, and deciding which transfers
should be maintained and which can be cancelled. See Dollevoet et al. (2018) for a survey. As
delays do usually not occur periodically, DM is not considered in the periodic EAN, but in aaperiodic (non-periodic) network. Here, an event does not represent the arrival or departure ofa line (which repeats every T minutes), but of a single trip. DM usually has a timetable as
input. This timetable is used to roll out the periodic EAN N = (E, A) to the aperiodic network
N = (E, A) for some given planning horizon I = [tmin , tmax ]. If K is the number of periods inI, every periodic event i ∈ E has K corresponding aperiodic events i1 , . . . , iK in the planninghorizon to which we add b := dmaxa∈A Ua/T e further events to make sure that also the arcs leaving
I can be considered. The set of activities A depends on the timetable, as can be seen in thesmall example in Figure 1.
The goal of our paper is to integrate PESP and DM. PESP is a periodic problem in the EAN,
while Delay Management uses the aperiodic network N . For the integrated problem we have touse the same network. We decided to use the aperiodic network N . Finding a periodic timetablein an appropriately rolled out aperiodic network is called Periodic Timetabling in Aperiodic
Network (PTTA) and was introduced in Grafe & Schöbel (2021), where it was also shown tobe equivalent to PESP. It requires solving an assignment problem to choose activities for thetimetable (in Figure 1(d) one of the two dashed activities has to be chosen).

3MODELLINGWe develop a mixed integer programming formulation. The objective function minimises thenominal travelling time summed over all passengers. The constraints can be divided into twosubproblems as indicated by the boxes. For the master problem PTTA of finding a periodic
timetable in the aperiodic network N (see Grafe & Schöbel (2021)) we need timetabling variables πi for i ∈ E and assignment variables ua for a ∈ A. (1) and (2) ensure that the chosen
activities respect the upper and lower bounds. The synchronisation constraints (3) enforce periodicity. The assignment problem is included by (4). The auxiliary variables Fa determinie thetravel time needed in the objective function, see (5). Note that due to the periodicity of thetimetable it suffices to have these variables only for one period, i.e. we only define them for arcsof the form a = (i1 , jt ). (6) and (7) ensure that the timetable is indeed within the planning horizon. We have to solve the delay management problem in every scenario. As in Schöbel (2007),TRISTAN XI Symposium

Original abstract submittal

V. Grafe, A. Schöbel

Xmin3wa Fa · K(RRPT(U, α, β))PTTA

a=(i1 ,jt )∈A

πj − πi + M (ua − 1) ≤ Ua

a = (i, j) ∈ A(1)πj − πi + M (1 − ua ) ≥ La

a = (i, j) ∈ A(2)is ∈ E, 2 ≤ s ≤ K + b(3)a = (i, j) ∈ A, 1 ≤ s ≤ K(4)a = (i1 , jt ) ∈ A(5)πi ≥ tmini∈E(6)πi1 ≤ tmin + T − 1i∈E(7)πi ∈ Ni∈E(8)ua ∈ {0, 1}

a∈A(9)a = (i1 , jt ) ∈ A(10)

πis − πis−1 = TX
ua0 = 1
t:a0 =(is ,jt )∈A

Fa ≥ M (ua − 1) + πjt − πi1

DMFa ≥ 0xri ≥ πi + dri
0M (1 − ua ) + xrj − xri ≥ La + dra
M 0 (1 − ua ) + M 0 yar + xrj − xri ≥ LaXwa yar ≤ βi ∈ E, r ∈ U(11)

a = (i, j) ∈ Atrain , r ∈ U(12)a = (i, j) ∈ Atransfer , r ∈ U(13)r∈U(14)r∈U(15)a ∈ Aout , r ∈ U(16)i ∈ E, r ∈ U(17)a ∈ Atransfer , r ∈ U(18)a ∈ Aout , r ∈ U(19)a∈AtransferX

wis (xris − πis ) +X

wa Har ≤ αis ∈E:s≤K
a∈Aoutr
00
r
Ha ≥ M (ua − 1) + xj − πjxri ∈ Nyar ∈ {0, 1}
Har ≥ 0in the DM subproblem, for every r ∈ U we need variables xri determining the time of event i ∈ E
in the disposition timetable and binary variables yar for every transfer activity a, determining if
the transfer is maintained. An event can not take place earlier than in the original timetable
π (plus some possible source delay), as enforced by (11). For the driving and waiting activities
Atrain as well as for the maintained transfer activities Atransfer the disposition timetables haveto fulfil the lower bound (plus source delay), which is ensured by (12) and (13). The total delay
over all passengers and the number of missed transfers are bounded by α respectively β in (15)and (14). (16) give special attention to arcs leaving the planning horizon. Note that nearly all
constraints of (DM) are coupling constraints and that we use different sizes of big-M -constraints.

4ANALYSIS AND OUTLOOKFor the concept of strict robustness it is known that a robust feasible solution remains robust
feasible if the uncertainty set is extended to its convex hull (Ben-Tal et al., 2009). Unfortunately,
for recoverable robustness this is not true in general as demonstrated in Carrizosa et al. (2017).
However, we can show this property for a special case:
TRISTAN XI SymposiumOriginal abstract submittal

V. Grafe, A. Schöbel

4Lemma 1. If π is (α, 0)-recoverable-robust w.r.t. U, then it is also (α, 0)-recoverable-robust w.r.t.
conv(U), if the integrality constraint on x is relaxed.
Proof. Since π is (α, 0)-recoverable-robust w.r.t. U, for every r ∈ U there is a DM-solution(xr , 0) with delay bounded by α. In particular, we have xrj − xri ≥ La + dra for all
P a = (i, j) ∈Atrain ∪ Atransfer . Let r̄P∈ conv(U), i.e. all source delays are of the form dr̄aP= r∈U λr dra fora ∈ Atrain resp. dr̄i = r∈U λr dri for i ∈ E. For every i ∈ E define xr̄i := r∈U λr xri and setyar̄ = 0 for all a ∈ Atransfer . It follows for a = (i, j) ∈ A:
XX
XX
xr̄j − xr̄i =λr (xrj − xri ) ≥λr (La + dra ) =λr La +λr dra = La + dr̄a(20)r∈Ur∈Ur∈Ur∈U

Analogously, we obtain xr̄i ≥ πi + dr̄i for i ∈ E. The total delay isXXwa (xr̄j − πj )wi (xr̄i − πi ) +i∈E=X

a=(i,j)∈AoutX
λr (wi (xri − πi ) +r∈Ui∈E|Xwa (xrj − πj )) ≤ max Z r ≤ αa=(i,j)∈Aout{z=Z r(21)r∈U}

In particular, we show that for integral input data and β = 0 it suffices to solve RRPT only
for the extreme points of the scenario set, i.e. if we require that all transfers are maintained, wecan reduce our problem size considerably. We further analyse the relation between α, β and theobjective function value: Requiring only few delay leads to bad nominal travelling times.
The integer program is too large to be solved by a solver even for small instances. However,timetabling and DM can be tackled, which is the basis of iterative and decomposition approaches.
We develop an iterative heuristic which is tested on close-to real world examples from the LinTim
library (Schiewe et al., 2021).

References
Ben-Tal, Aharon, El Ghaoui, Laurent, & Nemirovski, Arkadi. 2009. Robust Optimization. Princeton
University Press.
Carrizosa, Emilio, Goerigk, Marc, & Schöbel, Anita. 2017. A biobjective approach to recovery robustness
based on location planning. European Journal of Operational Research, 261, 421–435.
Dollevoet, Twan, Huisman, Dennis, Schmidt, Marie, & Schöbel, Anita. 2018. Delay propagation anddelay management in transportation networks. Pages 285–317 of: Handbook of Optimization in theRailway Industry. Springer.
Grafe, Vera, & Schöbel, Anita. 2021. Solving the Periodic Scheduling Problem: An Assignment Approachin Non-Periodic Networks. Pages 9:1–9:16 of: ATMOS 2021. Open Access Series in Informatics(OASIcs), vol. 96. Dagstuhl – Leibniz-Zentrum für Informatik.
Liebchen, Christian. 2006. Periodic timetable optimization in public transport. Ph.D. thesis, TU Berlin.
Liebchen, Christian, Lübbecke, Marco E., Möhring, Rolf H., & Stiller, Sebastian. 2009. The conceptof recoverable robustness, linear programming recovery, and railway applications. Lecture Notes in
Computer Science, 5868, 1–27.
Lusby, Richard M., Larsen, Jesper, & Bull, Simon. 2018. A survey on robustness in railway planning.
European Journal of Operational Research, 266, 1–15.
Schiewe, Alexander, Albert, Sebastian, Grafe, Vera, Schiewe, Philine, Schöbel, Anita, & Spühler, Felix.
2021. LinTim: An integrated environment for mathematical public transport optimization. Documentation for version 2021.12. Tech. rept. Fraunhofer-Institut für Techno- und Wirtschaftsmathematik.
Schöbel, Anita. 2007. Integer Programming approaches for solving the delay management problem. Pages
145–170 of: Algorithmic Methods for Railway Optimization. Lecture Notes in Computer Science, no.
4359. Springer.

TRISTAN XI Symposium

Original abstract submittal