Introduction

Ce mémoire présente le travail de recherche que j'ai réalisé dans le cadre de mon stage de DEA Automatisation des Systèmes Industriels et Humains (ASIH) à l'Université de Valenciennes et du Hainaut-Cambrésis en collaboration avec l'Institut National de Recherche sur les Transports et leur Sécurité (INRETS) de Villeneuve-d'Ascq.
Ce travail aborde la problématique de la capacité d'une infrastructure ferroviaire. Cette problématique trouve tout son intérêt dans le domaine de la planification, notamment dans le contexte actuel de diminution des ressources financières et d'accroissement prévisible du trafic durant les prochaines années.

La notion de capacité d'une infrastructure ferroviaire intervient dans plusieurs questions telle que l'étude de la faisabilité du passage des trains prévus dans cette infrastructure, la fluidification de ce passage ou la programmation des travaux, mais aussi dans le cadre de la tarification des sillons ou pour évaluer l'intérêt de modifications de l'infrastructure. Nous avons travaillé durant cette année sur le problème de la faisabilité du passage des trains dans un noeud par rapport à un horaire établi. La modélisation retenue pour cette étude s'inspire de travaux antérieurs publiés et relève du domaine de l'optimisation combinatoire.
Après un court rappel de problèmes classiques rencontrés en optimisation combinatoire (Set Covering, Node Packing et Set Packing Problems) et des méthodes existantes permettant de les résoudre, nous nous intéressons plus en détail à la résolution du Set Covering Problem. En effet, celui-ci a fait l'objet d'une littérature importante et plusieurs méthodes de résolution ont été évaluées sur des instances numériques de référence. Nous étudions ainsi le comportement et les performances d'une heuristique de type glouton, d'une métaheuristique stochastique (GRASP) et d'une méthode exacte de Branch & Bound.

Les résultats relevés lors de nos expérimentations sont ensuite présentés et commentés dans l'esprit d'une analyse comparative. De plus une confrontation avec les meilleurs résultats connus dans la littérature est effectuée. Au vu de cette campagne expérimentale, il apparaît que la métaheuristique GRASP fournit des résultats de bonne qualité tout en conservant des temps de résolution acceptables sur les instances de grande taille. Nous retenons donc pour la suite du travail la configuration et le réglage des paramètres de GRASP qui ont conduit aux meilleurs performances de la méthode approchée.
L'intérêt de GRASP étant validé, nous pouvons nous intéresser au problème de capacité ferroviaire. Après une brève présentation du problème, nous étudions les travaux réalisés par les chemins de fer néerlandais dans le cadre d'un projet visant à aider la planification d'une grille horaire sur l'ensemble du réseau des Pays-Bas, et plus spécialement la partie permettant de gérer le problème du routage des trains dans une gare. Le modèle qu'ils proposent est un Node Packing.

Pour finir, nous présentons une adaptation de ce modèle permettant de l'appliquer à une situation réelle française ainsi que sa résolution à l'aide de la métaheuristique GRASP. Dans ce but, nous avons retenu une modélisation du problème sous la forme d'un Set Packing qui se révèle plus adaptée dans le cadre d'une résolution approchée. De même, nous présentons une adaptation de GRASP à ce type de problème. Une première validation de ce travail a été obtenue sur base d'une expérimentation réalisée sur le noeud ferroviaire de Pierrefitte-Gonesse en considérant des situations de trafic réelles et fictives. Nous pouvons ainsi retenir les premiers résultats jugés pertinents vis-à-vis du vécu et les possibilités d'évolutions rapides de l'outil actuel vers un outil d'analyse de la saturation.
Notons que certains choix opérés lors du déroulement du travail proviennent du fait que nous ne disposions pas d'un code de calcul commercial. à défaut de ceci, nous avons travaillé avec des codes du domaine public qui, bien que performants, n'offrent pas tout le confort et les fonctionnalités attendues pour ce type d'étude.