Optimisation des moyens dans la recomposition commerciale de dessertes TER

Abstract

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.