Kaba Keita
email: kaba.keita@ifsttar.fr

Paola Pellegrini

Joaquin Rodriguez

A Benders' decomposition algorithm for the real-time Railway Traffic Management Problem

Keywords: real-time railway traffic management problem, MILP, Benders' decomposition

, a state-of-the-art algorithm for this problem. In our Benders' decomposition, we minimize total delays by making train routing and scheduling decisions in the master problem. Given these decisions, we compute the trains arrival and passing times in the slave problem to deduce the total delay. By applying our Benders' decomposition algorithm to RECIFE-MILP, we tackle large instances representing traffic in the Rouen-Rive-Droite control area, in France.

Introduction

For many railway systems, during peak hours, the infrastructure capacity is completely exploited for ensuring the trains circulations. Many trains travel within short time through critical points. If a disturbance occurs, the traffic may be perturbed and, as a result, conflicts may emerge. In a conflict, multiple trains would claim the same track section concurrently if traveling at the planned speed. Hence, some trains must be stopped or decelerated for ensuring safety, and delays propagate. In locations such as junctions, which are areas where multiple lines cross, the emergence of conflicts is very frequent and effectively dealing with them may be particularly difficult.

Two kinds of delays occur in railway traffic: primary and secondary delay. The unexpected events which disturb the traffic cause the primary delay. The secondary delay is the result of delay propagation due to the interactions between trains. We do not have means to avoid unexpected events; hence the primary delay cannot be prevented. Instead, the secondary delay may be avoided or reduced by suitably managing traffic. The realtime Railway Traffic Management Problem (rtRTMP) consists in modifying trains route and schedule to limit the delay propagation. This problem is tackled by dispatchers. They do it manually, so the result of their choices is generally suboptimal. The use of an efficient algorithm to help dispatchers decision making is crucial to ensure an effective traffic management when disruptions occur. The design of this efficient algorithm is typically based on two main models used to represent the railway infrastructure: macroscopic and microscopic. In the macroscopic model, the infrastructure is seen as a set of nodes (junctions or stations) connected by lines, and the separation between trains is imposed through the control of generic headway times. In the microscopic one, the infrastructure is seen as a set of track sections where the train separation is imposed according to the signaling system, as it happens in reality. With the former, we can solve very large instances, but with low precision at the local level; hence, the optimization choices may have unexpected effects on the traffic when they are actually implemented, due for example to the specific signaling system in place. With the latter, these unexpected effects are avoided by considering in the optimization all necessary details. However, solving large instances may become very difficult due to memory or computational time limits.

In the operations research literature, many algorithms have been proposed to address the rtRTMP. In the following, we report the most relevant contributions. We group the contributions in two categories: those that propose algorithms without focusing on the size of the instances, and those that explicitly tackle large instances through decomposition. For what concerns the first category, several algorithms have been proposed (for recent surveys, see [START_REF] Cacchiani | An overview of recovery models and algorithms for real-time railway rescheduling[END_REF]; [START_REF] Corman | A review of online dynamic models and algorithms for railway traffic management[END_REF]). In some papers, the authors propose heuristic solution approaches in which train routes are fixed and the optimization concerns the scheduling decisions. An algorithm which determines trains optimal scheduling on a single track is proposed by [START_REF] Higgins | Optimal scheduling of trains on a single line track[END_REF]. This algorithm can both give support to trains dispatchers to tackle the rtRTMP and evaluate the impact of timetable changes. A heuristic algorithm is designed by [START_REF] Sahin | Railway traffic control and train scheduling based on inter-train conflict management[END_REF] to tackle train rescheduling problem in disrupted situations. In [START_REF] Dessouky | An exact solution procedure to determine the optimal dispatching times for complex rail networks[END_REF], the authors propose a branch-and-bound algorithm for rescheduling trains using fixed routes. Some authors propose heuristic solution approaches that consider a limited number of alternative routes selected during the solution process [START_REF] D'ariano | Reordering and local rerouting strategies to manage train traffic in real-time[END_REF][START_REF] Corman | A tabu search algorithm for rerouting trains during rail operations[END_REF][START_REF] Acuna-Agost | A MIP-based local search method for the railway rescheduling problem[END_REF]; others start with a small number of alternative routes and increase it throughout the solution process [START_REF] Caimi | A new resource-constrained multicommodity flow model for conflict-free train routing and scheduling[END_REF][START_REF] Caimi | A model predictive control approach for discrete-time rescheduling in complex central railway station approach[END_REF]. While several algorithms exist to tackle the rtRTMP considering a limited number of alternative routes, few algorithms have been proposed to address the rtRTMP considering all alternative routes. An effort in this direction is the work of [START_REF] Rodriguez | A constraint programming model for real-time train scheduling at junctions[END_REF]; Törnquist Krasemann (2012); [START_REF] Pellegrini | Optimal train routing and scheduling for managing traffic perturbations in complex junctions[END_REF][START_REF] Pellegrini | Recife-milp: An effective milp-based heuristic for the real-time railway traffic management problem[END_REF]. An algorithm based on a constraint programming approach is proposed by [START_REF] Rodriguez | A constraint programming model for real-time train scheduling at junctions[END_REF]. Törnquist [START_REF] Törnquist Krasemann | Design of an effective algorithm for fast response to rescheduling of railway traffic during disturbances[END_REF] proposes a greedy heuristic for the rtRTMP, modeling track segments. The impact of the microscopic representation of the infrastructure on the optimal solution is assessed by [START_REF] Pellegrini | Optimal train routing and scheduling for managing traffic perturbations in complex junctions[END_REF]. In the paper, the authors show that the consideration of a fine granularity of the infrastructure representation, up to the track-circuit level, may allow the detection of better solutions than the use of the rough granularity, which is limited to the block section level. The RECIFE-MILP algorithm is proposed by [START_REF] Pellegrini | Recife-milp: An effective milp-based heuristic for the real-time railway traffic management problem[END_REF]. All these algorithms do not explicitly focus on the problem represented by the size of the instances to be tackled. However, a few papers exist dealing with this problem. For example, D'Ariano and Pranzo (2009); [START_REF] Corman | Optimal inter-area coordination of train rescheduling decisions[END_REF][START_REF] Corman | Dispatching and coordination in multi-area railway traffic management[END_REF] propose heuristic approaches to decompose the instances to be solved. The authors decompose large instances of the rtRTMP by dispatching areas and apply a bi-level optimization approach to solve the problem. At the lower level, the system manages traffic in their control areas without any knowledge of the traffic flow elsewhere. At the higher level, a coordinator module is responsible for the traffic management over a railway network including several areas with a global vision of the traffic flows. Others, as [START_REF] Lusby | A set packing inspired method for real-time junction train routing[END_REF], propose classic mathemat-ical decomposition approaches as column generation. This column generation approach is applied to a set packing model to tackle real-time train routing at junctions. The set packing model of the problem is formulated as an integer linear program with a resource based constraint system. [START_REF] Meng | Simultaneous train rerouting and rescheduling on an ntrack network: A model reformulation with network-based cumulative flow variables[END_REF] propose a Lagrangian relaxation approach to tackle the simultaneous train rerouting and rescheduling on N-track railway network. A logic Benders' decomposition approach is proposed by [START_REF] Lamorgese | An exact decomposition approach for the real-time train dispatching problem[END_REF]; Lamorgese et al. (2016) to solve the rtRTMP. In the paper, the authors combine a macroscopic and a microscopic model to perform a decomposition of the initial problem into two sub-problems (master and slave problem). This approach allows dealing with large instances but it does not consider many details of the microscopic infrastructure characteristics. In a recent seminar, Lamorgese and Mannino (2016) present a standard Benders' decomposition approach to tackle the train's rescheduling problem formulated with an alternative graph model. In their approach, the authors replace the standard Benders' feasibility and optimality cuts with strong cuts obtained by strengthening and lifting the standards ones.

In this work, we consider RECIFE-MILP, which allows solving some rtRTMP instances to optimality considering all details in the infrastructure. However, it has been shown [START_REF] Pellegrini | Recife-milp: An effective milp-based heuristic for the real-time railway traffic management problem[END_REF] that its performance may strongly worsen when tackling very large instances in the short time allowed by the real-time nature of the problem. For this formulation, we propose a Benders' decomposition [START_REF] Benders | Partitioning procedures for solving mixed-variables programming problems[END_REF] to increase the size of the instances which can be effectively tackled. In our Benders' decomposition algorithm, we separate the rtRTMP into two problems: the master and slave. The master problem is the real-time train routing and scheduling problem, it contains the routing and scheduling variables (binary variables) and one dummy variable representing the contribution of continuous variables to the master problem objective function. The schedule here is intended as the order in which trains cross common tracks, and do not include time information. Once an incumbent solution is found in the master problem, it is sent to the dual of the slave problem. This solution is a specific route and schedule assignment for each train in the instance. The slave problem contains the continuous variables which determine the track sections occupation and reservation times, and deduces the delay suffered by each train. Based on the result of the dual problem, we add an optimality or feasibility cut to the master problem to cut off the current solution, if suboptimal or infeasible for the overall problem. This process is repeated until the algorithm converges to an optimal solution or the maximum computational time imposed by the real-time nature of the problem has elapsed. Starting from this standard Benders' reformulation, we propose a reduced one to improve the computational performance. Solving these reformulations with an iterative and an integrated Benders' algorithm, we tackle instances representing traffic in the Rouen-Rive-Droite control area, in France.

