# Vehicle routing problems with multiple commodities: A survey

Wenjuan Gu, Claudia Archetti, Diego Cattaruzza, Maxime Ogier, Frédéric Semet, M. Grazia Speranza

► To cite this version:

Wenjuan Gu, Claudia Archetti, Diego Cattaruzza, Maxime Ogier, Frédéric Semet, et al. Vehicle routing problems with multiple commodities: A survey. European Journal of Operational Research, 2024, 317 (1), pp.1-15. 10.1016/j.ejor.2023.11.032. hal-04387456

HAL Id: hal-04387456

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

Submitted on 11 Jan 2024

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>
Vehicle routing problems with multiple commodities: a
survey

Wenjuan Gu¹, Claudia Archetti², Diego Cattaruzza³, Maxime Ogier³,
Frédéric Semet³, M.Grazia Speranza⁴

¹: School of Modern Posts, Beijing University of Posts and Telecommunications
100876 Beijing, China
wenjuan.gu@bupt.edu.cn

²: Department of Information Systems, Decision Sciences and Statistics
ESSEC Business School in Paris
95021 Cergy-Pontoise Cedex, France
archetti@essec.edu

³: Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9189 CRISTAL, F-59000 Lille, France
{diego.cattaruzza, maxime.ogier, frederic.semet}@centralelille.fr

⁴: Department of Economics and Management, University of Brescia
25122 Brescia, Italy
grazia.speranza@unibs.it

**Abstract:** In this paper, we present a survey on vehicle routing problems with multiple commodities. In most routing problems, only one commodity is explicitly considered. This may be due to the fact that, indeed, a single commodity is involved, or multiple commodities are transported, but they are aggregated and modeled as a single commodity, as no specific requirement imposes their explicit consideration. However, there exist cases in which this aggregation is not possible due to the characteristics of the commodities or to the fact that it would lead to sub-optimal routing plans.

This survey focuses on the analysis of the settings of the problems and the features of the com-
modities that require explicit consideration of disaggregated commodities in routing problems. We
show that problem settings are inherently different with respect to the single commodity problems,
and this has a consequence on both models and solution approaches, which cannot be straightfor-
wardly adapted from the single commodity cases. We propose a classification of the routing problems
with multiple commodities and discuss the motivations that force considering the presence of multiple
commodities explicitly. Specifically, we focus on the modeling perspective by proposing a general
formulation for routing problems with multiple commodities and showing how this formulation can be
adapted to the different features that characterize the problem classes discussed in the survey. Also,
for each major class of problems, promising future research directions are discussed by analysing what
has been studied in the current literature and focusing on challenging topics not covered yet.

**Keywords:** invited review; multiple commodities; vehicle routing problems.

# 1 Introduction

Vehicle Routing Problems (VRPs) have been widely studied in the last decades (Laporte (2009), Toth and Vigo (2014), Braekers et al. (2016)) and deal with the delivery or the collection of goods. For the sake of simplicity, we will refer to the delivery case in the following.

In the vast majority of papers dealing with routing problems, nothing is mentioned about ‘what’ has to be delivered to the customers. Instead, the only information provided is about ‘how much’ has to be delivered, where the amount can be measured in different ways (weight, volume,...). This means that either the problem concerns the delivery of a single commodity, which is the same for all customers and therefore there is no need to specify what is delivered to each of them, or that multiple commodities do not have specific features that make it necessary to consider them separately when designing the distribution plan. Of course, in practice, once the distribution plan is built, then the vehicles are loaded with the specific commodities requested by the customers.

In this paper we focus on the case where, on the contrary, the commodities must be individually considered when designing the distribution plan because, otherwise, the plan might turn out to be infeasible or suboptimal.

Before discussing the cases where multiple commodities have to be explicitly considered, let us first see how situations with multiple commodities can be modeled with the most standard vehicle routing problem, i.e., the Capacitated Vehicle Routing Problem (CVRP).

**Case 1:** multiple commodities are demanded by the customers and are available at the depot in the requested quantities. In this case, $d_i$ represents the *aggregated* demand of all the commodities requested by customer $i \in \mathcal{N} \setminus \{0\}$. The underlying assumption is that the same vehicle can deliver the commodities together;

**Case 2:** multiple commodities are delivered with a fleet of vehicles where each vehicle is dedicated to one specific commodity. Then, the overall problem can be modeled with as many independent CVRPs as the number of commodities. Here, $d_i$ represents the demand of customer $i \in \mathcal{N} \setminus \{0\}$ in one of the subproblems. Note that the solution to the overall problem consists in visiting each customer as many times as the number of required commodities.

These two cases correspond to situations where multiple commodities are present but not explicitly considered. They are not mentioned in the problem definition and are not taken into account in the mathematical models (via dedicated variable indexing, specific constraints, and cost functions...). Solving the problem reduces to the solution of a single (in Case 1) or multiple distinct and independent (in Case 2) CVRPs. These considerations may be extended to other problems as, for example, the CVRP with time windows (Kallehauge et al. (2006)) or the Split Delivery VRP (Archetti and Speranza (2008)).
Multiple commodities are explicitly considered during the planning phase when either this is mandatory to build a feasible distribution plan (as commodities have specific features that have to be taken into account as they have an impact on how the distribution is implemented) or when benefits (cost savings or profit increase) can be achieved by considering the commodities separately in the planning phase.

The contribution of this survey is to review the problem settings (named *cases* in the following), and the corresponding literature, on routing problems with multiple commodities. We aim to highlight the features that force the explicit consideration of multiple commodities. A classification of the problem settings is proposed that is based on the features of the commodities and the reasons why they have to be considered explicitly. We analyse the modeling issues and show how they can be handled. Also, besides revising the literature, we discuss the implications of having multiple commodities and highlight future avenues of research.

## 1.1 Contribution and structure of the paper

In practical applications, there are situations that make it possible or necessary to consider the presence of multiple commodities explicitly. When commodities are *explicitly* considered in mathematical models and algorithms, two different situations may occur: the commodities are *compatible* or, vice versa, *incompatible*. Commodities are said to be *incompatible* when they cannot be transported simultaneously in the same vehicle or in the same compartment of a vehicle with multiple compartments. Otherwise, they are said to be *compatible*. The incompatibility case happens when, for example, regulations impose that food and detergent cannot be transported together. It is also the case for bulk organic and conventional food products. More generally, bulk materials have to be transported in vehicles equipped with dedicated compartments.

The same vehicle can be used to transport incompatible commodities only if they are separated by using different compartments, each dedicated to a different commodity, or they are transported in different trips of the vehicle. The first case corresponds to the class of multi-compartment VRPs (Derigs et al. (2011)), while the second to VRPs with multiple trips (Cattaruzza et al. (2016)). In the latter case, it is assumed that vehicles can transport any commodity.

When commodities are *compatible*, they can be transported at the same time by the same vehicle, without the need of separating them. There may be different reasons why commodities have to be considered separately, for example, because they have different origins or destinations or because of other characteristics.

The scope of the paper is to revise papers that consider vehicle routing problems and explicitly deal with multiple commodities. We limit the survey to papers that deal with the transportation (collection or delivery) of goods. As a consequence, papers dealing with the transportation of people, such as the dial-a-ride problem, or with services at customer locations, such as in home care applications, are out of the scope of this survey.

Figure 1 classifies the problems that consider multiple commodities. The classification discussed in the next sections is depicted in the *Explicit* part, corresponding to the rectangle on the right of the figure. The main questions this paper addresses are: when and why do we need or is it beneficial to consider multiple commodities? To answer this question, we organize the discussion in two sections.
<figure><img src="image_2.png" /><figcaption>Figure 1: Classification of problems with multiple commodities. This paper reviews works where commodities are explicitly considered in routing problems, that are those in the rectangle in the right part of the scheme.</figcaption></figure>

The first considers routing problems where commodities are incompatible, that is, cannot be loaded simultaneously in the same vehicle. The second section considers routing problems where commodities are compatible.

The remainder of this paper is organized as follows. In Section 2, we provide a generic mathematical formulation for the CVRP with multiple commodities. This model will serve as a base to describe how commodities are explicitly considered in the mathematical formulation of the problems reviewed in this paper. Section 3 overviews vehicle routing problems with incompatible commodities and includes two subsections corresponding to two ways of transporting incompatible commodities using a single fleet of vehicles. Section 4 presents vehicle routing problems with compatible commodities and includes several subsections, each corresponding to a different reason forcing the model to consider the multiple commodities explicitly. In each of the two sections, future research opportunities are discussed. Section 5 concludes the paper.

## 2 The Capacitated Vehicle Routing Problem with multiple commodities

This section provides the notation that will be used in the rest of the paper as well as a mathematical model (1a)–(1i) for the Capacitated Vehicle Routing Problem (CVRP) with multiple commodities. The discussion of mathematical formulations of the problems studied in the following sections is based on formulation (1a)–(1i).

The basic problem in the class of routing problems is the CVRP that is usually defined over a network represented by a complete directed graph $\mathcal{G} = (\mathcal{N}, \mathcal{A})$. The set $\mathcal{N} = \{0, 1, \dots, N\}$ represents all the locations in the network, with 0 being the depot and $\mathcal{N} \setminus \{0\}$ the set of customers, whereas $\mathcal{A} = \{(i, j), i, j \in \mathcal{N}, i \neq j\}$ is the set of arcs that connect the locations in the network. Each arc $(i, j)$ is associated with travelling cost $c_{ij}$ that is paid when the arc is traversed by a vehicle. A fleet of homogeneous vehicles with capacity $Q$ is in charge of the delivery operations, and their routes start and end at the depot. Each customer $i \in \mathcal{N} \setminus \{0\}$ has a demand $d_i \ge 0$. The value $d_i$ represents the total quantity to be delivered to customer $i$. The CVRP aims to determine a set of routes such that
each customer is visited exactly once to satisfy its demand, the capacity constraints are satisfied, and the total routing cost is minimized.

The CVRP has been widely studied in the literature for decades (see Toth and Vigo (2014)). The underlying assumption of the CVRP is that a single commodity has to be distributed to customers. This means that the decisions are related to 'how' to serve customers, i.e., in the CVRP the assignment of customers to vehicles and the routes of the vehicles have to be found. No decision about 'what' should be delivered to the customers when visiting them is considered, as it is implicitly assumed that when a customer is served, the demand is completely satisfied. Thus, the only information needed to describe the demand concerns the quantity (in terms of weight, volume, ...). This is no longer the case when customers require multiple commodities. In this case, there is the need to decide also 'what' (which commodity) is delivered to a customer at each visit.

<table><caption>Table 1: Basic notation.</caption><thead><tr><th></th><th>Symbol</th><th>Description</th></tr></thead><tbody><tr><td rowspan="6">Sets</td><td>$\mathcal{N}$</td><td>Set of vertices, where 0 is the depot and {1; ...; N} are the customers</td></tr><tr><td>$\mathcal{A}$</td><td>Set of arcs</td></tr><tr><td>$\mathcal{K}$</td><td>Set of vehicles</td></tr><tr><td>$\mathcal{M}$</td><td>Set of commodities</td></tr><tr><td>$\delta^+(i)$</td><td>Set of successors of i in the graph $\mathcal{G} = (\mathcal{N}, \mathcal{A})$; $\delta^+(i) = \{j \in \mathcal{N} | (i, j) \in \mathcal{A}\}$</td></tr><tr><td>$\delta^-(i)$</td><td>Set of predecessors of i in the graph $\mathcal{G} = (\mathcal{N}, \mathcal{A})$; $\delta^-(i) = \{j \in \mathcal{N} | (j, i) \in \mathcal{A}\}$</td></tr><tr><td rowspan="3">Parameters</td><td>$c_{ij}$</td><td>Cost of traversing arc $(i, j) \in \mathcal{A}$</td></tr><tr><td>$d_i^m$</td><td>Demand of customer $i \in \mathcal{N} \setminus \{0\}$ for commodity $m \in \mathcal{M}$</td></tr><tr><td>$Q$</td><td>Capacity of the vehicles</td></tr><tr><td rowspan="2">Variables</td><td>$x_{ij}^k$</td><td>1 if arc $(i, j) \in \mathcal{A}$ is traversed by vehicle $k \in \mathcal{K}$, 0 otherwise</td></tr><tr><td>$y_i^{km}$</td><td>1 if commodity $m \in \mathcal{M}$ of customer $i \in \mathcal{N} \setminus \{0\}$ is delivered by vehicle $k \in \mathcal{K}$</td></tr></tbody></table>

## 2.1 A mathematical programming formulation for the CVRP with multiple commodities

The CVRP with multiple commodities can be formulated as the following Integer Linear Programming (ILP) model (1a)-(1i). Our aim is to describe the problem formally and not to provide the most efficient formulation.

Let us indicate with $\mathcal{K}$ the set of vehicles, $\mathcal{M}$ the set of commodities, $\delta^+(i)$ (resp. $\delta^-(i)$) as the set of successors (resp. predecessors) of $i \in \mathcal{N}$. The demand of customer $i \in \mathcal{N} \setminus \{0\}$ for commodity $m \in \mathcal{M}$ is $d_i^m$. Finally, let $x_{ij}^k$ be a binary variable equal to one if arc $(i, j) \in \mathcal{A}$ is traversed by vehicle $k \in \mathcal{K}$, zero otherwise, and $y_i^{km}$ be a binary variable equal to one if commodity $m \in \mathcal{M}$ of customer $i \in \mathcal{N} \setminus \{0\}$ is delivered by vehicle $k \in \mathcal{K}$, zero otherwise. The notation is summarized in Table 1. The
CVRP with multiple commodities can be formulated as follows:

