Sébastien Lannez

Christian Artigues

Jean Damay

Michel Gendreau

A railroad maintenance problem solved with a cut and column generation matheuristic

Keywords: arc routing, column generation, cutting planes, matheuristic, railtrack maintenance

In this paper we address a real life optimization problem, the Rail Track Inspection Scheduling Problem (RTISP). This problem consists of scheduling railway network inspection tasks. The objective is to minimize the total deadhead distance while performing all inspection tasks. Different 0-1 integer formulations for the problem are presented. A heuristic based on both Benders and Dantzig-Wolfe decompositions is proposed to solve this rich arc routing problem. Its performance is analyzed on a real life dataset provided by the French national railway company (SNCF). The proposed algorithm is compared to a dynamic programming-based heuristic. Its ability to schedule the inspection tasks of one year on a sparse graph with thousand nodes and arcs is assessed.

Introduction

One of the major problems that railway companies have faced since the very beginning are failures in tracks. Defects in rails, the basic parts of a track, may result in serious accidents. Réseau Ferré de France (RFF), the company that owns and manages the French railway infrastructure, has delegated a part of the railway maintenance responsibility to the Société Nationale des Chemins de Fers (SNCF), a French railway company. SNCF is committed to ensure the safety of the railway network. One of the maintenance activities is to prevent track failures. In order to quickly inspect the French network, SNCF is using ultrasonic defectoscopy to detect and survey imperfections in rails.

Inspection frequencies range from six months to twenty years depending on the train speed and the cumulated weight of the considered track type. Two third of the total inspections (35 000 km) are performed on tracks which should be visited once or twice a year. These tracks are called primary tracks. All the remaining inspections (secondary tracks) have much lower inspection frequencies. The subject of the present study is the primary track inspection scheduling problem. This problem is currently solved in a centralized way by the SNCF national logistics department while inspection of secondary tracks, which is less critical, is decomposed geographically into several sub-problems, each being solved by a local logistics department.

Ultrasonic inspections are performed with specialized rolling stock units, which will be called vehicles in the remaining of the text. Vehicles differ from one another in maximum speed and working capacity. The detection of defects inside the track is performed by a reverberation analysis of the ultrasonic waves passing through the rails. The inspection of primary tracks is subject to several limitations due to vehicle usage. First, a vehicle's speed depends on whether it is inspecting or not. A deadhead trip is a trip during which the vehicle is moving without inspecting the track. During inspection, speed can be more than three times slower than during a deadhead trip. The second limitation is due to the team working inside the vehicle (driver and technicians). There is a maximum shift duration and a vehicle can move during at most six hours per day. As a third limitation, there is a maximum daily inspection distance. Water is needed to keep sensors and rails coupled during the measurements. The inspection distance is limited by the water tank capacity. These tanks can only be refilled at special stations. Over the 200 stations on the primary tracks, only 90 are equipped with water supply. Furthermore, water tank refill is time consuming and may need available operators at the station. Hence, it is not desired to do more than one refill per shift. That is why the problem is structured in such a way that each vehicle starts and ends each shift at a refill node. A fourth limitation is that, for organizational purposes, vehicle maintenances should be performed periodically at specific stations. Last, as the same vehicles are used for secondary track inspection, each vehicle must be made available to local logistics departments and, to that purpose, has to be sent to other specific station during predefined periods. The inspection activity is also limited by the existence of track outages, that can alter the vehicle speed or even prevent it from circulating during specific periods.

The problem SNCF is dealing with is to visit the set of primary tracks taking into account the above-presented operational constraints and satisfying inspection frequencies.

The main cost indicator is a common logistic performance ratio for each vehicle which is equal to the amount (in distance) of tracks that have been inspected, divided by the total traveled distance (on a yearly basis).

This problem can be modeled as an arc routing problem related to the ones describing road deicing, waste collection or network weeding as described in the surveys from [START_REF] Perrier | A survey of models and algorithms for winter road maintenance. Part I: system design for spreading and plowing[END_REF][START_REF] Perrier | A survey of models and algorithms for winter road maintenance. Part II: system design for snow disposal[END_REF][START_REF] Perrier | A survey of models and algorithms for winter road maintenance. Part III: vehicle routing and depot location for spreading[END_REF][START_REF] Perrier | A survey of models and algorithms for winter road maintenance. Part IV: vehicle routing and fleet sizing for plowing and snow disposal[END_REF]. It involves complicating constraints, among which limited shift duration, water supply, track outages and heterogeneous fleet, as described above. Another difficulty is the network size which makes it a real challenge to solve.

The remaining of this article is structured as follows. In Section 2, we briefly present the relevant literature about arc routing problems. In Section 3, we present the notation and describe mathematical formulations and decompositions of the problem. Section 4 is devoted to the presentation of a heuristic, which, being based on the considered mathematical decompositions, can be called a matheuristic [START_REF]Matheuristics: hybridizing metaheuristics and mathematical programming[END_REF]. In Section 5, an alternative dynamic programming-based heuristic is presented. In Section 6, we introduce the different considered real datasets and we provide computational results that demonstrate the ability of the proposed matheuristic to schedule the inspection tasks of one year on a sparse graph with some thousand nodes and arcs. In terms of performance, the matheuristic compares favorably with the heuristic based on dynamic programming, at the expense of additional CPU time. To further analyze the heuristic's behavior, a comparison between the obtained performance ratio and a linear programming relaxation-based upper bound is carried out. The impact of the heuristic components on the performance is also evaluated. Section 7 concludes the paper with considerations on the practical implementation of the method and perspectives for further research.

2 Literature review

Industrial arc routing problems

In [START_REF] Hasle | Industrial vehicle routing[END_REF], the authors state that industrial vehicle routing problems can be rich in the sense that "they include aspects of the VRP that are essential to the routing of vehicles in real-life".

Road related problems have supplied researchers with a lot of (rich) arc routing problems. A review of problems arising during winter road maintenances has been published in the articles [START_REF] Perrier | A survey of models and algorithms for winter road maintenance. Part I: system design for spreading and plowing[END_REF][START_REF] Perrier | A survey of models and algorithms for winter road maintenance. Part II: system design for snow disposal[END_REF][START_REF] Perrier | A survey of models and algorithms for winter road maintenance. Part III: vehicle routing and depot location for spreading[END_REF][START_REF] Perrier | A survey of models and algorithms for winter road maintenance. Part IV: vehicle routing and fleet sizing for plowing and snow disposal[END_REF][START_REF] Perrier | Vehicle routing for urban snow plowing operations[END_REF]. They also present industrial applications. Waste collection or postal deliveries are also an active field of arc routing problems. In [START_REF] Kim | Waste collection vehicle routing problem with time windows[END_REF], a description of a waste collection problem is presented. A nation wide postal delivery problem has been modeled as an industrial arc routing problem in [START_REF] Irnich | Solution of real-world postman problems[END_REF].

Arc routing problems

In this section, some arc routing problems and their applications are listed. For a more detailed description of them, books [START_REF] Raghavan | The vehicle routing problem: latest advances and new challenges[END_REF] and [START_REF] Dror | Arc routing: theory, solutions and applications[END_REF] and survey articles [START_REF] Eiselt | Arc routing problems, part I: the chinese postman problem[END_REF][START_REF] Eiselt | Arc routing problems, part II: the rural postman problem[END_REF] are a good introduction.

The RTISP is related with the capacitated arc routing problem (CARP), described in [START_REF] Golden | Capacitated arc routing problems[END_REF]. It consists in visiting a set of arcs with a single vehicle. Each visited arc reduces the remaining working capacity of the vehicle by a given amount. In the RTISP, tasks and deadhead circulations can be modeled with arcs. The working capacity of vehicles is constrained by the vehicle's water tank capacity and the duration of a shift. The capacitated arc routing problem with time windows (CARP-TW) extends the CARP by constraining the possible visits of arcs to a set of periods. Paper [START_REF] Johnson | Solving the capacitated arc routing problem with time windows using column generation[END_REF] contains a description of a column generation procedure. In [START_REF] Reghioui | GRASP with path relinking for the capacitated arc routing problem with time windows[END_REF], this is solved problem with a greedy randomised adaptive search procedure (GRASP) associated with path relinking. Another extension is the capacitated arc routing problem with intermediate facilities (CARP-IF) presented in [START_REF] Ghiani | The capacitated arc routing problem with intermediate facilities[END_REF] also called the the capacitated arc routing problem with refill points (CARP-RP) presented in [START_REF] Amaya | The capacitated arc routing problem with refill points[END_REF]. It extends the CARP by adding refill facilities to specific nodes.

