Conclusion et perspectives
Le travail de recherche réalisé au cours de ce stage a donc permis de valider l'aptitude des modèles
issus de l'optimisation combinatoire à représenter des problèmes ferroviaires réels. Une modélisation
des noeuds ferroviaires permettant d'évaluer la faisabilité du passage de trains, dont l'horaire a été
établi, a ainsi pu être proposée. Elle trouve donc tout son intérêt dans le cadre d'une étude de capacité
basée sur une saturation maximale de la grille horaire sur la fenêtre temporelle considérée et donc dans
le domaine de la planification ferroviaire.
Dans la première partie, plusieurs méthodes de résolution (exactes ou approchées) ont pu être testées sur
un problème d'optimisation combinatoire courant proche du problème étudié : le Set Covering Problem. Une
comparaison de la qualité des solutions obtenues par GRASP et des temps de résolutions nécessaires a ainsi
pu être effectuée avec les résultats obtenus par des algorithmes gloutons et par une méthode exacte de
Branch & Bound. De même, la qualité de nos résultats a pu être mesurée vis à vis des résultats rencontrés
dans la littérature.
Cette analyse comparative a permis de mettre en évidence les aptitudes de la métaheuristique GRASP. Pour
des instances de grande taille, des solutions de bonne qualité ont ainsi été obtenues dans des temps de
résolution raisonnables.
Dans la seconde partie, nous avons pu montrer que le problème de la faisabilité du passage des trains
dans un noeud ferroviaire pouvait être modélisé sous la forme d'un Set Packing Problem. La métaheuristique
GRASP peut donc être utilisée pour résoudre ce problème.
Une application sur une situation réelle connue pour sa difficulté, celle du noeud de Pierrefitte-Gonesse,
a ainsi pu être réalisée grâce aux données issues du simulateur SISYFE. Les résultats obtenus lors de
cette expérimentation ont confirmé l'intérêt de la méthodologie employée pour les problèmes de ce type.
Toutefois, les instances considérées étaient de taille assez réduite et une résolution exacte de problèmes
de cette dimension par des méthodes exactes est encore envisageable.
Ainsi, il serait tout de même intéressant d'évaluer son comportement sur des problèmes de plus grande
taille correspondant principalement à des fenêtres temporelles plus étendues. De même, l'étude d'autres
noeuds ferroviaires en voie de saturation comme le triangle d'Ostricourt à Douai ou le noeud Lillois est
prévue.
Dans ce cadre, une comparaison des résultats obtenus avec GRASP et avec des algorithmes exacts pourrait
être réalisée afin de mesurer les limites d'une résolution exacte. Pour cela, le recours à un code de
calculs général comme Cplex et à un algorithme dédié comme le Branch & Cut proposé par les chemins de fer
néerlandais est envisagé.
De plus, un premier retour d'expérience permettrait sans doute d'améliorer la valeur des paramètres
utilisés pour GRASP afin d'en augmenter l'efficacité.
Enfin, l'expérience acquise grâce aux premières expérimentations devraient permettre d'améliorer le
modèle. De même, différentes évolutions du modèle pourraient être envisagées afin de compléter la réponse
obtenue par un algorithme exact avec le modèle actuel.
Ainsi, dans les cas où la faisabilité du passage des trains est constatée, l'optimisation multicritère [Visee et al.98]
du passage des trains dans le but de fluidifier le trafic pourrait être étudiée. Le choix
d'indicateurs de mesure pertinents pour évaluer et comparer les différentes solutions envisageables serait
alors très important.
Dans le cas contraire, il faudrait s'intéresser aux actions à entreprendre afin de permettre le passage
des trains prévus. Il y a alors deux types de modifications envisageables : celles changeant la grille
d'horaire et celles impliquant une modification des infrastructures.