The remainder of this paper is organized as follows. Section 2 presents the RECIFE-MILP formulation of the rtRTMP. The RECIFE-MILP Benders' reformulation and the Reduced RECIFE-MILP Benders' reformulation proposed are presented in Section 3 and Section 4, respectively. Computational experiments are reported in Section 5. Conclusions and directions for future work are discussed in Section 6.

RECIFE-MILP formulation

In this section, we present the RECIFE-MILP formulation of the rtRTMP proposed by [START_REF] Pellegrini | Recife-milp: An effective milp-based heuristic for the real-time railway traffic management problem[END_REF]. RECIFE-MILP is a heuristic algorithm based on the truncated solution Figure 1: Example of the track-circuit reservation with the 3-aspect signaling system. The arrows represent the reference track-circuits for tc 3 and tc 4 , i.e., the first track-circuit of the n-2nd preceding block section, with n equal to 3. of mixed-integer linear programming (MILP) formulation. This formulation is based on a microscopic representation of the infrastructure, capable to consider all the characteristics of the infrastructure in deep details.

Before presenting the RECIFE-MILP formulation of the rtRTMP, we define some technical expressions used to indicate some relevant elements of the railway system. Track-circuit: a detection device on which the presence of a train is automatically detected. Running time: the time spent by the head of a train on a track-circuit when traveling at the planned speed. Clearing time: the time elapsed between the moment when the train's head leaves a trackcircuit and the moment when its tail leaves it. Occupation time: the time interval during which a train physically occupies a track-circuit. Block section: a block section is a sequence of track-circuits whose access is controlled by a signal. Reservation time: in the blocking time theory [START_REF] Pachl | Railway Operations Processes[END_REF], a train is allowed to enter a block section opened by an n-aspect signal only if the following n -1 block sections are available. Before entering, the train reserves these n -1 block sections, and in particular it reserves all their track-circuits. Hence, the reservation time of the track-circuit starts before a train enters the reference track-circuit (the first track-circuit of the n-2nd preceding block section, e.g., in the example of Figure 1, the reference track-circuit of tc 3 is tc 2 in case of a 3-aspect signaling system) and ends when it enters the track-circuit itself. Formation time: in addition to the reservation time, a supplementary time is needed before a train starts the occupation of a sequence of block sections. This supplementary time is the formation time. It is used for example to take into account the signal visibility distance. Release time: the release time corresponds to the lapse of time in which the reservation of a track-circuit is still active after a train exits it. Utilization: we name utilization the sum of reservation and occupation time. Route: the complete sequence of track-circuits traversed by a train during its trip is named route.

If a train starts its trip at null speed, in the model its occupation of the first track-circuit is accounted only from the time at which it starts moving. Its staying still on the track-circuit before that time is represented through the reservation time.

In RECIFE-MILP, in addition to the actual track-circuits, two dummy ones are considered, tc 0 and tc ∞ . They represent the entry and the exit locations of the infrastructure, respectively. Each track-circuit has a running time and a clearing time which depend on the type of train traversing them and on the route traveled. For the dummy track-circuits, the running time and clearing times are null.

In the RECIFE-MILP formulation, the following notation is used: T ≡ set of trains; w t ≡ weight associated to train t's delay; ty t ≡ type corresponding to train t (train characteristics); init t , exit t ≡ earliest time at which train t can be operated and earliest time at which it can reach its destination given init t and the route assigned in the timetable; R t , TC t ≡ set of routes and track-circuits available for train t; TC r ≡ set of track-circuits composing route r; p r,tc , s r,tc ≡ track-circuits preceding and following tc along r; rt ty,r,tc , ct ty,r,tc ≡ running and clearing time of tc along r for a train of type ty; ref r,tc ≡ reference track-circuit of tc along route r; bs r,tc ≡ block section including track-circuit tc along route r; for bs , rel bs ≡ formation and release time for block section bs; M ≡ large constant.

The formulation contains non-negative continuous variables: for all triplets of t ∈ T , r ∈ R t and tc ∈ TC r : o t,r,tc : time at which t starts the occupation of tc along r, l t,r,tc : longer stay of t's head on tc along r, due to dwell time and scheduling decisions (delay); for all pairs of t ∈ T and tc ∈ TC t : sU t,tc : time at which t starts tc utilization; eU t,tc : time at which t ends tc utilization; for all t ∈ T : D t : delay suffered by train t when exiting the infrastructure.

In addition it includes binary variables: for all pairs of t ∈ T and r ∈ R t :

x t,r = 1 if t uses r, 0 otherwise,
for all triplets of t, t ∈ T such that the index t is smaller than the index t , and tc ∈ TC t ∩ TC t :

y t,t ,tc = 1 if t utilizes tc before t (t ≺ t ), 0 otherwise (t t ).
In the formulation, the objective (1) is the minimization of the total weighted delays suffered by trains at their exit from the infrastructure. This weighting of the objective function allows taking into account different train priorities. These priorities may be linked to the type of circulation (e.g., freight or passenger) or other aspects as the number of passengers traveling on each train. A train t cannot be operated earlier than init t (Constraints (2)). Constraints (3) indicate that the start time of track-circuit occupation along a route is zero if the route itself is not used. A train starts occupying track-circuit tc along a route after spending in the preceding track-circuit its longer stay and its running time, if the route is used (Constraints (4)). Constraints (5) impose that a train must use exactly one route. The value of delay D t at least equals the difference between the actual and the scheduled arrival times at the exit of the infrastructure (Constraints (6)). A train's utilization of a track-circuit starts as soon as the train starts occupying the track-circuit ref r,tc along one of the routes including it, minus the formation time (Constraints ( 7)). The utilization of a track-circuit lasts till the train utilizes it along any route, plus the formation and the release time (Constraints ( 8)). The track-circuit utilizations by two trains must not overlap (Constraints ( 9) and ( 10)). (1)

ot,r,tc ≥ initt xt,r ∀t ∈ T, r ∈ Rt, tc ∈ TC r : pr,tc = tc0, (2) ot,r,tc ≤ M xt,r ∀t ∈ T, r ∈ Rt, tc ∈ TC r , (3)
ot,r,tc = ot,r,p r,tc + lt,r,p r,tc + rtr,ty t ,p r,tc xt,r ∀t ∈ T, r ∈ Rt, tc ∈ TC r : pr,tc = tc0, (4) For a more detailed discussion of this formulation we refer the interested reader to Pellegrini et al. (2014,2015).

r∈R t xt,r = 1 ∀t ∈ T, (5)

RECIFE-MILP Benders' reformulation

By fixing routing and scheduling variables in the RECIFE-MILP formulation (1)-( 10) (let them be xt,r and ȳt,t ,tc ) we get the following Benders' Sub-Problem (BSP). In our Benders' decomposition algorithm, we do not solve the BSP ( 11)-( 19): its dual is solved to generate Benders' cuts. Hence, we present also the formulation of the Dual of the Benders' Sub-Problem (DBSP). Based on the DBSP ( 20)-( 33) formulation, we present the Restricted Benders' Master Problem (RBMP) that is the reformulation of RECIFE-MILP (1)-( 10).

Benders' Sub-Problem (BSP)

min t∈T wtDt. (11) ot,r,tc ≥ initt xt,r ∀t ∈ T, r ∈ Rt, tc ∈ T C r : pr,tc = tc0, ( 12
) ot,r,tc ≤ M xt,r ∀t ∈ T, r ∈ Rt, tc ∈ TC r , (13)
-ot,r,tc + ot,r,p r,tc + lt,r,p r,tc = -rtr,ty t ,p r,tc xt,r ∀t ∈ T, r ∈ Rt, tc ∈ TC r : pr,tc = tc0,

+ t∈T t ∈T tc∈T C t ∩T C t M ((1 -ȳt,t ,tc )η t,t ,tc + ȳt,t ,tc ψ t,t ,tc )). ( 20
)
αt,r,tc + βt,r,tc + λt,r,tc -

tc∈T C t φt,tc -ωt,tc ≤ 0 ∀t ∈ T, r ∈ Rt, tc ∈ T C r : pr,tc = tc0, (21)
λt,r,tc -λt,r,p r,tc + βt,r,tc -

tc∈T C t φt,tc -ωt,tc ≤ 0 ∀t ∈ T, r ∈ Rt, tc ∈ T C r , (22) λt,r,tc - tc∈T C t ωt,tc ≤ 0 ∀t ∈ T, r ∈ Rt, tc ∈ T C r , ( 23
) αt,r,tc ∞ + βt,r,tc ∞ -λ t,r,tc∞ -θt ≤ 0 ∀t ∈ T, r ∈ Rt, ( 24
) θt ≤ 1 ∀t ∈ T, ( 25
) φt,tc -η t,t ,tc -ψ t,t ,tc ≤ 0 ∀t, t ∈ T, t < t , tc ∈ T Ct ∩ T C t , (26)
ωt,tc + η t,t ,tc + ψ t,t ,tc ≤ 0 ∀t, t ∈ T, t < t , tc

∈ T Ct ∩ T C t , (27) αt,r,tc ≥ 0 ∀t ∈ T, r ∈ Rt, tc ∈ T C r , ( 28
) βt,r,tc ≤ 0 ∀t ∈ T, r ∈ Rt, tc ∈ T C r , ( 29
) λt,r,tc ∈ R ∀t ∈ T, r ∈ Rt, tc ∈ T C r , ( 30
) ωt,tc, θt ≥ 0 ∀t ∈ T, tc ∈ T Ct, (31) φt,tc ≤ 0 ∀t ∈ T, tc ∈ T Ct, (32)
η t,t ,tc , ψ t,t ,tc ≤ 0 ∀t, t ∈ T, t < t , tc ∈ T Ct ∩ T C t . (33)
Given the DBSP ( 20)-( 33), we can generate the cuts that are necessary to reformulate the RECIFE-MILP formulation (1)-( 10

) ≤ 0 ((α, β, λ, θ, φ, ω, η, ψ) ∈ RS) (36) r∈R t xt,r = 1 ∀t ∈ T, ( 37
) xt,r ∈ {0, 1} ∀t ∈ T, r ∈ Rt, (38)
y t,t ,tc ∈ {0, 1} ∀t, t ∈ T, t < t , tc ∈ T Ct ∩ T C t , (39)
z ≥ 0.

