Optimisation des tournées d’inspection des voies

Sébastien Lannez

To cite this version:

Sébastien Lannez. Optimisation des tournées d’inspection des voies. Mathématiques [math]. INSA
de Toulouse, 2010. Français. �tel-00595070�

HAL Id: tel-00595070

https://tel.archives-ouvertes.fr/tel-00595070
Submitted on 23 May 2011

HAL is a multi-disciplinary open access L’archive ouverte pluridisciplinaire HAL, est

archive for the deposit and dissemination of sci- destinée au dépôt et à la diffusion de documents
entific research documents, whether they are pub- scientifiques de niveau recherche, publiés ou non,
lished or not. The documents may come from émanant des établissements d’enseignement et de
teaching and research institutions in France or recherche français ou étrangers, des laboratoires
abroad, or from public or private research centers. publics ou privés.
 ฀
฀ ฀ ฀ ฀ ฀ ฀
%0$503"5
%&
-6/*7&34*5²
%&
506-064&

฀
฀ ฀
Institut National des Sciences Appliquées
฀ de Toulouse (INSA Toulouse)

฀ ฀ ฀
Systèmes Industriels
฀
฀
฀ ฀฀ ฀ ฀฀
Sébastien฀ Lannez
฀ jeudi 25 novembre 2010 ฀
฀
฀
฀

Optimisation des tournées

฀ d'inspection des voies
฀
฀
฀ ฀ ฀
Systèmes฀ (EDSYS)
฀ ฀ ฀ ฀
LAAS / CNRS
฀ ฀ ฀
Christian Artigues (LAAS/CNRS, Toulouse)
Michel Gendreau (CIRRELT, Montréal, Canada)
฀
Pierre Dejax (Ecole des
฀ Mines de Nantes)
Christian Prins (Université de
฀ Technologie de Troyes)
฀ ฀ ฀ ฀

Jean Damay (SNCF)

Dominique Feillet (Ecole des Mines de Saint-Etienne)
Frédéric Semet (Ecole Centrale de Lille)
François Vanderbeck (Université de Bordeaux 1)
 2
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
Table des matières

1 Introduction 11

I Présentation de la problématique 13
2 Environnement industriel et problématique 15
2.1 Les maintenances industrielles . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Le système ferroviaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.1 Les acteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.2 La production ferroviaire . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.3 Le référentiel d’enregistrement . . . . . . . . . . . . . . . . . . . . . . 17
2.3 Enjeux de l’auscultation ultrasonore par engins lourds . . . . . . . . . . . . . . 17
2.4 Projet grands axes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.5 Technique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.5.1 La détection par ultrasons . . . . . . . . . . . . . . . . . . . . . . . . 18
2.5.2 Les engins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.6 Étapes de la programmation . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.6.1 La conception des programmes d’auscultation . . . . . . . . . . . . . . 22
2.6.2 L’adaptation des programmes d’auscultation . . . . . . . . . . . . . . 22
2.6.3 La réalisation des programmes d’auscultation . . . . . . . . . . . . . . 23
2.6.4 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.7 Propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.7.1 Conception . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.7.2 Adaptation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.7.3 Réalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.8 Motivation et enjeux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3 Revue de littérature 31
3.1 Théorie des graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 Tournées sur arcs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.1 Problèmes principaux . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.2 Variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.3 Algorithmes de résolution . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4 Maintenances des installations ferroviaires . . . . . . . . . . . . . . . . . . . . 38

3
TABLE DES MATIÈRES TABLE DES MATIÈRES

4 Modélisation des tournées des engins de maintenances 41

4.1 Graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.1.1 Vue macroscopique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.1.2 Nœuds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.1.3 Arcs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2 Modèle journée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.3 Modèle engin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.4 Formulations mathématiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.4.1 Formulation arc-flot (Marc ) . . . . . . . . . . . . . . . . . . . . . . . . 47
4.4.2 Formulation chemins (Mchemin ) . . . . . . . . . . . . . . . . . . . . . . 49
4.5 Décompositions mathématiques . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.5.1 Décomposition de Dantzig-Wolfe de Marc (MDW ) . . . . . . . . . . . . . 51
4.5.2 Décomposition de Benders de Mchemin (MBenders ) . . . . . . . . . . . . . . 53

II Mise en œuvre 57
5 Approche algorithmique 59
5.1 Schéma général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.2 Présentation du problème maître augmenté MBenders
0 . . . . . . . . . . . . . . . . 61
5.3 Résolution de MBenders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
0 62
5.3.1 Initialisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.3.2 Génération des colonnes . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.3.3 Détermination d’une solution entière . . . . . . . . . . . . . . . . . . . 67
5.4 Génération des coupes de Benders Combinatoires . . . . . . . . . . . . . . . . 69
5.4.1 Description des sous problèmes de Benders . . . . . . . . . . . . . . . 69
5.4.2 Simplification des coupes BC pour MBenders0 . . . . . . . . . . . . . . . . 69
5.4.3 Coupe combinatoire « voyageur de commerce avec fenêtres de temps » 71
5.4.4 Coupe linéaire « affectation calendaire » . . . . . . . . . . . . . . . . . 73
5.5 Projection des coupes BC : Pseudo Coupes Locales . . . . . . . . . . . . . . . 75
5.6 Variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.6.1 Heuristique gloutonne d’arrondi : AlgoChvatalCover incrémental . . . 76
5.6.2 Heuristique d’ordonnancement : AlgoSchedList avec branchement . . . 77
5.6.3 Heuristique d’ordonnancement : AlgoSchedList avec VCG . . . . . . . 77
5.7 Un algorithme glouton évolué : AlgoGreedy . . . . . . . . . . . . . . . . . . . 79

6 Tests numériques 81
6.1 Présentation du jeu de données . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.2 Détails d’implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.2.1 MBenders
00 : Initialisation . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.2.2 AlgoEspprc : Durée maximum dynamique . . . . . . . . . . . . . . . . 83
6.3 Comportement des algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.3.1 Heuristique de couverture . . . . . . . . . . . . . . . . . . . . . . . . 83
6.3.2 Génération des journées de services . . . . . . . . . . . . . . . . . . . 86
6.3.3 Sélection des journées de services . . . . . . . . . . . . . . . . . . . . 93
6.3.4 Ordonnancement des journées de services . . . . . . . . . . . . . . . . 93
6.4 Performance globale et impact des chantiers . . . . . . . . . . . . . . . . . . . 96

4
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 6.4.1 Algorithme de référence . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.4.2 Algorithme final . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.5 Influence des pseudo coupes locales . . . . . . . . . . . . . . . . . . . . . . . 97

7 Logiciel 99
7.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
7.2 Données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
7.2.1 Entrées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
7.2.2 Sorties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
7.3 L’interface graphique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.3.1 Quelques écrans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.4 Le cœur de calcul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
7.4.1 Patrons de conception . . . . . . . . . . . . . . . . . . . . . . . . . . 108
7.5 Paramétrage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
7.6 Cas d’utilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

III Conclusion 113

8 Conclusion et perspectives 115
8.1 Perspectives de recherches académiques . . . . . . . . . . . . . . . . . . . . . 115
8.2 Perspectives d’amélioration industrielles . . . . . . . . . . . . . . . . . . . . . 116
8.2.1 engins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
8.2.2 pré-opérationnelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

Annexe 119

A Réseau grands axes 121

5
TABLE DES MATIÈRES TABLE DES MATIÈRES

6
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
Résumé

La SNCF utilise plusieurs engins spécialisés pour ausculter les fissures internes du rail. La
fréquence d’auscultation de chaque rail est fonction du tonnage cumulé qui passe dessus. La
programmation des engins d’auscultations ultrasonores est aujourd’hui décentralisée. Dans le
cadre d’une étude de réorganisation, la SNCF souhaite étudier la faisabilité de l’optimisation
de certaines tournées d’inspection. Dans le cadre de cette thèse de doctorat, l’optimisation de la
programmation des engins d’auscultation à ultrasons est étudiée.
Une modélisation mathématique sous forme de problème de tournées sur arcs généralisant
plusieurs problèmes académiques est proposées. Une méthode de résolution exacte, appliquant
la décomposition de Benders, est détaillée. À partir de cette approche, une heuristique de géné-
ration de colonnes et de contraintes est présentée et analysée numériquement sur des données
réelles de 2009. Enfin, un logiciel industriel développé autour de cette approche est présenté.

SNCF is using specialised rolling stock units to inspect internal defects in rails. Rail’s ins-
pection frequency is defined by the cumulative weight of the trains which are going through. In
2009, the scheduling of these train units is decentralised. SNCF is studying the centralisation
of this process. In this Ph.D. thesis, a new problem, the Railroad Track Inspection Scheduling
Problem is studied.
A mathematical formulation, based on the generalization of classical arc routing models,
is proposed. An exact solving approach, based on Benders’ decomposition scheme, is detai-
led. From this approach, a column and cut generation heuristic is developed, implemented, and
tested on real datasets for 2009. The industrial software developed around this heuristic is pre-
sented.

7
TABLE DES MATIÈRES TABLE DES MATIÈRES

8
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
Remerciements

Christian Artigues, je te remercie pour ton prosélytisme, tu m’as enrôler dans la section d’op-
timisation de l’IUP d’Avignon et depuis je n’ai pas quitté ce domaine. Ta rigueur scientifique et
tes qualités relationnelles font de toi un directeur de thèse parfait.

Michel Gendreau, je te remercie pour tous ces petits conseils si précieux et le recul dont tu
as sus faire preuve pendant nos réunions. Tu as accepté de co-diriger cette thèse et, tout comme
pour ma maîtrise, je t’en suis très reconnaissant.

Jean Damay, merci chef !

La SNCF a été pour moi un formidable environnement de travail et de développement. Je re-

mercie très chaleureusement, David de Almeida, Nicolas Marcos, Philippe Pouligny et Christian
Weber de m’avoir fait confiance et de m’avoir offert la possibilité de continuer ma formation
en optimisation combinatoire sur un sujet aussi passionnant et complexe. Merci aussi à Phi-
lippe Mercier, Philippe Lemarchand et François Pincemaille pour m’avoir aussi bien décrit leur
métier.

Merci à Mathilde Carlier-Clairouin, Caroline Desprez, François Ramond et Francis Sourd

d’animer avec tant de générosité le département d’optimisation de la SNCF.

Enfin, je remercie Jeanne de m’avoir soutenue et d’avoir facilité la tâche des correcteurs en
filtrant les erreurs de ce mémoire.

9
TABLE DES MATIÈRES TABLE DES MATIÈRES

10
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
Chapitre 1

Introduction

Ce mémoire de thèse de doctorat traite de la modélisation mathématique et de la résolution

d’un problème d’optimisation de tournées d’inspection du réseau ferroviaire.

Des trains spécialisés sont utilisés pour vérifier l’état des composants de l’infrastructure (rails,
caténaires, nivellement, ponts) ou pour les entretenir (désherbage, taille des haies). Ils servent à
inspecter le réseau ferroviaire pour vérifier sa conformité avec les standards de sécurité. Le pro-
blème d’optimisation des tournées d’inspection que nous proposons est assez générique pour
pouvoir être adapté facilement à différents types d’engins. Dans le cadre de ce mémoire, seule
l’application aux engins d’auscultation à ultrasons est présentée. Ces engins de mesures dé-
tectent les fissures internes du rail. Ces informations sont importantes pour l’exploitation du
réseau ferroviaire car elles permettent de prévenir les ruptures de rail en déclenchant des mainte-
nances correctives. Bien que la majorité de ces ruptures ne fassent pas dérailler les trains 1 , elles
peuvent perturber très sérieusement le trafic. Les fissures des 30 000 km de lignes (50 000 km de
voies) du réseau ferré français sont surveillées par les 23 régions SNCF à l’aide de ces engins.

Ce problème industriel a été initialement proposé par le département de recherche opération-

nelle (DIR/GDA 2 ) et le département de maintenance des voies (CSC-EM2) de la SNCF. Il est
stratégique car il consiste à optimiser des tournées de maintenance nationale et annuelle. Il est
original car il n’existe pas, à notre connaissance, d’outil d’optimisation des tournées d’engins à
la SNCF. Sa résolution est un défit de par la taille du réseau et l’horizon annuelle de planifica-
tion. De plus, la modélisation de ce problème nécessite de déterminer l’essence du problème,
c’est-à-dire trouver quelles caractéristiques d’une solution proposée apporte une réelle aide aux
programmateurs des engins.

Le modèle choisi pour formaliser ce problème est basé sur les tournées de véhicules sur
arcs. Le programme mathématique formulé pour le décrire généralise plusieurs problèmes de
tournées sur arcs avec contraintes de capacité. Une heuristique originale de résolution par dé-
composition mathématique est proposée pour obtenir une solution optimisée du problème de
tournées d’inspections. Dans le cadre de cette heuristique alliant génération de coupes et de
colonnes, une méthode de projection de coupes est proposée pour accélérer la convergence de
la génération de contraintes. Dans le cadre d’un algorithme d’ordonnancement, une méthode
1. En 2007, il y a eu uniquement 2 déraillements de trains SNCF.
2. Direction de l’Innovation et de la Recherche/Génie Décisionnel Appliqué

11
 Chapitre 1. Introduction

originale d’exploration de l’espace réalisables est aussi proposée. Cette méthode calcule une
estimation de l’impact des décision prises durant l’exploration de l’arbre de recherche. Cet im-
pact est quantifié sous la forme d’un prix marginal qui est utilisé pour mettre à jour la fonction
objectif.

Des expérimentations numériques sont réalisées à partir d’un jeu de données réelles décrivant
les auscultations à réaliser pour l’année 2009. Plusieurs approches sont comparées numérique-
ment afin de définir la variante la plus efficace pour les données considérées. La qualité des
solutions de cette « meilleure variante » est aussi analysée.
Deux logiciels développés pendant la thèse sont présentés. Le premier est le calculateur. Il
est développé avec un soucis de généricité, afin de pouvoir l’utiliser pour plusieurs types de
problèmes de tournées. Le second est utilisé pour la manipulation des données, l’affichage des
solutions et le contrôle du calculateur. Les schémas de données utilisés par ces deux applications
sont aussi présentés.

La première partie de ce mémoire s’articule autours de la présentation du problème d’opti-

misation des tournées d’inspections. Le chapitre 1 décrit l’environnement industriel, ainsi que
la problématique à résoudre. Il présente, entre autres, les enjeux de la maintenance des voies,
la description des tournées d’inspection, ainsi que le projet « grands axes » dans lequel s’ins-
crit l’outil d’aide à la décision. Le chapitre 2 fait une revue de la littérature sur les problèmes
de tournées sur arcs et leurs applications. Il contient aussi une présentation de quelques articles
sur l’optimisation des maintenances de voies. Le chapitre 3 présente des programmes mathéma-
tiques modélisant l’optimisation des tournées d’inspections. Un programme linéaire en nombres
entiers ainsi que deux méthodes de décomposition sont présentés.
La seconde partie traite de la mise en œuvre de la méthode de résolution. Dans le chapitre
4, nous décrivons un algorithme de résolution optimal basé sur l’application d’une méthode
de décomposition de Benders. Une heuristique basée sur cette approche optimale est également
développée. Les algorithmes composants cette heuristique, ainsi que des variantes y sont décrits.
Dans le chapitre 5, les différents composants de cette heuristique sont analysés numériquement.
Plusieurs jeux de données sont générés à partir des données réelles pour tester la qualité des
solutions obtenues. Enfin, le chapitre 6 présente les deux logiciels développés pour la SNCF. Il
détaille le logiciel de manipulation des données et de pilotage du calculateur. L’architecture de
ce dernier est aussi présentée dans ce chapitre.
La troisième partie conclut ce mémoire en résumant les apports proposés par cette thèse et
en présentant quelques pistes de recherche.

12
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 Première partie

Présentation de la problématique

13
Chapitre 2

Environnement industriel et
problématique

2.1 Les maintenances industrielles

Les maintenances industrielles peuvent être classées en deux catégories : les maintenances
correctives et les maintenances préventives.

Maintenances correctives Ce sont les actions de maintenance qui interviennent après une
défaillance. Elles peuvent être palliatives (réparation provisoire ou dépannage), ou curatives
(réparation définitive).

Maintenances préventives Elles sont réalisées pour réduire les probabilités de défaillance.
Elles se divisent en trois catégories principales selon l’événement déclencheur. Lorsqu’elles
sont planifiées selon un échéancier, on parlera de maintenances préventives systématiques.
Lorsqu’elles sont déclenchées dès qu’un indicateur franchit un certain seuil, ce sont des main-
tenances préventives conditionnelles. Ces maintenances nécessitent une collecte d’informations
systématique et la définition de seuils d’intervention. Elles permettent de programmer des in-
terventions à court ou moyen terme. Enfin, lorsqu’elles sont réalisées en fonction de l’analyse
de l’évolution de paramètres significatifs de dégradation, ce sont des maintenances préventives
prévisionnelles ou prédictives. Elles sont utilisées pour planifier à long terme des actions avant
que les seuils d’intervention ne soient atteints.
Le type de maintenance sera choisi en fonction du trafic, de l’impact sur la sécurité de la voie
et du type de matériel. Par exemple, les maintenances préventives systématiques sont effectuées
pour l’entretien des abords de la voie et le rétablissement des profils de ballast en fonction des
saisons, tandis que les maintenances préventives conditionnelles (et prévisionnelles) du rails
et de la géométrie de la voie sont effectuées en fonction du tonnage cumulé supporté et des
informations récupérées par divers instruments de mesures.
Les engins lourds d’auscultation à ultrasons (ELUS) font parties du plan de maintenance
préventive systématique. Ils utilisent un système de détection par ultrasons des défauts internes
du rail. Ce système produit des données utilisées pour déclencher des maintenances préventives
et correctives. Ces informations sont aussi utilisées pour améliorer les modèles de prédictions
d’évolution des fissures internes du rail.

15
 Chapitre 2. Environnement industriel et problématique

2.2 Le système ferroviaire

2.2.1 Les acteurs
Le système ferroviaire est constitué de l’ensemble des moyens de production ferroviaire,
composés de moyens humains et matériels. Par exemple, les voies, les locomotives, les voi-
tures, mais aussi les engins de maintenances, les centres de maintenances et les quais sont des
moyens de production matériels. Les moyens de productions « humains », constitués de savoir-
faire spécifique, sont les horairistes, les régulateurs, les aiguilleurs, les juristes, etc. Ces moyens
de production sont détenus par des acteurs différents et en concurrence, classés en trois catégo-
ries selon leur rôle. Tout d’abord, les organismes de contrôle et de régulation sont responsables
de la sécurité sur le réseau : coordination des acteurs, respect de la législation, organisation
des investissements, etc. Ensuite, les gestionnaires d’infrastructure (GI) sont les entités respon-
sables de la gestion, de l’entretien et du développement du réseau. En France, Réseau Ferré de
France (RFF) est l’unique GI. C’est aussi l’entité comptable qui perçoit les redevances d’ac-
cès (péages). Enfin, les Entreprises Ferroviaires (EF) exploitent commercialement le réseau. En
France, la Société des Chemins de Fers Français est le principal EF, que ce soit en transport
de fret ou de voyageurs. D’autres EF de pays Européens exploitent aussi le réseau ferroviaire
français. Les Gérants d’Infrastructure Délégués (GID) sont d’autres acteurs importants de la
production ferroviaire. En France, la branche Infrastructure de la SNCF est un GID. Elle est
mandatée par RFF pour réaliser certaines maintenances.

2.2.2 La production ferroviaire

Un des rôles incombant à RFF est l’entretien du réseau ferroviaire. Pour réaliser cette tâche,
RFF et la SNCF sont liés par un contrat de délégation de pouvoir. RFF, en tant que maître d’ou-
vrage, définit les objectifs de maintenance et délègue à la SNCF leur réalisation. Celle-ci s’en-
gage alors sur des objectifs de volume et de qualité. En ce qui concerne les maintenances cor-
rectives ou les renouvellements, RFF traite également avec la SNCF au travers de programmes
déclinés par types dŠinstallations. Ces deux acteurs principaux du système ferroviaire français
sont donc clients et fournisseurs l’un pour l’autre : la SNCF paye des redevances à RFF et RFF
rétribue la SNCF pour la réalisation des maintenances.

La production d’un train est une tâche qui nécessite la coordination de plusieurs entités du
systèmes. En effet, pour que le train puisse rouler, il faut que soient libres :
1. un conducteur,
2. un engin moteur (automotrice, locomotive, etc.),
3. une rame (constitué de voitures),
4. un sillon (réservation de voie),
5. et un ensemble de services (gares ouvertes, aiguilleurs, régulateurs, etc.).
La difficulté est alors de coordonner les acteurs qui détiennent ces ressources. Le conducteur,
l’engin moteur et la rame sont du ressort de l’EF qui exploite le train. Par contre, le sillon est
détenu par RFF et les services nécessaires peuvent être fournis par plusieurs EF.

16
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 Chapitre 2. Environnement industriel et problématique

2.2.3 Le référentiel d’enregistrement

L’UIC (Union Internationale des Chemins de fers) est une association ayant pour but la
standardisation des termes ferroviaires. Elle a établi une classification des lignes en fonction
de la charge de trafic qu’elles supportent (tonnage cumulé et vitesse de circulation maximale).
Cette classification va de 1 à 9. Le groupe UIC 1 correspond à des lignes très chargées. Le
référentiel IN2070 (2002) spécifie, pour ces groupes, les fréquences d’inspection qui varient de
6 mois pour une ligne TGV, à 20 ans pour un rail posé neuf sur une voie peu utilisée. Lorsqu’il
est impossible de réaliser les enregistrements nécessaires, des dérogations doivent être signées
par une autorité compétente 1 . Sans ces dérogations, des limitations de vitesse ou des fermetures
de voies sont imposées. Les fréquences et les dates d’auscultation passées décrivent des fenêtres
de temps pendant lesquelles les auscultations futures doivent être réalisées.
Ces auscultations futures sont appelées « tâches d’auscultation ». Lorsqu’un engin circule
en réalisant une tâche d’auscultation, on dit qu’il se déplace « en auscultation ». Dans le cas
contraire (auscultation non obligatoire ou haut-le-pied), on dit qu’il se déplace « en achemine-
ment ».

2.3 Enjeux de l’auscultation ultrasonore par engins lourds

Les causes principales de détérioration du rail sont l’usure mécanique, l’enrayage 2 et les
chocs thermiques. Lorsque le risque de rupture est trop important, des limitations de vitesse,
des fermetures de voies ou des maintenances correctives 3 sont à prévoir. Ces dernières peuvent
se révéler particulièrement coûteuses en personnels et matériels. Elles imposent des restrictions
de circulation et sont la cause de désagréments commerciaux.
Les graphiques présentés par l’EPSF dans le rapport de sécurité EPSF (2008) et repris dans
la figure 2.1(a) montrent une augmentation du nombre de déraillements entre 2006 et 2008,
alors que le nombre de rails cassés détectés est resté stable (voir 2.1(b)). Il serait possible de
conclure que l’augmentation des déraillements est due à un autre phénomène que les rails cas-
sés. Or, dans les rapports d’audit (page 21 du rapport EPSF (2008) et le rapport de Rivier et
Putallaz (2005)), il est fait mention d’un taux de déraillement qui augmente en raison de l’état
de vétusté du réseau. Il faut ajouter à cela que la rénovation du réseau et l’accroissement du
trafic vont augmenter la quantité de rail à ausculter annuellement. Ces constatations soulignent
l’importance du suivi des défauts de rails et donc de leur auscultation.

2.4 Projet grands axes

En 2010, la SNCF utilise un découpage administratif de la France en 23 régions. Chacune de
ces régions est responsable de la maintenance d’une partie du réseau ferroviaire. Elles planifient
la majorité des auscultations ultra-sonores. L’Établisselement Logistique National (ELOGN) est
l’entité responsable de l’acheminement des engins et de la coordination des régions. Il met à
leur disposition, entre autres, les engins lourds d’inspection à ultrasons (ELUS) et organise les
acheminements nécessaires aux transferts des engins.
1. INFRA/CSC ER IM2
2. blocage des roues
3. réparation des éclisses, des tampons, régénération de ballast, etc.

17
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 Chapitre 2. Environnement industriel et problématique

(a) Nombre de déraillement par million de km.train (b) Nombre de rails cassés par million de km.train

F IGURE 2.1 – Statistique des déraillements et rails cassés entre 2006 et 2008.

Les chantiers, massifiés dans le temps et l’espace, contraignent la libre circulation des en-
gins. Pour illustrer cette difficulté, la figure 2.2 présente une carte des principaux chantiers
prévus en 2010. Force est de constater que leur nombre est important et que certains d’entre eux
sont réalisés sur plusieurs régions en même temps. La prise en compte dans le planning de ces
réductions de capacité 4 est rendue difficile par la décentralisation des prises de décision.
La majeure partie du trafic ferroviaire est réalisée sur les grandes lignes et sur le réseau à
grande vitesse. Plus de la moitié de la distance totale à ausculter se trouve sur cette partie du
réseau. Elle totalise 21 500 km d’auscultation par an, soit une moyenne de 513 km par région
SNCF. Pour réduire les acheminements non productifs, la SNCF étudie la mise en place de
la « logique grands axes » afin de tester la viabilité d’une planification nationale partielle du
réseau. Ce sous-réseau qui serait planifié par l’ELOGN est appelé « réseau grands axes ». Il
est représenté en rouge et vert dans la carte de la figure 2.3. Les portions de voies appartenant
aux grands axes sont détaillées dans l’annexe A. Cette nouvelle organisation transférera la pro-
grammation des tournées d’inspections des défauts internes du rails des régions vers l’ELOGN.

2.5 Technique
2.5.1 La détection par ultrasons
Plusieurs technologies existent pour tester les rails de façon non destructive et détecter leurs
défauts. Dans le livre de Blitz (1997) cinq techniques sont décrites et analysées : radiogra-
phiques (rayons-X, gamma, neutrons), acoustiques (ultra-sons, impédance mécanique), élec-
triques et mécaniques (courant de Eddy, fuites magnétiques, micro-ondes), visuelles et optiques
4. interdictions de circuler

18
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 Chapitre 2. Environnement industriel et problématique

F IGURE 2.2 – Principaux chantiers de l’année 2010.

F IGURE 2.3 – Carte du réseau « grands axes » .

19
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 Chapitre 2. Environnement industriel et problématique

(interférométrie, holographie) ou thermiques (infrarouge).

Parmi toutes ces technologies, la détection par ultrasons semble la plus adaptée à l’auscul-
tation interne du rail. En effet, le métal absorbant très peu les vibrations acoustiques, le signal
ultrasonore est peu atténué. De plus, la modification du positionnement des capteurs à ultrasons
permet d’obtenir des coupes de rails avec différents angles. Un autre avantage de cette tech-
nologie est sa fiabilité. La mesure continue des défauts de rails est rendu possible par la haute
fréquence d’échantillonnage des échos ultrasoniques et la finesse du modèle de propagation des
ondes dans les métaux. Le désavantage majeur est que la qualité du signal varie en fonction
de la vitesse de déplacement du mobile. Pour réduire les interférences, une pellicule d’eau est
maintenue entre le capteur et le rail. Malgré cela, au-delà de 40 km/h, le signal devient inexploi-
table 5 sur la majorité du réseau. En pratique, le bruit induit par le passage sur certains appareils
de voie, tels que les aiguillages et les appareils de dilatation, est trop important pour que ces
éléments soient surveillés par les ELUS. Ils sont contrôlés à pied d’œuvre.

2.5.2 Les engins

En 2010, l’ELOGN gère une flotte de 3 véhicules bidirectionnels dénommés V3, V5 et V6.
La V3 est une voiture de type corail et doit être tractée par une ou deux locomotives selon
les nécessités de production. La V5 et la V6 sont des autorails 6 . Le réseau ferroviaire natio-
nale n’étant pas électrifié partout, ces engins utilisent l’énergie thermique pour se déplacer. Les
capteurs ultrasons sont montés sur des chariots fixés sous la voiture et les autorails.

Équipage Les engins V3 et V6 sont équipés de couchettes, l’engin V5 possède un wagon de

cantonnement. Ils peuvent héberger une équipe de 4 agents : généralement deux opérateurs, un
conducteur et un expert de la région visitée. Les connaissances du réseau de l’expert permettent
de signaler un défaut d’auscultation suite à une erreur d’aiguillage de l’engin. Sauf dérogation,
l’unicité de cet expert empêche deux engins d’ausculter simultanément la même région. Cette
contrainte ne sera pas prise en compte dans le problème présenté car le rôle de l’expert dans le
futur n’est pas encore défini.

Circulation Chaque engin, présenté sur les photos de la figure 2.4, possède des caractéris-
tiques de vélocité et d’autonomie propres. Le tableau 2.1 détaille ces caractéristiques de circu-
lation. Pour simplifier la compréhension du problème, nous distinguons deux types de mouve-
ment : la circulation en auscultation (AUS) et l’acheminement haut-le-pied (HLP). Pour faciliter
leurs mouvements, ils sont équipés de deux postes de commandes totalement identiques. Tous
les ELUS (Engins Lourds Ultra-Sons) sont bidirectionnels : ils peuvent circuler dans les deux
sens. Ils possèdent chacun une réserve d’eau utilisée pour maintenir couplés les capteurs et
le rail. Ce couplage hydraulique réduit le bruit du signal, mais limite la durée d’auscultation
journalière. Durant les circulations AUS, la vitesse réduite du mobile complique son insertion
dans le trafic (sillon dense, véhicule non prioritaire, vitesse lente, etc.) De plus, l’abaissement

5. Pour les défauts superficiels, des vitesses d’auscultations records ont été atteintes en laboratoire par Papaelias
et al. (2009). Ils ont présenté un protocole pour détecter à 120 km/h des défauts superficiels du rail. Dans le cas
des engins lourds (ELUS), les défauts repérés se situent à une distance de plus de 5 mm de la surface supérieure
du rail.
6. Voiture comportant un système de traction propre.

20
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 Chapitre 2. Environnement industriel et problématique

F IGURE 2.4 – Photo des 3 engins d’auscultation.

V3 V5 V6 moy
Vitesse maximale en haut-le-pied (km/h) 140 80 120
Vitesse maximale en auscultation (km/h) 50 50 50 7
Vitesse moyenne en haut-le-pied (km/h) 140 80 120 110
Vitesse moyenne en auscultation (km/h) 10,38 13,15 13,51 12
Autonomie d’auscultation (km) 150 150 200

Ces données sont issues du catalogue 2010 des engins de l’InfraLog, InfraLog (2010).

TABLE 2.1 – Caractéristiques des engins spéciaux, 2010

du chariot de capteurs restreint la capacité de courbure de l’engin et empêche l’auscultation de

certaines courbes.

Maintenance Les composants mécaniques et électriques des engins V3, V5 et V6 doivent

être vérifiés régulièrement. Une maintenance d’une demi-journée est réalisée sur chaque engin
environ 2 fois par mois. Cette « petite maintenance » permet de vérifier le bon fonctionnement
des organes principaux. Une fois par an, pendant la période estivale, l’engin est immobilisé
plusieurs semaines. Lors de cette « grande visite générale », la chaîne de mesure est recalibrée
et l’état de tous les composants est vérifié. À cela s’ajoutent des maintenances correctives qui
surviennent de manière aléatoire après des pannes matériel. La V6 a un plan de maintenance qui
impose une immobilisation d’au moins une journée tous les 37,5 jours. Cette contrainte n’est
pas prise en compte dans le modèle présenté.

2.6 Étapes de la programmation

Après avoir présenté le contexte et la technique, nous allons maintenant décrire l’organisa-
tion de la surveillance des défauts. La chaîne de suivi des anomalies internes du rail est compo-
sée de quatre blocs fonctionnels principaux : la conception des programmes d’auscultation, leur
adaptation, leur réalisation opérationnelle et la confirmation des mesures réalisées. Les trois
premiers blocs sont détaillés dans les sections suivantes et correspondent respectivement à des
horizons de planification de l’ordre de l’année, du mois et de la semaine. La confirmation des
défauts n’est pas décrite car elle n’influence pas les tournées des engins.

21
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 Chapitre 2. Environnement industriel et problématique

A A+1 A+2 A+3

Demande région A+1

Prog
Maintenances engins A+3 v1
Conception
Chantiers Prog
Dates auscultations A-1
A+2 v1
Prog Prog
A+0 v2 A+1 v1

Confirmation Adaptation

Prog
A+1 v2

Réalisation

Confirmation

F IGURE 2.5 – Les étapes de la programmation des ELUS

2.6.1 La conception des programmes d’auscultation

Les programmes (ou plannings) de l’année ’A’ sont finalisés au plus tard en novembre de
l’année ’A-1’. Ensuite, durant l’année ’A’, le concepteur finalise les programmes d’auscultation
qui seront réalisés l’année ’A+1’. En parallèle, il ébauche les plannings des années ’A+2’ et
’A+3’. Sa première tâche consiste à relever les dernières dates d’auscultation des portions de
voies dont il doit programmer l’auscultation. Ainsi, à l’aide du groupe UIC de chaque tron-
çon, du référentiel IN2600 (2002) et de la procédure IN2070 (2002), il peut définir les dates
d’auscultation futures.
Les grands axes (ou réseau « principal ») correspondent aux portions de groupe UIC 1 à 4.
Le reste du réseau (réseau « secondaire ») contient les portions de voie qui ont un groupe UIC
supérieur à 5. Il en résulte que tous les tronçons du « réseau grand axe » ont une fréquence
d’auscultation semestrielle ou annuelle. À la fin de cette étape de conception, le planificateur
connaît pour chaque tronçon les dates d’auscultation prévues et l’engin à utiliser. Il lui reste
à commander les sillons 8 pour autoriser et sécuriser la circulation du train. Le planning est
alors envoyé au planificateur des ressources humaines qui affecte une équipe à chaque jour de
circulation de chaque engin.

2.6.2 L’adaptation des programmes d’auscultation

Dès que le programme est conçu, il est continuellement modifié. Les aléas d’exploitation
(rupture matériel, situation perturbée, personnel) sont pris en compte au fil de l’eau. Il faut
alors, entre autres, commander de nouveaux sillons, réaffecter le personnel et vérifier les be-
soins en garages et manœuvres. Toutes ces modifications doivent se faire en s’assurant que les
dates d’auscultation au plus tard sont respectées. En pratique, moins de la moitié des journées
programmées est réalisée à la date prévue. Le travail d’adaptation est donc une étape primor-
diale pour pouvoir réaliser le programme produit en conception.
8. Un sillon horaire est une période durant laquelle une infrastructure donnée est affectée à la circulation d’un
train entre deux points du réseau ferré

22
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 Chapitre 2. Environnement industriel et problématique

2.6.3 La réalisation des programmes d’auscultation

Les campagnes d’auscultation sont découpées en journée de service (JS). Chaque JS corres-
pond à un temps de travail effectif d’environ 8h et une amplitude maximale de 11h. Ainsi, si
les équipes travaillent en 2 ou 3*8, la journée calendaire est décomposée en autant de JS qu’il y
a d’équipes. Une JS commence par la prise en charge du véhicule par l’équipe. Celle-ci vérifie
que l’engin est en état de fonctionner, que les réservoirs d’eau sont remplis et que les capteurs
sont opérationnels. Cette première étape dure environ une heure. Après ces vérifications, l’engin
réalise des auscultations ou des acheminements haut-le-pied. Lorsqu’un défaut est détecté, un
jet de peinture est projeté pour signaler sa position. Des équipes seront envoyées sur le terrain
pour confirmer, à l’aide d’outils plus précis (bifill, échographie, etc.), l’importance du défaut.
Enfin, la JS se termine dans une gare où il est possible de remplir les réservoirs d’eau. Les
données collectées sont alors transférées à l’autorité compétente pour analyse. Elles seront uti-
lisées pour le suivi historique des défauts. Elles serviront aussi à définir des lois de probabilité
pour prédire l’évolution des différents types de défauts. Si la gare est équipée pour accueillir
l’engin de mesure (fosse, électricité, eau courante, etc.), l’équipe dormira à son bord. Sinon, un
hébergement en hôtellerie est prévu. Tout comme la prise en charge de l’engin, sa restitution
dure environ une heure. Il y a donc, en moyenne, un maximum de 6 heures de circulation par
JS. En fonction des opérations annexes nécessaires en fin et début de service, le maximum de
circulation est de 6h31 pour la V3, 5h25 pour la V5 et 5h57 pour la V6.

2.6.4 Performance
Les tableaux de bord 2008 9 et 2009 10 (repris dans les tables 2.2 et 2.3 sous une forme
synthétique) présentent des indicateurs sur les distances totales parcourues en auscultation et en
haut-le-pied. Les informations ont été agrégées sous la forme d’indices de performance.
Les indicateurs annuels sont :
– la Distance totale d’Acheminement (DA), c’est la distance totale des circulations HLP,
– la Distance totale Utile (DU), c’est la distance totale des circulations AUS,
– le Temps d’Acheminement (TA = DA/ Vitesse max d’acheminement / durée journée de
service) et
– le Temps Utile (TU = DU/ / Vitesse max d’auscultation / durée journée de service).
À partir de ces informations agrégées, nous définissons l’indice de performance kilomé-
trique R[km] comme le quotient de la distance d’auscultation réalisée (DU) par la quantité totale
de kilomètres parcourus dans l’année (DU + DA). L’indice R[ j] de performance temporelle est
calculé de la même façon avec les données temporelles.

R[km] = DU/(DU + DA) ; R[ j] = TU/(TU + TA).

Les données recueillies pour les années 2008 et 2009 montrent que l’indice de performance
kilométrique R[km] est inférieur à 45% pour les deux années considérées. Plus de la moitié de la
distance totale parcourue par les engins est donc improductive. Un des leviers d’amélioration
est donc la réduction de ces trajets. C’est dans cette direction que s’inscrivent nos travaux.
Une vision globale des liens entre les tâches d’auscultation et les chantiers est obtenue
par projection des données temporelles et spatiales dans un espace à trois dimensions. Cette
9. Réf. : 364-08-ELOGNAT-OTP-TB-CD
10. Réf. : 573-09-ELOGNAT-OTP-TB-CD

23
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 Chapitre 2. Environnement industriel et problématique

F IGURE 2.6 – Représentation spatiale des tâches

représentation est montrée dans les figures 2.6 et 2.7.

Pour comprendre d’où provient cette perte d’efficacité, nous analysons les fenêtres de temps
des tâches d’auscultation et des chantiers. Pour ce faire, nous proposons, dans la figure 2.7, trois
représentations graphiques de la distribution des tâches dans le temps et dans l’espace. L’axe des
abscisses et des ordonnées forment le plan géographique, tandis que la profondeur de l’image
est utilisée pour décrire l’aspect temporelle des tâches et des chantiers. La carte de la figure 2.6,
présente la dispersion des tâches sur le réseau ferroviaire national. Elle montre que les tâches
sont adjacentes dans l’espace. Il paraît donc possible de les réaliser avec très peu de circulations
non productives. Dans la carte de la figure 2.7(a), il est possible d’observer l’étalement dans
le temps des tâches. On constate alors que certaines portions de lignes ne peuvent pas être
auscultées de façon continue 11 . Les choses se compliquent lorsque l’on ajoute les chantiers (en
rouge sur la représentation de la figure 2.7(b)). Il est alors possible de détecter visuellement un
certain nombre de tâches d’auscultation non réalisables, et de voir les difficultés à passer « entre
les chantiers ». Elles permettent aussi d’identifier les quelques tâches isolées qui risquent d’être
difficiles à insérer dans la tournée annuelle.

11. Voir par exemple autours de Paris.

25
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 Chapitre 2. Environnement industriel et problématique

(a) Représentation spatiale et temporelle des tâches(b) Représentation spatiale et temporelle des tâches
(vert) (jaune) et chantiers (rouge)

F IGURE 2.7 – Cartographie des dates de réalisation possibles des tâches d’auscultation, 2009.

2.7 Propositions
Dans cette section, nous proposons des leviers d’actions pour améliorer le travail des concep-
teurs à l’aide d’outils d’optimisation. Nous avons repris le découpage en blocs fonctionnels pour
présenter des innovations en phase de conception, d’adaptation et de réalisation. Ces proposi-
tions sont autant de pistes de recherche futures pour la SNCF.

2.7.1 Conception
Optimisation tâches/jours L’histogramme de la charge de travail mensuelle en 2009, pré-
senté dans la figure 2.8, montre le déséquilibre important entre les mois. Certains mois comme
janvier ou septembre sont très chargés tandis que d’autres comme juin ou juillet le sont beau-
coup moins. Cette hétérogénéité pose des problèmes d’organisation et de fiabilité. Il est difficile
de prévoir les équipes nécessaires pour assurer les mois surchargés. De plus, l’apparition d’un
aléa pendant un mois très chargé va provoquer une réaction en chaîne préjudiciable. Cet évé-
nement peut alors nécessiter une reprogrammation complète du mois (phase d’adaptation du
programme).
Cette situation complique la tâche du concepteur. Une des possibilités dont il dispose pour
lisser la charge de travail est d’avancer les dates d’auscultation prévues (sur-qualité) ou de
les repousser (sous-qualité). La sur-qualité est préférée pour des raisons de sécurité. De plus,
en cas de sous-auscultation, il faut obtenir une dérogation. La mise à disposition d’un outil
logiciel pour équilibrer la charge en optimisant les dates prévisionnelles standardiserait cette
pratique. Ce moteur de calcul prendrait en compte les affinités spatiales et temporelles des
tâches pour réduire le nombre de circulations HLP. Il pourrait être perfectionné en y intégrant
les informations de disponibilité des engins et des agents.

26
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 Chapitre 2. Environnement industriel et problématique

F IGURE 2.8 – Histogramme de la charge de travail mensuel, 2009.

Optimisation engins/tâches/jours Nous avons montré que la programmation est réalisée sur
un horizon temporel d’une année et que le réseau à ausculter est de taille conséquente. Avec un
tel volume de données, il semble inimaginable qu’un concepteur, qui produit les programmes de
plusieurs engins, puisse planifier les auscultations en s’assurant que les cycles sont satisfaits tout
en minimisant les circulations HLP. Une prise de décision automatisée de l’affectation d’une
date et d’un engin à chaque tâche serait un avantage certain dans le processus de planification.

Optimisation équipes/engins/jours Une autre difficulté, aujourd’hui gérée par le planifica-

teur des ressources humaines, est l’affectation des équipes aux trains. Cette tâche est réalisée
par l’opérateur humain qui affecte les équipes en s’assurant que les exigences du référentiel des
ressources humaines (notamment RH0077 (2005)) sont satisfaites. Par contre, l’optimisation du
planning en prenant en compte la pénibilité des tâches, l’éloignement du domicile, l’empreinte
carbone due aux déplacements, etc. est une tâche complexe. Un outil de planification automa-
tique serait un atout précieux pour améliorer la gestion des équipes. Il pourrait aussi être capable
de planifier les affectations d’équipes ayant plusieurs compétences.

2.7.2 Adaptation
À une échelle temporelle plus petite, le préopérationnel est résolument tourné vers l’adapta-
tion du programme aux nouvelles conditions opérationnelles. Durant cette phase critique, entre
conception et réalisation, l’adaptateur intègre dans le programme courant les tâches d’ausculta-
tion qui n’ont pas pu être réalisées. Il y ajoute les nouvelles demandes de mises à disposition,
les aléas matériels et les changements de personnels. Il y intègre aussi les modifications des
besoins en garages et manœuvres, s’assure de la possibilité de reprendre le planning original
en quelques jours, etc. Cette réorganisation est faite en utilisant l’expérience du concepteur.
Malheureusement, durant les périodes denses, le temps manque pour prendre en compte tous
ces aléas. Afin de parer au plus pressé, il est souvent nécessaire d’ajouter des circulations non
productives qui auraient pu être évitées avec une vision plus globale.
Afin de pallier ces désagréments, plusieurs outils d’optimisation sont possibles. Pour les
décrire, nous distinguons deux catégories principales complémentaires. Les optimisations pro-
actives et les optimisations réactives. Les optimisations pro-actives assurent que le planning
optimisé est facilement adaptable à des changements de conditions opérationnelles. Ce sont des
méthodes qui s’appliquent en amont de l’apparition d’un aléa. Les optimisations réactives sont

27
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 Chapitre 2. Environnement industriel et problématique

des méthodes qui s’appliquent après son apparition, ce sont donc des algorithmes de réparation
de solution.
En optimisation pro-active, nous suggérons l’utilisation d’un outil capable de générer des
programmes d’auscultation robustes. Ces programmes doivent être assez facilement modifiables
pour permettre d’absorber chaque mois plusieurs jours consécutifs d’indisponibilité d’un engin :
si un aléa bloque un engin pendant deux jours, des modifications mineures doivent permettre
de récupérer le planning original. Les casses étant plus fréquentes pendant les saisons froides et
chaudes, cette nouvelle approche devra être capable d’intégrer la saisonnalité des événements.
En optimisation réactive, il serait intéressant d’étudier la faisabilité d’un outil capable de
réoptimiser le programme d’auscultation. Cet outil devra fournir rapidement un nouveau pro-
gramme en cas de situation perturbée. Celui-ci devra être le plus proche possible du programme
initial afin de limiter les modifications d’hébergement, stationnement en gare, sillons, etc. Ces
deux propositions sont complémentaires car un outil d’optimisation réactif permet de réparer
des solutions optimisées pro-activement.
Ces approches n’ont pas été étudiées dans le cadre de cette thèse de doctorat.

2.7.3 Réalisation
En ce qui concerne la réalisation du programme, nous n’avons détecté aucune piste d’opti-
misation à l’aide d’un outil automatisé d’aide à la décision.

2.8 Motivation et enjeux

Motivation La décision de travailler sur l’optimisation de la conception des programmes des
ELUS est motivée par plusieurs constats. Ces trains spéciaux sont considérés comme difficiles
à programmer à cause de l’autonomie limitée, des points de garage disponibles, de leur vitesse,
etc. La réussite du déploiement d’un outil d’optimisation des tournées des ELUS offrira la pos-
sibilité d’optimiser les tournées d’autres engins. Cette réussite se concrétisera par une réduction
notable des trajets non productifs et une meilleure prise en compte des chantiers sur voie. La
modélisation de l’étape de conception est un prérequis essentiel pour comprendre comment
sont réalisées les tournées de maintenance et pour comprendre les modèles d’infrastructure fer-
roviaire. Ce travail préalable facilitera la création d’un modèle plus fin de la programmation des
auscultations (adaptation ou réalisation). Du point de vue managérial, un outil d’optimisation
facilitera la centralisation de prises de décisions auparavant distribuées et réduira les coûts d’ex-
ploitation. De plus, la génération automatique des programmes facilitera le travail du concepteur
en lui fournissant une trame de circulation qu’il devra habiller avec des sillons et des équipes.
D’un point de vue tactique, il sera aussi possible de dimensionner au mieux les parcs d’engins
de maintenances. Dans le contexte actuel de fluctuation du trafic ferroviaire et d’usure du ré-
seau, cette information est capitale. Elle pourra être utilisée pour tester de nouvelles politiques
de maintenances (fréquences, régionalisation, achat de ressources, tarification, etc.).

Enjeux Cette démarche est une démarche scientifique, avec ses risques propres. Bien que
les récents progrès en recherche opérationnelle aient prouvé la possibilité de résoudre des pro-
blèmes de plus en plus complexes, la sélection et la généralisation de ces résultats à des pro-
blématiques industrielles reste du domaine de la recherche. Il en est de même pour leur mo-
délisation : il n’est pas toujours possible de modéliser les pratiques et attentes des opérateurs

28
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 Chapitre 2. Environnement industriel et problématique

du système. Plusieurs objectifs antagonistes peuvent coexister, les contraintes du système sont
nombreuses et la souplesse avec laquelle elles doivent être satisfaites n’est pas connue a priori.
Les contraintes à sélectionner doivent donner une réelle valeur ajoutée à la prise de décision
automatisée. Leur nombre et leur complexité sont des caractéristiques à surveiller puisqu’elles
définiront le volume de données à gérer.

29
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 Chapitre 2. Environnement industriel et problématique

30
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
Chapitre 3

Revue de littérature

La section 1 présente les définitions de quelques termes utilisés dans la théorie des graphes.
La revue de littérature que nous présentons dans ce chapitre est organisée autours de trois
thèmes. Le premier thème, présenté dans la section 2, concerne les problèmes de tournées
sur arcs. Nous présentons quelques problèmes fondamentaux ainsi que certains résultats théo-
riques importants. Cette introduction aux tournées sur arcs facilitera la compréhension de la
modélisation mathématique que nous proposons dans le chapitre 4 pour résoudre le problème
d’inspection des voies. Le second thème, présenté dans la section 3, est relatif aux applications
pratiques des problèmes de tournées sur arcs. Le troisième thème, présenté dans la section 4,
expose quelques problèmes d’optimisation lié à la maintenance des voies ferrées.

3.1 Théorie des graphes

Graphe orienté Un graphe orienté G = (V, A) est composé d’un ensemble de nœuds V et
d’un ensemble d’arcs A dont les éléments sont des couples ordonnés de nœuds distincts.

Graphe non orienté Un graphe non orienté G = (V, E) est défini de la même façon qu’un
graphe orienté, à l’exception des arcs qui sont des couples non ordonnés de nœuds distincts
appelés arêtes (E).

Multigraphe Un multigraphe est un graphe possédant des arcs parallèles.

Sous graphe Un graphe G0 = (V 0 , A0 ) est un sous-graphe de G = (V, A) si V 0 ⊆ V et A0 ⊆ A.

Chaîne Une chaîne dans un graphe G = (V, E) est un sous-graphe de G composé d’une sé-
quence ordonnée de nœuds et d’arêtes. La chaîne est un concept non orienté.

Chemin Un chemin dans un graphe G = (V, A) est un sous-graphe de G composé d’une sé-
quence ordonnée de nœuds et d’arcs. Le chemin est un concept orienté.

Chemin (chaîne) élémentaire Un chemin (chaîne) élémentaire est un chemin (chaîne) sans
répétition de nœuds.

31
 Chapitre 3. Revue de littérature

Chemin (chaîne) simple Un chemin (chaîne) simple est un chemin (chaîne) sans répétition
d’arcs.

Cycle Un cycle est une chaîne dont les sommets de départ et de fin sont les mêmes.

Circuit Un circuit est un chemin dont les sommets de départ et de fin sont les mêmes.

3.2 Tournées sur arcs

3.2.1 Problèmes principaux
Les premiers travaux d’analyse mathématique des problèmes de tournées sur arcs sont attri-
bués à Euler (1736) qui résolut le problème des ponts de Königsberg. Ce premier problème de
décision se formalise de la façon suivante :
Problème 1 Le problème de Königsberg
Étant donné la ville de Königsberg et ses ponts, est-il possible de faire une promenade, partant
et arrivant au même endroit, tout en passant par chacun des ponts exactement une fois ?
Euler proposa une abstraction mathématique du problème, nommé problème du cycle eulérien.
Ce fut les prémices de la théorie des graphes. Il reformula le problème de la façon suivante :
Problème 2 Le problème du cycle eulérien
Étant donné un graphe non orienté G = (V, E), trouver un cycle contenant toutes les arêtes de
E exactement une fois ou déterminer qu’un tel cycle n’existe pas.
Il prouva qu’une solution existe si et seulement si tous les nœuds de G sont de degré pair, mais
ne proposa pas de procédure pour en déterminer un. Deux siècles plus tard, Mei-Ko (1962)
proposa une extension de ce problème de décision sous la forme d’un problème d’optimisation
qui sera nommé problème du postier chinois en son honneur. Ce problème consiste à trouver
un cycle contenant toutes les arêtes au moins une fois et dont la longueur totale est minimale. Il
peut être formulé de la façon suivante :
Problème 3 Le problème du postier chinois - CPP 1
Étant donné un graphe non orienté G = (V, E,C), avec C une matrice de coût sur les arêtes,
trouver un cycle qui passe par chaque arête au moins une fois et dont la distance totale est
minimale.
Edmonds et Johnson (1973) et Christofides (1973) ont montré qu’une solution à ce problème
pouvait être obtenue en temps polynomial lorsque le graphe est complètement orienté ou com-
plètement non orienté. Papadimitriou (1976) a montré que lorsque le graphe est composé d’arcs
et d’arêtes, le problème est N P -difficile. Une présentation d’articles sur ce sujet a été écrite par
Eiselt et al. (1995a). Cette revue contient un résumé des principales propriétés de ce problème.
Orloff (1974) proposa une extension de ce problème d’optimisation dans lequel le postier doit
visiter un sous ensemble des arêtes. Il fut nommé problème du postier rural en analogie avec les
longues distances que doit parcourir un tel postier entre les hameaux servis. Il peut se formaliser
de la façon suivante :
1. Chinese Postman Problem

32
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 Chapitre 3. Revue de littérature

Problème 4 Le problème du postier rural - RPP 2

Étant donné un graphe non orienté G = (V, E,C), avec C une matrice de coût sur les arêtes,
trouver un cycle de coût total minimal qui passe par toutes les arêtes R ⊆ E au moins une fois.

Lenstra et Kan (1976) ont prouvé que ce problème est N P -difficile. Eiselt et al. (1995b) ont
récapitulé quelques résultats importants sur ce sujet. Orloff (1974) proposa une généralisation
des problèmes de tournées sur arcs et nœuds, qu’il nomma problème de tournée général. Il peut
se formuler de la façon suivante :

Problème 5 Le problème de tournée général - GRP 3

Étant donné un graphe non orienté G = (V, E,C), avec C une matrice de coût sur les arêtes,
trouver un cycle de coût total minimal qui passe par toutes les arêtes RE ⊆ E et tous les nœuds
RV ⊆ V au moins une fois.

La dernière grande famille de problèmes de tournées sur arcs que nous présentons a été proposée
par Golden et Wong (1981) sous le nom de problème de tournées sur arcs avec contrainte de
capacité. Ce problème consiste à trouver un ensemble de tournées permettant de visiter certains
arcs tout en prenant en compte le fait que l’autonomie d’un véhicule diminue à chaque arc
traversé. Par réduction du problème de partitionnement, ils montrèrent qu’il est N P -difficile. Il
peut se formuler de la façon suivante :

Problème 6 Le problème de tournées sur arcs avec contrainte de capacité - CARP 4

Étant donné un graphe non orienté G = (V, E,C, Q), avec C une matrice de coût sur les arcs et
Q une matrice de demande sur les arêtes, et étant donné un ensemble de véhicules identiques de
capacité W , trouver des cycles qui 1) permettent de visiter toutes les arêtes ayant une demande
positive une seule fois, 2) dont la somme des demandes de chaque arête servie ne dépasse pas
W pour chaque véhicule et 3) dont le coût total est minimal.

Plusieurs formulations mathématiques de ce problème ont été répertoriées dans le livre coor-
donné par Dror (2000).

3.2.2 Variantes
Dans la version originale du CPP, le coût imputé lors de la traversée d’une arête est identique
quel que soit son sens de parcours. Dans de nombreuses applications, cette hypothèse n’est pas
satisfaite. Les tournées de véhicules dans des zones à fort dénivelé en sont un bon exemple.
Pour modéliser cette caractéristique, Minieka (1979) proposa le problème du postier chinois
venteux (WCPP), dans lequel le coût dépend du sens de parcours de l’arête. Brucker (1981) et
Guan (1984) ont montré que ce problème est N P -difficile. Win (1989) a montré que lorsque le
graphe était eulérien, il était possible de résoudre le problème en temps polynomial.
Dror et al. (1987) proposèrent le problème de postier hiérarchique (HPP) dans lequel des
classes de priorité sont utilisées pour définir des relations d’antériorité entre les arêtes. Chaque
arête requise appartient à une classe de priorité. Une relation d’ordre est définie entre ces classes.
Le problème consiste à déterminer un cycle qui passe par toutes les arêtes requises une fois,
2. Rural Postman Problem
3. General Routing Problem
4. Capacitated Arc Routing Problem

33
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 Chapitre 3. Revue de littérature

tout en s’assurant que la relation d’ordre est satisfaite. Ils ont montré que le problème est N P -
difficile dans le cas général et polynomial lorsque la relation d’antériorité est linéaire sur les
classes et que chaque sous-graphe de classe est connexe.
Le problème de postier rural avec profits décrit par Aráoz et al. (2006) modélise une problé-
matique moderne de livraison de courrier dans laquelle le postier collecte un gain la première
fois qu’il visite un arc requis, mais paye à chaque fois qu’il traverse cet arc. Ils montrent que ce
problème est N P -difficile. Corberán et al. (2002b) ont proposé une formalisation du problème
du postier rural avec pénalité de virage. Leur papier contient la description d’une procédure de
reformulation vers un problème de voyageur de commerce asymétrique.
Le CARP périodique (PCARP) consiste à affecter un ensemble de jours de service à chaque
arc requis et ensuite résoudre le CARP correspondant pour chaque journée de service. La fonc-
tion objectif est souvent la minimisation du nombre de véhicules ou la distance totale parcourue.
Lacomme et al. (2005) ont décrit le PCARP de façon formelle en s’appuyant sur une application
pratique de collecte de déchets. Les déchets s’accumulant au cours de la semaine, le problème
présenté prend en compte une demande cumulative sur les jours. Chu et al. (2005) ont proposé
une formulation mathématique en nombres entiers de ce problème, ainsi que des heuristiques
de résolution.
Une extension naturelle de ce problème, sans cumul des demandes, consiste à contraindre
la visite des arcs requis à être réalisée pendant certaines périodes. C’est le problème de tournées
sur arcs avec fenêtres de temps (CARP-TW). Lorsque les fenêtres de temps sont souples, une
pénalité est imputée lorsque l’arc est visité en dehors de la fenêtre de temps. Ce problème est
appelé problème de tournées sur arcs avec fenêtres de temps souples (CARP-sTW). Tagmouti
et al. (2007) ont décrit formellement ce problème et ont proposé un algorithme de résolution
par génération de colonnes pour le résoudre. D’autres extensions du CARP sont étudiées dans
la thèse de doctorat de Ramdane-Cherif (2002). Il y est fait mention, notamment, de problèmes
pénalisant certains virages, avec des lieux de vidages différents des dépôts, ou avec des coûts
variants en fonction du temps.
Dans ces problèmes, il n’y a qu’un seul dépôt d’où partent et arrivent tous les véhicules.
Lorsque le problème de tournées est défini avec plusieurs dépôts, on parle de problème de
tournées sur arcs avec dépôts multiples (MCARP). Ce problème a été traité par Amberg et al.
(2000) qui l’ont reformulé comme un problème d’arbre de recouvrement avec capacité.
Une autre variante du CARP est le problème de tournées sur arcs avec capacité et entre-
pôts intermédiaires. Dans ce problème, les véhicules peuvent être déchargés ou rechargés dans
certains entrepôts pendant la tournée. Ghiani et al. (2001) ont décrit ce problème et proposé des
méthodes de calcul de bornes inférieures et supérieures. Un problème similaire, dans lequel les
véhicules sont ravitaillés par d’autres véhicules, a été proposé par Amaya et al. (2007) sous le
nom de problème de tournées sur arcs avec contrainte de capacité et rechargement.

Les formulations présentées dans ces papiers considèrent toujours la flotte de véhicules
comme étant homogène. À notre connaissance, le problème de tournée sur arcs avec fenêtres
de temps, contrainte de capacité, entrepôt intermédiaire et flotte hétérogène n’a pas encore été
traité.

34
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 Chapitre 3. Revue de littérature

3.2.3 Algorithmes de résolution

Reformulation Une reformulation d’un problème de postier chinois avec des contraintes
d’antériorité en problème de postier rural a été présenté par Cabral et al. (2004). Ils décrivent un
algorithme d’exploration arborescente et de génération de coupes ainsi que deux heuristiques
de résolution. Corberán et al. (2002b) utilisent aussi une transformation vers un problème de
tournées sur nœuds pour résoudre un problème de postier rural avec pénalité de virage sur un
graphe mixte. Leur approche est basée sur une reformulation du problème vers une instance de
problème de voyageur de commerce asymétrique (ATSP). Une méthode de résolution pour le
ATSP, comme par exemple l’algorithme de branchement et évaluation proposé par Carpaneto
et al. (1995), peut alors être utilisé pour obtenir une solution optimale.
Pearn et al. (1987) ont proposé une méthode pour transformer un CARP en problème de
tournées de véhicule avec capacité (CVRP). Pour une instance de CARP ayant r arcs requis,
la méthode engendre une instance de CVRP ayant 3r + 1 nœuds à servir. Cette méthode fut
améliorée par Longo et al. (2006) qui réduisirent le nombre de nœuds de l’instance CVRP à
2r + 1. L’instance de CVRP peut ensuite être résolu à l’aide d’heuristiques ou de méthodes
exactes. Laporte et Semet (2001) ainsi que Toth et Vigo (2001) ont écrit deux introductions aux
méthodes de résolution du CVRP. Dans sa thèse de doctorat, Mullaseri (1997) proposa aussi
de traiter des problèmes de tournées sur arcs à l’aide d’une reformulation vers des problèmes
de tournées sur nœuds. Amberg et al. (2000) ont présenté une heuristique de résolution pour
le MCARP. Ils proposent d’utiliser une transformation vers une instance de problème d’arbre
de recouvrement avec contrainte de capacité. Le problème de recouvrement est résolu avec un
algorithme de recherche tabou.
Le problème de tournée général est une généralisation de problèmes de tournée sur arcs et
sur nœuds. Ghiani et Improta (2000b) ont proposé une procédure pour reformuler le GRP en
CARP.

L’inconvénient majeur des approches de reformulation en problème de tournées sur nœuds

est l’accroissement de la taille des instances du problème. Par contre, elles sont intéressantes
lorsque l’on dispose déjà de procédures efficaces pour des problèmes du type de la reformula-
tion.

Heuristiques Edmonds et Johnson (1973) ont proposé une heuristique de résolution pour
le CPP sur un graphe mixte. Frederickson (1979) a montré que cet algorithme produisait une
solution dont la valeur est, dans le pire cas, le double de la valeur optimale. L’heuristique se base
sur deux propriétés du CPP : 1) le CPP sur un graphe non orienté peut se résoudre en temps
polynomial si le degré des nœuds est pair, 2) le CPP sur un graphe orienté peut se résoudre en
temps polynomial si à chaque nœud il y a autant d’arcs sortants que d’arcs entrants. La première
étape de leur procédure consiste à modifier le graphe pour que le degré de chaque nœud soit pair,
en traitant chaque arc comme une arête. La deuxième étape consiste à ajouter des arcs pour qu’il
y ait autant d’arcs entrants que d’arcs sortants à chaque nœud. La détermination d’une solution
est obtenue en cherchant une circulation dans le graphe ainsi augmenté.
Pour le HPP, Dror et al. (1987) ont décrit une procédure ayant une complexité algorithmique
en O (kn5 ) pour le cas polynomial, avec n le nombre de nœuds et k le nombre de classes. Ghiani
et Improta (2000a) ont proposé un algorithme ayant une complexité algorithmique en O (k3 n3 ).
Cette procédure est donc plus intéressante lorsque le nombre de classes est faible. Plus récem-

35
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 Chapitre 3. Revue de littérature

ment, Korteweg et Volgenant (2006) ont amélioré la procédure décrite par Dror et al. (1987)
pour obtenir une complexité algorithmique en O (kn4 ).
Deux heuristiques constructives, basées sur la méthode de Win (1989), ont été proposées
par Benavent et al. (2005) pour résoudre le problème du postier rural venteux.
En ce qui concerne le CARP, trois heuristiques simples ont prouvé leur efficacité. The
construct-strike algorithm a été initialement proposé par Christofides (1973) puis amélioré par
Pearn (1989). Cette procédure consiste à rechercher des cycles réalisables puis à retirer les arcs
correspondants du graphe, tout en s’assurant que le graphe reste connexe. The Path Scanning
Algorithm proposé par Golden et al. (1983) consiste à construire les tournées de façon glou-
tonnes, arcs par arcs. Plusieurs critères de sélection d’arcs sont utilisés et la meilleure tournée
est sélectionnée à chaque étape. The Augment Merge Algorithm a aussi été proposé par Golden
et al. (1983). Il est inspiré de la méthode de Clarke et Wright (1964) pour les problèmes de
tournées sur nœuds. La première étape consiste à affecter chaque arc à une tournée différente.
Les tournées sont ensuite fusionnées entre elles lorsque la tournée fusionnée est réalisable.
Corberán et al. (2000) ont proposé une heuristique pour résoudre le problème de postier rural
sur un graphe mixte. Elle est basée sur la résolution d’un problème de flot puis un problème
de couplage. Benavent et al. (2005) ont proposé des heuristiques pour résoudre WRPP. Ils
l’utilisent pour résoudre un problème dont les instances ont plusieurs milliers d’arêtes.

Métaheuristiques Corberán et al. (2002a) ont présenté l’application d’un GRASP pour la
résolution du CPP sur un graphe mixte.
Lorsque la taille des instances CARP dépasse la centaine d’arcs, les métaheuristiques sont
des méthodes efficaces. La recherche tabou et les algorithmes mémétiques sont les deux prin-
cipales métaheuristiques ayant prouvé leur efficacité sur ces problèmes. La recherche tabou
fut expérimentée par Brandão et Eglese (2008) pour résoudre le CARP. Des algorithmes mé-
métiques ont été proposés par Lacomme et al. (2004) pour résoudre ce problème dans le cas
orienté, non orienté et mixte. Beullens et al. (2003) ont proposé de résoudre le CARP par re-
cherche locale. Ramdane Cherif (2006) a présenté l’utilisation d’un algorithme évolutionnaire
pour résoudre le CARP-TW.

Recherche de bornes Belenguer et al. (2006) ont proposé de résoudre le CARP par program-
mation linéaire et génération de coupes. Ils décrivent une procédure de calcul de bornes infé-
rieures ainsi que plusieurs heuristiques constructives. Dans leur article, Benavent et al. (2007)
ont proposé un algorithme de génération de plan sécant pour résoudre une formulation linéaire
de WRPP. Dans sa thèse de doctorat, Wohlk (2005) présente plusieurs bornes pour le CARP.

Dantzig-Wolfe Tagmouti et al. (2007) ont formulé un problème de tournées sur arcs avec
contrainte de capacité et fenêtres de temps souples. Ils ont reformulé le problème sous la forme
d’un problème de tournées sur nœuds avec fenêtres de temps souples. Ils ont utilisé un algo-
rithme de résolution de type Branch-And-Price (cf. Barnhart et al. (1998)). Afsar (2010) a pro-
posé de résoudre ce problème en utilisant une heuristique basée sur un algorithme de génération
de colonnes. Dans un premier temps, la relaxation linéaire du problème est résolue à l’optimum
en utilisant la méthode de décomposition de Dantzig et Wolfe (1960). Ensuite, un algorithme
d’exploration arborescente est utilisé pour rechercher une solution entière au problème restreint
aux colonnes générées. Johnson et Wohlk (2008) ont aussi appliqué la génération de colonnes
à un problème de tournées sur arcs, mais avec fenêtres de temps rigides. Le problème maître

36
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 Chapitre 3. Revue de littérature

est un problème de couverture d’ensembles dans lequel chaque colonne représente une tournée.
Les tournées sont générées a priori et ajoutées au problème maître au fur et à mesure.

Programmation par contraintes Les approches de résolution utilisant la programmation par

contraintes ont très peu été étudiées. Il n’y a, à notre connaissance, que le papier de Aminu
et Eglese (2006) qui présente l’application d’une telle méthode à un problème de tournées sur
arcs. Ils ont proposé un programme de satisfaction de contraintes pour le problème du postier
chinois avec fenêtres de temps.

3.3 Applications
Les applications ayant reçu le plus d’attention dans la littérature scientifique sur les tournées
sur arcs sont la collecte des déchets, les maintenances routières hivernales et la livraison de
courrier postal. Ces problèmes possèdent des analogies avec le problème d’inspection des voies.
En effet, un planning de collecte consiste à organiser les tournées de sorte que la collecte des
déchets d’une portion de rue soit réalisée sans interruption. Cette contrainte fait aussi partie du
problème d’inspection. En ce qui concerne les maintenances hivernales des routes, l’analogie
est plus directe puisque dans un cas il faut surveiller des portions de route et dans l’autre il faut
inspecter des portions de voies.
Une des premières publications sur le sujet fut présentée par Bommisetty et Dessouky
(1998) qui décrivirent l’optimisation de la collecte des déchets recyclables d’un campus de
l’Illinois. Ils ont proposé une approche heuristique utilisant un algorithme en deux phases ap-
pliqués à une formulation sur nœuds. Kim et al. (2006) ont aussi proposé une heuristique pour
résoudre un problème de collecte de déchets sur nœuds. L’originalité de leur papier vient de la
prise en compte de plusieurs sites de déchargement ainsi que de la prise en compte des pauses
déjeuner.
Amponsah et Salhi (2004) ont décrit des heuristiques constructives pour résoudre un pro-
blème de collecte de déchets solides dans les pays en voie de développement. Bautista et al.
(2007) ont présenté une application d’un algorithme de colonies de fourmis pour l’optimisa-
tion de la collecte des déchets urbains d’une ville espagnole. Le modèle proposé est un CARP
reformulé en CVRP. Fu et al. (2009) ont décrit une application d’optimisation des tournées
de maintenance hivernale des routes. Ils ont proposé un modèle d’optimisation qui prend en
compte les informations météo en temps réel.
Une application réelle d’optimisation d’un service de livraison postal en Allemagne a été
décrite par Irnich (2007). Le problème consiste à optimiser la chaîne de transport du courrier
en prenant en compte les spécificités du réseau routier. Le problème est modélisé sous la forme
d’une variante d’un problème de postier rural venteux et transformé en problème de voyageur
de commerce asymétrique.
Une application originale de surveillance du réseau routier Québécois a été présenté par
Marzolf et al. (2006). Le problème consiste à visiter l’ensemble du réseau toutes les deux se-
maines. Ils remarquent que la minimisation de la distance totale parcourue est un objectif com-
munément utilisé dans les problèmes de tournées sur arcs, mais qui a peu d’intérêt dans leur
cas. En effet, les tournées sont souvent interrompues en cours de route à cause d’incidents sur
le réseau. Ils proposent l’étude de plusieurs algorithmes et fonctions objectifs permettant de
prendre en compte la position en temps réel des véhicules. Toujours pour le Québec, Perrier et

37
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 Chapitre 3. Revue de littérature

al. (2008) ont présenté une application d’optimisation de la surveillance du réseau routier en
utilisant une heuristique basée sur la résolution d’un programme mathématique. Une revue de
littérature en quatre articles sur ces problématiques de maintenances hivernales à été proposée
dans Perrier et al. (2006a,b, 2007b,a).

3.4 Maintenances des installations ferroviaires

Les articles sur l’optimisation des maintenances d’installations ferroviaires que nous avons
trouvés traitent tous de la minimisation d’un coût engendré par l’interruption de trafic lors de
la maintenance. Ces travaux peuvent être classés en deux catégories selon qu’ils prennent en
compte la détérioration de l’élément maintenu ou non. Dans la première catégorie, les fré-
quences de réalisation des tâches sont des variables de décision. Dans la seconde catégorie, le
modèle ne prend pas en compte la détérioration, les tâches de maintenances sont des données
d’entrée du problème et les variables de décision correspondent à l’affectation des tâches.

Dans Oyama et Miwa (2006), les auteurs présentent une méthode pour optimiser l’ordonnan-
cement des tâches de maintenances sur les traverses. Dans un premier temps, un modèle statis-
tique de l’évolution des détériorations des défauts et de l’impact de la réalisation des tâches de
maintenances est calculé. Ce modèle utilise des données historiques de la compagnie. Ensuite,
un programme mathématique est utilisé pour optimiser l’ordonnancement et la sélection des
tâches de maintenances à réaliser. L’horizon de planification dure un an et est discrétisé en 36
périodes.
Higgins (1998) a présenté un problème d’optimisation de la réalisation des tâches de main-
tenance qui prend en compte le personnel. L’objectif est de minimiser le nombre de trains devant
être replanifiés. Plus particulièrement, ils minimisent le temps pendant lequel la portion de voie
en maintenance a un niveau de service inférieur à la normale. Toutes les tâches doivent être réa-
lisées et aucun train ne peut être supprimé. Une durée minimale entre la réalisation des tâches
permet de modéliser le repositionnement des équipes de maintenance. Par contre, il est possible
de les retarder. Le problème est résolu avec un algorithme de recherche tabou.
Budai et al. (2006) ont proposé un problème d’ordonnancement de tâches de maintenances
préventives (Preventive Maintenance Scheduling Problem). Leur modèle prend en compte les
tâches périodiques de maintenances (tâches courtes) et les chantiers de renouvellement (tâches
longues). Une description sous forme de programme mathématique et des heuristiques rapides
sont proposées pour le résoudre. den Hertog et al. (2005) ont décrit une méthode pour grouper
les tronçons de voies en maintenance. Cette méthode permet de créer des ensembles de portions
de voie tels que si toutes les portions de voies d’un même ensemble sont en maintenance, il
existe une route alternative pour les trains les traversant. Fokkert et al. (2007) ont utilisé cette
méthode pour résoudre un problème de réservation de capacité pour des maintenances de nuit.
La méthode consiste dans un premier temps à créer les ensembles de portions de voies. Ensuite,
chaque ensemble est affecté à une nuit. L’horizon de planification est cyclique et dure quatre
semaines. Le planning ainsi généré est utilisé toute l’année pour réaliser les tâches de mainte-
nances. L’application de cette méthode aux Pays-Bas a permis de diviser par deux le nombre
d’accidents de chantiers mortels, puisqu’aucun train ne circule sur les voies en maintenance.
Dans Cheung (1999), le problème présenté consiste à affecter un maximum de tâches de
maintenances à des portions de voie. Leur modèle considère plusieurs types de tâches. Les

38
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 Chapitre 3. Revue de littérature

tâches ne peuvent être réalisées qu’à certains moments de la journée. Le modèle prend en
compte des contraintes de compatibilité entre tâches, permettant d’assurer la sécurité des chan-
tiers. Chaque type de tâche a une priorité et l’objectif est de maximiser le nombre de tâches prio-
ritaires réalisées. L’article contient la description d’un programme de satisfaction de contraintes
résolu en utilisant le logiciel CHiP. Grimes (1995) a présenté un algorithme génétique pour
résoudre un problème d’affectation des tâches de maintenances à des journées calendaires.

Ces articles soulignent la spécificité du problème d’optimisation des tournées d’inspection

des voies. Lorsque l’on recherche la fréquence optimale de réalisation des tâches de mainte-
nance, la solution est une valeur seuil en-dessous de laquelle la maintenance est considérée
comme non sécuritaire (sous-qualité) et au-dessus de laquelle elle est considérée comme trop
couteuse (sur-qualité). Les études scientifiques sur ce sujet consistent à rechercher une loi de
probabilité réaliste décrivant le risque de défaillance en fonction de la fréquence de réalisation
de la tâche. Pour le problème d’inspection des voies, nous faisons l’hypothèse que le modèle
de détérioration a permis de déterminer les dates de réalisation au plus tôt et au plus tard des
tâches d’inspections.
Pour ce qui est de l’optimisation du groupement des tâches ou de la possession de la voie,
l’objectif est de réduire les coûts engendrés par l’impossibilité des autres trains de circuler. Ce
type d’optimisation est possible lorsque les tâches de maintenance à optimiser sont de natures
différentes, réalisables en parallèles ou que l’on dispose d’une information fiable sur la circu-
lation des trains. Dans notre cas, les tâches sont de nature identique et ne sont réalisables en
parallèle que s’il y a plusieurs engins : sur chaque engin, elles sont réalisées de façon séquen-
tielle. De plus, durant l’étape de planification, les informations de circulation des autres trains
ne sont pas disponibles.

Nous concluons ce chapitre en remarquant que nous n’avons pas trouvé de publications pro-
posant une méthode pour traiter directement le problème d’optimisation des tournées d’ins-
pections des voies. Pourtant, ce levier d’amélioration des coûts de maintenance et de fiabilité
est important. Dans le cas des tournées d’auscultation à ultrasons, les programmes actuels des
engins engendrent plus de trajets haut-le-pied que de circulation en auscultation. Cette consta-
tation laisse à penser qu’il est possible de réduire les coûts liés aux trajets haut-le-pied (péage
RFF, temps de travail, etc.) et de mieux utiliser les engins (réduction de la taille du parc de
ressources) en limitant les trajets improductifs.

Conclusion
Le problème de tournées d’inspections des voies ferrées peut se modéliser sous la forme
d’un problème de tournées sur arcs avec fenêtres de temps, contraintes de capacité et dépôts
intermédiaires. Dans la littérature scientifique, les méthodes proposées pour résoudre le CARP-
TW sont principalement de deux types. Les algorithmes mémétiques semblent aujourd’hui les
plus performants pour fournir une solution réalisable. Ils font intensivement appel à une rou-
tine qui fournit en temps polynomial une solution réalisable (satisfaction des contraintes de
capacité et insertion des retours au dépôt) à partir d’une séquence d’arcs. Dans ces approches,
l’optimisation du séquencement est réalisée par le biais de croisements de solutions (algorithme
génétique) tandis qu’une heuristique découpe de façon optimale la tournée géante pour fournir
la valeur de la solution. L’autre approche de résolution bénéficiant d’un intérêt certain dans la

39
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 Chapitre 3. Revue de littérature

communauté scientifique est la génération de colonnes. Les problèmes maîtres proposés par
les différents auteurs considèrent tous la sélection des tournées à réaliser. Le séquencement des
arcs et la satisfaction des contraintes de capacité sont réalisés par l’application d’un programme
dynamique.
Il faut remarquer que ces approches sont appliquées à des problèmes dont le séquence-
ment des tournées n’est pas déterminant puisqu’il n’y a qu’un seul dépôt et dont la flotte est
homogène. De plus, les instances proposées ne prennent pas en compte l’impossibilité de tra-
verser certains arcs à des périodes données. En ce qui concerne les algorithmes mémétiques,
les fenêtres de temps sont prises en compte lors de l’évaluation de la valeur de chaque indi-
vidu. Dans le cas du problème d’inspection, nous supposons que les fenêtres de temps sont trop
contraignantes et doivent être prises en compte pendant la génération des journées de service.
Un avantage certain des méthodes par génération de colonnes pour la réalisation d’une appli-
cation industrielle vient du fait qu’elles sont basées sur des programmes mathématiques. Les
évolutions du modèle et la prise en compte de contraintes spécifiques comme les gares de repos
sont alors facilitées. De plus, la possibilité de sauver les colonnes générées pour une résolution
ultérieure permet de pallier le désavantage principal dû à la longueur des temps de calcul.

40
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
Deuxième partie

Mise en œuvre

57
Troisième partie

Conclusion

113
Chapitre 8

Conclusion et perspectives

Le modèle mathématique proposé pour résoudre le problème d’inspection par ultrasons a été
validé. Sa capacité à fournir des solutions pertinentes pouvant servir de base à une programma-
tion annuelle des tournées d’engins d’auscultation à ultrasons à été démontrée. Ce modèle est
une base de travail pour d’autres travaux sur l’optimisation de tournées nationales.

La capacité du calculateur à prendre en compte les chantiers de façon pertinente n’a pas été
démontrée. Les deux raisons potentielles sont le manque d’informations sur les types de chan-
tiers et l’utilisation de vitesse moyenne des engins dans le modèle. Néanmoins, un post traite-
ment et une signalisation des tâches d’inspection réalisées pendant des chantiers directement
dans l’interface utilisateur a permis de valider l’intérêt de l’outil d’aide à la programmation. De
plus, l’objectif d’un maximum de 50% de haut-le-pied dans le programme optimisé est atteint
avec une tolérance de 1% pour l’ensemble des jeux de données testés.

Un schéma de décomposition exact, basé sur la méthode de décomposition de Benders, a été

proposé pour résoudre un problème général de tournées sur arcs. Une heuristique, basée à la fois
sur la génération de colonnes et de contraintes, capable de résoudre des problèmes de grande
taille a été tirée de cette méthode.

Une méthode originale de projection de coupe, invalidant la solution continue ayant servi
de point de départ à une procédure d’arrondi a été présentée. Elle a été utilisée dans le cadre
d’une méthode de résolution à base de programmation linéaire et coupes heuristiques. L’intérêt
des méthodes de décomposition mathématique pour la création d’heuristiques a été montré par
comparaison avec un algorithme glouton évolué. Une nouvelle méthode d’exploration basée sur
la détermination du prix de chaque décision prise a été proposée.

8.1 Perspectives de recherches académiques

Pseudo coupe locale La projection heuristique de la coupe combinatoire que nous avons
proposée n’a pas put être étudiée en détail. La caractéristique principale de cette coupe est
qu’elle est efficace directement dans la relaxation continue et donc n’impose pas la résolution
en nombres entiers du programme mathématique. En contrepartie, elle peut couper des solutions

115
 Chapitre 8. Conclusion et perspectives

réalisables. Il serait intéressant de comprendre quels sont les types de problèmes qui peuvent
bénéficier de ce type de projection.

Relaxation des sous problèmes de Benders L’intérêt de la relaxation des sous problèmes de
Benders semble avéré dans certains cas. Pour le problème d’inspection, la relaxation proposée
est résolue très rapidement et fournit une coupe de Benders plus efficace que la coupe issue du
sous problème original. Cette approche par relaxation permet donc de générer plus rapidement
des coupes qui invalident plus de solutions irréalisables. Il serait intéressant de continuer à
étudier l’impact d’une telle approche par relaxation des sous problèmes, notamment lors de la
résolution de problèmes industriels de grande taille. En effet, les modèles mathématiques les
représentant sont souvent le résultat de la fusion de plusieurs modèles développés au cours des
années. L’extraction de sous problèmes dont la solution peut être obtenue en temps polynomial
devient alors facile. La difficulté consiste alors à déterminer les sous problèmes qui prouveront
le plus rapidement l’irréalisabilité d’une solution partielle.

Génération de colonnes et contraintes Cette heuristique a prouvé son efficacité pour fournir
dans des temps de calcul courts des solutions de qualité satisfaisante. D’autres applications
industrielles pourraient bénéficier de cette approche.

8.2 Perspectives d’amélioration industrielles

8.2.1 engins
La généricité du problème de tournées d’inspection autorise l’utilisation du calculateur pour
optimiser d’autres types de tournées. Les engins à ultrasons sont un des nombreux engins qui
peuvent bénéficier d’une programmation optimisée par l’outil.
Par exemple, les Mauzin 1 sont des engins d’inspection qui mesurent les déformations de
la voies. Ils sont utilisés pour vérifier périodiquement la géométrie de la voie. Les tournées des
engins graisseur, qui doivent régulièrement graisser les caténaires, peuvent aussi être optimisées
avec cet outil.

8.2.2 pré-opérationnelle
Lors de la programmation pré-opérationnelle, les programmateurs des engins ont à leur dis-
position des informations plus fiables que pendant la programmation annuelle. Ils doivent aussi
prendre en compte la non réalisation de certaines tâches dont ils doivent rattraper le retard au
plus vite. Le besoin d’un outil pour accompagner les programmateurs pendant la phase pré-
opérationnelle de planification semble être essentiel. La remontée au niveau national de la pla-
nification des engins d’inspection augmente la charge de travail des concepteurs.
L’horizon de planification est donc restreint à quelques semaines. Cette restriction tem-
porelle peut permettre de prendre en compte des contraintes plus fines. Il serait par exemple
intéressant de pouvoir calculer les circulations des engins en fonction des sillons libres. Pour
faciliter le travail des programmateurs, il sera intéressant de fournir des solutions robustes aux
aléas ou facilement adaptable.
1. du nom de son inventeur André Mauzin

116
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 Chapitre 8. Conclusion et perspectives

Les domaines de recherche de l’optimisation en ligne, de l’optimisation robuste Mulvey

et Vanderbei (1995), de la recherche d’(a, b)-supersolutions Hebrard (2006) ou de l’optimisa-
tion inverse Ahuja et Orlin (2001) pourraient faciliter la programmation pré-opérationnelle des
engins de maintenances.

117
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
 Chapitre 8. Conclusion et perspectives

118
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
Annexe

119
Annexe A

Réseau grands axes

Le tableau de la figure A.1 présente les portions de voies prises en compte dans le réseau
grands axes. Pour faciliter la circulation des engins et pour favoriser des auscultations conti-
nues de lignes, certaines portions de voies, bien qu’ayant une fréquence supérieure à un an sont
ajoutées dans les grands axes. La sur-auscultation qui en résulte est présentée dans la colonne
« sur-auscultation ». Nous remarquons que cette sur-auscultation est importante puisqu’elle re-
présente presque la moitié de la longueur totale auscultée dans l’année. Cette importance est à
relativiser puisque les fréquences de la majorité de ces portions de voies (groupe UIC 4) sont
de l’ordre d’un an à quelques semaines.

121
 Chapitre A. Réseau grands axes

Axe Ligne PKD PKF L V1+V2 GrUIC d’axe Cycle km auscultés /an Sur auscultation Sous auscultation
Secteur NE
Paris - strasbourg - Mulhouse 70000 0,00 502,00 1004,00 3,03 1 an 1220,00 158 210
115000 0,00 108,00 216,00
Lille - Thionville - Metz - Nancy 267000 0,00 122,60 245,19 2,97 6 mois 1599,01 188
212000 0,00 27,64 55,28 110,56
222000 27,64 51,00 46,72 93,44
223000 150,51 142,49 16,04 32,08
204000 140,68 277,20 273,05 546,10
180000 188,00 154,32 67,37 134,74
89000 353,70 339,63 28,14 56,28
90000 377,19 343,33 67,72 135,43
Creil - Aulnoye 242000 50,89 72,70 43,61 3,51 1 an 329,41 168,74
Toul - Dijon 32000 114,01 0,00 228,02 3,00 1 an 389,60
1000 311,85 307,63 8,45
843000 390,77 346,81 87,93
849000 314,21 346,81 65,20
Paris - Lille 272000 0,00 250,93 501,86 2,98 6 mois 1003,71 803,71
Secteur Sud - Est
Paris - Marseille 830000 0,00 862,10 1724,20 2,86 6 mois 3448,40 2580,40
Marseille - Vintimille 930000 0,00 250,94 501,88 4,00 1 an 501,88 501,88
Lyon - Culoz - Modane 890000 0,00 101,36 202,71 2,79 6 mois 943,83 204,00
900000 101,36 235,96 269,20 538,04
Rive droite du Rhône 800000 530,48 744,58 428,20 3,80 1 an 428,20 343,04
Secteur Sud-Ouest
Tarascon - Sète 810000 0,00 104,53 209,06 3,00 1 an 209,60
Bordeaux - Sète 640000 0,00 475,89 951,78 3,99 1 an 951,78 530,00
Bordeaux - Bayonne 655000 0,00 197,56 395,11 4,00 1 an 395,11 395,11
Orléans - Montauban 590000 118,93 663,44 1089,02 4,18 1 an 1089,02 1089,02
Paris - Bordeaux 570000 0,00 583,84 1167,69 2,84 6 mois 2335,38 1959,38
Secteur Nord - Ouest
Paris - Le Havre 340000 0,00 227,92 455,84 3,39 1 an 455,84 177,84
Paris - Le Mans - Rennes 420000 0,00 373,25 746,50 4,20 1 an 746,50 524,50
Le Mans - Nantes 450000 210,98 305,82 189,68 4,04 1 an 364,62 189,68
LGV
5000 0,00 3,29 6 mois 5700,09
216000 0,00 115,22 230,44
226000 0,00 210,00 420,00
269000 2,00 15,00 26,00
752000 0,00 711,00 1422,00
226310 0,00 57,00 114,00
752100 0,00 39,40 78,80
429000 130,46 179,60 98,28
431000 1,25 231,51 460,52
Total 14135,49 22111,98 11459,97 210
Total (6 mois) 15030,42
Total (1 an) 7081,56

F IGURE A.1 – Description des grands axes.

122
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
Bibliographie

H. M. Afsar. A Branch-and-Price Algorithm for Capacitated Arc Routing Problem with Flexible
Time Windows. Electronic Notes in Discrete Mathematics, 36 :319–326, 2010.

R. K. Ahuja et J. B. Orlin. Inverse Optimization. Operations Research, 49(5) :771–783, 2001.

A. Amaya, A. Langevin et M. Trépanier. The capacitated arc routing problem with refill points.
Operations Research Letters, 35 :45–53, 2007.

A. Amberg, W. Domschke et S. Voß. Multiple center capacitated arc routing problems : A

tabu search algorithm using capacitated trees. European Journal of Operational Research,
124 :360–376, 2000.

U. Aminu et R. Eglese. A constraint programming approach to the Chinese postman problem

with time windows. Computers & Operations Research, 33 :3423–3431, 2006.

S. Amponsah et S. Salhi. The investigation of a class of capacitated arc routing problems : the
collection of garbage in developing countries. Waste Management, 24 :711–721, 2004.

J. Aráoz, E. Fernández et C. Zoltan. Privatized rural postman problems. Computers &

Operations Research, 33 :3432–3449, 2006.

C. Barnhart, E. L. Johnson, G. L. Nemhauser, M. W. P. Savelsbergh et P. H. Vance. Branch-

and-Price : Column Generation for Solving Huge Integer Programs. Operations Research,
46(3) :316–329, 1998.

J. Bautista, E. Fernández et J. Pereira. Solving an urban waste collection problem using ants
heuristics. Computers and Operations Research, 35 :3020–3033, 2007.

J.-M. Belenguer, E. Benavent, P. Lacomme et C. Prins. Lower and upper bounds for the mixed
capacitated arc routing problem. Computers & Operations Research, 33 :3363–3383, 2006.

E. Benavent, A. Carrotta, A. Corberán, J. M. Sanchis et D. Vigo. Lower bounds and heuristics

for the Windy Rural Postman Problem. European Journal of Operational Research, 176 :855–
869, 2007.

E. Benavent, A. Corberán, E. Piñana, I. Planaa et J. M. Sanchisb. New heuristic algorithms for

the windy rural postman problem. Computers & Operations Research, 32 :3111–3128, 2005.

J. Benders. Partitioning procedures for solving mixed-variables programming problems.

Numerische Mathematik, 4 :238–252, 1962.

123
BIBLIOGRAPHIE BIBLIOGRAPHIE

P. Beullens, L. Muyldermans, D. Cattrysse et D. V. Oudheusden. A guided local search heuristic

for the capacitated arc routing problem. European Journal of Operational Research, 147 :629–
643, 2003.

J. Blitz. Electrical and Magnetic Methods of Non-destructive Testing. Springer, 1997.

D. Bommisetty et M. Dessouky. Scheduling Collection Of Recyclable Material At Northern Illi-

nois University Campus Using A TwoPhase Algorithm. Computers & Industrial Engineering,
35 :435–438, 1998.

J. Brandão et R. Eglese. A deterministic tabu search algorithm for the capacitated arc routing
problem. Computers & Operations Research, 35 :1112 – 1126, 2008.

P. Brucker. Graph Theoretic Concepts in Computer Science, Chapitre The Chinese Postman
Problem for Mixed Graphs, pages 354–366. Springer, Berlin, 1981.

G. Budai, D. Huisman et R. Dekker. Scheduling Preventive Railway Maintenance Activities.

The Journal of the Operational Research Society, 57(9) :pp. 1035–1044, 2006.

E. A. Cabral, M. Gendreau, G. Ghiani et G. Laporte. Solving the hierarchical Chinese postman

problem as a rural postman problem. European Journal of Operational Research, 155 :44–50,
2004.

G. Carpaneto, M. Dell’Amico et P. Toth. Exact solution of large-scale, asymmetric traveling

salesman problems. ACM Trans. Math. Softw., 21 :394–409, 1995.

Cheung. Railway Track Possession Assignment Using Constraint Satisfaction. Engineering

Applications of AI, 12, 1999.

N. Christofides. The optimum traversal of a graph. Omega, 1(6) :719–732, 1973.

F. Chu, N. Labadi et C. Prins. Heuristics for the periodic capacitated arc routing problem.
Journal of Intelligent Manufacturing, 16 :243–251, 2005. 10.1007/s10845-004-5892-8.

V. Chvàtal. A Greedy Heuristic for the Set-Covering Problem. Mathematics of operations

research, 4(3) :233–235, 1979.

G. Clarke et J. W. Wright. Scheduling of Vehicles from a Central Depot to a Number of Delivery

Points. Operations Research, 12(4) :568–581, 1964.

G. Codato et M. Fischetti. Combinatorial Benders’ Cuts. Dans D. Bienstock et G. Nemhauser,

eds., Integer Programming and Combinatorial Optimization, volume 3064 de Lecture Notes
in Computer Science, pages 29–46. Springer Berlin / Heidelberg, 2004.

A. Corberán, R. Martí et A. Romero. Heuristics for the Mixed Rural Postman Problem.
Computers & Operations Research, 27 :183–203, 2000.

A. Corberán, R. Martí et J. Sanchis. A GRASP heuristic for the mixed Chinese postman pro-
blem. European Journal of Operational Research, 142 :70–80, 2002a.

A. Corberán, R. Martmí, E. Martmínez et D. Soler. The Rural Postman Problem on mixed

graphs with turn penalties. Computers & Operations Research, 29 :887–903, 2002b.

124
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
BIBLIOGRAPHIE BIBLIOGRAPHIE

G. B. Dantzig et P. Wolfe. Decomposition Principle for Linear Programs. Operations Research,

8 :101–111, 1960.

D. den Hertog, J. van Zante-de Fokkert, S. Sjamaar et R. Beusmans. Optimal working zone
division for safe track maintenance in The Netherlands. Accident Analysis & Prevention,
37(5) :890 – 893, 2005.

M. Dror. Arc Routing : Theory, Solutions and Applications. Springer, 2000.

M. Dror, H. Stern et P. Trudeau. Postman Tour on a Graph With Precedence Relation on Arcs.
Networks, 17 :283–294, 1987.

J. Edmonds et E. L. Johnson. Matching, Euler tours and the Chinese postman. Mathematical
Programming, 5 :88–124, 1973. 10.1007/BF01580113.

H. A. Eiselt, M. Gendreau et G. Laporte. Arc Routing Problems, Part I : The Chinese Postman
Problem. Operations Research, 43(2) :231–242, 1995a.

H. A. Eiselt, M. Gendreau et G. Laporte. Arc Routing Problems, Part II : The Rural Postman
Problem. Operations Research, 43(3) :399–414, 1995b.

EPSF. Rapport sur la sécurité du réseau ferroviaire national. Rapport technique, 2008.

L. Euler. Solutio Problematis ad Geometrian Situs Pertinentis. Commentarii academiae

scientarum Petropolitanae, 8 :128–140, 1736.

D. Feillet, P. Dejax, M. Gendreau et C. Gueguen. An exact algorithm for the elementary shor-
test path problem with resource constraints : Application to some vehicle routing problems.
Networks, 44(3) :216–229, 2004.

M. Fischetti, D. Salvagnin et A. Zanette. A note on the selection of Benders’ cuts. Mathematical

Programming, 124 :175–182, 2010. 10.1007/s10107-010-0365-7.

J. Fokkert, D. den Hertog, F. J. v. d. Berg et J. H. M. Verhoeven. The Netherlands Schedules

Track Maintenance to Improve Track Workers’ Safety. Interfaces, 37(2) :133–142, 2007.

G. N. Frederickson. Approximation Algorithms for Some Postman Problems. Journal of the

ACM, 26(3) :538–554, 1979.

L. Fu, M. Trudel et V. Kim. Optimizing winter road maintenance operations under real-time
information. European Journal of Operational Research, 196(1) :332 – 341, 2009.

M. R. Garey et D. S. Johnson. Computers and Intractability ; A Guide to the Theory of

NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1990.

G. Ghiani et G. Improta. An algorithm for the hierarchical Chinese postman problem.

Operations Research Letters, 26 :27–32, 2000a.

G. Ghiani et G. Improta. An efficient transformation of the generalized vehicle routing problem.

European Journal of Operational Research, 122 :11–17, 2000b.

125
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
BIBLIOGRAPHIE BIBLIOGRAPHIE

G. Ghiani, G. Improta et G. Laporte. The capacitated arc routing problem with intermediate
facilities. Networks, 37(3) :134–143, 2001.
B. Golden, E. Baker et J. DeArmon. Computational experiments with algorithms for a class of
routing problem. Computers and Operations Research, 10 :47–59, 1983.
B. L. Golden et R. T. Wong. Capacitated Arc Routing Problems. Networks, 11 :305–315, 1981.
C. Grimes. Application of genetic techniques to the planning of railway track maintenance
work. pages 467 –472. 1995.
M. Guan. A Survey of the Chinese Postman Problem. J. Math. Res. and Expos., 4 :113–119 (in
Chinese), 1984.
E. Hebrard. Robust Solutions for Constraint Satisfaction and Optimisation under Uncertainty.
Thèse de doctorat, University of New South Wales, 2006.
A. Higgins. Scheduling of Railway Track Maintenance Activities and Crews. The Journal of
the Operational Research Society, 49(10) :pp. 1026–1033, 1998.
K. Holmberg. On the convergence of cross decomposition. Mathematical Programming,
47 :269–296, 1990. 10.1007/BF01580863.
J. Hooker et G. Ottosson. Logic-based Benders decomposition. Mathematical Programming,
96(1) :33–60, 2003.
IN2070. Surveillance des rails posés sur voies principales. Rapport technique, SNCF, 2002.
IN2600. Engins lourds d’auscultation par ultrasons - Principes d’organisation. Rapport tech-
nique, SNCF, 2002.
InfraLog. Catalogue des engins + fiches techniques. Rapport technique, SNCF, 2010.
S. Irnich. Solution of real-world postman problems. European Journal of Operational Research,
2007.
E. L. Johnson et S. Wohlk. Solving the Capacitated Arc Routing Problem with Time Windows
using Column Generation. Rapport technique, Centre for Operations Research Applications
in Logistics, 2008.
M.-Y. Kao, ed.. Encyclopedia of Algorithms. Springer-Verlag GmbH, 2008.
B.-I. Kim, S. Kim et S. Sahoo. Waste collection vehicle routing problem with time windows.
Computers & Operations Research, 33 :3624–3642, 2006.
P. Korteweg et T. Volgenant. On the Hierarchical Chinese Postman Problem with linear ordered
classes. European Journal of Operational Research, 169 :41–52, 2006.
P. Lacomme, C. Prins et W. Ramdane-Cherif. Competitive Memetic Algorithms for Arc Routing
Problems. Annals of Operations Research, 131 :159–185, 2004.
P. Lacomme, C. Prins et W. Ramdane-Chérif. Evolutionary algorithms for periodic arc routing
problems. European Journal of Operational Research, 165 :535–553, 2005.

126
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
BIBLIOGRAPHIE BIBLIOGRAPHIE

G. Laporte et F. Semet. The Vehicle Routing Problem, Chapitre Classical Heuristics for the
Capacitated VRP, pages 109–128. SIAM, 2001.

J. K. Lenstra et A. H. G. R. Kan. On General Routing Problems. Networks, 6 :273–280, 1976.

H. Longo, M. P. de Aragão et E. Uchoa. Solving capacitated arc routing problems using a

transformation to the CVRP. Computers & Operations Research, 33 :1823–1837, 2006.

M. Lübbecke et J. Desrosiers. Selected Topics in Column Generation. Operations Research,

53 :1007–1023, 2005.

F. Marzolf, M. Trépanier et A. Langevin. Road network monitoring : algorithms and a case

study. Computers & Operations Research, 33 :3494–3507, 2006.

K. Mei-Ko. Graphic Programming Using Odd or Even Points. Chinese Mathematical Journal,
1 :273–277, 1962.

E. Minieka. The Chinese Postman Problem For Mixed Networks. Management Science,
25 :643–648, 1979.

P. Mullaseri. Capacitated Rural Postman Problem with Time Windows and Split Delivery.
Thèse de doctorat, MIS Department, University of Arizona, Tucson, Arizona, 1997.

S. M. Mulvey et R. J. Vanderbei. Robust optimization of large-scale systems. Operations

Research, 43 :264–281, 1995.

C. Orloff. A Fundamental Problem in Vehicle Routing. Networks, 4 :35–64, 1974.

T. Oyama et M. Miwa. Mathematical modeling analyses for obtaining an optimal railway track
maintenance schedule. Japan Journal of Industrial and Applied Mathematics, 23 :207–224,
2006. 10.1007/BF03167551.

C. H. Papadimitriou. On the complexity of edge traversing. Journal of the ACM, 23(3) :544–
554, 1976.

M. Papaelias, M. Lugg, C. Roberts et C. Davis. High-speed inspection of rails using ACFM

techniques. NDT & E International, 42(4) :328 – 335, 2009.

W. Pearn, A. Assad et B. Golden. Transforming arc routing into node routing problems.
Computers and Operations Research, 14(4) :285–8, 1987.

W. L. Pearn. Approximate solutions for the capacitated arc routing problem. Computers &
Operations Research, 16(6) :589–600, 1989.

N. Perrier, A. Langevin et C.-A. Amaya. Vehicle Routing for Urban Snow Plowing Operations.
Transportation Science, 42 :44–56, 2008.

N. Perrier, A. Langevin et J. F. Campbell. A survey of models and algorithms for winter road
maintenance. Part I : system design for spreading and plowing. Computers & Operations
Research, 33 :209–238, 2006a.

127
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF
BIBLIOGRAPHIE BIBLIOGRAPHIE

N. Perrier, A. Langevin et J. F. Campbell. A survey of models and algorithms for winter road
maintenance. Part II : system design for snow disposal. Computers & Operations Research,
33 :239–262, 2006b.

N. Perrier, A. Langevin et J. F. Campbell. A survey of models and algorithms for winter

road maintenance. Part III : Vehicle routing and depot location for spreading. Computers
& Operations Research, 34 :211–257, 2007a.

N. Perrier, A. Langevin et J. F. Campbell. A survey of models and algorithms for winter

road maintenance. Part IV : Vehicle routing and fleet sizing for plowing and snow dispo-
sal. Computers & Operations Research, 33 :239–262, 2007b.

W. Ramdane-Cherif. Problèmes d’optimisation en tournées sur arcs. Thèse de doctorat, Uni-

versité de Technologie de Troyes, 2002.

W. Ramdane Cherif. Evolutionary Algorithms for Capacitated Arc Routing problems with Time
Windows. Dans 12th IFAC Symposium on Information Control Problems in Manufacturing
- INCOM. Saint-Etienne/France, 2006.

RH0077. Réglementation du travail. Rapport technique, SNCF, 2005.

R. Rivier et Y. Putallaz. Audit sur l’état du réseau ferré national fran cais. Rapport technique,
EPFL, 2005.

S. Spoorendonk. Cut and Column Generation. Thèse de doctorat, Faculty of science, University
of Copenhagen, 2008.

A. Srinivasan. Improved approximations of packing and covering problems. Dans Proceedings

of the twenty-seventh annual ACM Symposium on Theory of Computing, pages 268–276.
1995.

M. Tagmouti, M. Gendreau et J.-Y. Potvin. Arc routing problems with time-dependent service
costs. European Journal of Operational Research, 181 :30–39, 2007.

P. Toth et D. Vigo. The Vehicle Routing Problem, Chapitre Branch-and-Bound algorithms for
the Capacitated VRP, pages 29–51. SIAM, 2001.

F. Vanderbeck. On Dantzig-Wolfe Decomposition in Integer Programming and ways to Perform

Branching in a Branch-and-Price Algorithm. Operations Research, 48(1) :111–128, 2000.

Z. Win. On the Windy Postman Problem on Eulerian Graphs. Mathematical Programming,

44 :97–112, 1989.

S. Wohlk. Contributions to arc routing. Thèse de doctorat, Faculty of Social Sciences, Univer-
sity of Southern Denmark, 2005.

128
Document confidentiel propriété de la SNCF
Ne peut être reproduit sans l’autorisation expresse de la SNCF