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

Jusseau, Joaquim (2026). 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. Mémoire de maîtrise électronique, Montréal, École de technologie supérieure.

Prévisualisation

PDF Télécharger (563kB) | Prévisualisation

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.

Titre traduit

Decomposition and sampling methods for large-scale network design problems in semi-flexible transportation systems

Résumé traduit

This master thesis addresses large-scale two-stage network design problems. In this class of problems, a first-stage decision consists in designing an infrastructure (a network) connecting several sites, while the second-stage decision consists in routing a set of demands over the network previously built. Such problems arise notably in transportation and logistics, and are characterized by a strong interaction between design and routing decisions. For large-scale instances, which involve routing a large number of demands, exact solution methods struggle to converge to the optimal solution.

The objective of this work is to develop approaches that yield high-quality solutions, together with guarantees on the optimal value, while preserving good scalability. Two complementary contributions are proposed.

The first contribution strengthens exact methods by introducing new lower bounds that exploit the integer structure of the problems under study. These bounds reduce the search space and improve the performance of branch-and-bound algorithms.

The second contribution introduces a paradigm shift through a demand sampling approach. The idea consists in approximating the original problem using only a random subset of demands, suitably rescaled. We show that this deterministic problem can be reinterpreted within a stochastic framework, which allows us to leverage the tools of stochastic programming to obtain statistical estimators of the optimal value, as well as valid lower and upper bounds.

The proposed approaches are analyzed theoretically and evaluated experimentally on instances from the literature, demonstrating their effectiveness and their ability to handle large-scale instances.

Type de document:	Mémoire ou thèse (Mémoire de maîtrise électronique)
Renseignements supplémentaires:	"Mémoire présenté à l'École de technologie supérieure comme exigence partielle à l'obtention de la maîtrise avec mémoire en génie des technologies de l'information". Comprend des références bibliographiques (pages 113-117).
Mots-clés libres:	conception de réseaux, TSP-GL, MUFND, décomposition de Benders, méthodes d’échantillonnage
Directeur de mémoire/thèse:	Directeur(-trice) Errico, Fausto
Programme:	Maîtrise en ingénierie > Génie des technologies de l'information
Date de dépôt:	18 juill. 2026 14:54
Dernière modification:	24 juill. 2026 14:38
URI:	https://espace.etsmtl.ca/id/eprint/4011

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt