Optimisation des moyens dans la recomposition commerciale de dessertes TER

The subject of this work is an integrated optimization approach for timetabling and rolling stock rotation planning in the context of passenger railway traffic. Our approach is based on a hypergraph based integer programming model, which can handle trains composed of multiple heterogeneous self-powered railcars. The method aims at producing a timetable and solving the rolling stock problem given a set of possible passenger trips, a service requirement and a fleet of self-powered railcars. The produced timetable optimizes the production cost and especially the use of railcars. To solve our optimization problem, we use a minimum cost flow problem in a time/space/configuration hypergraph network. These models are used to handle effectively constraints related to coupling and decoupling railcars. To reduce the size of the generated model, we propose a reduced-cost fixing method based on a surrogate relaxation of the flow constraints. This relaxation allows to produce a relaxed model with a similar structure, but significantly less variables and constraints. We are able to produce both lower and upper bounds for the initial problem. These bounds allow to apply implicitly reduced-cost fixing techniques to the initial model. The obtained reduced version of the initial model is then solved by an MIP solver. We present some results based on several French regional railway traffic case studies to show that our methods scales to real-life problems.Les travaux de la présente thèse traitent d’une approche d’optimisation intégrée pour la planification du matériel roulant et l’optimisation des grilles horaires dans le contexte du trafic ferroviaire de passagers. Notre approche repose sur un modèle de programmation entière basé sur un hypergraphe qui autorise des configurations composées de rames matérielles hétérogènes. L’objectif est de trouver une grille horaire et optimiser l’utilisation des rames étant donnés une demande voyageur, les besoins du service et le parc des rames matérielles. Les grilles produites permettent une optimisation du coût de production et un usage optimal des rames. Notre approche repose sur l’utilisation d’un flot de coût minimum sur un hypergraphe espace/temps/configuration. Nous nous servons de ces modèles pour gérer efficacement les contraintes liées aux coupes et accroches des configurations. Nous avons proposé un algorithme de filtrage sur les coûts réduits basé sur une relaxation surrogate des contraintes de flot pour réduire la taille du modèle généré. Cette relaxation débouche sur un modèle relâché avec une structure similaire et un nombre de variables et de contraintes sensiblement réduit. Nous sommes capables de produire à la fois une borne inférieure et une borne supérieure pour le problème initial. Ces bornes permettent l’application implicite de techniques de filtrage sur le modèle initial. Le modèle réduit est résolu par un solveur MIP. Nous présentons des résultats basés sur des études de plans de transport ferroviaire régional pour montrer que notre modèle passe à l’échelle sur des problèmes réels