We have not been aware of published work about methods for solving a problem having all these features. However, as the capacity of each vehicle is two-dimensional, the RTISP can be defined as a multi-capacitated arc routing problem with time windows, refill points and a heterogeneous fleet. In this section we start with providing preliminary definition and notations. Then, we propose three 0-1 formulations for the problem. The first one is an arc-flow model. The second one is obtained through a Dantzig-Wolfe decomposition of the first model and can be defined as a shift-flow model. The last one is obtained by applying a combinatorial Benders decomposition to the shift-flow model. The latter formulation yields an exact solving scheme consisting in solving iteratively the Benders master problem and the Benders sub-problems that also act as repairing methods for the master solution.

Definitions and notations

Modeling hypothesis Vehicle moves are modeled by arcs. They represent either inspection tasks, deadhead traversals of track portions, or complex moves like unit switch back or station traversal. Furthermore, arcs can represent deadhead trips from a node in the network to another node (for example to model a trip to a maintenance station which is not part of the inspected network). Arcs are suitable for the description of unidirectional railway tracks. As only primary tracks are directly modeled, bidirectional railway tracks are not considered in the study. Nodes describe stations, communication between railway tracks, or locations in the network where the vehicles can change their circulation mode. A map representing these tracks is presented in Figure 1a. A schematic zoom around Bordeaux is shown in Figure 1b. The presented graph represents the inspected railroad network. The arcs in dotted style represent inspection tasks to perform, and the other ones represent deadhead moves. The black node represents a refill station and the other nodes are normal stations without water facility.

In order to make the schedule being easily adapted during operations, multiple shifts per day are not allowed. As already mentioned, each shift consists of a trip between two refill stations with a total distance to inspect smaller than the maximal distance induced capacity of the water tank and a total trip duration smaller than the duration of a work shift. Given all the feasible shift paths, the RTISP becomes the problem of selecting and scheduling them in order to satisfy all inspections at the lowest cost.

Graph and vehicle representation

A multigraph G = (V, A) containing arcs (A) and nodes (V) models the railway network. Arcs can represent tasks (A * ), deadhead traversals (A d ) or waiting times (A W ). Note that a task arc represent either a track inspection task or a vehicle maintenance task or a vehicle requirement for secondary track inspection. An arc from node i to node j is denoted (i, j) * if it represents an inspection task and (i, j) d if it represents a deadhead trip. A waiting arc is a loop (i, i). Nodes can represent rest and refill stations (V r ), or communications between railroad tracks (V c ). For each vehicle, we assume that there exists a depot refill node D k ∈ V r from which the vehicle must start its trip and to which it must return.

The parameter d ak contains the time needed for vehicle k to traverse arc a. In practice, the average vehicle speed depends of multiple factors, such as the importance of the traffic in the considered track. In this study, the speed used for each vehicle is taken to be lower than the mean value computed during year 2009. This choice has been made in order to be able to use the schedule in practice. A waiting arc a ∈ A W has a unit time duration d ak = 1. The parameter l ak is the distance involved by the traversal of arc a by vehicle k. This parameter is actually vehicle-dependent for inspection arcs as the "distance" represents the water consumption, which may vary from one vehicle to the other. However, for deadhead arcs, this parameter can be considered as vehicle-independent as it represents the actual traveled distance. For each vehicle k, L k represents the maximum cumulated distance which can be inspected per shift and T k denotes the maximum working time during a shift. This time is different from the shift duration as waiting times are authorized and not included in the working time.

Calendar The calendar H is assumed to contain only working days. It is composed of integer values representing the number of "shift seconds" elapsed since the first period of the planning horizon. The need for small time slots comes from the wide range of task durations and the relatively high speed of vehicles (ranging from 20 km/h to 120 km/h). t is a time slot in H, s is the duration of a shift. We assume that |H| is a multiple of s and define S = {0, . . . , |H|/s -1} as the shift index set.

For example, consider a shift duration s =4 and an horizon H = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}. The shift index set is S = {0, 1, 2} corresponding to periods {1, 2, 3, 4}, {5, 6, 7, 8} and {9, 10, 11, 12}, respectively.

Track inspection is also time-constrained. Due to the small frequencies mentioned in Section 1, the planning period (less than one year) contains at most two inspections of the same track. Hence, periodicity is handled by assigning time windows to inspection tasks which sets a minimum time lag between two consecutive inspections (and also allows to consider the current state of the network). As mentioned in Section 1, maintenance tasks and local vehicle requirement tasks have also time windows. The subset H a,k ⊆ H contains the set of periods during which vehicle k can not traverse arc a. A period t ∈ H a,k reflects one of the following cases.

• The sub-network containing a is not accessible to vehicle k at period t due to a technical constraint or to a space-time vehicle preassignment.

• There is an outage on the track portion corresponding to arc a at period t.

• Arc a corresponds to a task and period t is outside its time window.

Costs

The objective being to minimize the total deadhead, the cost of an arc is the length of the arc if this arc is a deadhead one while no cost is considered when traversing a task arc.

c ak = l ak , if a ∈ A d , 0, else. (1)

Arc flow model

Using time discretization through calendar H, the problem can be represented as a multi-commodity flow problem on a space-time network with additional constraints. As mentioned above, the path of a each vehicle can be decomposed in shifts. A shift starts at a refill node v ∈ V r at the beginning of period 1 of the shift and ends at a refill node v ′ ∈ V r at the end of period s of the shift (with

possibly v = v ′ ).
For each shift index σ and each vehicle k ∈ K, we define a super-source o k σ with a set of additional arcs δ

+ (o k σ ) = {(o k σ , v)|v ∈ V r } and a super-sink d k σ with arcs δ -(d k σ ) = {(v, d k σ )|v ∈ V r }.
All these arcs have by convenience a duration equal to 1.

For each node v ∈ V, let δ σ,k- τ (v) denote the subset of arcs in A ∪ {(o k σ , v)} ending at v that can be traversed by vehicle k during period σs+τ . Symmetrically, let δ σ,k+ τ (v) denote the subset of arcs in A ∪ (v, d k σ ) starting at v that can be traversed by vehicle k during period σs + τ . These subsets reflect the constraints that arcs cannot be traversed during an unavailability period. For example, if, for a period τ and a vehicle k, there is an arc a and an unavailability period t ∈ H a,k in the interval [σs + τ -d ak + 1, σs + τ ], arc a is excluded from δ σ,k- τ (v). The same principle is applied to model the fact that the super-source and the super-sink can only be connected to refill nodes at the beginning and at the end of each shift, respectively. Let x kσ aτ denote the binary flow variable which equals 1 if vehicle k ∈ K starts traversing arc a ∈ A at the beginning of period t = σs + τ and ends traversing it at the end of period t + d ak -1, where σ ∈ S is the shift index and τ ∈ {1, . . . , s} is the shift period index. To represent the start and the end of each shift, we also introduce variables x kσ a0 for a ∈ δ + (o k σ ) and variables x kσ a,s+1 or a ∈ δ -(d k σ ). A shift is defined as a feasible time-stamped o k σ → d k σ path for a given vehicle k and a given shift index σ, visiting a certain number of required arcs. The set of feasible shifts for vehicle k and shift index σ is defined by the following integer points.

Q kσ = x kσ ∈ {0, 1} |A|×s x kσ satisfies (2) -(8) , k ∈ K, σ ∈ S
where constraints (2)-( 8) are detailed hereafter.

a∈δ + (o k σ )
x kσ a0 = 1 (2)

a∈δ -(d k σ )
x kσ a,s+1 = 1 (3)

a∈δ σ,k- τ -1 (v)
x kσ a,τ -d ak -

a∈δ σ,k+ τ (v) x kσ a,τ = 0 v ∈ V, τ ∈ {1, . . . , s + 1} (4) s τ =1 x kσ aτ ≤ 1 a ∈ A * (5) a∈A * s τ =1 l ak x kσ aτ ≤ L k (6) a∈A s τ =1 d ak x kσ aτ ≤ T k (7) x kσ a,τ ∈{0, 1} a ∈ A, τ ∈ {1, . . . , s} (8)
Constraints ( 2) and ( 3) enforce each shift to start and end at a refill node (as only refill nodes are connected to the super-source and to the super-sink). Constraints (4) ensure flow conservation at each node. Constraints (5) ensure that each task is at most performed once during a shift. Constraints [START_REF] Eiselt | Arc routing problems, part I: the chinese postman problem[END_REF] state that the maximum cumulated distance during a shift due to water capacity in inspection mode is not exceeded. Constraints [START_REF] Eiselt | Arc routing problems, part II: the rural postman problem[END_REF] limit the maximum working time during each shift. Note that to simplify the presentation, we assume that variables x kσ a,τ are equal to 0 for τ ≤ 0. From this model, it follows that a shift can be defined as a resource-constrained path in a time-space network where constraints (5-7) are the resource-constraints.

