Méthodes de décomposition et d’échantillonnage pour les problèmes de conception de réseaux à grande échelle dans le cadre des systèmes de transport semi-flexibles

Résumé

Ce mémoire porte sur les problèmes de conception de réseaux à deux niveaux à grande échelle. Dans ce type de problème, un premier niveau de décision consiste à concevoir une infrastructure (un réseau) reliant plusieurs sites entre eux, tandis que le second niveau consiste à router un ensemble de demandes sur le réseau précédemment construit. Ces problèmes apparaissent notamment dans les domaines du transport et de la logistique, et se caractérisent par une forte interaction entre les décisions de conception et de routage. Pour les instances de grande taille, qui impliquent de router un grand nombre de demandes, les méthodes de résolution exactes peinent à converger vers la solution optimale. L’objectif de ce travail est de développer des approches permettant d’obtenir des solutions de haute qualité, accompagnées de garanties sur la valeur optimale, tout en conservant une bonne capacité de passage à l’échelle. Deux contributions complémentaires sont proposées. La première renforce les méthodes exactes par l’introduction de nouvelles bornes inférieures exploitant la structure entière des problèmes étudiés. Ces bornes permettent de réduire l’espace de recherche et d’améliorer les performances des algorithmes de type séparation et évaluation. La seconde introduit un changement de paradigme via une approche par échantillonnage de la demande. L’idée consiste à approximer le problème original à partir d’un sous-ensemble aléatoire de demandes, convenablement remis à l’échelle. Nous montrons que ce type de problème déterministe peut être réinterprété dans un cadre stochastique, ce qui permet de mobiliser les outils de la programmation stochastique afin d’obtenir des estimateurs statistiques de la valeur optimale, ainsi que des bornes inférieures et supérieures valides. Les approches proposées sont analysées théoriquement et évaluées expérimentalement sur des instances issues de la littérature, démontrant leur efficacité et leur capacité à traiter des instances de grande taille.

Date	26 juin 2026
langue originale	Français
Établissement diplômant	École de technologie supérieure
Superviseur	Fausto Errico (Directeur(-trice))