Global Sensitivity Analysis Applied to Traffic Rescheduling in Case of Power Shortage

The problem of railway traffic rescheduling in the case of an undesirable event is becoming more and more important as traffic increases. Events such as bad weather, technical failures or accidents may cause a disturbance or a disruption, depending on their influence on the railway system. Disturbances are defined as small perturbations of the timetable and happen when a single train delay affects a large number of trains due to cascade effects, but does not require rolling stock or crew duty reorganization. In contrast, disruptions are large perturbations due to infrastructure or rolling stock failures that significantly influence the train operations on the railway network. Disturbance and disruption management are currently active research areas in operations research.

Until recently, most research about train rescheduling was dealing with disturbances and delay management [1–7]. Consequently, the literature that has addressed the subject of timetable adjustment during disruptions is limited. Most often, authors discuss the impact of the unavailability of one or several tracks during a certain time. A complete blockade corresponds to the situation in which all tracks of a certain segment are blocked, which prevents any trains to circulate on this segment. In the case of a partial blockade, only some of the tracks are blocked and limited traffic is still possible. In Ref. [8], authors consider the problem of rescheduling timetable in case of a partial and a complete blockade. They propose integer programming formulations, where the rescheduling actions are delaying trains, cancelling trains and reversing trains at stations adjacent to the blockade. The method is applied to a small two-line network in the Netherlands. In Ref. [9], the same type of method and network are considered and the authors focus on short-turning management in the case of total blockade to minimize the total weighted train delay and the number of cancelled trains, whereas in Ref. [10], authors consider a high-speed line in China, with a complete blockade but no reversing train action. In previous works, the cost to minimize mixes train delays and cancellation. The paper [11] develops a mixed-integer linear programing model that detects and resolves conflicts in the case of a single-track bidirectional line, with a complete temporary blockage. Disrupted trains are rescheduled in both directions of the line, with the objective of minimizing the total delay of all trains. In Refs [12] and [13], the overall passenger disutility is added to the operational costs. An adaptive large neighbourhood search meta-heuristic is proposed for faster rescheduling and multi-objective optimization including: deviation from the undisrupted timetable, low operational cost and acceptable passenger service [14] deals with real-time train rescheduling in case of a network with several lines. A mixed-integer programming model is formulated to reschedule trains by retiming, reordering, cancelling and rerouting trains. The readers can refer to Ref. [15] for an overview of recovery models and algorithms for real-time railway disturbance and disruption management. For in-depth reviews of this literature, we refer to Refs. [16] and [17] for recent surveys on train timetabling problems.

The present work addresses train traffic disruption due to an electrical infrastructure failure, for example a feeding substation which out of order. In such a case, the electric power available for moving the trains is reduced and the traffic needs to be adapted: less trains can travel at the same time, and they may have to be slowed down. This can be handled by rescheduling variables such as train delays, but also speed profiles. The problem requires a microscopic model in order to compute the interaction between the traffic and the electrical network and to determine which traffic can be supplied. This numerical model is complex and non-linear, which prevents the use of linear programing. When searching the literature, we did not find any paper dealing with this type of problem. We propose a method based on global sensitivity analysis and Monte Carlo filtering in order to rank the influence of the decision variables while accounting for various operational constraints. Our rescheduling methodology introduces a strategy that will help the decision-maker to choose an optimal solution according to various criteria for reorganization the railway traffic.

The article is organized as follows. Section 2 describes the problem with more details; Section 3 introduces global sensitivity analysis and presents how the method is applied to traffic rescheduling; Section 4 provides first results in a simple case and Section 5 concludes.

The electrical infrastructure of a railway network is designed and controlled so as to provide the power needed by the trains. It is a complex system, in which the main elements are the feeding substations, the catenaries, the rails (return conductor) and the trains. Other devices allow to configure the electrical network’s topology according to the needs. Numerous trains travel at the same time on different lines, and the analysis of the system relies on simulation.

In the present work, we use ESMERALDA NG [18], a simulator developed by the SNCF. This simulator is based on a multi-physical model of the railway network: mechanical, electrical and thermal. The input data are the physical description of the railway network on one hand (topology, position and characteristics of all devices, including the trains) and the description of the intended traffic on the other hand (type of trains, departure and passage times at various points and reference speed profiles along the way). The equations of train dynamics are coupled with the circuit equations of the electrical network and solved step by step over time in order to determine the position of the different trains at each time, as well as different electrical quantities such as the voltage at the pantographs, powers passing through catenaries and transformers and the resulting heating (Fig. 1). It is a non-linear numerical model with a large number of inputs and outputs. The computation cost is high, with a large number of variables involved and simulation times are typically around 10 minutes.