$$ \min \sum_{k \in \mathcal{K}} \sum_{(i,j) \in \mathcal{A}} c_{ij} x_{ij}^k \qquad (1a) $$

$$ \text{s.t.} \quad \sum_{j \in \delta^{-}(i)} x_{ij}^{k} = \sum_{j \in \delta^{+}(i)} x_{ij}^{k} \qquad \forall i \in \mathcal{N}, \forall k \in \mathcal{K} \qquad (1b) $$

$$ \sum_{j \in \delta^{+}(0)} x_{0j}^{k} \le 1 \qquad \forall k \in \mathcal{K} \qquad (1c) $$

$$ \sum_{i,j \in S} x_{ij}^{k} \le |S| - 1 \qquad \forall k \in \mathcal{K}, \forall S \subset \mathcal{N} \setminus \{0\}, |S| \ge 2 \qquad (1d) $$

$$ \sum_{k \in \mathcal{K}} y_{i}^{km} = 1 \qquad \forall i \in \mathcal{N} \setminus \{0\}, \forall m \in \mathcal{M} \qquad (1e) $$

$$ \sum_{m \in \mathcal{M}} y_{i}^{km} \le |\mathcal{M}| \sum_{j \in \delta^{+}(i)} x_{ij}^{k} \qquad \forall i \in \mathcal{N} \setminus \{0\}, \forall k \in \mathcal{K} \qquad (1f) $$

$$ \sum_{i \in \mathcal{N} \setminus \{0\}} \sum_{m \in \mathcal{M}} d_{i}^{m} y_{i}^{km} \le Q \qquad \forall k \in \mathcal{K} \qquad (1g) $$

$$ x_{ij}^{k} \in \{0, 1\} \qquad \forall i, j \in \mathcal{N}, \forall k \in \mathcal{K} \qquad (1h) $$

$$ y_{i}^{km} \in \{0, 1\} \qquad \forall i \in \mathcal{N} \setminus \{0\}, \forall k \in \mathcal{K}, \forall m \in \mathcal{M}. \qquad (1i) $$

The objective function (1a) aims at minimizing the total routing cost. Constraints (1b) are flow conservation constraints. Constraints (1c) impose that each vehicle is used at most once. Constraints (1d) are subtour elimination constraints. Constraints (1e) impose that each commodity required by a customer is delivered exactly once by a single vehicle. Constraints (1f) link the delivery of commodities by a vehicle with the visit of the customer with the same vehicle. Constraints (1g) impose to satisfy the vehicle capacity. Constraints (1h) and (1i) define the domain of the variables.

In this model, it is assumed that the commodities can be delivered by different vehicles to the same customer. However, a single commodity has to be delivered at once by a single vehicle. Moreover, the commodities are compatible and can be transported in the same vehicle.

In case all commodities must be delivered to each customer at once with a single vehicle (Case 1 presented in Section 1), we can aggregate the customer demands by defining $d_i = \sum_{m \in \mathcal{M}} d_i^m$. In this case, $|\mathcal{M}| = 1$, and the index $m$ disappears from the model. This leads to the classical CVRP. If a dedicated fleet must deliver commodities (Case 2 presented in Section 1), each commodity is associated with a set of vehicles $\mathcal{K}^m$, and constraints (1e) are then replaced by the following constraints:

$$ \sum_{k \in \mathcal{K}^m} y_{i}^{km} = 1 \quad \forall i \in \mathcal{N} \setminus \{0\}, \forall m \in \mathcal{M}. \qquad (2) $$

The model can then be decomposed by vehicle, i.e., by commodity. For each vehicle (commodity), the corresponding problem is the classical CVRP.

Before moving to the part dedicated to the different problem classes, we summarize in Table 2 the additional notation used in the formulations of the problems we describe in the following.
<table><caption>Table 2: Additional notation.</caption><thead><tr><th>Symbol</th><th>Description</th></tr></thead><tbody><tr><td>K<sup>m</sup></td><td>Set of vehicles that deliver commodity m</td></tr><tr><td>L</td><td>Set of compartments in the vehicles</td></tr><tr><td>I<sub>comp</sub></td><td>Set of incompatibilities between compartments and commodities</td></tr><tr><td>I<sub>comm</sub></td><td>Set of incompatible commodities</td></tr><tr><td>R</td><td>Set of possible trips</td></tr><tr><td>P</td><td>Set of depots</td></tr><tr><td>K<sup>p</sup></td><td>Set of vehicles available at depot p</td></tr><tr><td>T</td><td>Set of time periods</td></tr><tr><td>Q<sup>m</sup></td><td>Capacity of the vehicle dedicated to commodity m</td></tr><tr><td>Q<sup>l</sup></td><td>Capacity of compartment l</td></tr><tr><td>D<sup>m</sup><sub>p</sub></td><td>Maximum available quantity of commodity m at depot p</td></tr><tr><td>d<sup>m</sup></td><td>Total amount of commodity m to be collected</td></tr><tr><td>D<sup>m</sup><sub>i</sub></td><td>Maximum available quantity of commodity m at supplier i</td></tr><tr><td>p<sup>m</sup><sub>i</sub></td><td>Unitary selling price of commodity m by supplier i</td></tr><tr><td>r<sup>mt</sup></td><td>Production rate of commodity m in period t</td></tr><tr><td>C<sup>m</sup><sub>i</sub></td><td>Inventory capacity of commodity m at customer i</td></tr><tr><td>h<sup>m</sup><sub>i</sub></td><td>Holding cost of commodity m at customer i</td></tr><tr><td>d<sup>mt</sup><sub>i</sub></td><td>Demand of customer i for commodity m at period t</td></tr><tr><td>c<sup>m</sup><sub>ij</sub></td><td>Cost of traveling from i to j when transporting commodity m</td></tr><tr><td>z<sup>kml</sup><sub>i</sub></td><td>1 if commodity m of customer i is loaded in compartment l of vehicle k</td></tr><tr><td>z<sup>kmr</sup><sub>i</sub></td><td>1 if commodity m of customer i is delivered in trip r of vehicle k</td></tr><tr><td>z<sup>p</sup><sub>i</sub></td><td>1 if customer i is served from depot p</td></tr><tr><td>z<sup>pm</sup><sub>i</sub></td><td>1 if commodity m of customer i is served from depot p</td></tr><tr><td>z<sub>i</sub></td><td>1 if supplier i is visited</td></tr><tr><td>q<sup>m</sup><sub>ij</sub></td><td>Quantity on the vehicle along arc (i, j) for commodity m</td></tr><tr><td>q<sup>m</sup><sub>i</sub></td><td>Quantity of commodity m collected at supplier i</td></tr><tr><td>q<sup>kmt</sup><sub>i</sub></td><td>Quantity of commodity m delivered to customer i by vehicle k at period t</td></tr><tr><td>I<sup>mt</sup><sub>i</sub></td><td>Inventory level of commodity m of customer i at the end of period t</td></tr><tr><td>I<sup>mt</sup><sub>0</sub></td><td>Inventory level of commodity m at the supplier at the end of period t</td></tr><tr><td>w<sup>km</sup><sub>ij</sub></td><td>1 if vehicle k travels from i to j with the maximum risk level of commodity m</td></tr></tbody></table>
# 3 Incompatible commodities

This section reviews multi-commodity routing problems where the commodities are incompatible, i.e., cannot be mixed on the same vehicle or, when the vehicle has several compartments, cannot be placed in the same compartment of a vehicle. Two different ways are typically considered to handle incompatible commodities: using vehicles with multiple compartments or transporting commodities in different trips performed by the same vehicles. This gives rise to two different classes of problems: the so-called Multi-Compartment VRPs (MCmpt-VRPs, Section 3.1) and the Multi-Trip VRPs (MTVRPs, Section 3.2).

## 3.1 Multi-compartment vehicle routing problems

In this section, we provide an overview of the contributions on MCmpt-VRPs. The first contribution related to routing problems where vehicles are equipped with several compartments dedicated to specific commodities was motivated by applications related to petroleum distribution (see Brown and Graves (1981)). However, to the best of authors' knowledge, the first formal definition of a MCmpt-VRP is due to El Fallahi et al. (2008). In Coelho and Laporte (2015) a classification of the MCmpt-VRPs is proposed, based on the possibility to use a compartment for one or several commodities, and the possibility to split the delivery of a customer or not. For each case, they propose two Mixed Integer Linear Programming (MILP) formulations, with explicit and implicit assignment of products to compartments. Surveys can be found in Derigs et al. (2011) and Ostermeier et al. (2021). We refer the reader to these surveys for an extensive overview of MCmpt-VRPs. As many papers related to MCmpt-VRPs study practical applications, we proceed as follows. We present the problem description as given in Derigs et al. (2011) and review the contributions that study the problem without a specific connection to a real case. Then, we classify and revise the remaining contributions based on the application domain.

El Fallahi et al. (2008) study a MCmpt-VRP where each vehicle has dedicated compartments with a given capacity, i.e., for each vehicle $k \in \mathcal{K}$, the compartment for commodity $m \in \mathcal{M}$ has a capacity $Q^m$. The problem is a multi-commodity VRP, as presented in Section 2, where customers require different commodities, each customer may be visited by several vehicles, but each required commodity has to be delivered at once by a single vehicle. The problem can be formulated as (1) with the only difference that capacity constraints (1g) have to be replaced with capacity constraints for each vehicle compartment:

$$ \sum_{i \in \mathcal{N} \setminus \{0\}} d_i^m y_i^{km} \le Q^m \quad \forall m \in \mathcal{M}, \forall k \in \mathcal{K}. \quad (3) $$

Note that here we use the commodity index $m$ to distinguish among the different compartments of the vehicles as each commodity has a dedicated compartment.

