Mirsad Buljubašic
email: mirsad.buljubasic@mines-ales.fr

Michel Vasquez
email: michel.vasquez@mines-ales.fr

Haris Gavranovic
email: haris.gavranovic@gmail.com

Haris Gavranović

Two-phase heuristic for SNCF rolling stock problem

Keywords: Greedy heuristic, Integer programming, Local search, Rolling stock, Scheduling 1 Introduction

Two-phase heuristic for SNCF rolling stock problem

Mirsad Buljubašić, Michel Vasquez, Haris

non-modifiable. It had to be decided which train is assigned to each departure. It is feasible, but penalizing, not to cover (i.e. to cancel) some arrivals or departures. The set of train arrivals is denoted by T and a train t ∈ T is defined by the following characteristics:

-arrival time arr T ime t , ideal Dwell t and max Dwell t , respectively representing the ideal and the maximum time train should stay on the platform after arr T ime t , -remaining distance before maintenance rem D B M t , determining whether or not t must perform maintenance operations before being assigned to a departure.

The following attributes define a departure d ∈ D, where D represents the set of all departures:

-depT ime d , ideal Dwell d , max Dwell d : all similar to the train arrival attributes, -distance req D d of the journey following the departure; this value is compared, for a train t ∈ T , with rem D B M t , to determine whether or not maintenance operations have to be performed on t before depT ime d .

In practice, the trains associated with arrivals are usually trains which were earlier assigned to departures and which spent some time out of the system before coming back. To take this into account, some arrivals are linked with departures occurring earlier in the horizon.

When an arrival t has a linked departure d, there are two distinct. If d is cancelled (i.e. if no train is assigned to d), then rem D B M t is the one provided in the input data for t. If d is covered, then rem D B M t is replaced by the one induced by the train t assigned to d i.e. rem D B M t = rem D B M treq D d .

Maintenance

Trains must be serviced on a regular basis to enable them to operate safely. Maintenance work helps restore rem D B M t to its maximum value max D B M t . Maintenance operations can only be performed at servicing facilities. As the system's maintenance capability is limited, the number of operations which can be performed in one day, i.e. across all the system's maintenance facilities, is bounded by a maximum value represented by max Maint.

Infrastructure resources

Between arrivals and departures, trains are either moving or parked on tracks that we consider to be resources. Let R be the set of all resources. Resources can be either platforms, maintenance facilities, yards or track groups. Platforms and maintenance facilities represent portions of tracks considered individually, while track groups and yards are aggregated types of resources which usually contain more than one track as well as switches to physically link the different tracks together. An example of resources configuration is given in Fig. 1. A resource r ∈ R has a set of neighbouring resources, defining the possible transitions for trains, in a symmetrical way. Resources represent railways infrastructure elements which are in general linear and can be accessed from both sides, and in some cases from only one side. Given this aspect, the neighbours of a resource can then be divided into two subsets, one being physically associated with each side of the linear element. The transitions between a resource, r , and one of its neighbours, are performed through one of the entry/exit points, which we call gates, located on either side of the resource. These gates are the physical tracks linking the various resources. Platforms and facilities, representing individual tracks, have at most one gate on each side. Only track groups and yards may have more than one gate on each side. For these types of resources, two adjacent resources might be linked by more than one gate: the gate used for the transition between two resources has to be specified. For example, track group 1 in Fig. 1 has 8 gates and 8 neighbouring resources on the right side, and 14 gates and 2 neighbouring resources to the left. Platforms represent tracks within the train station where passengers can board and disembark. Maintenance facility resources are special tracks inside maintenance workshops. They are used to periodically reset the train remDBM. Platforms and maintenance facilities are both characterized by a length which may not be exceeded by the total length of trains using it (length of platforms in the example shown in Fig. 1 varies from 270 to 400, while all facilities have a length of 350 or 450).

Yards are sets of tracks used to park trains. Trains can stay in yards with no time restriction, but a yard has a limited physical capacity in terms of the number of trains it can handle simultaneously (25 for the yard in Fig. 1 example). Capacity is the only constraint when parking the trains in the yards, i.e. there are no constraints on movement of trains in the yards as is the case on platforms or in maintenance facilities.

Track groups are sets of tracks used by trains to move throughout the system. Its real physical configuration in terms of tracks and switches linking them can be very complex. Its complexity is not taken into account herein; we have considered it as a black box with some indications on how to identify conflicts. The duration of use of track group k by any train (i.e. travel time) is a constant denoted by trT ime k . It is the time required by a train to enter the track group k on one side and exit from the opposite side. Indeed, a train entering on one side of a track group must exit from the other side. All gates on one side are reachable from all gates of the opposite side. In addition, hwTime k represents the headway of the track group: this is a safety time which must be adhered to at any place between two trains. In Fig. 1, trT ime and hwTime are shown for each track group in the top left and bottom right corners respectively; for example, for track group 2 we have trT ime = 30 s and hwTime = 3min. When several trains use a track group over the same time period, there may be conflicts between them. A conflict occurs if the paths of two trains on the track group intersect and headway time hwT ime between them is not complied with. Conflicts are considered to be unfeasible. Each arrival and each departure has a fixed arrival/departure sequence. These sequences represent the routing of trains on the tracks during the last few km before reaching the platforms. Sequence is defined by an ordered set of track groups that a train has to use when arriving/departing. In Fig. 1, possible arrival sequences are TrackGroup3-TrackGroup1 and TrackGroup4-TrackGroup2-TrackGroup1.

