Offre de thèse: Méthodes itératives d'agrégation et désagrégation des commodités pour les problèmes

Enjeux, motivation et état de l'art

Le transport de marchandises est un maillon clé de notre économie et de nos sociétés, et ce pour de multiples raisons [5]. Il est par exemple un rouage essentiel dans la production et la distribution de produits finis vers les marchés de consommation, mais provoque également des externalités négatives telles que: la congestion du trafic, la pollution atmosphérique, les émissions de gaz à effet de serre, etc. Pour toutes ces raisons, il est essentiel d'optimiser la prise de décision liée aux activités de transport de marchandises. Ces dernières s'articulent généralement en trois segments: la collecte et la livraison des commodités en zones urbaines et péri-urbaines sur des réseaux de courtes distances connectant les origines/destinations vers/depuis des centres de distribution, i.e. first-mile delivery et last-mile delivery, et le transport interurbain des commodités réalisé sur des réseaux longues distances connectant les centres de distribution, i.e. middle-mile delivery. Deux familles de problèmes sont utilisées pour modéliser et assister la prise de décision sur ces différents segments: les problèmes de tournées de véhicule et les problèmes de conception de réseau de services. Dans cette thèse, nous nous intéressons à la deuxième famille de problèmes.

Les problèmes de conception de réseau de services - ou Service Network Design (SND) [6] -  visent à optimiser l'utilisation d'un système de transport pour répondre aux demandes des clients tout en respectant une qualité de service convenue. Les modèles induits visent à déterminer conjointement (i) le trajet réalisé par les marchandises et (ii) l'utilisation des véhicules nécessaires à leur transport, tout en respectant un certain nombre de contraintes et en minimisant différents coûts. La minimisation de ces coûts passe par une consolidation efficace des marchandises, c'est-à-dire un taux de remplissage élevé des véhicules, et une réduction du nombre de véhicules requis. Bien que la consolidation des marchandises passe par une synchronisation des expéditions dans l'espace et le temps, le SND est formulé sur un réseau statique qui reflète uniquement la dimension physique du transport, et caractérise donc une utilisation agrégée des véhicules. Pour pallier à cette approximation, le Scheduled Service Network Design (SSND) est formulé sur un graphe spatio-temporel permettant de caractériser à la fois les composantes physiques et temporelles des opérations de transports. Cette variante est notoirement plus difficile à résoudre que la version statique et a connu un intérêt croissant de la communauté scientifique ces dernières années [3,4,7].

Malgré les nombreux progrès réalisés dans le développement d'algorithmes pour le problèmes de SND, il existe un écart dimensionnel significatif entre les instances rencontrées en pratique et celles pouvant être résolues à l'optimalité, que ce soit par les méthodes ad-hoc ou les solveurs génériques. Pour surmonter les difficultés de passage à l'échelle, une piste de recherche prometteuse repose sur le développement de techniques d'agrégation/désagrégation itératives. L'agrégation permet la construction d'un modèle plus simple et de dimension réduite qui représente une relaxation du problème original. La résolution du modèle agrégé permet de trouver une borne inférieure au problème original, mais potentiellement non réalisable en raison des approximations effectuées. La désagrégation de l'information améliore la qualité des approximations, et peut donc être utilisée pour converger vers une solution réalisable, et donc optimale, du problème original. Une contribution algorithme majeure et récente est la méthode de découverte par discrétisation dynamique - ou Dynamic Discretization Discovery (DDD) [3]. Cette méthode itérative d'agrégation/désagrégation atténue l'impact de la discrétisation temporelle, un paramètre avec une influence importante à la fois sur la taille des instances et la qualité des solutions produites par le modèle mathématique de SND.

Objectifs de recherche

