Heuristiques et méthodes de décomposition appliquées à l'optimisation commerciale et technique à la SNCF / Sémi Gabteni ; sous la direction de Vangelis Paschos

Date :

Format : 189 p

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : français / French

Transports ferroviaires

Optimisation combinatoire

Gestion d'entreprise

Paschos, Vangelis T. (Directeur de thèse / thesis advisor)

Université Paris Dauphine-PSL (1968-....) (Organisme de soutenance / degree-grantor)

Relation : Heuristiques et méthodes de décomposition appliquées à l'optimisation commerciale et technique à la SNCF / Sémi Gabteni ; sous la direction de Vangelis Paschos / , 1999

Relation : Heuristiques et méthodes de décomposition appliquées à l'optimisation commerciale et technique à la SNCF / Sémi Gabteni ; sous la direction de Vangelis Paschos / Grenoble : Atelier national de reproduction des thèses , 1999

Résumé / Abstract : 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