An adaptive procedure for railway periodic timetabling andtracks assignment
G. Jouberta,b,∗ , A. Jougletb , D. Naceb and M. Posteca
a SNCF Réseau - DGEX, Saint-Denis, France{guillaume.joubert, marion.postec}@reseau.sncf.fr
b Heudiasyc, Compiègne, France{guillaume.joubert, antoine.jouglet, dritan.nace}@hds.utc.fr∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium onTransportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius IslandApril 4, 2022
Keywords: heuristic, timetabling, tracks assignment, scheduling

1INTRODUCTION

One of the tasks of SNCF Réseau, the French Railway Infrastructure Manager, is to produce
yearly timetables. Each train is characterised by an origin station, a destination station, and iscomposed by several operations : a train can run on line sections and pass through or dwell at
train stations. We name slot the spatio-temporal capacity reservation on the infrastructure thatis necessary to allow a train to perform its operations. A slot is said to be scheduled when aprecise time is decided for each of its operations. In this study, we focus on a specific phase of
the production of yearly timetables. This phase occurs about two years before the execution of
the timetables, and is called capacity structuring phase (SNCF_Réseau, 2021).
To tackle this planning phase, a Service Intention (SI) (Wüst et al. , 2018) is built by several
stakeholders and describes a set of slots to be scheduled within a given cyclic period of time.
For each slot, we know the origin and the destination points, the line sections and stations of
its itinerary, the stations where a stop is required and those where it is not, and the nominal
duration of each operation of running in line sections and dwelling at train stations. Moreover,
we have a railway infrastructure description, and timetabling rules that locally describe the way
to schedule one slot according to another in order to avoid the use of a same track at close times.
The challenge for SNCF Réseau is to assign a starting time for each operation of each slot ofthe SI, such that no conflict exists between the scheduled slots. This work aims to support thetimetable planners in this task, providing them suggestions of sets of scheduled slots covering theSI. This decision aid can be particularly useful when important modifications in the infrastructure(e.g. maintenance and construction) and in the SI appear with respect to the previous situations.
In addition to scheduling times for the slots, we provide solutions on which tracks are scheduled
as well for its operations. Those decisions are important since they fully determine the itineraryof trains and allow a clear view of the resource usage on busy sections of the infrastructure.

2PROBLEM DESCRIPTION

We aim at solving a combination between a Train Timetabling Problem and a Train Platforming
Problem (Petering et al. , 2015, Sels, 2016) with periodic time horizon and mesoscopic infrastructure scale. This scale is more detailed than the macroscopic one because we represent tracks
inside line sections and train stations. It is less detailed than the microscopic scale because we
TRISTAN XI Symposium

Original abstract submittal

G. Joubert, A. Jouglet, D. Nace and M. Postec

2

