A dynamic decomposition approach for the
real-time Railway Trac Management Problem

M. Petrisa,∗ , F. Naldinib , P. Pellegrinic and R. Pesentid
a Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 CRIStAL, F-59000 Lille, France
matteo.petris@inria.fr
b COSYS-ESTAS, Univ Gustave Eiel, IFSTTAR, Univ Lille, F-59650 Villeneuve d'Ascq,
Francefederico.naldini@univ-eiel.fr
c COSYS-LEOST, Univ Gustave Eiel, IFSTTAR, Univ Lille, F-59650 Villeneuve d'Ascq,
Francepaola.pellegrini@univ-eiel.fr
d Department of Management, Università Ca' Foscari Venezia, Cannaregio 873, 30121 Venice,Italypesenti@unive.it∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island
March 21, 2022

Keywords: railway trac management, real-time scheduling, problem decomposition.

1 INTRODUCTION
Railway services are operated following a predened timetable. However, their execution is often
perturbed by unexpected events that make this timetable infeasible. Delay caused by these events
is named primary delay, and it implies that trains occupy tracks at times that are dierent fromthe planned one. Depending on trac and track layout, these late occupations may bring toconicts, in which at least one train must slow down or even stop to preserve safe separation.
This slowing down generates secondary delay, which may quickly propagate in the network.
Dispatchers can take actions to limit delay propagation, as train rerouting and rescheduling. They mostly do so manually. Several optimization approaches have been proposed in theliterature to tackle this problem and support dispatchers (Cacchiani et al., 2014). This problem is named real-time Railway Trac Management Problem (rtRTMP). The great majorityof the existing approaches either focus on geographically limited infrastructures represented microscopically (D'Ariano & Pranzo, 2008, Törnquist Krasemann, 2012, Pellegrini et al., 2015), or
merge some microscopic aspect to a macroscopic representation to deal with large infrastructures(Lamorgese & Mannino, 2015). One of the main challenges of the microscopic based approaches
is their computational performance on large-scale networks. To deal with this challenge, few
papers try to coordinate trac management decisions made on several microscopic parts of infrastructures (Corman et al., 2012), or on a somehow obtained decomposition of the overall
problem. For example, (Luan et al., 2020) presents various approaches to dene decompositions
a priori and to force the various trac management decisions to be coherent. A rather dierent
problem conception is proposed by (Van Thielen et al., 2018): the decomposition of the problem
changes with trac evolution. Specically, the paper denes an algorithm based on the so-called
TRISTAN XI Symposium

Original abstract submittal

M. Petris, F. Naldini, P. Pellegrini and R. Pesenti

2

dynamic impact zone. As soon as a conict is detected, rst rerouting possibilities for the two
involved trains are assessed. If no rerouting possibility exists to eliminate conicts, the further
conicts that will be generated by the possible resolutions of the considered one are identied
and included in the dynamic impact zone. The conict resolution is then decided by assessing its
consequence in terms of delay propagation in the dynamic impact zone if rst-come-rst-served
is applied.

In this work, we propose a neighborhood-based trac management algorithm, following tosome extent the problem conception of (Van Thielen et al., 2018). We model the infrastructure
microscopically. Our algorithm consists in making asynchronous trac management decisions.
Asynchronous decisions are made also in (Dal Sasso et al., 2021), where train movements are
split in so called temporal ticks to assess the presence of deadlocks in a single track networkwith passing loops. In our case, these decisions allow trains to reach their destination aiming at
the minimization of delay propagation. Specically, we identify the neighborhood of a reference
train whenever a decision is to be made on its route or on the precedence with respect to anothertrain. This neighborhood includes only the trains that may use track sections in common with thereference one, in the vicinity of the latter's current location and in the very near future. Trac isthen managed by applying an optimization approach as the one by (Pellegrini et al., 2015), only
considering trains in the neighborhood and the identied possibly common track sections. By
doing so, alternative routes are taken into account, but they are as short as possible. This allows
limiting the size of the instance and hence the optimization time. Moreover, whenever possible,
it avoids making decisions that may have to be modied in the future, when the neighborhood
is recomputed. However, routes must be long enough to guarantee that no deadlocks occur
right out of the neighborhood due to the decisions made here. The algorithm starts identifying
the concerned trains and their shortest but long enough routes. Then, it follows the principlethat has proved to be successful in (Pellegrini et al., 2015), simultaneously optimizing routes
and schedules. We theoretically show that, in networks with some specic characteristics, thisalgorithm guarantees the achievement of a deadlock-free network-level solution, if it exists.

2 MODELING PRINCIPLESWe denote by BS and T C the set of block sections and track-circuits composing the infrastructure, respectively. We consider a set T of n trains traveling in the network. They may
use dierent routes to reach their nal destination: the set of the available routes for train t isdenoted by Rt . A train makes a decision upon alternative routes once it has reserved the block
section where the switch that gives rise to the alternatives is located. We call route decision block
section (RDBS) a block section where such decision is to be made: in a three-aspect system,
it is the block section such that a further one exists between it and the block section including
the switch. Given a route r ∈ Rt , a sub-route rbs→bs′ of r is the sequence of block sections of rfrom bs to bs′ , where bs and bs′ are block sections of r such that bs has to be traversed before
bs′ when traveling along r. To indicate that a sub-route is available for train t, we will write
rbs→bs′ ⊆ r ∈ Rt . Moreover, given a subset of routes R′ ∈ R and a subset of block sections
BS ′ ∈ BS , we denote by Ext(R′ , BS ′ ) the set of block sections composing sub-routes rbs→bs′ ⊆ r,r ∈ R′ , where bs ∈ BS ′ and bs′ ∈ BS \ BS ′ is the next RDBS on r. As an example, consider
Figure 1: let R′ contain routes r′ and r′′ and BS ′ the block sections up to the one identied by
the pair of signals s1 and s2. Set Ext(R′ , BS ′ ) includes all the block sections along r′ until the
RDBS identied by s3 and s4 and those along r′′ until the RDBS identied by s5 and s6.
TRISTAN XI Symposium

Original abstract submittal

M. Petris, F. Naldini, P. Pellegrini and R. Pesenti

3

Figure 1  Graphical representation of relevant sets of block sections: round brackets show set BS ′ , curly
brackets indicate set Ext(R′ , BS ′ ) for train t having routes r′ and r′′ available.

We describe railway trac as a discrete event system. Events occur at the latest times atwhich route or precedence decisions must be made. They are the situations in which a train must
exit a RDBS. Hereinafter, with a little abuse of notation, when we write time k we understandthe time instant of the occurrence of event k. The state of the network at time k = 0, 1, 2, . . . isidentied by: (i) the vector p(k) = [pt (k) : t ∈ T ] of the positions of all trains, that is the last
block section reserved by t; (ii) the set Y (k) = {yt,t′ ,tc (k) : t, t′ ∈ T, tc ∈ T C} of the precedences
previously dened and, hence, in force between times k − 1 and k, on common track-circuits.
Specically, a value yt,t′ ,tc ∈ Y (k) is set equal to 1 (respectively to 0) if train t is planned to use
tc before (respectively after) train t′ . If no precedence has been xed yet, yt,t′ ,tc is undened. At
a certain time k̄, the system is in its nal state if all the trains reserved or crossed their naldestination.
To conclude the section, let us introduce some sets of block sections that will be exploitedin our algorithm (Section 3). Given the state of the system at time k, let St (k) be the set ofblock sections that must be considered in the trac management decisions involving train t.
These are the block sections claimed by t at k. They are the ones that t may use betweenpt (k) and further RDBSs. Given St (k) and a route r ∈ Rt such that pt (k) ∈ r, we denotebs(r, St (k)) the last block section in St (k) that t encounters when traveling along r. We denoteby Rt (k) = {r ∈ Rt : pt (k) ∈ r} the set of routes available for t at k and by BS(St (k)) the setof all bs(r, St (k)). For example, in Figure 1, position pt (k) of t is the block section identiedby signals s1 and s2. Assuming St (k) contains all block sections shown in the gure, including
those derived by the extension discussed there, then Rt (k) = {r′ , r′′ }. Here, bs(r′ , St (k)) andbs(r′′ , St (k)) are, respectively, the ones identied by pairs of signals (s3, s4) and (s5, s6).

3 SOLUTION ALGORITHM
The algorithm is based on a dynamic decomposition of the problem. Specically, at time k,
train t for which decisions are to be made is identied. Its neighborhood is dened and thertRTMP is locally solved by iteratively calling the optimization algorithm RECIFE-MILP. The
neighborhood constitutes a sub-instance of the overall problem. A sub-instance is dened by apair (Qt (k), S(k)), where Qt (k) ⊆ T is a subset of trains and S(k) ⊆ BS is the subset of block
sections claimed by the trains in Qt (k), i.e., those along which they may travel.
The procedure to determine a short-term strategy, i.e., a local solution to manage trac when
event k is triggered for train t is outlined in Algorithm 1. To lighten the notation, we drop the
dependency on k when possible. In the initialization phase the algorithm takes a snapshop of theentire network. Given the positions of all trains t′ ∈ T , it determines sets St′ of block sections
claimed by t′ (lines 2- 4). Subset of trains Qt is set to be equal to the singleton containing t.
Each iteration starts with a call to function Sub-instance_generating_procedure, wheresome easy extensions of sub-instance (Qt , S) are performed in order to avoid trivially infeasible
iterations (line 7). For example, trains in T \ Qt sharing claimed block sections with trains in Qt
are included in Qt . Then, we call RECIFE-MILP to determine a short-term strategy ST S for
sub-instance (Qt , S) (line 8). The set of previously established precedences Y (k) is also given as
input to RECIFE-MILP. If a non-empty short-term strategy ST S is found, the algorithm stops
and returns ST S (line 13). Otherwise, we try to further extend the sub-routes of some trains
TRISTAN XI Symposium

Original abstract submittal

M. Petris, F. Naldini, P. Pellegrini and R. Pesenti

4

Algorithm 1: Short-term_strategy_generating_procedure
Data: State (p(k), Y (k)) at time k , a train t
Result: ST S
1 begin′2
foreach t ∈ T do
3
St′ := {pt′ (k)};4
if pt′ (k) is not RDBS then St′ ← St′ ∪ Ext(Rt′ (k), BS(St′ ));S
5
set Qt := {t}, S :=t′ ∈Qt St′ and ST S := ∅;6
while ST S = ∅ do
7
(Qt , S) := Sub-instance_generating_procedure(Qt , S);
8
ST S :=RECIFE-MILP(Qt , S, Y (k));
9if ST S = ∅ then10
select Q̃ ⊆ Qt : Ext(Rt′ (k), BS(St′ )) ̸= ∅ ∀t ∈ Q̃ ;11
if Q̃ = ∅ then return FAIL;′
12
foreach t ∈ Q̃ do St′ ← St′ ∪ Ext(Rt′ (k), BS(St′ ));13

return ST S ;(lines 10- 12). If an extension is possible we start the next iteration. Otherwise, the algorithm
stops and we return failure. We observe that in the worst-case scenario the sub-instance may be
extended to consider the entire network and all the trains travelling on it.
Finally, this algorithm enjoys an important property if the network of interest can be modeled
as a series-parallel graph (Dun, 1965):
Theorem 1 The algorithm always allows to reach the nal state of the railway trac system on
a network that can be modeled as a series-parallel graph, if at all possible.

In the paper, we will formally prove the validity of this theorem and we will provide a proof-ofconcept of the applicability of the algorithm.

References
Cacchiani, Valentina, Huisman, Dennis, Kidd, Martin, Kroon, Leo, Toth, Paolo, Veelenturf, Lucas, & Wagenaar, Joris. 2014. An overview of recovery models and algorithms for real-time railway rescheduling.
Transportation Research Part B: Methodological, 63(may), 1537.
Corman, Francesco, D'Ariano, Andrea, Pacciarelli, Dario, & Pranzo, Marco. 2012. Optimal inter-areacoordination of train rescheduling decisions. Transportation Research Part E: Logistics and Transportation Review, 48(1), 7188.
Dal Sasso, Veronica, Lamorgese, Leonardo, Mannino, Carlo, Onofri, Andrea, & Ventura, Paolo. 2021.
The Tick Formulation for deadlock detection and avoidance in railways trac control. Journal of RailTransport Planning & Management, 17, 100239.
D'Ariano, Andrea, & Pranzo, Marco. 2008. An Advanced Real-Time Train Dispatching System for
Minimizing the Propagation of Delays in a Dispatching Area Under Severe Disturbances. Networks
and Spatial Economics, 9(1), 6384.
Dun, Richard J. 1965. Topology of series-parallel networks. Journal of Mathematical Analysis andApplications, 10(2), 303318.
Lamorgese, L., & Mannino, C. 2015. An Exact Decomposition Approach for the Real-Time Train Dispatching Problem. Operations Research, 63(1), 4864.
Luan, X., De Schutter, B., Meng, L., & Corman, F. 2020. Decomposition and distributed optimizationof real-time trac management for large-scale railway networks. Transportation Research Part B:
Methodological, 141, 72  97.
Pellegrini, Paola, Marliere, Gregory, Pesenti, Raaele, & Rodriguez, Joaquin. 2015. RECIFE-MILP:
An Eective MILP-Based Heuristic for the Real-Time Railway Trac Management Problem. IEEE
Transactions on Intelligent Transportation Systems, 16(5), 26092619.
Törnquist Krasemann, Johanna. 2012. Design of an eective algorithm for fast response to the rescheduling of railway trac during disturbances. Transportation Research Part C: Emerging Technologies, 20(1), 6278.
Van Thielen, S., Corman, F., & Vansteenwegen, P. 2018. Considering a dynamic impact zone for real-time
railway trac management. Transportation Research Part B: Methodological, 111, 39  59.

TRISTAN XI Symposium

Original abstract submittal