The simulator calculates the actual traffic, for a given physical infrastructure and traffic instructions. For example, trains are scheduled to leave at given times and travel according to a certain speed profile. If the power supply is too weak, the train traction power is automatically reduced. From a technical point of view, the quality of power distribution is monitored through the catenary voltage: a too small value indicates that the electrical network is overloaded and requires the traffic to be adapted according to the power supply capacity.

If a component of the electrical infrastructure is unavailable, due to either a technical incident or a maintenance operation, the power available for traction is reduced. It is then necessary to check if the residual capacity allows to maintain the traffic initially planned. The criterion is the catenary voltage, which must remain within the range defined by the standards. If not, the train traffic must be rescheduled.

In the current situation, traffic rescheduling is carried out according to an iterative trialand- error method: on the basis of their experience, operators propose replanning solutions and run simulation to check if the catenary voltage remains within the prescribed limits. This process is slow because the analysed situation is complex (many trains, many lines) and numerous simulation runs are needed. Furthermore, the outcome of the process, in terms of both quality of the solution and time to reach it, fully depends on the operator experience and know-how. There is no guarantee that an optimal solution will be reached.

The goal of the presented work is to assist the operator in the rescheduling process, thanks to sensitivity analysis. Sensitivity analysis is used for a better understanding of the problem and answers questions as follows: (i) which adjustment operation is the most influential? (ii) How does a given input variable affect the output? (iii) Which traffic adjustments are needed to reschedule the traffic while respecting operational constraints?

We propose a global stochastic sensitivity analysis, associated with Monte Carlo filtering, in order to efficiently explore the decision space and build a set of acceptable solutions. ‘Acceptable solutions’ means traffic grids that respect all the operational constraints of the system. Sensitivity indicators are calculated in order to quantify the influence of the different traffic grid parameters (decision variables) on the traffic. In addition, the set of acceptable solutions is processed in order to build a practical Pareto front according to criteria defined by the traffic operator and guide him for the choice of the final solution.

Traffic rescheduling requires to adjust the traffic grid according to the actual power feeding capacity of the railway system: less train can circulate in a given time frame on a given line and/or their speed must be reduced. To do this, a set of decision variables must be defined, such as time and/or space intervals between trains or speed limits at particular points of the lines. Each point of the decision variables space corresponds to a particular traffic grid. The traffic operator uses simulation in order to explore the decision space and find the points which correspond to acceptable solutions, in the sense that they respect all physical and operational constraints of the system; then the operator has to choose which points are the best ones, with respect to different performance criteria.

The numerical simulator, ESMERALDA NG, is based on a dynamic non-linear electromechanical model. All train motions are computed step-by-step over time, along with other quantities such as train pantograph voltages, catenary currents and engine temperatures. All these quantities constitute the simulator outputs, and the operator must verify that they meet the various operational constraints they are subjected to. In the rescheduling process, the simulator is used as a black box in order to find inputs which result in acceptable outputs, in the sense that they meet the operational constraints.

The numerical model is a highly non-linear one, has a large number of variables (tens of trains traveling during hours), and is computationally expensive (typically around 10 minutes for a real case simulation). Hence, a rational procedure is needed in order to obtain as much information as possible about the relationships between the model inputs and outputs, at the lowest computation cost. Global stochastic sensitivity analysis is a possible approach to this type of problem, and the rest of this section explains how it is applied to traffic rescheduling.

Sensitivity analysis is the process of varying the input parameters of a model and observing the resulting output variations. It is used to explore how the model output variations can be qualitatively and quantitatively attributed to the different input variations.

While local sensitivity analysis considers variability stemming from input variations around a specific point, global sensitivity analysis considers input variations within their entire feasibility range. In this article, we will consider global sensitivity analysis, in order to explore the whole decision space. Three so-called ‘settings’ are commonly defined in order to quantify the input importance [19]:

• Factor prioritization aims at ranking the inputs in terms of their relative contribution to the output variability;

• Factor fixing aims at determining which inputs, if any, do not have any contribution to the output variability;

• Factor mapping aims at determining which part of the inputs space produces outputs in a specific region, for instance above a prescribed threshold.

Factor prioritization and factor fixing are linked settings: the second one focuses on inputs that have so little influence that they can be fixed and dropped in order to simplify the model. Factor mapping is a more difficult concept, dealing with model inversion and useful to handle output constraints. In the present work, we use Sobol sensitivity indexes for factor prioritization and factor fixing (Section 3.3). Factor mapping is handled, thanks to Monte Carlo filtering and empirical cumulative density functions (Section 3.4).

Sobol’s method is a variance-based sensitivity analysis that determines the contribution of each input parameter and their interactions to the overall model output variance. This method is based on the decomposition of the model output variance into summands of variances of the input parameters in increasing dimensionality [20].