Solution representation and objective function

A solution to the problem consists of a set of schedules, one for each train. The train schedule is a sequence of events during its presence in the system, along with details such as the time of each event, the resources used, etc. With this information for every train, the status of the system and each of its resources can be derived at any time during the horizon. The objective function to be minimized is a weighted sum of the following individual costs:

1. Uncovered arrival/departure cost, 2. Platform usage cost.

The uncovered arrival/departure cost is proportional to the number of cancelled arrivals and departures. Platform usage cost is the sum of the costs of using the platforms during arrivals and departures. Each arrival t ∈ T has an ideal dwell time ideal Dwell t , and each departure d ∈ D also has an ideal dwell time ideal Dwell d . The cost of using the platform during arrival/departure is proportional to the difference between actual dwell time (platform use duration) and ideal dwell time. It is important to mention that the actual objective function, as defined in the competition subject [START_REF] Ramond | Trains don't vanish! ROADEF EURO 2014 challenge problem description[END_REF], contains several other parts, but for reasons of simplicity, have been omitted here. Furthermore, for the set of instances introduced in the competition, these two objectives are, by far, the most critical.

Related work

A large body of literature on train routing problems is available. However, any exact or even similar matches from previous research with the current problem could not be identified. Only variations to some of the sub-problems occurring here can be found in publications such as [START_REF] Lentink | Applying operations research techniques to planning of train shunting[END_REF] and [START_REF] Freling | Shunting of passenger train units in a railway station[END_REF]. Furthermore, there is a broad range of optimization models for specific problem variants. We will not therefore be emphasizing any of the papers or related problem variants herein.

Recently, both during and after the competition, a few papers (or technical reports) were published on this topic. [START_REF] Cambazard | Roadef challenge 2014: A modeling approach, rolling stock unit management on railway sites[END_REF] propose a methodology heavily based on modelling with both integer programming (IP) and Constraint Programming technologies for problem resolution. These authors mainly concentrate on solving the problem of assigning trains to departures and using an integer programming approach similar to that explained in this paper. [START_REF] Haahr | Exact methods for solving the train departure matching problem[END_REF] propose two exact methods, IP and Column Generation, for solving the same sub-problem (called "Train Departure Matching Problem" in their paper). They report that solving the problem of assigning trains to departures exactly is very difficult, if not impossible, for a given set of instances. Most of the teams competing in the ROADEF/EURO Challenge 2014 proposed algorithms that rely on greedy procedures or integer programming or a combination of both. Modelling an entire problem, or a significant part of one, using IP is theoretically possible and has been achieved by a number of competitors, yet the outcome proved incapable of producing satisfactory results on the given set of instances. IP techniques therefore are mainly used to solve only specific sub-problems. The breakdown of a problem into two dependent sub-problems, i.e. assignment and scheduling problems, is quite a natural step given the complexity of the initial problem and was implemented in most of the approaches presented. To the best of our knowledge, none of competitors conducted a local search (at least as a significant component of their research).

Two-phase approach

In our method, the problem has been broken down into two sub-problems, which are then solved sequentially. During the first phase, a train assignment problem is solved by combining a greedy heuristic procedure with integer programming (IP). The main objective here is to maximize the number of assigned departures while meeting technical constraints. Other objectives are taken into account as well, with the aim of obtaining "better" input for the subsequent phase. During the second phase, the train scheduling problem, which consists of scheduling the trains inside the station, is solved using a constructive heuristic model. The goal is to schedule as many assignments as possible, by using station resources and complying with all the constraints. An iterative improvement procedure is implemented in order to improve the resulting schedule.

Assignment problem

This section will describe the method adopted to solve the problem of matching (assigning) trains to departures. Assigning train t ∈ T to departure d ∈ D must meet the following technical constraints:

-The remaining distance before the maintenance of train t must be sufficient for departure d: rem D B M t ≥ req D d . -The time difference between arrival and departure must be large enough (for maintenance operations, parking,…).

We maint T ime (t, d) is the total maintenance duration required for scheduling t to d (0 if maintenance not required), -addT ime(t, d) is an additional time necessary for parking and handling the train, i.e.

in the case where the train is required to leave the arrivals platform before departure (non-immediate departure). The train may be parked either at the maintenance facility to undergo servicing or at any authorized resource before being scheduled for departure.

Additional time, addT ime (t, d), is a variable value to be determined; it is used to increase the chance of finding a feasible schedule, yet an excessive value of this variable may also decrease the number of assigned departures. This value has been experimentally set to lie within the range of 5-60 min. Only feasible assignments (t, d) are to be considered. Furthermore, the solution to the assignment problem must abide by the maintenance limit constraint i.e. the total number of maintenance operations during any day must not exceed a given number max Maint.

The following objectives are considered in the assignment phase:

1. maximize the number of assigned departures, 2. maximize the number of immediate departures, 1 3. minimize the number of maintenance operations, 4. minimize the number of assignments with a large difference between departure time and arrival time (greater than 10 h for example).

These objectives are mixed and exact importance (weight) of each objective part will be given while describing the methods used for solving the problem. The reason for introducing objectives ( 2) and ( 3) is to minimize the use of track groups since minimizing track group use will obviously decrease the chance of conflict. Another goal of inserting ( 3) is to minimize the use of maintenance facilities, which are considered critical resources. The aim in avoiding long waiting time between arrival and departure is to minimize the use of parking resources.

