Generalization of the train routing selection problem forreal-time traffic management
B. Pascariua,∗ , M. Samàa , P. Pellegrinib , A. D’Arianoa , J. Rodriguezc , D. Pacciarelliaa Roma Tre University, Department of Engineering, Rome, Italy

bianca.pascariu@uniroma3.it, marcella.sama@uniroma3.it, andrea.dariano@uniroma3.it,dario.pacciarelli@uniroma3.it
b Univ. Lille Nord de France, Ifsttar, COSYS, LEOST, Villeneuve d’Ascq, Lille, France
paola.pellegrini@univ-eiffel.fr;
c Univ. Lille Nord de France, Ifsttar, COSYS, ESTAS, Villeneuve d’Ascq, Lille, Francejoaquin.rodriguez@univ-eiffel.fr∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium onTransportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

Keywords: Rail Transportation, Train Scheduling and Routing, Disturbance management, Alternative graph

1INTRODUCTION

In recent years, European and international transport policies have strongly promoted the shift
to railway transport system, due to sustainable, environmental and energy issues. The resulting
increase in railway market share is accompanied by a significant challenge: the need to guarantee
an adequate level of service in terms of train punctuality.
Typically, rail operations are regulated by a fixed timetable, which defines the train passingorders, the arrival and departure times of trains in stations and their route across the network.
During real-time operations, unpredictable events may cause timetable perturbations, which canlead to train conflicts, i.e., the simultaneous utilization of the same infrastructure section(s). Dispatchers are required to quickly detect new conflicts arising during operations and take actions
to recover them by retiming, reordering and rerouting trains in such a way that the timetable
perturbation is minimized. This problem is known in literature as the real-time Railway Traffic
Management Problem (rtRTMP). Several models and algorithms have been developed to solve
the problem to provide Decision Support Systems to help dispatchers take more informed decisions (Borndörfer et al., 2017). Still, the rtRTMP is NP-hard (Mascis & Pacciarelli, 2002):
solving the entire problem involves a high computational effort in large instances. However,
the real-time nature of the problem requires very short computational times. Simplifying thertRTMP is thus a key aspect to achieve high quality solutions in the available computation times.
Some approaches limit the size of the problem by intervening on the granularity used tomodel the infrastructures and the traffic flows (Lamorgese & Mannino, 2015), or focus on theresolution process to properly drive the search of good solutions (Pellegrini et al., 2015, Samàet al., 2017). Others limit the number of variables by considering only what they perceive to be
the most significant ones (Van Thielen et al., 2018). Often, rerouting variables are the ones mostaffecting the size of the rtRTMP search space, thus some works fix the routes in the timetable
as the only option, concentrating on the pure scheduling problem, while others use subsets ofTRISTAN XI Symposium

Original abstract submittal

B. Pascariu et al.

2

all the possible alternatives available, which are either based on guidelines set by infrastructure
managers, or chosen because considered the ones that will probably lead to the best quality
solutions.
The need for a systematic study on the routing selection has lead to the definition by Samàet al. (2016) of the Train Routing Selection Problem (TRSP). The TRSP consists in identify
promising alternative routes for each train in advance, which are then used in the rtRTMP as
the set of the only possible alternative routes. In the TRSP, the benefit of using specific subsetsof routes in the rtRTMP is approximated. This is assessed by considering estimations of costs due
to conflict occurrence and scheduling decisions. The validity of the TRSP and the impact of its
solution on the rtRTMP have been analyzed in the literature. The analysis has been performedby using a specific mixed-integer linear programming (MILP) formulation (Pellegrini et al., 2014)
and the RECIFE-MILP solution approach for the rtRTMP (Pellegrini et al., 2015). RECIFEMILP is a decision support tool developed at IFSTTAR, considering as objective function theminimization of the total train delay.
This paper proposes the generalisation of the TRSP for a different rtRTMP approach which
has a different model, objective function and solution approach than RECIFE-MILP. The aim
is to extend the validity of the TRSP and assess its general effectiveness for the rtRTMP. Weconsider for the rtRTMP the decision support system AGLibrary (Samà et al., 2017), developedat Roma Tre University, which solves an alternative graph model (Mascis & Pacciarelli, 2002)of the problem to minimize the maximum train delay. We analyze how changes in the rtRTMP
model and objective function have to be reflected on the TRSP one and/or on the estimationof costs, and how this may be achieved. The computational analysis is performed on a French
infrastructure: the line around the city of Rouen.

