Risk evaluation of a real-time Railway Traffic Management
solution under uncertain dwell times
C. Melonia , M. Pranzob , M. Samàc,∗a Sapienza University of Rome, Department of Computer, Control and Management

Engineering "Antonio Ruberti" (DIAG), Roma, Italy
carlo.meloni@uniroma1.it
b University of Siena, DIISM, Siena, Italy
marco.pranzo@unisi.it
c Roma Tre University, Department of Engineering, Roma, Italy
marcella.sama@uniroma3.it∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium onTransportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius IslandApril 4, 2022
Keywords: Train rescheduling, CVaR, Dwell times, Uncertainty, Activity Networks1INTRODUCTION

The real-time Railway Traffic Management Problem (rtRTMP) is the problem of detecting andsolving time overlapping conflicting requests done by multiple trains on the same track resourcesin order to compute a new plan of operations (Cacchiani et al., 2014). Typically, the rtRTMP ismodelled as a deterministic problem and requires to be solved in a short computation time. Assuch, both the structural and numerical model elements are often assumed to be fixed and known
in advance. However, uncertainty may still affect the computed plans and their expected quality,
since operation times may vary due to a change in a dynamic environment. This work proposesa new approach to evaluate the risk of delays associated to an rtRTMP solution when operation
times are uncertain and only an interval representation of them is known to the scheduler.
Among the operating times we focus on the so called dwell times, which represent the amountof time spent by trains on a platform to allow passengers boarding/alighting. They have beenshown in the literature to have a significant effect on network capacity and are recognized as oneof the main source of uncertainty (Larsen et al., 2014), over which the operators may have little
or no control and influence. The design, test, and implementation of advanced mathematicalmodels is a prerequisite to the development of innovative decision support systems for solving
the rtRTMP (Borndörfer et al., 2017, Pellegrini et al., 2019). Following this path, this work
considers the possible uncertainties that may affect a solution for rtRTMP, and proposes a new
method to compute a measure of the risk of delays.
In fact, the reliability of a scheduling solution is important for dispatchers to make informed
decisions, especially when operating in real-time. A tool able to quantify the risk associated to aschedule should offer a practical support to decision-makers, especially a tool that evaluates thedelay risks of a schedule taking advantage of a real-time forecasting of dwell times, assuming thatthey are represented by prediction intervals (Kecman & Goverde, 2015). The decision makers
may be risk-averse and may prefer solutions that do not just perform well “on average", but that
also perform satisfactorily “in most cases".
TRISTAN XI Symposium

Original abstract submittal

C. Meloni, M. Pranzo and M. Samà

2Adopting a coherent risk measure is a way of modeling risk in scheduling problems. To
this aim, a popular coherent risk measure is the Expected Shortfall (ES) or Conditional-Valueat-Risk (CVaR) (e.g., see (Bertsimas et al., 2004, Meloni & Pranzo, 2020, Sarin et al., 2014))
which measures the average loss in the worst (1 − α)100% of outcomes, with α ∈ [0, 1]. This
loss can represent a delay in railway transport services. This type of risk measure emphasizes
the contribution of the worst-case outcomes under the index performance of interest. CVaRα isrecommended when a decision maker is not only concerned with the frequency of undesirable
outcomes, but also with their severity (Bertsimas et al., 2004, Sarin et al., 2014).
In this work we propose an approach that deals with the evaluation of the CVaR for the delay
associated to rtRTMP solutions when the practical realization of the integer valued duration ofoperations are uncertain at the scheduling stage and may take any value within a given interval(i.e., between a lower and an upper bound obtained from an available prediction system) (Meloni& Pranzo, 2020). More precisely, we consider real-time uncertainty limited to dwell times andaddress the evaluation of the CVaR associated to a feasible schedule exploiting a graph model
representation of the problem to take advantage of a real-time information collection system. To
this aim, extending the approach recently proposed by (Meloni et al., 2021) for more generalactivity networks, we develop and test a suitable computational method to evaluate the CVaRof the delay of a given rtRTMP solution. The proposed method enables the use of this risk index
as evaluation criterion for different railway scheduling approaches.

2METHODOLOGY