With Q kσ as defined before, the arc flow model (M arc ) is given by the following 0-1 formulation .

(M arc ) min a∈A σ∈S s τ =1 k∈K c ak x k,σ a,τ (9)
subject to

k∈K σ∈S s τ =1 x kσ aτ = 1 a ∈ A * (10)
x k0

(o k 0 ,D k ),0 = 1 k ∈ K (11) x k,|S|-1 (D k ,d k |S|-1 ),s+1 = 1 k ∈ K (12) x k,σ (v,d k σ ),s+1 -x k,σ+1 (o k σ+1 ,v),0 = 0 σ, σ + 1 ∈ S, v ∈ V r , k ∈ K (13) x kσ ∈ Q kσ σ ∈ S, k ∈ K (14)
Objective ( 9) minimizes the total cost. Constraints [START_REF] Ghiani | The capacitated arc routing problem with intermediate facilities[END_REF] state that each task must be performed exactly once. Constraints [START_REF] Golden | Capacitated arc routing problems[END_REF] ensure that each vehicle will leave its depot at the beginning of the first shift while constraints (12) make it return to the depot at the end of the last shift. Constraints (13) ensure flow conservation for each vehicle at each refill node between two consecutive shifts by enforcing that the first visited refill node of shift σ+1 is the last visited refill node of shift σ. Constraints ( 14) enforce the feasibility of each shift for each vehicle.

Consider the example network of Figure 2. Bold arcs represent inspection tasks while thin arcs represent deadhead trips. Loops are omitted. Nodes 1, 2 and 3 are assumed to be refill stations. There are two shifts of 4 time periods each. We assume there is an outage at time period t = 4 on both task arc (1, 2) * and deadhead arc (1, 2) d . Later, there is an outage at time periods t ∈ {7, 8} on task arc (3, 2) * and deadhead arc (3, 2) d . Arcs are labeled with the travel time, which is assumed to be equal to the cost for each deadhead arc. Suppose there is a single vehicle. [START_REF] Amaya | The capacitated arc routing problem with refill points[END_REF] 1

1 1 3 2 1 2 3 Figure 2: A simple network
The space-time networks corresponding to shifts σ = 0 and σ = 1 are represented in Figure 3. Each node is labeled with the node index v and the 5)- [START_REF] Eiselt | Arc routing problems, part II: the rural postman problem[END_REF] in each spacetime network maps the feasible shift set Q kσ . The differences between the two networks are caused by the unavailability periods, as no vehicle can traverse arcs (1, 2) d and (1, 2) * at time period 4 (impacting shift σ = 0) nor arcs (3, 2) d and (3, 2) * at time periods 7 and 8 (impacting shift σ = 1). The concatenation of the shift paths is a feasible solution to (M arc ) if all inspection tasks are covered (Constraints 10) and if the consecutive shifts end and start at the same node (Constraints 13). An example of feasible shifts (if the depot is refill node 3) is given by path 1, 1 → 2, 4 → 3, 5 for shift σ = 0 and 3, 1 → 2, 3 → 2, 4 → 1, 5 for shift σ = 1. Its total cost is equal to 2 (deadhead trips from 2 to 3 and from 2 to 1).

τ = 1 τ = 2 τ = 3 τ = 4 t = 1 t = 2 t = 3 t = 4 τ = 1 τ = 2 τ = 3 τ = 4 3,1 3,2 3,3 3,5 3,4 2,2 2,5 2,4 1,1 1,2 1,3 1,5 1,4 o k 0 2, 1 2, 3 d k 0 σ = 0 3,1 3,3 3,5 3,4 2,1 2,2 2,3 2,5 2,4 1,1 1,2 1,3 1,5 1,4 3,2 o k 1 d k 1 t = 5 t = 6 t = 7 t = 8 σ = 1

Dantzig-Wolfe decomposition and shift flow model

The arc flow model naturally decomposes into several problems (one per shift/ vehicle pair) which are linked through Constraints ( 10) and [START_REF] Irnich | Solution of real-world postman problems[END_REF]. Following the Dantzig-Wolfe decomposition principle, let us assume that the elements of Q kσ are indexed from 1 to |Q kσ | for each vehicle k ∈ K and for each shift index σ ∈ S. We introduce binary variables z kσ q equal to 1 if shift q is selected in Q kσ , and to 0 otherwise. Given all the sets of feasible trips between two refill stations (sets Q kσ ), vehicle circulation can still be modeled as a flow on a multicommodity network, in which each arc represents now a feasible shift. This yields a shift-flow model, with set partitioning constraints to model task covering.

Let L kσ q denote the sequence of visited arcs for shift q ∈ Q kσ . The cost of a shift is defined as follows:

c kσ q = a∈L kσ q c ak , k ∈ K, σ ∈ S, q ∈ Q kσ . ( 15
)
Let Q kσ a denote the subset of Q kσ containing shifts that visit arc a. Let Q kσ v+ (Q kσ v-) denote the subset of Q kσ containing shifts that start (end) at refill node v ∈ V r , respectively. The shift flow model (M shift ) is as follows:

(M shift ) min k∈K σ∈S q∈Q kσ c kσ q z kσ q (16) subject to k∈K σ∈S q∈Q kσ a z kσ q = 1 a ∈ A * ( 17
)
q∈Q k0 D k + z k0 q = 1 k ∈ K (18) q∈Q k,|S|-1 D k - z k,|S|-1 q = 1 k ∈ K (19) q∈Q k,σ+1 v+ z k,σ+1 q - q∈Q kσ v- z kσ q = 0 σ ∈ S \ {|S|-1}, v ∈ V r , k ∈ K (20) q∈Q kσ z kσ q = 1 k ∈ K, σ ∈ S (21)
z kσ q ∈ {0, 1} k ∈ K, σ ∈ S, q ∈ Q kσ (22)
The objective function [START_REF] Lannez | Optimisation des tournées d'inspection des voies ferroviaires[END_REF] ensures that from all feasible solutions the one with minimum total deadhead cost will be selected. Constraints [START_REF]Matheuristics: hybridizing metaheuristics and mathematical programming[END_REF] ensure that the set of selected shifts allows to perform all inspection tasks. Constraints [START_REF] Perrier | A survey of models and algorithms for winter road maintenance. Part I: system design for spreading and plowing[END_REF] and [START_REF] Perrier | A survey of models and algorithms for winter road maintenance. Part II: system design for snow disposal[END_REF] ensure that each vehicle starts and ends at its depot. Constraints [START_REF] Perrier | A survey of models and algorithms for winter road maintenance. Part III: vehicle routing and depot location for spreading[END_REF] ensure for each vehicle that two consecutive shifts end and start at the same node. Constraints [START_REF] Perrier | A survey of models and algorithms for winter road maintenance. Part IV: vehicle routing and fleet sizing for plowing and snow disposal[END_REF] enforce for each vehicle the assignment of exactly one shift per calendar day. Constraints [START_REF] Perrier | Vehicle routing for urban snow plowing operations[END_REF] ensure that solutions are integer. Remark that the mathematical program presented above contains an exponential number of columns. Its relaxation could be solved by column generation and integer solutions could be searched by branch-and-price techniques. In this paper we take advantage of the structure of the problem to further decompose the problem, as explained in the next section.

Combinatorial Benders decomposition

Motivation and principle We explain the proposed decomposition scheme by describing how the planning is actually performed manually by operators. When they are scheduling the inspection tasks, the operators do not take into account the precise due date of each task. Instead, they prefer using the spatial information related to each task. Time windows are enforced at the end of the planning process. A simple graphical representation of where and when the tasks should be performed actually highlights the correlation between space and time. This information has been used to design a Benders decomposition scheme applied to the shift flow model. The master problem of this decomposition consists in finding a subset of shift patterns which covers every task and which can hopefully be transformed in a feasible inspection tour. The sub-problem checks if this subset violates constraints of the complete mathematical problem. If this is the case, a combinatorial cut is generated and added to the master problem and the process restarts. Otherwise the problem an optimal solution for the problem was found.

