FAKULT ¨
AT II
MATHEMATIK UND
NATURWISSENSCHAFTEN
Institut f ¨ur Mathematik
Computing Delay Resistant
Railway Timetables
by
Christian Liebchen
Michael Schachtebeck
Anita Sch¨
obel Sebastian Stiller
Andr´
e Prigge
No. 2007/17
Computing Delay Resistant
Railway Timetables∗
Christian Liebchen Michael Schachtebeck
Anita Sch¨obel Sebastian Stiller Andr´e Prigge
March 31, 2007
Abstract
In the past, much research has been dedicated to compute opti-
mum railway timetables. A typical objective was the minimization of
passenger waiting times. But only the planned nominal waiting times
were addressed, whereas delays, as they occur in daily operations, were
neglected. Delays were rather treated mainly in an online-context, and
solved as a separate optimization problem, called delay management.
We provide the first computational study which aims at computing
delay resistant periodic timetables. In particular we assess the delay
resistance of a timetable by evaluating it subject to several delay sce-
narios, to which optimum delay management will be applied.
We arrive at computing delay resistant timetables by selecting a
new objective function which we design to be in the middle of the tra-
ditional simple timetabling objective and the sophisticated delay man-
agement objective. This is a slight extension of the concept of “Light
Robustness” (LR), as it was proposed by Fischetti and Monaci (2006).
Moreover, in our application we are able to provide accurate interpre-
tations for the ingredients of LR. We apply this new technique to
real-world data of a part of the German railway network of Deutsche
Bahn AG. Our computational results suggest that a significant de-
crease of passenger delays can be obtained at a relatively small price
of robustness, i.e. by increasing the nominal travel times of the pas-
sengers.
∗This work was partially supported by the Future and Emerging Technologies Unit of
EC (IST priority - 6th FP), under contract no. FP6-021235-2 (project ARRIVAL) and by
the DFG Research Center Matheon in Berlin.
1
1 Introduction
Timetabling is among the most important tasks for optimization in public
transport. Not surprisingly the construction of timetables is a well studied
problem in the literature, and has been treated under various objective func-
tions. Besides technical restrictions and optimization of costs the main focus
lies on finding timetables which are optimal from the passengers’ point of
view. However, in most papers only the nominal travel times are considered
while the possibility of delays and stochastic changes is neglected. In reality
delay is a considerable phenomenon in almost all public transport systems.
It plays a particular role for customers’ satisfaction.
There is of course a trivial way to come up with delay resistant timetables:
Simply add huge time supplements on each trip. However, it is obvious that
such a solution is unacceptable for passengers. Delay resistance may not be
attained by inserting arbitrarily large time supplements. Rather, the art of
delay resistant timetabling is to achieve a certain level of robustness by a
minimum increase in nominal travel times.
Recently, theoretical studies have been directed towards the problem of de-
signing delay resistant timetables ([KDV05, LS06]). Kroon et al. consider
single trains and non-periodic corridors in a sampling approach. In both pa-
pers the construction of delay resistant timetables is considered as a matter
of most effectively placing a limited amount of slack time in the timetable.
They present optimization techniques aimed at minimizing the expected de-
lay for various topologies and network sizes. Although a variety of different
methods and settings is considered, all of this is done under the following
assumption: When the timetable is operated, the reaction towards delay will
follow a simple pattern, i.e., either always to wait for delayed trains or always
not to wait for delayed trains. Obviously, smarter reactions are possible.
There exists some literature on how to deal with delays when they occur
and find a disposition timetable which is as convenient as possible for the
passengers under the given circumstances. This problem is called delay man-
agement problem and includes to decide which connections between trains
should be maintained and which not, see [Sch06b] and references therein.
It would be desirable to optimize delay resistant timetables with respect to
an optimal delay management. But as the latter is already a hard problem
for a fixed plan and a fixed scenario of delays, a full integration of the two is
out of computational reach. However, we can clarify the following question:
Given a real-world data set for which optimal delay management is possible
within practical computation time. How does a delay resistant timetable
behave, that has been optimized for a simplified delay management? The
2
question is, whether those timetables keep what they promise, namely, that
disturbances do not affect the quality of service to the passengers too much,
if good delay management strategies are applied.
Although this is a straightforward question, it has to the best of our knowl-
edge not been treated in the literature before. In our paper we bridge this
gap between delay resistant timetabling and delay management. We consider
a real-world railway network. In a first step, we apply a new technique to op-
timize periodic timetables for different degrees of robustness. This is a slight
extension of the paradigm of “Light Robustness” as it had been proposed by
Fischetti and Monaci [FM06]. The resulting timetables are in a second step
confronted with different sets of disturbances. By solving the delay manage-
ment problem for each of these delay scenarios we obtain optimal disposition
timetables, from which we evaluate how much the passengers are affected
by the disturbances. We hence obtain a new empirical measure about the
quality of the original timetable.
This case study also allows to evaluate the power of optimal delay manage-
ment. In fact, we will also calculate the delay experienced by the passengers,
if the same timetables and the same set of source-delays are managed by a
simple delay management policy.
In some sense we combine the expertise of state-of-the-art delay management
and topical delay resistant timetabling techniques in order to overcome the
shortcomings of both. On the one hand, the optimization of timetables
cannot take into account a complicated delay management, but it optimizes
with respect to all scenarios of delay. On the other hand, delay management
can only be repeated for a small set of scenarios—in fact a very small set in
relation to the set of all scenarios. But it is optimal for each of these.
It turns out that the effects of delays are less worse in the delay resistant
timetables that we construct in our study than in a conventional timetable.
In addition, it becomes clear that a good delay management provides even
better disposition timetables. Finally, the delay resistant timetabling proves
particularly effective against short delays.
Related Work. The only comparable work we are aware of is due to
Engelhardt-Funke and Kolonko, see [EFK04]. Unlike ours their approach is
able to integrate the delay management into the construction of the timeta-
bles by evolutionary algorithms. Our approach in the first step constructs
optimal timetables with respect to the expectation over all scenarios for a
carefully simplified objective function. In the second step it evaluates them
with a limited number of scenarios and an optimal delay management policy,
thus for the real objective function in these scenarios. In contrast, in [EFK04]
3
for the heuristic construction of the timetable an evaluation is used, which
is not based on an optimal delay management and which solely relies on a
limited number of scenarios. Their construction of the timetable is not an
optimization in the strong sense, and they never pay respect to an optimal
delay management nor do they at any point take into account all scenarios.
The carefully simplified objective function we use to optimize is similar to
the one introduced by PTV AG, Germany, in its planning software VI-
SUM in order to enrich their evaluation by some penalty for tight—and
thus vulnerable—transfers. We give an exact interpretation of this objective
function, that allows to choose suitable parameters. Note again, that for
evaluation we use an exact objective, involving optimal delay management.
Outline. The remainder of the paper is structured as follows. In Section 2
we define our models for periodic timetabling, stochastic disturbances, and
delay management. We also explain in detail how event-activity networks
can be used to model both the periodic event scheduling problem as well as
the delay management problem. Our approaches for finding delay resistant
timetables, using them as input for defining delay management problem, and
solving these problems are developed in Section 3. In Section 4 we describe
the real-world data we used for our case study. Finally, we present the results
of the case study in Section 5 and give some conclusions for further research.
2 Models
In this paper we deal with two mathematical optimization problems: In our
first step we compute optimal periodic timetables with a robustness against
delays incorporated to the objective function; in the second step we solve the
delay management problem, i.e. we determine a disposition timetable to react
on a given set of (small) disturbances. Since both problems are timetabling
problems we start by recalling the concept of event-activity networks, which
can be used to model both of our problems.
2.1 Event-activity networks in timetabling
The basic graph model that we use is the Feasible Differential Problem (FDP),
see [Roc84]. In an instance I= (D, ℓ, u) of FDP, where D= (V, A) is a di-
rected graph and ℓ, u ∈QA, a vector π∈QVis sought such that
ℓa≤πj−πi≤ua,∀a= (i, j)∈A. (1)
4
Observe that by introducing antiparallel arcs, formally each instance of FDP
can be transformed such that ℓa=−∞, for all a∈A′. What remains are
nothing but the optimality conditions for the distance labels in the Shortest
Path Problem (SPP). In particular, for an instance Iof FDP there exists a
solution π, if and only if the transformed instance of SPP does not contain
any directed circuit of negative length.
The nodes in the network are called events and correspond to arrivals or
departures of trains at stations, i.e.
V=Varr ∪Vdep.
The vector πis then called a timetable, the value πiis the time instant at
which the event iis scheduled. One may think of πias an absolute point in
time of the day.
Of course, the times πimust not be chosen arbitrarily. Rather, they must
respect many operational and marketing requirements. These are encoded
by the constraints (1) that are defined for the arcs of the network. Observe
that the quantities πj−πiare time durations, and we refer to the arcs as
activities. We partition the set of activities into five subsets
A=Adrive ∪Astop ∪Atransfer ∪Aturn ∪Ahead,
where we explain the meaning of these subsets right after having presented
how periodicity is added to FDP.
In a periodic timetable, trains are grouped into lines which are required to
be operated with some periodicity T. In the case of T= 120 minutes, this
means that if one train of some fixed line starts its trip at 10:05, then there
will be a train five minutes past every even hour.
We obtain subsets of non-periodic events ikthat take place at time πik=
πi+kT for ai< k < bi, k ∈Z. Such a set represents the departure (or arrival)
of all trains of the same line at a specific station, and will in the following be
represented by one periodic event i. We can hence reduce the event-activity
network above to a periodic one,
D= (V , A)
in which Vconsists of equivalence classes of events in V. For i∈Vlet us
denote by V(i) the set of non-periodic events belonging to a given periodic
event i.
Consequently, if the goal is to find a periodic timetable, the mathematical
optimization model features the variables πifor the periodic time assigned to
the equivalence classes rather than those for the non-periodic events ik. It is
5
fruitful to think of the equivalence classes i={ik}kas periodic events with πi
as the periodic time assigned to i. As in such a periodic system every action
repeats after the period time T, one can assume w.l.o.g. that πi∈[0, T). The
values πiare of course still time instants. But in contrast to the values πik,
they do no longer refer to an absolute point in time of the day. Rather, they
refer to a point in time of one abstract copy of the period time. Section 3.3
describes in detail how the periodic events’ times are rolled out to obtain the
non-periodic event times.
The corresponding decision problem is called Periodic Event Scheduling Prob-
lem (PESP), see [SU89]. In addition to the input to an instance of FDP, a
fixed constant period time Tis specified. But in contrast to other approaches
to timetabling ([DV95, KS88]), in any of our computations we will use Tonly
in its binary encoding. In T-PESP—or PESP for short—one looks for a vec-
tor π∈[0, T)Vsuch that
∀a= (i, j)∈A∃ka∈Z:ℓa≤πj−πi+T·ka≤ua.(2)
The decision problem whether a given network admits a feasible solution π
is NP-complete, because it generalizes Vertex Colorability ([Odi96]). As in
the non-periodic case, we also partition the set Aof periodic constraints into
five subsets
A=Adrive ∪Astop ∪Atransfer ∪Aturn ∪Ahead.
Observe that the PESP is the building block of many studies on periodic
railway timetabling ([SS94, Nac98, Lin00, KP03, Lie06]). In particular, the
first mathematically optimized timetable that went into daily operation has
been computed based on the PESP ([Lie05a]).
On the one hand, periodic timetables are a specialization of general timeta-
bles in which each trip may be scheduled individually. Hence, in terms of
well-quantifiable objectives no periodic timetable will ever be strictly better
than the best general timetable. On the other hand, there have been identi-
fied many non-quantifiable criteria with respect to which periodicity adds an
additional benefit ([Lie05b]). Indeed, most public transportation companies
in Europe operate their networks subject to periodic timetables. This is why
in our case study we will always compute periodic timetables as the regular
service timetables. In contrast, the goal of any disposition timetable is to
react on the specific disturbances that occur during each individual day of
operation by tailored decisions. Hence, disposition timetables always have to
be non-periodic.
Now we explain the meaning of the five subsets of activities. Only the head-
way activities require different treatments in the non-periodic case (Ahead)
6
and in the periodic case (Ahead). We will leave out the Anotation for a
moment.
•Driving activities. The arcs in Adrive represent the driving of a train
between consecutive stations, i.e. a driving activity connects a depar-
ture event of some train twith its next arrival event. The bounds ℓa
and uarepresent the minimum and maximum allowed driving time.
•Stopping activities. The arcs in Astop model the time period in which a
train is stopping in a station to allow passengers to board and un-board.
A stopping activity hence connects an arrival event with a departure
event, if both events refer to the same train and the same station.
•Transfer activities. The arcs in Atransfer indicate that a transfer for the
passengers is possible from some train t1to another train t2. Conse-
quently, a transfer activity connects the arrival of train t1at a station
to the departure of train t2at the same station. The bound ℓarefers
to the minimum time passengers need when they change from t1to
t2. And uaensures a minimum level of quality because it prevents the
transfer waiting time from getting arbitrarily large.
Note that in the periodic formulation the optimizer retains the free-
dom to implicitly decide to which non-periodic event πjka passenger
arriving with event πi′
kwill connect. The offset kais chosen to ensure
that for given πi, πjthe shortest connection time, i.e., the connection
to the next train from A to B is counted.
•Turnaround activities. The arcs in Aturn are introduced, because each
timetable does not only affect the passengers, but also has an immedi-
ate impact on the operating costs, i.e., on the number of trains that are
required to operate the timetable. A turnaround activity thus measures
the time duration from the arrival of a physical train in its terminus
station until the departure of the same physical train, e.g., in the op-
posite direction. The lower bound ℓaensures that a train will only be
planned for its next trip, if that trip respects the (technical) minimum
turnaround time, see [LM04] for further details.
•Finally, the headway activities Ahead are needed to model the limited
capacity of the track system. There are two types: The first type refers
to trains departing from the same station into the same direction. By
setting the lower bound ℓaas the minimum security distance, they
guarantee that there is enough time between the two departures. In
the periodic case, the upper bound uathen is T−ℓa, where we assume
7
identical speeds of the trains, but different speeds can be modeled,
too, see [LM04, Lie06]. The second type refers to single track segments
between two stations. Here, a train has to wait until an oncoming train
has arrived.
In the aperiodic case, both types of headway constraints have to be
modeled as disjunctive constraints, i.e. only one of each pair of them
has to be respected: Either ihas to wait until i′is finished (plus some
security time ℓii′) or vice versa. This is due to the fact that the order
of the events i, i′is not given a priori.
The travel times and transfer activities will play the central role in our
stochastic expansion of the PESP, see Section 3.2. To conclude, a great
variety of features of railway timetabling is covered by event-activity mod-
els like FDP and PESP. Many more practical requirements can be modeled,
see [LM04, Lie06] for the case of periodic timetabling. Hence, these models
are the models of choice for the timetabling problems that we are going to
deal with.
station Dstation B
station C station E
station A
train h
train g
Figure 1: A part of a public transportation network with five stations and two
trains. After their departure in Aboth trains have to use the same track.
As an example, Figure 2 shows the (small) event-activity network corre-
sponding to the public transportation network of Figure 1.
If the time duration that a timetable πdefines for an activity aexceeds its
lower bound ℓa, we speak of slack, its amount is given by
(πj−πi)−ℓa≥0 or (πj−πi+T·ka)−ℓa≥0
in the non-periodic, or in the periodic case, respectively. In the pure fea-
sibility problems FDP and PESP, the quality of a timetable is ensured by
8
driving driving
driving
driving
of train g
of train g of train h
waiting of train h
of train h
waiting
of train g
from train h to g
from train g to h
headway constraints
disjunctive
g,D,arr
g,A,dep
g,A,arr h,A,dep
h,A,arr
g,E,dep
h,C,dep
h,B,arr
transfer
transfer
Figure 2: The event-activity network corresponding to Figure 1.
defining strict upper bounds ua−ℓaon the slack, e.g. for the most important
transfer activities.
There exists an alternative to ensure transfer quality in a network: minimiz-
ing the objective of total passenger transfer times in the entire network. To
this end, we must be given the number of passengers wafor each transfer
activity a∈Atrans, or a∈Atrans, respectively. Formally, we simply have to
minimize the linear objective function of the weighted sum of slack. There-
fore, in the periodic case the upper bound uais set to ua=ℓa+T−1,
whereby any (integer) transfer waiting time becomes feasible. Still shorter
waiting times are better than longer ones in respect to the linear objective
function.
Another motivation for a linear objective function is the fact that the timetable
has an immediate effect on the number of trains that are required for its op-
eration. In the case of periodic timetables, it has been shown that in the
PESP model only a linear objective function admits an adequate integration
of the corresponding real-world piecewise constant cost function ([LM04]). In
the case of a linear objective function being added to an instance of PESP,
we speak of an optimization instance of PESP.
9
2.2 The Source of Delay
As model of disturbances we assume the driving time of each train to vary
according to a known probability distribution. Therefore, the lower bounds
for arcs a∈Adrive or ∈Adrive corresponding to a single (periodic) train
ride are random variables ℓa:R→Q+, where Ris the set of all scenarios.
To comply with standard notions such a disturbance from now on will be
called a source delay. We distinguish between source delays, i.e., the seminal
prolongation of a trains’ driving time, and delays which result from source
delays. A source delay may cause several delays at different stations, even for
trains that have not themselves been subject to a source delay. Whereas in
a different situation, e.g., a schedule including a large amount of slack time,
a source delay may result in no delay at all.
As we are optimizing periodic timetables we also have to explain how source
delays and resulting delays fit into the periodic framework. Both, the periodic
and the non-periodic, singular perspective on disturbances is reasonable. A
periodic source delay is, e.g., a construction site slowing down all train trips
realizing a certain driving arc in every period. Whereas a singular source
delay could be a jammed door delaying a single train trip realizing this driv-
ing arc only in a single period. As singular source delays make up for an
important part of the practically relevant source delays, we cannot neglect
them. But a single singular source delay could affect several periods, and
each in a different way. Thus its incorporation into the stochastic PESP
model promises to be difficult. Periodic source delays cause the question,
whether the source delay of each period will be absorbed until the similar
event of the next period takes place. If this is not the case periodic source
delays have non-periodic consequences, too. Fortunately, this difference will
be immaterial in our optimization approach.
Moreover, we only specify the boundary distribution on each driving arc
instead of their joint distribution. In fact, for our optimization approach it
will be sufficient to know these boundary distributions, as will become clear
in Section 3.2.
In order to assess the delay resistance of a schedule the optimizer needs
not only to know the distribution of the source delay but also the reaction
towards source delay in a realization. This reaction is what is called delay
management policy.
We will explain and formalize the problem of delay management in the fol-
lowing section.
An ideal optimization takes the expectation of some objective function which
describes the behavior of the timetable and a corresponding optimal dispo-
sition timetable for each scenario, including singular and periodic source
10
delays, weighted according to their joint distribution. Here one has to make
some careful but effective simplifications to compute the timetables. This
will be found in Section 3.2.
2.3 Delay Management problem
Delay management deals with (small) source delays of a railway system, as
they occur in the daily operational business of any public transportation
company. In case of such delays, the question is to decide if trains should
wait for delayed feeder trains or if they better depart on time (wait-depart
decisions). From these decisions one obtains a disposition timetable. Such
a timetable has to respect operational constraints, in particular the limited
capacity of the track system. The difficulty of delay management comes with
the following evident goal: make the disposition timetable as convenient as
possible for the passengers.
If the transfer activities and the headway activities are neglected, the problem
is easy and can be solved efficiently by the critical path method (CPM). If
either the transfer activities or the headway activities are taken into account,
the problem gets NP-hard even in very special cases, see [GJPS05, GGJ+04,
CS07]. Neglecting only the headway activities, we obtain the (pure) delay
management problem. An integer programming model based on a repre-
sentation of the problem in an activity-on-arc-project network is given in
[Sch01, Sch06b]. These publications include an investigation of the special
structure of the activity networks used in delay management. The model
will be described in detail in Section 3.4. The general integer programming
model was further refined in [GHL06].
A first online-approach is provided in [GJPW07]. A bicriteria model for de-
lay management in the context of max-plus-algebra has been presented in
[RdVM98], a formulation as discrete time-cost tradeoff problem is given in
[GSar]. How to react in case of delays has also been tackled by simulation
and expert systems. We refer to [SM97, SM99, SBK01, SMBG01] for pro-
viding knowledge-based expert systems including a simulation of wait-depart
decisions with a what-if analysis. Real-world applications have been studied
e.g. within the project DisKon supported by Deutsche Bahn (see [BGJ+05]).
3 Integer programs
In the previous section we explained the pure theory, the ideal model. In
this section we are looking for ways to solve it. First we explain the integer
11
programming approach to the deterministic PESP. After that we give a de-
tailed description how we incorporate stochasticity and delay management
into this approach. This incorporation process has to find a smart balance
between accurate modeling and the mandatory feature not to increase the
size of the PESP-IP substantially. This is mandatory in order to construct
plans on the real-world level.
The last two parts of this section deal with the techniques used, when the
periodic timetable is fixed. First we explain how the periodic timetable is
rolled-out into a non-periodic plan based on which an instance of the delay
management problem is created. Each of these instances entails a concrete
scenario of source delays. In the last part of this section we explain one more
integer programming approach. This time it solves the delay management
problem.
3.1 Computing Optimum Periodic Timetables
The most straightforward way to compute an optimum solution for an op-
timization instance of PESP is to solve the following mixed-integer linear
program
(PESP-IP-π)min f(π, p) = X
a=(i,j)∈A
˜wa·(πj−πi+T·ka−ℓa)
such that
πj−πi+T·ka≤uafor all a= (i, j)∈A(3)
πj−πi+T·ka≥ℓafor all a= (i, j)∈A(4)
πi≥0 for all i∈V(5)
πi< T for all i∈V(6)
ka∈Zfor all a∈A.(7)
The constraints (3), (4), and (7) are a rephrasing of (2), and the con-
straints (5) and (6) scale the time vector πto the basic interval [0, T). Ob-
serve that (π, k) = (0,1
T·ℓ) is a trivial optimum solution of the LP relaxation
of PESP-IP-π. Thus the linear relaxation of the PESP is of little use.
Although not pushing the LP optimum value beyond zero, an IP formulation
which is equivalent to PESP-IP-πturns out to be much better suited for
practical computations ([LPW05]), e.g. using CPLEX. Instead of encoding
the time information in a vector πwhich we define over the events, Nachtigall
proposed to switch to time variables for the activities ([Nac98]). In the
context of electrical engineering, one would call these new variables xthe
12
(periodic) tension that is induced by some node potential π. It is convenient
to think of xas xa=πj−πi+T·ka. The resulting equivalent IP finally
reads
(PESP-IP-x-z)min f(x, z) = X
a∈A
˜wa·(xa−ℓa)
such that
xa≤uafor all a∈A(8)
xa≥ℓafor all a∈A(9)
ΓTx−T·z= 0 (10)
xa∈Zfor all a∈A(11)
zC∈Zfor all C∈B, (12)
where the |A| × (|A| − |V|+ 1)-matrix Γ is the arc-cycle incidence matrix
of some integral cycle basis Bof the directed graph D= (V , A), see [LP02,
LR07] for the relevant properties of integral cycle bases of graphs.
In fact one can take the most benefit out of PESP-IP-x-zby adding further
valid inequalities. Such have been proposed by Odijk ([Odi96]) and Nachti-
gall ([Nac98]), and we use them throughout any of our PESP optimization
runs.
3.2 Adding Delay-Resistance
Optimizing delay resistant timetables we simplify certain aspects of the un-
derlying model. We will present the model and point out our simplifying
assumptions. Some effects of the simplification can be quantified a priori,
some cannot. Nevertheless, we expect all simplifications to be tolerable in
the sense that the resulting plan performs well in practice. In order to verify
this claim, we test our plan in a non-simplified environment a posteriori.
Of course, the non-simplified testing can only take into account a limited
number of scenarios, whereas the simplified version is optimized with respect
to all scenarios. Optimizing or even assessing the accurate model over all
scenarios is far beyond the scope of computational possibilities.
3.2.1 Simplified Delay Management
The most important simplification concerns the delay management which
we assume to underly the performance of a timetable in a scenario, i.e.,
which determines the delay related part of the objective function. As delay
13
management policies and delay propagation are notoriously hard problems
in their own right, for the optimization of the periodic timetable some kind
of simplification at this point is unavoidable.
We assume a strict no-wait policy. This means for the assumed disposition
timetable every (non-periodic) constraint can be broken in order to ensure
that every departure event takes place as scheduled. Thus, under a strict no-
wait policy source delays can only affect those train rides on which they occur.
However, such a strict no-wait policy cannot be implemented in practice.
This is due to the following reasons:
•The headway activities in the PESP model infrastructure requirements,
e.g., that two trains using the same track must use it with a certain
time difference.
•A train‘s trip consists of several driving and waiting arcs. Among these
activities the order is of course mandatory.
•One physical train usually takes more than one trip. But it cannot
start the second trip before it has finished the first. This is modeled
by the turnaround activities in PESP, together with a linear objective
function, but also neglected in the strict no-wait policy.
Clearly, constraints expressing such conditions cannot be dropped in reality.
At some arcs an all-wait policy and therefore a propagation of source delays
is a matter of fact.
Hence, adopting the strict no-wait policy we underestimate the effects of
source delays, as we exclude delay propagation. This unrealistic assumption
yields that every departure event will in every scenario take place as sched-
uled. As a drawback, this implies that our optimization cannot respond to
the propagation of delay.
More precisely: the strict no-wait policy SN which we assume for optimiza-
tion is not practical. Compared to the practical no-wait policy PN , i.e., a
delay management that always decides to start as early as possible (though
not ahead of schedule), the expected delays (E[D(·)]) of the policies fulfill:
E[D(SN)] ≤E[D(PN )]. On the other hand, for an optimal delay man-
agement OM as used in the evaluation we have E[D(OM)] ≤E[D(PN)].
Whether the strict no-wait policy performs better because it unrealistically
neglects necessary delay propagation, or whether these effects are weaker
than what an optimal delay management can win against a no-wait policy is
not clear a priori.
14
3.2.2 Strict No-Wait Policy and Periodic Timetabling
At first glance the unrealistic assumption of a strict no-wait policy cancels
all effects of stochastic driving times. Looking closer, this approach within
periodic timetabling only neglects the technical aspects of the railway sys-
tem, whereas it accounts correctly for the passengers’ perspective. This will
become clear by the following considerations.
Scenario Expansion. For explanatory reasons we introduce a local sce-
nario expansion of the PESP graph that models correctly the strict no-wait
policy.
Assume the distribution of a train’s driving time, which is the random vari-
able giving the lower bound ℓaof the corresponding arc a, to be finitely dis-
cretized in h∈Nscenarios. To construct the expansion, substitute a driving
arc aby harcs areach starting at the same departure vertex but leading to
its own copy jrof the arrival vertex. For each train to which passengers will
transfer, those arrival vertices are connected to the single departure vertex of
the transfer train, see Figure 3. For each rthe set of arcs incident to jrare
an entire copy of those incident to jin the original graph. In fact rstands for
a scenario, and arcs incident to jrshall model what happens to the transfer
passengers arriving at jin scenario r. Each copy arof the driving arc gets a
different, fixed value for its duration, the driving time in that scenario. Each
transfer arc is weighted according to the probability that the driving time of
its start vertex’ unique incoming arc occurs. (The upper bounds on a driving
arc arare set equal to the lower bound, i.e., the actual driving time.)
Interpretation of the Expansion. In this way, a pair of departure events
of trains between which passengers transfer, is linked by a set of parallel paths
of length 2. Each of the paths represents a scenario. The first arc has fixed
length, namely the scenario’s driving time on that track. The second arcs’
length, i.e., the transfer times in the different scenarios, are set simultaneously
by the optimization process deciding on the relative values of the departure
events of the two trains.
The optimization will seek to keep these transfer times short. In a non-
periodic setting this would be trivial, as feasibility would imply that the
schedule is dictated by the longest driving time. In the periodic setting this
is not the case. A path representing a scenario with low probability but long
driving time might be quasi neglected in order to have a schedule that gives
short connections for the likely scenarios. This negligence does not make the
plan infeasible. The inequalities of transfer arcs of long but unlikely scenarios
are nevertheless fulfilled modulo the period time T. In practice this means,
15
drive
drive
drive
drive
drive
drive
transfer
transfer
transfer
transfer
transfer
transfer
station 1
station 2
station 2
station 2
station 2
station 2
station 2
station 2
arrival
arrival
arrival
arrival
arrival
arrival
departure departure
Figure 3: Expansion of a driving and waiting activity to six different scenarios.
that those passengers connect to the train of the next period. The waiting
time for this is expressed correctly in the periodic model.
In other words: In periodic timetabling a strict no-wait policy is realistic for
arcs expressing passengers’ connections to other trains. Here the connections
are not broken but only established with a later period, for which the waiting
time can be expressed correctly by a PESP graph with only a constant bigger
size than the deterministic problems’ PESP graph.
The technique we exemplified for the transfer arcs can also be applied to
other arcs that enter the objective function.
Stochastic Dependency. Nevertheless, the effects of uncertainty remain
local by virtue of the strict no-wait policy. Therefore it suffices to know the
boundary distributions for each arc’s driving time. In this model it does not
matter which joint distribution underlies the driving times of the trains.
Moreover, it is immaterial in this setting whether a source delay is periodic
or singular. In both cases the measure is the probability for a driving time to
occur weighted over all scenarios and—with uniform distribution—over all
periods. As there is no delay propagation a singular source delay that occurs
on average in 1 out of 3 realizations of a periodic trip, has the same effect,
16
as a periodic source delay that occurs in 1 out of 3 scenarios for all periods.
3.2.3 Objective Function
In the light of stochastic driving times two different objective functions appeal
to us. Prima facie, one can be interested in minimizing the sum of the
expected travel times of all passengers, where the travel time of a passenger
iis the span between the moment she gets on the first train of her journey
(ti
str) until her last train arrives at her destination (ti
arr).
E"X
i
ti
arr −ti
str#=X
r
X
a∈Adrive
watr
a+X
a∈Await
watr
a+X
a∈Atransfer
watr
a
This measure nicely decomposes into the expected driving and stopping time
of the trains weighted by their passenger load and the expected, weighted
time passengers have to wait for a transfer. The latter is the matter of
optimization. Invoking again the above discretization of the distributions,
and the described scenario expansion of the graph, the expected transfer
time of all passengers is counted correctly by summing the length of the
copies of the transfer arcs weighted by the probability of the corresponding
scenario. A more detailed description of this objective function, the graph
expansion and its non-discretized version can be found in [LS06].
Though natural at first sight, this objective function neglects an important
aspect of delay resistant timetabling and delay management. Delay is the
deviation from what was planned. A train that arrives notoriously five min-
utes behind schedule causes greater discomfort to the customers, than a train
that is scheduled to arrive five minutes later. In the first case, the company
breaks a promise, whereas in the latter case, the passenger already accepted
a less ambitious promise. Nominal travel time and expected delay, i.e., ex-
pected positive deviation from the schedule, must be weighed against each
other. In general a minute of expected delay weighs heavier than a minute
prolongation of nominal travel time. The objective described so far measures
the expected travel time of the passengers, with no respect to how much it
deviates from what passengers planned. The customers plans are generated
by the published timetable. To capture this aspect the objective function
must have some reference to the nominal schedule.
Before showing how this can be—and actually—is incorporated in our setting,
we address the delay resistant optimization of arrival times, which we did not
incorporate in this study, although it fits into our framework, too.
17
Arrival Events. In the graph expansion each vertex of an arrival event is
substituted by a set of arrival vertices, one for each scenario. The departure
events are not duplicated. This is because they play substantially different
roles in the interpretation. An arrival vertex corresponds to the arrival event
of a scenario. This is also true for the non-duplicated departure events, be-
cause in all scenarios every departure is on time. But the value of a departure
vertex also corresponds to the time published in the timetable. Which time
shall be published for an arrival event?
This matters in two respects: First, the published time is the time with
respect to which the delay in a certain scenario is measured.
Second, the relative time difference between the published arrival time of a
train and the published departure time of another train at the same station
decides which transfer time between the two trains is offered. For every
transfer a minimum transfer time is known. A passenger information system
that chooses a transfer will send the passenger to the earliest train reachable
after the minimum transfer time. Every transfer planned with at least this
minimum transfer time, is promised. This implies, that by fixing the arrival
time early enough for a quick transfer the railway company gives the service
guarantee to provide for this transfer, for which it will be liable—at least in
our objective function.
In practice planners sometimes use the arrival times to actively negate such
a service guarantee. A tight connection is rendered nominally impossible by
prolongating the nominal driving time in order to avoid liability in case the
short transfer fails.
In principal, our approach models also the arrival times as being to the
disposal of the optimizer, as it has also been done in [KDV05]. However, in
this study we refrain from using this optimization potential.
More precisely, in accordance with Leaflet 451–1 of UIC (Union Interna-
tionale de Chemins de Fer), we fix the nominal driving time of each train
to 107% of the technically minimal driving time, for performance reasons.
In the disposition timetable that we construct in the delay management, in
order to catch up their delays we allow trains to use 76.4% of these driv-
ing time supplements. For example, if under ideal conditions the technically
minimum driving time is 100 min, in the regular service schedule we plan a
driving time of 107 min. In contrast, in the disposition timetable a driving
time of 0.95 ·107 = 101.65 min can be planned to catch up at most 5 min
21 sec of delay, which equals 76.4% of the added supplement of 7 min.
Thus, driving times are fixed for the planning. Their fluctuation in the
scenarios must be compensated by planning buffered transfer times.
18
Incorporating Delay in the Objective Function. By fixing the nom-
inal driving time of each train, we have a reference to measure when a pas-
senger misses a guaranteed transfer. Assume, e.g., that 20% of the trains
corresponding to a certain driving arc a= (i, j) need more than 1.08 of
the minimal driving time. Assume further we schedule the departure event
hof a train, to which some passengers from awant to transfer, such that
πh−πi=ℓ(j,h)+ 1.08t(i,j), where ℓ(j,h)is the minimum transfer time and
t(i,j)denotes the minimum time of the driving activity corresponding to a.
Then 20% of the passengers will experience a delay of the period time T: As
the arrival event was published under the assumption that the train needs
1.07t(i,j)the passengers expect to get their transfer—but 20% will not get it.
The passengers, who miss the connection, plan to transfer to the train de-
parting at time πhkbut now have to wait for the train that departs at
time πhk+1 =πhk+T. Consequently, since trains shall never operate prior
to schedule, these passengers have a definite delay of T, compared to their
planned itinerary (or an integer multiple of T, in the case they even missed
other transfers). Observe that counting a delay of Tfor such a missed trans-
fer equals the sum of their extended transfer time plus the extended driving
time of the feeder train. Hence, we only check for delays at transfers. The
only error that we make this way is that we do not capture the delay that
passengers face on the last trains of their itineraries.1Therefore, scheduling
such that πh−πi=ℓ(j,h)+ 1.08t(i,j)yields 0.2Tminutes (20% of the passen-
gers have to transfer to the train of the next period) of expected delay for
the passengers who transfer from arrival jto departure h.
If we specify some delay-weighting factor s, such that one expected minute
of delay is as important as sminutes of nominal prolongation of travel time,
then we can incorporate the delay into the contribution of the transfer arc
b= (j, h) to the objective function. Finally, before entering the objective
function, this contribution is multiplied by a weight, wb. This is the same
weight that is also used in a purely nominal objective function, to deter-
mine the importance of an arc b. This weight typically and in our study
corresponds to the number of passengers using the transfer arc.
Convex and Piecewise-Linear Objective Functions. Let cbe the re-
sulting objective function and cbits restriction to the component of the solu-
tion vector corresponding to the transfer arc b. The function cb=(j,h)depends
on the distribution pafor scenarios r∈Rand their random variable ℓr
a, i.e.,
1In general, of course we would like to include the delays on the final trains of itineraries
as well. However, for this particular case study, unfortunately the data that would be
necessary to incorporate this effect was not available to us.
19
the driving time of the driving arc a= (i, j). (We denote the nominal driving
time by tato stress the difference.) The cost cbis independent of the other
driving times’ distributions.
cb(π) = wb[πh−ℓb−(πi+ta)] mod T
−TX
r
pa(r)[πh−ℓb−(πi+ta)] mod T−(ℓr
a−ta)
T
The clumsy expression rounded down serves as an indicator, whether under
timetable πin scenario rthe passengers who transfer along arc bget their
connection. If it becomes negative, they do not get it, and cbincreases by
wbpa(r)T. When checking this, keep in mind that we only consider small
disturbances (ℓr
a−ta), thus the rounded expression has absolute value less
than T. This cost function has a reference to the published timetable and
its promises for transfer. Despite its intimidating aspect, it can be included
into the PESP optimization under a mild assumption.
Such a function cbneed not be convex. However, the authors were told
by practitioners that real-world distributions give almost convex functions
in the sense that only a small error is incurred if one substitutes them by a
convex function. Given that cbis convex we perform a further approximation
by piecewise-linearizing the function. In this study we decided to split our
function into two intervals with negative slope and one interval with slope
equal to wb. The latter is the time interval when we expect all trains, that
instantiate the driving arc of the feeder train in any scenario, have reached
their destination.
Eventually, we have a piecewise-linear, convex objective function on each
transfer arc. Such functions can easily be integrated to the mixed integer
program with a small increase in size compared to the original, deterministic
PESP problem. In particular, this can be done without introducing new
integer variables. The technique is described in detail for a similar setting
in [LS06]. We introduce an artificial fractional variable yb. Additional linear
constraints ensure that given a certain transfer time xb, the value of the
variable ybwill be at least equal to that of the desired, convex, piecewise-
linear function at xb. As we minimize the value of yb, the convex, piecewise-
linear function is minimized, too.
For clarity in presenting the stochastic effects in the objective function we
present the contribution of the transfer arc bbefore the weighting with wb.
Figure 4 displays the two components of the contribution of a transfer arc bto
the objective without multiplication by wb. The x-axis gives the time planned
for the transfer. The figure is translated such that it starts at the minimum
20
T+ℓb
ℓb20 min 40 min
πk−πj
0.2T
T
cost
s= 1.5s= 1.5
s= 2s= 2
s= 5s= 5
Figure 4: The nominal and some delay-cost functions
transfer time ℓb. The nominal cost function—the transfer times according
to the published timetable—raises with slope equal to 1 through the whole
period. The three dotted lines of the decreasing functions correspond to
the three different delay-weighting factors swhich we consider, 1.5, 2 and
5. Each one gives the fraction of all passengers that will in expectation
miss their connection multiplied with s, if the planned transfer time is the
x-value and the y-axis ranges from 0 to 1. Thus if you interpret the y-axis
to range from 0 to T, as it is done for the graph of the nominal function,
the three graphs give the delay-cost incurred for the three delay-weighting-
factors s∈ {1.5,2,5}. This is because every missed connection means one
period, Tminutes, of delay for the transferring passenger. Fix a factor s
and a distribution, e.g., s= 1.5 and the distribution underlying the dotted
lines in Figure 4, then the complete cost function before multiplying with arc
weight wbfor an arc bis the sum of the nominal function and the function
depicted by the lowest dotted line.
After one period all cost functions repeat themselves. Note that we have
chosen the set of the delay-weighting factors ssuch that the non-continuous
21
jump of the summed cost function is negative for every of these factors,
except for s= 5.
For each of the three weighting factors we consider three different distribu-
tions shown in Figure 7. The three delay penalty functions in Figure 4 are
based on one of those, namely distribution C. We refrain from showing all
ten objective functions, corresponding to three distributions, three delay-
weighting factors s, plus the nominal function, in one complete unintelligible
diagram.
3.2.4 Strict No-wait, Practical No-wait, and Light Robustness
To summarize, we make the following simplifications for calculating delay
resistant timetables.
1. We assume a no-wait policy.
2. We even assume a strict no-wait policy.
3. We fix the scheduled driving times for our optimization.
4. We only count the delay of passengers that loose a connection, but not
the delay of the last train of a passenger’s trip.
5. We assume cbto be convex.
6. We approximate cbpiecewise linear, i.e., we assume discrete distribu-
tions.
We commented on some of these issues earlier. Note that the normal, feasible
no-wait policy in some railway networks is the only response that practition-
ers seem to have to the “repair game” [EGL05]:
The management of the region south-west (of Deutsche Bahn AG)
decided to apply a strict no-wait policy from March 24 on.
Die Regionalleitung (S¨udwest) hat beschlossen, dass wir bereits ab 24. M¨arz
die Wartezeitvorschrift auf ,Keine Wartezeit’ ab¨andern.
(Udo Wagner, Vorsitzender der Regionalleitung DB Regio S¨udwest,
in BahnZeit Mai 2004, employee newsletter of Deutsche Bahn AG)
The strict no-wait policy leads to the following situation. The effect of a
disturbance to the optimization problem is purely local. Yet, the solution
that hedges against these effects optimally exploits the network structure.
Therefore, our approach fits into the scheme of so-called Light Robustness.
Light Robustness [FM06] starts with calculating a conventional linear pro-
gram that describes the deterministic optimization problem in question. Its
22
optimal objective value is stored as a reference value c(x) = z. Then a lim-
ited disturbance in data is added to the model in a worst case approach: A
robust solution x′has to satisfy the linear program in all scenarios that may
occur due to the limited change of data. Moreover, for a minimization prob-
lem the new solution must not exceed the old objective value by more than
some α≥1, i.e., c(x′)≤αz. This double requirement may easily yield an
infeasible instance. Therefore, Light Robustness allows the new solution x′
to violate each of the robust counterparts of the original constraints. Denote
the vector of violations by λ(x′). The optimization computes an x′that min-
imizes a usually non-linear function f(λ(x′)). Light Robustness minimizes
the local violations.
Our solutions are lightly robust against the maximal driving time, which
may reasonably occur in any scenario. A transfer that is not provided for
the maximal driving time incurs a local punishment in our objective function,
namely in the delay penalty. The quality guarantee αis what will be called
in the result section the Price of Robustness.
We differ from standard Light Robustness in two respects. First, we incor-
porate the original objective into our new objective function. This means
we allow for a trade-off between the nominal quality guarantee α, and the
delay penalty, i.e., in terms of Light Robustness, the function f. Second, our
model allows a precise understanding of the function fin terms of a weight-
ing factor, distributions of driving times, and certain simpliying assumptions
on delay propagation and delay management. We apply this simplification
for being able to solve our model. The good news is that we can analyze our
simplification.
3.3 Creating an Instance of the Delay Management
Problem
Given a set V=Varr ∪Vdep of periodic events and a set A=Adrive ∪Astop ∪
Atransfer ∪Aturn ∪Ahead of periodic activities together with lower and upper
(periodic) bounds ℓa≤uafor all a∈A, the methods of Section 3.2 construct
timetables, which are the basis for solving the delay management problem.
In particular, the input consists of
•the period T(i) for each event i∈V,
•the time πfirst(i) of the first occurrence, and
•the time πlast(i) of the last occurrence for each periodic event i∈V.
23
Note that for each activity a= (i, j)∈Adrive ∪Astop ∪Aturn ∩Atransfer we
know that2T(i) = T(j), and that
ua−ℓa< T(i).(13)
Our goal is to expand the periodic network D= (V , A) into a non-periodic
network D= (V, A). As input for the delay management problem, we need
the scheduled time π(ik) for all ik∈V, and we need the lower bounds ℓafor
all non-periodic activities a∈A. Recall that in the case of delays, in the
disposition timetable we may plan every driving time by 5% faster than it was
fixed for the regular service timetable. Since in case of delays all activities
are performed at the same speed or faster than initially planned, and since
the original timetable πwas feasible with respect to the upper bounds ua,
upper bounds need not be considered in the delay management problem.
To obtain V, A,π(i) for all i∈V, and ℓafor all a∈Awe proceed as follows:
•for each periodic event i∈Vand for each kwith 1 ≤k≤1 +
jπlast(i)−πfirst(i)
T(i)kwe create a new non-periodic event ikwith time π(ik) =
πfirst(i) + kT(i)
•for each periodic activity a= (i, j)∈A
– if a= (i, j)∈Astop ∪Adrive ∪Atransfer ∪Aturn then do:
for each non-periodic event is∈V(i) look for a non-periodic event
jt∈V(j) satisfying π(jt)≥π(is) + ℓaand π(jt)≤π(is) + ua. If
such an event jtexists it is unique due to (13) and we create a
unique new non-periodic activity ast = (is, jt) and ℓast =ℓa.
– if a= (i, j)∈Ahead then do:
for each non-periodic event is∈V(i) and for each non-periodic
event it∈V(j) create two new non-periodic disjunctive activities
ast = (is, it) and ats = (it, is), define ℓast =ℓaand ℓats =T(j)−ua.
In a non-periodic event-activity network without headway constraints, a di-
rected edge a= (i, j)∈Afixes the order of the two events iand jby requir-
ing ˜πj≥˜πi+ℓa. Such a network is cycle-free. In contrast, the non-periodic
network D= (V, A) we generate by driving the algorithm above contains
directed cycles – for every headway edge a= (i, j)∈Ahead, there exists
another headway edge a−1= (j, i)∈Ahead. Analogously to a non-periodic
2In general, for a= (i, j)∈Atransfer one would have T(i)6=T(j), but the data that
we use in our study are such that also for Atransfer we have T(i) = T(j).
24
event-activity network without headway constraints, we can interpret these
headway edges as follows: For each pair (a= (i, j), a−1= (j, i)) of headway
edges, either ˜πi≥˜πj+ℓa−1or ˜πj≥˜πi+ℓahas to be satisfied – it is a part
of solving (DM) to decide which of these two disjunctive constraints should
be satisfied and which should be the one to be dropped. By solving (DM),
we decide for each such pair (a, a−1) if event iis scheduled before event j
respecting the lower bound ℓa(we keep aand drop a−1), or the other way
round. When doing so, we have to keep exactly one headway edge from each
such pair in such a way that the resulting network does not contain any
directed cycle (see [Sch06a]).
3.4 Solving the Delay Management Problem
Using the notation of event-activity networks D= (V, A), a timetable πis
given by assigning a time πito each event i∈V. In the context of delay
management, we are, however, interested in the disposition timetable, which
will be called ˜πi,i∈V. We further use the numbers ℓaas the technical
minimal necessary times for performing activity a∈A, and waas the number
of passengers planning to use the connection a∈Atransfer. We also take T
as the common period of all events.
Each of our delay scenarios is defined by a set of source delays, i.e., a set
of events Vdel ⊆Varr such that di>0 for all i∈Vdel and a set of activities
Adel ⊆Asuch that da>0. (For non-delayed events and activities we set
di= 0, and da= 0, respectively.) Note that there is a basic difference
between source-delayed events and source-delayed activities:
•A source delayed activity a= (i, j) can arise due to an obstacle on the
tracks or due to a detour within a station. It has to be added to a
possible other delay of event i. I.e., if a train starts delayed at event
iand there is an obstacle on the track, the additional delay has to be
added to its departure delay.
•A source-delayed event i, however, need not be added to a possible
other delay of event i. Source delayed events can be caused e.g. by a
delayed train driver starting his shift in the station or by a track that
is occupied due to repair work until a fixed point of time.
Integer programming formulation. To model the delay management
problem, we need the following three types of variables: First, for all events
i∈Vwe need
˜πi= actual time of event i.
25
Note that the delay of event iis hence given by ˜πi−πiand that we have
to require that ˜πi≥πiholds, since no train is allowed to start earlier than
planned. For all transfer activities a∈Atransfer we introduce
za=0 if transfer activity ais maintained
1 otherwise,
and for a= (i, j)∈Ahead we use
ga=0 if istarts before j
1 otherwise.
The following is an integer programming formulation of the delay manage-
ment problem (see [Sch06c, Sch06a]).
(DM) min f(˜π, z) = X
i∈V
wi(˜πi−πi) + X
a∈Atransfer
waTza
such that
˜πi≥πi+difor all i∈Vdel (14)
˜πj−˜πi≥ℓa+dafor all a= (i, j)∈Astop ∪Adrive ∪Aturn
(15)
Mza+ ˜πj−˜πi≥ℓafor all a= (i, j)∈Atransfer (16)
Mga+ ˜πj−˜πi≥ℓafor all a= (i, j)∈Ahead (17)
ga+ga−1= 1 for all a, a−1∈Ahead (18)
˜πi∈Nfor all i∈V
za∈ {0,1}for all a∈Atransfer
Note that wiare positive weights that represent the importance of event i.
The first constraint (14) makes sure that no train departs earlier as scheduled,
while (15) ensures that the delay is carried over correctly from one event
to the next. Recall that in (15) the lower bound is by 5% smaller than
the driving times that were used for the computation of the regular service
timetable. Constraints (14) and (15) additionally ensure that the source
delays diand da, respectively, are taken into account. In particular, if event
itakes place at some time point ˜πi, event jmust be later than ˜πi+ℓaif
a= (i, j) is the activity linking iand j. If za= 0, constraint (16) ensures
that the delay is carried over for each maintained connection. For za= 1,
however, constraint (16) becomes redundant whenever Mis large enough.
In particular, we need that M≥maxi∈V˜πi−πiis large enough. Since the
computation time allowed it, we used M=H+ 2Tand are hence sure
26
station 1
arrival
arrival arrival
arrival
station 1
station 1station 1 departure departure
departure
departure
station 2
station 2
station 2
station 2
wait drive
drive
wait wait
wait
drive
drive
transfer
4
066
Figure 5: Graphical interpretation of the capacity constraints
that Mis large enough. Constraints (14) to (16) describe the pure delay
management problem. However, to get realistic results we need to consider
also restrictions of the type Ahead as done in (17) and (18). These constraints
can be equivalently reformulated to
(17) and (18) ⇐⇒ ˜πj−˜πi≥ℓaor ˜πi−˜πj≥ℓ(a−1).
Hence, (17) and (18) require for all (i, j)∈Ahead that either ˜πi≥ℓ(a−1) + ˜πj
or ˜πj≥ℓa+ ˜πi. Figure 5 shows the graphical interpretation of the headway
constraints: While the solid activities are already fixed, the goal is to choose
exactly one of each pair of dashed edges. If one edge of each pair is chosen,
the order of the events is fixed, and at the same time the security distances,
indicated as bounds ℓaof edge a= (i, j), are respected. Recall that the
event-activity network without dotted edges is cycle-free. When fixing the
order of the events, one has to choose one edge from each pair of dotted edges
in such a way that the resulting network also does not contain any directed
cycle.
Objective function. The above formulation minimizes a combination of
(weighted) dropped connections and (weighted) train delays. The weight of a
(dropped) connection a∈Ais set to the time period Tsince this is the delay
a passenger will suffer, when missing a train. Although the formulation does
not minimize the sum of additional delays over all passengers in general, it
does so in a large class of delay management problems, namely, whenever the
never-meet property is satisfied (for a definition of the never-meet property
and its satisfaction in practice, see [Sch06c]). To this end, wihas to be chosen
as the number of passengers with final destination i.
In our case, the objective used in (DM) is an approximation of the sum of all
passengers’ delays. It can also be seen as a weighted scalarization of the two
objectives minimize (weighted) number of dropped connections and minimize
number of (weighted) train delays in minutes which are defined in bicriteria
delay management problems [GSar, HdV01].
27
In our case study we minimize the objective function mentioned above, but in
the evaluation we also calculate the following characteristics of the disposition
plan found:
•objective value
•number and percentage of missed connections
•number and percentage of passengers who missed a connection
•number and percentage of delayed arrival events
•sum of all delays over all arrival events.
Solution approach. If the zavariables and the gavariables have been
fixed, the remaining problem can be easily solved by the forward phase of
the critical path method (CPM). To this end, we assume that the events are
ordered according to the scheduled times πi, i.e. in their “natural order”.
Then we set
Arelevant := Astop ∪Adrive ∪Aturn
∪{a∈Atransfer :za= 0} ∪ {a∈Ahead :ga= 0}
and obtain the optimal disposition timetable ˜πthrough
˜π1:= π1+d1
˜πi:= max{πi+di,max
a=(j,i)∈A˜πj+ℓa}, i = 2,...,|V|.
Usually, the wait-depart decisions zaand the order in which the trains use
common capacities (represented by the variables ga) are not known. In this
case several heuristics may be used, see [SS07]. In our case study we were
fortunately able to solve the problem optimally by Xpress-Mosel 1.6.3 (2006b)
within less than one hour of computation time. We are aware of the fact
that these good results are achieved since we limited our calculations to an
observation period of some hours and since within the Harz region, there
are only few conflicts with the never-meet property in most of our delay
scenarios.
4 The Data of the Case Study
We apply our approach to the Harz Region of the Lower Saxony (Nieder-
sachsen) part of the German Railway network, see Figure 6. The northern
28
Hannover
Hbf
Lehrte Gifhorn
Wolfsburg
Helm-
stedt
Braunschweig
Hbf
Wolfen-
büttel
BadHarzburg
Goslar
Seesen
SZ-Ringelheim
SZ-Lebenstedt
Hildesheim
Bodenburg
Elze
Kreiensen
Northeim
Göttingen
Herzberg
BadLauterberg station
linestopsatstation
fixedlong-distanceline
regionalline
BadSachsa
omittedline
s
Figure 6: The railway lines in the Harz Region of the Lower Saxony part of the
German Railway network
and western boundary of this region are the tracks Wolfsburg–Hannover and
Hannover–G¨ottingen, respectively.
In our case study, we consider the entire set of passenger railway lines that
are operated within this region. Only this way we may expect to obtain
significant results. Otherwise delay propagation which is caused by limited
capacity of the infrastructure would not be an issue. The only relaxation that
we take in this first study on optimization and recovery of railway timetables
is that we assume all the lines to be operated with a period time of T=
120 minutes. In reality, there are a few lines which are operated hourly.
In the step of computing the periodic regular service timetable, we assume
the timetables of the long-distance lines to be fixed to a scenario that was
kindly provided to us by Deutsche Bahn AG. This way, we are sure that the
optimized timetables that we are about to compute for the regional service
lines can be embedded into a realistic scenario for Germany as a whole.
In total, our scenario features 30 pairs of directed railway lines, including
9 pairs of long-distance lines with fixed timetables. For most of the tracks,
29
the minimum headway that any timetable which we compute will respect is
3 minutes. Furthermore, for more than 30 single track segments we will
ensure safe operations. Interestingly, the long-distance ICE line Berlin–
Wolfsburg–Braunschweig–Hildesheim–G¨ottingen–Frankfurt–Basel/M¨unchen has
three of these single tracks along its route, and there are further regional ser-
vice lines that operate on the very same single tracks. Among the timetables
that respect all these infrastructural requirements, we mainly head for short
transfer times—both nominal and during operations—along the 182 most
important transfers within the region. More precisely, we have assigned
weights ˜wto the corresponding transfer activities. The weights represent
the number of passengers who use the transfers, and they were estimated by
Deutsche Bahn AG using their so-called traffic model.
In addition, note that when computing the periodic regular service timetable
we keep the driving times of the trains unchanged, for performance reasons.
Yet, we allow for 26 stop activities their minimum dwell time to be extended
by several minutes. This enables better synchronization at single tracks, and
at transfers. Moreover, we have to pursue two further important goals. First,
where two lines with T= 120 minutes share the same tracks over a long
distance, we require a balanced hourly service, e.g. between Braunschweig
and Seesen. Second, in order to compute realistic timetables, we must not
neglect operating costs, i.e. the number of trains that are required to operate
the timetable, see [LM04, Lie06] for any details.
In Table 1 we report the size of the resulting network D= (V , A). Notice
that for the purpose of periodic timetabling, many redundancies can be re-
moved from this network. Hence, we also provide the corresponding values
for the network that we obtain after having contracted many of the arcs, see
[Lie06] for details. Unfortunately, in the contracted network the information
becomes highly aggregated, and thus is no more suited to derive the non-
periodic network for the delay management problem. This is why we roll
out the non-periodic network D= (V, A) as three copies of the uncontracted
periodic network D= (V , A) (as described in Section 3.3) and give its size
in Table 1, too.
In the integer programming formulation (DM) of the delay management prob-
lem, we need to assign weights to all events i∈Vand to all activities a∈A.
As the only information we have on the number of passengers are the weights
˜waof the transfer activities a∈Atransfer derived from the periodic timetable,
we set wi= 1 for all i∈V. In order not to overestimate the importance of
missed connections (compared to delayed arrival events), we set wa=˜wa
wfor
all a∈Atransfer where wdenotes the arithmetic mean of the weights ˜waof
all transfer activities.
30
Table 1: The sizes of the networks D= (V , A), its contracted version, and
the non-periodic network D= (V, A)
quantity Dcontracted version of D D
|V|or V4721 65 ≈15000
|A|or A5469 517 ≈26500
|Atrans|or Atrans 182 – ≈500
|Ahead|or Ahead 454 – ≈11000
For delay resistant timetabling we consider three distributions of source de-
lays, described in Table 2 and shown in Figure 7. In that table Pontime denotes
the probability that a train needs for a certain driving arc at most 107% of
the corresponding minimal driving time. According to the UIC rule, 107%
can be understood as the uniform supplement used so far. The time tmax is
the maximum time in minutes a train exceeds this 107% driving time. Fi-
nally, zis some smaller time such that with probability P(≤z) the trains
take at most zminutes longer than 107% of their minimal driving time. The
table gives the values for type A, B, and C distributions. Together with
the delay-weighting factors sthis specifies the settings under which the ten
timetables are optimized. Thereby DEF is the ID of the nominal or default
plan that takes no delay into account.
In the figure the dashed line represents the type C distributions, the straight
line type A. Type C is stochastically greater than A, and B is incomparable
to both. It represents settings with many but small source delays. In type
A and C we assume 80% of the trains to run on time, in the sense that their
trip takes at most 107% of the minimal technical driving time. For type B
this probability is lowered to 75%.
40 min
0.5
type A
type B
type C
P
xbin min.
0.2
20
15
5
Figure 7: The three Boundary Distributions for the Probability to Miss a Con-
nection Scheduled with tension xbon transfer arc b.
31
Table 2: Distributions and Delay Weighting Factors
Id Pontime z P(≤z)tmax s
DEF 1 – – – 0
A1.5 0.8 5 0.9 20 1.5
B1.5 0.75 5 0.9 15 1.5
C1.5 0.8 15 0.95 40 1.5
A2 0.8 5 0.9 20 2
B2 0.75 5 0.9 15 2
C2 0.8 15 0.95 40 2
A5 0.8 5 0.9 20 5
B5 0.75 5 0.9 15 5
C5 0.8 15 0.95 40 5
To be able to solve the delay management problem optimally, we need to
limit our calculations to an observation period Hof some hours. Thus we
consider all trains which arrive at or depart from one of five central stations
within an interval of six hours. These five stations are chosen in such a way
that all lines contain at least one of these stations. We then reduce the
non-periodic network (V, A) as follows:
•generate a list Tof all trains τarriving at or departing from one of
the five central stations within the observation period H
•for each non-periodic event i∈V
–if ibelongs to a train τ∈T: keep i
–otherwise: delete ifrom V,V=V\ {i}
•for each non-periodic activity a= (i, j)∈A
–if i∈Vand j∈V: keep a
–otherwise: delete afrom A,A=A\ {a}.
The delays we use to compare different timetables are generated as follows:
For each rolled-out period, we choose 24 different driving or stopping activ-
ities at random. Among these 12 are delayed by a randomly chosen time
between 60 and 300 seconds, while the other 12 activities are delayed by
between 360 and 1200 seconds (also randomly chosen). Hence we have a
total of 72 source delayed activities during our 6-hours time slot, the sum
of all delays lies between 15120 and 54000 seconds. This choice corresponds
to an average scenario for a distribution fulfilling the boundary distributions
specified as distribution type A.
32
5 Results
We constructed delay resistant periodic timetables for three different distri-
butions and three different delay-weighting factors sfor the Harz subnetwork
of Deutsche Bahn AG. We also computed a nominally optimal timetable.
Then for each of these ten plans we computed optimal disposition timetables
under 68 random scenarios. The methods we applied in both steps proved
to be capable of solving both the delay resistant timetabling and the delay
management problem on the real-world level.
Analyzing the results the following questions are of central interest. Is it
possible to reduce the expected delay by means of delay resistant timetabling
in a realistic setting? How much nominal travel time of the passengers has to
be sacrificed to obtain a certain level of robustness? Is it possible to reduce
the passengers’ delay by means of delay management? Is the theoretical
robustness of the delay resistant timetables echoed by their actual behavior
under realistic delay management?
To answer these questions we simulate the nominally optimal and the delay
resistant timetables under an optimal delay management as well as under a
feasible no-wait policy.
It turned out that delay resistant timetabling reduces the expected delay
substantially both under no-wait and under optimal delay management. This
success is achieved at the expense of a clearly small increase in the nominal
travel times. Second, for both nominal and delay resistant timetabling the
improvement when applying optimal delay management instead of the no-
wait policy is significant. Finally, some more detailed observations were
achieved in the theoretical evaluation used in the optimization, which are
justified by the practical evaluation based on the simulation.
The optimization of the timetables has been obtained by solving PESP-IP-
x-z, with refined objective function, by CPLEX 10.1 on a 3GHz PC.
Each timetable has been optimized with respect to a different objective func-
tion, resulting from their underlying distribution and the weighting factor.
For a better comparison we also calculated the value that each timetable at-
tains under the nine objective functions of the other plans. For a timetable
ID let CID denote the function with respect to which ID has been optimized.
Thus CDEF is the nominal cost, and any other cost function CID can be writ-
ten as CID =CDEF +C′
ID, where C′
ID is the expected delay cost incurred by
the distribution and the weighting factor of ID—in other words, the delay
penalty.
For each plan ID we calculate the Price of Robustness
PoR(ID) := CDEF(ID)/CDEF(DEF) ,
33
which is the nominal cost of the plan ID in relation to the minimal nominal
cost of any plan. This serves as a measure for how much nominal passenger
traveling time is spent to achieve delay resistance in the sense of ID’s delay
penalty.
Like the PoR is a measure of how much is sacrificed, the Ratio of Delay
measures the gain. It is defined by
RoD(ID) = C′
ID(DEF)/C′
ID(ID) .
It measures for a given setting how much delay penalty the nominal plan
incurs in comparison to a plan optimized to that setting of distribution and
weighting factor.
Table 3: Results and performance of the optimization for our regular timeta-
bles. ID PoR RoD Delay Penalty CPU Time miss miss
*100 *100 C′
15Cin sec. opt no-w pol
DEF 100 100 100 4802 100 100 (218)
15A 101 132 85 4843 84 80 (174)
15B 102 162 80 9094 79 79 (171)
15C 101 121 83 7960 81 81 (176)
2A 102 137 82 9011 80 80 (174)
2B 103 195 73 6908 67 71 (156)
2C 102 124 81 18327 79 79 (171)
5A 107 220 60 44275 53 53 (115)
5B 106 253 62 83356 55 55 (121)
5C 111 205 49 53743 49 48 (105)
In Table 3 we compiled these results. To compare the different delay resistant
plans, we also show which delay penalties each plan incurs in the objective
function of 15C, i.e., we give C′
15C(ID) which is by constant factor equal to
C′
2C(ID) and C′
5C(ID). The choice of these functions will be become clear
by the closer analysis. As a first hint, observe that the plans 15C and 5C
achieve maximum and minimum PoR among all delay resistant timetables.
Furthermore, the table gives the CPU time in seconds until optimality was
established. The computation time for the nominal timetable can be re-
duced to less than half an hour by a further acceleration technique, that is
not ready yet to use for the delay resistant models. The last two columns
give the number of passengers who missed their connection in the simulation,
i.e., of those who experience a delay of two hours. These numbers are aver-
aged over the 68 random scenarios. The last column gives the value for the
34
feasible no-wait policy, whereas the previous column refers to the optimal de-
lay management. Except for the CPU time all columns are normalized such
that the nominally optimal plan gets a value equal to 100. For the average of
the simulated, feasible no-wait policy we also give in brackets the number of
missed connections in normalize with respect to the corresponding number
in the default plan with optimal delay management.
Qualitatively, the results of the theoretical evaluation by different objective
functions are echoed by both the simulation under the no-wait and under
an optimal delay management policy. Again a certain margin of imprecision
has to be granted because a simulation takes into account a relatively small
number of scenarios. Recall that the samples correspond to distribution A.
The data supports that our carefully simplified objective function is a good
direction for optimization to balance delay resistance and nominal travel
time in timetabling, particularly so for the short source delays, that haunt
everyday railway business.
The normalization in Table 3 disguises the improvements of the delay man-
agement. The ratio between absolute values for missed connections of the
feasible no-wait policy and the optimal delay management is 2.18. This
means, that even the most delay resistant plan 5C under no-wait delay man-
agement has 4.5% more missed connections than the nominally optimal plan
under optimal delay management. In other words, the most resistant plan
(5C) together with the feasible no-wait policy work almost as well as optimal
delay management with the nominal plan.
We have chosen the normalization nevertheless, because it reveals that the
qualitative assessment of a timetable by the simplified objective function
comply with the results of both delay management approaches. Interestingly,
the optimal delay management even in these relative terms is always better
than the no-wait policy. Optimal delay management makes better use of the
possibilities that delay resistant timetables offer.
Looking closer, it is most interesting how changes in the distribution or
changes in the delay-weighting factor sinfluence the features of the resulting
timetables.
The PoR seems a lot more susceptible to the weighting factor than to the un-
derlying distribution. Moreover, distribution C, which is the one with many
long source delays, for small weighting factors (1.5 and 2) has a smaller or
non-greater PoR than the other two distributions. This is surprising in two
respects. First, the distribution A is stochastically smaller than C. Therefore
contrary to the results one would expect the optimizer to invest less in delay
resistance for a timetable tailor made for A than for C. Second, the unex-
pected behavior vanishes, when the weighting factor is lifted to 5. Then the
35
optimizer pays respect to the higher total expected source delay and invests
a higher price for the robustness of plan 5C than for 5A or 5B.
This behavior gives rise to the following interpretation. To protect the sched-
ule against long source delays requires to intervene so strongly that it only
pays if delay is weighted very high. This interpretation is supported by an-
other detail. The plan 15C does not even have the lowest delay penalty in his
own setting. But it has the lowest nominal value among all delay resistant
plans. Therefore, in sum it is the best plan for his setting. In contrast con-
sider the plan 5C, which is also the best plan for his setting, but for different
reasons. It has the worst nominal value of all but the lowest delay penalty in
its own (and, in fact, in every other) setting. To conclude, for a small weight-
ing factor hedging against long source delays would be inappropriate. Only
for high weighting factors it pays to give up nominal optimality to curtail
the effect of long source delays.
Also the RoD increases with increasing weighting factors—at least for distri-
bution A and B. Under distribution C the RoD reacts only at high weighting
factors. The main difference between the behavior of the PoR and that of
the RoD lies in the susceptibility to distributions. The RoD of the B plans is
clearly higher than that of A plan with the same weighting factor. For dis-
tribution C always the lowest RoD values are achieved. This again backs the
interpretation that by means of timetabling one can do more against short
source delays than against long source delays.
850000 875000 900000 925000 950000 975000
1/RoD
C'
Opt DM
Figure 8: Simplified Objective Matches Optimal Delay Management
In fact, the delay penalty used in our simplified objective function provides
a surprisingly adequate estimate of the actual delay penalty, namely the
number of missed connections under optimal delay management. Note that
Figure 8 is obtained from the original values of the simplified delay penalty
36
with respect to distribution C only by multiplication with a constant. The
ten plans are ordered according to their nominal objective value. This re-
sult encouragingly justifies to use our simplified objective function for delay
resistant timetabling.
For the quantitative results one should look at the simulation average. There
it shows that at the price of a relatively small increase in the nominal objec-
tive value of the timetables (PoR), a substantial reduction of the probability
to miss a train can be achieved. For instance, take timetable 2B. Compared
to the optimum nominal timetable, it increases the nominal objective by only
3%. But this halves the number of passengers who miss a connection! Never-
theless, one might also want to take into account the different absolute levels
of these two conflicting objective functions. Then, it turns out that the gain
that we obtain with respect to the delay penalty outweighs the increase in
nominal waiting time, as long as the delay-weighting factor is chosen to at
least ≈1.5.
Note that the samples, the “reality” of our study if you like, were drawn
according to distribution A. Nevertheless, it may well be that a different
distribution—distribution B in this case—yields the more desirable approxi-
mation.
Recommended workflow. Here, it is time to recall what we were initially
aiming at: Computing a periodic timetable that allows for concise actions
in delay management during its operation. Hence, the key is to roughly
approximate the involved delay management objective function. In other
words, we are interested in identifying an add-on to the standard periodic
timetabling objective function with two major properties: (i) being easy to
evaluate; (ii) provide a cost value for each nominal timetable that is much
similar to the actual costs of the timetable under small disturbances.
We recommend the following workflow. First, compute several distinct timeta-
bles, which should put different emphasize on nominal waiting time and the
risk of missed connections, or on cost efficiency. Second, evaluate our simple
delay penalty functions on any of these timetables, for different distributions
for the delays. Third, simulate their behavior by confronting any of these
timetables with a sample set of scenarios, and compute optimum disposi-
tion timetables. Fourth, calibrate the simplified objective function for each
distribution via the delay-weighting factor sto best fit the cost observed in
the simulation. Fifth, select the distribution and delay-weighting factor that
fits best. Now, compute with this delay penalty function the delay resistant
periodic timetable. For the last step, the delay-weighting factor smay be
scaled according to the level of risk aversion the management targets at.
37
6 Conclusion
We successfully added delay resistancy to the computation of periodic rail-
way timetables. The computational study that we effected on a part of the
German railway network of Deutsche Bahn AG suggests that a significant
decrease of passenger delays could be obtained at a relatively small price
of robustness. This does not only apply to the nominal increase of passen-
ger waiting times, but also to the computation times, because in our slight
extension of the “Light Robustness” approach we did not add any integer
variables to the well-established integer programs for periodic timetabling.
Nevertheless, further research should aim at bringing the computation times
of the refined model even closer to the standard model. In particular, solving
the delay management problem serves as an accurate measure for estimating
the delay resistancy of a timetable.
Last but not least, let us mention that we are still seeking for a detailed
feedback from practitioners, but due to the huge variety of data, this remains
a challenge in its own right.
7 Acknowledgment
We thank Jens Dupont, Robert Firla, and Frank Geraets, Deutsche Bahn AG,
for inspiring parts of this research and for providing us with the data neces-
sary to perform our case study.
References
[BGJ+05] N. Bissantz, S. G¨uttler, J. Jacobs, S. Kurby, T. Schaer,
A. Sch¨obel, and S. Scholl. DisKon - Disposition und Kon-
fliktl¨osungs-management f¨ur die beste Bahn. Eisenbahntechnis-
che Rundschau (ETR), 45(12):809–821, 2005. (in German).
[CS07] C. Conte and A. Sch¨obel. Identifying dependencies among de-
lays. Technical report, Institut f¨ur Numerische und Angewandte
Mathematik, Universit¨at G¨ottingen, 2007. To appear at IAROR
2007.
[DV95] Joachim R. Daduna and Stefan Voß. Practical experiences in
schedule synchronization. In Joachim R. Daduna, Isabel Branco,
and Jos´e M. Pinto Paixao, editors, CASPT, volume 430 of Lec-
ture Notes in Economics and Mathematical Systems, pages 39–55.
Springer, 1995.
38
[EFK04] Ophelia Engelhardt-Funke and Michael Kolonko. Analysing sta-
bility and investments in railway networks using advanced evo-
lutionary algorithms. International Transactions in Operational
Research, 11:381–394, 2004.
[EGL05] Jan Ehrhoff, Sven Grothklags, and Ulf Lorenz. Parallelism for
perturbation management and robust plans. In Jos´e C. Cunha
and Pedro D. Medeiros, editors, Euro-Par, volume 3648 of Lecture
Notes in Computer Science, pages 1265–1274. Springer, 2005.
[FM06] M. Fischetti and M. Monaci. Robust optimization through
branch-and-price. In Proceedings of AIRO, 2006.
[GGJ+04] M. Gatto, B. Glaus, R. Jacob, L. Peeters, and P. Widmayer.
Railway delay management: Exploring its algorithmic complex-
ity. In Algorithm Theory - Proceedings SWAT 2004, volume 3111
of LNCS, pages 199–211. Springer, 2004.
[GHL06] L. Giovanni, G. Heilporn, and M. Labb´e. Optimization mod-
els for the delay management problem in public transportation.
European Journal of Operational Research, 2006. to appear.
[GJPS05] M. Gatto, R. Jacob, L. Peeters, and A. Sch¨obel. The computa-
tional complexity of delay management. In D. Kratsch, editor,
Graph-Theoretic Concepts in Computer Science: 31st Interna-
tional Workshop (WG 2005), volume 3787 of Lecture Notes in
Computer Science, 2005.
[GJPW07] M. Gatto, R. Jacob, L. Peeters, and P. Widmayer. On-line de-
lay management on a single train line. In Algorithmic Methods
for Railway Optimization, Lecture Notes in Computer Science.
Springer, 2007. presented at ATMOS 2004, to appear.
[GSar] A. Ginkel and A. Sch¨obel. To wait or not to wait? the bicriteria
delay management problem in public transportation. Transporta-
tion Science, to appear.
[HdV01] B. Heidergott and R. de Vries. Towards a control theory for trans-
portation networks. Discrete Event Dynamic Systems, 11:371–
398, 2001.
[KDV05] L.G. Kroon, R. Dekker, and M. Vromans. Cyclic
railway timetabling: A stochastic optimization ap-
proach. In Algorithmic Methods for Railway Opti-
39
mization, 2005. To appear. Preprint available at
http://www.few.eur.nl/few/research/ecopt/publications.
[KP03] Leo G. Kroon and Leon W.P. Peeters. A variable trip time model
for cyclic railway timetabling. Transportation Science, 37:198–
212, 2003.
[KS88] Wolf-Dieter Klemt and Wolfgang Stemme. Schedule synchro-
nization for public transit networks. In Joachim R. Daduna and
Anthony Wren, editors, Computer-Aided Transit Scheduling—
Proceedings of the Fourth International Workshop on Computer-
Aided Scheduling of Public Transport, volume 308 of Lecture
Notes in Economics and Mathematical Systems, pages 327–335.
Springer, 1988.
[Lie05a] Christian Liebchen. Der Berliner U-Bahn Fahrplan 2005 – Re-
alisierung eines mathematisch optimierten Angebotskonzeptes.
In HEUREKA ’05: Optimierung in Transport und Verkehr,
Tagungsbericht, number 002/81. FGSV Verlag, 2005. In German.
[Lie05b] Christian Liebchen. Fahrplanoptimierung im Personenverkehr—
Muss es immer ITF sein? Eisenbahntechnische Rundschau,
54(11):689–702, 2005. In German.
[Lie06] C. Liebchen. Periodic Timetable Optimization in Public Trans-
port. dissertation.de – Verlag im Internet, Berlin, 2006.
[Lin00] Thomas Lindner. Train Schedule Optimization in Public Rail
Transport. Ph.D. thesis, Technische Universit¨at Braunschweig,
2000.
[LM04] Christian Liebchen and Rolf H. M¨ohring. The modeling power
of the periodic event scheduling problem: Railway timetables –
and beyond. Preprint 020/2004, TU Berlin, Mathematical In-
stitute, 2004. To appear in Springer LNCS Volume Algorithmic
Methods for Railway Optimization. An extended abstract has
been accepted for publication in Proceedings of the Ninth In-
ternational Workshop on Computer-Aided Scheduling of Public
Transport (CASPT).
[LP02] Christian Liebchen and Leon W.P. Peeters. On cyclic timetabling
and cycles in graphs. Technical Report 761-2002, TU Berlin,
Mathematical Institute, 2002.
40
[LPW05] Christian Liebchen, Mark Proksch, and Frank H. Wagner. Perfor-
mance of algorithms for periodic timetable optimization. In Mark
Hickman, editor, Computer-Aided Transit Scheduling— Proceed-
ings of the Ninth International Workshop on Computer-Aided
Scheduling of Public Transport (CASPT), Lecture Notes in Eco-
nomics and Mathematical Systems. Springer, 2005. To appear.
[LR07] Christian Liebchen and Romeo Rizzi. Classes of cycle bases.
Discrete Applied Mathematics, 155(3):337–355, 2007.
[LS06] C. Liebchen and S. Stiller. Delay resistant timetabling. Technical
Report 2006/24, Technische Universit¨at Berlin, 2006. presented
at CASPT’06.
[Nac98] Karl Nachtigall. Periodic Network Optimization and Fixed In-
terval Timetables. Habilitation thesis, Universit¨at Hildesheim,
1998.
[Odi96] Michiel A. Odijk. A constraint generation algorithm for the con-
struction of periodic railway timetables. Transportation Research
B, 30(6):455–464, 1996.
[RdVM98] B. De Schutter R. de Vries and B. De Moor. On max-algebraic
models for transportation networks. In Proceedings of the Inter-
national Workshop on Discrete Event Systems, pages 457–462,
Cagliari, Italy, 1998.
[Roc84] R. Tyrrell Rockafellar. Network flows and monotropic optimiza-
tion. John Wiley & Sons, Inc., 1984.
[SBK01] L. Suhl, C. Biederbick, and N. Kliewer. Design of customer-
oriented dispatching support for railways. In S. Voß and
J. Daduna, editors, Computer-Aided Transit Scheduling, volume
505 of Lecture Notes in Economics and Mathematical systems,
pages 365–386. Springer, 2001.
[Sch01] A. Sch¨obel. A model for the delay management problem based
on mixed-integer programming. Electronic Notes in Theoretical
Computer Science, 50(1), 2001.
[Sch06a] A. Sch¨obel. Capacity constraints in delay management. In
CASPT 06, June 2006.
41
[Sch06b] A. Sch¨obel. Customer-oriented optimization in public transporta-
tion, volume 3 of Optimization and Its Applications. Springer,
New York, 2006.
[Sch06c] A. Sch¨obel. Integer programming approaches for solving the delay
management problem. Lecture Notes in Computer Science, 2006.
to appear.
[SM97] L. Suhl and T. Mellouli. Supporting planning and operation time
control in transportation systems. In Operations Research Pro-
ceedings 1996, pages 374–379. Springer, 1997.
[SM99] L. Suhl and T. Mellouli. Requirements for, and design of, an op-
erations control system for railways. In Computer-Aided Transit
Scheduling. Springer, 1999.
[SMBG01] L. Suhl, T. Mellouli, C. Biederbick, and J. Goecke. Managing
and preventing delays in railway traffic by simulation and opti-
mization. In M. Pursula and Niittym¨aki, editors, Mathematical
methods on Optimization in Transportation Systems, pages 3–16.
Kluwer, 2001.
[SS94] Alexander Schrijver and Adri G. Steenbeek. Dienstregelin-
gontwikkeling voor Railned. Rapport CADANS 1.0, Centrum
voor Wiskunde en Informatica, December 1994. In Dutch.
[SS07] M. Schachtebeck and A. Sch¨obel. Algorithms for the delay man-
agement problem. Technical report, Georg-August Universit¨at
G¨ottingen, 2007. working paper.
[SU89] Paolo Serafini and Walter Ukovich. A mathematical model for
periodic scheduling problems. SIAM Journal on Discrete Math-
ematics, 2(4):550–581, 1989.
[Wag04] Udo Wagner. P¨unktliche Abfahrt verhindert Domino-Effekt auf
dem Gleis. BahnZeit (employee newsletter of Deutsche Bahn
AG), 5:4, 2004. In German.
42
Reports from the group
“Combinatorial Optimization and Graph
Algorithms”
of the Department of Mathematics, TU Berlin
2007/22 Michael Elkin and Christian Liebchen and Romeo Rizzi: New Length
Bounds for Cycle Bases
2007/19 Nadine Baumann and Sebastian Stiller: The Price of Anarchy of a Net-
work Creation Game with Exponential Payoff
2007/17 Christian Liebchen and Michael Schachtebeck and Anita Sch¨obel and
Sebastian Stiller and Andr´e Prigge: Computing Delay Resistant Railway
Timetables
2007/03 Christian Liebchen and Gregor W¨unsch and Ekkehard K¨ohler and
Alexander Reich and Romeo Rizzi: Benchmarks for Strictly Fundamental
Cycle Bases
2006/32 Romeo Rizzi and Christian Liebchen: A New Bound on the Length of
Minimum Cycle Bases
2006/24 Christian Liebchen and Sebastian Stiller: Delay Resistant Timetabling
2006/08 Nicole Megow and Tjark Vredeveld: Approximation Results for Preemp-
tive Stochastic Online Scheduling
2006/07 Ekkehard K¨ohler and Christian Liebchen and Romeo Rizzi and Gregor
W¨unsch: Reducing the Optimality Gap of Strictly Fundamental Cycle Bases
in Planar Grids
2006/05 Georg Baier and Thomas Erlebach and Alexander Hall and Ekkehard
K¨ohler and Heiko Schilling: Length-Bounded Cuts and Flows
2005/30 Ronald Koch and Martin Skutella and Ines Spenke : Maximum k-
Splittable Flows
2005/29 Ronald Koch and Ines Spenke : Complexity and Approximability of
k-Splittable Flows
2005/28 Stefan Heinz and Sven O. Krumke and Nicole Megow and J¨org Rambau
and Andreas Tuchscherer and Tjark Vredeveld: The Online Target Date
Assignment Problem
2005/18 Christian Liebchen and Romeo Rizzi: Classes of Cycle Bases
2005/11 Rolf H. M¨ohring and Heiko Schilling and Birk Sch¨utz and Dorothea
Wagner and Thomas Willhalm: Partitioning Graphs to Speed Up Dijkstra’s
Algorithm.
2005/07 Gabriele Di Stefano and Stefan Krause and Marco E. L¨ubbecke and
Uwe T.Zimmermann: On Minimum Monotone and Unimodal Partitions of
Permutations
2005/06 Christian Liebchen: A Cut-based Heuristic to Produce Almost Feasible
Periodic Railway Timetables
2005/03 Nicole Megow, Marc Uetz, and Tjark Vredeveld: Models and Algorithms
for Stochastic Online Scheduling
2004/37 Laura Heinrich-Litan and Marco E. L¨ubbecke: Rectangle Covers Revis-
ited Computationally
2004/35 Alex Hall and Heiko Schilling: Flows over Time: Towards a more Real-
istic and Computationally Tractable Model
2004/31 Christian Liebchen and Romeo Rizzi: A Greedy Approach to Compute
a Minimum Cycle Bases of a Directed Graph
2004/27 Ekkehard K¨ohler and Rolf H. M¨ohring and Gregor W¨unsch: Minimizing
Total Delay in Fixed-Time Controlled Traffic Networks
2004/26 Rolf H. M¨ohring and Ekkehard K¨ohler and Ewgenij Gawrilow and Bj¨orn
Stenzel: Conflict-free Real-time AGV Routing
2004/21 Christian Liebchen and Mark Proksch and Frank H. Wagner: Perfor-
mance of Algorithms for Periodic Timetable Optimization
2004/20 Christian Liebchen and Rolf H. M¨ohring: The Modeling Power of the
Periodic Event Scheduling Problem: Railway Timetables — and Beyond
2004/19 Ronald Koch and Ines Spenke: Complexity and Approximability of k-
splittable flow problems
2004/18 Nicole Megow, Marc Uetz, and Tjark Vredeveld: Stochastic Online
Scheduling on Parallel Machines
2004/09 Marco E. L¨ubbecke and Uwe T. Zimmermann: Shunting Minimal Rail
Car Allocation
2004/08 Marco E. L¨ubbecke and Jacques Desrosiers: Selected Topics in Column
Generation
2003/050 Berit Johannes: On the Complexity of Scheduling Unit-Time Jobs
with OR-Precedence Constraints
2003/49 Christian Liebchen and Rolf H. M¨ohring: Information on MIPLIB’s
timetab-instances
2003/48 Jacques Desrosiers and Marco E. L¨ubbecke: A Primer in Column Gen-
eration
2003/47 Thomas Erlebach, Vanessa K¨a¨ab, and Rolf H. M¨ohring: Scheduling
AND/OR-Networks on Identical Parallel Machines
2003/43 Michael R. Bussieck, Thomas Lindner, and Marco E. L¨ubbecke: A Fast
Algorithm for Near Cost Optimal Line Plans
2003/42 Marco E. L¨ubbecke: Dual Variable Based Fathoming in Dynamic Pro-
grams for Column Generation
2003/37 S´andor P. Fekete, Marco E. L¨ubbecke, and Henk Meijer: Minimizing
the Stabbing Number of Matchings, Trees, and Triangulations
2003/25 Daniel Villeneuve, Jacques Desrosiers, Marco E. L¨ubbecke, and Fran¸cois
Soumis: On Compact Formulations for Integer Programs Solved by Column
Generation
2003/24 Alex Hall, Katharina Langkau, and Martin Skutella: An FPTAS for
Quickest Multicommodity Flows with Inflow-Dependent Transit Times
2003/23 Sven O. Krumke, Nicole Megow, and Tjark Vredeveld: How to Whack
Moles
2003/22 Nicole Megow and Andreas S. Schulz: Scheduling to Minimize Average
Completion Time Revisited: Deterministic On-Line Algorithms
2003/16 Christian Liebchen: Symmetry for Periodic Railway Timetables
2003/12 Christian Liebchen: Finding Short Integral Cycle Bases for Cyclic
Timetabling
Reports may be requested from: Sekretariat MA 6–1
Fakult¨at II – Institut f¨ur Mathematik
TU Berlin
Straße des 17. Juni 136
D-10623 Berlin – Germany
e-mail: kli[email protected]
Reports are also available in various formats from
http://www.math.tu-berlin.de/coga/publications/techreports/
and via anonymous ftp as
ftp://ftp.math.tu-berlin.de/pub/Preprints/combi/Report-number-year.ps