2METHODOLOGY

We consider the rtRTMP microscopically modelled using the alternative graph formulation (Mascis & Pacciarelli, 2002): the rtRTMP is considered as a job shop scheduling problem with flexible
routes and additional practical constraints. The rtRTMP is solved via AGLibrary (Samà et al.,2017), a decision support tool developed at Roma Tre University, which minimizes the maximum train delay. AGLibrary uses an iterative meta-heuristic approach for the rtRTMP. At
each iteration a scheduling solution is computed for the rtRTMP and then analyzed to evaluate
which rerouting action may transfer train on less congested routes, thus leading to better qualitysolutions, until a maximum computation time is reached or a solution with no delay is found.
In our approach, an optimized pre-processing phase is used to limit the number of routing
variables in the rtRTMP. This pre-process requires solving the TRSP, and consists in selecting
a feasible and optimized subset of alternative routes for each train. The route selection is basedon costs associated to scheduling decision impact, in terms of train conflicts. The TRSP solution
is given as input to the rtRTMP to reduce its search space and to provide better solutions.
The TRSP is modelled on a construction graph G = (V, E), for which an example is given
in Figure 1. Each vertex vi ∈ V represents an available train routing for a train. Each edgeeij ∈ E connects two vertices belonging to different trains if the associated routings satisfy
possibly existing rolling stock reutilization constraints between the two trains. Such graph isk-partite and each partition Vt ⊂ V represents all the available alternative routings for a given
train t = 1...k. Costs are associated to vertices and edges as an estimation of the influence ofchoosing a particular routing on its own or in combination with another one on the final qualityof the rtRTMP solution. Solving the TRSP translates into finding a certain number of minimum
cost k-vertex cliques, where k indicates the number of total trains considered. A clique is aclassical concept in graph theory defined as a subset of adjacent vertices. We propose alternative
ways of computing the cost of a clique, in order to evaluate how changes in the rtRTMP objectivefunction should be reflected on the TRSP.
TRISTAN XI Symposium

Original abstract submittal

B. Pascariu et al.

3Figure 1 – Example of a construction graph G = (V, E)
We solve the TRSP using an evolution of the algorithm in Samà et al. (2016), based on Ant
Colony Optimization (ACO) (Dorigo et al., 1996), a meta-heuristic inspired by the foraging
behaviour of ant colonies. For the TRSP, at each iteration the ants of the colony incrementallybuild cliques on the construction graph. The probability of selecting a vertex is computed via
the random proportional rule, using pheromone trails and heuristic information. The pheromone
trails represent historical information on the quality of the already visited solutions including
the vertex in exam. The heuristic information is a greedy measure of the achievable quality ofthe solution when such vertex is added.

3RESULTS

The proposed TRSP-rtRTMP approach is tested on a French case study based on real-world
data. It is the 27-km-long railway line around the city of Rouen, shown in Figure 2. The line ismainly on double-track with several intermediate stations, each with up to six platforms. The infrastructure is composed of 190 track-circuits, 189 block sections, and 11347 routes. On average,
there are 13 trains per hour, and 62 routing alternatives per train. A train can have a maximumof 192 routing alternatives. We generated 100 instances of 60-minute time window randomly
taken during the traffic peak-hours, considering multiple perturbed timetables. Timetable perturbations represent train entrance delays in the infrastructure. We perform the experiments on
an Intel Xeon 22 core 2.2 GHz processor with 1.5 TB RAM, under Windows distribution.
OisselSt. Etienne du Rouvray

Sotteville

Darnetal