Benders master problem If each set of unavailability periods H a,k is empty, each time-stamped path q ∈ Q kσ is valid for any other shift index σ ′ ∈ S by a simple translation of the shift start time from σs+1 to σs ′ +1. In presence of unavailability periods, this statement is not true in general but we can associate to each element q ∈ Q kσ a set of shift indices H q ⊆ S for which q is valid. With such a flexibility, all shifts q that can be obtained from one another by a shift period translation defines a unique shift pattern. Consider the example of Figure 3. Path 1, 1 → 2, 4 → 1, 5 is a valid shift pattern for shift indices σ = 0 and σ = 1. However, path 1, 1 → 2, 2 → 3, 3 → 2, 5 is valid for shift index σ = 0 while, even if we relax the constraint to finish the trip at the depot, this path is not valid for shift index σ = 1 due to the unavailability of track (3, 2) at periods 7 and 8.

Dropping index σ, we define Q k as the set of all shift patterns which are valid for vehicle k for at least one shift index σ ∈ S. According to expression [START_REF] Kim | Waste collection vehicle routing problem with time windows[END_REF], the cost of a shift is independent of σ. Let c k q denote the cost of shift pattern q ∈ Q k . We define Q k a as the subset of Q k containing shift patterns that visit arc a and

Q k v+ (Q k v-) as the subset of Q k containing shifts that start (end) at refill node v ∈ V r , respectively.
The principle of the Benders decomposition is to focus, in the master problem, on the selection of a set of shift patterns to cover all inspection tasks, without assigning the shift patterns to shift periods. The sub-problem aims, in a second phase, at finding a feasible schedule for the selected shift patterns. Let y k q denote a binary variable which takes value 1 if the shift pattern q is included in the path of vehicle k.

The Benders master problem (M Benders ), which is a set partitioning problem with additional constraints, can be written as follows:

(M Benders ) min k∈K q∈Q k c k q y k q (23) subject to k∈K q∈Q k a y k q = 1 ∀a ∈ A * ( 24
)
q∈Q k |ȳ k q =1 (1 -y k q ) + q∈Q k |ȳ k q =0 y k q ≥ 1 k ∈ K, ȳk ∈ I k (25) y k q ∈ {0, 1} k ∈ K, q ∈ Q k (26)
Objective [START_REF] Reghioui | GRASP with path relinking for the capacitated arc routing problem with time windows[END_REF] and Constraints [START_REF] Spoorendonk | Clique inequalities applied to the vehicle routing problem with time windows[END_REF] are the time-independent expressions of objective [START_REF] Lannez | Optimisation des tournées d'inspection des voies ferroviaires[END_REF] and Constraints [START_REF]Matheuristics: hybridizing metaheuristics and mathematical programming[END_REF], respectively. Constraints [START_REF] Spoorendonk | Clique inequalities applied to the vehicle routing problem with time windows[END_REF] state that all inspection tasks must be covered by the selected shift patterns. Constraints (25) are the combinatorial Benders cuts (or no-good cuts) as proposed in [START_REF] Codato | Combinatorial Benders' cuts[END_REF]. Set I k contains the set of shift pattern selections for vehicle k violating the constraints of the original mathematical problem which are not represented in the master problem. These sets are not known a priori, they are build at each iteration by solving the subproblem presented below. Each constraint (25) removes one solution of I k at a time.

Benders sub-problem Let ȳ be the solution of the master problem at some iteration. The Benders sub-problems, whose solutions determine if the partial solution from the master can be used to create a feasible inspection journey, can be split for each vehicle. A set of shift patterns Q k (ȳ) covering the required tasks has been selected by the master problem. The role of the sub-problem is to assign each shift pattern selected in ȳ to a precise shift, so that (i) track unavailability periods are respected and (ii) the shift sequence defines a feasible path for the vehicle. To increase the possibility of finding a feasible solution, more flexibility is added by relaxing the constraint that the last refill node of a shift q must be equal to the first refill node of the immediately following shift q ′ . Indeed, if these nodes differ, a deadhead trip from the last node of q to the first node of q ′ can be added at the end of shift q or at the beginning of shift q ′ to make the link. If the feasibility of the impacted shift is preserved by the modification, assigning q to σ and q ′ to σ+1 is feasible but incurs an additional deadhead cost, denoted c kσ qq ′ . The same principle can be applied to the shifts that start or end at the depot. We define

c k0 D k q (c k,|S|-1 qD k
) as the cost incurred if shift q starts (ends) the schedule, respectively. To model the shift/period assignment possibly incurring an additional cost, we reverse the shift-flow model presented in section 3.3 in which each shift was represented by an arc between refill stations in a time-space network. Each shift is now represented as a node while an arc connects two shifts that can be scheduled contiguously and each arc is weighted by the shift transition cost.

We introduce a dummy starting shift D k+ made of a single waiting arc at the depot D k that must be assigned to a dummy shift period σ = -1 and a dummy ending shift D k+ , including the same arc for period σ = |S|. We define P k (ȳ) as the set of "shift arcs" (q, q ′ ) with q ∈ Q k (ȳ) ∪ {D k+ } and q ′ ∈ Q k (ȳ) ∪ {D k-} such that q and q ′ can be scheduled contiguously w.r.t. the above-described adjustments. Note that, given the set of shifts selected by the master problem, the cost matrices and the shift arc sets are computed efficiently if the only allowed changes consist in adding dead-head trips at the start or the end of the two considered shifts and removing waiting times accordingly.

Consider again the example of Figure 3, ignoring depot constraints. Suppose the master problem has selected shift patterns q (1, 1 → 2, 4 → 2, 5) and q ′ (3, 1 → 2, 3 → 2, 4 → 2, 5) both with cost 0. Combining these shift patterns is not possible as such because their start and end nodes do not coincide. However, assigning q to shift 0 and q ′ to shift 1 becomes feasible by inserting deadhead trips (more precisely by replacing waiting period 2, 4 → 2, 5 by trip 2, 4 → 3, 5 in q and waiting period 2, 4 → 2, 5 by trip 2, 4 → 1, 5 in shift q ′ ). Figure 4 displays the modification of q (left side) to make it compatible with q ′ (right side) incurring costs c k0 qq ′ = 1 and c k1 q ′ D k = 1, i.e. a total cost of 2. Let z kσ qq ′ be a binary variable equal to 1 if shift pattern q ′ of vehicle k is assigned to shift period σ and preceded by shift pattern q. The Benders sub-problems can be written, for each vehicle k, as follows:

(SP k Benders ) min (q,q ′ )∈P k (ȳ) |S| σ=0 c kσ qq ′ z kσ qq ′ (27) 1, 1 2, 4 2, 5 3, 1 2, 3 2, 4 2, 5 3, 1 2, 3 2, 4 1, 1 2, 4 1, 5
Figure 4: Benders subproblem: assigning shift patterns to time periods and repairing the master solution

q|(D k+ q)∈P k (ȳ) z k0 D k+ q = 1 (28) q|(qD k-)∈P k (ȳ) z k|S| qD k-= 1 (29) q ′ |(q ′ ,q)∈P k (ȳ) z k,σ-1 q ′ q - q ′ |(q,q ′ )∈P k (ȳ) z kσ qq ′ = 0 σ ∈ {1, . . . , |S|}, q ∈ Q k (ȳ)∪{D k-} (30) σ∈S\{0} q ′ |(q,q ′ )∈P k (ȳ) z k,σ qq ′ = 1 q ∈ Q k (ȳ) (31) σ∈S q ′ |(q ′ ,q)∈P k (ȳ) z k,σ q ′ q = 1 q ∈ Q k (ȳ) (32) z kσ qq ′ = 0 (q, q ′ )∈P k (ȳ),(σ-1, σ) ∈ H q ×H q ′ (33) z kσ qq ′ ∈ {0,1} σ ∈ S ∪ {|S|}, (q, q ′ )∈ P k (ȳ) (34)
Objective ( 27) is to find a solution that minimizes the total cost of the shift modifications. Constraints (28) indicate that a shift pattern starting at the depot must be scheduled at the first period while Constraints (29) express that the last shift must end at the depot. Constraints (30) express flow conservation constraints for each shift at each shift period. All together, Constraints (28)-( 30) ensure that exactly one shift will be assigned to each time period and that consecutive shifts have to be compatible (a single path is selected in the shift time-space network). Constraints (31) and (32) state in addition that each shift must be assigned to exactly one shift period. Constraints (33) prevent a shift pattern from being assigned to an incompatible shift. To sum-up, the so-modeled shift scheduling problem is a special case of the traveling salesman problem with time windows.

