Abstract FR:

La génération de colonnes a montré, cette dernière décennie, une grande efficacité dans la construction d'horaires de personnels roulants. Cependant, son application à la SNCF soulève d'importantes difficultés dues à la complexité du sous-problème du plus court chemin avec contraintes supplémentaires. Les techniques de programmation dynamique ne permettent pas d'atteindre les niveaux de rapidité rencontres dans la littérature, et obligent à contraindre sévèrement le nombre d'appels au sous-problème. Dans ce contexte, les techniques d'initialisation courantes condamnent l'approche dans son ensemble, et incitent à construire des heuristiques d'initialisation basées sur une utilisation originale du graphe du sous-problème. Ce principe d'hybridation des méthodes de décomposition par des heuristiques est également applique à la résolution d'un problème d'allocation stochastique de ressources (yield management) résolu par relaxation lagrangienne et algorithme de sous-gradient. L’amélioration de la qualité des solutions initiales accroit la vitesse de convergence et la stabilité de l'algorithme face aux problèmes numériques posés à la SNCF. En outre, les méthodes de décomposition et leurs algorithmes de résolution sont eux-mêmes enrichis : ainsi les principes de branch and price sont adaptés à la résolution d'un problème de couverture d'ensemble avec séparation sur les variables plutôt que sur les connexions. L’algorithme de sous-gradient est enrichi de bornes inférieures originales qui offrent un meilleur contrôle de la qualité de la solution. L’ensemble de nos propositions sont assorties d'expérimentations et participent à des projets industriels menés aujourd'hui à la SNCF