The following definitions will be used herein:

-nmbM(t, d): the number of maintenances required to schedule train t to departure d (equals 0 or 1);

-imm(t, d): equals 1 if d is immediate, 0 otherwise; -long(t, d): equals 1 if depT ime d -arr T ime t > L, where L is a parameter, 0 otherwise.
The assignment problem is made significantly more complex as the remaining distance for some trains is not known before scheduling the linked departures. The maximum number of maintenance operations per day constraint complicates the problem even more. A combination of greedy and integer programming (IP) algorithms has been implemented to solve this assignment problem.

Greedy procedure

The greedy procedure tries to match departures one by one. For each departure d, the best train is chosen in consideration of the defined objectives. The procedure can be formalised as follows:

-sort departures d ∈ D in ascending order with respect to departure time; -for each departure d ∈ D, find the "best" available train.

Departure assigned to train t will be denoted by d(t) (d(t) = -1 in case no departure is assigned to t). After assigning train t to linked departure d, the value rem D B M of the corresponding linked train is updated according to the constraint. The exact choice of train for each departure is accurately described in the pseudo-code of the greedy assignment (Alg. 1). The following rules are informally applied when choosing the train for each departure d:

-consider only currently unassigned trains; -whenever possible, choose an immediate assignment; -assignments without required maintenance and trains with a small rem D B M are preferable for non-linked departures;

1 Departure d covered by train t is said to be immediate if train t can be scheduled to d without leaving the platform.

Algorithm 1: Greedy assignment -in contrast to the previous rule, assignments with required maintenance and trains with a large rem D B M are preferable for linked departures; -long waiting times between arrival and departure are not desirable.

1 big M = 1 + max t∈T (max D B M t ) 2 Sort departures by time; 3 for d = 0 to |D| -1 do // each departure 4 best T rain ← -1; 5 minV alue ← 2 × big M; 6 for t = 0 to |T | -1 do 7 if d(t) = -1 ∧ (t,
The 'maximum number of maintenance operations per day' constraint is taken into account in the following manner. For each interval of days [day 1 , day 2 ], we define a current number of maintenance operations performed between days day 1 and day 2 by m(day 1 , day 2 ). Obviously, m(day 1 , day 2 ) must not exceed (day 2day 1 + 1) × max Maint.Eachtimea maintenance operation needs to be performed for assignment (t, d),thevaluem(day 1 , day 2 ) is updated for each interval of days [day 1 , day 2 ] containing [arr Day t , depDay d ],where arr Day t and depDay d represent arrival day of train t and the day of departure d respectively. Adhering to the given bound for each interval of days guarantees a feasible choice of days for each required maintenance operation; a simple procedure for choosing the exact day of maintenance, along with the proof of correctness, is given in Sect. 4.1.3. This same concept is found in the IP model, which enables a daily maintenance limit constraint to be represented linearly.

IP model

To enhance solutions to the assignment problem, the greedy procedure explained above is combined with a integer programming (IP) approach. The main difficulty in applying IP directly (independently) to solve the assignment problem involves linked departures. More specifically, the remaining distance before maintenance (rem D B M) of some trains is not known before assigning the linked departures. The greedy procedure described in the previous section and IP have thus been combined as follows:

-The assignment problem is solved by a greedy procedure; -Linked departure assignments are fixed (in updating the data on linked trains); -The resulting assignment problem is solved once again with IP.

Let F = {( f t 1 , f d 1 ), ( f t 2 , f d 2 ), . . . , ( f t k , f d k )} ⊆ T × D be the set of fixed assignments.
Let the set of possible assignments be defined as:

S = {(t 1 , d 1 ), (t 2 , d 2 ), . . . , (t n , d n )} ⊆ T × D,
where:

-each assignment (t i , d i ) is feasible; -none of the departures d 1 , . . . , d n is linked; -none of the trains t 1 , . . . , t n has been assigned to linked departure i.e. ∀i ∈ {1, . . . , n}, j ∈ {1, . . . , k} t i = f t j .

For each pair (t j , d j ) in S, a decision variable x j is defined: x j = 1 if t j is assigned to d j , x j = 0 otherwise. All the objective parts are merged into a single objective function by applying a non-negative weight for each of them. The objective function to be maximized is formalized as follows:

n j=1 x j × assignment W eight + durationW eight × 1 -long(t j , d j ) + immW eight × imm(t j , d j ) + maint W eight × 1 -nmbM(t j , d j )
The weights are chosen experimentally, and all results in the paper have been obtained with the following choices: assignment W eight = 1000, durationW eight = 100, immW eight = 10 and maint W eight = 1. Next, we define the constraints included in this model. Let nmbFi xed(day 1 , day 2 ) be the number of maintenance operations between days day 1 and day 2 required by fixed assignments i.e.

nmbFi xed(day

1 , day 2 ) = k i=1 nmbM( f t i , f d i ) × 1 [arr Day f t i ,depDay f d i ]⊆[day 1 ,day 2 ]
The constraint on maintenance is formulated by the following:

∀[day 1 , day 2 ] n j=1 nmbM(t j , d j ) × x j × 1 [arr Day t j ,depDay d j ]⊆[day 1 ,day 2 ] ≤ (day 2 -day 1 + 1) × max Maint -nmbFi xed(day 1 , day 2 )

Choosing maintenance days