A tightened Benders master problem To improve the Benders master problem, we consider adding in (M Benders ) the following "equilibrium" constraints, yielding (M * Benders ).

q∈Q k v+ y k q - q∈Q k v- y k q = 0 v ∈ V r , k ∈ K (35)
Constraints ( 35) are the shift flow conservation constraints in space. They state that, for each vehicle, the number of shifts that end with a given refill node (including the depot) is equal to the number of shifts that start with the same refill node, independently of the time periods. They are not necessary for the proposed decomposition, as they are also tackled in the sub-problem. However, without these constraints, the master problem lacks information about how the tasks can be sequenced, either in space or time. This would lead to the generation of combinatorial Benders cuts (25) solely used to satisfy the flow constraints. This is illustrated by the two shifts selected by the master problem without Constraints (35) displayed on top of Figure 4. If we add Constraints (35) to the master problem, the selection of these two shifts becomes infeasible.

An exact Benders method From these decompositions, an exact Benders method that consist in iteratively solving the Benders master problem and the benders sub-problems can be derived.

Even if the set of shift patterns is smaller that the set of time-stamped shifts, the Benders master problem still has an exponential number of variables. Hence to solve (M * Benders ) exactly, a branch-and-price procedure has to be used, where at each node of a branch-and-bound tree, a column generation procedure solves the linear programming (LP) relaxation of (M * Benders ). Once the optimal solution of (M * Benders ) is obtained, sub-problems (SP k Benders ) have to be solved, one for each vehicle k ∈ K. The three following cases have to be considered after solving the sub-problems.

• If all sub-problems have an objective value equal to 0, the global optimal solution has been found.

• If one of the sub-problems is infeasible, ȳk can be discarded by generating the corresponding no-good feasibility cut (25) and adding it to the master problem, which will be solved again during a new iteration.

• If the sub-problems are all feasible but at least one has a non-zero cost, a feasible solution for the RTISP is found and an upper bound on the total dead-head cost is obtained. Yet, solution ȳk can be discarded from the search space of the master problem by generating the corresponding no-good optimality cut (25), which will be added to the master problem and the process is reiterated. Note also that, since the master is solved through column generation, the feasible shifts that are found can be added as possibly new columns.

4 Column and cut generation matheuristic

Motivation and general principles

The exact Benders method described in Section 3.4 cannot be applied to solve the RTISP instances provided by SNCF for at least two reasons. First, the instances are too large to be solved by an exact method. Second, as explained in Section 4.2, the combinatorial Benders cuts make the column generation sub-problem difficult to solve. To use the decomposition scheme in practice, we have chosen to develop alternatively a cut and column generation matheuristic, which is also able to yield lower bounds. The method is a four step heuristic, described as follows:

1. (ColGen) An LP relaxation of the Benders master problem (M * Benders ) is solved through column generation. At this step, a lower bound can be obtained.

Compared to (M *

Benders ), the considered model has two main differences. First, in a standard way, highly penalized slack variables are introduced in set partitioning constraints [START_REF] Spoorendonk | Clique inequalities applied to the vehicle routing problem with time windows[END_REF] to ensure feasibility. More importantly, the generated cuts may have a different form expression (25) , and/or the cut generation algorithm can be parametrized in a way that it become heuristic (in the sense that the generated cuts may exclude potentially optimal solutions). In the latter case, the obtained lower bound is not valid and the ColGen procedure is mainly used to obtain a diversified and relevant set of shift patterns. The procedure is described in mode details in Section 4.2 and the alternative Benders cut generation process is made at step 3 (RelCutGen).

(HeurCover)

From the solution of this relaxation, a rounding heuristic for the covering problem proposed in [START_REF]A greedy heuristic for the set-covering problem[END_REF] is adapted to find a good integer solution to the Benders master problem (M * Benders ). At this point, a set of shift patterns satisfying the equilibrium constraints (35) is obtained. The procedure is described in Section 4.3.

(RelCutGen)

The selected shift patterns have to be scheduled in compatible shift periods. For each vehicle k, a relaxation of the Benders sub-problem (SP k Benders ) is solved. If one of the relaxations is infeasible, a Benders infeasibility cut is added to the master problem to exclude the solution found at step 2 and we return to step 1. As mentioned in step 1, the Benders infeasibility cuts produced at this step have a different form than combinatorial cuts (25). This is either due to the structure of the relaxation (aa assignment problem) or to a heuristic cut generation scheme. The procedure is described in Section 4.4.

(HeurSched) If the relaxations of the Benders sub-problem are all feasible, a heuristic is used to solve (SP k

Benders ), i.e. to schedule the selected shift patterns, for each vehicle k. If one of the problems is infeasible, a combinatorial Benders cut (25) or a heuristic cut can be generated and we return to Step 1. Otherwise the solution is returned. The scheduling heuristic is described in Section 4.5.

ColGen: solving the relaxed Benders master problem (M * Benders ) with column generation

Initial column set The Benders master problem (M * Benders ) is considered with a restricted set of columns, corresponding to a restricted set of shift patterns Qk .

The initial column set is initialized by considering for each required arc a ∈ A * a shift pattern covering this arc. This allows to satisfy partitioning constraints [START_REF] Spoorendonk | Clique inequalities applied to the vehicle routing problem with time windows[END_REF]. Furthermore, for each pair of refill nodes, a column corresponding to a dead-head trip joining these two nodes is added to Qk to satisfy the equilibrium constraints (35).

Restricted master problem solving The LP relaxation of the so-obtained restricted master problem is denoted as ( M * Benders ). It is solved with the simplex algorithm. At the first iteration, there is no Benders cut (25). At the subsequent iterations, no-good cuts are incorporated to take the infeasibility of the corresponding Benders sub-problems (SP k Benders ) into account. As explained in Section 4.1, the cuts do not necessarily correspond to expression (25). This is due to several reasons that will be explained in Section 4.4.

Column generation subproblems

As only a restricted number of columns is considered, the solution is not necessarily the optimal LP solution, as there may exist non considered columns with negative reduced cost. To explain how such columns are searched, let us first give the expression of a variable's reduced cost, by considering problem (M * Benders ) without any no-good cut. The reduced cost of a variable y k q of the master problem is a function of the dual solution vector. Let α k a , for all task arcs a ∈ A * , denote the dual variables related to partitioning constraints [START_REF] Spoorendonk | Clique inequalities applied to the vehicle routing problem with time windows[END_REF]. Let β k v , for all refill nodes v ∈ V r and vehicles k ∈ K, denote the dual variables related to equilibrium constraints (35). If we ignore no-good cuts, the reduced cost of a variable y k q for a vehicle k ∈ K and a shift pattern q ∈ Q k starting at refill node v and ending at refill node v ′ is

ck q = c k q - a∈A * |q∈Q k a α a + β k v -β k v ′
The column generation sub-problem aims at finding for each vehicle k ∈ K a feasible shift pattern q ∈ Q k of negative ck q , or at proving that no such shift pattern exists. To be feasible, a shift pattern has to correspond to a valid shift for at least one shift period σ, i.e. a shift in some Q kσ . Hence, we obtain a column generation sub-problem (SP kσ ColGen ) per vehicle k ∈ K and shift index σ ∈ S, which can be written as an arc flow model, as follows.

(SP kσ

ColGen ) min

a∈A s τ =1 cakτ x k,σ a,τ (36)
subject to

x kσ ∈ Q kσ where c(i,j)kτ = c (i,j)k -α(i,j) + βk iτ -γk j,τ +d (i,j)k -1 , αa = α a if a ∈ A * 0 otherwise, βk iτ = β k i if i ∈ V r and τ = 1 0 otherwise, γk iτ = β k i if i ∈ V r and τ = s 0 otherwise.
Given the expression of Q kσ , each column generation sub-problem (SP kσ ColGen ) is a resource-constrained shortest path problem. The resulting path gives a new shift pattern corresponding to a variable y k q with a negative reduced cost (or it is proved that no such path exists).

