<figure><img src="image_1.png" /></figure>

HAL
open science

# Data-driven distributionally robust approach for the joint chance-constrained location routing problem with uncertain demands

Guillaume Massonnet, Juliette Medina

► To cite this version:

Guillaume Massonnet, Juliette Medina. Data-driven distributionally robust approach for the joint chance-constrained location routing problem with uncertain demands. Odysseus 2024, May 2024, Carmona, Spain. hal-05032962

HAL Id: hal-05032962

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

Submitted on 14 Apr 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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Data-driven distributionally robust approach for the joint chance-constrained location routing problem with uncertain demands

Guillaume Massonnet

LS2N, IMT Atlantique, Nantes, France

Email: guillaume.massonnet@imt-atlantique.fr

Juliette Medina

CRC Services, Nantes, France

Email: j.medina@crc-services.com

## 1 Introduction and related work

Fresh food supply chains generally handle products with very limited shelf-life and thus require just-in-time production and transportation from the suppliers to the retailers. In order to meet their clients' requirements for fast deliveries, it is critical for suppliers to anticipate their supply chain organization at a strategic and tactical level to provide efficient and responsive services.

This work originates from the practical case faced by a french food producer with several facilities that supplies multiple products to the warehouses of its clients on a daily basis. The transportation of these items is subcontracted to external carriers and is performed by vehicle routing, each starting from a single facility and delivering a few (generally between 2 and 3) clients. At the time this organization is decided, real demands are unknown and susceptible to vary from day to day since clients may place their orders as late as a few hours before delivery is due. As making last-minute search for additional vehicles is both costly and risky (or even occasionally impossible), the supplier's goal is to build a predefined vehicle routing plan, identical every day, that describes which facilities and which routes are used to deliver each type of product to its clients. The objective is then to propose a plan that offers enough production and transportation capacity to satisfy the clients demands with a high probability at minimum operating costs.

We refer to the above problem as the *Multi Products Capacitated Location Routing Problem (MCLRP)* with stochastic demands, which generalizes the Location Routing Problem (see [1, 2] for detailed references). We model the target service level of the supplier for full demand satisfaction as a set of constraints that must all be satisfied with
a predefined probability. Unfortunately in practice, one only has access to an empirical estimation of the true underlying distribution of random parameters through the historical data available. that allows approximate these probabilistic constraints. However when data is scarce or imprecise, standard approaches such as the Sample Average Approximation (SAA) are susceptible to achieve poor out-of-sample performances. Instead, we address this problem using a distributionally robust data-driven formulation based on Wasserstein balls (see [3, 4]), which ensures more consistent results even when the data sample is limited size. We provide first numerical evidences of its effectiveness on practical cases derived from real data sets.

## 2 Mathematical formulation

In what follows, we use boldface lower-case (resp. upper-case) letters to designate vectors (resp. matrices). Let $\mathcal{I} = \{1, \dots, I\}$ be the set of sites available to open a facility, $\mathcal{K} = \{1, \dots, K\}$ be the set of products and $\mathcal{J} = \{1, \dots, J\}$ be the set of final customers. The demand of a given client $j \in \mathcal{J}$ for product $k \in \mathcal{K}$ is modeled as a random variable $\tilde{\xi}_{jk}$ that may be correlated with the demand of other customers. The joint probability distribution $\mathbb{P}$ of $\tilde{\xi} = (\tilde{\xi}_{11}, \dots, \tilde{\xi}_{1K}, \dots, \tilde{\xi}_{J1}, \dots, \tilde{\xi}_{JK})$ is unknown but we assume that we have access to a historical data set of $N$ past demands $\hat{\xi}^{(1)}, \dots, \hat{\xi}^{(N)}$ drawn independently from $\mathbb{P}$. For all customers $j \in \mathcal{J}$, we denote $\mathcal{K}_j$ the set of items that it may order, i.e. all $k \in \mathcal{K}$ such that $\mathbb{P}(\tilde{\xi}_{jk} > 0) > 0$.

Each facility $i \in \mathcal{I}$ can produce and ship all types of products up to a limited capacity $S_i$ and incurs a setup cost $f_i$ when it is opened. Delivery to the customers is perfomed using an enumerable set of candidate routes $\mathcal{R} = \{1, \dots, R\}$, each starting from a single facility $i \in \mathcal{I}$ and visiting a subset of (generally up to 3) customers $\mathcal{J}_r \subseteq \mathcal{J}$. For all $i \in \mathcal{I}$, we denote $\mathcal{R}_i$ the subset of routes that start from facility $i$. Split delivery is allowed, i.e. demand $\tilde{\xi}_{jk}$ may be satisfied using one or more vehicles, from one or more of the opened facilities. In addition, a route $r \in \mathcal{R}$ may be used by up to $V_r$ vehicles, each with the same capacity $Q_r$. Any vehicle using route $r$ induces a transportation cost $c_r$.

The objective is to find a solution of minimum setup and transportation cost while ensuring that the totality of the demands is satisfied with probability at least $1 - \epsilon$. We define three types of decision variables: $x_r \in \{0, \dots, V_r\}$ is the number of vehicles that use route $r \in \mathcal{R}$ (maximum $V_r$ vehicles), $y_i \in \{0, 1\}$ is a boolean variable that indicates whether facility $i$ is open and $z_{jk}^r \in [0, 1]$ is the fraction of demand of customer $j$ for item $k$ that is served by a vehicle using route $r$.
## 2.1 Joint chance-constrained (JCC) formulation