As described earlier, the maximum number of maintenance operations per day constraint is met by complying with the limit for each interval of days [day1, day2], while updating the number of maintenance operations for each interval that contains [arr Day t , depDay d ] when servicing has to be performed for the assignment (t, d). The exact day for each maintenance operation still needs to be determined. A simple procedure, along with its proof of correctness, is presented in this section. This procedure functions as follows:

-sorting assignments (requiring maintenance) in ascending order by departure day and then by arrival day (example is given in Fig. 2); -for each assignment (t, d) in a sorted list:

-choose the first available day for maintenance, i.e. the first day in {arr Day t , . . . , depDay d } for which the maintenance limit has not been reached.

We will now prove the correctness of this procedure. Let M = {m 1 , m 2 , . . . , m k } be the set of all assignments requiring maintenance. Next, let A i and D i be the arrival and departure days of assignment m i respectively. We can now write

m i = (A i , D i ), A i , D i ∈ {1, 2, . . . , n Days}.
Claim If the following inequality holds for each interval of days [day 1 , day 2 ]:

k i=1 1 [A i ,D i ]⊆[day 1 ,day 2 ] ≤ (day 2 -day 1 + 1) × max Maint (1)
then the assignment of maintenance days using the procedure described above meets the 'maximum number of maintenance operations per day' constraint.

Proof This claim will be proven by way of contradiction. Let m j = (A j , D j ) be the first assignment for which a servicing day cannot be chosen by following the given procedure and M j-1 = {m 1 , m 2 , . . . , m j-1 } be the set of assignments with servicing days already set. This set-up means that the maintenance limit is reached for each day in [A j , D j ]. (*) Let day 0 be the first day such that the maintenance limit is reached for each day in interval [day 0 , D j ] (the existence of day 0 is obvious and day 0 ≤ A j ). Clearly, day 0 = 1 or -the limit is not reached for day 0 -1. (**)

Let F = { f 1 , f 2 , . . . , f l } ⊂ M j-1 be the set of assignments that have already been assigned to one of the days in [day 0 , D j ] (l = (D jday 0 + 1) × max Maint, since the limit has been reached for the entire interval). For each

f i = (A f i , D f i ) ∈ F, we have:
-A f i ≥ day 0 : otherwise, the chosen servicing day would not be greater than day 0 -1 because of the assignment rule and (**), -D f i ≤ D j : as a result of the sorting order.

The same holds for m j : A j ≥ day 0 and D j ≤ D j . Let us now consider the set U = F ∪ m j . As previously shown, the maintenance interval for each element of U lies in [day 0 , D j ], thus:

k i=1 1 [A i ,D i ]⊆[day 0 ,D j ] ≥ i∈U 1 [A i ,D i ]⊆[day 0 ,D j ] = |U | = (D j -day 0 + 1) × max Maint + 1
which is contradictory to the main assumption (1).

Scheduling problem

The goal of the second algorithm part is to schedule the assignments generated by the first phase inside the station while abiding by all resource constraints. Trains must move through the network/graph of inter-connected resources. All types of resources and constraints associated with the trains are given in the problem description provided in Sect. 2. A constructive procedure has been implemented here to solve the scheduling problem. The output schedule is then improved by an iterative procedure based on a local search. There are three scheduling options for each train t ∈ T : 1. t is scheduled for departure d ∈ D; 2. t is parked inside the station until the end of the planning time frame without being scheduled for any departure; 3. t is cancelled.

The schedule, possibly an empty one, must be given for each train t ∈ T . All resources used by the train must be specified, along with the exact time of entering and leaving each resource. The greedy procedure schedules the trains one by one, in a defined order (ordering will be addressed later). A complete schedule for the train is output before scheduling the next train. Nevertheless, all trains share the same resources and all constraints need to be complied with over the entire scheduling procedure.

Possible train movements

Modelling the scheduling problem exactly, i.e. taking all possible resource choices into consideration at every possible time instant, is not realistic given the size and structure of the instances proposed by SNCF. We have therefore limited possible train movements to the following:

-arriving at the platform via a given set of track groups (arrival sequence), -departing from the platform via a given set of track groups (departure sequence), -move from arrivals platform to yard, -move from arrivals platform to facility, -move from parking (facility, yard) to departure platform, -move from yard to facility, -move from facility to yard.

The train schedule will, for each train movement, specify the set of resources deployed with the exact resource enter and exit times. The connected set of resources used while moving the train from one place to another will be called path. P = (R 1 , R 2 ,..., R k ) denotes a path connecting resources R 1 and R k that starts at R 1 , visits resources R 2 , R 3 ,..., R k-1 and then ends at R k . Two consecutive resources on a path must be connected by a gate. The use of path P for given entry and exit times on each resource will be called travel.

To simplify the scheduling procedure, the time spent on each intermediate resource on a path (R 2 ,..., R k-1 ) is always a minimum. In the case of track groups, this time is set equal to trT ime, while in the case of other resources it equals to the constant value (minimum duration of resource usage) given as input. The travel of a given train is thus fully determined by the designated path and the starting time. Travel using path P and starting at time h will be denoted T (P, h). To conclude, the schedule of a train is represented as a set of travels {T (P 1 , h 1 ), T (P 2 , h 2 ), ... T (P l , h l )}. All paths potentially used for any movement are constructed before the start of the scheduling procedure. This set of paths includes those for each pair of resources (r 1 , r 2 ), such that r 1 and r 2 are of different types, with neither of them being a track group. Paths are sorted by length (i.e. total number of resources) for each pair (r 1 , r 2 ). Furthermore, should there be many paths between two resources, only the shortest ones are to be kept (15 shortest for example). This simple pre-processing step simplifies implementation considerably.