Let us denote the non-linear model by $Y=f(X)$, where $X \in \mathbb{R}^p$ is the model input vector and $Y \in \mathbb{R}^m$ is the model output vector. The function f represents the simulator. The input and output vectors are also written as: $X=\left(X_i\right)_{i=1, p}$ and $Y=\left(Y_r\right)_{r=1, m}$.

Let us first consider a single output model, i.e. m = 1. In Ref. [21], an indicator of the influence of the parameter Xi on this single output is proposed. It is denoted Si and is defined by:

where $V_i=V\left(E\left(Y \mid X_i\right)\right)$ represents the conditional variance of Y at the parameter X and V (Y ) is the total variance of Y. The sensitivity index Si is between 0 and 1. The closer the index is to 1, the more influential Xi is.

The sensitivity parameters Si are derived from the Hoeffding variance decomposition [22]. Y may be decomposed in the following way:

If the variables Xi are random and independent, eqn (2) makes it possible to obtain the decomposition of the functional variance by orthogonality (called functional ANOVA):

where,

In the general case, two parameters can be defined for each input parameter (eqns (5) and (6)): the first quantifies the main effect (interaction with other variables are not taken into account) and the second accounts for all the effects:

where $V_i=V\left[E\left(Y \mid X_i\right)\right], V_{T_i}=V(Y)-V\left[E\left(Y \mid X_{-i}\right)\right]$ and $X_{-i}$ denotes the set of all inputs excluding Xi [23]. The total effects of Xi take into account both the main effects and its interaction effects.

In general, models have several outputs, and generalized Sobol indexes were proposed in [24] is expressed by:

The numerator is the sum of Xi first-order effects on all the model outputs, and the denominator is the sum of the variances of all the model outputs. Sobol sensitivity indexes are used for factor prioritization, and for factor fixing if some inputs are found to have very low sensitivity indexes.

As mentioned before, output constraints need to be accounted for. This is done through regional sensitivity analysis and factor mapping [25]. The operator is interested in determining what input values cause the model output to be in a certain region, defined by a performance indicator or a constraint. In our case, we want the catenary voltage to be above a given threshold for all trains and at all times.

A simple qualitative method is Monte Carlo filtering: Monte Carlo runs are performed and the sampled input space is partitioned into two groups, depending on whether the associated model output satisfies or not the desired condition. The so-called ‘behavioural group’, denoted by ($X_i / R$), of size n, contains the elements that respect the performance indicators, while the ‘non-behavioural group’, denoted by ($X_i / \bar{R}$), of size $\bar{n}$, contains those that do not. The sum $n+\bar{n}$ corresponds to the total number of runs.

For each input, the empirical cumulative distribution functions of both groups, respectively denoted by $F_n\left(X_i / R\right)$ and $F_{\bar{n}}\left(X_i / \bar{R}\right)$, are computed and plotted (Fig. 2). Visual comparison between $F_n\left(X_i / R\right)$ and $F_{\bar{n}}\left(X_i / \bar{R}\right)$ provides qualitative information about the influence of each input variable with respect to factor mapping: if $F_{\bar{n}}\left(X_i / \bar{R}\right)$ and $F_{\bar{n}}\left(X_i / \bar{R}\right)$ are significantly different, then the sensitivity of the performance indicator to Xi is high.

The shape and the relative positions of the curves also contain information. If $F_n\left(X_i / R\right)$lies on the left side of $F_{\bar{n}}\left(X_i / \bar{R}\right)$, it means that the performance indicator is statistically more respected for smaller values of Xi: increasing Xi has a negative impact on the indicator performance criterion. Conversely, if $F_n\left(X_i / R\right)$ lies on the right side of $F_{\bar{n}}\left(X_i / \bar{R}\right)$, increasing Xi has a positive impact. The shape of the curves also gives information: the steeper the slope, the larger the local Xi influence.

The principles presented above have been applied to train traffic rescheduling, in order to better understand the influence of the rescheduling parameters on the model outputs. At the time being, we focus on the main performance criterion, which is the power feeding of the trains. The power feeding quality is monitored through the voltage pantograph, which must remain between standard limits

The rescheduling process is organized in four stages:

1. Problem specification: the decision-maker defines the traffic adjustment variables (time or distance intervals between trains and speed references), their range of variation, output performance indicators that define the set of acceptable solutions (voltage standard in the present case) and the criteria used to generate practical Pareto-optimal fronts (travel time, delays and electric consumption).

2. Monte Carlo runs: the simulator manager generates the sampling of the input space defined in stage 1 and runs the simulations. Quasi-random sampling should be used in order to avoid gaps and clusters in the sampled space. 3. Sensitivity analysis: the post-processor calculates the generalized Sobol indexes, generates the $X_i / R$ and $X_i / \bar{R}$ subsets, computes and plots the cumulative distribution functions and generates practical Pareto-optimal fronts.

