Nouvelle approche d'optimisation pour le problème d'affectation des unités ferroviaires

Nous nous intéressons au problème d’affectation des unités ferroviaires. Il s’agit d’un problème de couverture, où des voyages prévus au préalable doivent être associés à des unités ferroviaires. Nous avons travaillé sur ce problème sur un horizon d’une journée, en cherchant à obtenir une solution périodique qui puisse être appliquée sur un intervalle de temps plus long. L’assignation doit respecter un certain nombre de contraintes, notamment la disponibilité des différents types d’unités, la périodicité quotidienne des stationnements dans les dépôts, et des contraintes de couplage et de découplage des unités selon des règles prédéfinies. Ce problème peut être résolu efficacement en découpant en deux phases distinctes : calcul des compositions de trains optimales en ignorant certaines contraintes puis affectation des trains à ces compositions. Cette approche a notamment été utilisée par Giro avec lesquels nous avons travaillé au cours de cette maîtrise. Cette approche heuristique ne permet cependant pas de connaître l’erreur par rapport à la valeur optimale du problème. Nous avons donc cherché à modéliser ce problème en une seule phase, par un problème de plus court chemin dans un graphe avec contraintes supplémentaires, où chaque chemin décrit un enchaînement potentiel de voyages couverts par une unique unité. Nous résolvons ce modèle linéaire par génération de colonnes, avant d’utiliser un solveur en nombres entiers sur les colonnes retenues. Nous avons travaillé sur des instances construites aléatoirement et sur des instances fournies par la SNCF. La plus grosse de nos instances inclut 367 voyages à couvrir, répartis entre 26 gares. Les temps de résolution sur cette instance et celles de taille comparable nous ont poussé à utiliser des techniques heuristiques pour accélérer la résolution du problème en nombres entiers. Nous présentons nos résultats, comparés avec ceux de Giro, et avec les meilleures bornes que nous connaissons pour ce problème. Nous présentons enfin les limites de notre modèle, et les pistes d’amélioration de notre méthode.