The scheduling procedure seeks to identify a feasible schedule for a given train with small number of travels. The choice of movements depends on the type of operations that need to be carried out (e.g. maintenance), total time to be spent at the station, etc. Train movements are planned one by one. If no feasible travel can be found at some point during the planning procedure, then the train will be cancelled, i.e. no attempt will be made to modify the previous movements.

Resource consumption and travel feasibility

Resource consumption is tracked by recording the set of all previous visits for each resource in the station. A visit to a resource has the following attributes: entry time and side, exit time and side, train length, and entry and exit gates. Each time the resource needs to be visited by a train, all constraints for a given resource are checked and the visit is only allowed if found to be feasible. Then, verifying the feasibility of travel T (P, h) simply requires checking the visit feasibility on each resource in path P, with corresponding entry and exit times being uniquely determined by h.

Time spent on a resource between two travels

One of the difficulties involved in train scheduling is to determine an exit time for the last resource in each travel. Knowing the exit time on the last resource is required in order to check constraints regarding this particular resource. An exact exit time is often not known before the next travel is planned. The following strategy was used to deal with this issue:

1. If the last travel resource is a yard: the exit time is equal to departure time if the train is to be scheduled for a departure; otherwise, the exit time is the end of the planning horizon. 2. If the last travel resource is a facility (for either parking or maintenance).

-same as (1) in the case maintenance is not required, -otherwise, exit time is equal to the minimum between departure time and facility entry time plus 12 h.

3. If the last resource of travel T (P i , h i ) is a platform: travel T (P i , h i ) and T (P i+1 , h i+1 ) are planned together. This step is equivalent to planning a single travel, with possible routes/paths being a combination of two paths (paths for travels T (P i , h i ) and T (P i+1 , h i+1 )), yet time spent on the platform is no longer fixed and needs to be determined.

Travel starting time

An important decision to be made when scheduling each train is the starting time for each travel. Some starting times are fixed, such as the time of arrival and departure, while others are to be selected from a feasible set of time instants. An ideal starting time, ideal ST , will be defined for each travel. We can always calculate the earliest and latest possible travel times, est and lst, which depend on the time constraints such as minimum resource times, travel duration, fixed arrival and departure times, etc. The ideal travel starting time depends on the type of travel; for our purposes, the following was used:

-if arrival train t needs to be moved from platform (to yard or facility) then the ideal starting time will minimize the dwell cost on the platform, i.e. ideal ST = arr T ime t + ideal Dwell t ; -if train t, parked at a yard or facility, needs to be moved to the platform for departure d then the ideal starting time will minimize the dwell cost on the platform, i.e. ideal ST = depT ime dideal Dwell dtravel Dur , where travel Dur is the duration of travel; -if the train is to be moved from one parking resource to another (i.e. from yard to facility or vice versa) then the ideal starting time is the earliest possible starting time, est.

Once the ideal travel starting time, ideal ST , has been determined, the next step seeks to choose a starting time, between the earliest and latest possible, as close as possible to ideal ST . Formally speaking, the selected starting travel time, h, is the first one from the set {ideal ST, ideal ST -δ, ideal ST + δ, ideal ST -2δ, ideal ST + 2δ, . . .}, such that h ∈ [est, lst] and travel T (P, h) is feasible for some path P. Parameter δ is chosen from the interval [10s, 60s].

Dealing with parking capacity

Since the station has limited capacity, it is not possible for the number of trains arriving at the station to significantly exceed the number of departures from the station. Consequently, most trains associated with arrivals must be scheduled to a departure. However, some trains may remain at the station until the end of the planning horizon, though this number is typically much smaller than the number of trains scheduled to a departure. Furthermore, if station resources are critical, it is not desirable to consume them with the trains not scheduled for any departure, which could potentially disable the departure scheduling of some trains. We have therefore used the following simple heuristic in the scheduling procedure:

1. planning departures: schedule each assigned train t (d(t) ≥ 0) and if the train cannot be successfully scheduled for departure d(t), then cancel it; 2. park unassigned and cancelled trains at the very end of the procedure (after optimizing the solution).

It should also be noted that assignments with too much time between arrival and departure are not desirable from the standpoint of yard capacity, which is taken into account during the assignment phase.

Choosing gates: avoiding conflicts on track groups

The main difficulty with this problem, from our experience, lies in effectively choosing the gates for each track group to enter and exit, as this gate selection will allow more trains to travel on the track groups without conflict. As defined in Sect. 2, conflicts on track groups are prohibited. For each travel T (P, h) by a train t, a set of entry/exit gates on each track group in P needs to be determined. As with all other resources, the exact entry and exit times for each track group are known if the starting time, h, of the travel is given.