consider a decomposition of the infrastructure in homogeneous sections that are composed byparallel tracks with the same speed limit. If several microscopic routes exist between tracksof adjacent sections, we will consider only one corresponding route at the mesoscopic scale. Acompatibility matrix informs about the possibility for two trains to run simultaneously on mesoscopic routes. We model this problem by a Track-Choice Periodic Event Scheduling Problem(TC-PESP) (Wüst et al. , 2018), an extension from the PESP (Serafini & Ukovich, 1989), andwe propose a method in section 3 to solve it heuristically.
Let I = {1, 2, . . . , N } be the set of slots of the SI and Ji = {oi1 , oi2 , . . . , oini } the set of operations of slot i. S is the set of sections, that can either be line sections or train stations. Eachsection contains one or more parallel tracks that are travelable in one or both directions. For
each operation oij planned on a particular section s ∈ S, the problem is to choose a track where
the operation will be assigned on s, and a value for the starting time tij of operation oij , withtij ∈ [0..T [, where T stands for the periodic time horizon, also named period, in minutes. The
track assignment for every operation of a slot defines its precise itinerary on the infrastructure.
Let pij be the processing time of the operation oij , i.e. the nominal duration of the operation
oij including a mandatory robustness margin in order to allow some flexibility in the driving
behaviour and to absorb small delays that may occur. We look for a solution such that thePtotal duration of each slot is equal to j∈Ji pij . We can enforce this property by adding no-wait
conjunctive constraints modulo T over the operations of each slot : each operation of a slot has
to begin immediately after the completion of the precedent one, if they exist. Each operation
has to be assigned to a unique track among the tracks of the section where the operation takes
place. For any two consecutive operations of a slot, the track assignments have to be such thatit exists a corresponding mesoscopic route in the infrastructure.
Three types of safety constraints guarantee that no two slots use the same tracks simultaneously
or too close in time. Spacing constraints separate the beginning time of use of a line section
track by slots planned in the same direction. Reuse constraints ensure that the use of a trackis possible only if it has been released for a certain amount of time. Reuse constraints workon station tracks, and also on line section tracks in the case of slots planned in the opposite
direction. Crossing constraints prevent slots to be assigned on tracks that generate incompatible
routes whenever those slots are scheduled too close in time. Commercial requirements such as
passenger connections between slots at stations, slots splitting or merging, predefined temporal
spacing or predefined starting times for some operations are also to be taken into account.

3METHODOLOGY

We modelled this problem by an ILP, implemented and solved using an off-the-shelf solver. Theinfrastructure considered is a real case study around Chambéry area. The solving time increases
when we increase the number of slots in the SI. Thus we propose a heuristic in order to keep thisproblem tractable for larger instances. Recent research tackled a similar problem by a columngeneration framework (Reisch et al. , 2021) based on a train path assignment heuristic (Dahmset al. , 2019). Our procedure is illustrated in Figure 1. The model is now decomposed into atimetabling module in charge of deciding the starting times of the slots, and a tracks assignment
module responsible for the tracks decisions. The procedure is described in details below.

3.1

Timetabling module

The main feature of the timetabling module consists in the replacement of the safety constraints ofthe problem description by a conflict evaluation function that counts the number of inactivatedsafety constraints unsatisfied by the slots starting times. This allows to integrate the tracks
TRISTAN XI Symposium

Original abstract submittal

G. Joubert, A. Jouglet, D. Nace and M. Postec

3

assignment possible decisions without needing to fix them explicitly. Next subsections show how
we build a solution and iteratively solve the conflicts that may occur.

Figure 1 – Periodic timetabling and tracks assignment adaptive procedure flowchart
3.1.1

Constructive heuristic

This routine attributes a starting time for each slot of the SI, such that the aforementioned
conflict evaluation function is minimized in a greedy way. More precisely, at each step of theheuristic, a slot is selected to be scheduled, and a starting time is chosen for the selected slot.
Before each new step, we update for each remaining slot its number of possible starting times
for which the slot would be compatible with all the previously scheduled slots. The slot to bescheduled in priority is the one with the minimum strictly positive number of possible startingtimes that does not generate conflicts. In case of a tie, we look at the impact score of thoseslots: this score corresponds to the sum of the number of other slots planned on each section of
the operations of this slot. When a slot is selected to be scheduled, its starting time is chosensuch that it should impact as little as possible the number of possible conflict-less starting timesof the remaining slots to be scheduled. At some step of the heuristic, it is plausible that a listof slots cannot be scheduled in a conflict-free manner anymore. We prioritise those slots by theearliest heuristic step when they join the list, and we choose a starting time that deteriorates
as little as possible the conflict evaluation function. Once all the slots have been scheduled, theconstructive heuristic is completed. If the conflict evaluation value equals zero, then the tracks
assignment module is run. Otherwise, we stay in the timetabling module and resolve the conflicts
as explained below.
3.1.2

Local move

A solution of the timetabling module with a strictly positive conflict evaluation value is notconflict-free: infrastructure capacity is overused by some slots scheduled too close in time. Thoseslots are said to be involved in the conflict. When such a solution is found, a local move isperformed from the current solution to a new one, attempting to reduce the conflict evaluation
value. A local move consists in modifying the starting time of a small set of slots of the solution. A
heuristic way to choose among the moves is to select the slots that are involved in the maximum
number of conflicts. To escape from local optima that might prevent to reach a conflict-freesolution, we embed the local search into a tabu framework detailed in the subsequent subsection.
3.1.3

Tabu parameters updates

A local move applied to a given set of slots is named combination. Each combination is associated with a tabu countdown initialized with value 0, along with a tabu duration initialized withvalue 1. A combination is applicable only when its tabu countdown equals 0. When applied, acombination becomes tabu for the next tabu duration iterations. Indeed, we assign to the tabu
countdown of this combination the value of its tabu duration, and the tabu countdowns of every
combination is decremented at each iteration if strictly positive. Another effect of the applicationof a combination is the increment of its tabu duration, for the next times it may be reselected. Asa result, the more a combination is selected because of the concentration of the conflicts on somespecific slots, the longer it will be temporarily unavailable in order to let other combinations
TRISTAN XI Symposium

Original abstract submittal

G. Joubert, A. Jouglet, D. Nace and M. Postec

4attempt to unlock the situation.

3.2

Tracks assignment module

A conflict evaluation value of 0 ensures that a track assignment for each operation of each slot
respecting all the safety constraints exists while keeping the starting times obtained from thetimetabling module solution. This module is solved almost instantaneously on the instances
we tested, the main difficulty is indeed resolved during the timetabling module which evaluates
carefully the mesoscopic capacity necessary to perform the tracks assignment.

4RESULTSThe SI contains 32 heterogeneous slots hourly scheduled on the Chambéry area infrastructure,including 8 crossing each other at stations of three unique tracks of the area, and 18 passing
at Chambéry, of which 7 in each direction between Chambéry and Montmélian. We present 20instances with the same SI, differentiated by the randomly generated initial solution considered
before applying local moves on sets of 1 slot. Table 1 shows the number of moves applied on setsof 1 slot to resolve the conflicts.
Table 1 – Number of moves on sets of 1 slot applied to resolve the initial conflicts of 20 instances
Initial conflicts
min max average
395 1368
553

Number of moves
min max average
17117
40

The same instances are unable to be solved when we remove the tabu framework.

5DISCUSSION

The timetabling methodology using a mesoscopic scale conflict evaluation function to take into
account the tracks assignment decisions gave promising results. Ongoing work includes theimplementation of the constructive heuristic as well as additional types of local moves to solve
the conflicts more efficiently.

References
Dahms, Florian, Frank, Anna-Lena, Kühn, Sebastian, & Pöhle, Daniel. 2019. Transforming automatic
scheduling in a working application for a railway infrastructure manager. Rail Norrköping Conference.
Petering, Matthew E.H., Heydar, Mojtaba, & Bergmann, Dietrich R. 2015. Mixed-Integer Programmingfor Railway Capacity Analysis and Cyclic, Combined Train Timetabling and Platforming. Transportation Science.
Reisch, Julian, Grossmann, Peter, Pöhle, Daniel, & Kliewer, Natalia. 2021. Conflict resolving - A local
search algorithm for solving large scale conflict graphs in freight railway timetabling. European Journalof Operational Research, 293, 1143–1154.
Sels, Peter. 2016. Large-scale, passenger oriented, cyclic railway timetabling and station platforming androuting. Thesis manuscript.
Serafini, Paolo, & Ukovich, Walter. 1989. A Mathematical Model for Periodic Scheduling Problems.
SIAM Journal on Discrete Mathematics, 2, 550–581.
SNCF_Réseau. 2021. Document de Référence du Réseau Ferré National, Horaire de Service 2023.
Wüst, Raimond, Bütikofer, Stephan, Ess, Severin, Gomez, Claudio, Steiner, Albert, Laumanns, Marco,& Szabo, Jacint. 2018. Periodic Timetabling with "Track Choice"-PESP based on given line concepts
and mesoscopic infrastructure. Operations Research Proceedings 2018.

TRISTAN XI Symposium

Original abstract submittal