(40)

The additional dummy variable z represents the contribution of the RECIFE-MILP continuous variables to the RBMP (34)-( 40) objective function, while sets P s and R s contain the extreme points and extreme rays, respectively, of the polyhedron S representing the feasible solution space of the DBSP ( 20)-( 33). The RBMP ( 34)-( 40) has only one dummy variable z and the binary variables x t,r and y t,t ,tc of the original problem, RECIFE-MILP (1)-( 10). Note that the values of (α, β, λ, θ, φ, ω, η, ψ) are known because they are either the extreme points P s or the extreme rays R s calculated in the DBSP ( 20)-(33). Constraints ( 35) and ( 36) represent respectively the classic Benders' optimality and feasibility cuts. Constraints (37) represent the routing constraints equivalent to (5) in the RECIFE-MILP formulation (1)-( 10). We have thus reformulated the RECIFE-MILP formulation (1)-( 10) as an equivalent problem (RBMP ( 34)-( 40)) with binary variables and one continuous dummy variable.

At the beginning of our RECIFE-MILP Benders' decomposition algorithm, we seek a feasible solution to the RBMP ( 34)-( 40) by fixing sets P s and R s to empty (P s := ∅, R s := ∅). The problem obtained, when the constraints ( 35) and ( 36) are removed, is called the Unrestricted Benders' Master Problem (UBMP) which is formulated as follows.

Unrestricted Benders' Master Problem (UBMP)

min z (41)

r∈R t xt,r = 1 ∀t ∈ T, (42) xt,r ∈ {0, 1} ∀t ∈ T, r ∈ Rt, (43)
y t,t ,tc ∈ {0, 1} ∀t, t ∈ T, t < t , tc ∈ T Ct ∩ T C t , (44)
z ≥ 0. ( 45
)
We tackle our reformulation of the RECIFE-MILP formulation (1)-( 10) with two Benders' decomposition algorithms: the iterative algorithm and the integrated one. The integrated algorithm uses the lazy constraint callback method. Here, we embed the DBSP ( 20)-( 33) into the branch-and-bound procedure of the UBMP ( 41)-( 45). In particular, at any node where an incumbent is found, we run a callback in which the DBSP (20)-( 32) is solved. If the DBSP (20)-( 33) is unbounded we add the appropriate feasibility cut (Constraints ( 35)) to the UBMP ( 41)-( 45). If the DBSP (20)-( 33) is bounded we seek if its objective function value is equal to the value of the UBMP ( 41)-( 45) objective function. If so, a new integer incumbent solution is found and it is tested for the optimality. If it is not optimal, we add the appropriate optimality cut (Constraints (36)). Thus, in the integrated algorithm instead of iteratively solving the UBMP ( 41)-( 45) and the DBSP ( 20)-( 33), the whole problem is solved in one single integrated procedure. The algorithm stops when the optimal solution is found or when the computational time limit is elapsed. A similar approach is followed by [START_REF] Wu | An improved decomposition framework for accelerating lsf and bd based methods for netwok-constrained uc problems[END_REF] and [START_REF] Feizollahi | The robust cold standby redundancy allocation in series-parallel systems with budgeted uncertainty[END_REF].

For comparison, we also tackle the problem with the iterative algorithm in which the UBMP ( 41)-( 45) and the DBSP ( 20)-( 33) are iteratively solved at the optimum. At each iteration, we add to the UBMP ( 41)-( 45) either a Benders' optimality cut or a Benders' feasibility cut depending the solution of the DBSP ( 20)-( 33) until the optimum is found (the objective function value is the same for the UBMP ( 41)-( 45) and the DBSP ( 20)-( 33)) or when the computational time limit is elapsed.

Note that for the rtRTMP, the UBMP ( 41)-( 45) cannot be infeasible: any solution that fixes a routing decision for each train (x variables) is feasible because there are no constraints on the scheduling (y variables). As a result, the infeasibility case of the UBMP ( 41)-( 45) is not considered in the algorithms.

Reduced RECIFE-MILP Benders' reformulation

By studing the rtRTMP structure, we realize that most x-variables in an incumbent solution of the UBMP ( 41)-( 45) are zero. Hence, many constraints in the sub-problem are negligible: for example when we know the routing decision for each train, Constraints (13) in the BSP ( 11)-( 19) become unnecessary because they are trivially satisfied or their role is simply to set some variables equal to zero. Hence, many variables (as β t,r,tc ) and many constraints (as some Constraints ( 21) and ( 22)) in the DBSP ( 20)-( 33) are also unnecessary. For the same reason, we can discard all constraints in the BSP ( 11)-( 19) associated with the unused routes (x t,r = 0). Moreover, we observe that, in the BSP ( 11)-( 19), the disjunctive Constraints ( 18) and ( 19) are imposed for all track-circuits which may possibly be used by two trains t and t . However, if the routes chosen for the two trains imply that a possibly shared track-circuit is used by either only one or none of them, the scheduling decision implied by the corresponding y-variable is actually negligible from a practical point of view: RECIFE-MILP will fix this variable, but this information will not be used for the practical implementation of the solution since, in reality, no precedence needs to be set unless both trains are passing in the same location. Hence, the value of these practically negligible y-variable can be disregarded in the BSP ( 11)-( 19), together with the corresponding constraints. Remark that, when only one train uses a possibly shared track-circuit, only one assignment of the y-variable is feasible: if t is using it, then the variable must be equal to 0 since the utilization variables of t must be set to 0; if t is using it, then the variable must be set to 1. This implication is not explicit in the UBMP ( 41)-( 45): it can generate solutions which result infeasible for the BSP ( 11)-( 19) due to the negligible y-variables.

To avoid the generation of Benders' feasibility cuts due to these variables, we remove from the BSP ( 11)-( 19) the Constraints ( 18) and ( 19) which correspond to the track-circuits not actually used by each pair of trains. The result of the constraint and variable removals, from the BSP (11)-( 19) and hence from the DBSP (20)-( 33), is the Reduced RECIFE-MILP Benders' reformulation, whose details are described in the rest of this section.

In the Reduced RECIFE-MILP Benders' reformulation, we apply the same Benders' algorithms, the iterative algorithm and the integrated one, replacing the BSP (11)-( 19) and the DBSP (20)-( 33) by the Red-BSP ( 46)-( 53) and the Red-DBSP (54)-(66) described in the following.

Reduced Benders' Sub-Problem (Red-BSP) Let, r be the route used by train t and r the route used by train t , where t, t ∈ T . Remark, the set of track-circuits available for train t (T C t ) is reduced to T C r (set of track-circuits composing the route r) and the set of track-circuits available for train t (T C t ) is also reduced to T C r . The Reduced Benders' Sub-Problem (Red-BSP) can then be formulated as follows. (46)

ot,r,tc ≥ initt ∀t ∈ T, r, tc ∈ T C r : pr,tc = tc0, (47)
-ot,r,tc + ot,r,p r,tc + lt,r,p r,tc = -rt r,ty t ,p r,tc ∀t ∈ T, r, tc ∈ TC r : pr,tc = tc0, (48)

Dt -ot,r,tc ∞ ≥ -(exitt -rtr,ty t ,tc∞ -ctr,ty t ,tc∞ ) ∀t ∈ T, (49)
sU t,tc -o t,r,ref r,tc ≤ -for bs r,tc ∀t ∈ T, tc ∈ T C r , (50)
eU t,tc -o t,r,ref r,tc -lt,r,tc ≥ rel bs r,tc + ctr,ty t ,tc + rtr,ty t ,tc ∀t ∈ T, tc ∈ T C r , (51)

eU t,tc -sU t ,tc ≤ M -M ȳt,t ,tc ∀t, t ∈ T, t < t , tc ∈ T C r ∩ T C r , ( 52
)
eU t ,tc -sU t,tc ≤ M ȳt,t ,tc ∀t, t ∈ T, t < t , tc ∈ T C r ∩ T C r . (53)
As a consequence, the Red-DBSP ( 54)-( 66) is the following.

Reduced Dual of Benders

+ t∈T t ∈T tc∈T C r ∩T C r M ((1 -ȳt,t ,tc )η t,t ,tc + ȳt,t ,tc ψ t,t ,tc )). (54)
αt,r,tc + λt,r,tc -φt,tc -ωt,tc ≤ 0

∀t ∈ T, r, tc ∈ T C r : pr,tc = tc0, (55)
λt,r,tc -λt,r,p r,tc -φt,tc -ωt,tc

≤ 0 ∀t ∈ T, r, tc ∈ T C r , (56)
λt,r,tc -ωt,tc ≤ 0 ∀t ∈ T, r, tc ∈ T C r , (57)
αt,r,tc ∞ -λt,r,tc ∞ -θt ≤ 0 ∀t ∈ T, r, (58)
θt ≤ 1 ∀t ∈ T, (59) φt
,tc -η t,t ,tc -ψ t,t ,tc ≤ 0 ∀t, t ∈ T, t < t , tc ∈ T C r ∩ T C r , (60) ωt
,tc + η t,t ,tc + ψ t,t ,tc ≤ 0 ∀t, t ∈ T, t < t , tc ∈ T C r ∩ T C r , (61)
αt,r,tc ≥ 0 ∀t ∈ T, r, tc ∈ T C r , (62)