4. Choice of the rescheduled traffic: the decision-maker interprets the sensitivity analysis results and Pareto-optimal front in order to choose the best point in $X_i / R$.

The proposed approach has been tested on a very simple first example: a single-track line, fed by three substations (SST) and travelled by ten high-speed trains (Fig. 3). In the nominal case (no default), trains depart every 5 minutes. The present analysis focuses on the respect of the pantograph voltage operational constraint, which must remain between 17.5 and 27.5 kV at all times in order to ensure the proper operation of traction engines. Figure 4 shows the pantograph voltage of the ten trains. Which curve corresponds to which train is not a concern: what matters is that all curves remain in the desired range, between 17.5 and 27.5 kV.

In the default case, the substation located in the middle of the line is assumed to go down, which limits the power available and disturbs the traffic. Figure 5 shows that the pantograph voltage drops below the lowest allowed level. Some trains are more affected than others, but again, what matters is the global view. Operational constraints are not respected, and hence the traffic cannot be maintained as it is.

For this first test case, two rescheduling actions are considered: increase of the time interval between two trains and speed reduction on both sides on the disabled substation. These actions are converted into two input variables: X1 is the time interval increase, ranging between 0 and 15 min, and X2 is the speed reduction, ranging between 0 and 35 km/h. The considered model outputs are the pantograph voltages at each computation time, which correspond to the data plotted in Figs 4 and 5.

The sensitivity analysis methods presented in the previous section has been applied. Thousand quasi-random samples were generated according to a uniform distribution, and the corresponding simulations were done.

First, the generalized Sobol indexes were computed for each of the ten trains. Similar results were obtained for all of them, which is consistent with the fact that they have identical missions. Table 1 reports the generalized Sobol indexes for the third train. These indexes allow to quantify the influence of the two rescheduling actions on the pantograph voltage quality. It shows that increasing the time interval between trains has a larger influence that reducing their speed.

The next step is the regional analysis needed to account for the pantograph voltage constraint. Samples were filtered according to the voltage constraint criterion and divided into the behavioural set and non-behavioural set. The empirical cumulated density functions were computed for each adjustment variables.

Figure 6 displays the cumulated density functions relative to X1 (time interval increase). The blue and red curves, respectively, correspond to the behavioural and non-behavioural subsets. The blue curve indicates that the voltage constraint is never satisfied when X1 is less than 7.5 minutes. Starting from this value, more and more points respect the voltage constraints as increases. The red curve lies on the left side of the blue one, indicating that increasing has a positive influence with respect to the voltage constraint satisfaction. The large space between the two curves shows that this influence is large. Figure 8 displays the cumulated density functions relative to X2 (speed reduction). Again, the blue and red curves, respectively, correspond to the behavioural and non-behavioural subsets. Both curves are very close to each other, meaning that X2 has a very small positive influence with respect to the voltage constraint satisfaction.

A closer look of the behavioural subset, not detailed here, shows that it is possible to respect the voltage constraint by acting on the time interval only: with a time interval increase above 10 minutes, there is no need to reduce the speed around the disabled substation to respect the voltage standards. The contrary is not true: the voltage constraint cannot be respected by the single-speed reduction.

The last part of the analysis is to provide performance criteria to help the choice of the final solution. Performance criteria are defined by the decision-maker and the behavioural subset points are used to build practical Pareto front. Figure 7 shows a Pareto plot which represents the trade-off between two criteria: F1 is the average train travel time, whereas F2 is the time interval increase between trains. The red points correspond to non-dominated solutions.

The decision-maker now has qualitative and quantitative information to support his final choice, according to his priorities. For example, he can choose to have fast trains with large time interval between them, or conversely prefer to have closer but slower trains. The choice is his. Figure 8 shows the train pantograph voltage in the case where the criterion F2 is favoured.

Railway traffic rescheduling in case of electric power shortage is an important process for proper operation of the railway network. In this article, we propose to use global and regional sensitivity analysis in order to provide qualitative and quantitative information to the decision- maker. The method is applied to a simple test case and results show that the proposed approach is helpful to assist the operators in charge of railway traffic rescheduling. The influence of the different decision variables is determined, and the voltage operational constraints are accounted for. Pareto-optimal front are built and the operator can choose the final solution according to his priorities.

In the present article, the proposed approach is tested on a very simple case. Further work will test more complex situations, but Sobol’s method requires a rather fine sampling of the decision space, which will limit the size of the problem that can be efficiently dealt with. Hence, future work should consider less expensive methods, as well as ways to break down large problems into smaller ones.