Thèse : Génération et résolution de problèmes réalistes de conception de réseaux de transport à grande échelle par agrégation de commodités

Résumé

Les réseaux de transport de marchandises constituent un élément essentiel des chaînes logistiques modernes, mais ils sont confrontés à des défis croissants liés à l’augmentation des volumes d’échanges, à de nouvelles exigences de service, ainsi qu’à des contraintes de développement durable. Dans ce contexte, les transporteurs doivent prendre des décisions de planification complexes pouvant être assistées par la résolution de problèmes d’optimisation. Cette thèse s’intéresse au Service Network Design Problem (SNDP) et à son extension temporelle, le Scheduled Service Network Design Problem (SSNDP), deux problèmes combinatoires fortement NP-difficiles visant à optimiser conjointement l’allocation des services de transport et le routage des commodités dans les réseaux de transport. Ce travail répond à deux problèmes majeurs de la littérature : le manque d’instances de référence réalistes et accessibles publiquement, ainsi que la faible capacité de passage à l’échelle des méthodes exactes existantes lorsqu’elles sont confrontées aux très grands nombres de commodités rencontrées en pratique. Notre première contribution est un générateur open source d’instances capable de produire des instances de grande taille du SNDP et du SSNDP présentant des structures de type hub-and-spoke. À l’aide de métriques issues de l’analyse des réseaux complexes (Complex Network Analysis), nous montrons que les réseaux générés reproduisent mieux les caractéristiques structurelles des systèmes réels de transport de marchandises que les jeux d’instances de référence existants. Nous proposons ensuite une nouvelle relaxation du SSNDP fondée sur l’agrégation de commodités. En étudiant différentes stratégies d’agrégation, nous identifions des configurations permettant de réduire significativement la taille des modèles tout en conservant des bornes duales pertinentes. Des inégalités valides visant à renforcer la relaxation ainsi qu’une heuristique de réparation permettant de reconstruire des solutions primales réalisables sont également développées. Des expérimentations numériques menées sur des instances comportant jusqu’à 30 000 commodités démontrent l’efficacité de notre approche. Enfin, notre dernière contribution consiste en un schéma théorique de désagrégation itérative exacte basé sur l'agrégation partielle des commodités, ainsi qu'une implémentation heuristique de ce dernier. En affinant progressivement les solutions agrégées, l'approche heuristique permet d'explorer le compromis entre des considérations contradictoires: taille du modèle, temps de résolution, qualité de la borne duale. Dans l’ensemble, cette thèse apporte de nouveaux outils de génération d’instances ainsi que des méthodes d’optimisation basées sur l'agrégation de commodités, participant à étendre la taille et le réalisme des cas de conception de réseaux de services pouvant être résolus.

Abstract

Freight transportation networks are critical to modern supply chains but face growing challenges due to increasing trade volumes, higher service-level expectations, as well as sustainability concerns. In this context, carriers have to deal with complex planning decisions that can be assisted by solving optimization problems. This thesis focuses on the Service Network Design Problem (SNDP) and its time-dependent extension, the Scheduled Service Network Design Problem (SSNDP), NP-hard combinatorial problems that aim to jointly optimize the allocation of transportation services and shipment routing in freight transportation networks. The work addresses two major gaps in the literature: the lack of realistic and publicly available benchmark instances, and the limited scalability of existing exact solution methods when dealing with the large numbers of commodities encountered in practice. Our first contribution is an open-source instance generator capable of producing large-scale SNDP and SSNDP benchmark instances with hub-and-spoke structures. Using metrics from Complex Network Analysis, the generated networks are shown to better reflect the structural characteristics of real freight transportation systems than existing benchmarks. We then propose a new commodity aggregation-based relaxation for the SSNDP. Exploring varied aggregation strategies, we identify configurations that significantly reduce the model size of the problem while providing meaningful dual bounds. Valid inequalities to strengthen the relaxation and a repair heuristic scheme to recover primal solutions are also formulated. Computational experiments on instances containing up to 30,000 commodities demonstrate the potential of these approaches for solving large-scale SSNDP instances. Finally, our last contribution is a theoretical exact iterative disaggregation scheme based on partial commodity aggregation, together with a practical heuristic implementation. By progressively refining aggregated solutions, the practical heuristic approach enables the exploration of the tradeoff between competing considerations: model size, computational tractability, and dual bound quality. Overall, this thesis contributes new benchmark-generation tools and commodity aggregation-based optimization approaches that help extend the scale and realism of service network design instances that can be addressed.