λt,r,tc ∈ R ∀t ∈ T, r, tc ∈ T C r , ( 63
) ωt,tc, θt ≥ 0 ∀t ∈ T, tc ∈ T C r , (64)
φt,tc ≤ 0 ∀t ∈ T, tc ∈ T C r , (65)
η t,t ,tc , ψ t,t ,tc ≤ 0 ∀t, t ∈ T, t < t , tc ∈ T C r ∩ T C r . (66)
Finally, we need also to change the formulation of the RBMP ( 34)-( 40) to take into account the changes in the Red-DBSP ( 54)-(66). In particular, Constraints ( 35) and (36) become Constraints (67) and (68). The cuts now include only the variables which we considered in the Red-DBSP (54)-(66).

Computational experiments

In this section we assess the quality of the RECIFE-MILP Benders' reformulation and the Reduced RECIFE-MILP Benders' reformulation. The two reformulations are solved using the iterative algorithm and the integrated one. We consider a case-study representing traffic in the Rouen-Rive-Droite control area to run our experiments. This case-study is recognized to be difficult to tackle in the time limit imposed for the rtRTMP [START_REF] Pellegrini | Recife-milp: An effective milp-based heuristic for the real-time railway traffic management problem[END_REF]. We set the computational time available for the optimization to one minute, three minutes and five minutes. The implementation is done using IBM ILOG CPLEX Concert Technology for C++ (IBM ILOG CPLEX version 12.6 (IBM, 2012)). The weight associated to train t's delay is set to 1 for all trains, since we have no information on different trains' priority. The route formation and release times are 15 and 5 seconds for all block sections, respectively. The control area including Rouen-Rive-Droite comprises six stations, with two to six platforms, and one bifurcation. The presence of multiple stations with several possible platform assignments implies the availability of a very large number of alternative routes. The existence of these routes is the main source of complexity of traffic management in this location, together with the presence of mix traffic. The control area is depicted in Figure 2. The 190 track-circuits compose 189 block sections and 11 347 routes. The oneday timetable considered includes 186 trains: 2 high-speed and 107 conventional passenger trains, 33 freight trains and 44 local movements.

From this one-day timetable, we create 100 random scenarios: 20% of trains, randomly selected, suffer a random delay between 5 and 15 minutes at their entrance in the control area. We generate one rtRTMP instance from each of these 100 scenarios by considering all the trains entering the control area within an hour horizon. We set the time horizon from 6:00 am to 07:00 am. This time horizon corresponds to the morning peak hour.

The so obtained one-hour instances include between 10 and 13 trains (mean 11). Each train can use between 1 and 192 routes (mean 45), which translates into a RECIFE-MILP formulation with about 117 000 continuous variables, 78 000 binary variables and 364 000 constraints, for an instance including 10 trains. We run the experiments on a computer with eight Intel Xeon 3.5 Ghz processors and 128 GB RAM. In the next subsections, we compare first the two Benders' reformulations proposed: the RECIFE-MILP Benders' reformulation and the Reduced RECIFE-MILP Benders' reformulation. Second we compare the iterative algorithm to the integrated one. Finally we compare the best pair reformulation-algorithm to the RECIFE-MILP algorithm proposed by [START_REF] Pellegrini | Recife-milp: An effective milp-based heuristic for the real-time railway traffic management problem[END_REF].

Comparison of the two Benders' reformulations

To compare the two Benders' reformulations proposed in this paper, we tackle the 100 instances described at the beginning of this section using the integrated algorithm. We stop the algorithm after 20 DBSP (20)-( 33) solutions and we compare the computational time employed for the two reformulations. The results show that with the RECIFE-MILP Benders' reformulation, the computational time for solving the DBSP (20)-( 33) is very long: 165 seconds in average. The corresponding quantity for the Reduce RECIFE-MILP Benders' reformulation is 0.31 seconds. Indeed, the former is not suitable for tackling the rtRTMP, where the available computational time is only of some minutes. The latter instead complies with the real-time nature of the problem. In the following, then, we will only consider the Reduced RECIFE-MILP Benders' reformulation for the experiments.

Comparison of the two Benders' algorithms: the iterative and the integrated ones

In this section, we compare the iterative algorithm to the integrated one to solve the Reduced RECIFE-MILP Benders' reformulation.

The computational analysis on the 100 instances previously presented, limiting the computation time to 5 minutes, shows that the integrated algorithm outperforms the iterative one. For each instance, the integrated algorithm finds better solutions than the iterative one. The integrated algorithm improves the quality of the objective function value of the iterative one by 77% in average. In this section, we compare the performance of our Reduced RECIFE-MILP Benders' algorithm to the RECIFE-MILP one. We choose the RECIFE-MILP algorithm as the benchmark because it is an efficient algorithm for the rtRTMP.

In Table 1, 2 and 3, we report the results achieved on the 100 instances considered, setting the computational time available to one, three and five minutes, respectively. The first column indicates the name of the algorithm. The two last columns contain the number of instances solved to the optimum within the available computational time and the number of instances in which each algorithm found the best solution, respectively. The results show that the RECIFE-MILP algorithm achieves the best performance for more cases than the Reduced RECIFE-MILP Benders' algorithm. For the instances on which the Reduced RECIFE-MILP Benders' algorithm is the best, we observe that the percentage of optimality cuts with respect to the total number of Benders' cuts is very high: 97% in average. Instead, when the RECIFE-MILP algorithm is the best, we remark that this percentage decreases: 85% in average. Hence, we conjecture that the performance of the Reduced RECIFE-MILP Benders' algorithm would improve if the percentage of the optimality cuts generated during the integrated branch-and-bound process increased. For the instances in which the algorithms get a feasible but sub-optimal solution, the gap is still high: 98% in average for the RECIFE-MILP algorithm and 100% in average for the Reduced RECIFE-MILP Benders' algorithm. This is due to the weakness of the linear relaxation of the formulation, which we will investigate deeply in future works. In this paper, we proposed two reformulations of RECIFE-MILP for the rtRTMP: the RECIFE-MILP Benders' reformulation and the Reduced RECIFE-MILP Benders' reformulation. We solve them through two Benders' decomposition algorithms, the iterative and the integrated one. The latter implements the lazy constraint callback that is the integration of the Benders algorithm into the branch-and-bound procedure. We tackle large and difficult instances representing traffic at the Rouen-Rive-Droite control area, in France. The results show that the RECIFE-MILP Benders' reformulation is not appropriate for this problem. Instead, the Reduced RECIFE-MILP Benders' reformulation can be appropriate thanks to its better computational performance. Moreover, the integrated algorithm outperforms the iterative one. Nevertheless, the classic RECIFE-MILP achieves the best result in the majority of the instances tackled. We conjecture that the Benders' algorithm performance would improve if the percentage of optimality cuts generated increased. In future works, we will focus on how to generate strong inequalities in the unrestricted Benders' master problem. These inequalities must make the reduced dual of Benders' sub-problem bounded and warrant the generation of optimality cuts.

Figure 2 :

 2 Figure 2: Rouen-Rive-Droite control area

  eU t ,tc -M y t,t ,tc ≤ sU t,tc ∀t, t ∈ T, t < t , tc ∈ TC t ∩ TC t .

	Dt ≥	ot,r,tc ∞ +
	r∈R t
		(10)

