# Optimisation basée sur les données d'un problème de localisation d'entrepôts et tournées de véhicules

Guillaume Massonnet, Juliette Medina

► To cite this version:

Guillaume Massonnet, Juliette Medina. Optimisation basée sur les données d'un problème de localisation d'entrepôts et tournées de véhicules. 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, Marne La Vallée, France. hal-04976258

HAL Id: hal-04976258

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

Submitted on 4 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>

Distributed under a Creative Commons Attribution 4.0 International License
Optimisation basée sur les données d'un problème de
localisation d'entrepôts et tournées de véhicules

Guillaume Massonnet¹, Juliette Medina²

¹ LS2N, IMT Atlantique, Nantes, France

guillaume.massonnet@imt-atlantique.fr

² Weenlo, Nantes, France

j.medina@weenlo.com

**Mots-clés :** Optimisation stochastique et robuste, location and routing problem

# 1 Motivation et description du problème

On s'intéresse à un problème conjoint de localisation d'entrepôts et de transport de marchandise, qu'on retrouve notamment dans les chaînes d'approvisionnement de produits frais. Dans ce cadre où les industriels et leurs clients favorisent une approche par flux tendu pour éviter la perte de produits par péremption, les quantités de commande sont souvent communiquées peu de temps avant leur livraison. Cette exigence de réactivité oblige les fournisseurs à anticiper l'organisation de leur transport aux niveaux stratégique et tactique, capable d'absorber les variations induites par cette incertitude, en particulier lorsque l'expédition de différents types de produits depuis leurs usines vers les entrepôts de leurs clients sont sous-traitées auprès de transporteurs externes. L'objectif est de proposer une affectation pré-établie des commandes de produits aux usines et un plan de transport avec des tournées fixes, répétées chaque jour (en général vers deux à trois clients), qui permette de garantir un niveau de service minimum.

Nous désignons ce problème sous le nom de *Multi Products Capacitated Location Routing Problem (MCLRP)* avec demandes stochastiques, qui généralise le problème de localisation et de tournées de véhicules (voir [1] pour une liste plus détaillée de références). Nous caractérisons le niveau de service comme une probabilité prédéfinie de satisfaire l'ensemble de contraintes capacitaires. En pratique, les historiques de demandes disponibles sont souvent limités en taille, ce qui impacte les performances d'approches standards telles que le Sample Average Approximation (SAA) qui l'utilisent directement pour estimer la probabilité de violation des contraintes. Pour palier à ce problème, nous utilisons une formulation robuste en distribution qui exploite des ensembles d'ambiguité basée sur la distance de Wasserstein (voir [2, 3]), qui améliore la cohérence des résultats même lorsque la taille de l'échantillon de données disponible est limitée. Nous évaluons son efficacité sur des cas pratiques dérivés de données réelles.

# 2 Formulation mathématique et méthode de résolution

Soit $\mathcal{I} = \{1, \dots, I\}$ l'ensemble des usines disponibles, $\mathcal{K} = \{1, \dots, K\}$ l'ensemble des produits et $\mathcal{J} = \{1, \dots, J\}$ l'ensemble des clients. Pour tout client $j \in \mathcal{J}$, on note $\mathcal{K}_j$ l'ensemble des produits qui peuvent être commandés par $j$. L'ensemble des demandes des clients pour chaque produit est modélisé par un vecteur stochastique $\boldsymbol{\xi} = (\xi_{11}, \dots, \xi_{1K}, \dots, \xi_{J1}, \dots, \xi_{JK})$ dont la distribution jointe $\mathbb{P}$ est inconnue. On suppose néanmoins disposer d'un historique des flux commandés sur $N$ jours passés $\boldsymbol{\xi}^{(1)}, \dots, \boldsymbol{\xi}^{(N)}$ tirés indépendamment selon $\mathbb{P}$. Ouvrir une usine $i \in \mathcal{I}$ induit un coût $f_i$ et permet de produire tous les types de produits jusqu'à une capacité journalière $S_i$. Les clients sont livrés via un ensemble de tournées de véhicules connu $\mathcal{R} = \{1, \dots, R\}$, où chaque route part d'une usine $i \in \mathcal{I}$ et livre les clients $\mathcal{J}_r \subseteq \mathcal{J}$. La
demande $\tilde{\xi}_{jk}$ peut être satisfaite grâce à des quantités issues de une ou plusieurs usines ouvertes, en utilisant un ou plusieurs véhicules. Enfin, le nombre véhicules affectés à une route $r \in \mathcal{R}$ ne peut dépasser une limite $V_r$, chaque véhicule ayant une capacité $Q_r$ et un coût d'utilisation $c_r$.

