A branch-price-and-cut algorithm for a Multi-Commodity
two-echelon Distribution Problemaba

M. Petris , C. Archetti , D. Cattaruzza , M. Ogiera and F. Semeta,∗a Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9189 CRIStAL, F-59000 Lille, France
matteo.petris@inria.fr, diego.cattaruzza@centralelille.fr, maxime.ogier@centralelille.fr,frederic.semet@centralelille.fr

b ESSEC Business School in Paris, 95021, Cergy-Pontoise Cedex, Francearchetti@essec.fr∗ Corresponding author

Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

April 13, 2022

Keywords: multicommodity, routing problem, supply chain, cuts, branch-and-price.

1Introduction

In this presentation, we consider a Multi-Commodity two-echelon Distribution Problem (MC2DP)
which aims to design a two-echelon distribution system composed of a set of suppliersS, aset of distribution centers D and a set of customers C . Collection operations are performed atsuppliers, while delivery operations are performed at customers. More precisely, |K| commodities
are collected from the suppliers, sent to the distribution centers for consolidation purposes (rstechelon), and delivered to the customers to fulll their requests (second echelon).

For eachcommodity k ∈ K, each supplier i ∈ S provides an amount Pik≥ 0 of k , and each customerj ∈ C has a request Rjk ≥ 0 for k . An unlimited eet of homogeneous vehicles of capacity Q1 isavailable for the collection operations. Suppliers are linked to the distribution centers by direct

2trips. Each distribution center owns an unlimited eet of homogeneous vehicles of capacity Q
performing routes to deliver the commodities to the customers.

All vehicles can transport any set of commodities as long as their capacity is not exceeded. Inaddition, as in the Commodity constrained Split Delivery Vehicle Routing Problem (C-SDVRP)(see Archetti et al.

(2016)), customers can be visited multiple times.

for a given commodity has to be delivered in a single visit.

However, the request

The MC2DP aims to fulll thecustomer requests not exceeding the vehicle capacities and the available commodity amounts atthe suppliers and such that the overall transportation cost is minimized.
The classical 2E-CVRP considers theone-to-many case, where a single commodity has to bedelivered from a depot to a set of customers through distribution centers by means of two levelsof routing decisions. Only a few papers (Dellaert et al. (2021)) address a many-to-many setting.
The connection of the routes then considers the movement of commodities from the rst echelon
to the second echelon. The commodities are non-substitutable. Each commodity has an origin
in the rst echelon and a destination in the second. The MC2DP diers by considering multiple
substitutable commodities in amany-to-many setting. Indeed, commodities available in limited
quantities have to be collected from multiple suppliers and delivered to customers according totheir requests, but there is no assignment between suppliers and customers.

TRISTAN XI Symposium

Original abstract submittal

M. Petris, C. Archetti, D. Cattaruzza, M. Ogier and F. Semet

2In addition, in the 2E-CVRP, the link between the collection and delivery echelons is commonly done by the load synchronization strategy (Drexl (2012)). The amount of commodity sent
to each distribution center must be sucient to serve the customers assigned to that distribution
center. In the MC2DP, the same synchronization strategy is applied, but it is associated witheach commodity.
The study of the MC2DP was motivated by a case study presented in Gu et al.

(2021) forthe collection and delivery of fresh agri-food products (fruits and vegetables) through a shortand local supply chain.

More precisely, farmers deliver their products to distribution centersmanaged by professional associations. From them, the products are delivered to supermarkets
and canteens. In Gu et al. (2021), the authors proposed a heuristic sequential approach (collection rst, delivery second). Here, we propose an exact algorithm based on a branch-price-and-cut(BPC) framework.

2Problem formulation