r∈R t rtr,ty t ,tc∞ xt,r + ctr,ty t ,tc∞ xt,r -exitt ∀t ∈ T, (6) sU t,tc ≤ r∈R t : tc∈TC r o t,r,ref r,tc -for bs r,tc xt,r ∀t ∈ T, tc ∈ TC t, (7) eU t,tc ≥ r∈R t : tc∈TC r o t,r,ref r,tc + rel bs r,tc xt,r + ctr,ty t ,tc xt,r + rtr,ty t ,tc xt,r + lt,r,tc ∀t ∈ T, tc ∈ TC t, (8) eU t,tc -M (1 -y t,t ,tc ) ≤ sU t ,tc ∀t, t ∈ T, t < t , tc ∈ TC t ∩ TC t , (9)

  eU t ,tc -sU t,tc ≤ M ȳt,t ,tc ∀t, t ∈ T, t < t , tc ∈ T Ct ∩ T C t . (19)Let α t,r,tc , β t,r,tc , λ t,r,tc , θ t , φ t,tc , ω t,tc , η t,t ,tc , ψ t,t ,tc , be the dual variables associated with Constraints (12)-(19) respectively. The Dual of the Benders' Sub-Problem (DBSP) is written as follows.xt,r(inittαt,r,tc + M βt,r,tc -rtr,ty t ,p r,tc λt,r,tc) + t∈T r∈R t tc∈T C t xt,r((relbs r,tc + ctr,ty t ,tc + rt r,ty t ,tc )ωt,tc -f or bs r,tc φt,tc) xt,r(rtr,ty t ,tc∞ + ctr,ty t ,tc∞ ))θt

	Dual of Benders' Sub-Problem (DBSP)
	max(
	t∈T r∈R t tc∈T C r
	-	(exitt -
	t∈T		r∈R t
	o t,r,ref r,tc ≤ -	for bs r,tc xt,r	∀t ∈ T, tc ∈ T Ct,	(16)
	r∈R t : tc∈T C r	r∈R t : tc∈T C r
	eU t,tc -

-r∈R t ot,r,tc ∞ ≥ -(exitt -r∈R t rtr,ty t ,tc∞ xt,r -ctr,ty t ,tc∞ xt,r) ∀t ∈ T, (15) sU t,tc -r∈R t : tc∈TC r o t,r,ref r,tc -lt,r,tc ≥ r∈R t : tc∈T C r rel bs r,tc xt,r + ctr,ty t ,tc xt,r + rtr,ty t ,tc xt,r ∀t ∈ T, tc ∈ TC t, (17) eU t,tc -sU t ,tc ≤ M -M ȳt,t ,tc ∀t, t ∈ T, t < t , tc ∈ T Ct ∩ T C t , (18)

  ) as the Restricted Benders' Master Problem (RBMP).

	Restricted Benders' Master Problem (RBMP)
	min z	(34)
	z -(

t∈T r∈R t tc∈T C r xt,r(inittαt,r,tc + M βt,r,tc -rtr,ty t ,p r,tc λt,r,tc)

+ t∈T r∈R t tc∈T C t xt,

r((rel bs r,tc + ctr,ty t ,tc + rt r,ty t ,tc )ωt,tc -f or bs r,tc φt,tc) -t∈T (exitt -r∈R t xt,r(rtr,ty t ,tc∞ + ctr,ty t ,tc∞ ))θt + t∈T t ∈T tc∈T C t ∩T C t M ((1 -y t,t ,tc )η t,t ,tc + y t,t ,tc ψ t,t ,tc )) ≥ 0 ((α, β, λ, θ, φ, ω, η, ψ) ∈ PS) (35) t∈T r∈R t tc∈T C r xt,r(inittαt,r,tc + M βt,r,tc -rtr,ty t ,p r,tc λt,r,tc) + t∈T r∈R t tc∈T C t xt,r((rel bs r,tc + ctr,ty t ,tc + rt r,ty t ,tc )ωt,tc -f or bs r,tc φt,tc) -t∈T (exitt -r∈R t xt,r(rtr,ty t ,tc∞ + ctr,ty t ,tc∞ ))θt + t∈T t ∈T tc∈T C t ∩T C t M ((1 -y t,t ,tc )η t,t ,tc + y t,t ,tc ψ t,t ,tc

  ' Sub-Problem (Red-DBSP) (rel bs r,tc + ctr,ty t ,tc + rtr,ty t ,tc)ωt,tc -f or bs r,tc φt,tc -

	max(
	t∈T tc∈T C
	+
	t∈T tc∈T C t

r inittαt,r,tc -rtr,ty t ,p r,tc λt,r,tc t∈T (exitt -rtr,ty t ,tc∞ + ctr,ty t ,tc∞ )θt

  xt,r(inittαt,r,tc -rtr,ty t ,p r,tc λt,r,tc) xt,r((rel bs r,tc + ctr,ty t ,tc + rtr,ty t ,tc)ωt,tc -f or bs r,tc φt,tc) -t∈T (exitt -xt,r(rtr,ty t ,tc∞ + ctr,ty t ,tc∞ ))θt+ t∈T t ∈T tc∈T C r ∩T C rM ((1 -y t,t ,tc )η t,t ,tc + y t,t ,tc ψ t,t ,tc )) ≥ 0 xt,r(inittαt,r,tc -rtr,ty t ,p r,tc λt,r,tc) xt,r((rel bs r,tc + ctr,ty t ,tc + rtr,ty t ,tc)ωt,tc -f or bs r,tc φt,tc) xt,r(rtr,ty t ,tc∞ + ctr,ty t ,tc∞ ))θt + t∈T t ∈T tc∈T C r ∩T C r M ((1 -y t,t ,tc )η t,t ,tc + y t,t ,tc ψ t,t ,tc ) ≤ 0

	z -(
	t∈T tc∈T C
	+
	t∈T tc∈T C
	((α, λ, θ, φ, ω, η, ψ) ∈ PS)	(67)
	t∈T tc∈T C
	+
	t∈T tc∈T C
	-
	((α, λ, θ, φ, ω, η, ψ) ∈ RS)	(68)

r r r r t∈T (exitt -

Table 1 :

 1 Performance of the Reduced RECIFE-MILP Benders' algorithm vs the RECIFE-MILP algorithm on 100 instances (time limit 60 seconds)

	Algorithms	# optima # best solutions found
	RECIFE-MILP	1	96
	Reduced RECIFE-MILP Benders'	0	4

Table 2 :

 2 Performance of the Reduced RECIFE-MILP Benders' algorithm vs the RECIFE-MILP algorithm on 100 instances (time limit 180 seconds)

	Algorithms	# optima # best solutions found
	RECIFE-MILP	9	97
	Reduced RECIFE-MILP Benders'	0	3
	5.3 Reduced RECIFE-MILP Benders' algorithm versus RECIFE-MILP algorithm

Table 3 :

 3 Performance of the Reduced RECIFE-MILP Benders' algorithm vs the RECIFE-MILP algorithm on 100 instances (time limit 300 seconds)

	Algorithms	# optima # best solutions found
	RECIFE-MILP	10	96
	Reduced RECIFE-MILP Benders'	0	4

Rail Lille 2017, 7th International Conference on Railway Operations Modelling and Analysis, IAROR, Lille, France, 04 -07 avril 2017

Acknowledgment

The work of Kaba KEITA was partially supported by the "Direction Recherche, Enseignement Supérieur, Recherche et Formations Sanitaires et Sociales" of the HAUTS-DE-FRANCE region, in France.


Y Lasne
email: lasne@enscpb.fr

Philippe Paillou

G Ruffié

C Serradilla

F Demontoux

J.-M Malézieux

Martien Y Terrestre

Lasne

IMPACT DE LA SALINITE SUR LES PROPRIETES DIELECTRIQUES DES MATERIAUX GEOLOGIQUES : IMPLICATION POUR LA DETECTION D'HUMIDITE PAR TELEDETECTION ACTIVE HYPERFREQUENCES : CAS TERRESTRE ET MARTIEN

whether they are published or not. The documents may come

I. Introduction

La mesure de l'humidité des sols à l'aide de systèmes radar a fait l'objet de nombreux travaux ces vingt dernières années [1][2][3][4]. Plus particulièrement, la relation existant entre les propriétés diélectriques des sols et leur teneur en eau a conduit à s'interroger sur l'impact du taux d'humidité sur le coefficient de rétrodiffusion radar ! ! ! ! o [5][START_REF] Su | ESA[END_REF]. Si l'effet du taux d'humidité sur la permittivité a été largement étudié et modélisé, il n'en est pas de même pour la salinité. De récents travaux ont souligné l'influence de la présence de sels en solution sur les propriétés diélectriques des sols, spécialement sur la partie imaginaire " " " "'' de la constante diélectrique [START_REF] Aly | EARSeL Proceedings[END_REF][START_REF] Shao | [END_REF]. Si la partie réelle " " " "' de la permittivité, liée à la polarisation du milieu, conditionne la célérité d'une onde dans le matériau et donc sa capacité à conduire l'énergie, "

" " "'' quant à elle est liée à la conductivité du milieu et traduit l'atténuation du signal radar par absorption de l'énergie nécessaire pour atteindre la polarisation. Il apparaît donc indispensable de tenir compte de la présence de roches salines (évaporites) dans les applications de télédétection radar. Pour ce faire, nous nous proposons d'étudier l'influence de la présence de sels sur le coefficient ! ! ! ! o via les propriétés diélectriques des milieux considérés. La méthodologie adoptée repose sur une série de mesures réalisées en laboratoire au moyen d'un analyseur de réseau, pour évaluer le potentiel de lois de mélange diélectrique [9][10][11] reposant sur les formules de Debye. Ces modèles diélectriques permettront de définir les paramètres d'entrée nécessaires à la modélisation du coefficient ! ! ! ! o ,au moyen de modèles analytiques type IEM et SPM [3][4], [12][13]. Les résultats de simulations seront alors confrontés à des mesures terrain (Pyla, Death Valley, Mojave) et exploités pour l'interprétation d'images SAR (AIRSAR, JPL). L'objectif à terme est d'exploiter les propriétés des roches salines dans les applications de détection de résurgences d'eau tant pour les surfaces terrestres que dans le cadre de l'exploration martienne (la présence d'évaporites à la surface de la planète rouge étant aujourd'hui communément admise).

II. Contexte géologique : les roches salines ou évaporitiques

Les évaporites sont des roches sédimentaires résultant quasi-intégralement d'une précipitation chimique de substances dissoutes dans des solutions naturelles (complexes géodynamiques continentaux ou marins) par augmentation de leurs concentrations par apports terrigènes et évaporation [START_REF] Rouchy | Les Evaporites[END_REF]. Le principal facteur de concentration des saumures réside dans le processus d'évaporation bien que la congélation et l'hydrothermalisme conduisent également à des conditions sursaturées nécessaires à la précipitation minérale. La formation et la paragénèse minérale des dépôts salins sont donc étroitement liées aux propriétés physico-chimiques des minéraux en solution (en terme de solubilité) ainsi qu'aux paramètres propres des environnements évaporitiques (température, restriction, salinité, taux d'évaporation, différentiel hydrostatique, pH, activité microbienne).

III. Modèles de mélanges diélectriques

L'influence des dépôts salins dans les applications de télédétection radar réside dans le caractère soluble et les propriétés ioniques des phases minérales les constituant (salinité) qui conditionnent la conductivité de la solution mère. Plus spécifiquement, " " " "'' étant proportionnelle à la conductivité, nous avons cherché à évaluer l'impact de la présence de sels sur les propriétés diélectriques d'un milieu.

Proposant une interprétation multi-phase des mélanges (particules de sol, eau libre, eau liée, air, sels), nous avons initialement considéré les lois de mélanges diélectriques développées par Dobson [9] et Wang [19] pour étudier l'influence de la salinité sur la permittivité complexe de matériaux géologiques. Dans un premier temps, ces modèles ont été appliqués au cas d'un mélange sable/eau salée, pour notre site test de la dune du Pyla. L'eau de mer étant majoritairement constituée de NaCl, nous avons notamment considéré les résultats obtenus sur des solutions de NaCl comme première approximation permettant d'appliquer les équations de Stogryn [3,10] pour la caractérisation électromagnétique de l'eau de mer [START_REF] Hasted | [END_REF].

Contrairement au modèle de Dobson, le modèle semi-empirique proposé par Wang à 1.4 et 5 GHz permet de distinguer 2 régions distinctes dans les variations de la constante diélectrique en fonction du taux d'humidité m v du mélange. Lorsque m v < W t , W t étant l'humidité de transition, les molécules d'eau sont supposées être étroitement liées aux particules solides de sol. On parle d'eau liée ou adsorbée. Par comparaison aux molécules de glace, les travaux de Wang ont permit d'établir une similitude dans les valeurs d'énergie d'activation. En conséquence, nous considérerons les valeurs diélectriques de la glace comme première approximation de celles de l'eau adsorbée pour m v < W t . A l'opposé, lorsque m v > W t , l'eau est alors considérée comme libre et ses propriétés diélectriques peuvent être décrites au moyen des équations classiques de la théorie de Debye pour un milieu polaire.

Adoptant une description du mélange comme un système à 4 composantes (eau adsorbée, eau libre, air et sol sec), les expressions des constantes diélectriques complexes relativement à chaque région s'écrivent [19]:

( ) ( ) r a v v P m P m " " " # + # + = 1 , ( 1
)
pour m v < W t , avec ( ) $ " " " " % % # + = t v i w i x W m (2) et ( ) ( ) ( ) r a v w t v x t P m P W m W " " " " " # + # + # + = 1 (3) pour m v > W t , avec ( )$ " " " " i w i x # + = (4)
où P est la porosité du mélange. " a , " w , " r , et " i sont les constantes diélectriques respectivement de l'air, de l'eau, des particules solides de sol et de la glace. " x correspond à la permittivité complexe de l'eau adsorbée. Les paramètres W t et $ étant des paramètres dépendant de la texture du sol considéré (pourcentage volumique de sable, sel, argile...), nous avons considéré pour ces paramètres les valeurs déterminées en laboratoire sur des échantillons de la dune du Pyla.

Afin de tenir compte des pertes dues à la conductivité ionique des échantillons résultant de la présence de sels en solution (composante d'eau libre), la constante diélectrique de la solution de NaCl utilisée a été déterminée au moyen du modèle de Debye modifié par Lane et Saxton [START_REF] Lane | Proc. Roy. Soc[END_REF]. En accord avec la formulation de Stogryn, les parties réelles et imaginaires de la solution saline sont données par [3,10]

: 2 ' ) 2 ( 1 f sw sw swo sw sw &' " " " " # # + = ( ( (5)
o i sw sw swo sw sw f f f " & ! &' " " &' " 2 ) 2 ( 1 ) 2 ( 2 "
+ # # % = ( (6)
où ' sw et ! i représentent respectivement le temps de relaxation et la conductivité ionique de la solution concentrée de NaCl, et dépendent de la salinité et de la température [10].

La permittivité complexe du mélange sable/eau saline a été calculée en fonction de la fréquence (Bandes L et C), du taux d'humidité (0<m v <0.6) et de la salinité (0<S<140‰). La température a été fixée à 20°C, la densité du mélange estimée à 1.74g.cm -3 , et la densité spécifique de la fraction solide fixée à 2.65g.cm -3 . Les autres constantes correspondant à celles trouvées dans la littérature [3,9,10].

Effets de la salinité sur la constante diélectrique :

Les premiers résultats montrent que si les parties réelle et imaginaire augmentent logiquement avec le taux d'humidité, l'impact de la salinité n'est pas le même pour " " " "' et " " " "''. Concernant la partie réelle " " " "', les résultats présentés en Fig. 1a montrent une faible dépendance de " " " "' à la salinité excepté pour des taux d'humidité élevés (m v > 0.2) pour lesquels " " " "' décroît lorsque la salinité augmente. Pour de faibles valeurs de salinité, l'augmentation du taux d'humidité constitue le principal facteur de variation de "

" " "'. Par opposition, les résultats de modélisation indiquent que la partie imaginaire " " " "" est fonction non seulement de la salinité mais également du taux d'humidité du mélange. Plus particulièrement, il apparaît que plus le taux d'humidité est élevé et plus l'effet de la salinité sur " " " "'' est important. "

" " "'' étant proportionnel à la conductivité de la solution de NaCl, cette tendance peut être expliqué par une augmentation de la composante d'eau libre autorisant une plus grande concentration de sels dissous et donc une conductivité plus forte de la solution. Plus précisément, il apparaît que pour de faibles valeurs d'humidité, l'eau contenue dans le mélange se présente principalement sous forme d'eau liée. Il en résulte une faible variation des paramètres diélectriques du mélange dans la mesure où les propriétés diélectriques de l'eau liée sont approximées par celles de la glace. Pour des valeurs croissantes de m v , la composante d'eau libre devient plus importante autorisant une quantité croissante de sels en solution se traduisant par une augmentation de la conductivité.

La Fig. 1a montre également une diminution de la partie imaginaire lorsque la salinité augmente (S > 100‰) ce qui peut être corrélé à la précipitation des sels en solution contribuant à une diminution de la conductivité de la composante d'eau libre. Cette tendance confirme celle rapportée dans les travaux récents de Mironov [11] sur de la bentonite , Shao [START_REF] Shao | [END_REF] sur des solutions de NaCl, et Aly [START_REF] Aly | EARSeL Proceedings[END_REF] sur des échantillons de sols argileux.

Effets de la fréquence sur la constante diélectrique :

La conductivité dépendant de la fréquence [20 -22], nous avons cherché à évaluer l'impact de la fréquence sur les propriétés diélectriques du mélange au moyen du modèle de Wang. Si les résultats relatifs à la partie réelle (Fig. 1b) montrent que " " " "' décroît faiblement lorsque la fréquence augmente (indépendamment de la salinité, Fig. 2a), les résultats les plus pertinents concernent la partie imaginaire liée à la conductivité ionique de la solution saline. Comme le montre la Fig. 2b," " " "" décroît fortement dans la bande [1][2][3][4]. Cette tendance, également observée par d'autres auteurs sur des solutions de NaCl, de kaolinite, ou montmorillonite [START_REF] Shao | [END_REF][START_REF] Komarov | IGARSS'99[END_REF], peut être attribuée au temps de relaxation de la solution saturée. En accord avec la théorie de Debye-Falkenhagen [22], la relation entre "

" " "" et la fréquence peut être reliée aux variations fréquentielles de la conductivité ionique qui décrit le mouvement des ions dans la solution électrolyte. Plus spécifiquement, ces auteurs invoquent l'effet dynamique de la relaxation d'une atmosphère ionique (nuage de charges de signe opposé entourant un ion central) sur le déplacement d'un ion central. Sous l'effet d'un champ électrique, le déplacement de l'ion induit une force électrique de relaxation exercée par l'atmosphère ionique (devenue asymétrique) et s'opposant au déplacement de l'ion. Sous l'action d'un champ électrique oscillant, l'ion central oscille et l'atmosphère ionique atteint plus rapidement la relaxation. Il en résulte une diminution de l'intensité de la force de relaxation autorisant une plus grande mobilité de l'ion et donc une augmentation de la conductivité. Les basses fréquences favorisant le phénomène de relaxation (la période d'oscillation du champ électrique est grande devant le temps de relaxation), on observe logiquement une augmentation de la conductivité (et donc de "

" " "") à basse fréquence. Lorsque la fréquence augmente, l'amplitude d'oscillation de l'ion central est plus faible qu'à basse fréquence. L'ion central, de même que l'atmosphère ionique, peut alors être considéré comme statique conduisant à une diminution de la conductivité (par réduction de la mobilité ionique) et incidemment de la partie imaginaire de la permittivité complexe comme l'illustre la Fig. 2b.

IV. Protocole expérimental

Afin de déterminer la validité du modèle de mélange diélectrique précédent, nous avons réalisé une série de mesures de permittivité sur le mélange sable/eau saline pour les mêmes bandes de fréquence, et les mêmes valeurs d'humidité et de salinité. Les mesures ont été réalisées au moyen d'un analyseur de réseau vectoriel Anritsu37325A couplé à une sonde à effet de bout (de type SMA) fournissant le coefficient de réflexion S11 (en module et phase) de l'onde électromagnétique à la surface des échantillons [16] et dont sont extraits les paramètres de la sonde. La connaissance de ces paramètres permet alors de remonter aux parties réelle et imaginaire de la permittivité du matériau mesuré au moyen d'un modèle capacitif d'inversion (Fig. 3a et 3b). Si les résultats expérimentaux confirment la tendance théorique précédente sur le comportement des parties réelle et imaginaire, ils soulignent néanmoins les limitations du modèle de Wang pour la caractérisation de " " " "' à basse fréquence ([1-2 GHz]). Comparativement aux Figs. 1b et 4, les résultats de mesures indiquent que le modèle de Wang tend à sous-estimer les valeurs des parties réelle et imaginaire. Il conviendra donc d'apporter des modifications aux lois de mélange diélectrique par calibration au moyen de séries de mesures en laboratoire. Néanmoins, les mesures réalisées en laboratoire faisant apparaître une valeur d'humidité de transition (W t ~29%, cf. Fig. 3), elles confortent l'approche bimodale du modèle de Wang.

V. Simulations numériques du coefficient de rétrodiffusion radar

Afin d'estimer l'impact de la salinité sur les performances de systèmes SAR aéroportés ou orbitaux, nous avons modélisé les coefficients de rétrodiffusion en fonction des valeurs de permittivité complexes mesurées précédemment. Considérant des surfaces lisses (écart type des hauteurs de 0.3 cm, longueur de corrélation de 2.7 cm), nous avons utilisé les modèles de rétrodiffusion IEM et SPM. Supposant initialement le terme surfacique, le coefficient de rétrodiffusion radar par réflexion simple s'écrit: pour le modèle SPM. pp indique l'état de polarisation de l'onde en émission/réception (HH ou VV), ) est l'angle d'incidence, k le nombre d'onde, W n la transformée de Fourier de la puissance n ième de la fonction d'autocorrélation et * pp les coefficients de réflexion de Fresnel [3,4].

Les résultats présentés en Fig. 5 indiquent que la sensibilité du coefficient de rétrodiffusion radar à la salinité dépend du taux d'humidité. Cette sensibilité est plus marquée en polarisation verticale (VV). Bien que cette sensibilité affecte plus faiblement la polarisation horizontale (HH) notamment pour de forts taux d'humidité, la forte dépendance du coefficient de rétrodiffusion à la salinité pour de faibles valeurs d'humidité constitue un résultat d'importance pour les applications de détection de faibles résurgences d'eau. En supposant une dynamique de détection à -30dB pour un système radar orbital, ce résultat est particulièrement favorable à l'exploration martienne où la présence d'évaporites est communément admise [17] et où les variations d'humidité envisagées n'excèdent pas quelques pourcents.

VI. Travaux futurs

Nous avons considéré ici l'influence de la salinité sur le coefficient de rétrodiffusion. La différence de phase copolaire pouvant être utilisée dans la détection d'humidité des sous-sols [1,18], nous allons également étudier l'impact de la salinité sur les variations de la phase radar. Nous travaillons aussi au développement d'une méthode d'inversion des paramètres diélectriques au moyen du code numérique HFSS (High Frequency Structure Simulator).

Fig.

  Fig. 1a (à gauche) : Permittivité complexe dérivée du modèle de Wang à 1.5 GHz pour un mélange sable/eau salée. Fig. 1b (à droite) :Modélisation de la variation fréquentielle de la partie réelle de la constante diélectrique pour une salinité de S = 100‰.

Fig. 3 :

 3 Fig. 3 : Mesures de la constante diélectrique (partie réelle : Fig. 3a à gauche et partie imaginaire : Fig. 3b à droite) réalisées sur un mélange sable/eau salée en fonction de la fréquence et du taux d'humidité. La salinité de la solution saturée est de S = 100‰.

Fig. 4 (

 4 Fig. 4 (à gauche) : Modélisation de la variation fréquentielle de la partie imaginaire de la constante diélectrique pour une salinité de S = 100‰ et différentes valeurs d'humidité. Fig. 5 (à droite) : Modélisation IEM de coefficient de rétrodiffusion en bande L (1.3 GHz) et 40° d'incidence.


Solving the real-time Railway Traffic Management Problem with Benders decomposition

Kaba KEITA 1 , Paola PELLEGRINI 2 , Joaquin RODRIGUEZ 1 .

1 Univ Lille Nord de France, F-59000 Lille, IFSTTAR, COSYS, ESTAS, F-59650 Villeneuve D'Ascq 2 Univ Lille Nord de France, F-59000 Lille, IFSTTAR, COSYS, LEOST, F-59650 Villeneuve D'Ascq {kaba.keita, paola.pellegrini, joaquin.rodriguez}@ifsttar.fr

Mots-clés : real-time railway traffic management problem, MILP, Benders decomposition.

Context and contribution

In railway traffic, at peak hours, the infrastructure is extensively exploited for ensuring the trains circulation. It means that many trains travel within short time through critical points. If a disruption occurs, the traffic may be perturbed and, as a result, conflicts may emerge. In a conflict, multiple trains may claim the same track section concurrently. Hence, some trains must be stopped or decelerated for ensuring safety, and delays occur. The emergence of conflicts is particularly critical at junctions, which are locations where multiple lines cross. There are two kinds of delay : primary and secondary delay. The primary delay is the result of unexpected events which disturb the traffic. Due to the interaction between trains, this primary delay may be propagated to other trains causing secondary delay. The primary delay cannot be prevented because we don't have means to avoid unexpected events. However, the secondary delay can be avoided or reduced by suitably managing traffic. Modifying trains route and schedule to limit delay propagation in the network is the focus of the real-time Railway Traffic Management Problem (rtRTMP). It is the problem tackled by dispatchers. They tackle this problem manually, so the result of their choices is generally suboptimal. The use of automatic tools to support dispatchers decision making is crutial to ensure an effective traffic management when disruptions occur. Some optimization algorithms already exist to tackle the rtRTMP. However, they can hardly solve very large instances.

Two models can be used to represent the infrastructure of the rtRTMP : macroscopic and microscopic. In the former, the infrastrure is viewed as a set of nodes (junctions) connected by links and the separation between trains is imposed through the control of generic headway times. In the latter, the infrastructure is viewed as a set of track sections where the train separation is imposed according to the signaling system, as it happens in reality. With the macroscopic model, we can solve very large instances, but with low precision at a local level ; hence, the optimization choices may have unexpected effects on traffic when they are actually implemented, due to the specific signaling system. With the microscopic model, these unexpected effects are avoided by considering in the optimization all necessary details. However, solving large instances may become very difficult due to memory or computational time limits. In this work, we consider a state-of-the-art mixed integer linear programming formulation tackling the rtRTMP based on a microscopic model, and we propose a Benders decomposition to increase the size of the instances which can be effectively tackled.

Benders decomposition for the rtRTMP

In the rtRTMP litterature, few papers deal with the need of takling very large instances through a decomposition method. Some papers, as [START_REF] Pranzo | An Advanced Real-Time Train Dispatching System for Minimizing the Propagation of Delays In a Dispatching Area Under Severe Disturbances[END_REF], propose heuristic approaches to decompose the instances to be solved. Others, as [START_REF] Lusby | A Set Packing Inspired Method for Real-Time Junction Train Routing[END_REF], propose classic decomposition approaches as column generation. To the best of our knowledge, only [START_REF] Lamorgese | An Exact Decomposition Approach for the Real-Time Train Dispatching Problem[END_REF] proposes a Benders decomposition approach to solve the rtRTMP. In the paper, the authors combine a macroscopic and a microscopic model to perform a decomposition of the initial problem into two subproblems (master and slave problem). This approach allows dealing with instances representing a big infrastructure but it does not consider the actual details on the microscopic infrastructure characteristics. In this paper, we propose a Benders decomposition approach applied to a model considering all these microscopic characteristics. We use as the model to be decomposed the mixed integer linear programming formulation RECIFE-MILP, proposed by [START_REF] Pellegrini | RECIFE-MILP : An Effective MILP-based Heuristic for the Real-Time Railway Traffic Management Problem[END_REF].

Solution procedure

The definition of the structure of the master and the slave problems is the first task to be performed in Benders decomposition applications. We consider the rtRTMP as the combination of a routing and a scheduling problem. We keep the routing decisions in the master problem, and we delegate the scheduling decisions to the slave one.

The master problem is the real-time train routing problem, it contains the routing variables (binary variables) and one dummy variable representing the contribution of continuous variables to the master problem objective function. Once this master problem is solved, the solution is sent to the dual of the slave problem. This solution is a specific route assignment for each train in the instance. The slave problem is the real-time relaxed train scheduling problem. After sending the solution of the master problem, we solve the dual of the slave one and we add the optimality cut to the master problem to cut off the current solution, if suboptimal. This process is repeated until the algorithm converges to an optimal solution or the maximum computational time imposed by the real-time nature of the problem (3 min) has elapsed.

By applying the described Benders decomposition approach to RECIFE-MILP, we tackle instances representing traffic in the junction of Gonesse, in France. The results are promising.

Conclusion and future work

In this work, we addressed the solution of the real-time Railway Traffic Management Problem using a Benders decomposition approach. The decomposition algorithm is applyed to the RECIFE-MILP formulation of the problem. In future work, we will solve other instances to evaluate the effectiveness and the efficiency of our Benders decomposition approach. We plan also to use other decomposition methods, as column generation and Lagrangian decomposition, to compare their performance and to identify the one that is the most suitable for the specific problem tackled.


Kaba Keita
email: kaba.keita@ifsttar.fr

Paola Pellegrini
email: paola.pellegrini@ifsttar.fr

Joaquin Rodriguez
email: joaquin.rodriguez@ifsttar.fr

Keita

Kaba

Paola, RODRIGUEZ, Joaquin Pellegrini

A decomposition approach for the real time Railway Traffic Management Problem

Mots-clés : real-time railway traffic management problem, MILP, Benders algorithm.

In critical points and at rush hours, the traffic in the rail network is often very heavy. Hence, when a disruption occurs and the traffic is perturbed, conflicts may emerge: two or more trains traveling at the planned speed would claim the same portion of track concurrently. In case of conflict, some trains must be stopped or decelerated for ensuring safety, and delays propagate. The real-time Railway Traffic Management Problem (rtRTMP) aims to modify trains route and schedule to limit delay propagation in the network. In the practice, this problem is tackled by dispatchers. They tackle it manually, so the result of their choices is generally suboptimal. The use of an efficient algorithm to support dispatchers decision making is crucial to ensure an effective traffic management when disruptions occur. The design of this efficient algorithm is typically based on two mains models used to represent the railway infrastructure: macroscopic and microscopic. In the macroscopic model, the infrastructure is seen as a set of nodes (junctions or stations) connected by lines, and the separation between trains is imposed through the control of generic headway times. In the microscopic one, the infrastructure is seen as a set of track sections where the train separation is imposed according to the signaling system, as it happens in reality. With the former, we can solve very large instances, but with low precision at the local level; hence, the optimization choices may have unexpected effects on the traffic when they are actually implemented, due for example to the specific signaling system in place. With the latter, these unexpected effects are avoided by considering in the optimization all necessary details. However, solving large instances may become very difficult due to memory or computational time limits.

In the rtRTMP literature, few papers deal with the need of tackling very large instances microscopically by using a decomposition method. Some papers, as [START_REF] Pellegrini | An advanced real-time train dispatching system for minimizing the propagation of delays in a dispatching area under severe disturbances[END_REF], propose heuristic approaches to decompose the instances to be solved. The authors decompose large instances of the rtRTMP by dispatching areas and apply a bi-level optimization approach to solve the problem. At the lower level, dispatchers manage traffic in their control areas without any knowledge of the traffic flow elsewhere. At the higher level, coordinators are responsible for the traffic management over a railway network including several areas with a global vision of the traffic flows. Others, as [START_REF] Lusby | A set packing inspired method for real-time junction train routing[END_REF], propose classic decomposition approaches as column generation. This column generation approach is applied to a set packing model to tackle real time train routing at junctions. The set packing model of the problem is formulated as an integer linear program with a resource based constraint system. A Benders decomposition approach is proposed by [START_REF] Lamorgese | An exact decomposition approach for the real-time train dispatching problem[END_REF] to solve the rtRTMP. In the paper, the authors combine a macroscopic and a microscopic model to perform a decomposition of the initial problem into two subproblems (master and slave problem). This approach allows dealing with instances representing a big infrastructure but it does not consider the actual details on the microscopic infrastructure characteristics. In this paper, we propose a Benders algorithm applied to a model considering all these microscopic characteristics. We use as the model to be decomposed the mixed integer linear programming formulation RECIFE-MILP, proposed by [START_REF] Pellegrini | RECIFE-MILP: An effective MILPbased heuristic for the real-time railway traffic management problem[END_REF].

In our Benders algorithm train routing and scheduling decisions are made in the master problem. Given these decisions, we compute the trains actual arrival times in the dual of the slave problem to deduce the total delay. Based on the result of the dual, we add an optimality or feasibility cut to the master problem to cut off the current solution, if suboptimal or infeasible for the overall problem. This process is repeated until the algorithm converges to an optimal solution or a maximum computational time imposed by the real-time nature of the problem has elapsed.

We assess the performance of our Benders algorithm with respect to the RECIFE-MILP algorithm of [START_REF] Pellegrini | RECIFE-MILP: An effective MILPbased heuristic for the real-time railway traffic management problem[END_REF]. We consider a case-study representing traffic in the Rouen-Rive-Droite control area to run our experiments. This case-study is recognized to be difficult to tackle in the time limit imposed by the rtRTMP [START_REF] Pellegrini | RECIFE-MILP: An effective MILPbased heuristic for the real-time railway traffic management problem[END_REF]. We set the computational time available for the optimization to five minutes. The implementation is done using IBM ILOG CPLEX Concert Technology for C++ (IBM ILOG CPLEX version 12.6 [5]).

We consider a one-day timetable, and we create 100 random scenarios: 20% of trains, randomly selected, suffer a random delay between 5 and 15 minutes at their entrance in the control area. We generate one rtRTMP instance from each of these 100 scenarios by considering all the trains entering the control area within an hour horizon. We set the time horizon from 6:00 am to 07:00 am. This time horizon corresponds to the morning peak hour. The so obtained onehour instances include between 10 and 13 trains (mean 11). Each train can use between 1 and 192 routes (mean 45).

The results show that the RECIFE-MILP algorithm achieves the best performance for more cases than the Benders algorithm: 96 versus 4. For the instances on which the Benders algorithm is the best, we discover that the percentage of optimality cuts with respect to the total number of Benders cuts is very high: 97% in average. Instead, when the RECIFE-MILP algorithm is the best, we remark that this percentage decreases: 85% in average. Hence, we conjecture that the performance of the Benders algorithm would improve if the percentage of the optimality cuts generated during the Benders iterations increased. In a future work, we will focus on how to generate strong valid inequalities in the Benders master problem. These inequalities must make the dual of the Benders sub-problem bounded and warrant the generation of the optimality cuts.


Diego Arenas
email: diego.arenas@ifsttar.fr

Paola Pellegrini
email: paola.pellegrini@ifsttar.fr

Saïd Hanafi
email: said.hanafi@univ-valenciennes.fr

Joaquin Rodriguez
email: joaquin.rodriguez@ifsttar.fr

Train timetable rearrangement facing infrastructure maintenance activities

Keywords: train rescheduling, timetable rearrangement, infrastructure maintenance, MILP

Introduction

The performance of railway infrastructure maintenance activities (MAs) consumes an important part of the railway capacity of a network. Indeed, MAs directly or indirectly affect the circulations of trains in the network, either by banning or by restraining them in some locations, i.e., MAs are infrastructure capacity consumers. To optimize the capacity exploitation, an efficient coordination between MAs and trains is required [START_REF] Albrecht | Rescheduling rail networks with maintenance disruptions using problem space search[END_REF][START_REF] Forsgren | Maintaining tracks and traffic flow at the same time[END_REF].

In general, the MAs plan is considered during the timetable design. However, unforeseen MAs may emerge at any time, e.g., due to a device malfunction or an accident. When an unforeseen MA is introduced, the timetable may need to be adapted.

A typical example consists on the performance of a MA in a track segment of a doubletrack line connecting two stations. Train circulations are not allowed in the track where the MA takes place, while the adjacent track can be used for traffic in both directions provided that a temporal speed limitation is respected. A common approach applied in practice to overcome this situation is the use of a train batteries. In essence, this approach forms several groups of trains travelling in the same direction, which are called batteries. Then batteries use the available adjacent track in turns, one per direction. This straightforward approach allows a more efficient capacity exploitation than a first-come first-serve strategy which is still employed in several railway systems.

Problem Formulation

To tackle the problem of rearranging a timetable to cope with infrastructure maintenance activities, we present RECIFE-MAINT, a MILP formulation based on a microscopic representation of the infrastructure. Trains are allowed to be rerouted and rescheduled to cope with MAs. However, trains can not be advanced or cancelled because this problem occurs in a preoperational level, i.e., the timetable is already published. Moreover, we consider the planning of maintenance trains and the temporary speed limitations imposed by the MAs.

As trains are rescheduled and rerouted, delays may be introduced. The objective of the problem is to minimize the overall delay suffered by all trains. More specifically, the objective is: Find a new timetable that is compatible with all MAs and minimizes the weighted sum of arrival time delays. This objective is formalized in (Equation 1). Here, T is the set of trains, S t is the set of intermediate stops of train t, δ t,s is the arrival time delay of t at intermediate stop s, and w t,s is the weight associated to a late arrival of t to s.

We propose an algorithm implementing RECIF-MAINT which is used for our experiments. Moreover, we propose another algorithm which emulates the batteries approach to compare the quality of the solutions obtained by RECIFE-MAINT with respect to the current practice. min t∈T s∈St w t,s δ t,s

(1)

Experimental Results

We model approximately 70 km of the French railway infrastructure (between Rosny-sur-Seine and Saint-Etienne-du-Rouvray). This line segment contains 10 stations. We define 5 initially unplanned MAs: MA_01 to MA_05, with an approximate length of 11, 0.5, 12, 0.5 and 1 Km, respectively. We define 3 possible durations for each MA: 60, 90 and 120 minutes. In total, we tackle 150 instances, 10 instances per combination MA-duration. Our algorithms are implemented in C++ and use CPLEX 12.6 solver. The computational time limit is set to 1 hour. The results, summarized in Table [START_REF] Albrecht | Rescheduling rail networks with maintenance disruptions using problem space search[END_REF], show that our algorithm obtains at least a feasible solution for all the tacked instances. Moreover, 75% of these solutions are proven optimal.

Class

Trains

Conclusion and Perspectives

We introduce RECIFE-MAINT, a MILP formulation to tackle the problem of timetable rearrangement to cope with MAs. We consider specific aspects of the problem that are often disregarded: the planning of maintenance trains and the temporary speed limitations.

The results presented show that our algorithm implementing RECIFE-MAINT obtains good quality solutions in a practical computational time. Moreover, the solutions proposed are in mean 47% better, in terms of accumulated trains' delay, than the solutions obtained by the algorithm emulating the current practice.

Perspectives of future work include the exploration of other methods to reduce the computational time, e.g., hybrid meta-heuristics. Furthermore, we aim to study the possibility of MA rescheduling, which may lead to a better capacity exploitation: MAs may be scheduled in a time period which minimizes the impacts on train circulations.