Derigs et al. (2011) propose a more general MCmpt-VRP with incompatibilities. All vehicles have a set $\mathcal{L}$ of compartments, and each compartment $l \in \mathcal{L}$ is associated with a limited capacity $Q^l$. Contrary to El Fallahi et al. (2008), a commodity can be loaded in several compartments. Two types of incompatibilities are considered. First, commodities may be incompatible with some compartments, i.e., commodities cannot be loaded in these compartments. We define $\mathcal{I}_{comp} = \{(m, l) | m \in \mathcal{M}, l \in \mathcal{L}, m$ and $l$ are incompatible$\}$ as the set of incompatibilities between commodities and compartments.
Second, commodities may be incompatible with each other, i.e., cannot be loaded together in the same compartment even if they are compatible with the compartment itself. $\mathcal{I}_{comm} = \{(m, m')|m, m' \in \mathcal{M}, m$ and $m'$ are incompatible\}$ is the set of incompatible pairs of commodities. The problem requires determining, for each customer, in which compartment each required commodity is loaded. To do so, binary variables $z_i^{kml}$ are introduced that take value one if the commodity $m$ of customer $i$ is loaded in compartment $l$ of vehicle $k$, zero otherwise. Note that the $y_i^{km}$ variables defined in the multi-commodity VRP are the sum over the compartments $l \in \mathcal{L}$ of the $z_i^{kml}$ variables. With respect to the formulation presented in Section 2.1, in addition to the substitution of $y_i^{km}$ by $\sum_{l \in \mathcal{L}} z_i^{kml}$, the following constraints are imposed which are related to compartment capacities and incompatibilities:

$$ \sum_{i \in \mathcal{N} \setminus \{0\}} \sum_{m \in \mathcal{M}} d_i^m z_i^{kml} \le Q^l \qquad \forall k \in \mathcal{K}, \forall l \in \mathcal{L} \quad (4a) $$

$$ z_i^{kml} + z_j^{km'l} \le 1 \qquad \forall k \in \mathcal{K}, \forall l \in \mathcal{L}, \forall i, j \in \mathcal{N} \setminus \{0\}, \forall (m, m') \in \mathcal{I}_{comm} \quad (4b) $$

$$ z_i^{kml} = 0 \qquad \forall i \in \mathcal{N} \setminus \{0\}, \forall k \in \mathcal{K}, \forall (m, l) \in \mathcal{I}_{comp}. \quad (4c) $$

Constraints (4a) are similar to constraints (3) and replace constraints (1g). They ensure that the capacity of each compartment is satisfied. Constraints (4b) impose that two incompatible commodities are not loaded in the same compartment of the same vehicle. Constraints (4c) impose that each commodity is assigned to a compatible compartment.

An alternative formulation of the problem is possible by replicating the customers as many times as the number of required commodities and including constraints on the compatibility of the customers instead of the compatibility of the commodities. However, this would increase the number of variables $x$ and the number of routing constraints (1b)-(1d).

El Fallahi et al. (2008) propose two algorithms to solve the problem with dedicated compartments: a memetic algorithm, improved by a path relinking method, and a tabu search. Derigs et al. (2011) focus on the problem with incompatibilities and propose different heuristic algorithms, like construction heuristics, local search operators, large neighborhood search. Mirzaei and Wøhlk (2019) study the MCmpt-VRPs with dedicated compartments and propose a branch-and-price algorithm to solve a first variant of the problem where the commodities of a customer can be delivered by different vehicles, as in El Fallahi et al. (2008). They also adapt the algorithm for a second variant where all the commodities of a customer have to be delivered at once by a single vehicle. The computational results indicate that the second variant is easier to solve than the first one.

A MCmpt-VRP where the compartments are flexible and their size becomes a decision variable of the problem is addressed in Henke et al. (2015), Henke et al. (2019) and Heßler (2021). Each compartment may be loaded with any commodity. Each vehicle has a maximum number of compartments, possibly lower than the number of commodities, and the capacity of the compartments is multiple of a defined unit capacity. Henke et al. (2015) propose a variable neighborhood search algorithm while Henke et al. (2019) propose a MILP formulation with three-index decision variables, and develop a branch-and-cut algorithm to solve the problem. Recently, Heßler (2021) propose a three-index MILP formulation for the MCmpt-VRP where the compartment size is continuous. The author adapted the branch-and-cut of Henke et al. (2019) to the case of continuous compartment size and also proposed
an extension of the classical formulation of the CVRP based on two-index variables and an extended model involving route variables. These formulations are able to tackle both continuous and discrete compartment sizes and are solved with branch-and-cut and branch-and-price-and-cut algorithms, respectively.

Moon et al. (2020) study an extension of the MCmpt-VRP that includes the decision on the location of a set of depots, and the possibility for a vehicle to perform several trips. The compartments of the vehicles are dedicated. The authors propose a mathematical formulation, a constructive heuristic, and a population-based algorithm.

The papers reviewed above study the MCmpt-VRPs without specific connection to practical applications. In the following, we analyse contributions which instead consider problems motivated by a real case. As the specific settings of the problems studied are application-dependent, we classify the contributions on the basis of the application tackled.

## Petroleum distribution

The petroleum/fuel products distribution problem is known as the petrol station replenishment problem (Cornillier et al., 2008a). It is the most widely studied application of MCmpt-VRPs. The objective is to minimize the transportation costs for the distribution of several fuel products to a set of fuel stations (customers) using vehicles with multiple compartments since the fuel products cannot be mixed. Hence, each fuel product represents a commodity. Since accidental mixing of fuel products can be hazardous, compartments are not flexible and well separated from each other (Chajakis and Guignard, 2003). According to Cornillier et al. (2008a), compartments are usually not equipped with debit meters, which implies that when a delivery is made from a compartment to a tank in the fuel station, all the quantity loaded in the compartment has to be delivered. Consequently, each compartment is dedicated to a single customer and one commodity. Several compartments can be used to deliver a single commodity. Note that other requirements may be imposed on the order in which compartments are emptied to ensure the stability of the vehicle (Cornillier et al., 2008a). In the problem studied in Cornillier et al. (2008a), all commodities a customer requires must be delivered at once by a single vehicle. In practice, a vehicle contains 3 to 6 compartments, and stations require 2 to 3 fuel products. Hence, the number of stations visited on a given route rarely exceeds 2. Moreover, the quantity of a fuel product delivered to a station is a decision variable. It has to be sufficient to cover the demand for this product but must not exceed the capacity of the tank at the station.

The first study on the petroleum products distribution problem can be credited to Brown and Graves (1981). They studied a particular case considering only direct trips to the stations and time windows for the delivery. Later, several researchers studied the problem. Avella et al. (2004) consider a case where the vehicle compartments cannot be partially filled: they have to be either completely filled or empty. Cornillier et al. (2009) study an extension of the problem introduced in Cornillier et al. (2008a) where stations must be served within specified time windows. In that case, a vehicle can perform several trips during the one-day planning horizon. The multi-depot version of the problem is studied in Cornillier et al. (2012), where a heuristic is proposed. Since large customer demands often require multiple deliveries, Wang et al. (2020) allow split deliveries and multiple trips. Christiansen et al. (2015) propose a maritime application where the fuel is distributed to ships (the customers) by a fleet of vessels. The supply vessels load the fuel at the refineries in the port area and then deliver it
to a given set of ships within specified time windows. A ship can order more than one fuel type and
can be served by different vessels. The authors propose a MILP model for the problem and perform
a computational study based on real-life instances.

Petroleum products are usually delivered over a planning horizon of several days. Hence, they integrate inventory management for the tanks in the stations. The goal is typically to determine the distribution plan minimizing the routing and, in some cases, the inventory costs (see Cornillier et al. (2008b), Popović et al. (2012) and Vidović et al. (2014)).

Recently, Sun et al. (2021) considered a petroleum distribution problem where vehicles are equipped with debit meters such that the product loaded in a single compartment can serve multiple customers. Different types of vehicles are considered, with different compartment features. The problem is to select the suitable vehicles for delivery and to route the selected vehicles to minimize the total routing cost.

Waste collection

Waste collection typically involves different types of waste, for example, general waste, glass, paper,
and plastic (Golden et al., 2002). Since each type of waste has a specific disposal or recycling process,
it is convenient to consider it as a single commodity. If all commodities are aggregated, they must be
sorted when they arrive at the depot, which is a complex and time-consuming task. Nowadays, waste
is usually sorted by the users. Then, the collection can be performed by decomposing the problem
by commodity (dedicated vehicles are used for each type of waste) or by using vehicles with multiple
compartments. In the latter case, each compartment is dedicated to a single commodity. Muyldermans
and Pang (2010) study the case where compartments are not flexible and conduct experiments that
show that using vehicles with multiple compartments is beneficial, especially when the number of
commodities increases, when the vehicle capacity increases, when a large number of customers request
the collection of all commodities, when the customer density is low and when the depot is centrally
located in the collection area. Henke et al. (2019) study the case where compartments are flexible.
This comes from a real-world application where different types of glass (colorless, green, brown) have
to be collected. The authors performed experiments to assess the benefit of using discrete flexible
multi-compartment vehicles instead of single-compartment vehicles. Their analysis revealed that using
discrete flexible multi-compartment vehicles permits reducing the average number of vehicles (from
3.2 to 2.0) and decreasing the average routing cost by 34.8%. Henke et al. (2019) and Heßler (2021)
studied the impact on the total cost of using continuous versus discrete flexible size compartments.
Henke et al. (2019) reported an average cost reduction of 2.39% with continuous flexible sizes. Heßler
(2021) reported an average cost reduction from less than 1% when the discrete compartment size
is small (5% of the vehicle capacity) to more than 16% when the compartment size is large (50%
of the vehicle capacity). Both studies observed that cost reduction increases when the number of
commodities increases.

There are several papers on vehicle routing with applications to waste collection that only consider
one compartment. In this case, the collection is typically separated by commodity and belongs to the
Case 2 mentioned in the Introduction (see Delgado-Antequera et al. (2020)). The interested reader
can refer to the review by Ghiani et al. (2013).
## Livestock collection

Transportation of live animals involves a fleet of heterogeneous vehicles with limited capacity that collect animals from a set of farms to deliver them to a central slaughterhouse over a planning horizon of several days (Gribkovskaia et al., 2006). The slaughterhouse has a demand for several types of animals (bovines, sheep, pigs). Each day, vehicles with different compartments collect the animals to satisfy the demand at the slaughterhouse. Due to animal welfare regulations, different types of animals cannot be mixed inside the same compartment. Thus, it is natural to consider each type of animal as a commodity and to impose incompatibility among commodities. A farm can be visited by several vehicles, but all the animals of the same type must be collected at once by a single vehicle. The planning extends over several days since it is possible to keep the animals at the slaughterhouse, which makes it possible to anticipate some demands during the collection.

If we focus on the vehicle routing part of the problem, the vehicles have compartments, and different types of animals cannot be mixed inside the same compartment. In (Oppen et al., 2010), vehicles are divided horizontally into three sections with permanent partitions. It is possible to split these sections into upper and lower parts using a movable floor. Some vehicles have enough height to have pigs or sheep in the upper compartment and bovines in the lower. Since the loading operations are only done from the rear of the vehicles and different animals cannot share the same compartment, the order in which the animals are loaded into the vehicle is critical to optimize capacity. Solution methods for the problem are presented in Gribkovskaia et al. (2006), Oppen and Løkketangen (2008) and Oppen et al. (2010). Miranda-De La Lama et al. (2014) provide a general review on livestock transportation.

## Food transportation

MCmpt-VRPs may arise in food transportation for two main reasons: preserving products quality and providing the required temperature, as some products require refrigeration during transportation.

Caramia and Guerriero (2010) and Polat and Topaloğlu (2022) study a milk collection problem where different types of raw milk produced by the farmers have to be transported in vehicles with multiple compartments. The different types of raw milk should not be mixed in order to preserve their qualities, and therefore correspond to different commodities. The compartments are not flexible, and each compartment can be filled with a single commodity. Each farmer can be visited by several vehicles, even for the delivery of the same commodity. Similar problems are studied in El Fallahi et al. (2008) for distributing cattle food to farms and in Lahyani et al. (2015) for the collection of olive oils in Tunisia.

Chen et al. (2019) solve a MCmpt-VRP for a cold-chain distribution company which manages the distribution of fresh perishable foods. Each commodity represents a group of products that has to be transported within a specific temperature range. Each compartment is dedicated to a single commodity. Chajakis and Guignard (2003), Ostermeier and Hübner (2018) and Ohmori and Yoshimoto (2021) consider similar problems where the compartments correspond to different temperature ranges. Chen et al. (2020) study a MCmpt-VRP with time windows arising in the delivery of perishable foods, which considers not only the travel cost and fixed cost of vehicles but also the refrigeration cost as well as carbon emissions. Recently, Wang et al. (2023) studied a MCmpt-VRP in the context of perishable food delivery. Multiple compartments are used to set specific temperature and humidity conditions. This prevents the quality of products such as fruit and vegetables from deteriorating
during transportation.

Eshtehadi et al. (2020) consider a MCmpt-VRP in the city logistics context. Customers purchase different types of commodities online and require delivery. Some of these commodities might need temperature-controlled transportation. Thus, multi-compartment vehicles perform deliveries within the chosen time windows. The authors minimize an objective function considering fuel costs, driver wage(s), and temperature costs when products must be kept at certain temperatures during transportation. Vehicles have different compartments with individual and independent temperature values, which allow them to carry the different types of commodities. They develop an adaptive large neighborhood search algorithm.

As a final consideration about the applications of MCmpt-VRP reviewed above, we note that the presence of multiple compartments increases the complexity of the problem, especially when compartments are flexible. This motivated the choice to focus on heuristic approaches, which are much better suited for real applications. All problems share the complexity of managing the compartment capacity simultaneously with routing decisions. In petroleum distribution, the routing part is limited as routes tend to be short. However, in other applications (like waste management), compartment management might strongly impact route shapes.

## 3.2 Multi-trip vehicle routing problems

Battarra et al. (2009) introduced the first Multi-Commodity Multi-Trip VRP with Time Windows (MC-MTVRP-TW). We refer the reader to Cattaruzza et al. (2016) for a review of the MTVRPs. In general, in a MTVRP, each vehicle is allowed to perform several trips during the planning horizon.

In the MC-MTVRP-TW (see Battarra et al. (2009) and Cattaruzza et al. (2014)), it is assumed that commodities are incompatible and cannot be transported during the same trip. However, a vehicle can deliver incompatible commodities on different trips. Consequently, the commodities a customer requires are delivered on different trips. Time windows are not associated with the customers but with the commodities requested by each customer. The objective is to minimize the size of the fleet. Ties are broken by minimizing the routing cost.

From the modeling point of view, formulation (1) can be adapted to the multi-trip case as follows. We assume that, consistently with formulation (1), the objective function is to minimize the routing cost. The set of trips is denoted by $\mathcal{R}$. Decision variables $x$ and $z$ are indexed on trip $r \in \mathcal{R}$. Note that, as in the case of MCmpt-VRP with incompatibilities, we use $z$ variables instead of $y$ variables to represent the assignment of a commodity required by a customer to a trip of a vehicle. The set of incompatible commodities is denoted by $\mathcal{I}_{comm}$, as above. Therefore, the formulation of the Multi-Commodity Multi-Trip VRP (MC-MTVRP) is as follows.
$$ \min \sum_{k \in \mathcal{K}} \sum_{r \in \mathcal{R}} \sum_{(i,j) \in \mathcal{A}} c_{ij} x_{ij}^{kr} \qquad (5a) $$

$$ \text{s.t.} \quad \sum_{j \in \delta^-(i)} x_{ij}^{kr} = \sum_{j \in \delta^+(i)} x_{ij}^{kr} \qquad \forall i \in \mathcal{N} \setminus \{0\}, \forall k \in \mathcal{K}, \forall r \in \mathcal{R} \qquad (5b) $$

$$ \sum_{j \in \delta^+(0)} x_{0j}^{kr} \le 1 \qquad \forall k \in \mathcal{K}, \forall r \in \mathcal{R} \qquad (5c) $$

$$ \sum_{i,j \in S} x_{ij}^{kr} \le |S| - 1 \qquad \forall k \in \mathcal{K}, \forall r \in \mathcal{R}, \forall S \subset \mathcal{N} \setminus \{0\}, |S| \ge 2 \qquad (5d) $$

$$ \sum_{k \in \mathcal{K}} \sum_{r \in \mathcal{R}} z_i^{kmr} = 1 \qquad \forall i \in \mathcal{N} \setminus \{0\}, \forall m \in \mathcal{M} \qquad (5e) $$

$$ \sum_{m \in \mathcal{M}} z_i^{kmr} \le |\mathcal{M}| \sum_{j \in \delta^+(i)} x_{ij}^{kr} \qquad \forall i \in \mathcal{N} \setminus \{0\}, \forall k \in \mathcal{K}, \forall r \in \mathcal{R} \qquad (5f) $$

$$ \sum_{i \in \mathcal{N} \setminus \{0\}} \sum_{m \in \mathcal{M}} d_i^m z_i^{kmr} \le Q \qquad \forall k \in \mathcal{K}, \forall r \in \mathcal{R} \qquad (5g) $$

$$ z_i^{kmr} + z_j^{km'r} \le 1 \qquad \forall k \in \mathcal{K}, \forall r \in \mathcal{R}, \forall i, j \in \mathcal{N} \setminus \{0\}, \forall (m, m') \in \mathcal{I}_{\text{comm}} \qquad (5h) $$

$$ x_{ij}^{kr} \in \{0,1\} \qquad \forall i, j \in \mathcal{N}, \forall k \in \mathcal{K}, \forall r \in \mathcal{R} \qquad (5i) $$

$$ z_i^{kmr} \in \{0,1\} \qquad \forall i \in \mathcal{N} \setminus \{0\}, \forall k \in \mathcal{K}, \forall r \in \mathcal{R}, \forall m \in \mathcal{M}. \qquad (5j) $$

The objective function (5a) and constraints (5b)–(5g), (5i)–(5j) have a one-to-one correspondence with formulation (1). Constraints (5h) model incompatibilities among commodities.

In Battarra et al. (2009), the application that motivates the use of a MC-MTVRP-TW is the distribution of three commodities to supermarkets: vegetables, fresh products, and non-perishable items. The regulation imposes that these commodities are incompatible with each other and cannot be transported together in a vehicle. The authors propose an adaptive mechanism to guide simple heuristics. Cattaruzza et al. (2014) develop an iterated local search for the MC-MTVRP-TW.

It should be noted that many of the papers dealing with petroleum/fuel distribution or food transportation reviewed in Section 3.1 allow multiple trips to vehicles. However, the multi-trip feature results from the limited capacity and limited number of vehicles and is not the answer to the incompatibility among commodities, which is managed by multiple compartments.

## 3.3 Research directions

MCmpt-VRPs have been mostly studied in specific settings related to the applications under study. Finding the most appropriate formulation and the most efficient solution algorithm for the basic setting of this class of problems would be worth of further research.

More and more integrated problems receive research attention thanks to technological and algorithmic advances. For example, integrating the multi-trip and flexible multi-compartment features would give rise to a challenging problem where the routing cost should be minimized, as well as the cost of changes in the compartments between trips. This problem may also be viewed as a bi-objective optimization problem.

Multi-trip problems where the customers set different due dates for different commodities also constitute a promising research direction. These problems might arise in fast delivery services to
retailers that, due to limited storage space, prefer to get commodities separately.

Finally, another interesting research direction would be to study MCmpt-VRPs from a strategic point of view. Vehicles are associated with different fixed and operating costs according to their equipment (with or without compartments, flexible or fixed compartments). Thus, a problem that would be worth studying is about deciding on which type of vehicles to invest, before setting up the distribution service. This problem might be handled by combining MCmpt-VRPs with investment-related decisions.

# 4 Compatible commodities

This section is devoted to routing problems with compatible commodities. Vehicles have a single compartment, and different commodities are transported. The explicit consideration of multiple commodities may be either due to conditions that require it or for convenience purposes. In this section, based on the reasons for explicitly considering multiple commodities, we first review, in Section 4.1, the papers that study problems where the commodities are indivisible. In that case, it may be beneficial to consider them explicitly. Then, in Section 4.2, we review the literature on problems considering multiple origins and destinations. In Section 4.3, we survey the contributions on problems where commodities have different features that impact the constraints or solution value. Section 4.4 proposes future research directions.

## 4.1 Indivisible commodities

In this section, we consider multi-commodity routing problems where commodities are indivisible, that is, each commodity is delivered in a single visit. However, customers may require more than one commodity and may be visited multiple times. No condition imposes to consider the commodities explicitly.

The main problem we identified in this class is the Commodity Constrained Split Delivery VRP (C-SDVRP). As mentioned in the Introduction, the aggregation of commodities leads to large customer demands when multiple commodities are compatible. Hence, splitting the delivery optimizes the load of the vehicles and then reduces the transportation cost. However, this is not practical for the customers if a single commodity is split. Then, a customer may need to handle the deliveries of the same commodity several times during the planning horizon. This is why it is required that each commodity is delivered in a single visit. The C-SDVRP can be modeled as formulation (1).

The C-SDVRP is of practical relevance when the demand consists of a set of items with different sizes (Nakao and Nagamochi, 2007). Indeed, in this case, the solution of the SDVRP may not be feasible since it might provide a solution where the split does not respect the item sizes. Nakao and Nagamochi (2007) introduce this problem under the name Discrete Split Delivery VRP and propose a heuristic based on dynamic programming. Another application of the C-SDVRP (Gu et al., 2019) occurs when there are different categories of products like dairy products, fresh fruits, or vegetables. A group of products represents a commodity, and commodities are compatible. From the customer point of view, it is acceptable to have more than one delivery, but splitting the delivery of a specific commodity (a category of products) is not practical. When few commodities are considered, the
number of deliveries to a customer remains acceptable. Ceselli et al. (2009) study a rich VRP where the demand of a customer consists of a set of items where each item is a pallet of products with specific dimensions. Each item represents a commodity. The delivery of a customer can be split, but it is not possible to split the delivery of an item. They also consider incompatibilities between commodities and vehicles. The authors propose a three-phase column generation approach.

Archetti et al. (2014a) introduce the name C-SDVRP, and propose a branch-and-cut algorithm to solve small instances, and a heuristic for medium and large instances. Archetti et al. (2015) propose an extended formulation for the C-SDVRP and develop a branch-price-and-cut algorithm. Gschwind et al. (2019) develop a new branch-price-and-cut algorithm that includes stabilization techniques and dual optimal inequalities. Gu et al. (2019) propose an Adaptive Large Neighborhood Search (ALNS) heuristic to address medium and large size instances.

Some extensions of the C-SDVRP have also been considered. Salani and Vacca (2011) study an extension where any subset of commodities required by a customer represents an order. Each order is associated with a service time, which may not be linear in the number of commodities or the size of the order. The problem is solved through a branch-and-price algorithm. Fernández et al. (2018) study a C-SDVRP with multiple depots. Note that Fernández et al. (2018) do not use the term commodity in their paper. However, the problem they study can be considered as a multi-commodity problem, as described in the following. Each depot is managed by a carrier and is associated with a commodity that represents a product provided by the carrier. A customer may request several commodities, i.e., products from different carriers. Fernández et al. (2018) study a collaboration scheme among carriers such that a carrier can deliver to its customers a product on behalf of other carriers, to minimize the total routing cost. An additional constraint ensures that each carrier only visits a subset of its initial customers. Thus, in this case, commodities represent the products associated with each carrier, and each commodity is associated with a different depot. Rahmani et al. (2016) consider an extension of the C-SDVRP with multiple depots and a two-echelon supply chain with a single supplier that delivers to the depots. The choice of which depots to open is also part of the problem. Open depots are processing centers that transform a raw product received by the supplier into a final product to send to customers. In each depot, a single product (commodity) is handled. All routes in the second echelon start and end at the same depot. However, different depots can be visited in the meantime to pickup commodities delivered during the route.

Gu et al. (2022) extend the C-SDVRP with multiple depots and consider a two-echelon supply chain where the first echelon is the collection of a subset of commodities from suppliers to depots with direct trips, and the second is the distribution of commodities from depots to customers.

## 4.2 Multiple origins and destinations

In this section, we consider problems where commodities have to be transported from multiple origins to multiple destinations. This is by far the largest class of problems with compatible commodities. For this reason, we further classify the contributions according to the specific problem studied.
### 4.2.1 Multi-commodity pickup and delivery problems

The Pickup and Delivery Traveling Salesman Problem (PDTSP), also known as the one-commodity PDTSP (1-PDTSP), introduced by Hernández-Pérez and Salazar-González (2004), is a generalization of the classical Traveling Salesman Problem (TSP) where the customers are divided into two groups: delivery customers that require a given amount of a commodity, and pickup customers that provide a given amount of the same commodity. A vehicle with a fixed capacity has to perform a single tour to visit all customers, starting and ending at the depot. The objective of the 1-PDTSP is to design a minimum-cost Hamiltonian cycle such that the vehicle capacity is never exceeded. As customers require and deliver the same commodity, no pairing between pickup and delivery customers exists, i.e., the commodity picked up at a given customer can be delivered to any other customer. According to the classification of pickup and delivery problems (Battarra et al., 2014), this definition corresponds to a many-to-many problem where a single commodity has multiple origins and destinations. For extensive reviews of the pickup and delivery problems, the interested reader is referred to the surveys by Parragh et al. (2008) and Berbeglia et al. (2007). A recent review on vehicle routing with simultaneous pickup and delivery can be found in Koç et al. (2020), which covers broader literature.

The one-to-one Multi-Commodity Pickup and Delivery Traveling Salesman Problem (one-to-one m-PDTSP) was introduced by Hernández-Pérez and Salazar-González (2009). A set of objects (commodities) are transported by a single vehicle with capacity $Q$. Note that the multi-commodity aspect of this problem only imposes to introduce precedence constraints between pickup and delivery locations and does not require an explicit consideration of the different commodities.

In Hernández-Pérez and Salazar-González (2014) the original one-to-one m-PDTSP is extended to the case where customers provide or require known amounts of $m$ different commodities. A unit of a commodity collected from a customer can be delivered to any other customer that requires the same commodity. The resulting problem is, then, a many-to-many m-PDTSP. The initial quantity of each commodity in the vehicle is also a decision variable of the problem. The authors use the same acronym, namely m-PDTSP, to identify this extension. In this section, we will use m-PDTSP to indicate this more general problem. In the same paper, the authors propose a mathematical formulation for the m-PDTSP, which corresponds to formulation (1) with the following modifications. First, index $k$ is removed from variables $x$ (as we have a single vehicle), and variables $y$ are no longer needed (as each customer is visited exactly once by the vehicle). This means that the sum of incoming and outgoing arcs for each node is set to 1 in constraints (1b) and that constraints (1c), (1e) and (1f) are removed. Also, additional variables $q_{ij}^m \ge 0$ are introduced that represent the quantity of each commodity $m \in \mathcal{M}$ transported along arc $(i, j)$. The following constraints are then added:

$$ \sum_{j \in \delta^{-}(i)} q_{ij}^{m} - \sum_{j \in \delta^{+}(i)} q_{ji}^{m} = d_{i}^{m} \qquad \forall i \in \mathcal{N} \setminus \{0\}, m \in \mathcal{M} \qquad (6a) $$

$$ q_{0i}^{m} = 0 \qquad \forall i \in \mathcal{N} \setminus \{0\}, m \in \mathcal{M}, \qquad (6b) $$

$$ \sum_{m \in \mathcal{M}} q_{ij}^{m} \le Qx_{ij} \qquad \forall i \in \mathcal{N}, j \in \mathcal{N} \setminus \{0\}. \qquad (6c) $$

Equalities (6a) and (6b) are flow conservation constraints while (6c) are capacity constraints.
In addition to the problem formulation, Hernández-Pérez and Salazar-González (2014) propose a branch-and-cut algorithm. In Hernández-Pérez et al. (2016), a three stage algorithm with constructive heuristics and local search operators for the m-PDTSP is proposed. Recently, Lu et al. (2019) improved, on average, the computational results of Hernández-Pérez et al. (2016) with a population algorithm based on randomized tabu thresholding.

An application of the 1-PDTSP is the repositioning of bikes in bike-sharing systems (see, for example, (Raviv et al., 2013)), where a capacitated vehicle picks up or delivers the bikes from/to the bike stations to restore the initial configuration of the system. As pointed out by Hernández-Pérez et al. (2016), if one considers different types of bikes (for instance, with and without baby chairs), each type of bike represents a commodity, and then the problem to solve is the m-PDTSP. In the context of bank services, Hernández-Pérez and Salazar-González (2007) study a 1-PDTSP where branches of a bank provide or require money from the main branch. As the authors pointed out, if we consider bills and coins instead of money, the problem to be solved is an m-PDTSP with two commodities.

Erdoğan et al. (2010) consider the Non-Preemptive Capacitated Swapping Problem. This problem is slightly different from the m-PDTSP for the following reasons: (i) each customer can require a unit of a single commodity and can provide a unit of a single commodity; and (ii) there exists transshipment locations where commodities can be dropped off. Hence, the route of the vehicle is not a Hamiltonian cycle anymore. Erdoğan et al. (2010) provide mathematical programming formulations together with valid inequalities and incorporate them in a branch-and-cut algorithm. Note that even if the straightforward formulation explicitly considers the commodities, unitary demand, and supply permit provide formulations where commodities do not appear.

A generalization of the m-PDTSP is studied in Li et al. (2019) and in Zhang et al. (2019). The problem is related to a real-life application faced by a fast fashion retailer with a warehouse and a set of stores. Each week, based on the forecasted demands, a fleet of vehicles picks up and delivers several products from/to the stores to balance the storage levels of these products at the stores. Moreover, products can be picked up and delivered from/to the warehouse with an additional handling cost. The model generalizes the m-PDTSP by considering multiple vehicles and adding the handling cost at the warehouse to the distance traveled in the objective function. Furthermore, a branch-price-and-cut algorithm is developed in Li et al. (2019) whereas a heuristic approach is proposed in Zhang et al. (2019).

A variant of the m-PDTSP, which considers multiple vehicles, is studied in Zhang et al. (2020) for a bike repositioning and recycling problem that considers two different bike types, i.e., usable bikes and broken ones. The usable bikes balance user demands, while the broken bikes are collected from stations and transported to depots. Hence, trucks are not allowed to deliver broken bikes to stations. An adaptive tabu search algorithm is proposed to solve the problem.

### 4.2.2 Multi-commodity routing problems with multiple depots

In this section, we review contributions to various problems considering multiple depots with limited quantities of commodities. Due to these limited quantities, the assignment of commodity requests to depots must be determined to ensure that the availability constraints are not violated, which requires explicit consideration of commodities. In the following, we first detail the mathematical
modeling of the multi-commodity routing problem with multiple depots. Then, we review the different applications that motivate the study of this class of problems.

Let $\mathcal{P}$ be the set of depots and let $\mathcal{K}^p$ be the set of vehicles available at depot $p \in \mathcal{P}$, with $\mathcal{K} = \bigcup_{p \in \mathcal{P}} \mathcal{K}^p$. Moreover, let $D_p^m$ be the maximum quantity of commodity $m \in \mathcal{M}$ available at depot $p \in \mathcal{P}$. We distinguish two cases for the modeling, depending on whether or not customer demands can be split.

The first case is when all commodities, customer requests, must be served from a single depot. The following decision variables are then introduced: $z_i^p$ is a binary variable equal to one if the customer $i$ is served from depot $p$. The problem can then be modeled as (1a)-(1f), (1h)-(1i) and the following constraints:

$$ \sum_{i \in \mathcal{N} \setminus \{0\}} d_i^m z_i^p \leq D_p^m \qquad \forall p \in \mathcal{P}, m \in \mathcal{M} \qquad (7a) $$

$$ z_i^p \geq \sum_{j \in \delta^+(i)} x_{ij}^k \qquad \forall i \in \mathcal{N} \setminus \{0\}, p \in \mathcal{P}, k \in \mathcal{K}^p \qquad (7b) $$

$$ \sum_{p \in \mathcal{P}} z_i^p = 1 \qquad \forall i \in \mathcal{N} \setminus \{0\}. \qquad (7c) $$

Constraints (7a) ensure that the quantity of each commodity sent from each depot does not exceed the availability. Constraints (7b) link the routing variables with the $z_i^p$ decision variables. In particular, customers can be served by a vehicle assigned to a certain depot, only if they are themselves assigned to the same depot. Finally, constraints (7c) ensure that each customer is served from a single depot.

It can be noticed that the proposed model allows the service of a customer with several vehicles as long as these vehicles leave from the same depot. If one wants to add the constraint that all commodities must be delivered to each customer at once with a single vehicle, then, as mentioned at the end of Section 2, the delivery constraints and the vehicle capacity constraints can be written by aggregating the commodities.

The second case is when commodities requested by a customer may be delivered from different depots. The following decision variables are used: $z_i^{pm}$ is a binary variable equal to one if commodity $m$ of customer $i$ is served from depot $p$. Note that these variables can be deduced from the $y_i^{km}$ variables as $z_i^{pm} = \sum_{k \in \mathcal{K}^p} y_i^{km}$. The difference with respect to the former case is that constraints (7a) are replaced by:

$$ \sum_{i \in \mathcal{N} \setminus \{0\}} d_i^m z_i^{pm} \leq D_p^m \qquad \forall m \in \mathcal{M}, p \in \mathcal{P}. \qquad (8) $$

In the following, we review the different problems that fall in the category of routing problems with multiple depots and limited available quantities: the Many-to-Many Multi-Commodity Inventory Routing Problem (MCIRP), the Multi-Commodity Location Routing Problem (MCLRP) and the transportation of multiple commodities in disaster relief. Note that some problems might not use the terminology *depot*, but the concept is the same.

## Many-to-Many Multi-Commodity Inventory Routing Problem

The classical Inventory Routing Problem (IRP) combines vehicle routing and inventory management. It considers the distribution of a single commodity from a supplier (the depot) to a set of
customers over a given planning horizon. In each period, a quantity of the commodity is available
at the supplier, with the possibility to store it. Each customer consumes the commodity in given
quantities over time, keeping a local stock of the commodity up to a maximum quantity. A fleet of
homogeneous capacitated vehicles is available to deliver the commodity. The objective is to minimize
the average distribution cost plus the inventory cost over the planning horizon without generating any
stockout at the customers. The interested reader is referred to the literature reviews on the IRP by
Coelho et al. (2014) and Bertazzi and Speranza (2013).

The Multi-Commodity Inventory Routing Problem (MCIRP) is the extension of the IRP where multiple commodities have to be delivered to the customers. It is often referred in the literature as multi-product IRP. Usually, multiple commodities have to be considered explicitly when they share some common resources (storage capacity, vehicle capacity,...). They may also have different inventory costs and customers' consumption rates. Several applications motivate the study of the MCIRP, like the distribution of perishable commodities, transportation of gases by tanker trucks, and the component delivery in the automotive industry (Coelho and Laporte, 2013). The MCIRP applications are usually classified on the basis of the structure of the distribution network (cardinality of the set of origins and of the set of destinations): *one-to-one*, *one-to-many*, *many-to-one* or *many-to-many*. Since in this section we focus on the problems that consider multiple origins and multiple destinations, in the following, we only review the papers on *many-to-many* MCIRP. Note that the MCIRP with other network structure is reviewed in Section 4.3.2 with a focus on heterogeneous features of commodities.

The *many-to-many* case considers several suppliers and several customers. It is a special case of routing problems with multiple commodities and origins, where the origins correspond with the suppliers. The limited available quantity at the origins corresponds with the limited production rate $D_p^m$ at the suppliers. Ramkumar et al. (2012) study a special case in which each route begins at the depot and consists of a sequence of pickups from suppliers, followed by a sequence of deliveries to customers before returning to the depot. At each period, the collection and the delivery of an individual commodity may be split, i.e., it may be performed by different vehicles. Each commodity is produced by a single supplier. The authors propose a MILP formulation for the problem. Ghorbani and Jokar (2016) study a variant with a two-echelon supply chain: each supplier serves one or several depots using direct trips, and each depot serves several customers performing routes. All the commodities a customer requires must be served from a single depot. Decisions involve the depots to open and the assignment of customers to depots. The authors propose a MILP formulation and a hybrid algorithm based on Simulated Annealing (SA).

## Multi-Commodity Location Routing Problem

In the classical Location Routing Problem (LRP), there is a set of potential depots associated with an opening cost. Customers with known demands for a single commodity must be served from the opened depots using a fleet of vehicles. Each customer has to be visited by a single vehicle. The LRP consists in determining the depots to open, in assigning each customer to one open depot, and in determining the vehicle routes to serve customers from the open depots. The objective is to minimize the total cost: opening cost of the depots, fixed cost of the vehicles used, and routing cost (Prodhon and Prins, 2014). For a review of the LRP, the interested reader is referred to the surveys by Prodhon and Prins (2014), Drexel and Schneider (2015) and Mara et al. (2021).
The Multi-Commodity Location Routing Problem (MCLRP) is studied in the context of many-to-
many LRP. The network structure usually consists of three layers with suppliers, potential depots to
be opened, and customers. Customers have a known demand for commodities, and each supplier can
produce one or several commodities. At each open depot, a fleet of vehicles performs routes with pickup
operations at the suppliers and delivery operations at the customers. Another fleet of vehicles can
perform trips between the open depots to move the commodities among them. All the commodities
are compatible, and thus can be mixed inside the vehicles. The objective is to minimize the total
opening and transportation cost. The multi-commodity aspect has to be explicitly considered when:
(i) depots can manage multiple commodities, (ii) commodities required by a customer may be provided
from any supplier or depot. The many-to-many LRP with multiple commodities was introduced by
Nagy and Salhi (1998). However, the authors assumed that a supplier-customer pair is associated with
each commodity. Hence, the multi-commodity aspect is not explicitly considered, and the problem is
modeled as a one-to-one pickup and delivery problem.

Some studies on MCLRPs have been motivated by applications. Burks (2006) studies a MCLRP for the distribution of personnel, equipment, and material to a theater of war. Customers are cities, suppliers are airports, seaports or train stations, and depots are where the vehicles are based. Multiple commodities are considered explicitly since the same resources transport materials and personnel to the theater of war. Rieck et al. (2014) study a MCLRP motivated by a real-life application in the timber-trade industry. Suppliers are sawmills and wood manufacturers, and customers are distributors of wood products. Sawmills produce some commodities like beams and planks from different kinds of wood, whereas wood manufacturers produce wood for construction or indoor equipment (e.g., door and window frames). Distributors of wood require a mix of all these commodities for their production or retail activities. Shang et al. (2022) study an application of MCLRP in the healthcare supply chain. A supplier has to distribute several medical products (the commodities) to a set of hospitals. To do so, the suppliers rely on intermediate warehouses that can be opened in some hospitals.

Gianessi et al. (2015) study a particular variant of the MCLRP: the multi-commodity-ring LRP, where the depots have to be connected via a ring, i.e., the selected direct trips between the open depots must form a Hamiltonian cycle. The application is in city logistics, where depots represent urban distribution centers. The ring is used to transport massive flows of goods from one depot to another. Final customers are either delivery points or pickup points. They are served by electric vehicles performing routes. Suppliers represent the source of goods outside the city. Each supplier is associated with a single commodity representing the goods that must be sent/collected by this supplier.

Recently, Azizi and Hu (2020) presented a MCLRP with the possibility of direct shipments from suppliers to customers. Several commodities are available at suppliers that can be visited more than once. Each customer requires only one commodity that has to be delivered by a single vehicle. Commodities have to be explicitly considered in order to satisfy maximum availability constraints at suppliers. The authors also study a scenario where commodities are incompatible and cannot be mixed in the same vehicle. The results show that considering compatible commodities permits to decrease costs by up to 31%.

Transportation of multiple commodities in disaster relief
Golden et al. (2014) define as disaster an extraordinary event that occurs with or without limited forewarning and has devastating effects on the population (e.g., earthquakes, hurricanes, terrorist attacks, and industry disasters). The response phase considers the logistics operations to satisfy the urgent needs of a population just after a disaster. Unlike most VRPs, the goal of the VRPs in disaster relief is to provide the best possible supply regardless of the economic implications rather than to maximize the profit or to meet customer demands at minimum cost (Golden et al., 2014).

Routing problems in disaster response consider a set of supply points (suppliers) and a set of demand points (customers). Each supplier provides one or several commodities in limited quantities. Hence, as for MCLRP, routing problems in disaster response are extensions of routing problems with multiple commodities and multiple depots. The required commodities may be water, food, medicine, clothes, and machinery. Usually, demands are large, and it is necessary to split the delivery to a single customer. Since the commodities have different characteristics, several origins and destinations, they have to be explicitly considered.

Khare et al. (2021) study a two-stage relief delivery model where relief supply is to be distributed from primary depots, where the supply coming from humanitarian organizations and aiding countries is collected, to secondary depots which are areas identified in the vicinity of the affected region. A quantity of each commodity is available at each primary depot, while a demand for each commodity is associated with each secondary depot. Commodities are water, food, sanitation, and medical suppliers. Deliveries of a commodity may be split, and more than one vehicle may serve a secondary depot.

Farahani et al. (2020) provide a review on mass casualty management in disaster scenes.

## 4.3 Commodities with heterogeneous features

This section considers problems where commodities have different features that impact either the constraints or the solution value.

### 4.3.1 Traveling Purchaser Problem

This section presents the case in which customers require multiple commodities, the quantity of each commodity available at the supply node is limited, and the decision is to select the subset of customers to serve and the products to deliver. The Traveling Purchaser Problem (TPP), in which collection operations are performed instead of deliveries, falls into this class. The TPP is an extension of the TSP in which a purchaser based at the depot has a list of commodities to buy with an associated required quantity $d^m$ for commodity $m \in M$. Each supplier $i$ associated with a node of the graph offers a limited amount $D_i^m$ of each commodity $m$ (possibly zero) at a unit selling price $p_i^m$. The TPP consists in finding an optimal tour, starting and ending at the depot, that visits some suppliers to purchase all the required commodities. Consequently, $|K| = 1$, and the decision variables are no longer indexed by $k$. The fact that not all the suppliers have to be visited is expressed in the mathematical model by introducing a binary variable $z_i$ equal to one if the supplier $i$ is visited, zero otherwise. The objective is to minimize the sum of traveling and purchasing costs.

For the mathematical modeling of the TPP it is possible to distinguish two cases based on price assumptions. When the selling prices $p_i^m$ are heterogeneous, additional decision variables $q_i^m \ge 0$ are
needed to determine the quantity of commodity m collected at supplier i. The formulation is given by:

$$ \min \sum_{(i,j) \in \mathcal{A}} c_{ij}x_{ij} + \sum_{i \in \mathcal{N} \setminus \{0\}} \sum_{m \in \mathcal{M}} p_i^m q_i^m \quad (9a) $$

$$ \sum_{i \in \mathcal{N} \setminus \{0\}} q_i^m \geq d^m \quad \forall m \in \mathcal{M} \quad (9b) $$

$$ q_i^m \leq D_i^m z_i \quad \forall i \in \mathcal{N} \setminus \{0\}, m \in \mathcal{M} \quad (9c) $$

$$ z_i \leq \sum_{j \in \delta^+(i)} x_{ij} \quad \forall i \in \mathcal{N} \setminus \{0\} \quad (9d) $$

and routing constraints (1b) and (1d). Constraints (9b) ensure that the required amount of each commodity has been collected. Constraints (9c) ensure that a positive quantity bounded by the availability of the relevant commodity can be collected at a supplier only if this supplier is visited by the vehicle. Constraints (9d) link the $z_i$ variables with the routing variables.

If all selling prices at the suppliers are identical, i.e., $p_i^m = p^m \forall i \in \mathcal{N} \setminus \{0\}$, then the total price of the products collected is a constant and can be removed from the objective function. Moreover, $q_i^m$ variables are not needed anymore since constraints (9b) and (9c) can be replaced with:

$$ \sum_{i \in \mathcal{N} \setminus \{0\}} D_i^m z_i \geq d^m \quad \forall m \in \mathcal{M}. \quad (10) $$

It can be noticed that, even if all the commodities have the same selling price, constraints (10) explicitly consider the commodities since the amounts offered by the suppliers are different.

There are numerous contributions on the TPP. The interested reader is referred to the recent literature review by Manerba et al. (2017). A typical application is related to a company in charge of collecting several raw materials from a set of reliable suppliers. Another application is the school bus routing, where suppliers correspond to bus stops and the commodities to students (Riera-Ledesma and Salazar-González, 2012). A student may be assigned to different bus stops, and the objective is to find a route for the bus such that all students are picked up at a bus stop while minimizing the total transportation and assignment cost of the students to stops.

Different variants of the TPP have been studied, as surveyed in Manerba et al. (2017). Among them, we mention the multi-vehicle variant in which a fleet of homogeneous capacitated vehicles is available to perform the service. This variant is studied in Choi and Lee (2011), where the authors propose a mathematical formulation of the problem and apply it to a real case.

Gendreau et al. (2016) consider a multi-vehicle TPP with incompatibilities. In this problem, two incompatible commodities cannot be transported in the same vehicle. The authors propose a column generation approach. Bianchessi et al. (2021) present a branch-price-and-cut algorithm for the solution of different variants of the multi-vehicle TPP with unitary demands.

### 4.3.2 Multi-Commodity Inventory Routing Problem

In the IRPs commodities need to be explicitly considered when at least one of the following conditions applies: commodities are associated with different production rates at the origin; with
different costs (holding costs); or with different capacities (inventory capacity) at the customers. In these cases, we talk about Multi-Commodity Inventory Routing Problem (MCIRP). Otherwise, commodities can be aggregated and the problem handled with a single-commodity model.

As mentioned in Section 4.2, MCIRP applications are usually classified in: one-to-one, one-to-many, many-to-one or many-to-many. Since we have already introduced the many-to-many MCIRP in Section 4.2, we only review the remaining classes in the current section to avoid repetitions.

For the mathematical modeling of the MCIRP, we consider the classical one-to-many case with a single supplier and several customers. The supplier produces $r^{mt}$ units of commodity $m$ at period $t$. The demand $d_i^{mt}$ of each customer is indexed by the time period $t \in T$. Each customer $i \in \mathcal{N} \setminus \{0\}$ has an inventory capacity $C_i^m$ and a unit holding cost $h_i^m$ for each commodity $m$. Routing variables $x_{ij}^{kt}$ and $y_i^{mt}$ are indexed by the time period $t$. New decision variables $q_i^{kmt}$ for commodity $m$ have to be introduced to determine the quantity delivered to customer $i$ by vehicle $k$ at period $t$. Moreover, variables $I_0^{mt}$ (resp. $I_i^{mt}$) represent the inventory level of commodity $m$ at the end of period $t$ at the supplier (resp. at the customers). The objective function considers the entire planning horizon and integrates the transportation and holding costs. The formulation is as follows:

$$ \min \sum_{t \in T} \sum_{k \in \mathcal{K}} \sum_{(i,j) \in \mathcal{A}} c_{ij} x_{ij}^{kt} + \sum_{t \in T} \sum_{i \in \mathcal{N} \setminus \{0\}} \sum_{m \in \mathcal{M}} h_i^m I_i^{mt} \quad (11a) $$

$$ \sum_{i \in \mathcal{N} \setminus \{0\}} \sum_{m \in \mathcal{M}} q_i^{kmt} \le Q \qquad \forall k \in \mathcal{K}, \forall t \in T \quad (11b) $$

$$ q_i^{kmt} \le (C_i^m + d_i^{mt}) y_i^{kmt} \qquad \forall i \in \mathcal{N} \setminus \{0\}, \forall k \in \mathcal{K}, \forall m \in \mathcal{M}, \forall t \in T \quad (11c) $$

$$ I_0^{mt} = I_0^{mt-1} + r^{mt} - \sum_{k \in \mathcal{K}} \sum_{i \in \mathcal{N} \setminus \{0\}} q_i^{kmt} \qquad \forall m \in \mathcal{M}, \forall t \in T \quad (11d) $$

$$ I_i^{mt} = I_i^{mt-1} + \sum_{k \in \mathcal{K}} q_i^{kmt} - d_i^{mt} \qquad \forall i \in \mathcal{N} \setminus \{0\}, \forall m \in \mathcal{M}, \forall t \in T \quad (11e) $$

$$ 0 \le I_i^{mt} \le C_i^m \qquad \forall i \in \mathcal{N} \setminus \{0\}, \forall m \in \mathcal{M}, \forall t \in T, \quad (11f) $$

with the addition of routing constraints (1b), (1c), (1d) and (1f) which are defined for all time periods. Note that constraints (1e) are not included since it is not mandatory to visit each customer at each time period. However, $y_i^{mt}$ variables have to be introduced to decide about the subset of customers visited in each time period. As the quantities to deliver are decision variables, the capacity constraints have to be expressed with the $q_i^{kmt}$ variables (constraints (11b)), and the $q_i^{kmt}$ and $y_i^{kmt}$ are linked by constraints (11c). Constraints (11d) and (11e) define inventory levels. Constraints (11f) are storage capacity constraints at the customers. These constraints are defined for each commodity and each time period.

One-to-many is the most common case in which one supplier serves several customers. Coelho and Laporte (2013) propose a MILP formulation and some additional valid inequalities. They develop a branch-and-cut algorithm to solve the problem to optimality. Cordeau et al. (2015) consider a different version of the problem where the commodities are not mixed in customer warehouses and have dedicated storage capacities. The authors propose a three-phase heuristic to tackle this problem. Shaabani and Kamalabadi (2016) study a MCIRP where the commodities are perishable. This results in additional constraints for the storage capacity. Nambirajan et al. (2016) study a replenishment
problem in a two-echelon supply chain. In the first echelon a set of suppliers, each providing a single commodity (e.g., raw materials), supply a central depot. In the second echelon the central depot is in charge of the replenishment of a set of assembly plants that require different commodities. Neves-Moreira et al. (2022) study a MCIRP where commodities can be picked-up at customer locations and used to replenish other customers. The problem is studied under deterministic and uncertain demand scenarios and a branch-and-cut algorithm is proposed. The results show that the option of transferring commodities from one customer to another is very cost-effective when there are several commodities and demand is uncertain.

The case *many-to-one* considers a single depot, multiple suppliers, and only one customer. Moin et al. (2011) study a distribution network where many suppliers deliver to a single assembly plant. The customer requires multiple commodities and each supplier provides a single commodity. A route starts at the depot, visits some suppliers to pick up the commodities, and then visits the customer to deliver the commodities before going back to the depot. A supplier may be visited by more than one vehicle during a given period. Mjirda et al. (2014) propose a two-phase heuristic based on a VNS for the solution of the same problem, whereas Mirzapour Al-e hashem and Rekik (2014) study the same problem with the possibility of transhipment between the suppliers.

### 4.3.3 Transportation of commodities with non-additive characteristics

In this section, we review problems where commodities are associated with non-additive characteristics. This is the case, for instance, for commodities associated with a transportation risk or a temperature requirement. In these cases, when a vehicle is in charge of transporting a set of commodities, it is associated with the highest or the lowest value of the considered characteristic for all the commodities loaded in the vehicle.

A first example is the case of the transportation of Hazardous Materials (HazMat or dangerous goods, e.g., gasoline, toxic gases, dangerous waste, chemicals) where the risk associated with an accident is considered. Commodities are associated with a risk level, and the risk incurred by the vehicle when traversing an arc of the network corresponds with the maximum risk level of the commodities that it carries. Due to its nature, the transportation of hazardous materials is regulated by law in most countries (Holeczek, 2019) and different modes of transportation for HazMat exist, like road, rail, water, air, and pipeline (Erkut et al. (2007), Bianco et al. (2013)). HazMat routing problems often aim at finding one or several paths to route a single commodity from its origin to its destination (Holeczek, 2019). However, selecting optimal routes for each origin-destination pair may result in a dangerous concentration of HazMat transportation on some network links (Iakovou et al., 1999). Hence, recent contributions deal with the problem that explicitly considers multiple HazMat commodities with different origins and/or destinations routed in the same network with shared capacity constraints. However, in most cases, the resulting problem is a multi-commodity network flow problem and, thus, out of the scope of this survey.

To the best of our knowledge, Paredes-Belmar et al. (2017) is the only work to deal with a VRP with multiple commodities in the context of HazMat transportation. They propose a case study in the city of Santiago in Chile. A set of HazMats must be collected by a fleet of homogeneous capacitated vehicles starting and ending their route at a single depot. Each HazMat represents a commodity and
is associated with a level of risk. Commodities are compatible and can be loaded in the same vehicle. One or several commodities must be collected from each customer. The collection at a customer may be split, but a single commodity has to be collected at once. When a vehicle traverses an arc of the network (a street), it generates a risk equal to the highest risk of the commodities currently loaded in the vehicle. Hence, each time a vehicle collects HazMats from a customer, the risk associated with the vehicle either remains the same or increases. The objective that is usually considered is to minimize a weighted sum of transportation cost and risk.

From the modeling perspective, let $c_{ij}^m$ be the weighted cost of traveling from $i$ to $j$ with the risk level of commodity $m$. Since this cost is a weighted sum that includes the risk, the corresponding distance from $i$ to $j$ is not necessarily the shortest one. It can be assumed that the set of commodities $\mathcal{M}$ is ranked from the commodity with the lowest risk to the commodity with the highest risk. Let $\prec$ represent this relation. To take into account the level of risk when a vehicle traverses an arc $(i, j)$, a binary variable $w_{ij}^{km}$ is introduced. It takes value one if the commodity with the highest risk loaded in vehicle $k$ when it traverses $(i, j)$ is $m$, zero otherwise. This means that when $w_{ij}^{km} = 1$ the vehicle contains commodity $m$ and may contain other commodities $m' \prec m$.

The formulation is the following:

$$ \min \sum_{k \in \mathcal{K}} \sum_{(i,j) \in \mathcal{A}} \sum_{m \in \mathcal{M}} c_{ij}^m w_{ij}^{km} \quad (12a) $$

$$ \sum_{m \in \mathcal{M}} w_{ij}^{km} \le 1 \qquad \forall (i, j) \in \mathcal{A}, \forall k \in \mathcal{K} \quad (12b) $$

$$ \sum_{m \in \mathcal{M}} w_{ij}^{km} \ge x_{ij}^k \qquad \forall (i, j) \in \mathcal{A}, \forall k \in \mathcal{K} \quad (12c) $$

$$ \sum_{j \in \delta^+(i)} w_{ij}^{km'} \le 1 - y_i^{km} \qquad \forall k \in \mathcal{K}, \forall i \in \mathcal{N} \setminus \{0\}, \forall m \in \mathcal{M}, \forall m' \prec m \quad (12d) $$

$$ \sum_{j \in \delta^+(i)} w_{ij}^{km'} \le 1 - \sum_{j \in \delta^-(i)} w_{ji}^{km} \qquad \forall k \in \mathcal{K}, \forall i \in \mathcal{N} \setminus \{0\}, \forall m \in \mathcal{M}, \forall m' \prec m, \quad (12e) $$

and constraints (1b)-(1i). The objective function is the minimization of the weighted traveling cost. Constraints (12b) ensure that at most one risk level is selected for each vehicle and each arc. Constraints (12c) force the selection of one risk level when a vehicle traverses an arc. Constraints (12d) state that if a vehicle collects commodity $m$ of customer $i$, then the risk level of the vehicle when leaving $i$ cannot be lower than the one of $m$. Constraints (12e) guarantee that the risk level in the vehicle is not decreasing during the trip of the vehicle. Indeed, if a vehicle reaches a node with the risk level associated with commodity $m$, the right-hand side of the corresponding constraint is zero, which imposes that variables $w$ associated with commodities with lower risk cannot take the value one, that is, the risk associated with the vehicle is non-decreasing on its route. Note that one interesting aspect of this problem is that the sequence in which the commodities are collected in the route impacts the risk associated with the route itself.

Another example of routing problems where commodities are associated with a non-additive characteristic concerns the milk collection as studied in Paredes-Belmar et al. (2016) and Paredes-Belmar et al. (2022). Commodities are milks of different quality produced by farmers. Vehicles can collect one or several types of milk during the route. When a vehicle arrives at the depot, it generates a
profit corresponding with the one associated with the lowest quality milk collected in the route. The
objective of the problem is to maximize the total profit of the milk collected minus the routing cost.

Finally, Paradiso et al. (2022) study a VRP where each commodity is associated with a temperature range. When a vehicle traverses an arc, its temperature must fall within the temperature ranges of all commodities currently loaded. To achieve this, each vehicle can adjust its temperature during the route, usually after delivery to a customer. The objective is to minimize the transportation cost and the cost of maintaining a specific temperature in the vehicles.

## 4.4 Research directions

An interesting research direction on Multi-Commodity VRPs with compatible commodities is the study of multi-commodity routing problems with profits. In Vehicle Routing Problems with Profits (VRPPs), a profit is associated with each customer, and a subset of customers to be served must be determined along with the routes (Archetti et al., 2014b). Problems in this class could be extended to consider multiple commodities by associating a profit with each commodity a customer requires. This class of problems would belong to the class of problems surveyed in Section 4.3.1. The literature on routing problems with profits is vast. However, no contribution has yet considered the extension to multiple commodities. An interesting application is related to the distribution of products to supermarkets. While suppliers need to deliver their products to supermarkets, supermarkets require different types of products. Therefore, a carrier might sign contracts for delivering the corresponding products only if the price offered is convenient. The problem would therefore be that of the carrier who has to select which commodities to pick up from which supplier and for which supermarket. This would turn out to be a routing problem with profits and multiple commodities.

Another interesting research direction is about theoretical/methodological contributions that link the multi-commodity VRPs with compatible commodities and the single commodity counterparts. An example of such an analysis is provided in Archetti et al. (2014a) for the C-SDVRP. The authors show that, in case the multi-commodity aspect of the problem is ignored, two situations may occur:

* an infeasible solution is obtained when the problem is solved as an SDVRP, i.e., the constraint related to the fact that commodities are indivisible is relaxed;

* a feasible suboptimal solution is produced when all commodities required by a customer are aggregated, and the problem is solved as a CVRP. Archetti et al. (2014a) show that in this case, the loss may increase by up to 100% with respect to the best solution associated with the multi-commodity problem.

A similar theoretical analysis could be performed for the other problems in this class. From a methodological perspective, it is clear that the multi-commodity aspect of the problems increases their complexity. Indeed, by simply considering problem formulations, introducing the index (dimension) associated with the commodities increases the size of the formulation. Thus, it would be interesting to study in which cases it is beneficial to solve the multi-commodity problem or, instead, to obtain a 'good' solution by solving the single commodity problem and then devising procedures to either restore feasibility or improve the solution.
# 5 Conclusions and directions for further research

In this paper, we reviewed the literature on VRPs with multiple commodities. We focused on the case where commodities have to be explicitly considered. The problems have been classified into two categories: the VRPs with compatible and incompatible commodities. For each problem, we analysed the reasons for explicitly considering multiple commodities and reviewed the main applications.

From this literature review, it can be concluded that multiple commodities have to be considered for the following main reasons:

* Commodities are incompatible, i.e., they cannot be mixed, but it is possible to transport them in the same vehicle. A solution is to use specific vehicles with multiple compartments such that a compartment contains a single commodity. Another solution is to perform multiple trips with the same vehicles. In this case, two incompatible commodities cannot be loaded on the same vehicle during the same trip, but they can be loaded on the same vehicle in different trips.

Solution methods that tackle these problems need to determine the assignment of commodities to compartments, the size of each compartment, or the scheduling of the trips assigned to the same vehicle.

* Commodities are compatible with each other, but have different characteristics that have to be taken into account when building the distribution plan, either for feasibility reasons or to optimize the plan. For example, in the traveling purchaser problem, commodities have different prices, volumes, and supply quantities; or in the inventory routing problem, they have different inventory costs and customer consumption rates.

Methods for solving these problems must not only determine minimum cost routes but also the quantity of each commodity to be collected at or delivered to each location.

There are many applications for the transportation of multiple commodities. The main ones are the following:

* Transportation of petroleum, fuel, gas. Commodities represent different products, e.g., different types of fuel or gas. Problems in which this application arises are the Multi-Compartment VRP and the Multi-Commodity IRP. In most cases, these commodities are incompatible and, thus, either the vehicles (or ships) are equipped with multiple compartments or the commodities are transported in different trips.

* Transportation of perishable food. Commodities represent different kinds of food. Problems related to this application are Multi-Compartment VRPs, since the different types of food cannot be mixed together, for example, because they have to be transported at different temperatures or due to regulations. Transporting perishable food in the same vehicle implies more frequent deliveries and reduces the storage levels at the customers. This is why this aspect is sometimes studied as a Multi-Commodity IRP.

* Transportation of waste and livestock is usually studied as a Multi-Compartment VRP since the different types of waste or livestock cannot be mixed in the same compartment.
* Transportation of different products in case of disaster or war. In these applications, the commodities are food, water, medicine, people.

* Transportation of different compatible products that have different origins and destinations, or different characteristics. Some examples deal with bikes (different configurations), money (bills and coins), wood (beam, plank, door and window frames).

* Transportation of hazardous materials. In this case, commodities are typically compatible but they have different characteristics and different origins/destinations.

Considering multiple commodities in VRPs increases the number of variables and constraints in the MILP formulations. Thus, the problems are more challenging to solve than the ones with a single commodity. Some solution methods apply decomposition: the routing problem is solved in a first phase, and then the commodities to transport on each route are decided in the second phase.

The main perspective for VRPs with multiple commodities, in addition to the ones mentioned in Section 3.3 and 4.4, is to develop efficient solution methods. One interesting aspect is to avoid replicating the customers when the delivery of an individual commodity cannot be split as it is currently done in many of the solution approaches proposed in the literature. This is especially important nowadays, given the explosion of fast delivery services related to online shopping. In fact, what happens here is that delivery companies have to serve many different customer orders associated with different types of goods (commodities). The possibilities for consolidation, for example by clustering the orders related to the same type of commodity, are narrow because customers require their goods to be delivered within a very short time (same day or the day after). Thus, the distribution plan has to be built by taking into account the different commodity features as well as origins and destinations. This clearly gives rise to challenging multi-commodity routing problems. Efficient and effective methods are needed as, given the increasing volume of e-shoppers, the problem dimension is typically very large. Much work is needed in this direction, and, given the growing practical and scientific interest in last-mile delivery problems for e-commerce, this represents a great opportunity to develop novel and practically relevant research.

# Acknowledgments

This work is partially supported by the Double First-class Talent Introduction Project of China under Grant No.505023160. The authors are grateful to the anonymous reviewers for their useful comments.

# References

Archetti, C., Bianchessi, N., and Speranza, M. G. (2015). A branch-price-and-cut algorithm for the commodity constrained split delivery vehicle routing problem. *Computers & Operations Research*, 64:1–10.

Archetti, C., Campbell, A. M., and Speranza, M. G. (2014a). Multicommodity vs. single-commodity routing. *Transportation Science*, 50(2):461–472.
Archetti, C. and Speranza, M. G. (2008). The split delivery vehicle routing problem: A survey. In Golden, B., Raghavan, S., and Wasil, E., editors, *The Vehicle Routing Problem: Latest Advances and New Challenges*, pages 103–122. Springer.

Archetti, C., Speranza, M. G., and Vigo, D. (2014b). Chapter 10: Vehicle routing problems with profits. In *Vehicle Routing: Problems, Methods, and Applications, Second Edition*, pages 273–297. SIAM.

Avella, P., Boccia, M., and Sforza, A. (2004). Solving a fuel delivery problem by heuristic and exact approaches. *European Journal of Operational Research*, 152(1):170–179.

Azizi, V. and Hu, G. (2020). Multi-product pickup and delivery supply chain design with location-routing and direct shipment. *International Journal of Production Economics*, page 107648. Publisher: Elsevier.

Battarra, M., Cordeau, J.-F., and Iori, M. (2014). Chapter 6: pickup-and-delivery problems for goods transportation. In *Vehicle Routing: Problems, Methods, and Applications, Second Edition*, pages 161–191. SIAM.

Battarra, M., Monaci, M., and Vigo, D. (2009). An adaptive guidance approach for the heuristic solution of a minimum multiple trip vehicle routing problem. *Computers & Operations Research*, 36(11):3041–3050.

Berbeglia, G., Cordeau, J.-F., Gribkovskaia, I., and Laporte, G. (2007). Static pickup and delivery problems: a classification scheme and survey. *TOP*, 15(1):1–31.

Bertazzi, L. and Speranza, M. G. (2013). Inventory routing problems with multiple customers. *EURO Journal on Transportation and Logistics*, 2(3):255–275.

Bianchessi, N., Irnich, S., and Tilk, C. (2021). A branch-price-and-cut algorithm for the capacitated multiple vehicle traveling purchaser problem with unitary demand. *Discrete Applied Mathematics*, 288:152–170.

Bianco, L., Caramia, M., Giordani, S., and Piccialli, V. (2013). Operations research models for global route planning in hazardous material transportation. In *Handbook of OR/MS Models in Hazardous Materials Transportation*, pages 49–101. Springer.

Braekers, K., Ramaekers, K., and Van Nieuwenhuyse, I. (2016). The vehicle routing problem: State of the art classification and review. *Computers & Industrial Engineering*, 99:300–313.

Brown, G. G. and Graves, G. W. (1981). Real-time dispatch of petroleum tank trucks. *Management Science*, 27(1):19–32.

Burks, R. E. (2006). *An adaptive tabu search heuristic for the location routing pickup and delivery problem with time windows with a theater distribution application*. PhD thesis, Graduate School of Engineering and Management, Air Force Institute of Technology, Ohio.

Caramia, M. and Guerriero, F. (2010). A milk collection problem with incompatibility constraints. *Interfaces*, 40(2):130–143.
Cattaruzza, D., Absi, N., and Feillet, D. (2016). Vehicle routing problems with multiple trips. *4OR*, 14(3):223-259.

Cattaruzza, D., Absi, N., Feillet, D., and Vigo, D. (2014). An iterated local search for the multi-commodity multi-trip vehicle routing problem with time windows. *Computers & Operations Research*, 51:257-267.

Ceselli, A., Righini, G., and Salani, M. (2009). A column generation algorithm for a rich vehicle-routing problem. *Transportation Science*, 43(1):56-69.

Chajakis, E. D. and Guignard, M. (2003). Scheduling deliveries in vehicles with multiple compartments. *Journal of Global Optimization*, 26(1):43-78.

Chen, J., Dan, B., and Shi, J. (2020). A variable neighborhood search approach for the multi-compartment vehicle routing problem with time windows considering carbon emission. *Journal of Cleaner Production*, 277:123932.

Chen, L., Liu, Y., and Langevin, A. (2019). A multi-compartment vehicle routing problem in cold-chain distribution. *Computers & Operations Research*, 111:58-66.

Choi, M. J. and Lee, S. H. (2011). The multiple traveling purchaser problem for maximizing system's reliability with budget constraints. *Expert Systems with Applications*, 38(8):9848-9853.

Christiansen, M., Fagerholt, K., Rachaniotis, N. P., Tveit, I., and Øverdal, M. V. (2015). A decision support model for routing and scheduling a fleet of fuel supply vessels. In Corman, F., Voß, S., and Negenborn, R. R., editors, *Computational Logistics*, pages 46-60, Cham. Springer International Publishing.

Coelho, L. C., Cordeau, J.-F., and Laporte, G. (2014). Thirty years of inventory routing. *Transportation Science*, 48(1):1-19.

Coelho, L. C. and Laporte, G. (2013). A branch-and-cut algorithm for the multi-product multi-vehicle inventory-routing problem. *International Journal of Production Research*, 51(23-24):7156-7169.

Coelho, L. C. and Laporte, G. (2015). Classification, models and exact algorithms for multi-compartment delivery problems. *European Journal of Operational Research*, 242(3):854-864.

Cordeau, J.-F., Laganà, D., Musmanno, R., and Vocaturo, F. (2015). A decomposition-based heuristic for the multiple-product inventory-routing problem. *Computers & Operations Research*, 55:153-166.

Cornillier, F., Boctor, F., and Renaud, J. (2012). Heuristics for the multi-depot petrol station replenishment problem with time windows. *European Journal of Operational Research*, 220(2):361-369.

Cornillier, F., Boctor, F. F., Laporte, G., and Renaud, J. (2008a). An exact algorithm for the petrol station replenishment problem. *Journal of the Operational Research Society*, 59(5):607-615.

Cornillier, F., Boctor, F. F., Laporte, G., and Renaud, J. (2008b). A heuristic for the multi-period petrol station replenishment problem. *European Journal of Operational Research*, 191(2):295-305.
Cornillier, F., Laporte, G., Boctor, F. F., and Renaud, J. (2009). The petrol station replenishment problem with time windows. *Computers & Operations Research*, 36(3):919–935.

Delgado-Antequera, L., Caballero, R., Sánchez-Oro, J., Colmenar, J. M., and Martí, R. (2020). Iterated greedy with variable neighborhood search for a multiobjective waste collection problem. *Expert Systems with Applications*, 145:113101.

Derigs, U., Gottlieb, J., Kalkoff, J., Piesche, M., Rothlauf, F., and Vogel, U. (2011). Vehicle routing with compartments: applications, modelling and heuristics. *OR spectrum*, 33(4):885–914.

Drexl, M. and Schneider, M. (2015). A survey of variants and extensions of the location-routing problem. *European Journal of Operational Research*, 241(2):283–308.

El Fallahi, A., Prins, C., and Calvo, R. W. (2008). A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem. *Computers & Operations Research*, 35(5):1725–1741.

Erdoğan, G., Cordeau, J.-F., and Laporte, G. (2010). A branch-and-cut algorithm for solving the non-preemptive capacitated swapping problem. *Discrete Applied Mathematics*, 158(15):1599–1614.

Erkut, E., Tjandra, S. A., and Verter, V. (2007). Chapter 9 Hazardous Materials Transportation. In Barnhart, C. and Laporte, G., editors, *Handbooks in Operations Research and Management Science*, volume 14 of *Transportation*, pages 539–621. Elsevier.

Eshtehadi, R., Demir, E., and Huang, Y. (2020). Solving the vehicle routing problem with multi-compartment vehicles for city logistics. *Computers & Operations Research*, 115:104859.

Farahani, R. Z., Lotfi, M. M., Baghaian, A., Ruiz, R., and Rezapour, S. (2020). Mass casualty management in disaster scene: A systematic review of OR&MS research in humanitarian operations. *European Journal of Operational Research*, 287(3):787–819.

Fernández, E., Roca-Riu, M., and Speranza, M. G. (2018). The shared customer collaboration vehicle routing problem. *European Journal of Operational Research*, 265(3):1078–1093.

Gendreau, M., Manerba, D., and Mansini, R. (2016). The multi-vehicle traveling purchaser problem with pairwise incompatibility constraints and unitary demands: A branch-and-price approach. *European Journal of Operational Research*, 248(1):59–71.

Ghiani, G., Mourão, C., Pinto, L., and Vigo, D. (2013). Chapter 15: Routing in Waste Collection Applications. In Corberán, Á. and Laporte, G., editors, *Arc Routing: Problems, Methods, and Applications*, pages 351–370. SIAM.

Ghorbani, A. and Jokar, M. R. A. (2016). A hybrid imperialist competitive-simulated annealing algorithm for a multisource multi-product location-routing-inventory problem. *Computers & Industrial Engineering*, 101:116–127.

Gianessi, P., Alfandari, L., Létocart, L., and Wolfler Calvo, R. (2015). The multicommodity-ring location routing problem. *Transportation Science*, 50(2):541–558.
Golden, B. L., Assad, A. A., and Wasil, E. A. (2002). Routing vehicles in the real world: applications in the solid waste, beverage, food, dairy, and newspaper industries. In Toth, P. and Vigo, D., editors, *The vehicle routing problem*, pages 245–286. SIAM.

Golden, B. L., Kovacs, A. A., and Wasil, E. A. (2014). Chapter 14: Vehicle Routing Applications in Disaster Relief. In Toth, P. and Vigo, D., editors, *Vehicle Routing: Problems, Methods, and Applications, Second Edition*, pages 409–436. SIAM.

Gribkovskaia, I., Gullberg, B. O., Hovden, K. J., and Wallace, S. W. (2006). Optimization model for a livestock collection problem. *International Journal of Physical Distribution & Logistics Management*, 36(2):136–152.

Gschwind, T., Bianchessi, N., and Irnich, S. (2019). Stabilized branch-price-and-cut for the commodity-constrained split delivery vehicle routing problem. *European Journal of Operational Research*, 278(1):91–104.

Gu, W., Archetti, C., Cattaruzza, D., Ogier, M., Semet, F., and Speranza, M. G. (2022). A sequential approach for a multi-commodity two-echelon distribution problem. *Computers & Industrial Engineering*, 163:107793.

Gu, W., Cattaruzza, D., Ogier, M., and Semet, F. (2019). Adaptive large neighborhood search for the commodity constrained split delivery VRP. *Computers & Operations Research*, 112:104761.

Henke, T., Speranza, M., and Wäsher, G. (2015). The multi-compartment vehicle routing problem with flexible compartment sizes. *European Journal of Operational Research*, 246(3):730–743.

Henke, T., Speranza, M. G., and Wäscher, G. (2019). A branch-and-cut algorithm for the multi-compartment vehicle routing problem with flexible compartment sizes. *Annals of Operations Research*, 275(2):321–338.

Hernández-Pérez, H., Rodríguez-Martín, I., and Salazar-González, J.-J. (2016). A hybrid heuristic approach for the multi-commodity pickup-and-delivery traveling salesman problem. *European Journal of Operational Research*, 251(1):44–52.

Hernández-Pérez, H. and Salazar-González, J.-J. (2004). A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery. *Discrete Applied Mathematics*, 145(1):126–139.

Hernández-Pérez, H. and Salazar-González, J.-J. (2007). The one-commodity pickup-and-delivery traveling salesman problem: Inequalities and algorithms. *Networks*, 50(4):258–272.

Hernández-Pérez, H. and Salazar-González, J.-J. (2009). The multi-commodity one-to-one pickup-and-delivery traveling salesman problem. *European Journal of Operational Research*, 196(3):987–995.

Hernández-Pérez, H. and Salazar-González, J.-J. (2014). The multi-commodity pickup-and-delivery traveling salesman problem. *Networks*, 63(1):46–59.

Heßler, K. (2021). Exact algorithms for the multi-compartment vehicle routing problem with flexible compartment sizes. *European Journal of Operational Research*, 294(1):188–205.
Holeczek, N. (2019). Hazardous materials truck transportation problems: A classification and state of the art literature review. *Transportation Research Part D*, 69:305–328.

Iakovou, E., Douligeris, C., Li, H., Ip, C., and Yudhbir, L. (1999). A maritime global route planning model for hazardous materials transportation. *Transportation Science*, 33(1):34–48.

Kallehauge, B., Larsen, J., Madsen, O., and Solomon, M. (2006). Vehicle routing problem with time windows. In Desaulniers, G., Desrosiers, J., and Solomon, M. M., editors, *Column Generation*, pages 67–98.

Khare, A., Batta, R., and Kang, J. E. (2021). On the analysis of last-mile relief delivery on a tree network: Application to the 2015 Nepal earthquake. *Journal of the Operational Research Society*, 72(4):727–743.

Koç, c., Laporte, G., and Tükenmez, I. (2020). A Review on Vehicle Routing with Simultaneous Pickup and Delivery. *Computers & Operations Research*, 122:104987.

Lahyani, R., Coelho, L. C., Khemakhem, M., Laporte, G., and Semet, F. (2015). A multi-compartment vehicle routing problem arising in the collection of olive oil in Tunisia. *Omega*, 51:1–10.

Laporte, G. (2009). Fifty years of vehicle routing. *Transportation Science*, 43(4):408–416.

Li, C., Gong, L., Luo, Z., and Lim, A. (2019). A branch-and-price-and-cut algorithm for a pickup and delivery problem in retailing. *Omega*, 89:71–91.

Lu, Y., Benlic, U., and Wu, Q. (2019). A population algorithm based on randomized tabu thresholding for the multi-commodity pickup-and-delivery traveling salesman problem. *Computers & Operations Research*, 101:285–297.

Manerba, D., Mansini, R., and Riera-Ledesma, J. (2017). The traveling purchaser problem and its variants. *European Journal of Operational Research*, 259(1):1–18.

Mara, S. T. W., Kuo, R., and Asih, A. M. S. (2021). Location-routing problem: a classification of recent research. *International Transactions in Operational Research*, 28(6):2941–2983.

Miranda-De La Lama, G. C., Villarroel, M., and María, G. A. (2014). Livestock transport from the perspective of the pre-slaughter logistic chain: A review. *Meat Science*, 98(1):9–20.

Mirzaei, S. and Wøhlk, S. (2019). A branch-and-price algorithm for two multi-compartment vehicle routing problems. *EURO Journal on Transportation and Logistics*, 8(1):1–33.

Mirzapour Al-e hashem, S. M. J. and Rekik, Y. (2014). Multi-product multi-period inventory routing problem with a transshipment option: A green approach. *International Journal of Production Economics*, 157:80–88.

Mjirda, A., Jarboui, B., Macedo, R., Hanafi, S., and Mladenović, N. (2014). A two phase variable neighborhood search for the multi-product inventory routing problem. *Computers & Operations Research*, 52:291–299.
Moin, N. H., Salhi, S., and Aziz, N. A. B. (2011). An efficient hybrid genetic algorithm for the multi-product multi-period inventory routing problem. *International Journal of Production Economics*, 133(1):334–343.

Moon, I., Salhi, S., and Feng, X. (2020). The location-routing problem with multi-compartment and multi-trip: formulation and heuristic approaches. *Transportmetrica A: Transport Science*, 16(3):501–528.

Muyldermans, L. and Pang, G. (2010). On the benefits of co-collection: Experiments with a multi-compartment vehicle routing algorithm. *European Journal of Operational Research*, 206(1):93–103.

Nagy, G. and Salhi, S. (1998). The many-to-many location-routing problem. *TOP*, 6(2):261–275.

Nakao, Y. and Nagamochi, H. (2007). A dp-based heuristic algorithm for the discrete split delivery vehicle routing problem. *Journal of Advanced Mechanical Design, Systems, and Manufacturing*, 1(2):217–226.

Nambirajan, R., Mendoza, A., Pazhani, S., Narendran, T. T., and Ganesh, K. (2016). CARE: Heuristics for two-stage multi-product inventory routing problems with replenishments. *Computers & Industrial Engineering*, 97:41–57.

Neves-Moreira, F., Almada-Lobo, B., Guimarães, L., and Amorim, P. (2022). The multi-product inventory-routing problem with pickups and deliveries: Mitigating fluctuating demand via rolling horizon heuristics. *Transportation Research Part E: Logistics and Transportation Review*, 164:102791.

Ohmori, S. and Yoshimoto, K. (2021). Multi-product multi-vehicle inventory routing problem with vehicle compatibility and site dependency: A case study in the restaurant chain industry. *Uncertain Supply Chain Management*, 9(2):351–362.

Oppen, J. and Løkketangen, A. (2008). A tabu search approach for the livestock collection problem. *Computers & Operations Research*, 35(10):3213–3229.

Oppen, J., Løkketangen, A., and Desrosiers, J. (2010). Solving a rich vehicle routing and inventory problem using column generation. *Computers & Operations Research*, 37(7):1308–1317.

Ostermeier, M., Henke, T., Hübner, A., and Wäscher, G. (2021). Multi-compartment vehicle routing problems: State-of-the-art, modeling framework and future directions. *European Journal of Operational Research*, 292(3):799–817.

Ostermeier, M. and Hübner, A. (2018). Vehicle selection for a multi-compartment vehicle routing problem. *European Journal of Operational Research*, 269(2):682–694.

Paradiso, R., Dabia, S., Dullaert, W., and Gromicho, J. (2022). The commodity constrained split delivery vehicle routing problem with temperature requirements. In *VeRoLog 2022 - 8th meeting of the EURO Working Group on Vehicle Routing and Logistics optimization*, Hamburg, Germany.

Paredes-Belmar, G., Bronfman, A., Marianov, V., and Latorre-Núñez, G. (2017). Hazardous materials collection with multiple-product loading. *Journal of Cleaner Production*, 141:909–919.
Paredes-Belmar, G., Marianov, V., Bronfman, A., Obreque, C., and Lüer-Villagra, A. (2016). A milk collection problem with blending. *Transportation Research Part E*, 94:26–43.

Paredes-Belmar, G., Montero, E., Lüer-Villagra, A., Marianov, V., and Araya-Sassi, C. (2022). Vehicle routing for milk collection with gradual blending: A case arising in chile. *European Journal of Operational Research*, 303(3):1403–1416.

Parragh, S. N., Doerner, K. F., and Hartl, R. F. (2008). A survey on pickup and delivery problems. *Journal für Betriebswirtschaft*, 58(2):81–117.

Polat, O. and Topaloğlu, D. (2022). Collection of different types of milk with multi-tank tankers under uncertainty: a real case study. *TOP*, 30(1):1–33.

Popović, D., Vidović, M., and Radivojević, G. (2012). Variable neighborhood search heuristic for the inventory routing problem in fuel delivery. *Expert Systems with Applications*, 39(18):13390–13398.

Prodhon, C. and Prins, C. (2014). A survey of recent research on location-routing problems. *European Journal of Operational Research*, 238(1):1–17.

Rahmani, Y., Ramdane Cherif-Khettaf, W., and Oulamara, A. (2016). The two-echelon multi-products location-routing problem with pickup and delivery: formulation and heuristic approaches. *International Journal of Production Research*, 54(4):999–1019.

Ramkumar, N., Subramanian, P., Narendran, T. T., and Ganesh, K. (2012). Mixed integer linear programming model for multi-commodity multi-depot inventory routing problem. *OPSEARCH*, 49(4):413–429.

Raviv, T., Tzur, M., and Forma, I. A. (2013). Static repositioning in a bike-sharing system: models and solution approaches. *EURO Journal on Transportation and Logistics*, 2(3):187–229.

Rieck, J., Ehrenberg, C., and Zimmermann, J. (2014). Many-to-many location-routing with inter-hub transport and multi-commodity pickup-and-delivery. *European Journal of Operational Research*, 236(3):863–878.

Riera-Ledesma, J. and Salazar-González, J.-J. (2012). Solving school bus routing using the multiple vehicle traveling purchaser problem: A branch-and-cut approach. *Computers & Operations Research*, 39(2):391–404.

Salani, M. and Vacca, I. (2011). Branch and price for the vehicle routing problem with discrete split deliveries and time windows. *European Journal of Operational Research*, 213(3):470–477.

Shaabani, H. and Kamalabadi, I. N. (2016). An efficient population-based simulated annealing algorithm for the multi-product multi-retailer perishable inventory routing problem. *Computers & Industrial Engineering*, 99:189–201.

Shang, X., Zhang, G., Jia, B., and Almanaseer, M. (2022). The healthcare supply location-inventory-routing problem: A robust approach. *Transportation Research Part E*, 158:102588.
Sun, L., Zhang, Y., and Hu, X. (2021). Economical-traveling-distance-based fleet composition with fuel costs: An application in petrol distribution. *Transportation Research Part E*, 147:102223.

Toth, P. and Vigo, D. (2014). *Vehicle routing: problems, methods, and applications*. SIAM.

Vidović, M., Popović, D., and Ratković, B. (2014). Mixed integer and heuristics model for the inventory routing problem in fuel delivery. *International Journal of Production Economics*, 147:593–604.

Wang, L., Kinable, J., and Van Woensel, T. (2020). The fuel replenishment problem: A split-delivery multi-compartment vehicle routing problem with multiple trips. *Computers & Operations Research*, 118:104904. Publisher: Elsevier.

Wang, X., Liang, Y., Tang, X., and Jiang, X. (2023). A multi-compartment electric vehicle routing problem with time windows and temperature and humidity settings for perishable product delivery. *Expert Systems with Applications*, 233:120974.

Zhang, D., Xu, W., Ji, B., Li, S., and Liu, Y. (2020). An adaptive tabu search algorithm embedded with iterated local search and route elimination for the bike repositioning and recycling problem. *Computers & Operations Research*, 123:105035.

Zhang, Z., Cheang, B., Li, C., and Lim, A. (2019). Multi-commodity demand fulfillment via simultaneous pickup and delivery for a fast fashion retailer. *Computers & Operations Research*, 103:81–96.