Let n 1 be the number of possible gates to choose for an entering track group TG ∈ P,and n 2 the number of possible gates for exiting. We then have a total of n 1 ×n 2 possible moves to choose from. It is simple to check whether or not the selected move conflicts with any of the previous moves on the track group. For this purpose, as with any other resource type, we have kept a set of all visits (moves) to the track group, and only those moves that do not conflict with any moves in the given set are to be allowed. A set of entry/exit gates without conflicts must be determined for the entire travel T (P, h), which means that a feasible move needs to be found on each track group in P. Consequently, the number of possible combinations of moves becomes greater. One should notice that choice of exit gate on one resource automatically determines the choice of entering gate on the next one. A simple depth-first search (DFS) to find a feasible set of moves for travel has been used. This procedure explores all possible combinations of moves (one move for each track group in P) until a feasible one (without conflicts) is found. The most basic way of using a DFS procedure is to begin with the first possible gate on each track group and increase the gate index, according to a depth-first sequence, whenever a feasible choice has not been found. This manner of choosing the gates is not necessarily a good one as regards track group usage. To improve the choice of gates, let us attempt to identify a different order for exploring the possibilities in a DFS procedure. Formally, for each path P = (R 1 , R 2 ,..., R n ), a "preferred" entry gate on each resource in P will be defined and the DFS procedure will explore all possibilities by starting with a preferred gate on each resource. The set of preferred gates for travel T (P, h) is determined according to the first and last resources, more specifically R 1 and R n in P, and depending on the positions of these resources relative to the neighbouring track groups, R 2 and R n-1 .It should be noted that the majority of travels start or end at the platform. Consequently, the most critical track groups are those either connected to or close to the platforms. We have therefore decided to define the preferred gates solely according to the relative position of the platform with respect to the connected track group. If R 1 is the jth of N platforms connected to track group R 2 (according to gate indices) and g 1 , g 2 , . . . , g k are the gates from R i to R i+1 (2 ≤ i < n), then a preferred gate is g l , where: l = j×k N . The same rule is applied if R n is a platform. For example, if the chosen platform is the top platform, then it is only natural to choose the top gate on each resource in path P. We have conducted several experiments with a more complicated choice of gates, however the results obtained only changed slightly and were not necessarily always better. Moreover, the local search procedure described at the end of this section will question this choice of gates.

Virtual visits

One of the difficulties in avoiding conflicts is not knowing the "future traffic", i.e. overall track group use. This issue is particularly important when choosing the starting times of travels without a fixed starting time (i.e. all travels except arrivals and departures). Very often, many different possibilities are feasible and just one has to be chosen, although choosing any one of them might potentially block more trains yet to be scheduled than choosing another one. We have introduced the concept of "virtual visits" to improve the starting time of each travel. Virtual visits can be viewed as the potential visits capable of occurring on the track groups in the future. Virtual visits will be generated for each arrival and each matched departure (by the assignment procedure) and then taken into account when choosing the starting times and gates for the travel. The set of virtual visits V is built as follows:

-for each arrival t ∈ T and each matched departure d ∈ D -randomly choose a compatible platform p, -find a set of gates for arrival/departure (sequence + platform) with a minimum number of conflicts with V (as explained in previous section), -add the matching set of visits to the track groups to V .

The set of virtual visits is computed at the start of the scheduling phase, before scheduling any train. Next, during train scheduling, the starting time of each travel not matching an arrival or departure is selected in order to minimize the number of conflicts with virtual visits. The virtual visits of train t are removed from V when the scheduling procedure for t has been completed (t is scheduled for departure, parked or cancelled).

Scheduling order

Trains are to be scheduled independently and consecutively, one by one. Some trains however may have a higher scheduling priority than others. For example, cancelling a train assigned to a linked departure could cause cancellation of the linked trains, and some trains use far fewer resources than others, etc. Trains are therefore scheduled in the following order:

1. Assigned trains, (a) trains that may be departing immediately: only arrival and departure gates are used, (b) trains assigned to linked departures: uncovering a linked departure may cause more uncovered departures, (c) trains that do not require any maintenance, (d) remaining assigned trains, 2. Unassigned trains.

Constraints on linked departures are complied with, e.g. if train t 2 ∈ T is linked to departure d ∈ D and t 1 ∈ T is assigned to d, then t 1 must come before t 2 in the given order.

Iterative improvement procedure

This section recommends an iterative procedure for improving the schedule. This procedure operates as follows:

-(1) schedule more trains by allowing conflicts in the track groups, -(2) resolve conflicts by means of a local search, -repeat steps (1)-(2) until the stopping criteria are met.

The entire solution procedure is illustrated in Fig. 3.

Feasible to infeasible solution with more trains

The first step of this improvement procedure consists of adding more trains (and departures) to the feasible schedule by allowing conflicts. For each train added, the allowed track group conflicts are limited to a given number (e.g. a maximum of 3 conflicts per train). This scheduling procedure is the same as the one previously explained, but without adhering to the constraint on track group conflicts. All other constraints are to be met. An infeasible solution generated in this manner will serve as input for the local search procedure described below.

Local search to resolve track group conflicts

An infeasible solution is repaired by means of a local search procedure. The aim of this procedure is to change the choice of gates in order to reduce the number of conflicts to zero. The entry and exit times are to remain unchanged for each visit, as is the list of resources allocated for each train. Accordingly, a complete schedule for the train will either remain the same or be deleted (in the case of cancelling the train). The initial configuration (solution) is an infeasible set of visits on track groups. A visit is represented by a pair of gates (g1, g2). The configuration is denoted by V ={(g1 1 , g2 1 ),...,(g1 n , g2 n )} and the initial one by V 0 ={(g1 0 1 , g2 1 0 ),...,(g1 0 n , g2 n 0 )}. The domain of each variable g1 i (g2 i ) includes all gates connecting the same pair of resources as g1 i 0 (g2 i 0 )andnull value. A visit corresponding to (g1, null), (null, g2) or (null, null) is called a partial visit. It is assumed that no conflict occurs with a partial visit. A configuration V is called partial if it contains a partial visit.

