<figure><img src="image_1.png" /></figure>

HAL
open science

# Delay Propagation in Metro Timetables

Antoine Thébault, Loïc Hélouët, Kenza Harkouken Saiah

► To cite this version:

Antoine Thébault, Loïc Hélouët, Kenza Harkouken Saiah. Delay Propagation in Metro Timetables. 2024. [https://arxiv.org/abs/2407.04115](https://arxiv.org/abs/2407.04115)

HAL Id: hal-04711540

https://inria.hal.science/hal-04711540v1

Preprint submitted on 27 Sep 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Delay Propagation in Metro Timetables

Antoine Thébault, INRIA Rennes & Alstom Transport,
Loïc Hélouët, INRIA Rennes,
Kenza Saiah, Alstom Transport

***Abstract***—Metro networks are usually operated with timetables, i.e. schedules with fixed dates for departure and arrival events. However, when a delay occurs, timetables have to be adapted to mitigate the effect of this time gap. This paper proposes several algorithms to propagate the effects of primary delays in a timetable. The principle of delay propagation is to compute the minimal modification to the original timetable induced by this delay. We define timetables as weighted acyclic graphs depicting events, causal dependencies, and timing constraints, and show that the minimal modification is achieved by rescheduling events as soon as possible in this graph. We propose five algorithms to compute efficiently new consistent dates after a delay, with the minimal modification w.r.t. the original timetable. The first algorithm uses properties of critical paths in the timetable, the second algorithm builds a topological ordering on events before a linear rescheduling of events dates. The third algorithm is a recursive scheme that may explore the whole timetable in the worst case, but stops on events that need no rescheduling. The next algorithms are still recursive schemes, but use heuristics to choose an ordering for events updates. Recursive schemes have a bad theoretical worst case complexity. However, tests on two real case studies show that they are efficient in practice, and reschedule timetables in a fraction of seconds.

***Index Terms***—Metro scheduling, Timetables, planning, delay propagation.

## I. INTRODUCTION

Traffic management in metro system is an essential activity to ensure that the service provided to users meets an expected quality. Quality is often perceived through key performance indicators, that measure for a day of operation of a network the number of passengers transported, their comfort (the number of passengers per square meter), the average delay between two trains in a set of stations at peak hours, etc. [20].

On one hand, operators are helped by traffic management algorithms, that give advices: dwell times, speed profiles of trains... These advices are *online* timing and scheduling decisions provided to improve quality of service. On the other hand, a way to achieve good quality metrics is to plan trains missions *a priori* in an optimal way, and make sure that these plannings are respected. To achieve this objective, the orchestration of missions is collected in a timetable to define an ordering between arrivals, departures, train insertions, etc. The orchestration is then optimized w.r.t. quality objectives such as regularity of departures in stations. Optimization of timetables is called a *timetabling problem*. Many properties have to be considered: the available rolling stock, maintenance issues, regularity or punctuality of arrival/departure dates of trains, trains insertions and removals from a fleet,... An additional concern is also energy consumption [18], [22].

Timetabling optimizes performance indicators, but designers also have to ensure that the produced schedules are robust enough and can be realized even if some arrivals or departures of trains are delayed. This latter constraint is achieved by integrating *time buffers* to schedules: An event *f* is not scheduled at the earliest possible date $d_f$ meeting constraints w.r.t. its predecessors, but rather at a slightly delayed date $d_f + \delta$. Integrating a time buffer of $\delta$ time units between an event *e* and all its successors allow delaying *e* of up to $\delta$ time units without missing other future deadlines in the timetable. Optimization of a schedule is hence a difficult task: it requires expertise to design a good timetable, but it is also computationally expensive. As a consequence, timetabling is usually performed *offline*, using heavy simulation techniques, Mixed Integer Linear programming, or I.A. inspired algorithms. Such techniques cannot be used online to take a decision. So, as soon as an optimized reference timetable exists, a standard traffic management algorithm is to adhere as much as possible to this schedule.

Adhering to a schedule means monitoring all executed events up to the current date, and based on delayed events, reprogram the dates of the yet unexecuted part of the timetable so that in a near future, all events are scheduled at their originally specified date. Now, when an event is postponed, this delay may propagate to all its successors. A way to recover from a primary delay is to reduce the dwell time in stations, or increase trains speed. Reduction of dwell time or speed increase is visible in a timetable as time buffers, i.e. in situations where a departure or arrival date is not the earliest possible date $d_{opt}$, but rather at a later date $d_{opt}+b$. Consuming time buffers allows to recover from a primary delay after a few arrivals and departures. However, these decisions recover at most a few seconds of delay at each station, and a complete recovery after a large primary delay may occurs only after many consecutive arrivals and departures. Hence in the worst cases, a delay may force rescheduling the whole timetable.

Timetables are large data structures representing departures and arrivals of trains and their dependencies for a whole day of operation. This may represent thousands of events, so one cannot consider exploring this structure after each delay. Now, if timed buffers have been appropriately used, primary delays may propagate to a limited subset of events. An interesting question in hence how to propagate delays in a fast, accurate and efficient way, without considering a costly rescheduling of the whole timetable?

In this paper, we consider rescheduling algorithms for timetables encoded as timed dependency graphs, and study several online algorithms to reschedule a timetable. The first approach computes the maximal time constraint between a late
event and its successors to assign new dates to unexecuted events. This constraint is obtained by computing critical paths in the timetable. The second approach is a rescheduling algorithm that recomputes the earliest possible date of an event when all its predecessors have been attributed a new realization date. To achieve this objective, we reprogram the dates of events following a topological ordering. This algorithm ensures that the new date of an event is computed only after all dates of all its predecessors are available. The next approach proposed is a recursive algorithm, that propagates inductively delays along all possible path originating from the primarily delayed event up to stabilization. Even if this algorithm seems to have a bad theoretical worst case complexity, we show in the last part of the paper that its performances are good on real case timetables. The last solutions proposed use heuristics to guide recursion, and avoid exploring all paths in the timetable. This makes sense as recursive propagation of delays stops as soon as an event is not postponed. Several solutions are proposed: the first one visits events with maximal rescheduled dates first, the second one events with minimal dates. The third heuristic groups events into set of events with identical planned date, and orders them according to a topological ordering. Theoretical analysis show that the critical path solution and the recursive approaches have an exponential cost in the worst cases, and that the approach with a topological ordering requires polynomial time for a rescheduling of a timetable.

The last part of this work compares performance of our algorithms on case studies, namely the metros of Montreal and Rennes. For each case study, we consider several scenarios causing many delays w.r.t. a planned metro schedule covering several hours of operation of the network. We show on these large case studies that in fact, recursive solutions have better performance in practice than the approach based on topological ordering.

## II. PRELIMINARIES

A timetable can be formally encoded as a weighted acyclic graph with dates. In this graph, nodes represent events (arrivals or departures of trains), edges represent causal dependencies among events (the departure of a train must occur after the preceding arrival). The weight $w_{e,f}$ of an edge from an event $e$ to an event $f$ is a time constraint, and represents the fact that the occurrence date $d_f$ of event $f$ must be greater than the date of realization of $e$, plus some delay $w_{e,f}$. This type of constraint can model minimal dwell times, e.g. impose that a train cannot leave a station earlier than 10 second after its arrival, durations of trips from a station to the next one... In addition to this weighted graph structure, dates are attached to events. They represent a schedule for events.

In the rest of the paper, we will use timetable both for representation of timing constraints and for simulation purposes. We hence embed into our definition of timetable a notion of initially planned date, realized events, realization date and planned date for yet unexecuted events.

**Definition 1.** A timetable is a tuple $TT = (E, D_{init}, D_r, D_p, \mapsto, X)$ where:

* $E$ is a set of events, $X \subseteq E$ is a set of realized events

* $D_{init}: E \to \mathbb{R}$ is a map that defines the initial scheduled date of each event. These dates are never updated during simulation and rescheduling of events, as they serve as reference to decide whether an event is late or not w.r.t. the original schedule.

* $D_r: X \to \mathbb{R}$ assigns to each realized event its actual realization date.

* $D_p: E \to \mathbb{R}$ assigns to each event in $E \setminus X$ a planned realization date.

* $\mapsto \subseteq E \times E \times \mathbb{R}^{\ge 0}$ is a set of causal dependencies. Every dependency of the form $(e_1, e_2, c)$ indicates that event $e_1$ must occur before event $e_2$, and that at least $c$ time units must elapse between the realization of $e_1$ and the realization of $e_2$.

We consider systems running and taking decisions with a traffic management algorithm that tries to adhere to an optimal initial timetable, and reschedules events at best when delays occur. The system starts at date 0 with a timetable where $D_p(e) = D_{init}(e)$ for every $e \in E$. The timetable is maintained at each occurrence of one of its events, so planned and realization dates can be updated, but the timetable must preserve several properties at each instant. For simplicity, we consider that events can only occur on time, or late. This implies that for every event $e \in E$,

$$D_r(e) \geq D_p(e) \geq D_{init}(e) \quad (1)$$

The above property means the the realization date of an event is always greater or equal to its planned date, which is always greater or equal to its initially planned date. The second property is that occurrence dates of events are recorded faithfully, i.e. once an event $e$ is realized at instant $t$, we have: $\{D_p(e) = D_r(e) = t\}$. We further have three consistency rules for every dependency $(e_1, e_2, c) \in \mapsto$. We have a constraint on the dates in the original timetable:

$$D_{init}(e_2) \geq D_{init}(e_1) + c \quad (2)$$

and at every step of simulation, we have:

$$D_p(e_2) \geq D_p(e_1) + c \quad (3)$$

and if $e_1 \in X$ is an event that already occurred,

$$D_p(e_2) \geq D_r(e_1) + c \quad (4)$$

To simplify notations, for every event $e \in E$ in a timetable, we define the following sets:

* $succ(e)$ is the set of immediate successors of $e$, i.e. events that immediately depend on $e$: $succ(e) = \{f \in E | \exists(f, e, c) \in \mapsto\}$

* $pre(e)$ is the set of immediate predecessors of $e$: $pre(e) = \{f \in E | \exists(f, e, c) \in \mapsto\}$

* $succ^*(e)$ is the set of events which are successors of $e$, i.e. it is the transitive closure of the immediate successor relation: $succ(e) \in succ^*(e)$, and $f \in succ^*(e) \Rightarrow succ(f) \in succ^*(e)$.
<figure><img src="image_3.png" /><figcaption>Fig. 1: An example of consistent timetable with 6 events.</figcaption></figure>

For a pair of events $(e, f)$ such that $(e, f, c) \in \rightarrow$, we define $dep(e, f) = c$, i.e. $dep: E \times E \rightarrow \mathbb{R}$ is a function that gives the value of time constraint in dependency $(e, f, c)$. A path in a timetable from an event $e_0$ to an event $e_k$ is a sequence of events $\rho = e_0.e_1...e_k$ such that $\forall i \in 0..k-1, e_{i+1} \in succ(e_i)$. The weight of a path $\rho$ is $W_{\rho} = \sum_{i \in 0..k-1} dep(e_i, e_{i+1})$.

Figure 1 represents a toy timetable with 6 events. We represent events with circles, realized events in $X$ with a grey filled area, and dependencies of the form $(e, f, c)$ by an edge of weight $c$. In the current state of the system, events $e_0$ and $f_1$ have already occurred. Considering maps $D_{init}$, $D_p$, $D_r$, one can see that $e_0$ has occurred at date 2, i.e. with a delay of 2 time units w.r.t. the originally scheduled date, forcing rescheduling of events $f_1$ and $e_1$. Event $f_1$ has occurred with a delay of 1 time unit. Notice that despite the delay, events $e_2, e_3$ and $f_2$ can still be realized at their originally planned date.

We consider metro systems equipped with traffic management schemes that use and maintain a timetable. In this setting, we can abstract away most of the operational setting and the running environment, and consider only how timetables are updated at runtime upon occurrence of a particular event $e$ at date $d$. Realization of event $e$ at date $d$ transforms a timetable $TT = (E, D_{init}, D_r, D_p, \mapsto, X)$ into an updated timetable $TT' = (E, D_{init}, D'_r, D'_p, \mapsto, X' = X \cup \{e\})$ where:

* $D'_r(f) = d$ if $f = e$ and $D'_r(f) = D_r(f)$ otherwise

* $D'_p = D_p$ if event $e$ occurs on time, i.e. $d = D_p(e)$. If $d > D_p(e)$, then $D'_p$ is obtained as the result of a rescheduling algorithm that:

- sets $D'_p(e) = d$ and $D'_r(e) = d$,

- Preserves constraints (3) and (4),

- leaves $D_p$ unchanged for all events in $X$,

- minimizes

$$DSUM(TT) = \sum_{f \in E \setminus X} D_p(f) - D_{init}(f) \quad (5)$$

Intuitively, (5) means that the algorithm used to reschedule occurrence dates for yet unexecuted events should minimize the differences between new dates and the dates planned in original timetable. We will write $TT \xrightarrow{(e,d)} TT' = Update(TT, d, e)$ to denote the fact that $TT'$ is the timetable computed after occurrence of event $e$ at date $d$ (with the

help of a rescheduling algorithm). We will show later in this section that the rescheduled timetable that minimizes discrepancies w.r.t. the initial timetable is unique, and in the following sections, we will define several algorithms to compute $Update(TT, d, e)$. Abstracting the running environment, we can define the realization of a schedule and the associated timetable updates as the application of the operational rule below:

$$\frac{d \geq D_p(e) \quad \forall pre(e) \subseteq X}{TT \xrightarrow{(e,d)} TT' = Update(TT, d, e)}$$

Intuitively this operational rule says that $e$ can be executed at date $d$ if all predecessors of $e$ in $pre(e)$ have already occurred, and if $d$ is greater or equal to the planned date for $e$. The realization of a timetable starts at date 0, and evolves upon occurrence of events occurring at increasing dates. In a timetable, every event $e$ is planned at a particular date $D_{init}(e)$, but does not necessarily occur at this date during operation. We will say that a delay $\delta > 0$ occurs when realizing $e$ at date $d$ if $d - D_p(e) = \delta$. Execution dates for events are uncontrollable, and can be seen as a choice from the running environment of the timetable (i.e. the physical metro system, plus int traffic management algorithm). However, application of rescheduling allows to maintain consistency of timetables (i.e. satisfy inequalities (2-4)) at any instant.

The question now is how to propagate a delay to the successors of $e$, that is, how to design an algorithm to implement $Update(TT, d, e)$. A first requirement is that the propagation scheme must preserve the consistency of predicted dates $D_p$, see equation (1-4). Second, the propagation should help returning to the initial timetable as fast as possible. Formally, a rescheduling of a timetable $TT$ upon occurrence of a delay $\delta$ in realization of an event $e$ is performed as soon as possible (ASAP for short) iff, for every event $f$ in $E \setminus X$,

$$D'_p(f) = \max \left( D_{init}(f), \max_{y \in pre(f)} (D'_p(y) + dep(y, f)) \right) \quad (6)$$

A hidden advantage of a fast return to the original schedule is that it is also minimizes the discrepancies between dates of the original timetable and updated dates (value DSUM in (5)), as shown by the following proposition. Hence, assuming that a timetable is designed to optimize some KPI, returning to this schedule as fast as possible can be seen as a sensible way to preserve performances of a metro system.

**Proposition 1.** Rescheduling a timetable as soon as possible results in a unique timetable $TT'$, for which $DSUM(TT')$ is minimal.

*Proof.* Uniqueness of an earliest as possible rescheduling is easy to prove. First of all, for every realized event, $f \in X$, $D_p(f) = D_r(f)$ and is fixed in the timetables $TT$ and $TT'$. We also have that for every $f \in E$, $D_{init}(f)$ is constant. Now, assume that for a given event $x$, all values of $D'_p(y)$ for every predecessor $y \in pre(x)$ are uniquely defined. Then
$$D'_p(x) = \max \left( D_{init}(x), \max_{y \in pre(x)} (D'_p(y) + dep(y, x)) \right)$$ is also an unique value. Consider an event $e$ such that $pre(e) \in X$. Then all values of $D'_p(y)$ for every predecessor $y \in pre(e)$ are set to $D_r(y)$. Hence, by induction on the depth of events in the timetable, we can prove that $D'_p(f)$ is uniquely defined by an ASAP rescheduling.

It now remains to show that ASAP rescheduling minimize $DSUM(TT')$. Without loss of generality, we can assume that all timetables have a starting event $e_⊥$ that precedes all events in $e$ and occurs at date 0. Now, let $\rho = e_⊥, e_1, \dots, e_k$ be a sequence of consecutive nodes in timetable $TT$, i.e. such that $e_{i+1} \in succ(e_i)$. The duration of path $\rho$ is $C_\rho = \sum_{d_i, d_{i+1} \in X} D_r(d_{i+1}) - D_r(d_i) + \sum_{d_{i+1} \notin X} D'_p(d_{i+1}) - D'_p(d_i)$.

We can prove that, in a timetable rescheduled ASAP, $D_p(f)$ is either equal to $D_{init}(f)$ or to the maximal cost of a path from $e_⊥$ to $f$. This can be done by induction on the size of timetables. For a timetable of size 1, the property is rather straightforward, as no rescheduling is needed (only $D_p(e)$ and $D_r(e)$ are updated and take value $d$). Assume that the property holds up to timetables of size $n$. Let us now consider a timetable $T_{n+1}$ of size $n+1$. First of all, one can notice that if all predecessors of an event $f$ are rescheduled at their initial date (and hence the difference between the planned date and the rescheduled date for these events is 0), then $f$ is also rescheduled at date $D_{init}(f)$. Let $f$ be a maximal event in $T_{n+1}$, w.r.t. $\mapsto$. Every event $x$ in $T_{n+1} \setminus \{f\}$ has a planned date $D'_p(x)$ that corresponds to its initial date or to the cost of a maximal path from $e_⊥$ to $x$, and this is in particular the case for every predecessor of $f$. As $TT'$ must be consistent, any constraint of the form $(x, f, c)$ is verified, that is, $D'_p(f) \ge D'_p(x) + c$. It is hence easy to see that the minimal value for $D'_p(f)$ is either the maximal duration of a path from $e_⊥$ to $x \in pre(f)$ plus $dep(x, f)$, that is also the maximal duration of a path from $e_⊥$ to $f$, or $D_{init}(f)$.

We can now show that, for a timetable $TT_n$ of size $n$, if events are rescheduled at their earliest possible dates to obtain a timetable $TT'_n$, then $DSUM(TT')$ is minimal. This property can again be proved by induction on the size of the timetable. Let us first prove that this property is true for a timetable of size 2, i.e. when the first event $e_1$ is realized and only the second one $e_2$ needs to be rescheduled. There are two possibilities: either $(e_1, e_2, c) \not\mapsto$, and hence $D'_p(e_2) = D_{init}(e_2)$ and so $DSUM(TT')$ is minimal, or $(e_1, e_2, c) \mapsto$, and $D'_p(e_2) = \max(D_{init}(e_2), D_r(e_1) + c)$ and in this case, $D'_p(e_2)$ is the unique and hence minimal date allowed for $e_2$, so $DSUM(TT')$ is minimal.

Now, let us assume that, for every timetable of size $n$, the ASAP rescheduling of events is optimal w.r.t. $DSUM(TT')$. Consider a timetable $TT_{n+1}$ of size $n+1$. One can divide this timetable in a timetable $TT_n$ of size $n$ on one hand, and one event $e_{n+1}$, that is maximal w.r.t $\mapsto$, i.e. such that there exists no event $f$ such that $(e_{n+1}, f, c_{n+1})$ exists. Let $TT'_n$ be the ASAP rescheduling of $TT_n$. This rescheduling minimizes $\sum D'_p(e_i) - D_{init}(e_i)$ over $TT'_n$. Then the ASAP rescheduling of $TT_{n+1}$ is just an ASAP rescheduling of $TT_n$ followed by a calculus of a new date

for $e_{n+1}$. Let $X$ be the set of predecessors of $e_{n+1}$ in $TT_{n+1}$, i.e. events $x \in E$ such that $(x, e_{n+1}, c_x) \in \mapsto$. Then $D'_p(e_{n+1}) = \max \left( D_{init}(e_{n+1}), \max_{x \in X} D'_p(x) + c_x \right)$. If $X = \emptyset$ or $D_{init}(e_{n+1}) \ge D'_p(x) + c_x$ for every $x \in X$, then $D'_p(e_{n+1}) = D_{init}(e_{n+1})$ and so $DSUM(TT'_{n+1}) = DSUM(TT'_n)$ and is minimal (using the induction hypothesis). Otherwise, we have $D'_p(e_{n+1}) = D'_p(x) + c_x$ for some $x \in X$, and $D'_p(x) + c_x$ is hence the smallest possible value for $D'_p(e_{n+1})$, so $DSUM(TT'_{n+1}) = DSUM(TT'_n) + (D'_p(e_{n+1}) - D_{init}(e_{n+1}))$ is minimal. $\square$

A consequence of Proposition 1 is that optimizing the differences between an original timetable after realization of an event $e$ at some date $d$ amounts to scheduling remaining events at their earliest possible date. This is not surprising, as one tries to mitigate the effect of a primary delay by using the flexibility provided by time buffers in the original timetable. So, the delay of each rescheduled event decreases with the depth of the timetable. This does not provide straightforward ways to discriminate events that should be rescheduled or not. Consider the example of Figure 2. Let us assume that the event $e_1$, originally planed at date 5 occurs at date 10. A consequence is that events $e_2$ and $e_4$ have to be postponed to satisfy the consistency constraints. However, event $e_3$, which initial date was 15, needs no rescheduling. One can see from this example that events that are not delayed may have successors that are rescheduled anyway.

Building on Proposition 1, the rest of the paper will focus only on algorithms that compute ASAP reschedulings of timetables. Note, however, that even if the result of an ASAP rescheduling is unique, we will show in the next sections that there are several ways to compute the new planned dates of yet unexecuted events.

### III. CRITICAL PATHS

In this section we consider how the structure of a timetable and the planned date both influence the timetable updates. Let $TT \xrightarrow{(d,e)} TT'$. As highlighted in the proof of Proposition 1, the new planned date of an event $e_i$ in $TT'$ is the maximal date imposed by a path ending on $e_i$, and by the planned date $D_p(e_i)$ in the initial timetable. In planning algorithms and tasks scheduling, these paths are called *critical paths*. We can be more precise, and show that the critical paths that influence the new date of an event are paths originating from the executed event.

**Proposition 2.** Let $TT \xrightarrow{(d,e)} TT'$. Then, for every $f \in succ^*(e)$, $D'_p(f)$ is either equal to $D_p(f)$ or to $d + cps(e, f)$, where $cps(e, f)$ is the weight of a critical path from $e$ to $f$.

*Proof.* This is a direct consequence of the properties of ASAP rescheduling shown in section II, that require that $D'_p(f) = \max(D_p(f), \max_{x \in pre(f)} (D'_p(x) + dep(x, f)))$. Assume that Proposition 2 holds up to predecessors of $f$. Then we can show that it also holds at event $f$. A first case is
<figure><img src="image_4.png" /><figcaption>Fig. 2: Propagation of a delay: event $e_1$ is realized with a 5 time units delay.</figcaption></figure>

when every event $x \in \text{pre}(f)$, we have $D'_p(x) = D_p(x)$. Then, as TT is consistent, we have $D'_p(f) = D_p(f)$. Now, assume $D'_p(f) > D_p(f)$. Then, there exists a predecessor $x_{\max} \in \text{pre}(f)$ such that $D'_p(x_{\max}) > D_p(x_{\max})$ and $D'_p(x_{\max}) + \text{dep}(x_{\max}, f) \ge D'_p(x') + \text{dep}(x', f)$ for every $x' \in \text{pre}(f)$. So, the critical path from $e$ to $x_{\max}$ augmented with the edge $(x_{\max}, f, \text{dep}(x_{\max}, f))$ is a critical path from $e$ to $f$, and $D'_p(f) = d + \text{cps}(e, f)$. $\square$

Computing the weight of a critical path from an event $e$ to an event $f$ in an acyclic graph can be done using shortest paths algorithms, as proved in [23].

