Soutenance de thèse de EL GHAZI Yousra


Titre de thèse

Conception et optimisation de réseaux de transport maritime régulier à l'aide de la programmation par contraintes

Design and Optimization of Liner Shipping Networks Using Constraint Programming

Date

3 décembre 2026 à 9h00

Adresse

salle des thèses : Bâtiment 36, 52 avenue Escadrille Normandie-Niemen 13397 Marseille, Salle des thèses

Ecole doctorale

Mathématiques et Informatique de Marseille

Specialité

Informatique

Etablissement

Aix-Marseille Université

Mots clés

programmation par contraintes,optimisation combinatoire,transport maritime régulier,conception de réseaux maritimes,routage des marchandises,

Keywords

Constraint Programming,Combinatorial Optimization,Liner Shipping,Liner Shipping Network Design,Cargo Routing,

Jury

Jury de thèse
Qualité Nom Etablissement
Professeur M. HABET Djamal Aix Marseille Université
Chargé de recherche M. DE GIVRY Simon MIAT, INRAE Toulouse
Professeur M. VISMARA Philippe L'Institut Agro Montpellier
Professeur M. TERRIOUX Cyril Aix Marseille Université
Professeur Mme SOLNON Christine INSA Lyon

Résumé de la thèse

Le transport maritime régulier est l'un des principaux modes d'échange du commerce international en reliant les continents à travers un réseau mondial connectant plus de 900 ports à conteneurs. Les principaux armateurs déploient chacun une flotte de plus de 700 navires de tailles très variées afin de desservir plus de 200 lignes maritimes. Chaque ligne constitue une rotation cyclique où les navires visitent une séquence fixe de ports selon un horaire régulier. L'interconnexion de ces rotations par des ports communs forme un réseau global permettant d'acheminer la demande de marchandises entre leurs origines et leurs destinations.

La conception de ce réseau représente un problème décisionnel majeur pour les armateurs. Ce problème d'optimisation combinatoire, reconnu pour sa complexité NP-difficile et formalisé dans la littérature sous le nom de Liner Shipping Network Design Problem, combine trois sous-problèmes déjà difficiles lorsqu'ils sont traités séparément, la conception de la structure des rotations, l'affectation optimale des navires aux rotations, et le routage optimal des marchandises sur le réseau formé.

Face à cette complexité et à la forte interdépendance entre ces décisions, combinées à l'évolution des besoins du secteur, la littérature a progressivement eu recours à des hypothèses simplificatrices pour rendre le problème traitable. Les travaux existants s'appuient principalement sur des formulations en programmation linéaire en nombres entiers, associées à des méthodes exactes de décomposition ou à des métaheuristiques.

L'objectif de cette thèse est de développer un outil d'aide à la décision permettant de concevoir et d'optimiser des réseaux de transport maritime en intégrant simultanément plusieurs de ces relâchements d'hypothèses, souvent traités de manière isolée dans la littérature. Compte tenu de la complexité du problème et de l'évolution des besoins et des contraintes, nous proposons dans ce travail d'étudier, à notre connaissance pour la première fois, l'intérêt de la programmation par contraintes pour la modélisation et la résolution de ce problème, en exploitant sa flexibilité et sa modularité afin de construire des modèles facilement adaptables aux différents cas d'utilisation du problème, sans remettre en cause l'architecture générale du modèle.

À partir de ce cadre, trois contributions principales sont développées pour la modélisation et la résolution du problème. La première repose sur une formulation intégrée regroupant l'ensemble des décisions du problème au sein d'un même modèle. La deuxième exploite la modularité de la programmation par contraintes pour isoler et étudier en profondeur le sous-problème de routage des marchandises, dont les décisions conditionnent directement l'utilisation effective du réseau et la qualité des choix de conception. La troisième contribution propose une approche par décomposition afin de dépasser les limites de l'approche intégrée et de traiter des instances de taille réaliste. Les décisions y sont réparties entre plusieurs modèles complémentaires, chacun prenant en charge une partie du problème, tout en maintenant des échanges d'informations afin de construire une solution globale cohérente.


Thesis resume

Regular liner shipping is one of the main modes of international trade, connecting continents through a global network linking more than 900 container ports. Major shipping companies each deploy a fleet of more than 700 vessels of widely varying sizes to operate more than 200 liner shipping services. Each service forms a cyclic rotation in which vessels visit a fixed sequence of ports according to a regular schedule. The interconnection of these rotations through common ports forms a global network enabling the transportation of cargo demands between their origins and destinations.

The design of this network represents a major decision-making problem for shipping companies. This combinatorial optimization problem, recognized as NP-hard and formalized in the literature as the Liner Shipping Network Design Problem, combines three subproblems that are already difficult when addressed separately: the design of the rotation structure, the optimal assignment of vessels to rotations, and the optimal routing of cargo through the resulting network.

Faced with this complexity and the strong interdependence among these decisions, combined with the evolving needs of the sector, the literature has progressively relied on simplifying assumptions to make the problem tractable. Existing studies are mainly based on mixed-integer linear programming formulations, combined with exact decomposition methods or metaheuristics.

The objective of this thesis is to develop a decision-support tool for designing and optimizing liner shipping networks by simultaneously relaxing several of these assumptions, which are often addressed separately in the literature. Given the complexity of the problem and the evolution of needs and constraints, we propose in this work to study, to the best of our knowledge for the first time, the potential of constraint programming for modeling and solving this problem, exploiting its flexibility and modularity in order to build models easily adaptable to the different use cases of the problem, without modifying the overall architecture of the model.

Based on this, three main contributions are developed for modeling and solving the problem. The first is based on an integrated formulation that combines all the decisions of the problem within a single model. The second exploits the modularity of constraint programming to isolate and study in depth the cargo routing subproblem, whose decisions directly determine the effective use of the network and the quality of the design choices. The third contribution proposes a decomposition approach to overcome the limitations of the integrated approach and address realistically sized instances. The decisions are distributed among several complementary models, each handling a specific part of the problem, while maintaining information exchanges in order to construct a coherent global solution.