If we want to integrate the no-good constraints in the column generation sub-problem along the method iterations, we have to take care of the following issues. While set partitioning constraints [START_REF] Spoorendonk | Clique inequalities applied to the vehicle routing problem with time windows[END_REF] and equilibrium constraints (35) are defined on arcs and nodes of the space-time network, the Benders infeasibility cuts (25) are defined on a shift pattern. This characteristics can slow down the dynamic programming algorithm used for solving the RCESP. This was for example recently experienced in [START_REF] Spoorendonk | Clique inequalities applied to the vehicle routing problem with time windows[END_REF] with clique inequalities defined on the set partitioning master problem of the vehicle routing problem with time windows, which required adding multiple resources in the RCESP. In this work, we ignore the dual information carried by no-good constraints when solving the column generation subproblems. As the reduced cost is simplified, the column generation algorithm could generate already existing columns. Hence, a duplicate detection mechanism is implemented and the algorithm stops in case of cycling.

It should be noticed that it could be time consuming to compute |K| • |S| constrained shortest paths at each column generation iteration. Our implementation enables finding valid shortest paths for several consecutive shifts. It can be parametrized to generate from |K| to |K| • |S| subproblems. At the first extreme, the feasible solution space of each of the |K| subproblems is large. Solving one of them may take time. In the other extreme, the feasible solution space of each of the |K| • |S| subproblems is narrow and solving one of them is fast.

Column generation algorithm For solving the sub-problems, we implea variant of the dynamic programming algorithm of [START_REF] Feillet | An exact algorithm for the elementary shortest path problem with resource constraints: application to some vehicle routing problems[END_REF] for the resourceconstrained elementary shortest path problem. This algorithm has been selected because it is very flexible and adapting it to different types of vehicles cis easy. This is important in our case because the solving scheme should be general enough to allow its use for different problems.

The dynamic programming is a labelling algorithm. At each iteration, a node and an associated label are picked from a queue. The label is then extended through the traversal of the outgoing arcs, consuming resources according to the arc type. Dominance rules allow to prune labels which are known not to lead to an optimal solution as explained in [START_REF] Feillet | An exact algorithm for the elementary shortest path problem with resource constraints: application to some vehicle routing problems[END_REF]. The main difference is that the path does not need to be strictly elementary, unlike in paper [START_REF] Feillet | An exact algorithm for the elementary shortest path problem with resource constraints: application to some vehicle routing problems[END_REF]. In our setting, communication arcs and nodes can be traversed as needed. We just have to be sure that each task arc is visited at most once, as stated by Constraints 5.

HeurCover: greedy rounding heuristic for solving the

Benders master problem (M * Benders )

Starting with the continuous solution ỹ of the Benders master problem (M * Benders ) obtained by procedure ColGen (see Section 4.2), a greedy rounding heuristic inspired by the one proposed in [START_REF]A greedy heuristic for the set-covering problem[END_REF] is used to get an integer solution (satisfying only the Benders master problem constraints). The principle of the heuristic is the following. For each vehicle k ∈ K, let Qk denote the set of shift patterns which can be selected, initially containing all shift patternS q such that ỹk q = 0.

Let A * qk be the set of tasks covered by a shift pattern q ∈ Qk . Let C denote the tasks still not covered, initially equal to A * . Let C k q denote the set of uncovered inspection tasks that can be covered by q ∈ Qk , initially set to A * qk . Let f (q, k) denote a priority function associated to shift pattern q ∈ Qk .

At each iteration, the greedy heuristic selects the shift pattern q * for the vehicle k * with the minimum priority function value. q * is removed from Qk . Each inspection task a ∈ A * q * k is removed from C and from all C k q with k = k * or q = q * . Each shift pattern q ∈ Qk such that C k q becomes empty is removed from Qk . The process is repeated until C is empty or no shift pattern can be selected anymore.

We propose several priority functions f . In [START_REF]A greedy heuristic for the set-covering problem[END_REF], function f 0 (q, k) = c k q /|C k q | gives the ratio of the variable objective coefficient to the number of uncovered tasks it would cover if q was selected. We also propose alternative priority functions.

f 1 (q, k) = c k q (1 -|C k q |/(|A * \ C| + 1)
) is a dynamic priority function that multiplies the variable cost by the ratio of the number of tasks that would remain uncovered if q was selected to the number of tasks already covered . Finally,

f 2 (q, k) = c k q (1 -|C k q |/(|(A * \ C) ∩ A * qk | + 1)
) multiplies the variable cost by 1 minus the ratio of the number of uncovered tasks that q would cover if it was selected to the number of already covered tasks also covered by q. Both dynamic priority functions give priority to the shift patterns covering a lot of tasks at the first iterations and, when the number of covered tasks becomes large, to the shift patterns with a low cost.

In addition, weighted variants of these priority functions can be obtained by taking into account the value of the variable in the solution of the LP relaxation. Let nint(i) denote the nearest integer to i. We define the following weighted functions:

f ′ x (q, k) = f (q, k)(1 + nint(ỹ k q ) -ỹk q ). Last, the procedure is significantly improved by iteratively fixing the selected variables and resolving the linear relaxation of (M * Benders ). At each iteration of HeurCover, the linear relaxation of (M * Benders ) (with the last generated restricted set of columns) is solved with the additional constraint that y k q = 1. ȳ is updated before selecting the next variable in the next HeurCover iteration, and the rpocess is iterated until all tasks are covered or no column are added. This incremental variant of HeurCover allows handling every constraint of the Master problem (not only the ones which ensure that every required arc belongs to a feasible trip).

RelCutGen: cut generation based on relaxations of the Benders sub-problems (SP k Benders )

At this point, an integer solution ȳ to the Benders master problem (M * Benders ) has been computed by the greedy procedure HeurCover (see Section 4.3). The Benders sub-problems (SP k Benders ), for k ∈ K can be solved to generate no-good cuts in case of infeasibility or sub-optimality. However, no-good cuts (25) invalidate a single solution ȳ. Their impact to the LP relaxation ( M * Benders ) is weak and we do not use any branch-and-price procedure where they could have a pruning power. Furthermore, each Benders sub-problem is a special instance of the TSPTW, and, consequently, is hard to solve. We propose two ways to deal with this issue.

Solving relaxations of the Benders sub-problems Dropping flow conservation constraints (30) in each (SP k

Benders ) for k ∈ K yields an easy-to-solve assignment problem.

To explain how cuts can be obtained by this relaxation, let us focus only on the feasibility of the Benders sub-problem for shift/period assignment. We add slack variable h D k-to Constraint (29) and slack variables h q , ∀q ∈ Q k (ȳ) to constraints (32). Consider solving the assignment problem min q∈{D k-}∪Q k (ȳ) h q subject to (29), (32), (33), non negativity of variables h q and relaxing integrity constraints for variables z σk qq ′ . The objective function gives a lower bound on the number of shifts of Q k (ȳ) selected by the master problem that cannot be assigned to a feasible period, given the availability periods in H q . This yields the following Benders cut

q∈Q k (ȳ) y k q ≤ q∈Q k (ȳ) σ∈S q ′ |(q ′ ,q)∈P k (ȳ) zkσ q ′ q
where zkσ q ′ q is the (integer) solution of the relaxed Benders sub-problem. By introducing different assignment constraints in the linear program, different cuts can be obtained by applying the same principle.

Pseudo-cuts Pseudo-cuts, i.e. cuts that may exclude valid integer solutions of the master problem, can be defined to invalidate continuous solutions of the master problem, so that the integer solution has little chance to be generated by the HeurCover heuristic. More concretely, let ỹ be a continuous solution of the master problem, and let ȳ denote its integer solution found by HeurCover.

Combinatorial or assignment-problem-based Benders cuts are generally of the following form.

q∈Q k (ȳ) y k q ≤ n
where n is the number of variables that cannot be selected. As these cuts are violated by the integer solution we have

q∈Q k (ȳ) ȳk q > n
Then, if we assume, in addition, that ȳk q ≤ ⌈ỹ k q ⌉, the following constraint invalidate continuous solution ỹ

q∈Q k (ȳ) y k q ỹk q ≤ n
Note that the closer the value ỹk q is to an integer solution the more the cuts resemble to the original Benders cuts.

4.5

HeurSched: heuristic for the solving the Benders subproblems (SP k Benders )

If the relaxations presented in Section 4.4 are feasible for the current solution to the master problem, the original combinatorial Benders subproblems (SP k Benders ), for k ∈ K, should be solved to determine the actual feasibility of this solution and possibly repairing it.