We propose a risk aware rtRTMP solution framework as a computational tool for solving thertRTMP and assessing the risk in terms of possible delays associated with the obtained solutions
on the basis of the information received from a dwell time prediction system. The rationale isto provide, through the proposed framework, the dispatcher with a restricted pool of rtRTMP
solutions for their final choice and approval in view of the actual implementation.
Firstly, the framework receives as input an instance of rtRTMP which is solved through adeterministic scheduler on the basis of available nominal data, corresponding to the minimum
duration values. In our computational analysis, we model the rtRTMP as Job Shop Scheduling
Problem using the Alternative Graph model and considering as objective function the minimization of the maximum delay Md introduced in the plan by scheduling decisions. We then solve
the rtRTMP using AGLibrary, a state-of-the-art optimization solver that deals with complex
routing and scheduling problems (D’Ariano et al., 2007, Samà et al., 2017). The solver continues
providing further rtRTMP solutions until a stopping criteria is reached. In our implementation,
the stopping criteria is either the rtRTMP solution optimality, or the reaching of the maximum
allowed computation time.
Each time a new rtRTMP solution is found, it is translated into a corresponding temporal
activity network with integer interval-valued durations (IIN) (Meloni & Pranzo, 2020) whichincludes the independent dwell times prediction intervals. Specifically, an IIN can be described by
the pair (G′ , D), where G′ is a directed network of r activities, and D = (D1 , . . . , Dr ) is a vectorof independent integer interval durations associated with the r activities. The considered network
is directed, connected, and acyclic with single source and sink nodes. Interval activity integers
times Tp = [ap , ap ] for p = 1, . . . , r are assigned to the activity durations D = (D1 , . . . , Dr )representing their specific number of time units, with ap and ap integers, and ap ≤ ap for all p.
When a duration value of an activity p is known with certainty, we have the deterministic caserepresented by an interval Tp where ap = ap . We observe that, even if this study focuses on thedwell time uncertainties, this modeling solution is quite general and can be used to representinterval-valued uncertainties associated with all the arcs in G′ .
The IINs have an intrinsically discrete nature, and for a given IIN network Q the uncertainperformance measure Md is finite and bounded keeping values in [Md , Md ], where the optimistic
TRISTAN XI Symposium

Original abstract submittal

C. Meloni, M. Pranzo and M. Samà3value Md (the pessimistic value Md ) refers to the configurations of Q in which all durations areat their minimum (maximum) value. The finite length Γ (in terms of number of integers) of thetime interval [Md , Md ] represents a measure of the amount of uncertainty of the IIN. The CVaR
at probability level α of Md in the IIN is adopted as risk measure, and it is finite and boundedholding the following: Md ≤ CVaRα (Md ) ≤ Md , ∀α ∈ [0, 1].
The IIN forms the input of the framework module devoted to the risk delay evaluation which
is based on the CVaRα (Md ) index. As for this risk measure, one or more probability levels α
may be chosen by the dispatchers to represent different distributions of the effects of (possible)
extreme realizations. Higher values of α are of interest for risk-averse decision makers, while
α = 0 can be associated with the risk-neutral behavior. In fact, when selecting values of αtending to 1 the CVaRα (Md ) tends to the pessimistic case Md ; whereas for values of α tending
to 0, CVaRα (Md ) tends to the expected value E(Md ) of the adopted delay index.
All rtRTMP solutions found by the solver are processed for risk delay assessment then arecollected and analyzed in a solution archive that can be further exploited in order to identify arestricted pool of preferable solutions, e.g., adopting some additional criteria. This allows thedispatchers to be aware of quality and risk of a feasible solution and thus to choose the one thatsolves the trade-off between performance level and the risk measures they are most comfortable
with, possibly also in consideration of company protocols or risk regulations.

3RESULTS

To show how the risk aware rtRTMP solution works, we consider an example instance basedon the railway network around the central station of Utrecht (NL), the busiest station in theNetherlands. Of the 140 existing dwell time constraints, 50% randomly chosen are affected byuncertainty. Specifically, we assume as deterministic duration for each dwell time its minimumvalue. For each dwell time arc p affected by uncertainty, its interval duration is Tp = [ap , ap ],where ap = δap , and with δ ∈ {1.25, 1.50, 1.75, 2.00} to gradually represent the severity of theuncertainty. The time unit adopted is 1 second. Regarding the probability levels for the CVaR
assessment, three different values are used, i.e., α ∈ {0.99, 0.95, 0.90}, meaning the assessmentof the average of Md for the worst 1%, 5%, and 10% cases. The solver found 6 feasible solutions
for the example instance, taking 0.2 seconds, with an optimal solution value of Md∗ = 105 s. A
total of 72 risk evaluations was carried out for all solutions found. The risk assessment takes
0.24 s on average.
α1.25

0.99

0.95

1.50

0.90

1.75

2.00

CVaR(Md)

240

200

160

120

140

160

180120140160180120140160

180

120

140

160

180

Md

Figure 1 – Example instance with 50% of uncertain dwell times and δ ∈ {1.25, 1.50, 1.75, 2.00}.
Figure 1 shows the risk analysis for all feasible solutions found on the 4 uncertain scenarios.
Each scenario has a dedicated plot, labeled with the related δ value. The x-axis represents
TRISTAN XI Symposium

Original abstract submittal

C. Meloni, M. Pranzo and M. Samà4the maximum delay value Md associated with the deterministic solution found. The y-axis
represents the risk evaluation of a feasible solution with respect to the uncertainty affecting it,i.e. the CVaRα (Md ) index, in terms of how much the solution may worsen. We represent in thesame plot the evaluations made with different α values using a colored cross symbol as reported
in the legend on top. In a given scenario, considering probability levels α1 ≤ α2 , for a feasible
solution CVaRα1 (Md ) ≤ CVaRα2 (Md ) holds. The bold vertical axis at x = 105 indicates thevalue of the deterministic optimal solution.
This analysis allows the decision maker to easily identify (if any) the presence of feasible
solutions with better risk profiles than the optimal deterministic solution. For example, in thescenario with the lowest level of uncertainty (δ = 1.25) there are no such cases. While, as thelevel of uncertainty increases, various alternative solutions are revealed. Here, two types of cases
are visible. The first one represent solutions that offer a better risk profile, yet having a worse
deterministic value. In the figure this is shown by the crosses that are not on the bold verticalline, i.e., the Md deterministic optimal value, but have lower values of CVaR. These cases callthe decision maker to resolve a trade-off. The second case, on the other hand, happens whenmore than one solution exists with optimal deterministic value, though they differ for their riskprofiles, as clearly visible for δ = 1.75 and δ = 2.00, where on the bold vertical line two solutions
with the same optimal value but different CVaR are visible. The dominant one is preferable.
As the degree of uncertainty increases, solutions show a different risk profile which also tends
to vary more significantly on the basis of the α levels. In these cases, the decision maker’s risk
attitude becomes relevant.

References
Bertsimas D, Lauprete GJ, Samarov A, (2004) Shortfall as a risk measure: properties, optimization and applications. Journal of Economic Dynamics & Control, 28 (7), 1353—1382.
Borndörfer R, Klug T, Lamorgese L, Mannino C, Reuther M, Schlechte T, (2017) Recent successstories on integrated optimization of railway systems. Transportation Research Part C, 74 (1),196–211.
Cacchiani V, Huisman D, Kidd M, Kroon L, Toth P, Veelenturf L, Wagenaar J, (2014) An
overview of recovery models and algorithms for real-time railway rescheduling. Transportation
Research Part B, 63 (1), 15–37.
D’Ariano A, Pacciarelli D, Pranzo M, (2007) A branch and bound algorithm for scheduling trains
in a railway network. European Journ of Operational Research, 183 (2), 643–657.
Kecman P, Goverde RMP, (2015) Predictive modelling of running and dwell times in railway
traffic. Public Transport: Planning and Operations, 7 (1), 295–319.
Larsen R, Pranzo M, D’Ariano A, Corman F, Pacciarelli D, (2014) Susceptibility of Optimal Train
Schedules to Stochastic Disturbances of Process Times. Flexible Services and Manufacturing
Journal, 26 (4), 466–489.
Meloni C, Pranzo M, (2020) Expected shortfall for the makespan in activity networks underimperfect information. Flexible Services and Manufacturing Journal, 32, 668-692.
Meloni C, Pranzo M, Samá M, (2020) Risk of delay evaluation in real-time train scheduling withuncertain dwell times. Transportation Research Part E, 152, 102366.
Pellegrini P, Pesenti R, Rodriguez J, (2019) Efficient train re-routing and rescheduling: Validinequalities and reformulation of RECIFE-MILP. Transportation Research Part B, 120 (1),33-48.
Samà M, D’Ariano A, Corman F, Pacciarelli D, (2017) A variable neighbourhood search for fasttrain scheduling and routing during disturbed railway traffic situations. Computer & Operation
Research, 78 (1), 480–499.
Sarin SC, Sherali HD, Liao L, (2014) Minimizing conditional-value-at-risk for stochastic scheduling problems. Journal of Scheduling, 17 (1), 5–15.

TRISTAN XI Symposium

Original abstract submittal