**Proposition 3** ([23], Proposition T.). Let $G = (E, \rightarrow)$ be a directed acyclic weighted graph with root $e$, let $-G$ be the weighted graph obtained by replacing every weight in $G$ by its negation. Let $W_f$ be the weight computed by a shortest path algorithm for vertex $f$ in $-G$. Then, the longest path from $e$ to $f$ in $G$ has weight $-W_f$.

Let us notice an important point for practical use of Proposition 3: the shortest path algorithm used to compute lengths of critical paths from $e$ to one of its successors cannot be Dijkstra's algorithm [11], because a prerequisite of Dijkstra's algorithm is that the considered graph has positive weights. However, the well known Bellman-Ford algorithm [1], [2] can compute shortest distances from a source node to all other nodes in a graph with $n$ nodes and $m$ vertices in $O(m \cdot n)$.

Computing the weight of a critical path from $e$ to every event in $E' = E \setminus X$ is then done by application of Bellman-Ford's algorithm on graph $-G = (E', R)$ where $(e, f, -c) \in R$ iff $e, f \in E'$ and $(e, f, c) \in \rightarrow$. We obtain, for each event $f \in \text{succ}^*(e)$ a negative value $\text{CPD}(f)$, that is the negation of the weight of a critical path from $e$ to $f$. Then, for every event $f \in E'$, if $D_p(f) < D_r(e) - \text{CPD}(f)$ we set $D'_p(f) = -\text{CPD}(f) + c$.

A quick improvement is to consider only events in $\text{succ}^*(e)$. Let $n_s = |\text{succ}^*(e)|$ denote the size of the set of successors of $e$, and $m_s$ the number of dependencies among events in $\text{succ}^*(e)$. Considering events in $\text{succ}^*(e)$ restricts updates to a part of the timetable with $n_s < n$ events and $m_s < m$ edges. These edges and events can be found found via a breadth First Search (BFS) in the timetable, starting from event $e$, i.e. it can be done in $O(m_s + n_s)$. This slight change yields an overall complexity in $O(m_s \cdot n_s)$ for the rescheduling of a

single event. This improvement (BFS followed by Bellman-Ford on a negation of the explored graph) is implemented in Algorithm 1 below.

For the realization of a whole timetable of size $n$, assuming in the worst case that every event is late, and that the timetable has many dependencies (yielding a number of dependencies in $O(n^2)$), then the running cost overhead due to updating events dates is in $O(\sum_{i=1..n} i^3) = O(\frac{1}{4} \cdot n^2(n+1)^2)$. We will show in the next sections that there exists algorithms that can perform a rescheduling in $O(2 \cdot (m_s + n_s))$, so Algorithm 1 is a priori inefficient.

However, reasoning in terms of critical path can help building exploration strategies that reduce the number of paths visited in a timetable. As mentioned earlier, the new date $D'_p(f)$ of a rescheduled event $f$ in $\text{succ}(e)$ is the date imposed by a critical path ending on event $f$, that is a path of the form $\rho = e \cdot e_1 \cdot e_2 \dots e_k \cdot f$, and such that $D'_p(e_i) = D'_p(e_{i-1}, +\text{dep}(e_{i-1}, e_i))$. Lemma 1 below shows that along a critical path of a consistent table, there exists a position in the path where delays stop propagating to the following events of the path, i.e. there is an integer value $mr$ such that, if $i > mr$ we have $D'_p(e_{i+1}) = D_p(e_{i+1}) = D_p(e_i) + \text{dep}(e_i, e_{i+1})$.

**Lemma 1.** Let TT be a consistent timetable. Let $\rho = e \cdot e_1 \cdot e_2 \dots e_k \cdot f$ be a critical path from $e$ to $f$, and $m_r$ be the index of the first event such that $D'_p(e_{mr}) = D_p(e_{mr}) = D_p(e_{mr-1}) + \text{dep}(e_{mr-1}, e_{mr})$. Then, for every event in $\rho$ of index $i > mr$, $D'_p(e_i) = D_p(e_i)$.

*Proof.* We can show this property by induction on the length of critical paths. If the path is of length 2, then the property vacuously holds. Now, let us assume that the property holds for every path of size $\le n$, and let us show that it holds for paths of length $n+1$. First, we can notice that if $\rho = e \cdot e_1 \cdot \dots \cdot e_{n-1} \cdot f$ is a critical path from $e$ to $f$, then $e \cdot e_1 \cdot \dots \cdot e_{n-1}$ is a critical path from $e$ to $e_{n-1}$. Hence, there exists an index $mr_n$ such that for every $i$ in $mr_n+1 \dots n-1$, $D'_p(e_i) = D_p(e_i)$. If $mr_n = n-1$, then there are two options: either $D'_p(e_{n-1}) = D_p(e_{n-1})$, or $D'_p(e_{n-1}) > D_p(e_{n-1})$. In the first case, as $\rho$ is a critical path to $f$, then $D'_p(f) = \max(D_p(f), D_p(e_{n-1} + \text{dep}(e_{n-1}, f)))$. As TT is consistent, we have $D_p(f) \ge D_p(e_{n-1} + \text{dep}(e_{n-1}, f))$, so $D'_p(f) = D_p(f)$, and we can take $mr_n$ as index witnessing the property for path $\rho$ of size $n+1$. In the second case, we have $D'_p(e_{n-1}) > D_p(e_{n-1})$. So, if $mr_n$ exists, it can only be set to $n$, and hence it is vacuously true that in $\rho$, for every $i > mr_n$ we have $D'_p(e_i) = D_p(e_i)$. If $mr_n < n-1$,
**Algorithm 1 Critical Path Propagation**

**Input**: A timetable TT, an event *e*, realized at date $D_r(e)$

**Output**: A new timetable TT' with ASAP rescheduling

// (Step 1) BFS exploration
//to build graph $-G = (S, R)$

$S = \{e\}$ // Vertex list in -G
$CPD(e) = 0$ // CPD assigns a path value
// to each event, and gives the
// weight of critical paths
// at the end of Algo.1

$R = \emptyset$ // List of edges in SxS

$F = e$ // Queue containing unexplored
// successors of e

while F is not empty do

$x := \text{RemoveFirstElement}(F)$

for each event $f \in \text{Succ}(x)$ do

add $(x, f, -\text{dep}(x, f))$ to R

if $f$ not in S then

$S = S \cup \{f\}$

$F := F.f;$

$CPD(f) = \infty$

end if

end for

end while

// Graph $-G = (S, R)$ is built,
// S contains all successors of e,
// weights in SxS are negated

// (Step 2) (Bellman-Ford)

// Compute weights of critical paths

// from e to vertices in S

for each event $e \in S$ do

for each arc $(x, y, c) \in R$ do

$CPD(y) = \min(CPD(x) + c, CPD(y))$

end for

end for

// (Step 3) Use CPD values to change

// planned dates of successors of e

for each event $x \in S$ do

$D'_p(x) = \max(D_p(x), D_r(e) - CPD(x))$

end for

then as the property holds for path of size up to *n*, we have
$D'_{p}(e_{mr+1}) = D'_{p}(e_{mr+1}), D'_{p}(e_{mr+2}) = D'_{p}(e_{mr+2}), \dots$ and
$D'_{p}(e_{n-1}) = D_{p}(e_{n-1})$. As *TT* is consistent, the same argu-
mentation as with index $mr_n = n-1$ holds, that is, $D'_{p}(f) =$
$\max(D_{p}(f), D_{p}(e_{n-1} + \text{dep}(e_{n-1}, f))) = D_{p}(f)$. $\square$

Consider the example of Figure 3. We show a situation where an event $e_1$ (in red), originally planned at date 21 is delayed and occurs at date 24. We represent planned date of an event $f$ in the timetable as a dependency from a fake event $e_\perp$ to $f$ carrying weight $D_p(f)$. Dependencies among events are represented by dashed arrows, or plain red arrows if they belong to a critical path from $e_\perp$. The table below shows how

events dates are updated after late execution of $e_1$. In this table, $D_p(x)$ is the original date, and $D'_p(x)$ the updated date of an event $x$. Notice in particular that events $e_2, e_3, e_4$ and $e_6$ take the date imposed by the critical path from $e_1$, while other events keep their former dates. In Figure 3, we color the event $e$ with the initial delay in red, the rescheduled events in orange, and events with unchanged dates in green.

<table><caption>TABLE I: An update of events dates for the timetable of Figure 3.</caption><thead><tr><th></th><th>e<sub>1</sub></th><th>e<sub>2</sub></th><th>e<sub>3</sub></th><th>e<sub>4</sub></th><th>e<sub>5</sub></th><th>e<sub>6</sub></th><th>e<sub>7</sub></th><th>e<sub>8</sub></th><th>e<sub>9</sub></th></tr></thead><tbody><tr><td>D<sub>p</sub>(x)</td><td>20</td><td>25</td><td>25</td><td>30</td><td>40</td><td>45</td><td>53</td><td>50</td><td>54</td></tr><tr><td>D'<sub>p</sub>(x)</td><td style="background-color: #f8d7da; color: #49a049;">24</td><td style="background-color: #f8d7da; color: #49a049;">27</td><td style="background-color: #f8d7da; color: #49a049;">28</td><td style="background-color: #f8d7da; color: #49a049;">32</td><td style="background-color: #d9ead3; color: #49a049;">40</td><td style="background-color: #d9ead3; color: #49a049;">47</td><td style="background-color: #f8d7da; color: #49a049;">55</td><td style="background-color: #d9ead3; color: #49a049;">50</td><td style="background-color: #49a049; color: #f8d7da;">54</td></tr></tbody></table>

IV. TOPOLOGICAL ORDER

As shown in previous section, computing an optimal rescheduling of a timetable (w.r.t. differences with the original timetable) amounts to scheduling events as soon as possible. Finding a consistent date for an event is straightforward when the date of all its predecessors is known. Hence, to reschedule a timetable, one can consider once every unexecuted event $f$ and compute its new date if the order used to visit events assigns a new date to all events in $pre(f)$ before considering $f$. In task scheduling questions, this appropriate ordering is called a *topological ordering*.

**Definition 2.** Let $G = (E, \rightarrow)$ be an acyclic graph. A topological ordering on $E$ is a sequence $e_1 \cdot e_2 \dots e_{|E|}$, such that for every $e_i$, $(f, e_i) \in \rightarrow$ implies $f = e_k$ for some $k < i$.

Computing a topological order is a standard algorithm [9]. For an acyclic graph, it consists in building an ordered list $L_o$ of nodes such that the indices of events in the list satisfy the property of Definition 2: every predecessor of an event $e_i$ appear before $e_i$ in the list. In timetables, the graph $(E, \mapsto)$ is acyclic, so the notion of topological ordering applies. Notice that, if $e$ is an initially delayed event, and $f \notin succ^*(e)$, then the new date of $f$ in the updated timetable is unchanged. As a consequence, it is sufficient to build a topological ordering on $succ^*(e)$ and then explore this set in the order prescribed by the topological ordering to obtain consistent updated dates for events.

Building a topological order mainly consists in a depth first exploration of vertices in the graph, starting from an initial vertex. This exploration is given in Algorithms 2 and 3 The algorithms maintains a set of explored events $L_v$, and builds a sequence of events $L_o$. Initially, $L_o$ is empty, and all events are unexplored so $L_v$ is also empty. At each step of the algorithm starting from a node $e$ of the graph, a new DFS is initiated from every successor of $e$ yet unexplored. When all these successors are explored, node $e$ is appended to $L_o$ at the beginning of the list. This algorithm has been proved correct, with a complexity in $O(m+n)$, where $n$ is the number of nodes in the graph and $m$ the number of edges.
<figure><img src="image_5.png" /><figcaption>Fig. 3: Critical paths and rescheduling in $Succ^*(e_1)$. Critical paths are indicated in red.</figcaption></figure>

**Algorithm 2** Topological Order

**Input**: A graph $G = (E, \rightarrow)$, and event $e \in E$

**Output**: An ordered list of $L_o$ events in $Succ^*(e)$

**procedure** TOPOLOGICAL($e$)

$L_v := \emptyset$ Set of visited events

$L_o := \text{empty list}$ List of successors

DFS($e, L_v, L_o$)

return $L_o$

end procedure

**Algorithm 3** Depth First Search

**Input**: A graph $G = (E, \rightarrow)$, and event $e \in E$

**Output**: An update of set $L_v$ and list $L_o$

**procedure** DFS($e, L_v, L_o$)

for each $e' \in \text{succ}(e)$ do

if $e' \notin L_v$ then

$L_v := L_v \cup \{e'\}$

DFS($e', L_v, L_o$)

end if

end for

$L_o := e \cdot L_o$

add $e$ at the start of $L_o$

end procedure
If the topological ordering calculus described in Algorithm 2 is used from a node *e*, then the algorithm computes a topological ordering for the subgraph obtained by projection of the timetable on all successors of *e*. The cost of this calculus will then be in $O(n_s + m_s)$ where $n_s$ is the size of $succ^*(e)$ and $m_s$ is the number of dependencies in $\mapsto \cap(succ^*(e) \times succ^*(e) \times \mathbb{R})$

When an event *e* occurs late, its successors are the only events which dates are impacted by the delay. However, every event in $succ^*(e)$ may need to be rescheduled. This rescheduling can then be done by:

* Computing a topological order $L_o$ for events in $succ^*(e)$

* Visiting every event $e_i$ according to the order imposed by $L_o$, and at each event compute the new value for $D_p(e_i)$, i.e. set $D'_p(e_i) = \max(D_{init}(e_i), \max_{x \in pre(e_i)} D'_p(x) + dep(x, e_i))$.

This gives Algorithm 4 next page. Consider again the example of Figure 3, with event $e_1$ occurring late. The topological order construction of Algorithm 2 may return a sequence such as $L_o = e_1.e_2.e_4.e_5.e_3.e_6.e_8.e_9.e_7$, and from this sequence, Algorithm 4 computes the same results as in Table I. This is always the case, as we can prove that delay propagation using Topological Ordering builds the unique ASAP rescheduling of a timetable.

**Theorem 1.** *Delay propagation from an event *e* in a timetable *TT* with Topological Ordering computes a timetable *TT'* that is an ASAP rescheduling.*

*Proof.* We can proceed by induction on the size of the timetable. If *TT* is a timetable of size 1, then the delayed event is necessarily the only event in the timetable. Rescheduling of *TT* is hence *TT* itself, and one can vacuously conclude that all events delayed after *e* have been rescheduled at their earliest possible date. Now, let us assume that the property is true for any timetable of size up to *n*, and show that it then also holds for timetables of size *n* + 1. Let *TT*<sub>*n*+1</sub> be a timetable of size *n* + 1, and let *X* be the set of already executed events, *e* be the delayed event. Let $e_{n+1}$ be a maximal event w.r.t. $\mapsto$. We can compute a timetable *TT*<sub>*n*</sub> of size *n* by erasing $e_{n+1}$ from *TT*<sub>*n*+1</sub>. Then, according to the property, one can compute an ASAP rescheduling of *TT*<sub>*n*</sub> w.r.t. the delay occurring at event *e*. If $e_{n+1}$ is not in $succ^*(e)$, then any topological order on successors of *e* in *TT*<sub>*n*</sub> is also a topological order produced when exploring successors of *e* in *TT*<sub>*n*+1</sub>. Furthermore, one can safely compute a rescheduling for *TT*<sub>*n*+1</sub> by setting $D'_p(e_{n+1} = D_p(e_{n+1})$. So this rescheduling of *TT*<sub>*n*+1</sub> is an ASAP rescheduling. Let us now assume that $e_{n+1} \in Succ^*(e)$. The first step of the algorithm builds a topological order, using a Depth First Search algorithm. The topological order returned by the first step of the algorithm is hence a sequence of the form $L_{n+1} = e_1.e_2...e_i.e_{n+1}.e_{i+1}...e_k$, where $L_n = e_1.e_2...e_i.e_{i+1}...e_k$ is the topological order computed by DFS for *TT*<sub>*n*</sub>, and all predecessors of $e_{n+1}$ are in $e_1.e_2...e_i$. Hence, exploring sequence $L_{n+1}$ gives to events of *TT*<sub>*n*</sub> the same rescheduled date as in *TT*<sub>*n*</sub>, and associates to event $e_{n+1}$ the date $D'_p(e_{n+1}) =$

$\max(D_p(e_{n+1}), \max_{x \in Pred(e)}\{D_p(x) + c(x, e)\})$. So, updating timetable $TT_{n+1}$ when $e_{n+1} \in Succ^*(e)$ also gives an ASAP rescheduling. □

**Algorithm 4** Propagate a delay with topological order list

procedure PROPAGATETOPOLOGICAL(e)

$L_o = Topological(e)$

for each $e_i \in L_o$ do

$D'_p(e_i) = D_p(e_i)$

for each $x \in pre(e_i)$ do

$D'_p(e_i) = \max(D'_p(x) + dep(x, e_i), D'_p(e_i))$

end for

end for

end procedure

**Proposition 4.** *Algorithm 4 computes an ASAP rescheduling of a timetable after occurrence of a primary delay at event *e* in $O(2.(n_s + m_s))$.*

*Proof.* Overall, the complexity of delay propagation for a single late event *e* is in $O(2.(n_s + m_s))$, as it requires to build a topological order (in $O(n_s + m_s)$), and then reschedule each event in $succ^*(e)$ according to the dates of its predecessors. Notice that dependencies w.r.t. preceding events are visited only once, yielding a complexity in $O(n_s+m_s)$ for this second step. □

Now, rescheduling events at runtime may result in a time overhead in management of timetables, so we have to consider the overall cost of the algorithm for the whole period of operation for a timetable.

Every event may occur late, which may force rescheduling the remaining part of the timetable at each step. This means that rescheduling may occur $|E|$ times during the realization of a timetable. In the worst case, the size of the initial graph to consider with *n* events and a number of edges in $O(n^2)$, and every event is delayed. At step *i* of a timetable realization, let $E_i$ be the set of yet unexecuted events and let $n_i = |E_i|$ be the number of remaining events. Let us assume that in the worst case every event occurs late and requires rescheduling. We have $n_i = n_{i-1} - 1$, and the number of dependencies among events in $E_i$ is in $O(n_i^2)$. Hence, the overall operational cost for using a topological order is smaller than $\sum_{i \in 1..n} i^2 + \sum_{i \in 1..n} i$, that is in $O(n^3 + n^2)$. In practice, the subgraph visited by algorithm 4 is limited to $succ^*(e)$, and timetables have the shape of grids, so their are rather sparse graphs. If $succ^*(e)$ remains small, one may not have to pay this maximal overall cost for the realization of a timetable.

A possible variant is to build a topological order for the whole timetable once, an use this ordering for each rescheduling to avoid the initial step of Algorithm 4. Without loss of generality, we can consider that the timetable has a single root event $e_\perp$, that is a predecessor of all events in *E*. Then, one can compute $L_{init} = Topological(e_\perp)$, and at every late realized event *e*, consider events $e_i$ one after the other according to the unique ordering $L_{init}$, and update $D_p(e_i)$ if this event has not
yet been executed. This avoids recomputing a topological order for every realized event, but forces to consider a list of events that do not belong to $succ^*(e)$, or that need no rescheduling. That is, in the worst case, at each realized event, the whole set of yet unexecuted events in the timetable may have to be explored to update $D_p$. The worst case complexity of this variant is hence also in $O(n^3)$.

A natural question is whether the whole sequence $L_o$ for the topological ordering (computed once for all for a timetable or at each step on successors of a delayed event) must be explored. Remind Lemma 1, that indicates that along a critical chain, one can stop rescheduling along that chain as soon as an event with unchanged date is found. During the rescheduling of Algorithm 4, if, for en event $f_i \in succ^*(e)$ we have $D_p(f_i) \ge \max_{x \in pre(f_i)} D'_p(x) + dep(x, f_i)$ then $D'_p(f_i) = D_p(f_i)$, i.e., event $f_i$ is not rescheduled. The question is hence whether we can save some computation steps by stopping Algorithm 4 as soon as we find an event $f_i$ such that $D'_p(f_i) = D_p(f_i)$. An immediate answer is no, as a timetable can be a single chain of totally ordered events for which the condition $D_p(f_i) \ge \max_{x \in pre(f_i)} D'_p(x) + dep(x, f_i)$ is not met before the end of the sequence $L_o$. A second concern is that a topological ordering is built out of causal dependencies among events, without consideration for their dates. Topological orders are not critical chains, and the fact that $D'_p(f_i) = D_p(f_i)$ at index $i$ in a sequence $L_o$ does not mean that $D'_p(f_j) = D_p(f_j)$ for every $j > i$.

Consider, for instance the timetable represented in Figure 4. Assume that events $e_{11}, \dots, e_{18}$ have an initially planned date of 10, 20, \dots, 80 minutes, that events $e_{22}, \dots, e_{28}$ have planned dates 30, 40, \dots, 90, and events $e_{33}, \dots, e_{38}$ planned dates 50, 60, \dots, 100. This timetable is consistent. Now suppose that event $e_{11}$ (in red) occurs with a delay of 33 minutes, that is at date 43. This delay propagates to its successors: event $e_{12}$ cannot occur before date 45, event $e_{22}$ before date 50, etc. Now, after several propagation steps, as the timetable contains time buffers, the propagation stops. In Figure 4, we represent the initial late event in red, the rescheduled events in orange, and the event that are not rescheduled in green. The bottom part of the Figure represents a possible topological order returned by Algorithm 2. Ideally, one would like to explore the subpart of the timetable containing all orange events and stop. However, one cannot detect these events a priori from the topological order. When appending an event $e$ to a topological ordering obtained after a DFS (last instruction of Algorithm 3), one does not consider the date of $e$ nor the (future) date of its predecessors. Hence, in the sequence $L_o$ built, even when $i < j$ one can have $D_p(e_i) > D_p(e_j)$ or $D'_p(e_i) > D'_p(e_j)$, as $e_i, e_j$ need not be causally related. So, the total order on events given by a topological order cannot be seen as a sequence of delayed (orange) events followed by a sequence of up to date (green) events. This is for instance the case for events $e_{34}$ and $e_{15}$ in Figure 4. Hence, one cannot stop propagation of delays in Algorithm 4 as soon as a non-delayed (green) event is found.

## V. RECURSIVE PROPAGATION ALGORITHM

As shown in previous section, the topological ordering does not bring information on whether an event needs to be rescheduled. Hence, in Algorithm 4 one has to consider all events in $succ^*(e)$ and recompute their dates. However, one can see that if an event $e_i$ is not rescheduled, the constraint between $e_i$ and its successors is already met by $D_p()$. This does not mean however that no event in $succ(e_i)$ will be rescheduled, as $e_i$ need not be their unique predecessor. Yet, this means that one does not have to propagate constraints originating from $e_i$. In this section, we will formalize this idea and use it in a recursive scheme to update timetables, where recursion stops when there is no delay to propagate from an event to its successors.

We propose the following recursive scheme. Starting from a delayed event $e$, we will explore paths of the form $\rho = e.e_1.e_2 \dots e_k$ originating from $e$ in the graph $(E, \mapsto)$ and propagate the remaining effect of the original delay to events on this path to update $D'_p(e_i)$. For each explored event $e_i \in succ^*(e)$, we will memorize in $D'_p(e_i)$ the maximal value for the earliest consistent dates imposed by constraints met along a path ending in $e_i$ if it is greater than $D_p(e_i)$. We continue the recursive exploration of a path with an additional event $e_{i+1}$ if condition $D'_p(e_{i+1}) < D'_p(e_i) + dep(e_i, e_{i+1})$ holds.

<caption>**Algorithm 5 Nested Recursive Delay Propagation**</caption>

**Input**: A timetable $TT = (E, D_{init}, D_r, D_p, X)$, an event $e$, realized at date $d > D_p(e)$
**Set** $TT' = (E, D_{init}, D_r, D'_p, X \cup \{e\})$
**with** $D'_p(x) = \begin{cases} D_p(x) & \text{if } x \neq e, \\ d & \text{otherwise} \end{cases}$
**PROPAGATEDDELAY(e)**
**return** $TT'$

**procedure** PROPAGATEDDELAY(e)
    **for each** $e' \in succ(e)$ **do**
        **if** $D'_p(e) + dep(e, e') > D'_p(e')$ **then**
            $D'_p(e') := D'_p(e) + dep(e, e')$
            **PROPAGATEDDELAY(e')**
        **end if**
    **end for**
    **end procedure**

**Proposition 5.** *Delay propagation from an event $e$ in a timetable $TT$ with Nested Delay Propagation computes a timetable $TT'$ that is an ASAP rescheduling.*

*Proof.* Again we proceed by induction on the size of the timetable. First, the proposition holds obviously for a timetable of size 1, because $e$ is the only event to consider. So, recursion stops with the expected rescheduling $D_p(e) = d$. Let us now assume that Algorithm 5 computes ASAP dates for timetables of size $n$. Consider a timetable of size $n+1$ and an event $e_{n+1}$ that is maximal wrt $\mapsto$. The final planned date $D'_p(e_{n+1})$ is equal to the maximal value between $D_p(e_{n+1})$, and the maximal value $D'_p(x) + dep(x, e_{n+1})$ among predecessors of $e_{n+1}$. If each $x \in pre(e_{n+1})$ has its ASAP date, then
<figure><img src="image_6.png" /><figcaption>Topological ordering</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 4: Propagation of delays in $Succ^*(e_{11})$</figcaption></figure>

$e_{n+1}$ also has its ASAP rescheduled date. So if the algorithm computes ASAP dates for timetables of size $n$, it computes ASAP dates for timetables of size $n+1$. □

A direct consequence of Proposition 5 is that Algorithm 5 is correct, i.e., it computes an optimal and consistent rescheduling of a timetable after a primary delay.

**Proposition 6.** *Algorithm 5 computes an ASAP rescheduling of TT in $O(2^{n_s-1})$.*

*Proof.* Let us first prove that in the worst case, Algorithm 5 has to reschedule all events in $succ^*(e)$.

Let $bmax = \max_{(x,y) \in \rightarrow} D_p(y) - D_p(x) - dep(x, y)$ be the maximal size of a buffer in the timetable, i.e. the maximal delay that can be recovered when rescheduling a single event. Let $dmax$ be the maximal depth of a path starting at $e$. Assume that the initial delay at event $e$ is such that $d - D_p(e) > bmax \cdot dmax$. Then, the buffers in TT are not sufficient to recover from the primary delay, and all events in $succ^*(e)$ will be rescheduled.

Further, we can prove that, in some cases, the date of each event $f$ in $succ^*(e)$ has to be rescheduled every time $f$ is met along a new path during the execution of the algorithm. Let us first count the number of paths in $succ^*(e)$. It is well known that the number of paths from a source node $s$ to a target sink node $t$ in a graph of size $n$ is $O(2^{n-2})$. For a graph of size $n$, this number is achieved if there is an edge from every node of index $i$ to nodes of index greater than $i$.

Visiting all paths starting at $e$ amounts to visiting all paths from $e$ to a maximal node in $succ^*(e)$, or equivalently all paths in a graph of size $n_s+1$ built by adding to $succ^*(e)$ a new sink state $t_\perp$ and an edge from every maximal node in $succ^*(e)$ to $t_\perp$, whence the complexity. The bound is sharp, as one can build a graph with vertices $e_1...e_n$ and a dependency from every $e_i$ to all nodes with greater index, yielding $2^{n_s-1}$ paths. This type of graph have the shape of the graph represented in Figure 5. One can notice in this example that there are $2^3$ path from $e$ to $e_4$, visiting any subset of events in $\{e_1, e_2, e_3\}$. This type of acyclic graph can be generalized to an arbitrary number of nodes.

<figure><img src="image_8.png" /><figcaption>Fig. 5: A graph with $2^3$ paths of growing weight from $e$ to $e_4$.</figcaption></figure>

Now, we can prove that in the worst case, Algorithm 5 may have to visit all paths in $succ^*(e)$. To do so, we have to show that there exist timetables and executions of Algorithm 5 which constraints force considering all paths. The exploration performed by Algorithm 5 is a depth first search, stopped if one encounters an event that is not rescheduled. Assume that the algorithm explores a timetable of the form of the family of graphs represented in Figure 5, and that successors of an event $x$ are selected with growing index number. This allows us to set an ordering $\rho_1, \rho_2, \dots$ for the exploration of paths of the timetable. For a given edge $(x, y, c)$, let $k = \text{FirstPath}(x, y)$ be the index of the first path of the exploration containing edge $(x, y, c)$. Then if $c$ is greater than the highest weight of paths $\rho_1, \dots, \rho_{k-1}$, all events visited after edge $(x, y, c)$ will be rescheduled. This is for instance the case of the weights assigned to the example of Figure 5. Hence, for a given timetable TT, and for the exploration order set by Algorithm 5, there is always an assignment of weights in the timetable that forces exploration of all paths in TT. □

In the worst cases, Algorithm 5 has to visit all paths in $G_{succ} = (succ^*(e), \mapsto \cap(succ^*(e) \times succ^*(e)))$, i.e. has a complexity in $O(2^{n_s-1})$. This is however a coarse approximation of the cost of rescheduling, achieved in a worst case occurring for the family of dense graphs depicted in Figure 5, with the less favorable weights and path exploration scheduling. This cost is expressed as a function of $n_s$, the size of $succ^*(e)$. However, the actual cost of the algorithm is the
cost of visiting all path contained in the set of rescheduled events in $G_{succ}$. So, if we denote by $n_r$ the number of rescheduled events, the cost of this algorithm is in $O(2^{n_r-1})$.

Assumptions on timetables also allow for a refinement of this bound. Let $dg$ be the branching degree in $G_{succ}$, and assume that the rescheduled events are at most at depth $d_{max}$. Then, the cost of Algorithm 5 is in $O(dg^{d_{max}})$. It seems sensible to consider that $dg$ is small, as dependencies among events are mainly due to sequencing of arrival and departures, or to shared resources (tracks, needles) between a train and its successor. In the same way, the maximal length of a path is usually the length of a mission of a train, and hence is likely to be bounded by $n_s/k$, where $k$ is the number of trains. According to our experience, timetables are usually grids of the form of the example of Figure 4. We can hence expect a branching degree of 2, and a complexity in $O(2^{n_s/k})$.

## VI. HEURISTICS IN RECURSIVE PROPAGATION SCHEMES

The recursive scheme shown above is blind, i.e. for each event, we restart a recursive exploration every time a successor of the initially delayed event $e$ is visited and assigned a fresh new date. We may hence visit the same event several times. We can now highlight another property of the critical paths in the rescheduled timetable, and build on this property to update timetables.

**Lemma 2.** Let $e_i \in succ(e)$ be an event such that $D'_p(e_i) = D_p(e_i)$. Then, for every critical path $\rho = e_1.e_2...e_k.f$ containing $e_i$, for every $j > i$, $D'_p(e_j) = D_p(e_j)$.

*Proof.* Path $\rho$ is a critical path. We have two cases. The first one is if event $e_i$ is the first event such that $D'_p(e_i) = D_p(e_i)$, and lemma 1 applies, i.e. for every $j > i$, $D'_p(e_j) = D_p(e_j)$. The second case is if there exists an event $e_l, l < i$ which is the first event such that $D'_p(e_l) = D_p(e_l)$, and from lemma 1, for every $j > l$, $D'_p(e_j) = D_p(e_j)$, and as $i > l$ we can conclude. □

Lemma 2 shows that one can stop exploration of critical paths of $succ^*(e)$ as soon as the date of an event $e_i$ is not updated. Indeed, when exploring a successor of $e_i$ with unchanged date along a path $\rho$ of the timetable, either one stays on a critical path, and for every event $e_{i+k}$ along this path we have $D'_p(e_{i+k}) = D_p(e_{i+k})$ (from Lemma 2), or $\rho$ is not a critical path, and at the end of exploration of $succ^*(e)$, we will have $D'_p(e_k) \ge D'_p(e) + \sum_{j \in i..k-1} \text{dep}(e_j, e_{j+1})$, i.e. either the date of all reached events will either remain unchanged or be computed from the weights accumulated on another (critical) path that differs from $\rho$. This property can be used to guide the exploration of paths in a timetable: assume that $\rho$ is a path from $e$ to $f$ of weight $W_\rho$. This means that $D'_p(f) > D'_p(e) + W_\rho$. Now, if we find another path $\rho'$ from $e$ to $f$, but $W_{\rho'} < W_\rho$, it is clear that $\rho'$ is not a critical path, and an exploration visiting $\rho'$ after $\rho$ will stop at event $f$ in Algorithm 5. Now, as highlighted in the proof of Proposition 6, nothing guarantees that $\rho$ will be explored before $\rho'$. In the following algorithms, we try to force this choice of critical path by maintaining a list of events to visit, weighted by the highest

weight of a path leading from $e$ to each event. We choose at every step to explore a propagation of constraints starting from the event with the maximal weight. We also consider the opposite rule, choosing the event with the minimal weight, and compare the results of both choices in Section VIII.

<caption>**Algorithm 6 Propagation-Latest**</caption>

**Input** : a directed acyclic weighted graph $G = (E, \to)$
an event $e$ and a date $d$
**PQ** := empty priority queue
Add $(e, d)$ to PQ
**while** $PQ \ne \emptyset$ **do**
  $(e_i, W_{e_i})$ = get record with maximal priority from PQ
  $D'_p(e_i) = W_{e_i}$
  **for each** $f \in succ(e_i)$ **do**
    **if** $D'_p(f)$ is defined **then**
      $C_f = D'_p(f)$
    **else**
      $C_f = D_p(f)$
  **end if**
  **end if**
  **if** $W_{e_i} + \text{dep}(e_i, f) > C_f$ **then**
    **if** $(f \in PQ)$ **then**
      **if** $W_{e_i} + \text{dep}(e_i, f) > W_f$ **then**
        Update Priority of $f$ in PQ
      **end if**
    **else**
      Add $(f, W_{e_i} + \text{dep}(e_i, f))$ to PQ
  **end if**
  **end if**
  **end for**
  **end while**

In algorithm 6 above, the choice of the next event to reschedule is guided by the maximal date found so far. An event considered at a step of the algorithm can be put in queue again if one can compute a larger date for it by exploring one of its predecessors.

**Lemma 3.** *Algorithm 6 visits every rescheduled event.*

*Proof.* Every rescheduled event $f$ is at the end of a critical path $\rho = e_1.e_2...e_k.f$ in $succ^*(e)$, where every $e_{i+1}$ is a successor of $e_i$, and $D'_p(e_{i+1}) = D'_p(e_i) + \text{dep}(e_i, e_{i+1})$. Further, using lemma 1, $D'_p(e_{i+1}) > D_p(e_i)$. We hence have $D'_p(e_i) + \text{dep}(e_i, e_{i+1}) > D_p(e_{i+1})$, and if $e_i$ appears in PQ, then so does $e_{i+1}$. The property holds up to event $f$. □

**Lemma 4.** *Algorithm 6 visits only rescheduled event.*

*Proof.* Assume that all dates are correctly computed by the algorithm. Let $f$ be an event of $succ^*(e)$ that needs not be rescheduled. Then, for every predecessor of $f$ that is reached by the algorithm, we have $D_p(f) \ge D'_p(e_i) + \text{dep}(e_i, f)$. So, $f$ is never put in queue and is not rescheduled, even when predecessors of $f$ are put in PQ. □

**Lemma 5.** *At the end of the algorithm, every visited event $f$ has either a new date $D'_p(f) = d + wcp$, where wcp is the weight of a critical path from $e$ to $f$ or its initial date $D_p(f)$;*
**Proof.** Let us assume that an event $f$ is not rescheduled by Algorithm 6. Then its new date is $D'_p(f) = D_p(f)$, as the date of $f$ is never modified by the algorithm (Lemma 3). It hence remains to show that for every rescheduled event $f$, $D'_p(f) = d + wcp$ for some critical path of weight $wcp$. We can proceed by induction on the size of the rescheduled timetable. First, if the considered timetable is of size 1, then the property holds (there is no event to reschedule). Now, let us assume that the property holds up to timetables of size $n$. Let $TT_{n+1}$ be a timetable of size $n+1$, $e_{n+1}$ be a rescheduled event that is maximal w.r.t. $\rightarrow$. The property holds for every rescheduled event in $TT_{n+1} \setminus \{e_{n+1}\}$. As $e_{n+1}$ is rescheduled, we have $D'_p(e_{n+1} = D'_p(e_n) + dep(e_n, e_{n+1})$ for some event $e_n$ that is maximal w.r.t. $\rightarrow$ in $TT_{n+1} \setminus \{e_{n+1}\}$. By induction hypothesis, $D'_p(e_n) = D'_p(e) + wcp_n$, where $wcp_n$ is the weight of a critical path $\rho_n$ from $e$ to $e_n$. So, $D'_p(e_{n+1} = D'_p(e) + wcp_n + dep(e_n, e_{n+1})$, and $\rho_n.e_{n+1}$ is a critical path of weight $wcp_n + dep(e_n, e_{n+1})$. Hence, the property holds for timetables of size $n+1$. $\square$

**Proposition 7.** The new dates of events after application of Algorithm 6 is an ASAP rescheduling of timetable $TT$ after realization of event $e$ at date $d$.

**Proof.** Direct consequence of Lemma 5. $\square$

<figure><img src="image_9.png" /></figure>

Algorithm 6 suffers the same drawback as the blind recursive schemes proposed in section V, i.e., an event (and its successors) can be rescheduled several times, causing useless recursive propagation of secondary delays. Further, the example in the proof of Proposition 6 can be updated to force choosing first the most promising successors of an event that nevertheless leads to exploring path of growing weights, still yielding an exponential worst case complexity. Algorithm 6 can be easily modified to select events with the lowest weight in the priority queue. This algorithm will be called *Propagation - earliest*, but it may also select the worst successor during its exploration, leading to the same exponential worst case complexity. We will show in the next section two examples of timetables where rescheduling cost reaches the worst possible cost.

As one can see, recursive schemes efficiency depends on selection of the most appropriate path/event that will reduce the number of recursion steps needed to propagate delays in the following stages of the algorithm. A random choice of a successor, a choice of a successor with the highest/lowest weight results in similar complexities. In [15], the authors propose an algorithm to reschedule events organized into *buckets*. Each bucket represents a set of events that are rescheduled at the same integral date according to the current calculus of the algorithm. The rescheduling algorithm lets time progress, and studies one bucket at each time stamp. Inside each bucket, events are rescheduled following a total ordering. A minor drawback of the bucket algorithm is that it considers every integral date, as it is only sufficient to move to the date of the next non-empty bucket.

This idea can be adapted to our timetable setting. An important point in the algorithm is that we assume that indexes of events in the timetable are compatible with some topological

order, i.e. given two events $e_i, e_j$, if $e_j \in succ^*(e_i)$, then $j > i$. This can be a property of the timetable satisfied a priori, but one can also compute a (total) topological order for a given timetable, and attach to every event its rank in this ordering. We associate to every event $e_i$ a variable label $l_i = (i, t_i)$, where $i$ is its index and $t_i$ the date computed so far by the delay propagation algorithm. For two labels $l_i = (i, t_i)$, $l_j = (j, t_j)$ we will say that $e_i$ is rescheduled before $e_j$, and write $e_i \ll e_j$ if either $t_i < t_j$, or $t_i = t_j$ and $i < j$. The algorithm below maintains a priority queue ordered w.r.t. the order $\ll$ on events labels. When the date of an event $e_j$ is updated, the priority queue is also updated: If $e_j$ appears in $F$, its place in the queue is modified to keep an ordering that respects order $\ll$ on labels. If $e_j$ does not appear in $F$, it is put at its proper place according to label $l_j$ and order $\ll$ in $F$. Building on this priority queue, the algorithm continuously selects the event that is minimal in the queue (w.r.t. $\ll$) and propagates constraints from the selected event to its successors.

**Algorithm 7** Propagation-DateAndTopologicalID

**Input:** A timetable $TT = (E, D_{init}, D_r, D_p, X)$, with events numbers according to some topological order an event $e_k$, realized at date $d > D_p(e_k)$

$F$: new priority queue containing $e_k$ with label $l_k = (k, d)$

while $F$ is not empty **do**

extract the minimal event $e_i$ with label $(i, d_i)$ from $F$

for each $e_j \in Succ(e_i)$ **do**

if $D'_p(e_j)$ is defined **then**

$$C_j = D'_p(e_j)$$

else

$$C_j = D_p(e_j)$$

end if

if $C_j < d_i + c(e_i, e_j)$ **then**

$$D'_p(e_j) = d_i + c(e_i, e_j)$$

$$l_j = (j, D'_p(e_j))$$

Update $F$ with $e_j$ equipped with label $l_j$

end if

end for

end while

Notice that even with this type of priority for en队eueing events, an event can appear several times in queue with different dates, and hence propagation may still follow several paths leading to an event, and not exclusively critical paths. The major change w.r.t. preceding algorithms is that events with identical dates are sorted w.r.t. a topological ordering, i.e. one cannot visit an event before a predecessor with identical date.

**Proposition 8.** *Algorithm 7 computes an ASAP rescheduling of a timetable in $O(2^{n_r-1})$*

**Proof Sketch.** This proposition can be proved similarly to Proposition 7. Indeed, as the only change w.r.t. Algorithm 6 is the way the priority queue is handled, lemmas 4 and 5 still hold for Algorithm 7. Complexity comes from the number of paths to follow, already computed in Proposition 6. $\square$

<figure><img src="image_10.png" /></figure>
## VII. COMPLEXITIES OF RESCHEDULING ALGORITHMS

In the previous sections, we have introduced three algorithms to propagate primary delays in a timetable. Let us summarize the theoretical complexities of these algorithms. First of all, when an event *e* in a timetable *TT* = {*E*, *D*<sub>init</sub>, *D*<sub>r</sub>, *D*<sub>p</sub>, ↦→, *X*} occurs late, one can notice that the whole timetable does not need to be explored.

Algorithm 4 in section IV builds a topological order on the set of successors of *e*, and then computes the dates of all events in *succ*<sup>*</sup>(*e*) following this order. Events of *TT* outside *succ*<sup>*</sup>(*e*) are not considered. The overall complexity of the algorithms is hence in *O*(*m*<sub>s</sub> + *n*<sub>s</sub>), where *n*<sub>s</sub> is the number of events in *succ*<sup>*</sup>(*e*) and *m*<sub>s</sub> the number of dependencies.

Algorithm 5 in section V explores recursively all paths originating from *e*, and at each step continues exploration if the new dates computed for an event is increased. It visits only paths that contain a rescheduled event. One can notice that the order in which vertices are visited may affect the current planned date *D*'<sub>p</sub>(*f*) of some event visited, and may hence affect the depth and number of paths explored. Consider for example the graph of Figure 6. Let us assume that events *e*, *e*<sub>1</sub>...*e*<sub>6</sub> are respectively scheduled at dates 10, 16, 22, 28, 13, 14, 15, and that event *e* occurs at date 21. If the first path visited is *ρ*<sub>6</sub> = *e*.e*<sub>6</sub>.e*<sub>2</sub>.e*<sub>3</sub> (this is a critical path from *e* to *e*<sub>3</sub>), then we have *D*'<sub>p</sub>(*e*<sub>2</sub>) = 29 and *D*'<sub>p</sub>(*e*<sub>3</sub>) = 30. All other path visited afterward will stop propagation at node *e*<sub>2</sub>. However, the algorithm can first explore path *ρ*<sub>1</sub> = *e*.e*<sub>1</sub>.e*<sub>2</sub>.e*<sub>3</sub>, and set *D*'<sub>p</sub>(*e*<sub>2</sub>) = 23 and set *D*'<sub>p</sub>(*e*<sub>2</sub>) = 24, then path *ρ*<sub>4</sub> = *e*.e*<sub>4</sub>.e*<sub>2</sub>.e*<sub>3</sub>, setting *D*'<sub>p</sub>(*e*<sub>2</sub>) = 25 and *D*'<sub>p</sub>(*e*<sub>2</sub>) = 26, then path *ρ*<sub>5</sub> = *e*.e*<sub>5</sub>.e*<sub>2</sub>.e*<sub>3</sub>, setting *D*'<sub>p</sub>(*e*<sub>2</sub>) = 27 and *D*'<sub>p</sub>(*e*<sub>2</sub>) = 28, and end with path *ρ*<sub>6</sub>. This example shows that Algorithm 5 can explore all paths of a timetable, with an increasing duration at every path, and increasing values for *D*'<sub>p</sub>. This example also shows that selecting earliest successors in Algorithm 6 may lead to the exploration of all paths among the set of rescheduled events in *succ*<sup>*</sup>(*e*). The overall complexity of Algorithm 5 is hence in *O*(2<sup>*n*<sub>r</sub>−1</sup>), where *n*<sub>r</sub> is the number of rescheduled events. The value of *n*<sub>r</sub> is not known a priori, and depends on the timetable, on its buffers, and on the initial delay. Similarly, the example of Figure 7 shows a situation where the date of successors is a bad indication of the cost of paths. In this situation, Algorithm 6, that selects the next event to explore by choosing the event with the highest date will first explore path *e*.e*<sub>5</sub>.e*<sub>2</sub>.e*<sub>3</sub>, then *e*.e*<sub>4</sub>.e*<sub>2</sub>.e*<sub>3</sub>, and last *e*.e*<sub>1</sub>.e*<sub>2</sub>.e*<sub>3</sub> to find the critical path from *e* to event *e*<sub>3</sub>. The modification of the recursive algorithm with heuristics to choose events with latest or earliest dates for the next propagation of delays in Algorithm 6 may still force to explore all paths among rescheduled events, and hence still runs in *O*(2<sup>*n*<sub>r</sub>−1</sup>).

Table II below summarizes the complexities of our algorithms. They do not compare well, as *m*<sub>r</sub>, *m*<sub>s</sub> depend on the shape of the dependency graph in the timetable, on its branching degree, etc. Similarly, we have in general *n*<sub>r</sub> < *n*<sub>s</sub>, but in the worst case, *n*<sub>r</sub> = *n*<sub>s</sub>. In the railway domain, timetables often have the shape of grids, of the form of the example of Figure 4. The reason is that timetables include on one hand an ordering due to train missions (an event precedes

<figure><img src="image_11.png" /><figcaption>Fig. 6: Path exploration in a timetable: a case where choosing earliest successors first may force visiting all paths.</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Fig. 7: Path exploration in a timetable: a case where choosing latest successors first may force visiting all paths.</figcaption></figure>

the next departure/arrival in the same trip), and on the other hand dependencies due to resources allocations and safety (an event precedes another similar event at the same location in the next trip). In such graphs, the restriction to a set of nodes of size *n* yields a projected graph of with at most 2·*n* edges. Assuming a length of trips *l* and a number of missions *k*, the maximal length of a path in a set of nodes is *l* + *k*. The rightmost column of Table II bounds the worst case complexity in a (*l* × *k*) grid when *n*<sub>s</sub> = *n*<sub>r</sub> = *k*·*l*.

<table><caption>TABLE II: Complexities of rescheduling algorithms</caption><thead><tr><th>Algorithm</th><th>Complexity</th><th>in a (l × k) Grid</th></tr></thead><tbody><tr><td>Topological Order<br>Algo. 2</td><td>O(m<sub>s</sub> + n<sub>s</sub>)<br>Prop. 4</td><td>O(3.(l·k))</td></tr><tr><td>Nested Recursive<br>Algo. 5</td><td>O(2<sup>n<sub>r</sub>−1</sup>)<br>Prop. 6</td><td>O(2<sup>(l+k)−1</sup>)</td></tr><tr><td>Priority Queue Latest date<br>Algo. 6</td><td>O(2<sup>n<sub>r</sub>−1</sup>)<br>Prop. 6</td><td>O(2<sup>(l+k)−1</sup>)</td></tr><tr><td>Priority Queue Earliest date<br>Algo. 6 (variant)</td><td>O(2<sup>n<sub>r</sub>−1</sup>)<br>Prop. 6</td><td>O(2<sup>(l+k)−1</sup>)</td></tr><tr><td>Priority Queue + Topological<br>Algo. 7</td><td>O(2<sup>n<sub>r</sub>−1</sup>)<br>Prop. 8</td><td>O(2<sup>(l+k)−1</sup>)</td></tr></tbody></table>

## VIII. CASE STUDIES

The worst case theoretical complexities shown in Section VII are difficult to compare. Exploring paths in a recursive way may seem a bad idea a priori, but if the set of rescheduled events is small, this solution might perform an ASAP rescheduling more efficiently than an algorithm requiring a topological ordering on all successors of a late event. It may even be the case that recursive schemes perform better when timetables impose little dependencies among distinct trips. To complete the theoretical study of our algorithms, we perform experiments on models and timetables of existing metro systems.
We have evaluated the impact of rescheduling algorithms with the help of a simulator tailored for the evaluation of traffic management in metro systems, namely the MOCHY tool [19]. In a nutshell, MOCHY accepts as input a model of a metro network designed with a variant of time Petri nets, and a timetable. Runs of the model maintain in parallel the current state of the system (positions and speed of trains,...), simulated delays due to incidents or normal variations in trip durations, and update the timetable accordingly to handle delays. The timetable is also used to plan departures of trains from stations. A run of a model with a given timetable is hence a way to execute a timetable (according to the semantics given in Section II) with realistic dates and delays originating from a description of the metro network. The results shown below give the duration of simulation campaigns involving several runs of a metro system, and the total time spent by each algorithm to reschedule events during these simulations. In the rest of this section, we consider two types of scenarios for two different types of networks and timetables.

### A. First experimentation: The metro of Montreal

The results shown in this section were obtained with a model of the metro network in Montreal, equipped with a timetable denoted $TT_M$ in the rest of the section. The timetable was built from open data description a whole day of train operations for Montreal's network [25].

The timetable $TT_M$ is composed of three independent subgraphs, one per metro line in the network. In these timetables, some have no successors, but most of events have a single successor. The reason is that this timetable is mainly a collection of trip descriptions. The timetable $TT_M$ describes operations in the network for a time span of 20 hours. It starts at 5h00 and stops at 1h00. $TT_M$ contains 29946 events and 29.922 dependencies.

$TT_M$ contains a set $D_{dwell}$ of dependencies which imposes constraints between an event $e_1$ representing an arrival at a station and another event $e_2$ representing a departure from the same station. We have:

$$ \forall (e_1, e_2, c) \in D_{dwell}, \quad D_{init}(e_2) - D_{init}(e_1) = 20 \\ \text{and } c = 20 $$

More intuitively, the planned duration between an arrival and a departure is 20 seconds. At each train stop represented by a pair of events $e_1$ and $e_2$, if the dwell time exceeds 20s, then the event $e_2$ is delayed, and this primary delay will necessarily be propagated from $e_2$ to its successors in $TT_M$.

Table III shows the results for the simulation of operations of the Montreal network with timetable $TT_M$. We have evaluated the impact of rescheduling algorithms in two delay scenarios. For each scenario, and for each rescheduling algorithm, we measure the total time needed to play 100 simulations of the whole timetable including randomized delays, and the average time spent by the algorithm in rescheduling tasks.

**Scenario 1** studies rescheduling in the context of major incidents. It is a scenario where long delays slow down the whole network. However, these delay occur with a low frequency. We simulate 10 minutes delays occurring every

two hours at each station between 7:00AM up to 5:10PM. Delays occur on the three lines of the network, i.e. on the three different sub-timetables of $TT_M$.

**Scenario 2** studies rescheduling in the context of minor but frequent incidents (e.g. due to passengers misbehaviors). This scenario implements frequent but small delays for a long period of time. It simulates random delays occurring at each station in the whole network. These delays apply to departures of trains only, i.e. they change the date of one event over two. The random duration of dwell time is sampled with a Gaussian law, within interval [20s, 30s], the distribution is $N(\mu = \frac{20+30}{2}, \sigma^2 = \frac{30-20}{2})$.

To make sure that the differences between performances of the rescheduling algorithms are not consequences of our samples, we make another round of tests with **Scenario 3**. Scenario 3 is a replay of randomly sampled delays, containing 100 runs sampled according to Scenario 2. The simulation time reported in Table III is rather indicative, as it includes the time needed to resets timetable $TT_M$ for a new simulation, the time needed to parse and process delay files, plus the time spend by the algorithm for the delay propagation in $TT_M$.

<table><caption>TABLE III: Rescheduling durations for the metro network of Montreal.</caption><thead><tr><th rowspan="2">Algorithm</th><th colspan="2">Scenario 1</th><th colspan="2">Scenario 2</th><th colspan="2">Scenario 3</th></tr><tr><th>Rescheduling time</th><th>Simulation time</th><th>Rescheduling time</th><th>Simulation time</th><th>Rescheduling time</th><th>Simulation time</th></tr></thead><tbody><tr><td>Topological Order Algo. 2</td><td>8min 32s</td><td>16min 37s</td><td>10min 24s</td><td>18min 30s</td><td>3min 51s</td><td>3min 55s</td></tr><tr><td>Nested Recursive Algo. 5</td><td>0s 660ms</td><td>8min 3s</td><td>0s 938ms</td><td>8min 3s</td><td>0s 380ms</td><td>3s 377ms</td></tr><tr><td>Propagation Latest Algo. 6</td><td>0s 543ms</td><td>8min 4s</td><td>1s 238ms</td><td>7min 58s</td><td>0s 435ms</td><td>3s 887ms</td></tr><tr><td>Propagation Earliest Algo. 6 (variant)</td><td>0s 512ms</td><td>8min 11s</td><td>0s 918ms</td><td>8min 44s</td><td>0s 478ms</td><td>3s 505ms</td></tr><tr><td>Date-Id Topological Propagation Algo. 7</td><td>0s 611ms</td><td>8min 54s</td><td>1s 156ms</td><td>8min 51s</td><td>0s 446ms</td><td>3s 433ms</td></tr></tbody></table>

### B. Second experimentation: Metro Line A in Rennes.

This section shows results of an experimentation with a model for the line A of the subway of Rennes. The model uses a timetable $TT_R$ that depicts events on a single metro line during 4 hours of operation. The timetable contains 3078 events and 5249 dependencies, and has a grid-like shape. Figure 8 shows an excerpt of the timetable $TT_R$. The time elapsed between two consecutive events for the same metro is 0.5 minutes and the constraint adding dependencies between events for different metros is set to 0.4 minutes. The time buffer between two consecutive events of the same metro is 6 seconds. With this setting, we have measured the effect of rescheduling on two scenarios. As the timetable and the model are smaller than for Montreal's network, we have tested these scenarios on 1000 runs for each scenario and each algorithm. The results of our simulations are shown in Table IV.
<figure><img src="image_13.png" /><figcaption>Fig. 8: An excerpt from the timetable $TT_R$ used for scheduling metros in Rennes.</figcaption></figure>

**Scenario 1** simulates repetitive failures at a given station. It creates incidents every 30 minutes, i.e. impose a delay of 3 minutes during 3 minutes to each departure event occurring at a particular station. This scenario is tested on a sample of 1000 runs. This scenario simulates 4 hours of operation on Line A of the metro in Rennes, and creates incidents at the second station from the beginning of the line. Notice that within this setting, a 3 minutes failure period may cause more than one primary delay (several departures can be delayed during the 3 minutes due to track occupation constraints), or conversely cause no delay (for instance if this failure occurs during off-peak hours). We can now give the results obtained during the simulation. First, the number of failures periods appearing during the simulation is 8. These failures have caused 10 primary delays, which duration ranged between 0.29 and 2.90 minutes. The sum of all primary delays imposed during simulation was 22.19 minutes, The total time needed to recover from these delays was 109.59 minutes and required rescheduling of 216 events. In other words, the average time needed to recover from a primary delay was 10.95 minutes, and the average number of events before recovery 21.

**Scenario 2** introduces shorter delay with the same setting: delays are of 1 minute instead of 3 minutes. In this scenario, one expects faster recovery with ASAP rescheduling. As for the first scenario, the number of failures created is 8. However, these failures have caused less trouble, and resulted in 3 primary delays, which durations were close to 0.89 minutes. The sum of all primary delays imposed during simulation was 2.69 minutes, the total time needed to recover from these delays was 14.6 minutes and required rescheduling of 29 events. In other words, the average time needed to recover from a delay was 4.86 minutes, and the average number of events before recovery 9.

### C. Analysis of results

Before discussing the results of our experimentation, let us highlight that the time needed for ASAP rescheduling seems negligible w.r.t. the total operation time simulated in our experiment. Indeed, the case study of Montreal involves a timetable with 29946 events and a duration of 20 hours. The total amount of time required by rescheduling is at most 10 minutes in the less favorable case, and in general less than 1 second. The case study of Rennes with 4 hours of operation and 3078 events in its timetable shows similar performance of ASAS rescheduling algorithms. As this rescheduling is applied on real timetables, we believe that they can be used online in a real environment, even when decisions have to be taken in a few seconds.

<table><caption>TABLE IV: Rescheduling durations for the metro line A in Rennes.</caption><thead><tr><th rowspan="2">Algorithm</th><th colspan="2">Scenario 1</th><th colspan="2">Scenario 2</th></tr><tr><th>Rescheduling time</th><th>Simulation time</th><th>Rescheduling time</th><th>Simulation time</th></tr></thead><tbody><tr><td>Topological Order Algo. 2</td><td>1s 448ms</td><td>22s 975ms</td><td>1s 351ms</td><td>24s 567ms</td></tr><tr><td>Nested Recursive Algo. 5</td><td>0s 57ms</td><td>21s 0ms</td><td>0s 20ms</td><td>20s 739ms</td></tr><tr><td>Propagation Latest Algo. 6</td><td>0s 87ms</td><td>21s 909ms</td><td>0s 29ms</td><td>21s 208ms</td></tr><tr><td>Propagation Earliest Algo. 6 (variant)</td><td>0s 120ms</td><td>20s 335ms</td><td>0s 16ms</td><td>19s 376ms</td></tr><tr><td>Date-ID Topological Propagation Algo. 7</td><td>0s 54ms</td><td>22s 434ms</td><td>0s 21ms</td><td>20s 772ms</td></tr></tbody></table>

From the experimentation, we can draw the following conclusions: first, in all situations, Algorithm 2 building on topological ordering needs more time than algorithm 5 (Recursive delay propagation) and Algorithm 6 (recursive propagation with latest event chosen from a priority queue) to reschedule events. The reason is that buffers allow for recovery in a few events, and hence, during most of simulations, $n_r$ is much smaller than $n_s$. On all examples, Algorithm 5 and Algorithm 6 perform well, with comparable complexities. So, in practice, recursive solutions do not need a time exponentially greater than a priori polynomial algorithms. One can immediately deduce that all paths among the successors of an event are not explored. A possible explanation is that timetables are often organized as sequences of missions, and that the critical path to an event must often be a path following a single mission. Further, buffers between two events belonging to different missions can be large. If the critical paths from the primarily delayed event to its successors are rapidly found during propagation of a delay in a recursive scheme, then other paths are not explored. This hypothesis is strengthened by our example of Figure 6 showing that the order in the exploration of path has an impact on the number of propagation steps.

The results shown in Table III and IV have been obtained via simulation of real case studies. Even if these simulation use abstract models of metro networks, we think that the evaluations of the costs of rescheduling algorithms are close to the costs that could be observed in real life network operation, because the algorithms did not rely on any characteristics of the simulation environment to perform their propagation, and because the timetable used in the study were real timetables.

## IX. RELATED WORK

In this section, we compare our approach with former works that deal either with timetable calculus, optimization or rescheduling. As our paper mainly deals with rescheduling, we will not emphasize on works that address construction of timetables or on their robustness. We will rather focus on works that handle unspecified delays or trips, and on different
models and techniques that have been used in the past to represent schedules. We refer interested readers to [6] for a survey on timetabling. We do not claim for exhaustiveness, and refer readers to [5], [13] for surveys on rescheduling.

A first work to mention is the series of paper on scheduling based on the *alternative graph model* (see for instance [12]). An alternative graph is a dynamic schedule model close to the model depicted in section II, but where dependencies can be changed. Some arcs are simple dependencies given by weighted arcs as in our Definition 1. Other constraints are pairs of arcs ((e, e'); (f, f')) meaning that either *e* precedes *e'*, or *f* precedes *f'*. A timetable is obtained by choosing one arc per alternative, in such a way that the obtained graph is acyclic, and by assigning to events realization dates that satisfy all constraints on edges. This variability allows for optimization of schedules while handling conflicts in parts of a network such as forks and joins. However, selection of alternatives in graphs introduces combinatorics. Optimal (re)scheduling can be rapidly bought back to a Mixed Integer Linear programming (MILP) problem [21], and calls for dedicated algorithms (e.g. Branch and Bound [10] or Tabu search [8]) to find an efficient schedule. A close model called disjunctive graph is proposed by [3]. The graph is a task scheduling graph, where edges represent dependencies among trains operations. The model also contains pairs of arcs capturing exclusive dependencies due to scheduling of trains on a given section of the network. This framework model is used to insert additional trains into existing timetables. A new schedule is obtained either by computing an optimal timetable as a solution of a job shop scheduling problem, or with an approximate solution obtained with a simulated annealing algorithm.

A close problem is considered in [4]. Operators a re given a timetable $T_1$, specifying visited stations, dates of arrivals and departures, and an additional set $T_2$ of trips from an origin to a destination, modeling freight trains. The problem addressed is to find an optimal schedule for trains in $T_2$ while leaving $T_1$ unchanged. It is solved as an Integer Linear Programming problem using a Lagragian heuristic.

In [15], the author propose a ($\max$, +) framework to repre-
sent timetables and address propagation of delays. The setting
considered is a discrete event representation that define regular
behaviors in timetables. A set of events (departures, arrivals
and events depicting resources usage) is repeated with a fixed
period $T$. Dependencies among event dates are constraints
of the form $x_i(k) \ge a_{ij} + x_j(k)$, specifying that the $k^{th}$
occurrence of event $i$ occurs at least $a_{ij}$ time units after the $k^{th}$
occurrence of event $j$, or of the form $x_i(k) \ge a_{ij} + x_j(k-l)$,
to address dependencies between events of different periods
($l$ is bounded by some constant). These dependencies can
be captured either by matrices, or by marked precedence
graphs (a variant of weighted graph). Within this setting,
the propagation of a set of delays is performed iteratively
by exploring the set of delayed events and maintaining their
latest date. During exploration, events with identical dates are
grouped into "buckets". The next event to consider is the first
event according to topological order in the earliest non-empty
bucket. This algorithm is close to the solution used in our
Algorithm 7.

In [14], the problem addressed is also a rescheduling
question, but the rescheduling objective is to minimize energy
consumption rather than mitigating the effects of a primary
delay. To this extent, the author proposes to synchronize
departures and braking phases of close trains in order to
benefit from energy saving allowed by regenerative braking.
The timetable model is given as a set of constraints among
events dates, and the objective function is to minimize the
integration of instant power demand during a day of operation.
The rescheduling allows only modification of dwell times in
station. The author uses greedy heuristics algorithms in a
setting where energy consumption is evaluated via a non-linear
approximation technique.

In [7], the objective is to reduce the waiting time of passen-
gers in case of a sudden increase in the demand. There is no
explicit timetable, but rather a regular schedule of departures,
and planned speeds/dwell times along track segments, which
allow to compute the arrival and departure dates of trains. To
answer a sudden increase in transport demand, the authors
propose to use additional trains that are allowed to skip some
stops in stations, hence speeding up the arrival date at stations
with high demand. Traffic management strategies are also
allowed to speed up turns at the end of lines, to increase trains
speed and to reduce dwell times. The overall system is given
as a set of constraints over all variables representing speeds,
dwell times, etc. with an objective to minimize. It is solved
using CPLEX. The authors then suggest that a good strategy
to minimize the time needed to adsorb the demand peak is to
minimize the arrival time of the last train launched for each
origin-destination pair affected by the peak.

In [17], [16], the authors consider propagation of delays in
timetables. Delays are modeled as a stochastic distribution,
and the possible dates of events are captured by a symbolic
representation (polyhedras) representing possible distributions
of delays due to time constraints once a primary delay has
occurred. This setting is then used to perform stochastic
simulation, and assess robustness of timetables.

A more recent trend is to use reinforcement learning to
address rescheduling. [24] proposes to train a standard Q-
learning algorithm with a simulator. In the considered setting,
states consider trains location, blocks availability, and a dis-
cretized time. The learned function associates a quality value
to two possible actions: setting signals to red to force trains to
wait, or green to allow them to move to the next block. The
reward function at each time step is the negation of delays,
i.e. rewards are low if trains are late. The learning approach
allows rescheduling of trains order, which is not considered
in most traffic management settings. Notice however that the
framework in [24] does not propose to reschedule a timetable,
but rather to use it as a reference to compute a reward for a
learning algorithm.

X. CONCLUSION

In this work, we have considered several algorithms for the
rescheduling of events in a timetable upon occurrence of a
primary delay. We have considered algorithms that minimize
the discrepancies w.r.t. the original timetable, and shown that
the best updated schedule was an unique schedule planning
events occurrence at the earliest possible dates meeting time
constraints imposed by the timetable (ASAP rescheduling).
The first rescheduling algorithm considered relies on weights
of critical paths in the timetable, but it is clearly inefficient.
The second algorithm considers one event after the other,
following a topological ordering. It allows to compute the
earliest possible date of each event once, and only after the
dates of its predecessors. The complexity of this algorithm
is polynomial in the number of successors of the event
causing the primary delay. The last algorithms considered
use recursive schemes to propagate delays and constraints
among events. They converge to the ASAP rescheduling of
a timetable, but may recompute new dates of events several
times. Several variants are proposed: blind recursive schemes,
propagation of delays starting with events with the latest (resp.
earliest) date first, recursive schemes that consider both earliest
date and topological ordering to choose the next event to
reschedule. In the worst cases, all these variants may have to
visit all paths going through the set of rescheduled events,
yielding an exponential cost in the number of rescheduled
events. Though this family of algorithms seems less efficient
than the polynomial algorithm, in practice recursive schemes
exhibit good performances. The algorithms were tested on
timetables originating from real case studies (the metro of
Montreal and the Metro of Rennes). In all cases, the time
spent for rescheduling after delays seems negligible (a total
of few seconds in most cases) w.r.t. the duration of the period
simulated (several hours to a whole operation day).

In a future work, we plan to extend rescheduling to handle
different objectives, and different traffic management strate-
gies. Indeed, ASAP rescheduling considers that the original
timetable is an optimal schedule and tries to adhere to this
schedule, without changing composition of trains fleets, their
ordering at forks, etc. Adherence to an original timetable is
evaluated as the sum of all differences between planned and
rescheduled dates, but there are other criteria to evaluate the
quality of a rescheduling. For instance, one might want to
preserve the amount of energy needed to realize a schedule: in
this setting, reducing dwell time is acceptable, but increasing
trains speed might increase energy consumption. One can
also allow for the use of spare trains parked at the end of
a line, change priorities of trains at needles, etc. This results
in a rescheduling that modifies the number of events and the
dependencies in timetables, and calls for different algorithms.
Last, we want to consider traffic management schemes that
impose less constraints than a timetable, and are guided by
more global objectives such as regularity of service at some
points in the network, or adequacy between transport offer and
the number of passengers.

REFERENCES

[1] Richard Bellman. Network flow theory. *Santa Monica, California: RAND Corporation*, page 923, 1956.

[2] Richard Bellman. On a routing problem. *Quart. Appl. Math.*, 16:87-90, 1958.

[3] R.L. Burdett and E. Kozan. Techniques for inserting additional trains into existing timetables. *Transportation Research Part B: Methodological*, 43(8):821-836, 2009.

[4] Valentina Cacchiani, Alberto Caprara, and Paolo Toth. Scheduling extra freight trains on railway networks. *Transportation Research Part B: Methodological*, 44(2):215-231, 2010.

[5] Valentina Cacchiani, Dennis Huisman, Martin Kidd, Leo Kroon, Paolo Toth, Lucas Veelenturf, and Joris Wagenaar. An overview of recovery models and algorithms for real-time railway rescheduling. *Transportation Research Part B: Methodological*, 63:15-37, 2014.

[6] Valentina Cacchiani and Paolo Toth. Nominal and robust train timetabling problems. *European Journal of Operational Research*, 219(3):727-737, 2012.

[7] David Canca, Eva Barrena, Alejandro Zarzo, Francisco Ortega, and Encarnación Algaba. Optimal train reallocation strategies under service disruptions. *Procedia - Social and Behavioral Sciences*, 54:402-413, 2012. Proceedings of EWGT2012 - 15th Meeting of the EURO Working Group on Transportation, September 2012, Paris.

[8] Francesco Corman, Andrea D'Ariano, Dario Pacciarelli, and Marco Pranzo. A tabu search algorithm for rerouting trains during rail operations. *Transportation Research Part B: Methodological*, 44(1):175-192, 2010.

[9] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. *Introduction to Algorithms*. The MIT Press, 2nd edition, 2001.

[10] Andrea D'Ariano, Dario Pacciarelli, and Marco Pranzo. A branch and bound algorithm for scheduling trains in a railway network. *Eur. J. Oper. Res.*, 183(2):643-657, 2007.

[11] E.W. Dijkstra. A note on two problems in connexion with graphs. *Numerische Mathematik*, 1:269-271, 1959.

[12] Andrea D'Ariano, Dario Pacciarelli, and Marco Pranzo. Assessment of flexible timetables in real-time traffic management of a railway bottleneck. *Transportation Research Part C: Emerging Technologies*, 16(2):232-245, 2008.

[13] Wei Fang, Shengxiang Yang, and Xin Yao. A survey on problem models and solution approaches to rescheduling in railway networks. *IEEE Transactions on Intelligent Transportation Systems*, 16(6):2997-3016, 2015.

[14] David Fournier. *Metro Regenerative Braking Energy Optimization through Rescheduling: Mathematical Model and Greedy Heuristics Compared to MILP and CMA-ES*. PhD thesis, UNIVERSITÉ PARIS DIDEROT, 2014.

[15] Rob M.P. Goverde. A delay propagation algorithm for large-scale railway traffic networks. *Transportation Research Part C: Emerging Technologies*, 18(3):269-287, 2010. 11th IFAC Symposium: The Role of Control.

[16] Rebecca Haehn. *Optimisation and Analysis of Railway Timetables under Consideration of Uncertainties*. PhD thesis, Aachen University, 2022.

[17] Rebecca Haehn, Erika Ábrahám, and Niklas Kotowski. Acceleration techniques for symbolic simulation of railway timetables. In *Simon Collart Dutilleul, Anne E. Haxthausen, and Thierry Lecomte, editors, Proc. of RSSRail'22*, volume 13294 of *Lecture Notes in Computer Science*, pages 46-62, 2022.

[18] Saeed Hasanzadeh, Seyed Fariborz Zarei, and Ehsan Najafi. A train scheduling for energy optimization: Tehran metro system as a case study. *IEEE Transactions on Intelligent Transportation Systems*, 24(1):357-366, 2023.

[19] Loïc Hélouët and Antoine Thébault. Mochy : A tool for the modeling of concurrent hybrid systems. In Luis Gomes and Robert Lorenz, editors, *Application and Theory of Petri Nets and Concurrency*, pages 205-216. Springer Nature Switzerland, 2023.

[20] International Association of Public Transports (UITP). Metro service performance indicators. https://www uitp org, 2011.

[21] Paola Pellegrini, Grégory Marlière, Raffaele Pesenti, and Joaquin Rodriguez. Recife-milp: An effective milp-based heuristic for the real-time railway traffic management problem. *IEEE Transactions on Intelligent Transportation Systems*, 16:1-11, 10 2015.

[22] M. Peña-Alcaraz, A. Fernández, A.P. Cucala, A. Ramos, and R.R. Pecharromán. Optimal underground timetable design based on power flow for maximizing the use of regenerative-braking energy. *Proceedings of the Institution of Mechanical Engineers, Part F: Journal of Rail and Rapid Transit*, 226:397-408, 2012.

[23] Robert Sedgewick and Kevin Wayne. *Algorithms (Fourth edition deluxe)*. Addison-Wesley, 2016.

[24] Darja Semrov, R. Marsetic, Marijan Zura, Ljupco Todorovski, and Aleksander Srdic. Reinforcement learning approach for train rescheduling on a single-track railway. *Transportation Research Part B Methodological*, 86:250-267, 04 2016.

[25] STM. STM Developpers section. https://www.stm.info/en/about/developers, 2023. [Online; accessed 30-November-2023].