The corresponding traveling salesman problem with time windows is solved using a guided multi-start heuristic. Consider a chronological search tree with a maximum depth equal to |S| in which each node corresponds to a partial assignment of the selected shifts up to shift index σ. An iteration of the heuristic consists in a depth-first search on the search tree, yielding a complete shift/period assignment. At a given node of depth σ, let q σ-1 be the previously selected shift, where q -1 = D k+ for the root node σ = 0. The depth first search algorithm selects the decision (a shift q such that σ ∈ H q and (q σ-1 , q) ∈ P k (ȳ)) that minimizes a dynamic transition function t(q σ-1 , q). The transition function is initially set to the dead-head cost t(q, q ′ ) = c k qq ′ for each pair (q, q ′ ) ∈ P k (ȳ). However, for each possible decision at a node, two depth-first explorations are performed by using the current transition cost: one which selects the first shift according to the transition function, yielding a complete solution with a cost c + q and one which cannot select this shift yielding a complete solution with a cost c - q . A price π q is associated with the decision to schedule shift q right after shift q σ-1 where π q = c + q -c - q . The transition cost matrix is updated with t(q σ-1 , q) ← t(q σ-1 , q) + π q . The algorithm iterates until the matrix transition cost modification becomes negligible. For the considered dataset, this method proved to be the most efficient in terms of quality and solution time. This principle can be mixed with backtracking, when a decision does not yield a feasible solution.

A dynamic programming heuristic

In order to evaluate the proposed decomposition scheme with another heuristic which is closer to what would be performed by a human operator, we additionally designed a greedy algorithm to solve the complete RTISP based on the dynamic programming method used to generate the shift patterns for the column generation procedure. This algorithm uses the resource constrained shortest path solver to compute at each iteration the set of best shift patterns which can be performed starting from the last visited node. Hence, the algorithm is greedy in terms of shift scheduling, while the dynamic programming method used to generate the shift still performs an implicit enumeration. The shift of lowest cost is appended to the current partial solution. We select a vehicle and, starting from its depot, we apply this procedure until the end of the schedule horizon is reached. Then, we start with the next vehicle.

If no task is reachable from the current node, a deadhead move is performed to find the nearest node which enables performing a task. Deadhead speed is fast enough to allow every vehicle to travel from one node to every other node in less than a shift. This simple choice allows the potential generation of solutions which cover every task.

The cost function drives the algorithm towards a good solution and should be carefully chosen based on the characteristics of the dataset, and on whether the problem is more constrained in time or space. For task selection during the shortest path computation, different weight update rules have been tested. The best performing one uses information about task time windows and durations.

Let w k a denotes the cost of performing task a on vehicle k. This cost is defined as follows:

w k a = -M + c a (2.0 - es a ls a ),
with es a and ls a , denoting respectively the earliest and latest start of task a. M should have a value such that the algorithm will always prefer performing a task over performing a deadhead trip.

Computational tests 6.1 Real data from 2009

The computational test was conducted on real data provided by SNCF. Full results are available in the PhD thesis [START_REF] Lannez | Optimisation des tournées d'inspection des voies ferroviaires[END_REF]. These data has been used to calculate the time windows for each of the 2009's inspection tasks. The data model contains three vehicles and a realistic average working speed. Based on this data, multiple scenarios have been established by varying the track outages duration, the size of the considered network, the time horizon and other practical characteristics.

Complete network characteristics

The complete graph has 2100 arcs and 760 nodes of which 90 are refill stations and about 700 tasks to perform. Task time windows have a fixed size of 28 days and their duration range from a few minutes to six hours. The duration of a shift is fixed to 7 hours.

Data sets

The first two data sets (RTISP1.1 and RTISP1.2) involve a single vehicle with no track outage (the vehicle may circulate at any time in any part of the network). The first scenario captures data from the first half of 2009 and the second scenario extends it by adding the rest of the year. The second series of data sets (RTISP2.1 and RTISP2.1) still involves no track outage but consider special tasks limiting vehicle availability. Data set RTISP2.1 includes the special tasks corresponding to regional demands. Recall that, as only primary tracks inspection is precisely scheduled, regional departments can ask for one vehicle during a fixed period to inspect the secondary tracks . This is modeled by a fictitious inspection task located at the node where the vehicle must be provided and will be returned. As this period can be large, such scenarios are more constrained. Three vehicles are considered. Data set RTISP2.2 includes the regional demand tasks and maintenance tasks which are also special tasks representing a time period during which the vehicle must be sent to maintenance at a specific node. This set also includes three vehicles. The third data set series (RTISP3.1, RTISP3.2, RTISP3.3, RTISP3.4) contains 100 tasks and a one month time horizon but includes an increasing number of track outages. RTISP3.1 includes no outages, RTISP3.2, RTISP3.3 and RTISP3.4 include all tracks outages of more than 6 hours, 3 hours and 1 hour, respectively. The fifth series is made of the single data set RTISP4.1, which is identical to set RTISP3.1, except that one of the two vehicles is significantly slower than the other one. The last series of data sets (RTISP5. the tasks are performed. These sets correspond to the cases where vehicles can be required for maintenances and/or regional demands. This shows that maintenance and regional demands should be carefully planned, given the limited number of inspection vehicles. In terms of performance ratio, the presence of maintenance and regional demand activities penalizes the results (as shown by the difference between series 1 and 2). It must be noticed, however, that the performance ratio naturally decreases as the number of inspection tasks decreases, which explains the difference between instances RTISP1.1/RTISP1.2 on the one hand and instance RTISP3.1 on the other hand (which all have no outage). Indeed, when a reduced number of inspection tasks is considered in the full network, the total dead-head distance increases comparing to the inspection distance.

Comparison with the dynamic programming heuristic

To assess the performance of the proposed heuristic we first compare it to the dynamic programming heuristic proposed in Section 5. We compare the two heuristics (AlgoBenders and AlgoGreedy) on the instance series 3 since the number of rail track outages appears to be discriminant. The results are displayed in Table 3. The dynamic-programming-based heuristic solves all datasets in less than 5 minutes. However both its completion rate and its performance ratio decrease as the number of outage increases. This seems to show that the heuristic takes local decisions which badly impact the global quality of the solution. In comparison, the decomposition algorithm performs well: every task is executed and the performance ratio is much better (more than twice better for the larger number of outages). Furthermore, the matheuristic is less sensitive to outage variations.

RTISP1

Impact of algorithm

The complexity of the algorithm and the necessity of industrial standard lead the design of the algorithm implementation towards a very modular solution. Indeed, the building blocks are inspired by the design patterns proposed in [START_REF] Gamma | Design patterns: elements of reusable object-oriented software[END_REF]. Each algorithm is a building block (set cover heuristic, column generation, assignment problem, ...) and can have multiple implementations.

In this section, we study the impact of variants of algorithm component on the global performance. The most important impact on the solving time was obtained by tuning the algorithm used to solve the Benders master problem (M * Benders ). Multiple priority functions in the HeurCover heuristic for finding integer solutions to (M * Benders ) have been tested. The conducted tests also demonstrate the great importance of adding the redundant equilibrium constraint in (M * Benders ). The interest of the proposed cuts is also assessed.

Multiple priority functions in HeurCover

The different priority rules f 0 , f 1 and f 2 are detailed in Sections 4.3 for the rounding heuristic HeurCover. Table 5 presents the value of the best integer solution (total dead-head distance in TKm) for different computation times (in minutes) for data sets RTISP1.1 and RTISP1.2. It demonstrates the effectiveness of the rule f 0 proposed in [START_REF]A greedy heuristic for the set-covering problem[END_REF] for solving the instance RTISP1.1. It also shows the new rule we propose f 3 is much more efficient on the instance RTISP1.2. The analysis of the 2009 data shows that vehicle workload is higher in the second part of the year than in the first. It should be noticed that rule f 0 only takes into account the ratio between the variable cost in the objective function and the number of tasks it would cover if it is selected. This rule may lead to the selection of columns which cover multiple times the same task, hence reducing the working capacity of the vehicle. The rule f 2 reduces this issue by taking the overlap of multiple columns into account in the priority weight. These remarks explain the differences between the two results. Table 6: Impact of the flow conservation cut in the column generation procedure accelerate the convergence of the algorithm. These constraints reduce the set of partial solutions which lead to infeasible subproblems hence limiting the number of generated cuts. Furthermore, they seem to improve the conditioning of the elementary shortest paths by reducing the number of non-dominated partial paths. Indeed, the dual information obtained from these equilibrium constraints can be interpreted as a deficit or surplus cost for the given node at the beginning of a shift. These weights highly impact the way the dynamic program selects the very first arcs of the solution by improving the efficiency of the dominance rule, hence speeding up the dynamic programming algorithm.

In order to highlight this behavior, a slack variable has been added to each flow conservation constraint. The penalty cost of each variable defines how much the constraint is enforced. Table 6 evaluates four variants, presented below:

1. f lowCst -1 No slack variable has been added. Table 6 provides the objective function values (in TKm) and the CPU times (in minutes) of the column generation procedure for the different variants on data sets RTISP1.1 and RTISP1.2.

The comparison of columns "30", "60" and "120" for instance RTISP1.2 shows that adding the equilibrium constraint helps the column generation procedure a lot , leading to a solution with a smaller cost. It can also be noticed that the best continuous solution is found more quickly (in less than 30 minutes with the equilibrium constraint, in more than 100 minutes without the equilibrium constraint). Interestingly, a well chosen penalty price for the violation of the constraint (as the one used in the third case) can drastically improve the convergence and the quality of the solution.

Impact of Benders cuts

In most of the above-presented results, the cuts proposed in Section 4.4 do not have a visible impact. More precisely, cuts are generated on columns with low quality that are unlikely to be selected. We have to recall that the cuts presented in Section 4.4 are feasibility cuts obtained by relaxations of the Benders sub-problem, as the combinatorial cuts could not easily be incorporated in the heuristic. Also, for data sets that are feasible or nearly feasible, this low impact could be explained. This is not true anymore for instance RTISP4.1 for which the heuristic performs less than 30% of the

  (a) Map of primary tracks (b) Graph model of railtracks around Bordeaux

Figure 1 :

 1 Figure 1: French railway network model

Figure 3 :

 3 Figure 3: Space-time networks representing feasible shifts shift time period index τ . Each arc from v, τ to v ′ , τ ′ corresponds to a variable x kσ aτ with a = (v, v ′ ) * (bold arcs) or a = (v, v ′ ) d (thin arcs) with a travel time d ak = τ ′ -τ . Each horizontal arc from v, τ to v, τ +1 is a waiting arc. The set

  Equilibrium cuts in the Benders master problem The redundant equilibrium cut (35) in the Benders master problem has proven to be very efficient to

2. f lowCst 0

 0 Penalty cost of slack variables is 0.3. f lowCst 10e3Penalty cost of slack variables is 10000.4. f lowCst 10e4Penalty cost of slack variables is 100000.

Table 2 :

 2 Results of the proposed heuristic on the real data sets

	1, RTISP5.2, RTISP5.3, RTISP5.4) involves
	both a time restriction (may 2009) and a network restriction (Brittany region).
	It was generated mainly to have "small" non trivial instances (56 tasks). It
	involves 2 vehicles and possibly track outages. The data set characteristics are
	synthesized in Table 1.

