# Progressive Hedging pour la planification d'un réseau de transport de marchandises sous incertitudes temporelles

Guillaume Joubert, Fabien Lehuédé, Guillaume Massonnet, Juliette Medina

► To cite this version:

Guillaume Joubert, Fabien Lehuédé, Guillaume Massonnet, Juliette Medina. Progressive Hedging pour la planification d'un réseau de transport de marchandises sous incertitudes temporelles. ROADEF 2025: 26ème congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Feb 2025, Champs-sur-Marne, France. hal-04973545

HAL Id: hal-04973545

https://hal.science/hal-04973545v1

Submitted on 3 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
Progressive Hedging pour la planification d'un réseau de
transport de marchandises sous incertitudes temporelles

Guillaume Joubert¹, Fabien Lehuédé¹, Guillaume Massonnet¹, Juliette Medina²

1 IMT Atlantique, LS2N, UMR CNRS 6004, Nantes, France

{guillaume.joubert, fabien.lehuede, guillaume.massonnet}@imt-atlantique.fr

² Weenlo, Nantes, France

j.medina@weenlo.com

Mots-clés : *Progressive Hedging*, *Service Network Scheduling Problem*, *incertitudes*.

# 1 Introduction

Nous nous intéressons au problème d'un transporteur de colis souhaitant planifier l'horaire de départ de ses véhicules sur la partie *middle mile* de son réseau en minimisant les coûts liés au nombre de véhicules utilisés. Sur cette partie du réseau, des lots de colis sont expédiés depuis des entrepôts vers des agences chargées de la distribution du dernier kilomètre. Entre ces deux types de sites, les flux de colis sont concentrés sur des hubs, triés, et répartis vers les agences afin de réduire les coûts de transport. On considère une planification au niveau tactique qui concerne uniquement le nombre de véhicules et les heures de départ des véhicules sur les liens du réseau. Ce type de problème est nommé *Scheduled Service Network Design Problem* [5], et plus particulièrement *Service Network Scheduling Problem* (SNSP) [6] quand les itinéraires des colis sont prédéterminées. Les travaux présentés intègrent des temps de trajets incertains dans ce réseau [3, 4] en prenant en compte les capacités de traitement aux hubs : le retard d'un véhicule à l'arrivée sur un hub peut impacter l'ensemble du processus de tri et se propager vers tous les transports qui lui succèdent. L'objectif est de réaliser la planification en garantissant une qualité de service basée sur le pourcentage de flux acheminés dans un délai prédéterminé à l'agence de destination. Le problème est modélisé comme un SNSP stochastique à deux étapes avec durées de transport incertaines, capacités de traitement limitées et qualité de service. Pour le résoudre, nous présentons une métaheuristique basée sur le *Progressive Hedging* [1, 2, 4, 7].

# 2 Formulation du problème

Soit un réseau de transport $\mathcal{D} = (\mathcal{N}, \mathcal{A})$ où $\mathcal{N}$ est un ensemble de sites et $\mathcal{A}$ un ensemble d'arcs modélisant les trajets inter-sites. Un lot de colis transitant sur le réseau est modélisé par une commodité $k \in \mathcal{K}$ définie par une origine $o_k$, une date de disponibilité $e_k$ à $o_k$, une destination $d_k$, une date de livraison $l_k$ à $d_k$ et une quantité $q_k$. La qualité de service est le pourcentage $1 - \epsilon$ donné de la somme totale des quantités de commodités notée $Q$ devant arriver à l'heure à destination. Des véhicules de capacité $u_{ij}$ empruntent les arcs $(i, j) \in \mathcal{A}$ pour un coût par véhicule noté $f_{ij}$ et avec une durée de transport $\tau_{ij}^t$. La durée $\tau_{ij}^t$ est sujette à des incertitudes et est dépendante de l'horaire de départ $t \in \mathcal{T}$. Le problème consiste à déterminer le nombre de véhicules $y_{ij}^t$ débutant leur trajet sur l'arc $(i, j) \in \mathcal{A}$ à l'horaire $t \in \mathcal{T}$, permettant le transport et le tri des flots de commodités dans le réseau, de manière à minimiser la somme $\sum_{(i,j) \in \mathcal{A}} f_{ij} \sum_{t \in \mathcal{T}} y_{ij}^t$ des coûts de transports, avec une probabilité $1 - \eta$ donnée de satisfaire la contrainte de qualité de service.
# 3 Méthode de résolution

Nous proposons d'adapter la méthode *Progressive Hedging* pour résoudre des instances difficiles du SNSP avec durées de transport incertaines, capacités de traitement limitées et qualité de service. Cette technique itérative cherche à obtenir un consensus sur les variables de première étape en résolvant des sous-problèmes issus d'une décomposition par scénarios obtenue par une relaxation lagrangienne augmentée des contraintes non-anticipatives sur les horaires de départ des véhicules. A chaque itération, les solutions des sous-problèmes sont agrégées en une solution de référence qui guide la mise à jour de paramètres lagrangiens et de coûts de véhicules dans l'espoir de converger vers une solution consensuelle respectant la qualité de service et de coût réel satisfaisant.

Nous appliquons cette méthode sur des instances basées sur des données réelles provenant d'une collaboration avec un partenaire industriel. Nous montrons l'impact des incertitudes temporelles et des capacités de traitement sur le coût des solutions liées à une qualité de service associée à son niveau de confiance. Nous caractérisons, en outre, la difficulté des instances selon leur taille en précisant celles pour lesquelles nous obtenons plus rapidement des solutions de qualité au moins supérieure avec notre méthode comparée à l'utilisation d'un solveur.

# Remerciements

Ce projet a le soutien financier de l'ANR dans le cadre du projet de laboratoire commun CRC Lab entre IMT Atlantique, l'équipe MODELIS du laboratoire LS2N et l'entreprise Weenlo.

# Références

[1] R Tyrrell Rockafellar et Roger J-B Wets. *Scenarios and policy aggregation in optimization under uncertainty*. Mathematics of operations research, 16(1):119-147, 1991.

[2] Teodor Gabriel Crainic, Xiaorui Fu, Michel Gendreau, Walter Rei et Stein W Wallace. *Progressive hedging-based metaheuristics for stochastic network design*. Networks, 58(2):114-124, 2011.

[3] Emrah Demir, Wolfgang Burgholzer, Martin Hrušovský, Emel Arıkan, Werner Jammerlegg et Tom Van Woensel. *A green intermodal service network design problem with travel time uncertainty*. Transportation Research Part B: Methodological, 93:789-807, 2016.

[4] Giacomo Lanza, Teodor Gabriel Crainic, Walter Rei et Nicoletta Ricciardi. *Scheduled service network design with quality targets and stochastic travel times*. European Journal of Operational Research, 288(1):30-46, 2021.

[5] Teodor Gabriel Crainic et Mike Hewitt. *Service network design*. Network Design with Applications to Transportation and Logistics, :347-382, 2021.

[6] Mike Hewitt et Fabien Lehuédé. *The service network scheduling problem*. Eleventh Triennial Symposium on Transportation Analysis conference (TRISTAN XI), 2022

[7] David Escobar-Vargas, Teodor Gabriel Crainic, Walter Rei et Stein W Wallace. *The Two-chelon Multicommodity Location-routing Problem with Stochastic et Correlated Demands*. Bureau de Montreal, Université de Montreal, 2023.