We dene the MC2DP on a directed weighted graph G= (V, A), where V = S ∪ D ∪ C andA = (S × D) ∪ (D × S) ∪ (D × C) ∪ (C × D). A1 denotes the subset of arcs : D × S . Each arc(i, j) ∈ A is associated with cost Cij ≥ 0. For each distribution center o ∈ D, Ro is the set ofthe feasible routes that a vehicle owned by o can perform, i.e., non-empty cycles in the delivery
echelon starting and ending at o such that the total amount of delivered commodities does not
2r
exceed vehicle capacity Q . Finally, Cr is the cost associated with route r and ajk is a binaryparameter taking value 1 if r delivers commodity k to customer j and 0 otherwise.
We introduce the following variables. For all distribution centers o ∈ D and suppliers i ∈ S ,1integer variable xoi represents the number of vehicles traversing arc (o, i) ∈ A . For all o ∈ D ,k are associated with the amount ofi ∈ S and k ∈ K, non-negative continuous variable qoi
commodity k loaded at supplier i and sent to distribution center o. Finally, for all o ∈ D andr ∈ Ro , binary variable λr takes value 1 if route r is selected in the solution and 0 otherwise.
Our extended formulation, referred to as Master Problem (MP), is as follows:

Xmin(Coi + Cio )xoi +(o,i)∈A1

X X

Cr λ r(1)o∈D r∈Rosubject to:

Xkqoi≤ Pik∀i ∈ S, ∀k ∈ K(2)o∈DXkqoi≤ Q1 xoi∀o ∈ D, ∀i ∈ S(3)k∈KX X

arjk λr ≥ 1 ∀j ∈ C, ∀k ∈ K s.t.Rjk > 0(4)o∈D r∈RoXi∈Sxoi ∈ N ∀(o, i) ∈ A1 ,kqio≥X X

Rjk arjk λr∀o ∈ D, ∀k ∈ K(5)r∈Ro j∈Ckqoi∈ R+ ∀(o, i) ∈ A1 ∀k ∈ K, λr ∈ {0, 1}∀r ∈ Ro , ∀o ∈ D.

The objective function minimizes the total transportation cost.

(6)

Constraints 2 and 3 are

related to the collection echelon. Constraints 2 guarantee that the quantity of each commodity picked-up at each supplier does not exceed the maximum quantity available. Constraints 3link the quantities collected at suppliers to the number of vehicles needed to transport them.
Constraints 4 are the covering constraints ensuring that customer requests are fullled.

Con-straints 5 impose the load synchronization strategy linking the collection and delivery echelons
at the distribution centers. Constraints 6 dene the domains of the decision variables.

TRISTAN XI Symposium

Original abstract submittal

M. Petris, C. Archetti, D. Cattaruzza, M. Ogier and F. Semet

3Table 1  Preliminary computational results.

|S|

4444444444443

Instance
|C|
2 10
2 10
2 10
2 15
2 15
2 15
2 20
2 20
2 20
2 25
2 25
2 25

|D|

|K|

222
222222222UB
579.52562.34663.52771.34790.28896.121063.711108.311243.961188.391416.33
1526.09

Cplex
LB t(s)/gap(%)
549.03
5.55%
1441s
2261s
654.28 17.89%
682.49 15.79%
742.96 20.62%807.35 31.75%
851.34 30.18%
867.64 43.37%
904.92 31.32%
915.13 54.77%
952.69 60.19%

BPCUB
LB t(s)/gap(%)
579.520.39s
562.340.53s
663.520.32s
742.710.96s
784.05127.33s893.080.52s
1007.048.82s
1065.98 1077.43
1.07%
1177.460.55s
1184.6270.71s1258.9170.08s1367.61
11.34s

A branch-price-and-cut algorithm

To solve the MP introduced in Section 2, we design a BPC algorithm, where, at each column
generation iteration, we price λr variables. Specically, we solve the pricing problem min{C̄r |r ∈ Ro , o ∈ D}, where C̄r is the reduced cost of λr , by decomposing it per distribution center.
Solving min{C̄r | r ∈ Ro , o ∈ D} reduces to solve an Elementary Shorthest Path Problems withResource Constraints (ESPPRC) (see Gschwind et al. (2019)). We tackle the ESPPRC througha label setting dynamic programming algorithm which incorporates the ng-path relaxation and
an implicit version of the bidirectional labeling search. Our BPC implements several classicaland advanced techniques (Pessoa et al.

(2020)) to accelerate the column generation procedure:

the automatic dual pricing smoothing stabilization, a multi-phase strong branching procedure,
and three heuristic approaches to solve the ESPPRC. Two of these are similar to the graphreduction heuristics proposed in Gschwind et al.

(2019).

The third one is a novel two-phaseheuristic. The rst phase computes a lower bound on the value of min{C̄r | r ∈ Ro , o ∈ D} anda set of promising customer sequences: it does so by solving the ESPPRC on a modied graph,
where customers are delivered with their least requested commodity. The second phase retrievesthe route to be inserted in the MP by solving the ESPPRC again on several acyclic graphs,
one for each customer sequence computed in the previous phase. Finally, we look for violated
valid inequalities before starting the branching phase. We consider the capacity constraints andtwo new families of valid inequalities based respectively on the set covering polytope and on thenumber partitioning problem polytope. Last, we implement a sophisticated branching strategy,
considering rst the variables associated with the collection level and then those associated withthe arcs involved in the pricing problem. To ensure the correctness of the algorithm, we need toimplement the Foster and Ryan rule (see Foster & Ryan (1976)).

4

Preliminary computational results

Table 1 shows preliminary results obtained by running our BPC algorithm on 12 small instancesconsidered in Gu et al.

(2021).

We compare our results with those obtained by solving thecompact formulation of the MC2DP presented in Gu et al.

(2021) with the commercial solver

Cplex 12.8. For both approaches, we report the upper and lower bounds returned after a time
limit of one hour for Cplex and of 600 seconds for our approach. We indicate the computationaltime, if the instance is solved to optimality (-in column LB), or the optimality gap computes
asU B−LB· 100. The BPC algorithm outperforms Cplex in terms of time and solution quality:
LB

it optimally solves all but one instances in short computation times.
As future research direction, we plan to generalize the MC2DP by considering route decisions
also in the collection echelon and, hence, to adapt our BPC algorithm accordingly.

TRISTAN XI Symposium

Original abstract submittalM. Petris, C. Archetti, D. Cattaruzza, M. Ogier and F. Semet

4References
Archetti, Claudia, Campbell, Ann M., & Speranza, M. Grazia. 2016. Multicommodity vs. SingleCommodity Routing. Transportation Science, 50(2), 461472.
Dellaert, Nico, Van Woensel, Tom, Crainic, Teodor Gabriel, & Dashty Saridarq, Fardin. 2021. A multicommodity two-Echelon capacitated vehicle routing problem with time windows: Model formulations
and solution approach. Computers & Operations Research, 127, 105154.
Drexl, Michael. 2012. Synchronization in Vehicle RoutingA Survey of VRPs with Multiple Synchronization Constraints. Transportation Science, 46(3), 297316.
Foster, Brian A, & Ryan, David M. 1976. An Integer Programming Approach to the Vehicle Scheduling
Problem. Journal of the Operational Research Society, 27(2), 367384.
Gschwind, Timo, Bianchessi, Nicola, & Irnich, Stefan. 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, Wenjuan, Archetti, Claudia, Cattaruzza, Diego, Ogier, Maxime, Semet, Frédéric, & Speranza,
M. Grazia. 2021. A Sequential Approach for a Multi-Commodity Two-Echelon Distribution Problem. Computers & Industrial Engineering, nov, 107793.
Pessoa, Artur, Sadykov, Ruslan, Uchoa, Eduardo, & Vanderbeck, François. 2020. A Generic Exact Solverfor Vehicle Routing and Related Problems. Mathematical Programming, 183(1-2), 483523.

TRISTAN XI Symposium

Original abstract submittal