These 3
These 3
These 3
THÈSE
pour l’obtention du
Discipline : Informatique
présentée par
Xavier DELORME
Xavier Delorme i
Avant-propos
J’adresse également tous mes remerciements à l’ensemble des personnes que j’ai cotoyé
durant ces trois années au sein de l’INRETS et de l’Université de Valenciennes. Je pense plus
particulièrement à ceux ayant travaillé avec moi au sein de l’unité de recherche Évaluation
des Systèmes de Transports Automatisés et de leur Sécurité dirigée par Monsieur Gérard
Couvreur, et de l’équipe Recherche Opérationnelle et Informatique du Laboratoire d’Auto-
matique et d’Informatique industrielles et Humaines dirigée par le Professeur Frédéric Semet.
Je tiens notamment à saluer David, Dorian, Georges, Olivier, Samuel et Philippe pour leur
Enfin, je remercie ma femme, ma famille et mes amis pour la patience qu’ils ont eue à
mon égard et les moments de joie et de détente qu’ils ont su m’apporter.
iv Xavier Delorme
Table des matières
Introduction 1
1 Contexte de modélisation 5
1.1 Principes de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1 Qu’est-ce qu’un modèle linéaire ? . . . . . . . . . . . . . . . . . . . . 6
1.1.2 Résolution exacte d’un modèle linéaire . . . . . . . . . . . . . . . . . 7
1.1.3 Résolution approchée d’un modèle linéaire . . . . . . . . . . . . . . . 10
1.2 Un problème facile : le problème de plus court chemin . . . . . . . . . . . . . 11
1.2.1 Définition du problème de plus court chemin . . . . . . . . . . . . . . 12
1.2.2 Résolution du problème de plus court chemin . . . . . . . . . . . . . 13
1.3 Un problème difficile : le problème de set packing . . . . . . . . . . . . . . . 13
1.3.1 Définition du problème de set packing . . . . . . . . . . . . . . . . . 14
1.3.2 Similarités avec d’autres problèmes en variables binaires . . . . . . . 15
1.3.3 Résolution du problème de set packing . . . . . . . . . . . . . . . . . 19
1.4 Optimisation de problèmes multiobjectifs . . . . . . . . . . . . . . . . . . . . 20
1.4.1 Qu’est-ce qu’un problème multiobjectif ? . . . . . . . . . . . . . . . . 20
1.4.2 Résolution d’un problème multiobjectif . . . . . . . . . . . . . . . . . 22
1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Xavier Delorme v
Table des matières
vi Xavier Delorme
Table des matières
Glossaire 133
Bibliographie 135
Index 144
Xavier Delorme ix
Table des figures
x Xavier Delorme
Liste des tableaux
Xavier Delorme xi
Liste des algorithmes
Xavier Delorme xv
Introduction
Ce mémoire synthétise mes travaux de recherche réalisés, durant ces trois dernières
années, au sein de l’INRETS1 (unité de recherche ESTAS2 ) et du LAMIH3 (équipe ROI4 )
dans le cadre de mon doctorat. Ils s’inscrivent dans l’une des thématiques principales de ces
deux laboratoires : la gestion et l’optimisation des systèmes de transport. Plus précisément,
le problème traité ici relève du domaine de la planification et de la programmation de l’ex-
ploitation ferroviaire. Parmi les très nombreuses problématiques issues de ce domaine, nous
nous intéressons à la question de l’évaluation de la capacité des infrastructures.
Cette question s’inscrit dans le cadre d’un processus de gestion ferroviaire prévisionnelle
à long et moyen terme. Pour mettre en œuvre une stratégie d’offre, il est impératif de se doter
d’outils permettant de situer les limites d’un réseau (existant ou futur) par rapport à une,
ou plusieurs, offre(s) possible(s). En outre, ces outils doivent aussi faciliter l’étude précise
de chaque variante d’infrastructure pour en évaluer l’intérêt, la construction de nouvelles
infrastructures nécessitant la mobilisation de moyens financiers très importants. L’évaluation
de la capacité d’une infrastructure ferroviaire permet ainsi de concevoir et d’évaluer une offre
répondant à la demande future sans surdimensionner les investissements et en utilisant au
mieux l’existant.
Cette question s’avère cruciale dans le contexte actuel. En effet la demande, en terme
de transport ferroviaire, est appelée à évoluer (concurrence des autres modes de transport,
séparation entre le gestionnaire et l’exploitant de l’infrastructure, . . .) et à croı̂tre fortement
(besoins accrus en terme de mobilité, substitution souhaitée à la route, . . .) dans les pro-
chaines années. Dans ce cadre, cette problématique se révèle particulièrement importante
dans une région comme le Nord-Pas-de-Calais, celle-ci étant placée en position de carrefour
au niveau européen. Le projet régional RECIFE, dans lequel s’inscrit cette thèse, tente
de répondre à ce besoin croissant. Il est l’objet d’une collaboration en cours entre l’INRETS,
le LAMIH et la SNCF5 et doit donner lieu à une validation sur la gare de Lille-Flandres.
1
Institut National de REcherche sur les Transports et leur Sécurité
2
Évaluation des Systèmes de Transport Automatisés et de leur Sécurité
3
Laboratoire d’Automatique, de Mécanique et d’Informatique industrielles et Humaines, UMR CNRS
8530
4
Recherche Opérationnelle et Informatique
5
Société Nationale des Chemins de fer Français
Le champ de questions soulevées lors d’une étude de capacité est vaste. Il inclut notam-
ment la détermination du nombre de trains pouvant circuler dans l’infrastructure. Cependant,
d’autres questions se posent aussi très souvent :
– La capacité de l’infrastructure est-elle suffisante pour faire face aux évolutions de
l’offre ?
– Quels sont les investissements offrant le meilleur débit pour les offres à venir ?
– Quelle est la meilleure façon de répondre à l’offre ?
De plus, si ces études peuvent être réalisées sans difficulté particulière pour des infra-
structures simples, la combinatoire induite par la complexité de certaines infrastructures
rend nécessaire l’utilisation de méthodes algorithmiques. Cela est notamment le cas lors de
l’étude d’une portion importante d’un réseau ou d’une zone comprenant de nombreux croise-
ments comme un nœud. L’accroissement des circulations transforme ainsi certains nœuds du
réseau ferroviaire en véritables goulets d’étranglement. Cette situation y rend très critique
la gestion du trafic. Ces nœuds se comportent alors comme de véritables amplificateurs de
retards, en transformant une petite perturbation en une avalanche de retards.
ont aussi été engagés. Des expérimentations numériques, menées sur des instances correspon-
dant au problème ferroviaire étudié mais aussi sur d’autres générées aléatoirement, montrent
l’efficacité de ces algorithmes pour obtenir la solution optimale, ou au moins une solution de
très bonne qualité dans des temps raisonnables.
Contexte de modélisation
linéaires affines des variables de décision, ce problème sera appelé programme linéaire. La
plupart des éléments généraux présentés dans cette section ont été décrits dans de nombreux
ouvrages (citons à titre d’exemple l’ouvrage de Gondran et Minoux [GM95] ou encore de
Nemhauser et Wolsey [NW99]).
Cependant, dans de nombreuses situations réelles, des variables peuvent être astreintes
au domaine des valeurs discrètes (nombre de pièces à produire par exemple). Ces problèmes
sont dits en variables mixtes (Mixed Integer Linear Problem). Lorsque toutes les variables du
1
La notation X ∈ D signifie que le vecteur X représente une solution admissible vis-à-vis du système de
contraintes et des bornes
problème sont entières, on parle d’un problème en variables entières (Integer Linear Program)
qui se présente sous la forme suivante (1.2) :
n
X
Opt zILP (X) = ci xi
i=1
n
X
sc ti,j xi ∆j dj , ∀j
i=1
(1.2)
li ≤ xi ≤ ui , ∀i
xi ∈ ZZ , ∀i
∆j ∈ {≤ ; = ; ≥} , ∀j
Lorsque les contraintes d’intégrité des variables d’un MILP ou d’un ILP sont relachées,
on parle de relaxation linéaire du problème. Cette relaxation donne une borne supérieure
(resp. inférieure) à la valeur de la fonction objectif pour les problèmes de maximisation (resp.
minimisation).
Enfin, certains problèmes comportent uniquement des variables de type booléen (pour
des décisions par exemple). La formulation algébrique d’un problème en variables binaires
(0-1ILP) est la suivante (1.3) :
n
X
Opt z0-1ILP (X) = ci xi
i=1
Xn
sc ti,j xi ∆j dj , ∀j
(1.3)
i=1
x = {0 ; 1} , ∀i
i
∆j ∈ {≤ ; = ; ≥} , ∀j
Les problèmes n’utilisant que des variables booléennes sont nombreux (par exemple des
problèmes d’affectation, de transport, de transbordement). Même si une variable binaire
peut-être considérée comme une variable entière aux valeurs restreintes à l’intervalle discret
[0; 1], ces problèmes méritent une attention particulière en raison de leurs caractéristiques
spécifiques et des méthodes de résolution qui leur sont appliquées.
lution optimale et de démontrer son optimalité. Les méthodes de résolution exactes sont
nombreuses. Comme pour tout algorithme, une manière de comparer ces méthodes est de
considérer leur complexité mathématique dans le pire des cas. Ainsi, on parlera d’un algo-
rithme de complexité :
– polynomiale lorsque son temps de calcul est borné par un polynôme de la taille du
problème (c-à-d que la complexité dans le pire des cas de l’algorithme est en O(np mq )
avec p et q constants),
– exponentielle lorsque son temps de calcul ne peut pas être borné par un polynôme de
la taille du problème (c-à-d que la complexité dans le pire des cas de l’algorithme est
par exemple en O(pn ) ou en O(pm ) avec p constant).
Par extension, la théorie de la complexité (voir l’ouvrage de Garey et Johnson [GJ79]
pour une description détaillée) s’intéresse à la complexité des modèles de programmation
linéaire. Celle-ci se détermine en fonction de la complexité des algorithmes susceptibles de
le résoudre exactement. Ces modèles peuvent ainsi être classés en deux catégories :
– ceux pour lesquels un algorithme de résolution exacte en temps polynomial est connu.
On parlera alors de problèmes faciles.
– ceux pour lesquels on ne connait pas d’algorithme de résolution exacte en temps poly-
nomial. On parlera alors de problèmes difficiles.
Parmi cette deuxième catégorie, les problèmes pour lesquels il ne peut pas exister d’algo-
rithme de résolution exacte en temps polynomial, à moins que la conjecture P =
6 N P ne soit
fausse, sont appelés NP difficiles.
Pour les problèmes en variables continues, le nombre de solutions admissibles est in-
fini lorsque leur domaine n’est pas vide. Heureusement, des résultats d’algèbre linéaire ont
montré que le domaine des solutions admissibles (ou espace de recherche) d’un programme
linéaire en variables continues est soit un polytope convexe (cas d’un domaine non borné),
soit un polyhèdre convexe (cas d’un domaine borné). De plus, si le domaine est borné et non
vide, la solution optimale est un sommet du domaine (ou une face s’il y a plusieurs solutions
optimales). Ainsi, l’algorithme du simplexe de G.B. Dantzig permet d’obtenir la solution
optimale d’un problème en parcourant la fermeture convexe de l’espace de recherche et ce en
passant de sommet en sommet. Malgré une complexité théorique dans le pire des cas expo-
nentielle, il permet de résoudre la plupart des problèmes rapidement. D’autres algorithmes
en temps polynomial ont été proposés pour résoudre ces problèmes. Certains peuvent ainsi
se révéler très compétitifs sur certains types de problèmes. La méthode du simplexe reste
malgré tout largement utilisée dans la pratique.
Pour les problèmes en variables discrètes, le nombre de solutions admissibles est fini
lorsque leur domaine est borné. Pourtant, le nombre de ces solutions grandissant généralement
de manière exponentielle (on parle d’explosion combinatoire), et la propriété de convexité du
domaine des solutions n’étant en général plus valable, la résolution de ces problèmes n’est
souvent pas aisée. Une exception existe lorsque la matrice des contraintes T est totalement
unimodulaire (c-à-d que tous les déterminants de ses sous-matrices carrées soient égaux à
−1, 0 ou 1). Tous les sommets du domaine des solutions admissibles de la relaxation linéaire
du problème sont alors entiers. Le problème peut donc être résolu comme un problème en va-
riables continues (et donc en temps polynomial, voir section 1.1.2.1). D’une manière générale,
la résolution de ces problèmes n’est cependant pas aisée. Beaucoup de ces problèmes sont
ainsi NP difficiles.
Dans le cas des problèmes en variables binaires, en plus des difficultés liées aux problèmes
en variables entières ou mixtes, la principale difficulté provient du grand nombre de variables
nécessaires pour modéliser des situations réelles. Cependant certains problèmes présentent
des structures particulières. Ils font partie d’un domaine appelé Optimisation Combinatoire.
Il est alors possible de tirer profit de l’information liée à cette structure pour faciliter leur
résolution.
Les méthodes de résolution exacte pour les problèmes en variables discrètes ou mixtes
sont nombreuses, cependant trois familles principales peuvent être distinguées :
– les méthodes dites par séparation et évaluation (Branch & Bound par exemple) con-
sistent à faire une énumération implicite en séparant le problème en sous-problèmes
(branchements) et en évaluant ceux-ci à l’aide d’une relaxation (continue ou lagran-
gienne principalement) jusqu’à ne plus avoir que des problèmes faciles à résoudre ou
dont on sait avec certitude qu’ils ne peuvent pas contenir de solution optimale,
Typiquement ce type de méthodes est particulièrement utile pour les problèmes nécessi-
tant une solution en temps réel (ou très court) ou pour résoudre des problèmes difficiles sur
des instances numériques de grande taille. Elles peuvent aussi être utilisées afin d’initialiser
une méthode exacte (Branch & Bound par exemple).
À côté des méthodes heuristiques, sont apparues des méthodes qualifiées de métaheuris-
tiques. Plusieurs définitions ont été proposées pour décrire leurs particularités par rapport
aux heuristiques. Osman et Laporte [OL96] (voir la définition 1.2) comparent une méta-
heuristique à un processus maı̂tre pilotant une heuristique (parfois même plusieurs) à l’aide
d’une stratégie permettant d’approcher la solution optimale de manière plus efficace.
2
du grec heuriskein = trouver
Cependant, cette définition ne fait pas clairement apparaı̂tre l’indépendance des méta-
heuristiques actuelles vis-à-vis des problèmes à traiter. Nous préférerons la définition de Pirlot
[Pir02] (définition 1.3) qui assimile les métaheuristiques à des stratégies de recherche. Ainsi,
il faut distinguer les heuristiques ciblées sur un problème particulier et les métaheuristiques
plus générales et adaptables pour résoudre un grand nombre de problèmes. Cependant, pour
être suffisamment performante sur un problème donné, une métaheuristique nécessitera une
adaptation intelligente aux caractéristiques de ce problème. Une même métaheuristique peut
d’ailleurs être à l’origine d’heuristiques différentes pour un même problème.
court chemin dans un graphe. Ce problème a été abondamment décrit dans de nombreux
ouvrages (par exemple celui de Faure [Fau91] ou de Gondran et Minoux [GM95]).
En outre, le problème du plus court chemin d’un sommet a à un sommet b peut aussi
être formulé avec le modèle mathématique suivant (équation 1.4) :
X
Min z(X) = ci,j xi,j
(i,j)∈E
X X
sc x i,a − xa,j = −1
−
i∈ΓG (a) +
j∈ΓG (a)
X X
x − xj,i = 0 , ∀j ∈ V \ {a, b} (1.4)
i,j
− +
i∈ΓG (j) i∈ΓG (j)
X X
xi,b − xb,j = 1
−
i∈ΓG (b) +
j∈ΓG (b)
xi,j ∈ {0, 1} , ∀(i, j) ∈ E
avec :
(
1 si l’arc (i, j) fait parti du chemin
– une matrice X = (xi,j ) telle que xi,j =
0 sinon
– une matrice C = (ci,j ) telle que ci,j = valuation de l’arc (i, j)
De manière surprenante pour un problème aussi classique et étudié, très peu d’applica-
tions pratiques modélisées par un problème de set packing sont présentées dans la littérature.
En fait, si des inégalités de type set packing apparaissent dans de nombreux problèmes, elles
ne permettent que rarement de représenter un problème à elles seules. Nous pouvons malgré
tout citer six applications pratiques récentes (indiquées par ordre chronologique) :
– Rönnqvist [Rön95] a travaillé sur un problème de cutting stock qu’il a formulé comme
un problème de set packing et résolu en utilisant une relaxation lagrangienne combinée
à une optimisation de sous-gradient,
– Zwaneveld et al. [ZKR+ 96, Zwa97, ZKVH01] ont formulé un problème de faisabilité de
passage de trains dans un nœud ferroviaire en problème de set packing et l’ont résolu
de manière exacte à l’aide de tests de réduction et d’un algorithme de Branch & Cut,
– Kim et Lee [KL97] ont représenté un problème d’ordonnancement de bateaux par un
set packing et ont utilisé le logiciel LINDO pour le résoudre,
– Mingozzi et al. [MMRB98] ont utilisé une formulation de type set packing afin de
calculer des bornes pour un problème d’ordonnancement de projet avec contraintes de
ressource (RCPSP) à l’aide d’un algorithme glouton,
– Rossi et Smriglio [RS01] ont considéré une formulation de type set packing pour un
Le problème de node packing est en fait un cas particulier du problème de set packing
dans lequel les sous-ensembles de Tj sont tous de cardinalité 2 (c-à-d que les contraintes
P
concernent uniquement des paires d’éléments, i∈I ti,j = 2, ∀j ∈ J).
Tous les problèmes de set packing peuvent être formulés en problèmes de node packing.
Pour cela, il suffit de substituer chaque contrainte par les contraintes entre toutes les paires
d’éléments apparaissant dans la contrainte initiale. Cependant, cette reformulation augmente
de manière importante le nombre de contraintes ; chaque contrainte concernant n éléments
est remplacée par Cn2 contraintes entre deux éléments. De plus, la relaxation linéaire du
problème ainsi obtenue est beaucoup plus faible que celle du problème initial.
mathématique de ce problème (équation 1.8) est très proche de celles des problèmes de set
packing et de set covering.
X
Min z(X) = ci xi
i∈I
X
sc ti,j xi = 1, ∀j ∈ J (1.8)
i∈I
xi ∈ {0, 1} , ∀i ∈ I
avec : (
1 si i ∈ P
– un vecteur X = (xi ) tel que xi =
0 sinon
– un vecteur C = (ci ) tel que ci = coût (de l’élément i
1 si i ∈ Tj
– une matrice T = (ti,j ) telle que ti,j =
0 sinon
Là encore, il est intéressant de noter que tout problème de set packing peut être exprimé
comme un problème de set partitioning en ajoutant des variables d’écarts xej de valeur nulle
dans chacune des contraintes (équation 1.9).
X X
Max z(X) = ci xi + 0 xej
i∈I j∈J
X
sc ti,j xi +xej = 1 , ∀j ∈ J
(1.9)
i∈I
xi ∈ {0, 1} , ∀i ∈ I
xej ∈ {0, 1} , ∀j ∈ J
On peut ensuite remplacer les variables artificielles xaj dans la fonction objectif :
X X X X X
ci xi + θxaj = ci xi + θ (1 − ti,j xi )
i∈I j∈J i∈I
X j∈J Xi∈IX
= ci xi + θ|J| − θ ti,j xi
i∈I
X X j∈J i∈I
= (ci − θ ti,j )xi + θ|J|
i∈I j∈J
Enfin, le fait de supprimer les variables artificielles xaj (équation 1.11) des contraintes
correspond à une relaxation du problème et augmente le domaine des solutions admissibles.
Mais cela ne change pas l’ensemble des solutions optimales grâce aux pénalités qu’il y a à ne
pas respecter une égalité.
X X
Min z(X) = (ci − θ ti,j )xi + θ|J|
i∈I j∈J
X
sc ti,j xi ≤ 1 , ∀j ∈ J (1.11)
i∈I
xi ∈ {0, 1} , ∀i ∈ I
Ce problème est basé sur la notion, courante dans les graphes, de clique (voir la définition
1.5).
Ce problème peut être formulé avec le modèle mathématique suivant (équation 1.12) :
X
Max z(X) = ci xi
i∈I
sc (1.12)
/E
xi + xj ≤ 1, ∀(i, j) ∈
xi ∈ {0, 1} , ∀i ∈ I
avec : (
1 si i ∈ C
– un vecteur X = (xi ) tel que xi =
0 sinon
– un vecteur C = (ci ) tel que ci = valeur du sommet i
Le problème de set packing est connu comme NP-difficile au sens fort d’après Garey et
Johnson [GJ79]. Ainsi, nous ne connaissons pas d’algorithme polynomial pour le résoudre
dans le cas général. Il existe cependant des cas particuliers. Ainsi, si la matrice des contraintes
T est totalement unimodulaire, il peut être résolu en temps polynomial. Par ailleurs, lorsque
la matrice des contraintes T contient au plus deux 1 par colonne et que toutes les valuations
P
sont unitaires ( j∈J ti,j ≤ 2, ∀i ∈ I et ci = 1, ∀i ∈ I, ce qui revient au calcul d’un ensemble
d’arrêtes indépendantes de cardinalité maximum), le problème peut être résolu en temps
polynomial d’après Garey et Johnson [GJ79]. Sakarovitch [Sak84], par exemple, présente
une méthode de marquage pour résoudre ce problème.
De plus, de nombreux travaux ont été réalisés sur sa structure particulière. Ainsi, les
travaux de Padberg sur les cliques et les cycles de longueur impaire [Pad73] ont initié de
nombreuses recherches liées à l’étude polyhédrale du problème de set packing. Borndörfer
[Bor98] recence un grand nombre de familles de facettes et d’inégalités valides spécifiques au
problème de set packing. En pratique pourtant, la détermination de l’ensemble de l’enveloppe
convexe est impossible à part pour des problèmes de petite taille. De ce fait, la meilleure
méthode connue actuellement pour résoudre exactement le problème de set packing est le
Branch & Cut. Deux implémentations de cette méthode ont été récemment proposées par
Borndörfer [Bor98] et Esö [Esö99] pour résoudre un problème de set partitioning en recher-
chant des familles de coupes spécifiques au problème de set packing.
Enfin, Nemhauser et Wolsey [NW99] indiquent une propriété très intéressante du problème
de set packing et plus particulièrement de sa formulation en problème de node packing. En
effet, nous avons vu dans la section 1.3.2.1 que tout problème de set packing peut être
formulé en un problème de node packing. Or lorsque la solution optimale de la relaxation
linéaire d’un problème de node packing contient des variables dont les valeurs sont entières,
ces valeurs font obligatoirement parties d’une solution optimale entière. Le lecteur intéressé
pourra trouver la démonstration de cette propriété dans l’ouvrage pré-cité. Cette dernière
peut se révéler très intéressante lorsque le nombre de variables entières dans la solution opti-
male de la relaxation linéaire est important. Cependant, cet intérêt est limité par le fait que
la relaxation linéaire d’un problème de set packing est souvent beaucoup plus forte que celle
de sa formulation en node packing. En effet, cette propriété ne s’applique pas au problème
de set packing.
– une matrice C = (cqi ) définissant les coefficients appliqués à chaque variable de décision
dans chaque fonction objectif z q (X),
– un ensemble de contraintes J = {1, . . . , m} représenté par une matrice T = (ti,j ),
– un ensemble (li ) (resp. (ui )) de bornes inférieures (resp. supérieures) sur les valeurs des
variables de décision.
Toute solution X définie dans l’espace de décision (IRn ) peut être projetée en un point
de l’espace des objectifs (IRp ). Bien évidemment, deux solutions différentes dans l’espace de
décision peuvent correspondre à un même point dans l’espace des objectifs. Ces solutions
seront appelées équivalentes.
La difficulté de ces problèmes vient du fait que, contrairement aux problèmes mono-
objectifs, il n’existe plus de relation d’ordre entre toutes les solutions admissibles et donc
plus de notion d’optimalité (à moins qu’une solution soit optimale pour toutes les fonctions
objectifs, ce qui est rarement le cas). Dans le cas des problèmes multiobjectifs, elles sont
remplacées par les notions de dominance et de Pareto optimalité (voir respectivement les
définitions 1.6 et 1.7) :
Une solution Pareto optimale est aussi appelée solution non-dominée. Nous ne parlerons
donc plus de solution optimale, mais d’un ensemble de solutions Pareto optimales (aussi
appelées solutions efficaces). L’ensemble des solutions efficaces est noté E. La projection
dans l’espace des objectifs de cet ensemble E décrit une frontière communément appelée
frontière efficace. En outre, deux points caractéristiques ne correspondant généralement à
aucune solution admissible sont aussi souvent utilisés :
– le point Idéal (z̄ q = maxX∈E z q (X) (resp. minX∈E z q (X) ), ∀q ∈ Q pour un problème
de maximisation (resp. minimisation)),
– et le point Nadir (η q = minX∈E z q (X) (resp. maxX∈E z q (X) ), ∀q ∈ Q pour un problème
de maximisation (resp. minimisation)).
De la même manière, les problèmes multiobjectifs peuvent être en variables mixtes (MO-
MILP), entières (MOILP), binaires (0-1MOILP) ou encore relever du domaine de l’Optimi-
sation Combinatoire (MOCO, Ehrgott et Gandibleux [EG02a] proposent une bibliographie
annotée spécifique à ces problèmes). Dans ce cas les solutions efficaces regroupent des solu-
tions dites supportées (correspondants aux sommets de la fermeture convexe de la frontière
efficace et notées SE), et des solutions non-supportées (n’appartenant pas à cette ferme-
ture convexe et notées NE). La figure 1.1 illustre ces différents points caractéristiques dans
l’espace des objectifs sur un exemple de problème de maximisation biobjectif.
Point supporté
z2
+ Point dominé
+
Point Idéal
+ Point Nadir
+
z1
Fig. 1.1 – Points caractéristiques d’un problème de maximisation biobjectif
La première catégorie regroupe des méthodes ramenant la résolution d’un problème mul-
tiobjectif à la résolution d’un (ou de plusieurs) problème(s) mono-objectif(s). Leur but est
de trouver une (ou plusieurs) solution(s) qui correspondra(ont) à un bon compromis entre
les différents objectifs en fonction des préférences exprimées par le décideur à l’aide des
paramètres. Ces méthodes peuvent être utilisées soit avec des paramètres fixés a priori,
soit de manière interactive en modifiant les paramètres durant la recherche. De nombreuses
méthodes peuvent entrer dans cette catégorie, nous en présentons ci-dessous quatre couram-
ment utilisées :
– Aggrégation des objectifs : une première méthode est d’aggréger les différents objectifs
en un seul. Pour cela il faut que tous les objectifs représentent des grandeurs d’unités
comparables. De plus, il est nécessaire de déterminer des poids respectifs pour chacun
de ces objectifs (notés λq , ∀q ∈ Q). Il est ainsi possible de se ramener à un problème
mono-objectif en faisant la somme pondérée des différents objectifs :
X X
zSomme pondérée = λq cqi xi
q∈Q i∈I
des objectifs. Pour cela, des poids sont affectés à chaque objectif (notés λq , ∀q ∈ Q),
et la somme pondérée des écarts en excès (notés d+ −
q ) comme en défaut (notés dq ) par
rapport aux valeurs cibles doit être minimisée. Le problème sera alors formulé de la
manière suivante (équation 1.14) :
X
Min zGoal Programming = λq (d+ −
q + dq )
q∈Q
sc X∈D
(1.14)
X q
ci xi + d− + bq , ∀q ∈ Q
q − dq = z
i∈I
d+ −
q , dq ≥ 0 , ∀q ∈ Q
La structure de la matrice des contraintes est alors cassée. La solution obtenue par une
résolution exacte de ce problème mono-objectif ne sera pas obligatoirement l’une des
solutions de E.
– Max-ordering : une quatrième méthode correspond au cas où il faut optimiser non pas
tous les objectifs, mais uniquement le moins bon. Dans ce cas, le problème reviendra à
optimiser l’objectif suivant pour un problème de maximisation (resp. minimisation) :
La structure de la matrice des contraintes est alors cassée. La solution obtenue par une
résolution exacte de ce problème mono-objectif ne sera pas obligatoirement l’une des
solutions de E.
La deuxième catégorie rassemble les méthodes déterminant l’ensemble complet des solu-
tions Pareto optimales du problème, ou plus souvent seulement l’ensemble minimum complet
(nom donné par Hansen [Han79] au sous-ensemble des solutions efficaces ne contenant pas
les solutions équivalentes). Ces méthodes permettent au décideur de sélectionner a poste-
riori la (ou les) solution(s) qui l’intéresse parmi l’ensemble des solutions efficaces. Différentes
méthodes peuvent être utilisées, nous présentons ci-dessous quatre méthodes courantes :
– la méthode en deux phases est un principe de résolution général applicable aux pro-
blèmes biobjectifs. Elle consiste à déterminer dans un premier temps l’ensemble SE
des solutions supportées, puis à rechercher l’ensemble des solutions non supportées (en-
semble NE) localisées dans les triangles définis par deux points supportés adjacents.
– la méthode du ranking est, elle aussi, applicable uniquement aux problèmes biobjec-
tifs. Elle consiste à rechercher l’ensemble des solutions situées entre le point Nadir et le
point Idéal. Ceux-ci sont obtenus en calculant les points extrèmes de la frontière efficace
(par deux résolutions lexicographiques successivement sur chaque objectif). Ensuite,
en partant de l’une des solutions extrèmes, la deuxième meilleure est cherchée, puis la
troisième, . . . puis la kième jusqu’à atteindre la valeur du point Nadir.
– la recherche dichotomique est, là encore, seulement applicable aux problèmes biobjec-
tifs. Elle consiste à effectuer une optimisation dans un sous-domaine de recherche borné
par deux solutions non dominées de références (initialement les deux points extrèmes)
pour trouver une autre solution efficace. Le sous-domaine est ainsi divisé en deux nou-
veaux sous-domaines jusqu’à ce que ceux-ci ne contiennent plus de solution efficace.
– la méthode -contrainte est valable quelque soit le nombre d’objectifs. Elle consiste à
optimiser le problème sur l’un des objectifs en bornant tous les autres objectifs, ce qui
revient pour l’objectif q ∈ Q d’un problème de maximisation à résoudre le problème
suivant (équation 1.15) :
q
Max z (X)
sc X∈D (1.15)
z q (X) ≥ qq0 , ∀q 0 ∈ Q \ {q}
0
Toutes ces méthodes font appel à de nombreuses résolutions exactes de problèmes mono-
objectifs (dont certains pour lesquels la structure de la matrice des contraintes est cassée) et
peuvent donc demander beaucoup de temps.
Une autre méthode parfois utilisée consiste à faire une recherche paramétrique sur la
somme pondérée des objectifs (la structure de la matrice des contraintes est donc conservée).
Cependant, cette technique présente l’inconvénient de ne permettre de trouver que les solu-
tions de SE ; cette méthode n’est donc valide que pour les problèmes pour dont toutes les
solutions efficaces sont supportées (E = SE). Pour les autres problèmes, cette méthode peut
cependant être utilisée pour obtenir un sous-ensemble de la frontière efficace.
1.5 Conclusion
Dans ce chapitre, nous avons présenté l’ensemble des notions de recherche opérationnelle
nécessaires à la compréhension du travail rapporté dans ce mémoire. Nous nous sommes
ainsi plus particulièrement intéressés à la modélisation linéaire des problèmes. De même, les
principales méthodes utilisées pour résoudre ces problèmes, de manière exacte ou approchée,
ont été indiquées. En particulier les différences, en terme de difficulté de résolution et de
technique employée, découlant du type de variables, du nombre d’objectifs ou encore de la
structure des problèmes, ont été mises en évidence.
En outre, nous avons décrit plus en détail deux problèmes classiques appelés plus court
chemin et set packing. Ainsi, si la résolution exacte du premier est facile, le second appartient
à la classe des problèmes NP difficiles. De plus, si de nombreux travaux ont exploré ses
propriétés dans le cadre d’une résolution exacte, sa résolution approchée n’a pour le moment
quasiment pas été étudiée.
Évaluation de la capacité
d’infrastructures ferroviaires
– une zone hétérogène correspond aux autres éléments d’une infrastructure. Une zone
englobant une zone hétérogène est forcément hétérogène aussi.
Nœud
{ Tronçon
Ligne
La marche d’un (ou plusieurs) train(s) sur une infrastructure donnée est habituellement
décrite à l’aide de deux modes de représentations principaux :
– le graphique de circulation représente par un trait l’évolution d’un train dans un gra-
phique où le temps et l’espace sont représentés de manière continue respectivement en
abscisse et en ordonnée. Il permet de donner une bonne vue de trains se succédant et
du sillon qu’ils occupent. Il est donc bien adapté pour la représentation d’un tronçon
ou d’une ligne. Par contre, il peut rendre difficile la visualisation des conflits dûs à
un croisement entre deux trains dans des nœuds complexes. La figure 2.3 en propose
un exemple correspondant à une situation comprenant quatre trains, dont deux se
succédent en batterie (t2 et t3). De plus, le train t4 circule dans l’autre sens et ralentit
au cours de la période observée. Les zones de détection et les deux parcours de l’in-
frastructure utilisés pour cet exemple sont représentés dans la figure 2.2. En outre, les
zones z2 et z3 appartiennent à un même canton.
– le diagramme de Gantt représente par des rectangles le temps d’occupation (et éven-
tuellement de réservation et de dégagement) d’un train sur les différentes zones de
détection d’une infrastructure dans un graphique où l’espace est représenté de manière
discrète (toujours en ordonnée). Il permet ainsi de visualiser tous les conflits de res-
sources liés à l’infrastructure. Même s’il est peu utilisé actuellement (voir Rodriguez
[Rod00b]), nous l’estimons donc plus adapté pour représenter un nœud. La figure 2.4
en propose un exemple correspondant à la même situation que la figure 2.3. Notons
dans cet exemple la synchronisation des dates de début d’occupation des zones z2 et
z3 puisqu’elles appartiennent à un même canton.
z4
Parcours
de t4
Parcours de z1 z2 z3 z5
t1, t2 et t3
Fig. 2.2 – Exemple d’infrastructure
Distance (m)
t1 t2 t3 t4
400 Temps minimum
de succession
300
200
100
0 t(s)
0 10 20 30 40 50 60 70 80 90 100 110 120 130
Fig. 2.3 – Exemple de graphique de circulation
Temps de
dégagement
z1 t1
z2 t2
z3 t3
z4 t4
Temps de
z5 réservation et
de dégagement
t(s)
0 10 20 30 40 50 60 70 80 90 100 110 120 130
Fig. 2.4 – Exemple de diagramme de Gantt
Tab. 2.1 – Niveaux de décisions en gestion prévisionnelle des modes de transport en commun
Pour mettre en œuvre une stratégie d’offre dans le cadre d’un processus de gestion ferro-
viaire prévisionnelle à long et moyen terme (planification et programmation), il est impératif
de se doter d’outils permettant de situer les limites d’un réseau (existant ou futur) par
rapport à une ou plusieurs offres possibles, et facilitant l’étude précise de chaque variante
capacité pratique quant à elle, tient compte d’une marge dite de souplesse afin d’éviter la
saturation totale et les retards en cascade en cas d’incident.
Une étude de capacité peut se faire sur l’ensemble des parties d’un réseau ferroviaire.
En fait, devant l’importance croissante que pourrait prendre le trafic entre les différents
pays européens, il pourrait même s’envisager sur plusieurs réseaux. Suivant la typologie de
l’infrastructure dont on cherche à évaluer la capacité, la difficulté de cette évaluation peut
énormément varier. Basiquement, la capacité C d’une voie ferroviaire dans un sens et pour
un intervalle de temps u donné est définie par l’expression théorique suivante (équation 2.1) :
u
C= (2.1)
h
1
Incluant des marges pour tenir compte des variations inévitables dans la pratique (tension électrique,
patinage des roues), du mécanicien (temps de réaction, conduite) et des normes de sécurité.
avec h le temps minimum de séparation entre deux trains successifs. Ce temps de séparation
dépend du système de signalisation installé sur la voie considérée. Des expressions plus
précises peuvent être utilisées pour considérer des situations plus complexes (voir la norme
UIC [U.I78]). De même, la capacité d’une zone homogène comme un tronçon peut être
facilement calculée en effectuant la somme des capacités des différentes voies parallèles qui
la composent
Par contre, l’additivité n’est plus applicable dès que l’on considère des zones hétérogènes.
Il n’est donc pas possible de calculer la capacité d’une ligne ou d’un nœud, et a fortiori d’un
réseau complet, en combinant à l’aide d’une fonction quelconque (comme le minimum ou le
maximum par exemple) les capacités des différents éléments qui la composent. Ainsi, il est
nécessaire de construire des modèles plus complexes. La capacité d’une jonction peut être
définie comme la solution d’un problème d’optimisation appelé «problème de saturation »
(voir la définition 2.3).
Plus généralement, une étude de capacité ne se résume pas à un seul problème d’optimi-
sation. En fait, parmi les autres questions souvent soulevées lors d’une analyse de capacité
ferroviaire, celles qui reviennent le plus souvent sont :
1. La capacité de l’infrastructure est-elle suffisante pour faire face aux évolutions de
l’offre ?
2. Quels sont les investissements offrant le meilleur débit pour les offres à venir ?
3. Quel est la meilleure façon de répondre à l’offre pour une infrastructure donnée ?
À la première question correspond un autre problème d’optimisation appelé «problème
de faisabilité » (voir la définition 2.4).
Enfin, la dernière question est encore plus large puisqu’elle correspond à la notion difficile
à définir de qualité de service. Elle couvre ainsi plusieurs problèmes d’optimisation du passage
des trains dans l’infrastructure. Cela concerne notamment l’optimisation des préférences
émises par le décideur en fonction des attentes supposées ou exprimées des usagers (voir la
définition 2.5).
Enfin, la stabilité d’un routage est une notion très importante soulevée par cette question.
Elle représente la capacité de ce routage à absorber les retards de certains trains. Une solu-
tion avec une ponctualité dégradée peut entraı̂ner un mécontentement des usagers et donc
une réduction de la demande. Cela peut ainsi rendre inutiles tous les efforts réalisés pour
augmenter l’offre. Il n’existe cependant pas de définition générale de la stabilité. S’il apparaı̂t
clairement qu’il peut exister une dépendance entre le niveau d’utilisation de la capacité (taux
de saturation) et la stabilité, il n’existe pas dans le cas général de corrélation négative entre
ces deux valeurs. La capacité maximale d’une infrastructure n’est pas forcément atteinte
lorsque la stabilité est minimale. Une façon (mais pas la seule) d’évaluer la stabilité d’un
routage est de calculer les retards générés sur les autres trains du routage par le retard d’un
ou plusieurs trains.
d’informations important.
Parmi ces catégories, les méthodes basées sur la construction d’horaires sont les seules à
permettre d’effectuer une évaluation de la capacité tout en garantissant l’existence de grilles
horaires correspondant aux valeurs calculées. Dans la suite nous nous intéressons donc aux
méthodes algorithmiques appartenant à cette catégorie. Nous présentons ainsi (par ordre
chronologique) trois méthodes développées dans le cadre de projets réalisés dans différents
pays européens.
2.4.1 DONS
Le projet DONS 2 a été développé par les chemins de fer néerlandais3 . Il a été présenté
initialement par Van den Berg et Odijk [vdBO94]. Zwaneveld [Zwa97] en a ensuite donné
une description plus complète. Son objectif est d’aider à planifier une ou plusieurs grille(s)
horaire(s) pour l’ensemble du réseau hollandais afin d’évaluer la capacité de différents projets
d’aménagement à absorber un trafic prévu.
Le résultat de ce projet est un logiciel comprenant une interface graphique et deux mo-
dules de calcul complémentaires. Le premier, appelé CADANS, tente d’établir une grille ho-
raire cadencée à une heure pour le réseau complet, alors que le deuxième, appelé STATIONS,
aide à résoudre les problèmes de routage dans chaque gare afin de vérifier la faisabilité de
la grille horaire (dates d’arrivée et de départ de chaque train) proposée par CADANS. Dans
le cas où le routage de tous les trains ne peut pas être réalisé par STATIONS, il met en
évidence les trains bloquants pour que CADANS génère une autre grille horaire. Lorsque
CADANS ne parvient pas à trouver de grille horaire, de nouveaux projets d’aménagements
doivent être intégrés ou les estimations de trafic doivent être revues à la baisse.
2.4.1.1 CADANS
L’objectif du module CADANS est de déterminer une grille horaire cadencée à une heure
pour l’ensemble du réseau. Cette grille horaire doit être réalisable uniquement en dehors des
gares. Par contre, elle peut ne pas être réalisable dans l’une des gares du réseau. Elle ne
prend donc en compte que les lignes situées entre ces gares.
Une grille horaire est caractérisée par les dates d’arrivées et de départs des trains dans
chaque gare. Les variables de décisions entières xt,s considérées représentent donc la date de
départ du train t depuis la gare s. Les dates d’arrivée peuvent ensuite être déduites car le
temps passé dans la gare est supposé constant. Ces variables sont soumises à trois familles
de contraintes :
2
Design Of Network Schedules
3
Nederlandse Spoorwegen (NS)
– sur les temps de parcours, l’écart entre les dates de départ d’un train pour deux gares
successives où il doit passer devant être cohérent avec le temps de parcours entre ces
deux gares et le temps d’arrêt prévu dans la deuxième gare,
– pour les connexions entre certaines paires de trains, les temps de présence au quai de
deux trains dans une même gare devant être suffisamment proches pour permettre une
correspondance lorsqu’il y a lieu,
– et sur l’utilisation de l’infrastructure, deux trains utilisant une même partie de l’infra-
structure devant le faire avec un temps d’écart suffisant.
Toutes ces contraintes peuvent être exprimées sous la forme générale suivante (équation 2.2) :
De nombreuses approches ont été considérées pour résoudre ce modèle (Lindner [Lin00]
présente les principales). Ces méthodes font appel à des techniques très diverses :
– programmation par contraintes,
– algorithme de Branch & Bound après une reformulation en un MILP,
– méthode de coupes.
La plupart des instances de ce problème sont ainsi résolues dans des temps raisonnables. Il
existe cependant encore des cas de figure où la résolution exacte de ce problème n’est pas
possible.
2.4.1.2 STATIONS
L’objectif des travaux autour de STATIONS, présentés par Zwaneveld et al. [ZKR+ 96,
Zwa97, ZKVH01] et par Kroon et al. [KRZ97], est de réaliser le routage d’un nombre maxi-
mum de trains dans un nœud ferroviaire sur une période de temps donnée. Le fait de chercher
un routage valide pour un nombre maximum de trains et non directement pour tous les trains
permet d’identifier un sous-ensemble de trains bloquants lorsque le routage de tous les trains
n’est pas possible.
Dans cette étude, un nœud ferroviaire est caractérisé par un certain nombre de points
d’entrée, de quais et de points de sortie. Un train parcourant ce nœud emprunte donc un
itinéraire d’entrée, composé de plusieurs sections, depuis son point d’entrée (dépendant de
la provenance du train) jusqu’à un quai. Puis, il emprunte un itinéraire de sortie de ce quai
Ainsi, ce problème est modélisé en considérant l’ensemble des trains T , l’ensemble des
5
itinéraires R (l’ensemble Rt ∈ R représentant
( les itinéraires possibles pour un train t ∈ T ) et
1 si le train t ∈ T utilise l0 itinéraire r ∈ Rt
l’ensemble des variables de décision xt,r = .
0 dans les autres cas
L’ensemble Ft,t0 contient toutes les combinaisons d’itinéraires possibles pour deux trains t et
t0 . Il peut donc se formuler comme le problème en variables binaires suivant (2.3) :
XX
Max z(X) = xt,r
t∈T r∈Rt
X
xt,r ≤ 1 , ∀t ∈ T (a)
(2.3)
r∈Rt
x + x ≤ 1 , ∀(t, t0
) ∈ T 2
, r ∈ R , r 0
∈ R , (r, r 0
) ∈
/ F (b)
t,r 0
t ,r 0 t t0 t,t0
xt,r ∈ {0, 1} , ∀t ∈ T, r ∈ Rt
où les contraintes (a) modélisent le fait qu’un train ne peut prendre qu’un seul parcours et
les contraintes (b) le fait que le passage de deux trains sur deux parcours non compatibles
ne peut pas être réalisé en même temps. C’est donc un problème de set packing.
Deux extensions ont aussi été proposées. La première permet d’autoriser un léger décalage
des horaires d’arrivée et de départ des trains. Ces deux décalages sont exprimés par une
déviation δ = (δa , δd ). Ainsi, l’ensemble Ft,t0 contient toutes les combinaisons d’itinéraires-
déviations possibles pour les trains t et t0 , et Rt les itinéraires-déviations possibles pour le
train t.
4
La décomposition des itinéraires en itinéraires d’entrée et en itinéraires de sortie permet ainsi de modéliser
le couplage ou le découplage de certains trains.
5
La décomposition des itinéraires permet donc ainsi de diminuer le nombre d’itinéraires : si un train a
respectivement n1 et n2 itinéraires d’entrée et de sortie et |P | quais possibles, le nombre d’itinéraires complets
possibles passera de n1 ∗ n2 ∗ |P | à (n1 + n2 ) ∗ |P |.
La seconde permet d’exprimer les préférences de certains trains pour un itinéraire par-
ticulier, comme par exemple des choix de quais pour des correspondances ou des raisons de
convenance des usagers qui préfèrent qu’un même type de train parte toujours du même
quai. Dans ce cas, seule la fonction économique du modèle est modifiée par l’introduction
d’un paramètre ρt,r qui vient pondérer les différentes variables xt,r .
La méthode utilisée pour résoudre de manière exacte ce problème pour une grille horaire
cadencée à l’heure est composée de trois phases :
1. L’initialisation sert à déterminer toutes les variables (itinéraires pour un train) ainsi que
les itinéraires compatibles. Pour cela, les seules sections considérées sont celles conte-
nant un aiguillage, une intersection, un point d’entrée, un quai ou un point de sortie.
Ce choix de ne considérer que les sections dites déterminantes pour détecter les conflits
potentiels n’est valide que sous des hypothèses très fortes. Il suppose notamment que
les infrastructures étudiées ne contiennent aucune voie banalisée et qu’aucun croise-
ment n’a lieu. De même, il requiert l’hypothèse d’égalité des temps de parcours évoquée
précédemment, et exclue les cas de dépassement d’un train par un autre dans le nœud.
Cette dernière hypothèse s’avère surtout restrictive lorsque le trafic est hétérogène et
comprend des trains circulant à des vitesses très différentes.
2. Une phase de réduction utilise successivement un test sur la pertinence des variables
puis quatre autres tests valides pour tout problème de node packing 6 :
(a) «Detour routes» supprimant les variables dont l’itinéraire correspond à un détour
par rapport à un autre itinéraire possible,
(b) «Node dominance» supprimant les variables dominées par une autre,
(c) «Combining nodes» combinant des couples de variables en une seule si la sélection
de l’une dans une solution optimale entraı̂ne la sélection de l’autre,
(d) «Set dominance» supprimant des variables dominées par un ensemble de va-
riables,
(e) «Iterative set dominance» supprimant des ensembles de variables dominé par un
autre ensemble.
Ces tests de réduction permettent de diminuer très fortement la taille des problèmes
considérés. Ainsi, dans les résultats rapportés, le nombre de variables des problèmes
est ramené en moyenne à 7.7% du nombre initial de variables. Les trois premiers tests
sont les plus efficaces (de très loin, surtout pour les deux premiers).
6
Ils utilisent pour cela la transformation du problème de set packing en node packing décrite à la section
1.3.2.1 (page 15)
3. Un algorithme de Branch & Cut résout le problème en utilisant une relaxation linéaire
et en ajoutant des cliques spécifiques. Cependant, celui-ci pouvant nécessiter un temps
important, le problème à résoudre ne doit plus être de trop grande taille.
2.4.2 CAPRES
Le projet CAPRES 7 a été développé par les chemins de fer suisses8 . Il est basé sur les
travaux d’Hachemane [Hac97]. Le logiciel résultant, décrit par Curchod et Lucchini [CL01],
est aussi utilisé dans d’autres pays et notamment en France pour certaines études menées
par la SNCF. Son objectif est de fournir un système d’aide à l’évaluation de la capacité
d’infrastructures complexes (réseaux) par construction d’horaires. Pour cela, il traite les
deux problèmes suivants :
1. élaborer des variantes d’horaires (c-à-d d’ordonnancement et non pas de grille horaire)
cadencées d’un ensemble de trains permettant de les faire circuler dans l’infrastructure
étudiée,
2. mesurer la capacité de cette infrastructure en saturant une de ces variantes avec des
trains supplémentaires.
La partie du réseau étudiée est représentée sous forme de nœuds et de tronçons. Les
nœuds peuvent être modélisés selon trois niveaux de détail différents : conflits dans le nœud
non pris en compte par le modèle, conflits de cisaillement uniquement pris en compte, conflits
de cisaillement et d’attribution des quais pris en compte. Les contraintes à respecter dans la
construction de l’horaire peuvent être rangées en deux catégories :
– Les contraintes dites potentielles modélisent les intervalles horaires imposés aux trains,
leurs temps de parcours, leurs durées d’arrêt et leurs correspondances. Elles expriment
le fait qu’un événement B doit se produire dans une fourchette de temps dépendant
d’un autre événement A. Il s’agit en fait de contraintes de localisation d’un événement
par rapport à un autre exprimés par les deux inégalités de potentiel suivantes (équation
2.4) :
hA + t− ≤ hB et hB ≤ hA + t+ (2.4)
hB ≥ hA + t+ OU hB ≤ hA − t− (2.5)
7
système d’aide à l’analyse de la CAPacité des RÉSeaux ferroviaires
8
Chemins de Fer Fédéraux suisses (CFF)
Ces contraintes sont en fait très proches de celles exprimées dans le modèle CADANS décrit
dans la section 2.4.1.1.
La résolution utilisée s’inspire directement des travaux de Fukumori et Sano [FS87]. Elle
se base sur des méthodes de propagation des contraintes potentielles. L’algorithme effectue
sa recherche en branchant sur les contraintes disjonctives. Il peut ainsi positionner tous les
trains en commençant par les plus contraints. Pour le problème de saturation, le même
algorithme est utilisé de manière itérative en introduisant successivement les trains (seuls ou
par groupes selon la stratégie utilisée) de la liste saturante ordonnée.
2.4.3 DÉMIURGE
Le projet DÉMIURGE est actuellement développé par les chemins de fer français9 . Il
est encore à l’état de prototype et a, pour le moment, été uniquement présenté de manière
succinte par Labouisse et Djellab [LD01, LD02]. Son objectif est de mettre au point un outil
d’aide à la décision permettant de mesurer et d’optimiser la capacité de toutes les parties
d’un réseau (pour le moment les grandes lignes). Cet outil serait commun à tous les services
de la SNCF, et devrait donc remplacer l’utilisation du logiciel CAPRES. Il doit notamment
permettre de considérer les points suivants :
– vérifier dans quelle mesure le réseau actuel peut absorber l’accroissement prévu de
différents types de trafic,
– identifier les points bloquants du réseau,
– évaluer différentes hypothèses d’investissements pour modifier l’infrastructure au ni-
veau des points bloquants,
– et optimiser les grilles horaires.
La partie du réseau étudiée est représentée sous forme de nœuds et de tronçons. Là
encore, les trois niveaux de détail utilisés pour les nœuds dans CAPRES (voir la section 2.4.2)
peuvent être considérés. Les trains considérés sont, eux, répartis en trois catégories : ceux de
l’horaire de base, ceux demandés à court ou moyen terme et ceux demandés à long terme.
Les variables de décision utilisées sont les heures d’arrivée et de départ de ces trains dans les
nœuds. Les valeurs possibles de ces variables sont définies par des contraintes techniques liées
à l’infrastructure telles que l’espacement entre les trains successifs ou le temps de séparation
entre des trains utilisant des itinéraires incompatibles, et par des contraintes commerciales
comme les parcours et les horaires des trains, les temps d’arrêt en gare, le cadencement ou
encore les correspondances. La solution recherchée pour le MILP ainsi modélisé peut alors
optimiser différents critères :
9
SNCF
La résolution est effectuée à l’aide du logiciel commercial Cplex (basé sur une résolution
de type Branch & Cut). L’ajout de pré-traitements et la recherche de coupes a ainsi permis
d’obtenir des résultats dans des temps satisfaisants pour les cas de figures testés. Cepen-
dant, une méthode de résolution par décomposition est actuellement envisagée. De plus,
plusieurs autres améliorations (principalement pour optimiser le routage des trains et pour
évaluer la robustesse des grilles horaires vis-à-vis de petits aléas d’exploitation) pourraient
être développées.
Tout d’abord, si ces projets considèrent tous le problème de la capacité ferroviaire, ils
ne traitent pas toujours le même champ de questions. S’ils permettent tous de répondre au
problème de faisabilité, les problèmes de saturation et surtout d’optimisation des préférences
et de fluidification ne sont pas toujours considérés. En outre, hormis CAPRES, ils considèrent
ces problèmes de manière indépendante et non pas selon une approche multiobjectif. De
plus, la notion de stabilité n’est jamais traitée à l’intérieur de ces projets. Ils renvoient ainsi
l’utilisateur vers des méthodes de simulation pour effectuer cette évaluation10 .
Ensuite, chacun de ces projets a été réalisé dans une logique liée aux contraintes d’ex-
ploitation propres au pays où il a été développé. Le type d’horaire considéré est ainsi ca-
ractéristique. L’utilisation plus rare, jusqu’à maintenant, en France d’horaires cadencés a
amené la SNCF à ne considérer cela que comme une possibilité.
Enfin, la diversité des méthodes de résolution considérées montrent bien la difficulté de
ces problèmes. Notons à ce sujet que les problèmes traités étant fort contraints, l’utilisation
de méthodes de propagations de contraintes ou basées sur des ajouts de coupes semblent
plus performantes. Bien évidemment, la pertinence des résultats (et les temps de réponse)
de ces méthodes (et la faisabilité réelle des grilles horaires construites) dépendra grandement
de la précision des données fournies en entrée. Ceci peut parfois amener à représenter les
nœuds d’un réseau d’une manière trop simplifiée. L’approche du projet DONS est dans cette
optique très intéressante, puisqu’elle décompose le problème, ce qui permet de traiter à part
le cas des gares.
2.5 Conclusion
Dans ce chapitre, nous avons présenté la problématique d’une étude de capacité d’infra-
structures ferroviaires. Après avoir indiqué son positionnement dans le cadre des problèmes
de transport ferroviaire, nous avons montré son importance dans le contexte actuel. De plus,
nous avons vu que de nombreuses questions, et donc de nombreux problèmes, se posent
lors de ce type d’étude. Dans notre cas, nous nous intéressons plus particulièrement aux
problèmes de faisabilité, de saturation, d’optimisation des préférences et à la stabilité des
routages correspondants, pour des infrastructures à l’échelle d’un nœud ou d’une gare.
Pour répondre à ces questions, de nombreuses méthodes sont possibles pour des in-
frastructures simples, mais la combinatoire induite par la complexité de certaines infra-
structures comme les nœuds rend nécessaire l’utilisation de méthodes algorithmiques. Parmi
celles existantes à l’heure actuelle, aucune ne répond complètement au champ de questions
nous intéressant, et aucune à la question de la stabilité. De même, l’aspect multiobjectif
du problème n’est jamais envisagé. En outre, une seule de ces méthodes considère l’échelle
10
L’évaluation s’effectue alors habituellement en observant les effets d’une ou plusieurs perturbations sur
la grille horaire
d’un nœud, mais retient des hypothèses trop fortes pour des nœuds complexes comprenant
des voies banalisées et accueillant un trafic hétérogène. Les autres, elles, s’intéressent à des
échelles plus macroscopiques et représentent les nœuds de façon trop simplifiée pour garantir
la faisabilité des grilles horaires générées.
Dans la suite, nous allons donc développer la modélisation linéaire, puis les méthodes
de résolution, que nous proposons pour traiter complètement le problème considéré. Nous
verrons notamment comment nous pouvons considérer un niveau de détail plus approprié à
une infrastructure telle qu’un nœud complexe. De plus, nous montrerons de qu’elle manière
l’évaluation de la stabilité des grilles horaires générées peut être intégrée dans ce modèle.
Après avoir présenté notre problème, nous allons maintenant développer dans ce chapitre
les différents éléments de la modélisation que nous proposons. En effet, aucune des méthodes
présentées dans le chapitre précédent ne répond complétement à nos attentes, notamment à
cause de l’échelle considérée et des questions traitées. Cette modélisation s’inspire cependant
des travaux réalisés par Zwaneveld et al. [ZKR+ 96, Zwa97, ZKVH01] dans le cadre du projet
STATIONS (voir la section 2.4.1.2) qui considérait une échelle équivalente. Avant de la
présenter, il est nécessaire d’introduire quelques notations et définitions. Ensuite, nous nous
intéresserons aux problèmes, décrits dans la section 2.3 (page 33), de faisabilité, de saturation
et d’optimisation des préférences d’une grille horaire, puis à l’évaluation de la stabilité des
solutions obtenues.
TF ais ⊆ T
TSat = T \ TF ais
q
TSat Sous-ensemble des trains saturants de type q ∈ T ypes :
[ q
\ q
TSat = TSat , TSat =∅
q∈T ypes q∈T ypes
TCycle Sous-ensemble des trains devant effectuer leur parcours de manière cyclique ou
cadencée avant et après l’horizon temporel du scénario :
TCycle ⊆ T
TCoupl ⊂ T
La fonction fCoupl (t) : TCoupl → T associe à chaque train t devant être couplé,
le train auquel il se couple.
TDecoupl Sous-ensemble des trains devant être découplés d’un autre train :
TDecoupl ⊂ T
Hypothèse 3.1
Les marches des trains associées à chacun des parcours considérés correspondent à des
marches types pré-définies (par exemple des marches en voie libre) et indépendantes des
autres trains ou de l’horaire.
Ainsi par exemple, le parcours d’un train dans une gare peut être séparé en une route
d’entrée, un arrêt au quai et une route de sortie. En notant a (resp. c) le nombre de routes
d’entrée (resp. de sortie) et b le nombre de quais possibles, on obtient a + b + c itinéraires
en partitionnant les parcours au lieu de a ∗ b ∗ c parcours (si toutes les combinaisons sont
possibles). Notons que pour un parcours partitionné, toutes les combinaisons d’itinéraires
physiquement compatibles sont possibles.
0 0
En outre, la fonction fCoupl (t) : TCoupl → IfCoupl (t) (resp. fDecoupl(t) : TDecoupl → IfDecoupl (t) )
associe à chaque train devant être couplé (resp. découplé) à un autre train, la partition du
parcours de cet autre train sur laquelle le couplage (resp. découplage) a lieu.
Hypothèse 3.2
Les horaires possibles pour chacun des trains considérés correspondent à un ensemble discret
pré-défini d’horaires compatibles avec :
– les disponibilités en matériel roulant et en personnel,
Certains couples de trains peuvent aussi être mis en correspondances. Les éléments ci-
dessous définissent ces horaires :
Ht Horaire de référence du train t ∈ T . Dans le cas où les parcours de t ne sont
pas partitionnés (|It | = 1) et que t traverse le nœud, Ht correspond à l’heure
d’arrivée du train dans le nœud. Dans les autres cas (|It | > 1), Ht est un
|I |−1
(|It | − 1)-uplet (Ht1 , . . . , Ht t ) qui correspond aux dates d’intersections entre
les partitions. Par exemple, pour des parcours en trois parties (route d’entrée,
arrêt au quai, route de sortie) Ht représente les heures d’arrêt et de redémarrage
du quai.
corrt,r,t0 ,r0 Temps minimum requis pour la correspondance du train t ∈ T arrêté au quai
r ∈ Rt,i (avec i ∈ It ) vers le train t0 ∈ T arrêté au quai r 0 ∈ Rt0 ,i0 (avec i0 ∈ It0 ).
Une valeur du paramètre corrt,r,t0 ,r0 supérieure à la durée de l’horizon temporel
(c-à-d corrt,r,t0 ,r0 ≥ (f in − debut)) signifie que la correspondance du train t vers
le train t0 ne doit pas se faire entre les quais r et r 0 .
Par définition, les horaires de référence et les décalages temporels de tous les trains sont
dans l’horizon temporel défini par les horaires de début et de fin du scenario.
Toutes ces définitions correspondent au cas de figure classique où les trains entrent et
sortent de l’infrastructure par les itinéraires prévus (ou alors sont présents depuis le début
du scénario ou jusqu’à la fin). Si un train t doit «disparaı̂tre» de (resp. «apparaı̂tre» dans)
|I |
l’infrastructure au cours du scénario, une composante supplémentaire Ht t (resp. Ht0) doit
être ajoutée à l’horaire de référence Ht pour indiquer l’horaire de cet événement. De même,
une composante δ|It | (resp. δ0 ) doit être ajoutée à l’ensemble des décalages temporels ∆t
autorisés. Cette particularité sert essentiellement lors du couplage ou du découplage de deux
trains (voir section 3.2.2.7).
haz,t,r,δ Heure à partir de laquelle la zone z ∈ Zones est utilisée par le train t ∈ T
empruntant l’itinéraire r ∈ Rt,i (avec i ∈ It ) avec un décalage temporel δ ∈ ∆t .
Cette utilisation peut être soit physique (présence sur la zone), soit «logique»
(respect des règles de sécurité et d’espacement entre les trains induites par
le cantonnement de l’infrastructure et sa signalisation). Elle correspond à un
parcours en voie libre du train, et peut être déterminée soit par des relevés de
terrain, soit par une simulation.
hdz,t,r,δ Heure à partir de laquelle la zone z ∈ Zones n’est plus utilisée par le train
t ∈ T empruntant l’itinéraire r ∈ Rt,i (avec i ∈ It ) avec un décalage temporel
δ ∈ ∆t et est donc disponible pour d’autres trains.
À la différence des horaires de références, les heures d’utilisation des zones peuvent être
en dehors de l’horizon temporel du scénario afin de modéliser le routage complet du parcours
du train.
Le diagramme de Gantt de la figure 3.1 présente un exemple d’utilisation des zones
dépassant l’horaire de fin du scénario par un train s’arrêtant sur un quai en cul-de-sac.
Réservation
z1 et entrée Sortie
Arrêt
z2 au quai
z3 Ht1 Ht2
z4
(Quai)
t(s)
485 495 505 515 525 535 545 555 565 575 585 595 605 615
haz4,t,r,δ hdz4,t,r,δ f in
Fig. 3.1 – Utilisation des zones
En outre, le décideur peut définir une pondération wt,r,δ ∈ IN pour chacune des variables
xt,r,δ . Celle-ci est utilisée dans le cadre du problème d’optimisation des préférences (voir la
section 3.2.1.3).
3.2.1.1 Faisabilité
Le premier objectif de notre problème (équation 3.2) consiste à faire circuler un nombre
maximum de trains de la grille horaire initiale. Il correspond au problème de faisabilité
(voir la définition 2.4, page 35). Les parcours étant partitionnés, cet objectif correspond à
la somme, pondérée en fonction du nombre de partitions, des variables représentant un des
trains de cette grille horaire. En effet, lorsque le parcours d’un train est partitionné, une
variable associée à ce train ne représente que son affectation à un itinéraire et non pas à un
parcours complet.
X 1
max zF ais = xt,r,δ (3.2)
t∈TF ais ,i∈It ,r∈Rt,i ,δ∈∆t
|It |
Ainsi, par exemple, pour un train dont le parcours est partitionné en une route d’entrée,
un arrêt au quai et une route de sortie (|It | = 3), une variable représentant un itinéraire
possible pour la route d’entrée de ce train aura une pondération d’ 31 dans la fonction objec-
tif. Cela signifie que la sélection de cette seule variable ne permet pas d’assurer le routage
complet du train. Pour que le train soit routé entièrement, il faut aussi que deux autres
variables représentant ce train soit sélectionnées.
3.2.1.2 Saturation
Ensuite, nous avons une famille d’objectifs (équation 3.3) correspondant au problème
de saturation (voir la définition 2.3, page 35) pour chacune des catégories de trains. Pour
chaque catégorie, il s’agit de maximiser le nombre de trains sélectionnés dans la solution. Le
principe est le même que pour l’objectif de faisabilité mais concerne les trains contenus dans
les listes saturantes.
q
X 1
max zSat = xt,r,δ , ∀q ∈ T ypes (3.3)
q |It |
t∈TSat ,i∈It ,r∈Rt,i ,δ∈∆t
Dans le cas général, il n’y a pas de priorité fixée a priori entre ces objectifs de saturation.
Pour exprimer la capacité dans une autre unité que le nombre de trains par unités de
temps (voir section 2.3, page 33), un coefficient multiplicateur représentant la quantité as-
sociée à chaque train peut être intégré dans les équations 3.2 et 3.3.
Enfin, le dernier objectif (équation 3.4) correspond au problème d’optimisation des pré-
férences (voir la définition 2.5, page 36) émises par le décideur. Il s’agit de maximiser la
somme, pondérée en fonction du nombre de partitions et de ces préférences, de l’ensemble
des variables du problème (c-à-d tous les trains de la grille horaire et des listes saturantes).
Ce niveau de préférence peut éventuellement être aussi utilisé pour modéliser une capacité
exprimée dans une autre unité que le nombre de trains (voir la section 2.3). Dans ce cas wt,r,δ
représentera l’apport du train t vis-à-vis de cette unité.
X 1
max zP ref = wt,r,δ xt,r,δ (3.4)
|It |
t∈T,i∈It ,r∈Rt,i ,δ∈∆t
Là encore, il n’y a pas de priorité fixée a priori entre cet objectif et ceux de saturation
(équation 3.3).
Une première famille de contraintes permet de s’assurer qu’un parcours unique est choisi
pour chacun des trains sur une même partition (équation 3.5). En effet, plusieurs variables
du modèle correspondent aux différents itinéraires et décalages temporels de ce train. Une
seule de ces variables peut être sélectionnée dans une solution.
X
xt,r,δ ≤ 1, ∀t ∈ T, ∀i ∈ It (3.5)
r∈Rt,i ,δ∈∆t
Une deuxième famille permet de s’assurer du respect des règles de sécurité liées à l’utili-
sation des zones (équation 3.6). La plupart des zones sont des ressources unaires. Ainsi, deux
trains différents ne peuvent pas utiliser en même temps une même zone.
xt,r,δ + xt0 ,r0 ,δ0 ≤ 1, ∀t, t0 ∈ T 2 , t 6= t0 , ∀i, i0 ∈ It × It0 , ∀r, r 0 ∈ Rt,i × Rt0 ,i0 , ∀δ, δ 0 ∈ ∆t × ∆t0
, ∃z ∈ Zones, [haz,t,r,δ , hdz,t,r,δ ] ∩ [haz,t0 ,r0 ,δ0 , hdz,t0 ,r0,δ0 ] 6= ∅
(3.6)
Le diagramme de Gantt de la figure 3.2 présente le passage de deux trains t1 et t2 sur
quatres zones (z1, z2, z3 et z4). Ces deux trains sont en conflit puisqu’ils utilisent la zone z3
au même moment ([haz3,t1,r,δ , hdz3,t1,r,δ ] ∩ [haz3,t2,r0 ,δ0 , hdz,t2,r0 ,δ0 ] = [45, 60] 6= ∅).
Pour les problèmes cadencés, cette vérification doit être faite pour les cycles précédent et
suivant des trains cadencés (équation 3.7).
z1 CONFLIT t1
z2 t2
z3
z4
t(s)
0 10 20 30 40 50 60 70 80 90 100 110 120 130
Fig. 3.2 – Conflit entre deux trains sur une zone
Horizon temporel
z1
z2
z3
t(min)
−60−50−40−30−20−10 0 10 20 30 40 50 60 70 80 90 100 110
debut f in
Fig. 3.3 – Cadencement d’un train
alors cette zone pendant tout le temps de son arrêt. Les contraintes concernant l’utilisation
de ces zones sont donc celles définies dans la section 3.2.2.2.
Hypothèse 3.3
La place occupée dans un quai est uniquement considérée en nombre de trains pouvant être
accueillis en même temps sur ce quai, et non pas en fonction de la longueur réelle de ces
trains.
De plus, afin de gérer l’ordre d’arrivée et de départ des trains sur ce quai (le dépassement
de train par un autre n’étant pas possible sur le quai), le train utilisera aussi pendant une
durée forfaitaire (dans notre cas nous avons considéré une durée d’une seconde) les autres
zones fictives qu’il traversera. La date de début d’utilisation de toutes les zones traversées lors
de l’arrivée sera la date de début d’utilisation de la zone d’arrêt, et la date de fin d’utilisation
de toutes les zones traversées lors du départ sera la date de fin d’utilisation de la zone d’arrêt.
Il faut distinguer deux cas :
– pour les quais au passage, le train traverse les zones précédant la zone d’arrêt lors de
son arrivée et les zones suivantes lors de son départ. On obtient ainsi un comportement
de type FIFO (premier entrée, premier sorti). La figure 3.4 représente le diagramme
de Gantt d’un exemple dans lequel un train s’arrête sur la deuxième des trois zones
fictives (z1, z2 et z3) d’un quai au passage. Dans ce cas, il traversera la zone z1 lors de
son arrivée et la zone z3 lors de son départ.
– pour les quais en cul-de-sac, le train traverse les zones précédant la zone d’arrêt lors
de son arrivée et retraverse les même zones lors de son départ (dans ce cas, certaines
zones peuvent ne pas être traversées). On obtient ainsi un comportement de type LIFO
(dernier entrée, premier sorti). La figure 3.5 représente le diagramme de Gantt d’un
exemple dans lequel un train s’arrête sur la dernière des trois zones fictives (z1, z2 et
z3) d’un quai en cul-de-sac. Dans ce cas, il traversera les zones z1 et z2 lors de son
arrivée et de son départ.
arrivée
z1
Quai z2
z3
t(s)
départ
0 5 10 15 20 25 30 35 40 45 50 55
Fig. 3.4 – Quai au passage
arrivée
départ
z1
Quai z2
z3
t(s)
0 5 10 15 20 25 30 35 40 45 50 55
Fig. 3.5 – Quai en cul-de-sac
Une cinquième famille permet de s’assurer du respect des temps minimums requis pour
les correspondances (équation 3.10).
Nous avons décidé de ne pas permettre de demander une correspondance entre deux
trains saturants dans notre modèle. En effet, les futurs utilisateurs de ce modèle estiment
que cela ne présente pas d’intérêt en pratique. Dans le cas où une correspondance implique-
rait un train t traversant le nœud dans sa première (resp. dernière) partition, on considérera
|I |
que Ht0 = debut (resp. Ht t = f in) et que δ0 = 0 (resp. δ|It | = 0), ∀δ ∈ ∆t .
z1
(Quai)
.. 1
Ht2 2
Ht2
.
z2
(Quai)
t(s)
0 10 20 30 40 50 60 70 80 90 100 110 120 130
Fig. 3.6 – Correspondance entre deux trains
0
xt,r,δ + xt0 ,r0 ,δ0 ≤ 1, ∀t ∈ TCoupl , t0 = fCoupl (t), i0 = fCoupl (t)
, ∀r, r 0 ∈ Rt,|It | × Rt0 ,i0 , ∀δ, δ 0 ∈ ∆t × ∆t0
, (r, r 0 zones de quai fictives non successives) (3.11)
|I |−1 0
/ [Hti0 −1 + δi0 −1 ; Hti0 + δi0 − couplt,t0 ])
0
ou (Ht t + δ|It |−1 ∈
|I | 0
ou (Ht t + δ|It | 6= Hti0 + δi0 )
arrivée
t1
départ Temps disponible pour le
couplage de t1 à t2 t2
1 2
Ht1 Ht1
Quai z1
1 2
Ht2 Ht2
z2
t(s)
0 10 20 30 40 50 60 70 80 90 100 110
Fig. 3.7 – Couplage sur un quai en cul-de-sac
xt,r,δ + xt0 ,r0 ,δ0 ≤ 1, ∀t, t0 ∈ T 2 , ∀i, i0 ∈ It × It0 , ∀r, r 0 ∈ Rt,i × Rt0 ,i0
(3.13)
, ∀δ, δ 0 ∈ ∆t × ∆t0 , (xt,r,δ , xt0 ,r0 ,δ0 ) ∈ Inc
Dans la suite, nous utiliserons cette dernière notation.
Enfin, une septième famille permet de garantir la complétude des parcours des trains
sélectionnés dans la solution (équation 3.14). Pour cela, il faut avoir un nombre de parcours
choisis égal pour tous les couples de partitions successives d’un même train.
X X
xt,r,δ = xt,r,δ , ∀t ∈ T, ∀i ∈ {1, . . . , |It | − 1} (3.14)
r∈Rt,i ,δ∈∆t r∈Rt,i+1 ,δ∈∆t
De plus, les trains devant être couplés (resp. découplés) ne peuvent être routés que si
le train auquel ils doivent se coupler (resp. découpler) est lui aussi routé (équations 3.15
(resp. 3.16)). Pour cela, il faut avoir un nombre de parcours choisis égal pour une partition
quelconque de ces deux trains (par exemple la partition 1).
X X
xt,r,δ = xt0 ,r,δ , ∀t ∈ TCoupl , t0 = fCoupl (t) (3.15)
r∈Rt,1 ,δ∈∆t r∈Rt0 ,1 ,δ∈∆t0
X X
xt,r,δ = xt0 ,r,δ , ∀t ∈ TDecoupl , t0 = fDecoupl(t) (3.16)
r∈Rt,1 ,δ∈∆t r∈Rt0 ,1 ,δ∈∆t0
Il est aussi intéressant de noter que ces contraintes peuvent être supprimées pour les
trains de la grille horaire initiale quand l’objectif est de faire circuler tous ces trains. La
contrainte d’unicité des parcours (équation 3.5) limitant à un le nombre de variables d’un
même train et d’une même partition dans une solution, une condition nécessaire pour obtenir
zF ais = |TF ais | est en effet de vérifier l’équation suivante (3.17) :
X X
xt,r = 1 = xt,r , ∀t ∈ TF ais , ∀i ∈ {1, . . . , |It | − 1} (3.17)
r∈Rt,i ,δ∈∆t r∈Rt,i+1 ,δ∈∆t
L’ensemble des éléments indiqués dans les parties précédentes peut être rassemblé dans
un modèle complet. Celui-ci est présenté dans l’équation 3.18. La structure principale de ce
modèle, hormis les contraintes de complétude des parcours (équation 3.14), correspond à un
problème de set packing (décrit dans la section 1.3, page 13). De plus, c’est un problème
multiobjectif avec un objectif prioritaire (zF ais ). Il n’y a, par contre, pas d’ordre de priorité
q
entre les autres objectifs (zSat et zP ref ).
Ainsi, par exemple, la figure 3.8 représente la matrice des contraintes obtenue dans un
scénario à six trains. Dans un souci de clarté, seuls les éléments non nuls y ont été indiqués.
Dans cet exemple, les parcours ne sont pas partitionnés (|It | = 1, ∀t ∈ T ). Le nombre de
parcours possibles varie de deux à trois suivant les trains, et l’horaire de référence est le seul
autorisé pour chacun des trains (|∆t | = 1, ∀t ∈ T ).
La matrice est scindé en deux parties. La partie (a) correspond aux contraintes d’unicité
de parcours (équation 3.5), alors que la partie (b) correspond aux contraintes d’incompati-
bilités (équation 3.13).
q
lex max(zF ais , zSat |zP ref )
X
1
sc zF ais = xt,r,δ
|It |
t∈T F ais ,i∈I t ,r∈Rt,i ,δ∈∆ t
X 1
q
zSat = xt,r,δ , ∀q ∈ T ypes
|It |
q
t∈TSat ,i∈It ,r∈Rt,i ,δ∈∆t
X 1
z = wt,r,δ xt,r,δ
P ref
|I
t|
t∈T,i∈It ,r∈Rt,i ,δ∈∆t
X
xt,r,δ ≤ 1 , ∀t ∈ T, ∀i ∈ It
r∈Rt,i ,δ∈∆t (3.18)
xt,r,δ + xt0 ,r0,δ0 ≤ 1 , ∀t, t0 ∈ T 2 , ∀i, i0 ∈ It × It0
, ∀r, r 0 ∈ Rt,i × Rt0 ,i0
, ∀δ, δ 0 ∈ ∆t × ∆t0
, (xt,r,δ , xt0 ,r0 ,δ0 ) ∈ Inc
X X
xt,r,δ = xt,r,δ , ∀t ∈ T, ∀i ∈ {1, . . . , |It | − 1}
r∈Rt,i ,δ∈∆t r∈Rt,i+1 ,δ∈∆t
xt,r,δ ∈ {0, 1} , ∀t ∈ T, ∀i ∈ It , ∀r ∈ Rt,i , δ ∈ ∆t
1 1 1
1 1
1 1
(a)
1 1 1
1 1
1 1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1 (b)
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
Hypothèse 3.4
Lorsqu’un train est en retard par rapport à l’horaire initial prévu, l’ensemble des choix de
parcours et d’ordre entre les différents trains fait dans le routage et les temps d’arrêt au quai
prévus ne sont pas remis en cause.
Notre évaluation de la stabilité correspond à la somme des retards générés par chacun
des trains du routage soumis à un retard initial, sur tous les autres trains. Elle correspond à
celle proposée par Delorme et al. [DGR03a]. Il est important de noter que les retards générés
peuvent l’être directement ou indirectement (effet «boule-de-neige»). Bien évidemment, cette
évaluation dépendra fortement de la valeur du retard initial considéré. Il peut donc être
intéressant de considérer non pas une mais plusieurs évaluations de stabilité pour des valeurs
de retard initial différentes. Nous allons maintenant introduire quelques notations nécessaires
à la compréhension du modèle d’évaluation de la stabilité.
Par définition, deux variables de cet ensemble sont compatibles ((x1, x2) ∈
/
∗
Inc, ∀(x1, x2) ∈ X ) puisqu’elles font parties d’une même solution
réalisable.
∃d > 0, ∃z ∈ Zones, ([haz,t,r,δ + d, hdz,t,r,δ + d] ∩ [haz,t0 ,r0 ,δ0 , hdz,t0 ,r0 ,δ0 ] 6= ∅))}
G(X ∗ , P ) Graphe orienté des conflits potentiels directs. Dans ce graphe, chaque som-
met représente une des variables sélectionnées dans la solution à évaluer.
Chaque paire de sommets est reliée par un arc orienté lorsque le retard du
train associé au premier sommet peut provoquer un retard de celui associé
au deuxième.
0 , ∀((t, i, r, δ), (t, i + 1, r 0 , δ 0 )) ∈ X ∗ 2
0 0 ∗2
0 , ∀((t, i + 1, r, δ), (t, i, r , δ )) ∈ X
we =
min d ≥ 0, (∃z ∈ Zones, [haz,t,r,δ + d + 1, hdz,t,r,δ + d + 1] ∩ [haz,t0 ,r0 ,δ0 , hdz,t0 ,r0 ,δ0 ] 6= ∅)
0
ou (corrt,r,t0 ,r0 > 0 et (Hti0 + δi00 ) − (Hti−1 + δi−1 + d + 1) < corrt,r,t0 ,r0 )
, ∀((t, i, r, δ), (t0 , i0 , r 0 , δ 0)) ∈ X ∗ 2 , t 6= t0
(3.19)
À l’aide du graphe G(X ∗ , P ) et de la fonction de valuation w, on peut calculer l’ensemble
des retards générés par le retard d’un des trains de la solution sur chacun des autres trains
en prenant en compte les retards générés par des conflits directs et indirects.
La marge margex1,x2 de temps disponible entre les trains associés aux deux sommets
x1 = (t1, i1, r1, δ1) et x2 = (t2, i2, r2, δ2) du graphe correspond au retard maximum possible
pour la variable x1 sans générer de retard sur la variable x2. Elle peut être obtenue par un
calcul de plus court chemin entre ces deux sommets (équation 3.20).
X
margex1,x2 = min wi,j xi,j
−
i∈X ∗ ,j∈ΓG (i)
X
sc xi,j = 1
i∈Γ−
G (x2) (3.20)
X X
xi,j − xj,i = 0, ∀j ∈ X ∗ \ {x1, x2}
i∈Γ−
G (j) i∈Γ+ G (j)
(x1, x2) ∈ X ∗ , x1 6= x2
Le calcul de cette marge correspond donc à la résolution d’un problème de plus court
chemin (décrit dans la section 1.2, page 11) dans le graphe G(X ∗ , P ).
Une fois cette marge connue, le retard retardx1,x2 généré par un retard initial de la
variable x1 sur la variable x2 peut être calculé (équation 3.21) et notre évaluation de la
stabilité (équation 3.22) peut en être déduite. Les différentes partitions d’un même train
étant synchronisées par des arcs de valuations nulles, elles ont forcément le même retard.
Nous pouvons donc ne considérer que les variables correspondant à la première partition du
parcours du train pour ce calcul.
X X
zStabilite = ( retardx1,x2) (3.22)
x1=(t1,1,r1,δ1)∈X ∗ x2=(t2,1,r2,δ2)∈X ∗ \{x1}
De la même manière, on peut calculer la stabilité d’un routage pour différentes valeurs
de retard initial (équation 3.23).
X X
retardInitial
zStabilite = ( max (0, retardInitial − margex1,x2))
x1=(t1,1,r1,δ1)∈X ∗ x2=(t2,1,r2,δ2)∈X ∗ \{x1}
(3.23)
∗
Le graphe G(X , P ) ne prend pas en compte le cadencement éventuel de certains trains.
Les retards ne sont calculés que pour les trains de l’horizon temporel considéré.
La figure 3.9 présente un exemple de graphe des conflits potentiels directs pour un routage
contenant quatre trains (avec trois partitions pour les parcours des trains t1 et t3 et une seule
pour ceux de t2 et t4). Les valeurs des itinéraires et des décalages temporels correspondant
à chacune des variables ne sont pas indiquées. Dans cet exemple, pour un retard initial de
20 s, on obtient les retards suivants :
– t1 génère un retard de 10 s de t4 (marge(t1,1,...),(t4,1,...) = 10),
– t2 génère un retard de 15 s de t1 (marge(t2,1,...),(t1,1,...) = 5), de 15 s de t3 (marge(t2,1,...),(t3,1,...)
= 5) et de 5 s de t4 (marge(t2,1,...),(t4,1,...) = 15),
– t3 ne génère aucun retard,
– t4 génère un retard de 10 s de t3 (marge(t4,1,...),(t3,1,...) = 10).
Nous avons donc une évaluation de stabilité pour un retard initial de 20 s égale à 55 s
20
(zStabilite = 55).
3.4 Conclusion
Dans ce chapitre, nous avons présenté le modèle que nous proposons pour le problème
de l’évaluation et de l’analyse de la capacité d’infrastructures ferroviaires complexes. C’est
un modèle linéaire multiobjectif en variables binaires. Sa structure principale correspond à
celle de deux problèmes classiques de recherche opérationnelle appelés plus court chemin et
set packing.
L’échelle considérée ici est celle d’un nœud ou d’une gare. Le principal avantage de cette
modélisation est de considérer un niveau de détail suffisamment fin pour pouvoir obtenir des
grilles horaires réalisables dans la pratique sur ce type d’infrastructure. De plus, elle intègre
l’ensemble des questions se posant dans notre étude :
t1
0 0
(t1, 1, . . .) (t1, 2, . . .) (t1, 3, . . .)
0 0
t2 20 5 t4 10
(t2, 1, . . .) (t4, 1, . . .)
5
10 10 20
0 0
(t3, 1, . . .) (t3, 2, . . .) (t3, 3, . . .)
0 0
t3
de set packing est NP-difficile. Nous nous focaliserons donc sur les différentes méthodes de
résolution, exactes et approchées, que nous proposons pour le problème de set packing.
Dans le chapitre précédent, nous avons décrit la modélisation retenue pour notre problème
d’évaluation de la capacité d’infrastructures ferroviaires. Cette modélisation fait apparaı̂tre
deux structures principales correspondants aux problèmes de plus court chemin et de set
packing. Nous avons vu au chapitre 1 que la résolution du premier ne présentait pas de
difficulté avec les algorithmes existants (section 1.2.2, page 13), mais que celle du deuxième
pouvait se révéler difficile (section 1.3.3, page 19). Dans ce chapitre, nous allons donc décrire
les méthodes de résolution (exactes et approchées) du problème de set packing que nous
avons utilisées dans les cas mono et biobjectifs.
4.1.1 Pré-traitements
4.1.1.1 Cliques propres au problème de capacité
Nous avons vu au chapitre 1 (section 1.3.3, page 19) que les cliques d’un problème de set
packing correspondaient à des inégalités valides pour ce problème (et même à des facettes
lorsqu’elles sont maximales). La détermination de cliques (même non maximales) permet
ainsi d’améliorer la valeur de la borne supérieure obtenue par relaxation linéaire. Dans cette
optique, la formulation du modèle peut être modifiée. En effet, les contraintes entre paires
de variables incompatibles (équation 3.13, page 60) peuvent être remplacées par les cliques
suivantes (équation 4.1) :
X
xt,r,δ + xt0 ,r0 ,δ0 ≤ 1, ∀t, t0 ∈ T 2 , ∀i, i0 ∈ It × It0 , ∀r ∈ Rt,i , ∀δ ∈ ∆t
r 0 ∈ Rt0 ,i0 , δ0 ∈ ∆t0 , (4.1)
(xt,r,δ , xt0 ,r 0 ,δ0 ) ∈ Inc
En effet, les variables xt0 ,r0,δ0 forment une clique en raison de la contrainte d’unicité de
parcours (équation 3.5, page 54). La variable xt,r,δ étant en conflit avec chacune d’elles, elle
forme une clique avec elles.
Ce principe peut être étendu aux variables, notées xt,r00 ,δ00 , faisant partie de la même
clique d’unicité de parcours que la variable xt,r,δ , à condition qu’elles soient aussi en conflit
avec toutes les variables xt0 ,r0 ,δ0 . Nous obtenons ainsi les cliques suivantes (équation 4.2) :
X X
xt,r,δ + xt0 ,r0,δ0 + xt,r00 ,δ00 ≤ 1
r 0 ∈ Rt0 ,i0 , δ0 ∈ ∆t0 , r 00 ∈ Rt,i , δ00 ∈ ∆t , (r 00 , δ00 ) 6= (r, δ), ∀r 0 ∈ Rt0 ,i0 , ∀δ0 ∈ ∆t0 ,
(xt,r,δ , xt0 ,r 0 ,δ0 ) ∈ Inc ((xt,r,δ , xt0 ,r 0 ,δ0 ) ∈ Inc) ⇒ ((xt,r 00 ,δ00 , xt0 ,r 0 ,δ0 ) ∈ Inc)
X X
xt,r,δ + xt0 ,r0 ,δ0 ≤ 1, ∀t, t0 ∈ T 2 , ∀i, i0 ∈ It × It0
r∈Ar ,δ∈Aδ
r 0 ∈ Rt0 ,i0 , δ0 ∈ ∆t0 , ∀r ∈ Ar
(4.3)
, ∀δ ∈ Aδ , (xt,r,δ , xt0 ,r 0 ,δ0 ) ∈ Inc
Notons aussi que la famille définie par l’équation 4.3 est une généralisation de la famille de
cliques présentée par Zwaneveld [Zwa97] (voir l’équation 4.4). En effet celle-ci ne concernait
X X
xt,r,δ + xt0 ,r0 ,δ0 ≤ 1, ∀t, t0 ∈ T 2 , ∀i ∈ It ∩ It0
r∈Ar ,δ∈Aδ
r 0 ∈ Rt0 ,i , δ0 ∈ ∆t0 , ∀r ∈ Ar
(4.4)
, ∀δ ∈ Aδ , (xt,r,δ , xt0 ,r 0 ,δ0 ) ∈ Inc
Nous avons considéré cette généralisation car les conflits entre trains sur des partitions
différentes (par exemple entre la route d’entrée d’un train et la route de sortie d’un autre
train) sont très nombreux dans les instances sur lesquelles nous avons travaillé. Ceci est
notamment dû au grand nombre de voies banalisées dans les infrastructures que nous avons
étudiées.
Cependant, rien ne garantit que les cliques définies dans la section précédente soient
maximales1 . Nous avons donc développé l’algorithme 4.1 afin de compléter les contraintes
du problème de sorte qu’elles correspondent toutes à des cliques maximales.
pour j ∈ J faire
I0 ← {i ∈ I, ti,j = 0}
pour i ∈ I0 faire
si (∀k ∈ I \ I0 , ∃j 0 ∈ J, (tk,j 0 = 1) et (ti,j 0 = 1)) alors
ti,j ← 1
I0 ← I0 \ {i}
finSi
finPour
finPour
Alg. 4.1 – Calcul de cliques maximales
Cet algorithme complète chacune des contraintes en y ajoutant des variables en conflit
avec toutes celles déjà présentes dans la contrainte. C’est un algorithme de type glouton. Il
effectue ainsi cette opération successivement pour toutes les variables. Notons qu’il n’est pas
spécifique au problème de capacité et peut être utilisé pour tout problème de set packing.
Sa complexité théorique est en O(n2 m) dans le pire des cas.
1
Une clique est maximale si aucune variable ne peut y être ajoutée pour former une nouvelle clique. Cette
notion ne doit pas être confondue avec celle de clique maximum (décrite dans la section 1.3.2.4, page 18)
dont la détermination est un problème NP-difficile.
répéter
It ← I
pour i1 ∈ I faire
si ∃i2 ∈ I \ {i1 }, (∃j ∈ J, ti1 ,j = 1 et ti2 ,j = 1) et (∀i3 ∈ I \ {i1 , i2 },
(∃j ∈ J, ti2 ,j = 1 et ti3 ,j = 1) ⇒ (∃j ∈ J, ti1 ,j = 1 et ti3 ,j = 1))
et (ci1 ≤ ci2 ) alors
I ← I \ {i1 } P
J ← J \ {j : ti1 ,j = 1 et i∈I ti,j ≤ 2}
sortie(finPour)
finSi
finPour
jusqu’à It = I
Alg. 4.2 – Test de dominance entre variables
Ce test de dominance correspond à celui proposé par Zwaneveld [Zwa97] sous le nom de
«Node dominance» (voir section 2.4.1.2, page 39). Parmi les autres pré-traitements qu’ils
avaient proposés, nous avons écarté celui nommé «Detour routes» car il n’est pas valide pour
notre problème. En effet, ce type de routes peut, par exemple, permettre l’évitement de deux
trains devant se croiser, ou le dépassement d’un train par un autre. De plus, nous n’avons
pas retenu les autres pré-traitements en raison de leur faible efficacité. Des expérimentations
préliminaires ont ainsi montré que le test appelé «Combining nodes» n’avait aucun effet sur
les instances que nous avons considérées, car il n’était pas possible d’identifier des couples
de variables vérifiant cette propriété.
pour j ∈ J faire
si ∃j 0 ∈ J \ {j}, {i ∈ I, ti,j = 1} ⊆ {i ∈ I, ti,j 0 = 1} alors
J ← J \ {j}
finSi
finPour
Alg. 4.3 – Test de dominance entre contraintes
La complexité théorique de cet algorithme est en O(nm2 ) dans le pire des cas.
complétées pour en faire des cliques maximales, auraient pu devenir des contraintes non
dominées. Cependant, nous avons constaté que cette situation est rare en pratique.
Un exemple de ce processus est présenté dans les figures 4.1, 4.2 et 4.3. Il illustre les
étapes 1 à 6 de la résolution d’un problème ferroviaire avec une fonction économique dont
les coefficients sont tous égaux à 1.
La figure 4.1, composée de deux matrices, correspond à l’étape 1. La matrice de gauche
est la matrice initiale des contraintes du problème ; elle est identique à celle présentée dans
l’exemple de la section 3.2.3 (page 61). Pour ne pas surcharger la figure, seuls les coefficients
égaux à 1 sont indiqués, la case étant laissée vide lorsque le coefficient est nul. Chaque
ligne de la matrice correspond à une contrainte. Notons la distinction de deux blocs de
contraintes : celles d’unicité de parcours (définies par l’équation 3.5, page 54) puis celles
d’incompatibilités (définies par l’équation 3.13, page 60). Dans la matrice de droite, les
contraintes du deuxième bloc sont reformulées en utilisant les cliques ferroviaires (définies
par l’équation 4.2, page 72). Ces dernières sont indiquées en vis-à-vis de celles de la matrice
de gauche. Lorsqu’une contrainte dans la matrice de droite correspond à plusieurs contraintes
(celles-ci sont forcément successives), elle est alignée sur la première contrainte et les lignes
correspondantes suivantes sont laissées blanches.
La figure 4.2 illustre, elle, l’étape 3. La matrice de gauche représente l’état de la matrice
après la suppression des contraintes redondantes (étape 2). Les lignes blanches ont aussi été
supprimées. La matrice de droite est la matrice obtenue en supprimant les variables dominées
(algorithme 4.2). Les colonnes de ces variables sont marquées par des tirets . De plus, les
contraintes devenues inutiles (celles ne contenant plus qu’un seul élément à 1) sont aussi
enlevées (là encore, une ligne blanche est mise à leur place pour conserver l’alignement).
Ainsi, lorsqu’une colonne est entièrement blanche, cela signifie que la variable n’est pas
supprimée mais n’intervient plus dans aucune contrainte.
Enfin, la figure 4.3 représente la matrice obtenue à la fin de l’étape 4. Dans cet exemple,
la matrice obtenue à l’issue de l’étape 6 est strictement identique puisque les cliques sont
déjà maximales. C’est donc cette matrice qui devra être résolue par Cplex.
1 1 1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1 1 1
1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1
1 1
1 1 1 1 1 1
1 1
1 1 1 1 1 1 1
1 1
1 1 1 1 1 1
1 1
1 1 1 1 1 1 1
1 1
1 1 1 1 1
1 1
1 1 1 1 1
1 1
1 1 1 1
1 1 1 1 1 1
1 1
1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1 1
1 1
1 1
1 1 1 - - - - - 1 1 - -
1 1 - - - - - 1 1 - -
1 1 1 1 - - - - 1 1 - - -
1 1 1 1 1
1 1 1 - - - - 1 1 - - -
1 1 1 - - - - 1 - 1 - -
1 1 - - - - 1 - 1 - -
1 1 1 1 - - - - 1 - - - 1
1 1 1 - - - - - 1 1 - -
1 1 1 1 - - - - - 1 - - 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
équation 4.5) :
2
X
q
Max zλ (X) = λq z (X)
q=1
sc X∈D
c1 X > z 1 (X (B) ) (4.5)
2 2
c X > z (X ) (A)
0 ≤ λq ≤ 1 , ∀q ∈ Q
P2
q=1 λq = 1
avec X (A) et X (B) les deux solutions optimales respectivement pour z 1 et z 2 du problème
scalairisé.
L’ajout de contraintes d’inégalité stricte sur la valeur des fonctions objectifs permet
ainsi de calculer les solutions non supportées (NE). Cet algorithme génère donc l’ensemble
minimum complet des solutions efficaces. L’ensemble complet peut aussi être obtenu par
cette méthode si toutes les solutions optimales des différents problèmes paramétriques sont
recherchées (et non une seule solution optimale par problème).
Après avoir présenté les principes généraux de GRASP nous décrirons l’adaptation de
ces principes pour le problème de set packing que nous avons effectuée.
Solutions ← ∅
répéter
initialSol ← greedyRandomized(problem, α)
improvedSol ← localSearch(initialSol)
[improvedSol ← intensif ication(improvedSol)]
Solutions ← Solutions ∪ {improvedSol}
jusqu’à critère d’arrêt
[Solutions ← postOptimization(Solutions)]
f inalSol ← best(Solutions)
Alg. 4.4 – GRASP
Pour la phase gloutonne de notre algorithme GRASP, nous avons considéré trois algo-
rithmes gloutons différents (appelés greedy1, greedy2 et greedy3). Leurs caractéristiques sont
détaillées ci-dessous :
L’algorithme greedy1 Notre procédure greedy1 (voir l’algorithme 4.5) est inspirée par
l’adaptation de GRASP pour le problème de set covering proposée par Féo et Resende [FR95].
Elle construit une solution en partant de la solution non-réalisable2 triviale, xi = 1, ∀i ∈ I.
Les valeurs de plusieurs variables sont mises à 0 jusqu’à ce que la solution soit réalisable.
Ces changements ne concernent à chaque fois qu’une seule variable par itération. Afin de
conserver une valeur maximale pour la fonction objectif, les variables sont évaluées. Celles
faisant parties d’un nombre maximum de contraintes et avec une valeur minimum (c-à-d
avec ci minimum) sont privilégiées. Une liste restreinte de variables candidates (RCL pour
Restricted Candidate List) est ainsi constituée avec les meilleures variables. Un paramètre
α ∈ [0, 1] appliqué comme coefficient multiplicateur sur la meilleure évaluation permet de
fixer un seuil en dessous duquel les variables ne sont pas conservées dans la RCL. Le choix de
la variable devant être fixée à 0 est fait de manière aléatoire parmi toutes les variables de la
RCL. Ainsi, avec une valeur α = 0, l’algorithme correspond à une construction entièrement
aléatoire ; avec une valeur α = 1, il correspond à un algorithme glouton pur.
La complexité théorique de cet algorithme est en O(n2 m) dans le pire des cas.
2
À l’exception du cas de figure évident à résoudre dans lequel il n’y a aucune contrainte.
It ← I
xi ← 1, ∀i ∈ IPt
Jt ← J \ {j : i∈It ti,j xi ≤ 1}
tant que (Jt 6=
P∅) faire
Evali ← j∈Jt ti,j /ci , ∀i ∈ It
Limit ← mini∈It (Evali ) + α ∗ (maxi∈It (Evali ) − mini∈It (Evali ))
RCL ← {i ∈ It , Evali ≥ Limit}
i∗ ← RandomSelect(RCL)
xi∗ ← 0
It ← It \ {i∗ } P
Jt ← Jt \ {j : i∈It ti,j xi ≤ 1}
finTant
Alg. 4.5 – Construction gloutonne aléatoire greedy1
L’algorithme greedy2 Notre procédure greedy2 (voir l’algorithme 4.6) est inspirée par
l’adaptation de GRASP pour le problème de node packing proposée par Féo et al. [FRS94,
FR95]. Elle construit une solution en partant de la solution réalisable triviale, xi = 0, ∀i ∈ I.
Les valeurs de plusieurs variables sont mises à 1 tant que la solution reste réalisable. Ces
changements ne concernent à chaque fois qu’une seule variable par itération. Afin d’obtenir
une valeur maximale pour la fonction objectif, les variables sont évaluées. Celles faisant
parties d’un nombre minimum de contraintes et avec une valeur maximum (c-à-d avec ci
maximum) sont privilégiées. Comme pour la procédure greedy1, le choix de la variable devant
être fixée à 1 est fait de manière aléatoire parmi les variables sélectionnées dans une RCL.
It ← I
xi ← 0, ∀i ∈ PIt
Evali ← ci / j∈J ti,j , ∀i ∈ It
tant que (It 6= ∅) faire
Limit ← mini∈It (Evali ) + α ∗ (maxi∈It (Evali ) − mini∈It (Evali ))
RCL ← {i ∈ It , Evali ≥ Limit}
i∗ ← RandomSelect(RCL)
xi∗ ← 1
It ← It \ {i∗ }
It ← It \ {i : ∃j ∈ J, ti,j + ti∗ ,j > 1}
finTant
Alg. 4.6 – Construction gloutonne aléatoire greedy2
La complexité théorique de cet algorithme est en O(βnm) dans le pire des cas, avec β
représentant le nombre maximum d’itérations. Ce nombre est égal au nombre maximum de
variables pouvant être fixées à 1 dans une solution réalisable. Cela signifie que sa complexité
théorique est en O(n2 m) (β ≤ n), mais en pratique β est souvent très petit par rapport à n.
Ainsi, la complexité de l’algorithme greedy2 est très souvent largement inférieure à celle de
greedy1.
L’algorithme greedy3 Notre procédure greedy3 est une évolution de la procédure greedy2
décrite précedemment. Elle y inclue un processus d’apprentissage permettant d’améliorer
l’évaluation des variables pour les itérations suivantes de l’algorithme GRASP (voir l’al-
gorithme 4.4). Ainsi, un poids est associé à chaque contrainte en fonction de la fréquence
avec laquelle elle est saturée3 dans l’ensemble des solutions générées au cours des itérations
précédentes. Dans l’algorithme 4.7, SaturationF requency(j) représente le rapport entre le
nombre de fois que la contrainte j a été saturée et le nombre de solutions générées. Ce calcul
est réalisé par la fonction Update(). SaturationF requency est initialisée à 0 pour la première
itération de GRASP.
It ← I
xi ← 0, ∀i ∈ PIt
Evali ← ci / j∈J (ti,j ∗ (1 + SaturationF requency(j))), ∀i ∈ It
tant que (It 6= ∅) faire
Limit ← mini∈It (Evali ) + α ∗ (maxi∈It (Evali ) − mini∈It (Evali ))
RCL ← {i ∈ It , Evali ≥ Limit}
i∗ ← RandomSelect(RCL)
xi∗ ← 1
It ← It \ {i∗ }
It ← It \ {i : ∃j ∈ J, ti,j + ti∗ ,j > 1}
finTant
Update(SaturationF requency(j)), ∀j ∈ J
Alg. 4.7 – Construction gloutonne aléatoire greedy3
Des expérimentations préliminaires ne nous ont pas permis d’identifier une valeur par-
ticulière du paramètre α pouvant être considérée comme une recommandation pour toutes
les instances (ou au moins une grande partie). Cette observation avait déjà été rapportée
par Resende et Ribeiro [RR02]. En conséquence, nous avons décidé d’utiliser plusieurs va-
leurs pour le paramètre α. Notre première stratégie fut de choisir la valeur de α de manière
aléatoire parmi un ensemble discret pré-défini alphaSet de valeurs possibles avec une distri-
bution de probabilités uniforme. Cependant, nous avons aussi considéré une seconde stratégie
3
Une contrainte j est considérée comme saturée par une solution si une variable i, fixée à 1 dans cette
solution, apparaı̂t dans cette contrainte (c-à-d ∃i ∈ I, xi = 1 et ti,j = 1).
Solutions ← ∅
probaα ← 1/|alphaSet|, ∀α ∈ alphaSet
répéter
α∗ ← RandomSelect(alphaSet, proba)
initialSol ← greedyRandomized(problem, α∗ )
improvedSol ← localSearch(initialSol)
[improvedSol ← intensif ication(improvedSol)]
Solutions ← Solutions ∪ {improvedSol}
P oolα∗ ← P oolα∗ ∪ {improvedSol}
si condition probaUpdate est vrai alors
δ
means∈P oolα (z(s))−z(worst(Solutions))
valuationα ← z(best(Solutions))−z(worst(Solutions)) , ∀α ∈ alphaSet
P
probaα ← valuationα / α ∈alphaSet
0 valuation α0 , ∀α ∈ alphaSet
finSi
jusqu’à critère d’arrêt
[Solutions ← postOptimization(Solutions)]
f inalSol ← best(Solutions)
Alg. 4.8 – Reactive GRASP
Le voisinage N utilisé pour notre procédure de recherche locale (voir l’algorithme 4.9)
est basé sur des échanges k − p. Le voisinage, défini par les échanges k − p, d’une solution x
est l’ensemble des solutions obtenues à partir de x en changeant la valeur de k variables de 1
à 0, et en changeant la valeur de p variables de 0 à 1. En raison de l’explosion combinatoire
du nombre d’échanges possibles lorsque les valeurs de k et de p augmentent, nous avons
seulement considéré des échanges 0 − 1, 1 − 1, 2 − 1 et 1 − 2. De plus, la procédure de
recherche a été implémentée en utilisant une stratégie de choix de type première solution
améliorante trouvée (c-à-d que nous sélectionnons le premier voisin trouvé dont la valeur
est meilleure que celle de la solution courante). Chaque fois qu’un échange est réalisé, la
recherche locale est relancée à partir de la nouvelle solution obtenue. Elle s’arrête lorsqu’il
n’y a plus d’échange améliorant possible.
fonction searchNeighbourhood(s, N )
tant que s non localement optimal faire
Trouver s0 ∈ N (s) avec z(s0 ) > z(s)
s ← s0
finTant
renvoyer s
fin searchNeighbourhood
répéter
Solution ← searchNeighbourhood(Solution, 0 − 1exchanges)
Solution ← searchNeighbourhood(Solution, 1 − 1exchanges)
Solution ← searchNeighbourhood(Solution, 2 − 1exchanges)
Solution ← searchNeighbourhood(Solution, 1 − 2exchanges)
jusqu’à Solution non amélioré
renvoyer Solution
Alg. 4.9 – Recherche locale
La procédure d’intensification que nous proposons est basée sur le principe du path
relinking (recomposition de chemins en français). Ce principe a été proposé à l’origine pour
la recherche tabou par Glover et Laguna [GL97]. Le path relinking vise à générer un chemin
reliant deux solutions X (i) et X (f ) de bonne qualité (aussi appelées solutions d’élite), et de
l’explorer pour trouver de meilleures solutions (voir figure 4.4). La notion de chemin utilisée
ici ne correspond pas à celle de la définition 1.4 (chapitre 1, page 12), mais à une succession
de solutions (admissibles ou non) X (t1 ) , . . . , X (tk ) telle que le passage d’une solution à la
suivante peut se faire à l’aide d’un mouvement élémentaire. Il a été utilisé pour la première
fois comme phase d’intensification d’une procédure GRASP par Laguna et Martı́ [LM99].
Solution ← initialSolution
pour i ∈ I faire
si initialSolution(i) 6= targetSolution(i) alors
Solution(i) ← targetSolution(i)
currentSolution ← Solution
si currentSolution non réalisable alors
currentSolution ← repairing(currentSolution)
finSi
currentSolution ← saturation(currentSolution)
P ool ← P ool ∪ {currentSolution}
finSi
finPour
Alg. 4.10 – Path relinking
le problème de set packing (voir l’algorithme 4.10) est inspiré de celui proposé par Resende
et Ribeiro [RR03].
Les meilleures solutions obtenues avec GRASP sont mémorisées dans un ensemble P ool de
taille limitée. À chaque itération de GRASP, l’algorithme de path relinking est appliqué entre
la solution obtenue après la recherche locale et une solution sélectionnée aléatoirement parmi
celles mémorisées dans l’ensemble P ool. La meilleure de ces deux solutions est prise comme
solution initiale (initialSolution), et l’autre comme solution cible (targetSolution). À chaque
itération du path relinking, une solution admissible (currentSolution) est générée à partir de
la solution du chemin (Solution). Celle-ci est donc réparée si cela est nécessaire. La fonction
de réparation considérée utilise l’algorithme 4.5, avec une valeur de 1 pour le paramètre α (c-
à-d une procédure gloutonne pure). Elle est ensuite saturée à l’aide d’une fonction saturation
qui utilise l’algorithme 4.6 (là aussi avec une valeur de 1 pour le paramètre α). Les solutions
ainsi générées peuvent aussi être inclues dans l’ensemble P ool.
Nous disposons ainsi d’une procédure GRASP complète pour le problème de set packing
mono-objectif. De plus, nous avons utilisé cette procédure pour obtenir une approximation
de la frontière efficace pour les problèmes de set packing biobjectifs. Pour cela, nous l’avons
encapsulée de manière à l’appliquer successivement et indépendamment sur 20 directions de
recherche différentes. Ces directions de recherche correspondent aux combinaisons convexes
des objectifs. Cela revient donc à résoudre les 20 problèmes de set packing mono-objectifs
définis par l’équation 4.6. La figure 4.5 illustre le principe de résolution utilisé. La méthode
décrite ici correspond à celle proposée par Delorme et al. [DGD03].
1
1 2
Max zλ (X) = λz (X) + (1 − λ)z (X) , ∀λ ∈ {0, 19
, . . . , 18
19
, 1}
(4.6)
sc X ∈D
z 2 (X)
λ=0
λ=1
z 1 (X)
Fig. 4.5 – Schéma de l’utilisation de GRASP dans le cas biobjectif
Nous avons vu au chapitre 1 (section 1.4.2.2, page 24) que les solutions obtenues avec
une telle technique et une méthode de résolution exacte appartenaient toutes à l’ensemble
SE des solutions supportées. Dans notre cas, la méthode de résolution appliquée étant une
méthode approchée, les solutions obtenues, lorsqu’elles sont efficaces, peuvent aussi appar-
tenir à l’ensemble NE des solutions non supportées. Durant ce processus, l’ensemble des
solutions potentiellement efficaces générées (à chaque itération de GRASP et même du path
relinking) sont conservées.
4.3 Conclusion
Dans ce chapitre, nous avons décrit les différents algorithmes que nous proposons pour
résoudre, de manière exacte ou approchée, le problème de set packing. Ceux-ci peuvent
ainsi être utilisés pour résoudre le problème d’évaluation de la capacité d’infrastructures
ferroviaires tel que nous l’avons modélisé au chapitre 3.
La méthode de résolution exacte que nous avons considérée s’appuie sur des algorithmes
de pré-traitements et sur le logiciel Cplex. Nos pré-traitements mettent notamment à profit la
structure du problème de set packing et les spécifités des instances ferroviaires. La méthode
de résolution approchée, quant à elle, est une adaptation de la métaheuristique GRASP.
Plusieurs programmes, inspirés de cette métaheuristique et de certaines de ses extensions
les plus connues, ont ainsi été développés et présentés. En outre, afin de prendre en compte
l’aspect multiobjectif de notre modélisation, des travaux sur des algorithmes biobjectifs ont
aussi été engagés. Ceux-ci reposent sur une extension des méthodes de résolution mono-
objectifs proposées.
Dans la suite, nous allons nous intéresser à l’évaluation des performances de ces différents
algorithmes. Pour cela, nous allons présenter les résultats que nous avons obtenus sur un
ensemble d’instances tests. Ces résultats sont ainsi commentés et analysés.
En raison de l’absence (en tout cas à notre connaissance) d’instances tests disponibles
pour le problème de set packing mono-objectif, nous avons basé notre évaluation sur des
instances que nous avons générées. Ces instances peuvent être classées en deux catégories :
– un ensemble d’instances générées aléatoirement afin d’observer le comportement de nos
algorithmes sur une gamme de problèmes aux caractéristiques variées,
– et un ensemble d’instances correspondant à l’application de notre modèle ferroviaire
d’évaluation de la capacité sur une infrastructure réelle. Ce deuxième ensemble peut
ainsi permettre d’identifier des difficultés spécifiques à la structure de ces instances. De
plus, il permet de mesurer l’impact de la reformulation du problème ferroviaire (voir
section 4.1.1.1, page 71).
En outre, un ensemble d’instances aléatoires de plus petite taille a aussi été généré afin
d’effectuer une validation dans le cas biobjectif.
Pour obtenir la diversité souhaitée, les instances mono-objectifs aléatoires ont été générées
avec les caractéristiques suivantes :
– le nombre de variables est égal à 1000 ou à 2000,
– le nombre de contraintes est égal à 100% ou à 500% du nombre de variables,
– le nombre maximum
X d’éléments non nuls par contrainte est égal à 1% ou 5% du nombre
de variables ( ti,j ≤ 0, 01 ∗ n(resp. 0, 05 ∗ n), ∀j ∈ J, c-à-d que le nombre d’éléments
i∈I
non nuls d’une contrainte est choisi aléatoirement entre deux et ce pourcentage ; en
effet, une contrainte comprenant moins de deux éléments n’aurait aucun intérêt pour
le problème),
– les valeurs des variables (ci ) sont uniformément distribuées dans l’intervalle [1-20] (ins-
tances à coûts pondérés) ou toutes fixées à 1 (instances à coûts unitaires).
Toutes les combinaisons possibles de ces caractéristiques ont été considérées. Seize instances,
portant le label Rnd, ont ainsi été générées. Leurs caractéristiques sont présentées dans le
tableau 5.1. La colonne densité indique le pourcentage d’éléments non nuls dans la matrice
des contraintes1 . Les instances à coûts pondérés sont aussi signalées. Enfin, les valeurs de
la fonction objectif de la relaxation linéaire (LP) et de la meilleure solution entière connue
(avec un astérisque lorsque cette solution a été démontrée comme optimale par Cplex) sont
mentionnées. Notons l’écart très important entre ces deux valeurs.
Toutes ces instances sont disponibles sur un site web présentant une collection d’instances
tests du problème de set packing mono-objectif [Del].
1
Même si ce pourcentage est influencé par le nombre maximum d’éléments non nuls par contrainte, il ne
doit pas être confondu avec ce dernier.
Paris Chantilly
Grande ceinture
LGV
deux sens augmente le nombre de conflits possibles. La détermination de la capacité d’un tel
nœud n’est donc pas une chose aisée.
Les instances numériques présentées ici correspondent à des instances du problème de
saturation sur des configurations de grille horaire différentes. Ainsi, elles contiennent des
contraintes issues des équations 3.5 et 3.13. Tous les trains considérés sont des trains satu-
rants, l’ensemble des trains de la grille horaire initiale est donc vide (TF ais = ∅, T = TSat ).
La fonction objectif de ces instances provient donc de l’équation 3.3 ; ces instances sont à
coûts unitaires (ci = 1, ∀i ∈ I).
Quinze instances, portant le label Gon, ont ainsi été générées. Leurs caractéristiques sont
présentées dans le tableau 5.2. Là encore, les valeurs de la fonction objectif de la relaxation
linéaire (LP) et de la meilleure solution entière connue (avec un astérisque lorsque cette
solution a été démontrée comme optimale) sont mentionnées.
c2n−i+1 = c1i , ∀i = 1, . . . , n ;
E : un objectif unitaire et un aléatoire
c1i = 1, c2i = rnd[1..100], ∀i = 1, . . . , n ;
F : un objectif unitaire et un avec motifs
c1i = 1, ∀i = 1, . . . , n ;
N◦ n m Densité ci LP Meilleure
solution connue
Rnd1 1 000 5 000 2.60% [1-20] 330.26 67*
Rnd2 1 000 5 000 2.59% [1-1] 22.81 4*
Rnd3 1 000 5 000 0.60% [1-20] 1 365.64 661
Rnd4 1 000 5 000 0.60% [1-1] 111.77 48
Rnd5 1 000 1 000 2.60% [1-20] 434.71 222
Rnd6 1 000 1 000 2.65% [1-1] 29.91 15
Rnd7 1 000 1 000 0.58% [1-20] 2 349.19 2 260*
Rnd8 1 000 1 000 0.60% [1-1] 184.32 175
Rnd9 2 000 10 000 2.54% [1-20] 339.62 40*
Rnd10 2 000 10 000 2.55% [1-1] 22.59 2*
Rnd11 2 000 10 000 0.55% [1-20] 1 500.10 478
Rnd12 2 000 10 000 0.55% [1-1] 114.01 32
Rnd13 2 000 2 000 2.55% [1-20] 423.98 140
Rnd14 2 000 2 000 2.56% [1-1] 28.70 9
Rnd15 2 000 2 000 0.56% [1-20] 2 209.57 1 784
Rnd16 2 000 2 000 0.60% [1-1] 168.82 132
N◦ |T | n m Densité LP Meilleure
solution connue
Gon1 90 465 8 661 0.44% 90,00 45*
Gon2 120 620 11 676 0.33% 120,00 60*
Gon3 240 1 240 23 736 0.16% 240,00 120*
Gon4 240 1 240 50 705 0.16% 240,00 94*
Gon5 360 1 860 55 938 0.11% 360,00 151*
Gon6 360 1 860 119 009 0.11% 360,00 76
Gon7 380 1 620 79 5144 0.12% 380,00 88
Gon8 720 3 720 155 985 0.05% 720,00 280*
Gon9 720 3 720 482 887 0.05% 720,00 93
Gon10 150 2 400 186 861 0,08% 150,00 85
Gon11 125 2 683 228 972 0,07% 125,00 87
Gon12 200 2 880 311 228 0,07% 200,00 89*
Gon13 157 3 210 380 292 0,06% 157,00 90*
Gon14 150 2 160 140 632 0,09% 150,00 88
Gon15 130 2 503 185 523 0,08% 130,00 104
n n
l1 = rnd[1.. 10 ], l2 = rnd[1.. 10 ], . . . ;
c1 = c2 = . . . = cl1 = rnd[1..100] ; c2l1 +1 = c2l1 +2 = . . . = c2l1 +l2 = rnd[1..100] ; . . .
2 2 2
Cela représente un total de 120 instances numériques (20 par famille de fonctions objec-
tifs). Du fait de leur nombre, leurs caractéristiques détaillées ne sont pas présentées dans ce
mémoire. Toutes ces instances sont disponibles dans la collection d’instances de problèmes
MOCO hébergée sur le site web de la MCDM society [MCD].
Nous allons maintenant nous intéresser à la résolution exacte de ces instances. Dans
ce but, nous commencerons par observer l’impact de nos différents algorithmes de pré-
traitements (décrits dans la section 4.1.1), puis nous indiquerons la qualité des solutions
et des bornes supérieures obtenues. Les résultats présentés dans cette section reprennent et
complètent ceux présentés par Delorme et al. [DGR03a, DGR03b].
Les tableaux 5.3 et 5.4 rapportent respectivement l’évolution du nombre de variables des
instances aléatoires et ferroviaires (entièrement due au test de dominance entre variables,
les calculs de cliques ne pouvant pas supprimer de variable). Les Figures 5.2 et 5.3, quant
à elles, rapportent respectivement l’évolution du nombre de contraintes et de la densité de
la matrice des contraintes. Dans un souci de clarté et en raison des écarts très importants
entre les différentes instances étudiées dans le nombre de contraintes, celui-ci est indiqué en
proportion du nombre de contraintes du problème initial et non pas en valeur (c-à-d que la
valeur 100% sur l’axe des ordonnées correspond au nombre de contraintes du problème avant
l’utilisation des pré-traitements).
L’impact sur le nombre de variables est en général assez limité sur les instances aléatoires.
Hormis pour les instances Rnd09 et Rnd10, seulement 1% en moyenne, et au plus 8%, des
variables des autres instances sont ainsi supprimées.
Sur les instances ferroviaires, l’impact s’avère un peu plus important (16% de variables
supprimées) et surtout mesurable sur toutes les instances (au moins 7% de variables sup-
primées). Il faut cependant noter que le pourcentage semble plus faible sur les instances de
plus grande taille : il est d’environ 10% pour les instances Gon08 à Gon15 (celles dont le
nombre de variables est supérieur à 2000). En effet, si certains choix de parcours peuvent ne
présenter aucun intérêt lorsque le trafic est faible, ce n’est souvent plus le cas quand celui-ci
devient plus dense. De plus, ces valeurs restent relativement basses par comparaison avec
celles rapportées lors du projet DONS (voir section 2.4.1.2). Ceci peut s’expliquer par la
présence de nombreuses voies banalisées et par les différences de temps entre les choix de
100 %
98 %
94 %
en pourcentage du nombre
Nombre de contraintes
du probleme initial
92 %
90 %
88 %
86 %
84 %
Rnd01 Rnd02 Rnd03 Rnd04 Rnd05 Rnd06 Rnd07 Rnd08 Rnd09 Rnd10 Rnd11 Rnd12 Rnd13 Rnd14 Rnd15 Rnd16
Instances
25 %
Reformulation
Dominance entre variables
Cliques maximales
20 %
en pourcentage du nombre
Nombre de contraintes
15 %
du probleme initial
10 %
5%
0%
Gon01 Gon02 Gon03 Gon04 Gon05 Gon06 Gon07 Gon08 Gon09 Gon10 Gon11 Gon12 Gon13 Gon14 Gon15
Instances
50 %
Probleme initial
Dominance entre variables
Cliques maximales
45 %
40 %
35 %
matrice des contraintes
30 %
Densite de la
25 %
20 %
15 %
10 %
5%
0%
Rnd01 Rnd02 Rnd03 Rnd04 Rnd05 Rnd06 Rnd07 Rnd08 Rnd09 Rnd10 Rnd11 Rnd12 Rnd13 Rnd14 Rnd15 Rnd16
Instances
2.5 %
Probleme initial
Reformulation
Dominance entre variables
Cliques maximales
2%
matrice des contraintes
1.5 %
Densite de la
1%
0.5 %
0%
Gon01 Gon02 Gon03 Gon04 Gon05 Gon06 Gon07 Gon08 Gon09 Gon10 Gon11 Gon12 Gon13 Gon14 Gon15
Instances
parcours.
L’impact sur le nombre de contraintes des instances aléatoires est en général très limité.
Environ 2% de contraintes sont supprimées sur la plupart des instances grâce au test de
dominance entre paires de variables, quasiment rien avec le calcul de cliques maximales.
Seules deux instances (Rnd09 et Rnd10) laissent apparaı̂tre un effet plus significatif (plus de
10% avec le test de dominance et environ 3% supplémentaires avec les cliques maximales). De
même, l’impact sur la densité est négligeable sur la plupart des instances. Quatre instances
(Rnd01, Rnd02 et là encore Rnd09 et Rnd10) font cependant exception puisque le calcul de
cliques maximales augmente la densité de manière très importante (environ 1000% pour les
deux premières et 2000% pour les deux autres). La densité de ces instances après les pré-
traitements est ainsi beaucoup plus élevée que celle des autres instances. Il est intéressant de
noter que ce sont les instances aléatoires les plus contraintes (grand nombre de contraintes
par rapport au nombre de variables et densité importante).
Par contre, dans le cas des instances ferroviaires, l’impact est beaucoup plus fort. Si le
test de dominance entre paires de variables n’a, là encore, qu’un effet limité sur le nombre
de contraintes et quasiment nul sur la densité, ce n’est pas le cas des calculs de cliques. En
effet, la reformulation du problème permet de diviser par 5 ou plus le nombre de contraintes,
tout en doublant leur densité. De même, le calcul de cliques maximales divise encore par
2 le nombre de contraintes et double à nouveau leur densité. La présence de nombreuses
contraintes n’incluant que deux variables dans la formulation initiale du modèle explique
sûrement cette marge importante de progrès.
1200 %
Probleme initial
Dominance entre variables
Cliques maximales
1000 %
800 %
lineaire en pourcentage de la
meilleure solution connue
Valeur de la relaxation
600 %
400 %
200 %
Rnd01 Rnd02 Rnd03 Rnd04 Rnd05 Rnd06 Rnd07 Rnd08 Rnd09 Rnd10 Rnd11 Rnd12 Rnd13 Rnd14 Rnd15 Rnd16
Instances
800 %
Probleme initial
Reformulation
Dominance entre variables
Cliques maximales
700 %
600 %
lineaire en pourcentage de la
meilleure solution connue
Valeur de la relaxation
500 %
400 %
300 %
200 %
100 %
Gon01 Gon02 Gon03 Gon04 Gon05 Gon06 Gon07 Gon08 Gon09 Gon10 Gon11 Gon12 Gon13 Gon14 Gon15
Instances
nul). Suite aux pré-traitements, l’écart se retrouve à un niveau beaucoup plus bas que pour
les instances aléatoires (au plus 25%).
Pour finir, la Figure 5.5 présente l’évolution des solutions obtenues avec le logiciel Cplex
8.0 [ILO02]. Nous avons utilisé pour cela les réglages par défaut du logiciel. Des expérimen-
tations préliminaires ont en effet montré que ces réglages étaient les plus performants. La
valeur indiquée correspond au gap entre la meilleure solution entière et la borne supérieure
trouvées par Cplex (exprimé en pourcentage). Il est donc nul lorsque la solution optimale est
trouvée. Dans les autres cas, le gap indiqué est celui obtenu après 50 000 secondes de calcul.
Ces résultats montrent l’amélioration globale observée. Il est cependant intéressant de no-
ter que l’utilisation des pré-traitements ne provoque pas automatiquement une amélioration
du gap. Ainsi pour certaines instances (Rnd01, Rnd11, Rnd12, Rnd15, Gon07 et Gon14),
le gap obtenu avec Cplex peut être légèrement moins bon après l’utilisation de l’un d’eux.
Cela peut notamment être dû à la modification de la structure du problème qui intervient
notamment sur le fonctionnement interne de Cplex (ordre de branchement sur les variables,
cliques détectées, solutions heuristiques générées, . . .). Notons que cette dégradation inter-
vient le plus souvent (instances Rnd11, Rnd12 et Rnd15) pour des instances sur lesquelles
l’impact des pré-traitements sur les caractéristiques et la valeur de la relaxation linéaire était
très faible. L’impact global est malgré cela positif, avec en particulier six instances dont la
solution optimale a été trouvée grâce à l’application préliminaire des pré-traitements (Rnd01,
Rnd02, Rnd09, Rnd10, Gon12 et Gon13).
1200 %
Probleme initial
Dominance entre variables
Cliques maximales
1000 %
800 %
Gap
600 %
400 %
200 %
0%
Rnd01 Rnd02 Rnd03 Rnd04 Rnd05 Rnd06 Rnd07 Rnd08 Rnd09 Rnd10 Rnd11 Rnd12 Rnd13 Rnd14 Rnd15 Rnd16
Instances
350 %
Probleme initial
Reformulation
Dominance entre variables
Cliques maximales
300 %
250 %
200 %
Gap
150 %
100 %
50 %
0%
Gon01 Gon02 Gon03 Gon04 Gon05 Gon06 Gon07 Gon08 Gon09 Gon10 Gon11 Gon12 Gon13 Gon14 Gon15
Instances
Fig. 5.5 – Impact des pré-traitements sur le gap obtenu avec Cplex
800 %
Solution entiere - Borne superieure
LP
700 %
600 %
Cplex en pourcentage de la
500 %
meilleure solution connue
Valeur de la solution
400 %
300 %
200 %
100 %
0%
Rnd Rnd Rnd Rnd Rnd Rnd Rnd Rnd Rnd Rnd Rnd Rnd Rnd Rnd Rnd Rnd
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Instances
125 %
Solution entiere - Borne superieure
LP
120 %
115 %
Cplex en pourcentage de la
meilleure solution connue
Valeur de la solution
110 %
105 %
100 %
95 %
90 %
Gon Gon Gon Gon Gon Gon Gon Gon Gon Gon Gon Gon Gon Gon Gon
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Instances
exemple celui du sac-à-dos biobjectif (voir Gandibleux [Gan01]). La Figure 5.7 donne une
illustration de ces écarts en montrant la frontière efficace exacte (01) et les bornes obtenues,
par relaxation linéaire (RL) et par un algorithme glouton, sur une des instances considérées.
RL
01
2800 glouton
2600
2400
z2
2200
2000
1800
2000 2100 2200 2300 2400 2500 2600 2700 2800 2900
z1
- condition probaUpdate : les probabilités sont mises à jour toutes les 20 itérations de
GRASP (uniquement pour reactive GRASP)
- δ = 5 (uniquement pour reactive GRASP)
– l’algorithme de recherche locale décrit dans la section 4.2.2.3
– la phase d’intensification décrite dans la section 4.2.2.4 avec
- |P ool| = 5
- Un P ool différent pour chaque valeur du paramètre α considérée. En effet, des
expérimentations préliminaires avec un P ool unique pour toutes les valeurs ont mis
en évidence des résultats de qualité inférieure. Cette observation concorde avec les
commentaires faits par Glover et Laguna [GL97] sur l’utilisation du path relinking
en tant que phase d’intensification.
– le critère d’arrêt : 200 itérations de GRASP.
Seize lancements indépendants de GRASP ont ainsi été effectués pour chaque configura-
tion présentée et pour chaque instance considérée. À chaque lancement, nous considérons la
meilleure solution obtenue. Tous les résultats rapportés pour GRASP correspondent (sauf
indication contraire) à la moyenne de ces meilleures solutions. Dans la suite, nous allons com-
parer les différentes stratégies que nous avons proposées, puis étudier l’impact de chacune
des phases de GRASP. Une synthèse des résultats obtenus est ensuite présentée.
108 %
Apprentissage
Reactive GRASP
106 %
Apprentissage + Reactive GRASP
104 %
la meilleure solution connue
solution en pourcentage de
Valeur moyenne de la
102 %
100 %
98 %
96 %
94 %
Rnd01 Rnd02 Rnd03 Rnd04 Rnd05 Rnd06 Rnd07 Rnd08 Rnd09 Rnd10 Rnd11 Rnd12 Rnd13 Rnd14 Rnd15 Rnd16
Instances
Apprentissage
104 %
Reactive GRASP
102 %
la meilleure solution connue
solution en pourcentage de
Valeur moyenne de la
100 %
98 %
96 %
Gon01 Gon02 Gon03 Gon04 Gon05 Gon06 Gon07 Gon08 Gon09 Gon10 Gon11 Gon12 Gon13 Gon14 Gon15
Instances
En fait, les résultats observés avec chacune des stratégies proposées sont très proches.
Chaque version se révèle ainsi la meilleure pour certaines instances, mais aussi la moins
bonne pour d’autres : la version 1 est la meilleure pour 10 instances, la version 2 pour 5, la
version 3 pour 11 et GRASP-Ref pour 5. De plus, les écarts de performance sont minimes :
ils atteignent 8% dans le pire des cas (entre les versions 2 et 4 sur l’instance Rnd2) et sont en
général inférieurs à 1%. L’écart de performance moyen sur l’ensemble des instances étudiées
est inférieur à 0,5%. Cette proximité de performance ne permet donc pas d’identifier une
stratégie surclassant les autres.
Remarquons tout de même que l’utilisation de reactive GRASP seul amène les écarts
négatifs les plus importants par rapport à GRASP-Ref (-5% pour Rnd9 et -3% pour Rnd13).
Son écart moyen sur l’ensemble des instances est d’ailleurs quasiment nul. Au contraire, le
processus d’apprentissage seul présente un impact moyen positif (+0,37% par rapport à
GRASP-Ref en moyenne sur l’ensemble des instances). Si la combinaison peut générer des
résultats décevants sur certaines instances (particulièrement Rnd2), elle présente elle aussi un
écart moyen positif. Étant donné que cette version est celle qui permet d’obtenir la meilleure
solution moyenne sur le plus grand nombre d’instances (14 sur 31), nous l’avons retenue pour
les expérimentations suivantes.
100 %
95 %
la meilleure solution connue
solution en pourcentage de
Valeur moyenne de la
90 %
85 %
80 %
75 %
Rnd01 Rnd02 Rnd03 Rnd04 Rnd05 Rnd06 Rnd07 Rnd08 Rnd09 Rnd10 Rnd11 Rnd12 Rnd13 Rnd14 Rnd15 Rnd16
Instances
100 %
95 %
la meilleure solution connue
solution en pourcentage de
Valeur moyenne de la
90 %
85 %
80 %
Gon01 Gon02 Gon03 Gon04 Gon05 Gon06 Gon07 Gon08 Gon09 Gon10 Gon11 Gon12 Gon13 Gon14 Gon15
Instances
100 %
80 %
temps de calcul total
60 %
en pourcentage du
Temps de calcul
40 %
20 %
0%
Rnd01 Rnd02 Rnd03 Rnd04 Rnd05 Rnd06 Rnd07 Rnd08 Rnd09 Rnd10 Rnd11 Rnd12 Rnd13 Rnd14 Rnd15 Rnd16
Instances
100 %
80 %
temps de calcul total
60 %
en pourcentage du
Temps de calcul
40 %
20 %
0%
Gon01 Gon02 Gon03 Gon04 Gon05 Gon06 Gon07 Gon08 Gon09 Gon10 Gon11 Gon12 Gon13 Gon14 Gon15
Instances
Fig. 5.10 – Répartition par phase du temps utilisé par notre procédure GRASP
Ces améliorations ont cependant un coût important en terme de temps de calcul : les
phases de recherche locale et de path relinking utilisent l’essentiel du temps de calcul (res-
pectivement 24,5% et 72,3%). Notons aussi que la phase gloutonne consomme plus de temps
pour les instances fortement contraintes (instances Rnd 1, 2, 9 et 10). Ceci est dû au
temps nécessaire pour l’évaluation des variables, et ne permet pas pour autant d’obtenir
une meilleure qualité des résultats. De même, la recherche locale peut utiliser une grande
partie du temps de calcul sans avoir un impact sur la qualité de solution (instances Rnd 9
et 10). Au contraire, le path relinking ne consomme qu’une faible partie du temps de calcul
pour les instances où il n’a pas d’impact (instances Rnd 1, 2, 9 et 10). Il est intéressant
de noter que ces quatre instances sont les plus contraintes. Les solutions admissibles de ces
problèmes contiennent donc peu de variables fixées à 1. Ainsi, l’algorithme de path relinking
n’effectue en fait qu’un nombre limité d’itérations sur ces instances.
100 %
95 %
la meilleure solution connue
GRASP en pourcentage de
90 %
Valeur de la solution
85 %
80 %
Rnd01 Rnd02 Rnd03 Rnd04 Rnd05 Rnd06 Rnd07 Rnd08 Rnd09 Rnd10 Rnd11 Rnd12 Rnd13 Rnd14 Rnd15 Rnd16
Instances
100 %
98 %
la meilleure solution connue
GRASP en pourcentage de
96 %
Valeur de la solution
94 %
92 %
90 %
Gon01 Gon02 Gon03 Gon04 Gon05 Gon06 Gon07 Gon08 Gon09 Gon10 Gon11 Gon12 Gon13 Gon14 Gon15
Instances
Fig. 5.11 – Synthèse des résultats obtenus avec notre procédure GRASP complète
En effet, nous avons vu dans la section 5.2.3 que les bornes obtenues sur ce problème étaient
de mauvaise qualité. Elles ne peuvent donc pas être utilisées pour évaluer nos approximations.
De même, aucune relation de dominance n’a pu être observée dans le cas général entre elles.
L’utilisation d’un indicateur de performance unique peut introduire un biais (voir Jasz-
kiewicz [Jas04]). Ainsi, pour mesurer la qualité des approximations obtenues, nous avons
utilisé les trois indicateurs suivants :
1. le pourcentage de solutions efficaces trouvées (M1 proposé par Ulungu et al. [UTF95]),
2. la distance euclidienne moyenne à la frontière efficace,
3. l’hypervolume (S-metric proposé par Zitzler et Thiele [ZT99]) correspondant pour le
biSPP à la surface définie dans l’espace des critères par l’ensemble des solutions de
l’approximation.
De plus, afin de faciliter la comparaison sur l’ensemble ou sur des familles d’instances,
les valeurs de l’indicateur hypervolume ont été exprimées en pourcentage par rapport aux
valeurs de cet indicateur pour la frontière efficace (une valeur de 100% correspond donc à
une couverture complète de la frontière efficace).
(algorithme glouton fixant des variables à 0 tant que toutes les contraintes ne sont pas res-
pectées) permet de les ramener dans le domaine des solutions réalisables. Une procédure de
saturation (algorithme glouton fixant des variables à 1 tant que cela est possible en conser-
vant une solution réalisable) permet d’améliorer toutes les solutions générées. Enfin, une
sélection par tournois est effectuée afin de limiter la taille de la population.
De plus, afin d’améliorer les performances de l’algorithme sur le biSPP, plusieurs éléments
ont été ajoutés. Ainsi, toutes les solutions potentiellement efficaces trouvées sont conservées
dans la population (ce qui n’était pas le cas avec la méthode originale). De même, afin
d’améliorer les performances de l’algorithme dans les régions de l’ensemble des solutions
efficaces proches des solutions extrémales2 , la saturation est effectuée dans trois directions
de recherche différentes pour chaque solution (z 1 , z 2 et une combinaison des deux objectifs).
Enfin, pour diminuer les «trous3 » observés dans les approximations au cours de premières
expérimentations, une recherche locale basée sur des échanges 1-1 (une variable fixée à 0,
une autre à 1) a été ajoutée entre chaque génération. Cette procédure est appliquée à toutes
les solutions de la population.
Le critère d’arrêt utilisé pour les deux algorithmes est le temps de résolution, fixé à
20 secondes pour les instances à 100 variables et à 80 secondes pour celles à 200 va-
riables. Les résultats indiqués correspondent aux résultats moyens observés sur 16 lance-
ments indépendants de chaque algorithme. Tous ces résultats sont synthétisés pour chaque
indicateur, respectivement dans les tableaux 5.5, 5.6 et 5.7.
A B C D E F Total
100 variables 81% 88% 81% 86% 95% 87% 86%
SPEA 200 variables 71% 68% 71% 80% 72% 81% 74%
Total 75% 76% 75% 82% 82% 83% 79%
100 variables 91% 92% 85% 94% 84% 88% 89%
GRASP 200 variables 58% 54% 64% 67% 57% 62% 60%
Total 72% 70% 73% 79% 68% 73% 72%
Au regard de ces indicateurs, les approximations obtenues avec les deux méthodes sont de
bonne qualité. Les résultats sont cependant moins bons sur les instances de plus grande taille
(200 variables). À l’examen des indicateurs 2 et 3 (distance moyenne et hypervolume), les
résultats de GRASP sur les instances des familles E et F semblent un peu moins satisfaisants.
2
Une solution s est appelée extrémale si s ∈ SE et ∃q ∈ Q, z q (s) = max z q (x).
x∈SE
3
Un trou est une zone de la frontière potentiellement efficace vide de solution.
A B C D E F Total
100 variables 4,00 1,43 1,98 0,60 0,25 0,60 1,48
SPEA 200 variables 5,08 6,73 6,68 3,44 3,20 1,72 4,47
Total 4,62 4,49 4,70 2,24 1,96 1,25 3,21
100 variables 0,44 0,71 1,21 0,54 3,12 4,77 1,80
GRASP 200 variables 8,52 8,53 5,42 6,05 13,61 20,30 10,40
Total 5,12 5,24 3,65 3,73 9,19 13,76 6,78
A B C D E F Total
100 variables 99,5% 99,4% 99,0% 99,6% 99,7% 99,3% 99,4%
SPEA 200 variables 98,5% 98,3% 98,9% 99,0% 98,6% 98,7% 98,7%
Total 98,9% 98,8% 99,0% 99,3% 99,1% 99,0% 99,0%
100 variables 100,0% 100,0% 100,0% 100,0% 99,7% 99,9% 99,9%
GRASP 200 variables 99,8% 99,7% 99,8% 99,8% 98,9% 99,0% 99,5%
Total 99,9% 99,8% 99,9% 99,9% 99,2% 99,4% 99,7%
En fait, ceci est probablement lié à la présence d’un objectif unitaire. En effet, le nombre de
solutions efficaces de ces instances est plus faible et les écarts mesurés en pourcentage sont
donc plus importants.
Par contre, si SPEA apparaı̂t comme meilleur vis-à-vis des deux premiers indicateurs,
GRASP produit de meilleurs résultats vis-à-vis de l’indicateur d’hypervolume. En fait, SPEA
génère une population très proche de la frontière et une densité de solutions intéressante,
mais éprouve des difficultés à trouver les solutions extrémales. Au contraire, l’approximation
produite par GRASP représente une bonne répartition le long de la frontière efficace, mais la
densité de solutions obtenues est plus faible (sans doute à cause de l’utilisation de directions
de recherche). La Figure 5.12 rapporte les approximations obtenues pour une instance sur
une exécution de chacune des heuristiques et illustre bien le comportement caractéristique
des deux dernières.
5.4 Conclusion
Dans ce chapitre, nous avons testé les différents algorithmes que nous avons présentés
au chapitre 4 et analysé leurs performances. Nous nous sommes appuyés pour cela sur une
gamme d’instances mono et biobjectifs. Certaines d’entre elles correspondent au problème
ferroviaire étudié dans ce mémoire, mais d’autres instances, générées aléatoirement, ont aussi
été utilisées.
SPEA
GRASP
2800
2600
2400
z2
2200
2000
1800
2000 2100 2200 2300 2400 2500 2600 2700 2800 2900
z1
Ces expérimentations numériques ont permis de mettre en évidence l’intérêt des algo-
rithmes de pré-traitements et notamment des recherches de cliques. En effet, ils se sont
avérés très efficaces pour réduire la taille des instances considérées et améliorer la qualité
de la borne supérieure obtenue. Ils ont ainsi permis d’améliorer de manière significative les
résultats obtenus avec Cplex, et de résoudre exactement plusieurs instances. Malgré tout, la
résolution exacte de plusieurs des instances considérées est encore impossible, le gap pouvant
rester extrêmement important pour certaines d’entre elles.
Au contraire, les résultats enregistrés avec notre algorithme GRASP indiquent qu’il se
montre performant sur l’ensemble des instances. Il est ainsi capable de générer des solutions
de bonne qualité, même pour des instances de grande taille. Si l’implémentation de reactive
GRASP ne donne pas encore entièrement satisfaction, le processus d’apprentissage a un
impact positif significatif. De plus, l’apport de chacun des composants utilisés a pu être
mesuré. Enfin, l’utilisation de GRASP dans le cas biobjectif, et sa comparaison avec la
métaheuristique SPEA, a révélé des résultats très encourageants.
Dans la suite, nous allons voir comment tous les travaux présentés dans cette thèse
peuvent être utilisés dans le cadre d’un logiciel d’aide à la décision pour l’étude de la capacité
d’infrastructures ferroviaires.
Description de la plate-forme
expérimentale
Dans les chapitres précédents, nous avons vu que le problème de capacité d’infrastructures
ferroviaires que nous étudions peut se modéliser sous la forme d’un problème de set packing,
et que nous disposons d’algorithmes performants pour résoudre ce problème. Nous allons
maintenant voir que l’ensemble de ces travaux s’inscrivent dans le cadre d’un projet régional
regroupant trois partenaires :
– l’INRETS avec l’Unité de Recherche ESTAS,
– l’UVHC avec l’équipe Recherche Opérationnelle et Informatique du LAMIH,
– et la SNCF avec l’unité Études prospectives Infrastructure (Pôle exploitation) de la
Délégation Régionale Infrastructure de Lille.
Ce projet est encore en cours, et certaines des tâches prévues ne sont pas terminées. Après
avoir indiqué les objectifs visés, nous détaillons ses principales étapes et présentons l’archi-
tecture logicielle considérée pour la plateforme d’expérimentation.
Ces données d’infrastructure sont extraites de fichiers issus d’applications SNCF, ou le cas
échéant saisies manuellement à partir de documents techniques comme les schémas de signa-
lisation, la consigne rose ou le KVB. La figure 6.2 représente l’interface graphique permettant
de saisir une infrastructure ou de la modifier.
À l’issue de cette tâche, quatre fichiers sont produits. Le premier fichier décrit l’infra-
structure et sa signalisation et notamment les limitations de vitesse. Le second fichier décrit
les points d’arrêt et leur durée. Le troisième fichier définit les circulations programmées,
y compris les mouvements haut le pied. Enfin, pour compléter la description de l’offre, un
quatrième fichier donne les contraintes d’équilibre.
Cette étape est maintenant pratiquement terminée, et ne demande plus qu’une validation,
par un expert de la SNCF, des données saisies.
post-traitement pour rendre accessible ces résultats sous une forme plus ergonomique pour
le décideur. Une information plus pertinente est par exemple celle qui permet de se focaliser
sur les ressources critiques ou les périodes où l’exploitation est la plus dense.
Lorsque toutes les circulations d’un problème de faisabilité ont été programmées, il est
important aussi d’apprécier la marge entre les trains pour faire face aux aléas de l’exploitation
(stabilité de la grille horaire, voir section 3.3, page 64). Si au contraire certaines circulations
n’ont pu être programmées, il faut pouvoir identifier les circulations en conflit ainsi que
l’élément du parcours sur lequel se produit le conflit. Les résultats issus des modules d’opti-
misation nécessitent donc des post-traitements qui facilitent l’analyse des solutions produites.
À côté de ces modules d’analyse, un second type de modules est utile à l’interprétation
des résultats : ce sont des modules de simulation. Ils permettent de déterminer le mouvement
complet, et les horaires de réservation des zones, de tous les trains dont le parcours et les
horaires de références ont été calculés par le module de résolution. Ces informations peuvent
ensuite être utilisées pour visualiser une grille horaire à l’aide de représentations graphiques
comme les diagrammes de Gantt d’occupation des zones isolées (voir Figure 6.3) et les dia-
grammes espace-temps. De plus, les parcours des différents trains peuvent être observés sur
le plan de voies de l’infrastructure (voir Figure 6.4). Enfin, un mode simulation permet de
visualiser au cours du temps l’évolution de la position de chacun des trains (voir Figure 6.5).
Si plusieurs de ces modules sont terminées, d’autres sont encore en cours de développement.
SAFIR 1 - PREDIT
1998-1999
SAFIR 2 - GRRT
1999-2000
RECIFE- GRRT
2002-2003
L’architecture logicielle résultante pour le projet RECIFE est présentée dans la figure 6.7.
Afin d’obtenir le modèle que nous avons présenté au chapitre 3, les horaires de réservation
de chacune des zones de l’infrastructure pour chacun des parcours possibles sont nécessaires.
Ces données peuvent être calculées une seule fois pour une infrastructure. Elles sont obtenues
4
Programme National de Recherche et d’Innovation dans les Transports Terrestres
5
Système d’Aide à la Fluidification des cIRculations
à partir des marches de trains déterminées par le logiciel SISYFE (voir Fontaine et Gauyacq
[FG01]). Des modules SAFIR permettent ensuite d’intégrer dans ces horaires les temps de
réservation des zones liés à la signalisation (et donc aux cantons). En effet, pendant ces temps,
même si le train n’occupe pas encore physiquement une zone qu’il a réservé, aucun autre
train ne peut l’utiliser. La conversion des données du format utilisé pour SAFIR au format
RECIFE est réalisée par un module développé par Suray [Sur01]. Tous ces modules ont été
codés en C++ à l’aide des bibliothèques Ilog Views, Solver et Scheduler [ILO01b, ILO01a].
Pour chaque scénario de données d’exploitation (grille horaire initiale, listes saturantes,
préférences, correspondances, . . .) étudié, le modèle en variables binaires correspondant peut
ainsi être généré. Ce travail est réalisé par une API (codée en C++), développée par Cliqué
[Cli02] et Wiart [Wia03]. En outre, celle-ci sert d’interface avec les modules de résolution
(codés en Ada) présentés au chapitre 4, et permet de récupérer les grilles horaires correspon-
dant aux solutions générées.
Ces solutions peuvent ensuite être analysées par différents modules (voir section 6.2.2). De
plus, les modules de simulation issus de SAFIR permettent de calculer le mouvement de tous
les trains de cette grille horaire. Ces informations peuvent ensuite être visualisées grâce à une
application regroupant plusieurs interfaces graphiques (codée en C++). Cette application est
une évolution de celle développée par Marlière [Mar01] pour le projet SAFIR. Elle permet
ainsi de piloter l’ensemble du processus en mettant à jour les données d’infrastructure et
d’exploitation des différents scénarios à étudier, et en réglant les paramètres (temps alloué,
stratégie retenue, composants utilisés, . . .) de la (ou des) méthode(s) de résolution choisie(s).
6.4 Conclusion
Dans ce chapitre, nous avons vu que les travaux présentés dans ce mémoire s’inscrivaient
dans le cadre d’un projet régional. Celui-ci, baptisé RECIFE, vise à développer des outils
d’aide à la décision pour l’étude de la capacité d’infrastructures ferroviaires à l’échelle d’une
gare ou d’un nœud. S’il n’est pas encore terminé, les différents modules développés dans le
cadre de ce projet, et son architecture logicielle globale, ont été décrits.
SISYFE
Marche
des trains
SAFIR Réservation
des zones
API
Solution(s)
Modules
SAFIR Pré-
traitements
Modules
SAFIR
d’analyse
Données de
simulation
Application
graphique Modules
RECIFE
Les travaux que nous avons présentés dans ce mémoire s’inscrivent tous dans une optique
d’évaluation de la capacité d’infrastructures ferroviaires. Ils peuvent cependant être ventilés
selon trois axes :
1. la modélisation du problème que nous proposons,
2. les algorithmes de résolution du problème de set packing que nous avons développés,
3. l’intégration de ces travaux dans un logiciel d’aide à la décision pour l’étude de la
capacité et leur validation sur des applications réelles.
Dans la suite, nous allons récapituler pour chacun de ces axes les possibilités et les limites
du travail accompli. En outre, nous indiquerons ses évolutions possibles et les perspectives
de recherche ou d’application qui en découlent.
La modélisation que nous proposons s’est voulue la plus générale possible, de manière à
pouvoir traiter un grand nombre de situations. La principale contrepartie de ce choix provient
de la complexité de la mise en équations du modèle qui en résulte. En outre, comme pour tout
modèle, il a malgré tout été nécessaire de poser certaines hypothèses simplificatrices. Celles-
ci sont pour l’essentiel liées à la discrétisation du problème. Nous pensons cependant que
ces dernières ne sont pas trop réductrices dans le cadre d’une gestion prévisionnelle de l’uti-
lisation d’infrastructures ferroviaires. Il est par contre fort probable qu’elles se révèleraient
beaucoup trop fortes pour un problème lié à l’exploitation en temps réel de ces mêmes in-
frastructures.
Enfin, même si nous avons essayé de considérer le problème de la manière la plus complète
possible, notre modèle permet uniquement d’évaluer la stabilité d’une solution, et non pas de
déterminer une solution optimale en terme de stabilité. Une modification du modèle intégrant
la stabilité de l’horaire comme l’un des objectifs du problème pourrait s’avérer utile, lors de
la programmation de l’exploitation, pour choisir un plan de transport adéquat. De plus, cela
permettrait de déterminer de manière précise l’impact de l’ajout d’un train supplémentaire
sur une grille horaire.
Nous avons considéré deux types de méthodes. La première, exacte, est basée sur une
méthode de Branch & Cut (Cplex) et l’utilisation de pré-traitements mettant à profit
la structure du problème et les particularités des instances ferroviaires. Nous avons vu au
chapitre 5 que les pré-traitements que nous avons développés s’avèraient très efficaces pour
réduire la taille des problèmes et améliorer la qualité de la borne supérieure obtenue, no-
tamment sur les instances ferroviaires. Plusieurs instances ont d’ailleurs pu être résolues de
manière exacte grâce à ces pré-traitements. Cependant, en raison de la taille des problèmes
considérés dans notre cas, la résolution exacte de ces instances s’est souvent révélée impos-
sible dans un temps raisonnable.
L’implémentation d’une méthode de résolution exacte dédiée pourrait certainement per-
mettre d’améliorer encore la qualité de la borne supérieure. Cette méthode, basée sur une
architecture de Branch & Cut, utiliserait, tout au long du processus, les pré-traitements
que nous avons développés. L’utilisation des techniques de recherche de cliques, notamment,
semble prometteuse. De plus, l’intégration dans cette méthode d’une heuristique perfor-
mante, pourrait permettre d’améliorer la qualité des solutions entières générées. Si cela ne
devrait pas permettre de résoudre toutes les instances que nous avons considérées, la solution
optimale de certaines d’entre elles pourrait ainsi être obtenue.
La seconde méthode, approchée, repose sur une adaptation au problème de set packing
de la métaheuristique GRASP. Plusieurs variantes algorithmiques, inspirées de cette
métaheuristique et de certaines de ses extensions les plus connues, ont ainsi été développées
et testées. Les résultats observés montrent que notre heuristique est efficace sur une large
gamme d’instances du problème. Elle présente une qualité de solution intéressante et re-
lativement stable sur l’ensemble des instances que nous avons traitées. Pour des instances
de grande taille, des solutions de bonne qualité ont ainsi été obtenues dans des temps de
résolution réduits.
En dépit de ces résultats intéressants, plusieurs pistes restent ouvertes pour améliorer
les performances de notre heuristique. Ainsi, il semble que notre procédure reactive GRASP
puisse encore être améliorée, notamment pour l’utiliser plus efficacement avec notre processus
d’apprentissage. De même, le fait de ne plus considérer le chemin complet entre deux solutions
pour le path relinking, mais seulement en partie comme indiqué par Resende et Ribeiro
[RR02], pourrait permettre de réduire le temps utilisé sans pour autant compromettre la
qualité des solutions.
Le développement d’heuristiques, pour le problème de set packing inspirées par d’autres
métaheuristiques, ouvre des perspectives de recherche très nombreuses. Le fait que nous ayons
rendu disponibles sur deux sites web [Del, MCD] l’ensemble des instances aléatoires avec les-
quelles nous avons travaillé, permet ainsi de proposer une série d’instances de référence sur
lesquelles de nouvelles heuristiques pourront être testées et comparées. Nous espérons que
cela encouragera le développement de ce genre de travaux.
En outre, nous avons développé une première extension de cette heuristique au cas biob-
jectif. Celle-ci présente déjà des résultats intéressants, notamment en comparaison avec la
métaheuristique multiobjectif classique SPEA. Ainsi, les solutions obtenues s’avèrent très
proches de la frontière efficace tout en présentant une répartition régulière le long de celle-ci.
Il semble cependant que des progrès peuvent encore être réalisés. Ainsi, une amélioration
possible pourrait venir d’une adaptation plus fine de notre algorithme GRASP au cas biob-
jectif. Certaines phases comme le path relinking pourraient certainement être plus efficaces
en étant utilisées sur des solutions générées pour des directions de recherche différentes. Une
autre possibilité serait de développer une phase de post-optimisation permettant de densifier
l’approximation de la frontière efficace obtenue. Dans ce cadre, une hybridation avec une
méthode évolutionnaire semble être une piste intéressante. Enfin, cette méthode pourrait
être étendue pour pouvoir traiter des problèmes avec plus de deux objectifs.
Dès que les modules d’analyse seront achevés, ce logiciel permettra de réaliser une étude
de capacité complète de la gare de Lille-Flandres. Celle-ci servira ainsi à valider le logiciel
sur une infrastructure telle qu’une gare. Cette validation pratique achèvera les travaux liés
au projet RECIFE. Il serait cependant intéressant de confronter ce logiciel à d’autres in-
frastructures, en France comme dans d’autres pays européens. À terme, le couplage de ce
logiciel avec celui développé actuellement dans le cadre du projet DÉMIURGE, à l’image
des projets CADANS et STATIONS au sein du projet DONS, permettrait de disposer d’un
outil d’aide à la décision utilisable pour l’étude de la capacité de l’ensemble des sous-parties
du réseau ferroviaire français.
Perspective transversale
Pour finir, une perspective transversale aux deux premiers axes est actuellement explorée.
En effet, lors d’expérimentations préliminaires (voir Delorme et al. [DRG01] et Rodriguez et
al. [RDG02]), nous avons montré la complémentarité de notre approche avec une autre, basée
sur un modèle et des techniques de résolution issus de la programmation par contraintes.
Ainsi, par exemple, si notre approche s’avérait plus performante dans le choix des parcours à
attribuer aux trains, celle basée sur la progammation par contraintes permettait de considérer
une discrétisation plus fine des horaires de références.
Une amélioration du processus de résolution pourrait ainsi résulter d’une hybridation de
Blanc-travaux : période pendant laquelle aucune circulation n’est prévue sur une voie
donnée, de façon à permettre l’exécution de la maintenance courante de l’infrastructure. À
la SNCF, cette période est généralement d’au moins 1h50 par voie et par jour.
Cadence : durée du cycle de l’horaire. Un horaire cadencé est conçu de façon à pouvoir
se répéter à la fin de chaque cycle : il ne possède ni début ni fin. Dans la pratique, il va de
soi que l’horaire possède un début et une fin, ce qui rompt bien entendu sa cadence.
Canton : section de voie où figure en amont de chaque point d’entrée un signal. Le
signal précise si le canton est libre ou occupé par un train. Les états possibles d’un signal
sont appelés aspects de signalisation ; chaque aspect est interprété par le mécanicien dans la
façon de de conduire le train.
Haut le pied : train roulant «à vide» entre le dépôt et le lieu de départ d’une «circu-
lation commerciale».
d’un train coı̈ncide partiellement ou totalement avec une ligne ferroviaire bien définie.
Marche d’un train : circulation réelle d’un train caractérisée par son passage à un point
donné, à une vitesse donnée et à une date donnée.
Nœud : point critique du réseau, tels une gare, une bifurcation, une jonction, un point
de croisement, y compris tous les appareils de voie et voies qui y sont rattachés.
Routage : affectation de chacun des trains arrivant dans une zone à un parcours lui
permettant de rejoindre sa destination.
Saturation : 1. état d’un réseau dans lequel il n’est plus possible d’ajouter un train.
2. pratique consistant à introduire dans le réseau une série de trains, dits
saturants, jusqu’à ce qu’il ne soit plus possible de le faire. La capacité
du réseau est définie par le nombre de trains à l’horaire saturé.
Sillon : capacité d’infrastructure requise (voie et horaire) pour faire circuler un train
donné d’un point à un autre à un moment donné (directive 95/19/CE du conseil de l’union
européenne).
Tronçon : partie d’une ligne composée éventuellement de plusieurs voies reliant deux
nœuds du réseau.
Voie banalisée : voie autorisant la circulation des trains dans les deux sens.
Voie libre : fait pour le mécanicien de n’apercevoir que des signaux lui permettant
d’adopter la vitesse maximum autorisée.
[APR99] James Abello, Panos M. Pardalos, et Mauricio G.C. Resende. On maximum clique
problems in very large graphs. Dans J. Abello et J. Vitter, éditeurs, External
memory algorithms and visualization, volume 50 de DIMACS Series on Discrete
Mathematics and Theoretical Computer Science, pages 119–130. American Mathe-
matical Society, 1999.
[Bel97] H. Bellaiche. Recherche sur la saturation des lignes ferroviaires (rapport d’étape
de la phase 1). Rapport technique 2166/ESF/317-97/RA, SYSTRA, France, mai
1997.
[Bor98] Ralf Borndörfer. Aspects of set packing, partitioning, and covering. PhD thesis,
Fachbereich 3 Mathematik der Technischen Universität Berlin, Berlin, Germany,
1998.
[BWZ97] M.R. Bussieck, T. Winter, et U.T. Zimmermann. Discrete optimization in public
rail transport. Mathematical programming, 79 :415–444, 1997.
[CL01] Anne Curchod et Luigi Lucchini. CAPRES : Description générale du modèle.
Rapport technique 788/5 f, LITEP, juin 2001.
[Cli02] Manuel Cliqué. Développement d’une API C++ pour la génération du modèle
SPP appliqué à un problème de faisabilité et de saturation ferroviaire. Rapport
technique RE-02-710-FR, INRETS-ESTAS, 2002.
[CTV98] Jean-François Cordeau, Paolo Toth, et Daniele Vigo. A survey of optimization
models for train routing and scheduling. Transportation Science, 32(4) :380–404,
novembre 1998.
[Deg02] Fabien Degoutin. Problèmes bi-objectifs en optimisation combinatoire et capacité
d’infrastructures ferroviaires. Mémoire de DEA, Université de Valenciennes et du
Hainaut Cambrésis, Valenciennes, France, 2002.
[Del] Xavier Delorme. Instances tests pour le problème de set packing.
http://www3.inrets.fr/~delorme/Instances-fr.html.
[Del00] Xavier Delorme. Optimisation combinatoire et problèmes de capacité d’infrastruc-
ture ferroviaire. Mémoire de DEA, Université de Valenciennes et du Hainaut
Cambrésis, Valenciennes, France, 2000.
Abstract : This thesis deals with a planning problem in railroad infrastructure operation at the
node or station level. In order to determine an offer strategy, having tools for evaluating infrastruc-
ture capacity is important. These tools allow the network limits to be evaluated, and the impact
of proposed modifications to be studied. The main questions considered include the feasibility of
a given timetable, its optimization according to such criteria as the number of trains (saturation),
and its stability evaluation.
A new multiobjective linear model, which is accurate enough to produce practicable timetables
for the studied infrastructures, is proposed for this problem. This model is structured primarily
as two classic combinatorial optimization problems named shortest path and set packing. If resol-
ving shortest path problems can be considered fairly easy, the set packing problem is known to be
NP-hard. Several pre-processing algorithms, and an approximation method based on the GRASP
metaheuristic, dedicated to set packing resolution are proposed. A preliminary extension of this
method to the bi-objective case is also presented. These algorithms were successfully tested on both
randomly generated instances and instances related to the Pierrefitte-Gonesse node. The integra-
tion of this research in a decision support system for evaluating railroad infrastructure capacity
(RECIFE project, in collaboration with the French National Railroad Company) is described.
Discipline : Informatique