Rouen-Rive-Droite

MarommeMalaunay

Le Havre

ParisSaint Lazare
Serqueux

Figure 2 – Rouen networkWe summarize the benefit of solving the rtTRSP in terms of the performance obtained forthe rtRTMP in Table 1. Specifically, we report the average objective value obtained by using
AGLibrary when minimizing the maximum train delay for the rtRTMP and the average computation time at which the best solution is found. We compare two different approaches used tosolve the TRSP in order to generate the input for the solution of the rtRTMP:• ACO-TRSP: A TRSP solution with p routing alternatives for each train is computed by
the ACO-TRSP algorithm with a time limit of 30 seconds. This TRSP solution is given
as an input for the solution of the rtRTMP by AGLibrary. A computation time limit of150 seconds is set for the rtRTMP. The best ACO-TRSP routing for each train is set as
its default routing alternative;
TRISTAN XI Symposium

Original abstract submittal

B. Pascariu et al.

4• ALL ROUTINGS: All routing alternatives are given as input to AGLibrary. A computation time limit of 180 seconds is set. The timetable routing is set as the default routing
alternative for each train.
The numerical results shows that ACO-TRSP is able to select high quality train route combinations which enforce the objective function of the AGLibrary solver: the rtRTMP objective values
improve by 25%. Furthermore, ACO-TRSP allows the computation of the best quality solution
in a much shorter computation time compared to AGLibrary with all routings.
Table 1 – Average AGLibrary-rtRTMP objective valueApproach
ACO-TRSPALL ROUTINGS

p
10
2030
50
70192

Obj. value (s)
82.9
81.5
80.6
80.8
81.0
106.5

Time best (s)
1.3
4.8
6.3
6.0
3.7
90.0

Future research will be dedicated to apply our methodology to other rail infrastructures, withdifferent characteristics from those presented here. Furthermore, other exact or meta-heuristic
methods for the TRSP could be designed and compared.

References
Borndörfer, R., Klug, T., Lamorgese, L., Mannino, C., Reuther, M., Schlechte, T., 2017. Recent
success stories on integrated optimization of railway systems. Transportation Research Part C,74, 196–211.
Caimi, G., Fuchsberger, M., Laumanns, M., Lüthi, M., 2012. A model predictive control approach for discrete-time rescheduling in complex central railway station approach. Computers& Operations Research, 39 (11), 2578–2593.
Dorigo, M., Maniezzo, V. and Colorni, A., 1996. Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics),
26(1),29–41.
Lamorgese, L., Mannino, C., 2015. An exact decomposition approach for the real-time Train
Dispatching problem. Operations Research, 63 (1), pp. 48–64
Mascis, A., Pacciarelli, D., 2002. Job shop scheduling with blocking and no-wait constraints.
European Journal of Operational Research, , 143 (3), 498–517.
Pellegrini, P., Marlière, G., Rodriguez, J., 2014. Optimal train routing and scheduling for managing traffic perturbations in complex junctions. Transportation Research Part B, 59 (1), 58–80.
Pellegrini, P., Marlière, G., Pesenti, R., Rodriguez, J., 2015. RECIFE-MILP: An effective MILPbased heuristic for the real-time railway traffic management problem. IEEE Trans. on Intelligent Transportation Systems, , 16 (5), 2609–2619.
Samà, M., Pellegrini, P., D’Ariano, A., Rodriguez, J., Pacciarelli, D., 2016. Ant colony optimization for the real-time train routing selection problem. Transportation Research Part B, 85 (1),89–108.
Samà, M., D’Ariano, A., Corman, F., Pacciarelli, D. 2017a. A variable neighbourhood search
for fast train scheduling and routing during disturbed railway traffic situations. Computers &Operations Research, 78, 480–499.
Van Thielen, S., Corman, F., Vansteenwegen, P., 2018. Considering a dynamic impact zone forreal-time railway traffic management. Transportation Research Part B, 111 (1), 39–59.
TRISTAN XI Symposium

Original abstract submittal