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.

Abstract

We interested ourselves in the problem of allocating rail units. This is a hedging problem, where pre-scheduled trips have to be associated with railway units. We have worked on this problem over a one-day horizon, seeking to obtain a periodic solution that can be applied over a longer time interval. The assignment must respect a number of constraints, including the availability of different types of units, the daily periodicity of parking in depots, and constraints on coupling and uncoupling units according to predefined rules. This problem can be solved efficiently by dividing it into two distinct phases: calculating optimal train compositions while ignoring certain constraints, and then assigning trains to these compositions. This approach was used in particular by Giro, with whom we worked during the course of this master’s degree. However, this heuristic approach does not allow us to know the error with respect to the optimal value of the problem. We therefore sought to model this problem in a single phase, by means of a shortest path problem in a graph with additional constraints, where each path describes a potential sequence of journeys covered by a single unit. We solve this linear model by column generation, before using an integer solver on the selected columns. We worked on randomly constructed instances and on instances provided by SNCF. The largest of our instances included 367 trips to cover, spread over 26 stations. Solving times on this instance and others of comparable size prompted us to use heuristic techniques to speed up solving the integer problem. We present our results, compared with those of Giro, and with the best bounds we know for this problem. Finally, we present the limitations of our model, and suggest ways of improving our method.