Cette thèse ambitionne de proposer des solutions algorithmiques pour atténuer l'impact d'un autre paramètre avec une influence majeure sur la taille et la difficulté des instances de SND: le nombre de commodités. Dans un contexte industriel, ce nombre peut-être extrêmement élevé - plus de 30 000 commodités à transporter dans les instances transmises par notre partenaire industriel. Néanmoins, à notre connaissance les instances proposées dans la littérature ne considèrent pas plus de 2000 commodités [8]. Il existe peu de contributions algorithmiques basées sur l'agrégation/désagrégation des commodités, et celles-ci ne s'appliquent qu'à des variantes du problème cœur [1,2].

Le but de cette thèse est de développer des méthodes itératives exactes d’agrégation/désagrégation des commodités contribuant au passage à l'échelle lors de la résolution du problème de SND. La première étape consistera à résoudre la version statique du problème pour les réseaux de distribution en étoile (i) qui sont très répandus dans le contexte du transport interurbain longue distance, et (ii) dont les structures spécifiques peuvent être exploitées dans la conception des solutions algorithmiques. La poursuite de la thèse consistera à étendre les méthodes proposées pour des extensions impliquant (i) des graphes spatio-temporels et/ou (ii) des réseaux de distributions généraux. 

La définition d’instances de benchmark, disponibles en open-access, permettra de mesurer la performance des solutions algorithmiques proposés et de les comparer avec les méthodes de l'état de l'art. Les méthodes seront également éprouvées sur des jeux de données réalistes communiqués par notre partenaire industriel.

Environnement de thèse

La thèse s'inscrit dans le projet ANR AD-Lib (An Aggregation-Disaggregation LIBrary for sequential decision models) qui est mené par un consortium regroupant l'INRIA de l’Université de Bordeaux, le LAAS-CNRS, et la Toulouse Business School. Des échanges sont également prévus avec la Quinlan School of Business de l'université de Loyola (Chicago).

Encadrants

• Simon Belieres, professeur assistant, Toulouse Business School, France
• Sandra Ulrich Ngueveu, maître de conférences HDR, Toulouse INP, LAAS-CNRS, France

Profil de candidat(e) recherché(e)

• Elève-ingénieur(e) ou étudiant(e) en maitrise ou master en recherche opérationnelle ou toutes disciplines connexes (Bac +5)
• Aptitudes en programmation informatique - idéalement C/C++

Documents demandés

Relevés de notes, CV, et lettre de motivation

Pour postuler

Transmettre les documents demandés à s.belieres@tbs-education.fr

Date limite pour postuler

Dès maintenant et jusqu'à ce que le poste soit pourvu

Date prévue de début

1er Septembre 2023

Références

[1] Belieres, S., Hewitt, M., Jozefowiez, N., Semet, F., & Van Woensel, T. (2020). A Benders decomposition-based approach for logistics service network design. European Journal of Operational Research, 286(2), 523-537.

[2] Belieres, S., Hewitt, M., Jozefowiez, N., & Semet, F. (2022). Meta partial benders decomposition for the logistics service network design problem. European Journal of Operational Research, 300(2), 473-489.

[3] Boland, N., Hewitt, M., Marshall, L., & Savelsbergh, M. (2017). The continuous-time service network design problem. Operations research, 65(5), 1303-1321.

[4] Boland, N., Hewitt, M., Marshall, L., & Savelsbergh, M. (2019). The price of discretizing time: a study in service network design. EURO Journal on Transportation and Logistics, 8(2), 195-216.

[5] Crainic, T. G. (2000). Service Network Design in Freight Transportation. In European Journal of Operational Research, 122(2), 272-288.

[6] Crainic, T. G., & Hewitt, M. (2021). Service network design. In Network Design with Applications to Transportation and Logistics (pp. 347-382). Springer, Cham.

[7] Hewitt, M. (2022). The flexible scheduled service network design problem. Transportation Science, 56(4), 1000-1021.

[8] Wu, H., Herszterg, I., Savelsbergh, M., & Huang, Y. (2022). Service network design for same-day delivery with hub capacity constraints. Transportation Science.