Remark Two successive visits of the same train (g1 i , g2 i ) and (g1 j , g2 j ) share a common gate, i.e. g2 i = g1 j . For these cases, the local search procedure will perform the same modification at both gates. The objective of the local search procedure is to minimize the number of cancelled trains. A train is cancelled if one of its visits is partial.

Greedy procedure to resolve track group conflicts

The first part of a local search is the greedy procedure to clear conflicts by deleting gates, i.e. setting the gate values to null. The objective here is to compute a partial, but feasible, configuration (set of visits). The heuristic is simple: delete the gate that will decrease conflicts by the greatest number until conflicts no longer exist.

Tabu search on the partial feasible configuration

The tabu search procedure starts from a partial, but feasible, configuration of gates given by the previous procedure. The goal is to assign gate values to partial visits while keeping the configuration feasible. The following two elementary moves are carried out:

-ADD gate means one of 2 possible moves:

-(null, g2 i ) ⇒ (g1 i , g2 i ) (g1 i = null and g1 i leads to the same neighbour resource as g1 0 i ) -(g1 i , null) ⇒ (g1 i , g2 i ) (g2 i = null and g2 i leads to the same neighbour resource as g2 0 i ) -DROP gate means one of 2 possible moves:

-(g1 i , g2 i ) ⇒ (null, g2 i ) (delete g1) -(g1 i , g2 i ) ⇒ (g1 i , null) (delete g2)
These modifications are also applied to the next/previous visit of the given train (see remark in Sect. 4.3.2). The local search move consists of a single ADD move and, should conflicts occur, is to be followed by a few DROP moves in order to clear the conflicts. Deleting a gate g i (DROP) is allowed only if g i has not been added for a given number of iterations (i.e. if setting g i to null is not tabu). The number of iterations for which deleting a gate is tabu equals the frequency of adding this gate. The current configuration is evaluated by the following hierarchical function:

1. number of trains cancelled, 2. number of deleted gates, i.e. the number of gates with a null value.

At each iteration, a non-tabu move that minimizes this function is performed. If there are two or more moves with the same objective, then a random choice is made. This process is repeated until no non-tabu move exists or until a maximum number of moves without improvement has been reached. In all reported experiments this limit has been set to 300.

An illustration of the objective function change during this improvement procedure is given in Fig. 4. It can be noted that most of the improvement occurs during the early stage and not many new trains are added at the end. The improved results due to the local search are illustrated in Fig. 5.

MIP instead of Local Search

The problem of repairing the conflicts explained above, and solved by local search procedure, may also be solved in different ways. One possible approach that we tested is to define a problem as a mixed integer program (which is not too complicated), with the objective of determining the maximum subset (in terms of number of the feasible solutions. In addition, many more iterations can be done in the same running time if local search is used, which is crucial for some instances. Similar conclusions can be drawn when MIP is used with a given running time limit (thus, transforming an exact solution approach into an heuristic one). The percentage of arrivals and departures cancelled varies from 11.90% on the B3 instance to 44.21% on B12, the average value being 26.17%. Train cancellation is mainly due to the fact that track group conflicts are prohibited. These conflicts are not always the actual conflicts due to a "black-box" approach introduced to model track groups in the current problem. The approach does not appear to lead to a solution that can be used in practice, due to a large number of cancelled arrivals and departures. As previously stated, we have been trying to solve the problem 'as posted' in the competition, adhering to all the given constraints to obtain the best possible result. However, the problem needs to be formulated differently in order to recommend solutions that can be used in practice. It is important to mention that the original problem formulated at the start of the competition allowed track group conflicts and there was a penalty in the objective function for each conflict. But the organizers changed this in a later phase.

Conclusion

This rolling stock unit management problem on a railway site is extremely difficult to solve for several reasons. Most induced sub-problems, such as the train assignment, scheduling, track group conflicts and platform assignment, are indeed complicated. In order to solve this problem, we implemented a two-phase approach that combines exact and heuristic methods. A natural way of approaching the problem consists of dividing it into two sub-problems, the first consisting of matching (assigning) trains to departures and the second consisting of planning train movements (scheduling) inside the station, and then solving both sequentially. It would also be quite natural to consider a break down of the problem by days (and subsequently combining the days), as there are hardly any arrivals and departures at night. However, the experiments we performed have shown that the quality of the solutions decreases, while not greatly increasing algorithm simplicity or computational time. This was the case, in particular, for the first version of the problem (i.e. with conflicts on track group as soft constraints), where many more trains have not been assigned to any departure. It should also be noted that the assignment procedure presented in this paper tends to schedule the arrival and departure of atrain on thesameday.

The presence of linked departures and a constraint on the daily maintenance limit further complicate the assignment problem. Otherwise, the problem could be solved in a polynomial time by means, for instance, of the maximum weighted matching algorithm. A common strategy for overcoming these constraints calls for modelling the assignment problem as a mixed integer program. The number of linked departures in the given set of instances however makes the IP model unworkable due to the tremendous number of variables to be generated in order to cope with the linked departures. A greedy procedure has therefore been used to solve the assignment problem. The departures are sorted by departure time and matched to the trains one by one, in a greedy manner. A simple function was used to evaluate the quality of assignment (t, d). Solutions to the assignment problem are improved by combining a greedy procedure with IP, whereby all train assignments with linked departures obtained by the greedy procedure are fixed and the remaining assignment is solved by IP. We recommended the simple idea (and proved its correctness) of modelling the constraint on the daily maintenance limit as a linear one.

The second step in solving the problem is to plan train movements inside the station while complying with all resource constraints and cancelling as few trains as possible. This problem is very complex and contains a huge number of decision variables (resources, gates and entry/exit times must be specified for each train); hence, modelling the problem exactly and solving it efficiently are likely to be impossible. We therefore opted for a constructive procedure to schedule the trains. They are scheduled sequentially, one by one, after being ordered by a given set of criteria. The possible train movements are restricted to just a few of critical importance in order to reduce problem complexity. For this purpose, a set of potential paths that trains are allowed to use was compiled at the beginning of the procedure. A concept of virtual visits was offered to expand the choice of starting times for each travel in order to address track group conflicts. An iterative procedure was adopted to improve scheduling phase solutions, by allowing infeasible solutions as regards track group conflicts and then resolving these solutions by means of a local search. The introduction of both virtual visits and an iterative improvement procedure helped greatly improve these solutions. The algorithm described in this paper was ranked first at the ROADEF/EURO Challenge 2014.

Fig. 1

 1 Fig. 1 Example of infrastructure with 8 platforms, a single yard, 5 maintenance facilities and 4 track groups connecting them

Fig. 2

 2 Fig. 2 Assignments ordered by departure day and arrival day

Fig. 3

 3 Fig. 3 Solution process

Fig. 5

 5 Fig. 5 Improvement by local search (instances B1-B12)

  Objective function oscillation during improvement phase for instances B1 and X4. The X-axis represents time elapsed since improvement procedure start, while the Y-axis represents the value of the objective function after adding new trains to the feasible solutions and after the local search procedure scheduled trains) of train schedules without conflicts on track groups. The overall improvement procedure remains the same, we only try to "repair conflicts" by using mixed integer programming instead of local search. If we consider a single improvement phase iteration (add trains + repair) i.e. solving the problem-given a set of train schedules with conflicts, choose the gate values so that a minimum number of departures/arrivals is cancelled-it is clear that MIP will produce better (or at least the same) solutions than local search. However,

		•10 5			•10 6
				2
		7.8
		7.6
				1.5
	objective	7 7.2 7.4	Objective	1
		6.8		0.5
		6.6				withoutLS
		0		0	50		100 withLS	150	200	250	300	350
	0 Fig. 4 1 50 1 1.1 1.2 1.3 1.4 •10 6 objective	2	100 3	4	time (sec) 150 time (sec) 5 6 7 Instance	200 8	250 9 10 11 12	300	350