On définit quatre types de variable de décision : l'utilisation d'une route $r \in \mathcal{R}$ est modélisée par une variable booléenne $x_r \in \{0; 1\}$, tandis que la variable entière $v_r \in \{0 \dots, V_r\}$ représente le nombre de véhicules qui l'empruntent, une variable booléenne $y_i \in \{0; 1\}$ qui indique l'ouverture de l'usine $i$ et une proportion $z_{jk}^r \in [0, 1]$ de la demande client $j$ pour le produit $k$ livrée par un véhicule via la route $r$. Le domaine admissible correspond à l'ensemble suivant :

$$ \mathcal{X} = \left\{ (\mathbf{x}, \mathbf{v}, \mathbf{y}, \mathbf{z}) \in \mathbb{N}_+^R \times \{0, 1\}^I \times \mathbb{R}_+^{RJK} : \begin{array}{ll} x_r \le y_i & \forall i \in \mathcal{I}, \forall r \in \mathcal{R}_i \\ v_r \le V_r x_r & \forall r \in \mathcal{R} \\ z_{jk}^r \le x_r & \forall r \in \mathcal{R}, \forall j \in \mathcal{J}_r, \forall k \in \mathcal{K}_j \\ \sum_{r \in \mathcal{R}} z_{jk}^r = 1 & \forall j \in \mathcal{J}, \forall k \in \mathcal{K}_j \end{array} \right\} $$

Pour un ensemble de variables admissible $(\mathbf{x}, \mathbf{v}, \mathbf{y}, \mathbf{z}) \in \mathcal{X}$, on note

$$ S(\mathbf{x}, \mathbf{v}, \mathbf{y}, \mathbf{z}) = \left\{ \boldsymbol{\xi} \in \mathbb{R}_+^{JK} : \sum_{r \in \mathcal{R}_i} \sum_{j \in \mathcal{J}_r} z_{jk}^r \xi_{jk} \le Q_r v_r \quad \forall r \in \mathcal{R} \\ \sum_{r \in \mathcal{R}_i} \sum_{j \in \mathcal{J}_r} z_{jk}^r \xi_{jk} \le S_i \quad \forall i \in \mathcal{I} \right\} \quad (1) $$

l'ensemble de réalisations de demandes telles que les contraintes capacitaires sur les usines et les véhicules sont respectées. Le programme ci-dessous permet d'obtenir une solution de coût minimum telle que la probabilité de satisfaire la totalité des demandes est supérieure à $1 - \epsilon$ :

$$ \min_{\mathbf{x}, \mathbf{y}, \mathbf{z}} \sum_{i \in \mathcal{I}} f_i y_i + \sum_{r \in \mathcal{R}} c_r x_r \quad (2) $$

$$ \text{s.t } \mathbb{P} \left( \tilde{\xi} \in S(\mathbf{x}, \mathbf{v}, \mathbf{y}, \mathbf{z}) \right) \geq 1 - \epsilon \quad (3) $$

$$ (\mathbf{x}, \mathbf{v}, \mathbf{y}, \mathbf{z}) \in \mathcal{X} \quad (4) $$

Nous proposons une contrepartie robuste en distribution en définissant un ensemble d'ambiguïté sous la forme d'une boule de Wasserstein à partir de l'échantillon historique $\hat{\xi}^{(1)}, \dots, \hat{\xi}^{(N)}$. Les résultats préliminaires montrent que la modélisation est efficace pour respecter le niveau de service requis, mais la résolution directe du MIP atteint rapidement ses limites. Nous introduisons donc une approche basée sur une génération de contraintes qui utilise des propriétés identifiées dans ce cadre par [4], ce qui nous permet de renforcer cette formulation initiale et d'accélérer la résolution sur des instances créées à partir de données réelles.

## Remerciements

Ce travail est financé par l'Agence Nationale de la Recherche (ANR) dans le cadre du projet LabCom CRC Lab.

## Références

[1] Michael DREXL et Michael SCHNEIDER. "A survey of variants and extensions of the location-routing problem". In : Eur. J. of Oper. Res. 241.2 (2015), p. 283-308.

[2] Zhi CHEN, Daniel KUHN et Wolfram WIESEMANN. "Data-driven chance constrained programs over Wasserstein balls". In : Oper. Res. 72.1 (2024), p. 410-424.

[3] Weijun XIE. "On distributionally robust chance constrained programs with Wasserstein distance". In : Math. Prog. 186.1-2 (2021), p. 115-155.

[4] Nam HO-NGUYEN et al. "Strong formulations for distributionally robust chance-constrained programs with left-hand side uncertainty under Wasserstein ambiguity". In : INFORMS J. on Optim. 5.2 (2023), p. 211-232.