Let $\mathcal{X}$ be the set of variables values that satisfy jointly the deterministic constraints of the problem, that is: 1) Any selected route $r$ must start from an opened facility and be used at most $V_r$ vehicles, 2) transport is only allowed using selected routes, and 3) the sum of deliveries to customer $j$ is sufficient to cover its demand for all products in $\mathcal{K}_j$:

$$ \mathcal{X} = \left\{ (\mathbf{x}, \mathbf{y}, \mathbf{z}) \in \mathbb{N}_+^R \times \{0, 1\}^I \times \mathbb{R}_+^{RJK} : \begin{array}{ll} x_r \le V_r y_i & \forall i \in \mathcal{I}, \forall r \in \mathcal{R}_i \\ 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\} $$

Given variables $(\mathbf{x}, \mathbf{y}, \mathbf{z}) \in \mathcal{X}$, we define the safe set $\mathcal{S}(\mathbf{x}, \mathbf{y}, \mathbf{z})$ for the CMLRP as the set of all realizations $\xi \in \mathbb{R}_+^{JK}$ for which the capacity constraints on both the facilities and the vehicles are satisfied. Formally, we have:

$$ \mathcal{S}(\mathbf{x}, \mathbf{y}, \mathbf{z}) = \left\{ \xi \in \mathbb{R}_+^{JK} : \begin{array}{ll} \sum_{j \in \mathcal{J}_r} \sum_{k \in \mathcal{K}_j} z_{jk}^r \xi_{jk} & \le Q_r x_r \quad \forall r \in \mathcal{R} \\ \sum_{r \in \mathcal{R}_i} \sum_{j \in \mathcal{J}_r} \sum_{k \in \mathcal{K}_j} z_{jk}^r \xi_{jk} & \le S_i \quad \forall i \in \mathcal{I} \end{array} \right\} \quad (1) $$

We then use (1) to define the Joint Chance-Constrained (JCC) version of the CMLRP:

$$ \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} \quad \mathbb{P} \left( \xi \in \mathcal{S}(\mathbf{x}, \mathbf{y}, \mathbf{z}) \right) \ge 1 - \epsilon \quad (3) $$

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

The objective (2) aims at minimizing the sum of facilities opening and transportation. Constraint (3) ensures that the capacity of the openend facilities and used vehicles are sufficient to satisfy the demand with probability at least $1 - \epsilon$ for $\epsilon \in [0, 1]$.

## 2.2 Distributionally robust formulation using Wasserstein ambiguity

For conciseness reasons, we cannot include the mathematical details and the resulting distributionally robust (DR) formulation of the JCC CMLRP introduced above. Instead, we describe the main ideas to derive this model. We build upon the approach presented in [5] to define and strengthen the formulation of JCC programs with right-hand side uncertainty: 1) We are able to define a relaxation of the safety set (1) based on new lifted variables $\bar{\xi}$ that corresponds to the DR counterpart of the JCC program above, 2) we strengthen this formulation with additional constraints from the nominal chance-constrained case, 3) we compute better values for the big-M constants involved in the formulation, and 4) we propose a new constraints generation method to handle real-size problems.
# 3 Experimentations and perspectives

In order to evaluate the performances of the proposed approach, we compare the standard SAA method with the DR formulation of the JCC program, with and without constraints generation. We derive instances from real-life data sets provided by a french food producer, each consisting in 1) a set of historical demands of its customers for each type of product, 2) a set of candidate starting facilities with a shipping capacity, and 3) a set of pre-generated feasible routes. We consider various sizes of requests (small, medium, large) and capacities for the starting facilities (tight, large). Using Gurobi 10.0 with a maximum computation time of one hour, we obtain preliminary results on medium-size instances ($I = 6, J = 20, K = 3, R \approx 1500$) for the DR counterpart of the JCC problem that achieves a final Gurobi gap lower than 2%, which is shown to be lower than 1% with the stronger lower bound provided by the constraints generation method. Future numerical experiments include the application of our methods to larger instances to assess the scalability of this approach to industrial cases. We also plan to conduct an extended sensitivity analysis of these techniques to the size of the training sample and the radius of the Wasserstein ball. The overall objective is to derive a method allowing practitioners to estimate the impact of their target service-level on the out-of-sample performances, helping them to adjust the trade-off between costs and customer satisfaction.

# Acknowledgments

This work was funded by the French National Research Agency (ANR) LabCom project CRC Lab.

# References

[1] Michael Drexel and Michael Schneider. "A survey of variants and extensions of the location-routing problem". In: *Eur. J. of Oper. Res.* 241.2 (2015), pp. 283–308.

[2] Caroline Prodhon and Christian Prins. "A survey of recent research on location-routing problems". In: *Eur. J. of Oper. Res.* 238.1 (2014), pp. 1–17.

[3] Zhi Chen, Daniel Kuhn, and Wolfram Wiesemann. "Data-Driven Chance Constrained Programs over Wasserstein Balls". In: *Oper. Res.* 0.0 (0), null.

[4] Weijun Xie. "On distributionally robust chance constrained programs with Wasserstein distance". In: *Math. Prog.* 186.1-2 (2021), pp. 115–155.

[5] Nam Ho-Nguyen et al. "Strong formulations for distributionally robust chance-constrained programs with left-hand side uncertainty under Wasserstein ambiguity". In: *IN-FORMS J. on Optim.* 5.2 (2023), pp. 211–232.