using MIP instead of local search has not made any (or negligible) improvements to the final results using presented improvement framework, particularly for a 10-min running time when using MIP usually produces poorer results. The main reason for this is the fact that after many improvement phase iterations (e.g. 100) solution values obtained by local search come very close to the values of infeasible solutions, i.e. only a few trains can be added to

Table 2

 2 Results on data sets B, X: average and best values from 20 runs of 10 min are reported, as well as competition results

	Instance	Challenge		With MIP included (20 runs)
		Our result	Best others	Average	Best
	B1	699,750	1,026,208	643,651	622,879
	B2	636,550	980,607	582,000	561,579
	B3	545,974	976,754	480,960	462,848
	B4	1,263,764	1,671,107	1,179,584	1,142,660
	B5	1,573,290	2,060,485	1,471,631	1,417,578
	B6	1,097,572	1,586,010	1,047,493	993,580
	B7	168,369	257,986	171,257	167,993
	B8	213,190	291,216	221,480	208,573
	B9	1,332,256	1,719,646	1,234,501	1,130,644
	B10	168,457	155,100	149,301	142,600
	B11	1,192,687	1,142,072	1,100,200	1,076,260
	B12	620,527	571,497	577,000	556,853
	X1	790,506	1,036,393	712,260	683,939
	X2	1,176,901	1,323,148	890,666	874,014
	X3	735,579	1,040,464	669,864	655,220
	X4	1,109,468	1,608,134	1,026,635	983,693
	X5	1,012,268	1,519,608	925,955	884,348
	X6	943,024	1,560,462	822,780	768,395
	X7	1,642,024	1,914,783	1,569,772	1,543,090
	X8	534,889	777,363	560,170	553,427
	X9	732,818	871,027	748,539	711,395
	X10	193,210	184,022	180,707	168,407
	X11	1,107,732	988,996	1,018,810	965,892
	X12	501,218	467,605	477,634	455,736
	Best competition results are shown in bold

This paper

Final algorithm

The pseudo-code of the final algorithm is given in Algorithm 2.

Algorithm 2: Final Algorithm

Evaluation and computational results

The method has been tested on the official set of competition instances provided by SNCF. This test data consists of two sets of instances, i.e. dataset B and dataset X. The first set was made available during the competition, while dataset X is a hidden set of instances provided The algorithm sequentially produces independent solutions until the time limit is exceeded and retains the best one. The results obtained on datasets B and X, in a 10-min running time, are listed in Table 2; average and best result over 20 runs with different initial seeds for the random number generation are reported. We also report the results submitted for the competition, along with the best results obtained by other competitors (our submitted program produced less good results due to the fact that IP model given in Sect. 4.1.2 was not included).

There is clearly a significant difference between the average and best solutions, sometimes more than 5%. This is due to the randomness in the heuristics proposed. However, running the algorithm for more seeds (e.g. 100 instead of 20) or with larger time limit will not yield a significant further improvement for a given set of instances.