Table 5 :

 5 Comparison of priority function for HeurCover scenarios, tasks are neither contiguous in space nor in time. Consequently, the results do no necessarily generalize to the complete network. By contrast, for data sets RTISP1.1, RTISP1.2, RTISP1.3 and RTISP1.4 (extracted on a larger period and for the complete network), the shift sequencing heuristic did not add any additional dead-head trips (the solution provided by the Benders master problem was feasible).

		.1	RTISP1.2
	30 60 120	30	60 120
	f 0 35 25	25		90	90
	f 1 45 45	45 120 120 120
	f 2 45 45	45 110	82	62

Key indicators

For each algorithm and each of these scenarios, the completion rate r defines the number of task which are covered by the solution. The performance ratio p gives information about the total distance traveled without inspecting (deadhead). The higher the ratio, the better the solution from the point of view of the end user. The performance ratio p is calculated to reflect the rate between the total inspected distance (d i ) and the cumulated deadhead length (d d ):

The task completion rate r is used to get information about the hardness of the instance. When comparing the decomposition heuristic with the dynamic programmming heuristic, this indicator gives valuable information about how hard it is to schedule the instance.

Global results

The experiments were carried out on an Intel Xeon (64bits) 3.0GHz, having 4 cores. We use IBM CPLEX 12.2 for linear programming and IBM CP 1.6 and SCHEDULER for the guided multi-start scheduling heuristic. All programs were written in C++. We parallelize the column generation procedure since the subproblems are independent.

In Table 2, the results of the proposed heuristic on the above presented data set is presented. The alloted CPU time has been adapted to the instance size with 4 hours for the largest instances, 30 min for the 100-task instances and 5 min for the small instances. In terms of completion rate, the global performance of the heuristic is good, except for instance set RTISP4.1 for which less than 30% of the tasks are performed. This set is identical to set RTISP3.1, except that a vehicle is significantly slower than the other, which makes the instance infeasible. There are also two sets (RTISP2.1 and RTISP2.2) for which less than 90% of

Comparison with linear programming relaxation

To further evaluate the quality of the proposed heuristic, we compare it with the linear programing relaxation of the Benders master problem, using the column generation procedure ColGen (see Section 4.2). For large instances, the column generation procedure is stopped by the predefined time limit before a valid lower bound on the total dead-head distance is obtained. A valid lower bound can be obtained only on the fifth instance series, which contains 56 tasks.

The results are displayed in Table 4. Row "Gap (IP-LP)/LP" gives the gap between the dead-head distance of the LP relaxation obtained by ColGen and the total dead-head distance obtained by the rounding heuristic HeurCover presented in Section 4.3. Row "Performance UB" gives the upper bound on the performance ratio given by the LP relaxation while row "Performance LB" recalls the performance ratio of the solutions computed by the matheuristic. First, it has to be noticed that the rounding heuristic gives results very close to the LP relaxation. The performance gap between the proposed heuristic and the LP relaxation is much larger, although. This means that the dead-head distance is added by the repairing Benders sub-problem solving procedure when sequencing the selected shifts. However, the upper bound on the performance ratio provided by the LP relaxation is under 45% in average which tempers the apparently low performance of the the proposed heuristic (around 30% in average). Indeed, this provides the valuable information that reaching a performance of 50% is an unachievable goal in this subnetwork. However, to explain the 15% difference, we suspect that the upper bound quality is not so good. By analyzing the continuous solutions, we observe that they include a lot of subtours related to the visited refill nodes, and they do not take into account deadhead moves between these subtours. Furthermore, these data sets consider only the Brittany trgion and only a few weeks, whereas the initial algorithm was developed to solve a one year planning on the whole network. Hence, in these 7. The results show the highly positive impact of the generated cuts which allow to increase the number of performed tasks by a factor three. After analyzing the results closely, we ntived that 15 shifts are assigned to vehicle 1 and 12 shifts are assigned to vehicle 2 when the cuts are applied while 20 shifts are assigned to vehicle 1 and only 6 shifts are assigned to vehicle 2 when no cuts are applied. Hence the Benders feasibility cuts avoid overloading the fastest vehicle.

Conclusion

An exact decomposition procedure for the RTISP has been proposed. This procedure is general enough to be used for others arc routing problemsand it has been used to design a matheuristic which is able to schedule real datasets. The proposed solution is flexible enough to be adapted by the operator. Starting from the schedule given by the solver, the expert can adapt it to take into account the real speed of the vehicles, the precise date of the outages and most importantly the pathways. The industrialization of the proposed tool is currently in an evaluation phase at SNCF. In terms of lessons learned from a practical point of view, the method has shown, especially through the upper bound on the performance ratio, that maintenance and regional demands are limiting factors due to the limited availability of vehicles and should consequently be planned carefully. Indirectly, the generated data sets also show that performance ratio of the solutions proposed by the matheuristic is much higher for the larger problems considering the whole network and planning horizon, in comparison with restricted sets. This may seem counterintuitive at first sight, but planning on the whole network allows the algorithm to smooth the vehicle load over the entire horizon and significantly increase the proportion of inspections w.r.t. dead-heads. This fully justifies the need for an integrated planning of the primary track inspection that originated the project.

The use of the relaxed Benders subproblem may be of interest in other problems where the resolution of the Benders subproblem is the part which is consuming the most computation power. Furthermore, this approach can provide stronger cuts.

From the industrial point of view, the RTISP can be generalized to other railroad maintenance problems. The proposed approach is also usable to solve other type of maintenance problems.

However, the proposed method has limitations in the sense that the solutions proposed by the Benders master problem include subtours that needs introduction of extra deadhead costs in the repairing phase. Generating cuts to eliminate the subtours is a promising way of improving the performance gap.