Wenjuan Gu
email: wenjuan.gu@bupt.edu.cn

Claudia Archetti
email: archetti@essec.edu

Diego Cattaruzza
email: diego.cattaruzza@centralelille.fr

Maxime Ogier
email: maxime.ogier@centralelille.fr

Frédéric Semet
email: frederic.semet@centralelille.fr

M Grazia Speranza

A sequential approach for a multi-commodity two-echelon distribution problem

Keywords: multicommodity, routing problem, local fresh food supply chain, sequential solution. 1

We address a Multi-Commodity two-echelon Distribution Problem (MC2DP) where three sets of stakeholders are involved: suppliers, distribution centers, and customers. Multiple commodities have to be sent from suppliers to customers, using multiple distribution centers for consolidation purposes. Commodities are collected from the suppliers and delivered to the distribution centers with direct trips, while a fleet of homogeneous vehicles distributes commodities to customers. Commodities are compatible, that is any vehicle can transport any set of commodities as long as its capacity is not exceeded. The goal is to minimize the total transportation cost from suppliers to customers. We present two sequential schemes based on the solution, in a different order, of a collection and a delivery subproblem. In both cases, the solution of the first subproblem determines the quantity of each commodity at each distribution center. The second subproblem takes this information as input. We also propose different strategies to guide the solution of the first subproblem in order to take into account the impact of its solution on the second subproblem. The proposed sequential heuristics are evaluated and compared both on randomly generated instances and on a case study related to a short and local fresh food supply chain. The results show the impact of problem characteristics on solution strategies.

Introduction

In this paper we study a complex distribution problem in a two-echelon supply chain where three sets of stakeholders are involved: suppliers, distribution centers and customers. Multiple commodities are collected from the suppliers and delivered to the customers through distribution centers for consolidation purposes. Each supplier has a given available quantity for each commodity and each customer has a demand for each commodity.

We consider a single decision maker who manages all distribution centers and organizes the collection and delivery operations. The commodities are collected from suppliers and delivered to distribution centers through direct trips, and distributed from the distribution centers to customers with a fleet of vehicles performing routes. Direct deliveries from suppliers to customers are not allowed. Commodities are compatible, that is, any vehicle can transport any set of commodities as long as its capacity is not exceeded. Multiple visits to a customer are allowed to reduce transportation costs. However, for the sake of customers convenience, a single commodity has to be delivered at once. The problem is named Multi-Commodity two-echelon Distribution Problem (MC2DP). The objective is to find a collection and delivery plan that minimizes the total transportation cost, satisfying customer demands, and not exceeding the available quantities at the suppliers and the vehicle capacities. The MC2DP is a problem belonging to the operational decision level. The plan covers one day only, i.e., collection and delivery operations performed during a day. The study of this problem is motivated by a case study presented in Section 6 for the collection and delivery of fresh agri-food products (fruits and vegetables) through a short and local supply chain.

In the following, we detail the application on short and local fresh food supply chain to motivate our work. The production and delivery of fresh food products have undergone important changes in Europe since the 1950's, especially through the modernization of the tools and processes in order to meet the customer demand with low production costs. Multinational companies have played a major role as intermediaries between farmers and consumers [START_REF] Rucabado-Palomar | Short food supply chains for local food: a difficult path[END_REF]. Nowadays, one of the major problems faced by farmers is the shortfall of their incomes: over the last decades they have been encouraged to produce more, while their unit selling price was decreasing. However, in many regions there coexist (1) supplies with medium-sized farms where various products of high quality (freshness, few pesticide) are cultivated and (2) customers with a strong desire for product quality and traceability [START_REF] King | Growing Local: Case Studies on Local Food Supply Chains[END_REF]. Hence, the idea has emerged to locally connect suppliers and customers [START_REF] Berti | Competitiveness of small farms and innovative food supply chains: The role of food hubs in creating sustainable regional and local food systems[END_REF], by means of a short (and/or) local food supply chain. The main purpose of this kind of supply chain is to capture more end-use value for the farmers.

Short food supply chains are defined as an opportunity for agricultural products to reach the market either through direct sales or through indirect sales with only one intermediary between producers and consumers. Local food supply chains may involve several intermediaries with all the actors located on a limited area (e.g. considering geographical or political restrictions). The maximum distance between actors is usually around 80 km [START_REF] Blanquart | The logistic leverages of short food supply chains performance in terms of sustainability[END_REF]. In this paper, we consider short and local food supply chains with indirect sales to canteens, restaurants or supermarkets.

Short and local supply chains involve few intermediaries. Hence, farmers have to take charge of a large part of their products marketing and distribution, which is not their core business. It is feasible for direct sales since the volumes are usually low, and consequently farmers can spend time selling their products. For indirect sales (canteen, restaurants or supermarket), volumes are more important and, therefore, the supply chain has to rely on a set of distribution centers in order to organize product flows and to minimize transportation costs, with the aim to be competitive with conventional food supply chains. Farmers supply these distribution centers by performing direct trips since the volumes are large. The distribution centers are then in charge of consolidation and delivery of the products to customers. In a local supply chain context, all the actors (farmers, distribution centers and customers) are located in a restricted area. A single decision maker manages all the distribution centers, and coordinates the transportation planning for both collection and delivery operations. This decision maker can be an association of farmers, or a local political authority. These distribution centers are considered as the only intermediary in the supply chain.

The Multi-Commodity two-echelon Distribution Problem belongs to the broad class of two-echelon routing problems, which are distribution problems where transportation activities take place in two echelons of a supply chain. There exists a wide literature on this class of problems. We refer to [START_REF] Cuda | A survey on two-echelon routing problems[END_REF] for a recent survey on two-echelon routing problems and to [START_REF] Guastaroba | Intermediate facilities in freight transportation planning: a survey[END_REF] for a more general survey on transportation problems with intermediate facilities. As mentioned in [START_REF] Cuda | A survey on two-echelon routing problems[END_REF], there are different classes of two-echelon routing problems. The closest to the MC2DP is the 2-Echelon Vehicle Routing Problem (2E-VRP) for which a wide literature exists, as surveyed in [START_REF] Cuda | A survey on two-echelon routing problems[END_REF]. We refer to [START_REF] Guimarães | The two-echelon multi-depot inventory-routing problem[END_REF], [START_REF] Zhou | A multi-depot two-echelon vehicle routing problem with delivery options arising in the last mile distribution[END_REF] and [START_REF] Yu | Two-echelon urban deliveries using autonomous vehicles[END_REF] for recent applications of the problem.

The problem we study here contributes to the literature on two-echelon routing problems by explicitly considering multiple commodities that are required by final customers. To the best of our knowledge, multiple commodities have never been considered in two-echelon distribution systems. The title of [START_REF] Dellaert | A multi-commodity twoechelon capacitated vehicle routing problem with time windows: Model formulations and solution approach[END_REF] could make the reader think the opposite. However, in [START_REF] Dellaert | A multi-commodity twoechelon capacitated vehicle routing problem with time windows: Model formulations and solution approach[END_REF] the authors studied a one-to-one pickup and delivery problem in a two-echelon distribution system. In other words, a commodity corresponds to an origin-destination pair. In our paper, instead, we have a many-to-many setting where each commodity can be picked up from any origin (supplier in our case) offering it and delivered to any destination (customer) requiring it. Multiple commodities have been explicitly modeled in two-echelon location problems (see, for example, [START_REF] Hinojosa | A multiperiod two-echelon multicommodity capacitated plant location problem[END_REF] and [START_REF] Sadjady | Two-echelon, multi-commodity supply chain network design with mode selection, lead-times and inventory costs[END_REF]). These problems do not involve routing decisions but evaluate the cost of assigning final customers to a specific distribution center.

The distribution centers considered in this work can be viewed as cross-docking stations. Using cross-dock platforms is a common practice for fresh products since it allows the transfer of incoming shipments directly to outgoing vehicles, without the need to store them in between [START_REF] Bruzzone | Fresh-food supply chain[END_REF]). Cross-dock platforms are also often used for the delivery from manufacturers in e-commerce, home delivery and urban logistics [START_REF] Qiu | The two-echelon production routing problem with cross-docking satellites[END_REF]. The direct consequence of this practice is to have shorter delivery times that help to preserve the freshness of the foods. It is also well-known that cross-docking or consolidation platforms increase the overall performance of a delivery system, independently of the products that go through the platform. They allow cost reduction of the overall logistics service [START_REF] Ladier | Cross-docking operations: Current research versus industry practice[END_REF]Alpan, 2016, Van Belle et al., 2012).

Contributions on the management of a cross-docking platform, motivated by the fresh food delivery, exist in the literature. These studies usually deal with the management and coordination of inbound and outbound vehicles and the consolidation of products in outbound vehicles. [START_REF] Agustina | Vehicle scheduling and routing at a cross docking center for food supply chains[END_REF] consider the problem of building the delivery plan to serve customers while minimizing inventory and routing costs plus earliness and tardiness delivery penalties. The authors propose a mixed integer linear program that is solved with Cplex. [START_REF] Rahbari | The vehicle routing and scheduling problem with cross-docking for perishable products under uncertainty: Two robust bi-objective models[END_REF] propose a bi-objective model that considers cost minimization as well as product freshness maximization. In both papers, customers' demands do not explicitly consider multiple commodities.

The presence of multiple commodities makes the MC2DP substantially different with respect to the standard 2E-VRP. In fact, the demand matching decision, i.e., the decision related to the assignment of suppliers and customers to distribution centers, is constrained not only by the matching of quantities, but also involves the matching of commodities. In addition, in the MC2DP, customers may be visited more than once, according to the number of commodities they request. An additional consideration is due to synchronization constraints that might be present in two-echelon distribution systems. The two echelons may be linked by different kinds of synchronization constraints (see [START_REF] Drexl | Synchronization in vehicle routing-a survey of vrps with multiple synchronization constraints[END_REF]). The most common one considered in the 2E-VRP is the load synchronization that establishes that the quantity delivered to each distribution center in the first echelon has to be sufficient to satisfy the demand of the customers assigned to the distribution center in the second echelon. Another common synchronization constraint is the operation synchronization, implying precedence constraints between the collection and the delivery operations. In the MC2DP, only load synchronization is considered, specified for each commodity. Operation synchronization is not considered. In other words, we assume that all collection operations are performed before the delivery operations (for example, collection in the morning and delivery in the afternoon).

The explicit consideration of different commodities is essential in the agri-food supply chains since availability at the producer depends on the production of farmers and requirements made by customers concern specific commodities.

There is a large literature on planning problems in agri-food supply chains. The main focus is, in general, evaluating the level of degradation and the quality of products in the planning models [START_REF] Yu | Analysis of cold-chain service outsourcing modes in a fresh agri-product supply chain[END_REF]. When focusing on short and local food supply chain, the literature is very scarce. As pointed out by [START_REF] Flores | A modeling framework for the strategic design of local freshfood systems[END_REF], there is a lack of supply chain planning tools for local fresh food supply chains. [START_REF] Flores | A modeling framework for the strategic design of local freshfood systems[END_REF] develop an agricultural planning framework that determines an optimal production planning of vegetables for local supply chains. [START_REF] Bosona | Cluster building and logistics network integration of local food supply chain[END_REF] address a case study in Sweden. They first study the location of distribution centers using the centre-of-gravity technique. Then, farmers are assigned to one distribution center, and can bring their products to the distribution center, or the latter can perform collection by grouping farmers into routes. Routes are then optimized using a dedicated software (Route LogiX). [START_REF] Ogier | Service network design in short and local fresh food supply chain[END_REF] propose a mixed integer linear programming model for service network design of a short and local supply chain.

Even though the application presented in this paper deals with the agri-food supply chain, the methods we propose can be applied to MC2DPs that consider direct delivery trips in the first echelon and allow splitting the delivery of different commodities in the second level.

In this paper, we present a solution approach to the MC2DP. Due to the complexity of the problem, we propose a sequential approach that first decomposes the MC2DP in two subproblems, associated with the collection and delivery phases, respectively, and then sequentially solves them. Two sequential schemes are presented, depending on which of the two subproblems is solved first. In both cases, the solution of the first subproblem determines the quantity of each commodity at each distribution center.

The second subproblem takes this information as input. We also propose different strategies to guide the solution of the first subproblem in order to take into account the impact of its solution on the second subproblem. It is worth noting that the subproblem associated with the delivery phase is itself a new problem. It is a Vehicle Routing Problem (VRP) with multiple commodities and multiple depots, with a maximum available quantity of each commodity at the depots. The VRP with multiple depots is a well-studied problem in the literature [START_REF] Montoya-Torres | A literature review on the vehicle routing problem with multiple depots[END_REF]. In this paper, the delivery subproblem is an extension of the VRP with multiple depots where several commodities are available at each depot with given quantities. A further contribution of this paper is a solution method for the delivery subproblem, based on the Adaptive Large Neighborhood Search (ALNS) algorithm proposed for the one depot case by [START_REF] Gu | Adaptive large neighborhood search for the commodity constrained split delivery VRP[END_REF]. The two proposed sequential heuristic schemes and the different strategies are evaluated and compared both on randomly generated instances, with different characteristics (supplier locations, customer locations, maximum supply quantities), and on a case study for the collection and delivery of fresh food products (fruits and vegetables) through a short and local supply chain using a set of distribution centers located in the French department of Isère. The size of the instances for this case study is large, and two kinds of customers are considered: school canteens and supermarkets. The computational results show the impact of the instance on the solution approaches and strategies.

The remainder of this paper is organized as follows. A definition of the MC2DP is given in Section 2, as well as the problem formulation. A decomposition of the problem into a collection and a delivery subproblems is presented in Section 3. Then, the sequential approach is described in Section 4. Section 5 provides the computational results. The case study on short and local fresh food supply chains in the French department of Isère is discussed in Section 6. Finally, conclusions and prospects are presented in Section 7.

Problem definition and formulation

The Multi-Commodity two-echelon Distribution Problem (MC2DP) is defined on a directed graph G = (V, A), in which V is the set of vertices and A is the set of arcs. More precisely, V is defined as

V S V D V C where V S = {1, . . . N S } represents the set of N S suppliers, V D = {N S + 1, . . . , N S + N D } is the set of N D distribution centers and V C = {N S + N D + 1, . . . , N S + N D + N C } represents the set of N C customers.
We only consider direct trips from suppliers to distribution centers. Direct deliveries from suppliers to customers are not allowed. Moreover, transfers of commodities between distribution centers are not considered. Thus,

A = {(i, j), (j, i)|i ∈ V S , j ∈ V D } ∪ {(i, j), (j, i)|i ∈ V D , j ∈ V C } ∪ {(i, j)|i, j ∈ V C } is the set of arcs.
Suppliers provide a set of commodities M, which are transported to the distribution centers by an unlimited fleet of homogeneous vehicles of capacity Q S . Each supplier s ∈ V S is associated with a maximum available quantity O sm ≥ 0 of commodity m ∈ M. Each distribution center has its own unlimited fleet of homogeneous vehicles of capacity Q D that are used to deliver the commodities to the customers. Customer i ∈ V C requires a quantity D im ≥ 0 of each commodity m ∈ M. For each customer i ∈ V C , M i = {m ∈ M|D im > 0} represents the set of commodities required by customer i. Commodities are compatible, i.e., they can be transported on the same vehicle. The demand of a customer can be split, that is the customer can be served by several vehicles. However, for the sake of customer convenience, the split policy is constrained: each commodity has to be delivered by one vehicle only. Without loss of generality, it is assumed that m∈M D im ≤ Q D for all customers i ∈ V C . Note that, in case there is a customer i such that m∈M D im > Q D , then we split the customer and create as many copies as the number of commodities requested by i.

A cost c ij is associated with each arc (i, j) ∈ A and represents the non-negative cost of traversing arc (i, j). In the MC2DP, the decision maker is the logistic provider who manages all the distribution centers. He decides how to collect commodities from the suppliers and how to distribute the commodities from the distribution centers to the customers. The objective is to find a collection and delivery plan that minimizes the total transportation cost, satisfying customer demands, not exceeding the available quantities at the suppliers and the vehicle capacities.

The MC2DP is NP-hard as it reduces to the Traveling Salesman Problem (TSP) in the case where |M| = |V D | = |V S | = 1 and vehicles have unlimited capacity.

In the following, we will call collection the transportation of commodities from suppliers to distribution centers and delivery the distribution of commodities from distribution centers to customers. Note that, in the following, we will use the word truck to indicate a vehicle used for collection operations, to differentiate it from a vehicle used for delivery operations. The collection and delivery phases of the MC2DP are connected through the quantities of commodities at the distribution centers. We denote by U dm the unknown quantity of commodity m ∈ M at distribution center d.

An example of an instance of the MC2DP is depicted in Figure 1. There are two commodities, the truck capacity is Q S = 8 and the vehicle capacity Q D = 10. A feasible solution of this instance is shown in Figure 2. In the solution, five trucks are used to supply the distribution centers, each truck performing a direct trip. The numbers on the arcs representing direct trips report the quantities transported for each commodity, where the number corresponding to the commodity is reported in parentheses. Note that two trucks are used from supplier 1 to distribution center 4. Quantities U dm are as follows: U 41 = 4, U 42 = 14, U 51 = 5 and U 52 = 3. For the distribution to customers, two vehicles leave distribution center 4, while one vehicle leaves distribution center 5. Note that customer 9 is visited twice: one vehicle delivers commodity 1 while another vehicle delivers commodity 2.

6 1 1 7 O  2 1 4 O  2 2 8 O  1 2 1 0O  3 2 1 0 O  6 1 2 D  6 2 1 D  7 1 2 D  7 2 3 D  8 2 8 D  9 1 3 D  9 2 2 D  10,2 1 D  11,1 2 D  11,2 2 D 
8 O  12 10 O  32 10 O  61 2 D  62 1 D  71 2 D  72 3 D  82 8 D  91 3 D  92 2 D  10,2 1 D  11,1 2 D  11,2 2 D  2 (1 )
8( 2)

2 (1 )+ 6 (2 ) 5 ( 1 ) 3 (2 )
Figure 2: A feasible solution of the MC2DP instance.

Problem formulation

We now propose a mathematical formulation of the problem. Let us indicate with F d the fleet associated with the delivery from distribution center d ∈ V D . Since this fleet in the MC2DP is supposed to be unlimited, we set |F d | = N C , ∀d ∈ V D . This is clearly an upper bound on the number of vehicles needed at each distribution center, since m∈M D im ≤ Q D for all i ∈ V C .

Let us number the vehicles such that

F 1 = {1, . . . , N C }, F 2 = {N C + 1, . . . , 2N C }, . . . , F N D = {N C (N D -1) + 1, . . . , N D N C }. Let F = ∪ N D d=1 F d .
Note that labelling the vehicles by increasing index allows us to drop the distribution center index in the variable definition.

Let us indicate with

A = A 1 ∪ A 2 , where A 1 = {(i, j)|i ∈ V S , j ∈ V D } and A 2 = {(i, j), (j, i)|i ∈ V D , j ∈ V C } ∪ {(i, j)|i, j ∈ V C }. Let us also define D - im = min m∈M i {D im } and d(f ) as the distribution center d ∈ V D associated with vehicle f ∈ F.
The following decision variables are introduced.

x 1 sd : non-negative integer variable equal to the number of trucks traversing arc (s,

d) ∈ A 1 , s ∈ V S , d ∈ V D .
x 2 ijf : binary variable equal to 1 if arc (i, j) ∈ A 2 is traversed by vehicle f ∈ F.

z if : binary variable equal to 1 if customer or distribution center i ∈ V C ∪ V D is visited by vehicle f ∈ F.
u if : non-negative real variable equal to the accumulated demand to be delivered by vehicle f ∈ F when arriving at customer i ∈ V C .

y m if : binary variable equal to 1 if commodity m ∈ M of customer i ∈ V C is delivered by vehicle f ∈ F.
q m sd : non-negative variable equal to the quantity of commodity m ∈ M picked up at supplier s ∈ V S and delivered to distribution center d ∈ V D .

In addition, we define as csd = c sd +c ds the direct trip cost between supplier s ∈ V S and distribution center d ∈ V D .

The compact formulation for the MC2DP, denoted as F M C2DP , is as follows:

(F M C2DP ) min (s,d)∈A 1 csd x 1 sd + (i,j)∈A 2 f ∈F c ij x 2 ijf (1) s.t. f ∈F d i∈V C y m if D im ≤ s∈V S q m sd , ∀d ∈ V D , ∀m ∈ M, (2)
m∈M q m sd ≤ Q S x 1 sd , ∀s ∈ V S , ∀d ∈ V D , (3)
d∈V D q m sd ≤ O sm , ∀s ∈ V S , ∀m ∈ M, (4)
f ∈F

y m if = 1, ∀i ∈ V C , ∀m ∈ M i , (5)
j|(i,j)∈A 2 x 2 ijf = j|(j,i)∈A 2 x 2 jif = z if , ∀i ∈ V C ∪ V D , ∀f ∈ F, (6)
f ∈F \F d z df = 0, ∀d ∈ V D , (7)
y m if ≤ z if , ∀i ∈ V C , ∀m ∈ M i , ∀f ∈ F, ( 8
) i∈V C m∈M i D im y m if ≤ Q D z d(f )f , ∀f ∈ F, (9)
u if -u jf + Q D x 2 ijf ≤ Q D -D - jm , ∀(i, j) ∈ A 2 , ∀f ∈ F, (10)
x 1 sd ∈ N, ∀(s, d) ∈ A 1 , (11)
x 2 ijf ∈ {0, 1}, ∀(i, j) ∈ A 2 , ∀f ∈ F, (12)
z if ∈ {0, 1}, ∀i ∈ V C ∪ V D , ∀f ∈ F, (13)
y m if ∈ {0, 1}, ∀i ∈ V C , f ∈ F, ∀m ∈ M, (14)
u if ≥ 0, ∀i ∈ V C , ∀f ∈ F, (15)
q m sd ≥ 0, ∀(s, d) ∈ A 1 , ∀m ∈ M. ( 16
)
The objective function (1) minimizes the total transportation costs. Constraints (2) impose that the quantity of each commodity delivered to a distribution center is sufficient to carry out delivery operations from there. Constraints (3) impose the use of a sufficient number of trucks for collection operations. Constraints (4) fix the maximum availability of each commodity at each supplier. Constraints (5) state that each required commodity is distributed exactly once to each customer. Constraints (6) are flow conservation constraints. Constraints (7) manage the assignment of vehicles to distribution centers. Constraints (8) impose to use a vehicle if this delivers at least one commodity of a customer. Constraints (9) are vehicle capacity constraints. Constraints (10) eliminate subtours that do not contain a distribution center. Constraints (11)-( 16) define the variables.

Problem decomposition

The MC2DP integrates two subproblems, one considering the collection of commodities, that is the transportation of the commodities from the suppliers to the distribution centers, the other considering the delivery of commodities from the distribution centers to the customers. In this section, we present a decomposition of the MC2DP and define the two subproblems: the SPC (SubProblem Collection) and the SPD (SubProblem Delivery). The connection of these two problems is made by quantities U dm that represent the available quantity of commodity m at distribution center d. For the sake of clarity, when necessary, we will denote by U D dm the quantity of commodity m that is delivered from the distribution center d to customers, and by U C dm the quantity of commodity m that is collected at the suppliers and delivered to the distribution center d. Figure 3 illustrates the solutions of the SPC and the SPD for the instance in Figure 2, with the associated U dm variables that link the two subproblems. We now provide a formal definition of the SPC and the SPD. Note that each subproblem is concerned with the optimization of the related operations, i.e., SPC minimizes the cost of collection operations only while SPD minimizes the cost of delivery operations only.

11 7 O  1 2 3 4 5 21 4 O  22 8 O  12 10 O  32 10 O  2( 1) 8(2) 2( 1) + 6( 2) 5 ( 1 ) 3( 2) 4 1 4 D U  4 2 1 4 D U  5 1 5 D U  5 2 3 D U  7 8 9 10 11 6 61 2 D  62 1 D  71 2 D  72 3 D  82 8 D  91 3 D  92 2 D  10,2 1 D  11,1 2 D  11,2 2 D  4 5 4 1 4 C U  4 2 1 4 C U  5 1 5 C U  52 3 C U  (

The collection subproblem (SPC)

The SPC is defined on a graph

G 1 = (V 1 , A 1 ), where V 1 = V S V D and A 1 = {(i, j), (j, i)|i ∈ V S , j ∈ V D }.
The SPC consists in determining a set of direct trips for trucks between suppliers and distribution centers with the associated quantities for each commodity. The objective is to minimize the transportation cost, defined as the total cost for the direct trips, that is independent of the quantity transported on each truck. For each commodity, the quantity transported to distribution centers has to be sufficient to satisfy customer demands in the SPD. Moreover, the solution of the SPC must satisfy the following constraints:

(1) the total quantity of commodities transported by each truck does not exceed the truck capacity Q S ;

(2) for each supplier s, the quantity of each commodity m that is transported to distribution centers must be at most equal to the available quantity O sm ;

(3) the quantity of each commodity m transported to each distribution center d is greater than the required quantity U D dm .

When the SPC is solved first, the values U D dm are not known and have to be set to a valid lower bound. Next, the values U C dm are computed from the solution of the SPC and used as input to the SPD.

The SPC is related to the Multi-commodity Capacitated fixed-charge Network Design problem (MCND) [START_REF] Magnanti | Network design and transportation planning: Models and algorithms[END_REF]. The MCND problem is a discrete optimization problem in which a set of commodities has to be routed through a directed network. Each commodity has a demand to be transported from an origin to a destination. Each arc has a limited capacity, a unit cost flow, and a fixed cost if the arc is used (the flow is positive). The SPC differs from the MCND problem because of the cost structure. In the SPC, the cost of an arc depends on the number of trucks used: it is a step-wise cost function defined by a unitary cost associated with each truck used. Thus, steps are defined as multiples of the truck capacity Q S .

The delivery subproblem (SPD)

The SPD is defined on a graph

G 2 = (V 2 , A 2 ) where V 2 = V D V C and A 2 = {(i, j), (j, i)|i ∈ V D , j ∈ V C } ∪ {(i, j)|i, j ∈ V C }.
In the following, we will use the word vehicle to indicate a vehicle used in the SPD.

The SPD consists in assigning commodities to vehicles and in determining a set of vehicle routes to meet all customer demands. The solution must satisfy the following constraints:

(1) the total quantity of commodities delivered by each vehicle does not exceed the vehicle capacity

Q D ;
(2) each commodity requested by each customer is delivered by a single vehicle;

(3) the demand of all customers is satisfied;

(4) the quantity of each commodity m distributed from each distribution center d does not exceed the available quantity U C dm ;

(5) each vehicle starts and ends its route at the same distribution center.

When the SPD is solved first, the values U C dm are not known and have to be set to a valid upper bound. Next, the values U D dm are computed from the solution of the SPD and used as input to the SPC.

The SPD is the multi-depot case of the Commodity constrained Split Delivery Vehicle Routing Problem (C-SDVRP) [START_REF] Archetti | Multicommodity vs. single-commodity routing[END_REF]. The C-SDVRP is a problem where customers require multiple commodities. Each customer can be served by different vehicles, but each commodity has to be delivered at once by a single vehicle. The C-SDVRP considers only one distribution center with sufficient quantity for each commodity to satisfy all the customer demands.

A sequential approach

In this section we describe the sequential solution approach for the MC2DP. We first describe a solution method for the SPC based on the solution of a mathematical programming model. Then, we propose a solution method for the SPD. It is an Adaptive Large Neighborhood Search (ALNS) algorithm that extends the approach described in [START_REF] Gu | Adaptive large neighborhood search for the commodity constrained split delivery VRP[END_REF]. As the solution of the first subproblem solved, whatever it is, has an impact on the solution of the second subproblem, we describe, in Section 4.3, different strategies for taking into account this impact when solving the first subproblem.

We will make use of the concept of customer-commodity. A customer-commodity represents the demand of a customer for a single commodity. A customer may be seen as a union of customercommodities.

Solution of the SPC

The SPC is modelled as a Mixed Integer linear Program (MIP). The formulation, that will be solved to optimality, is based on the following decision variables:

x sd : non-negative integer variable equal to the number of trucks traversing arc (s,

d) ∈ A 1 , s ∈ V S , d ∈ V D ;
q m sd : non-negative variable equal to the quantity of commodity m ∈ M picked up at supplier s ∈ V S and delivered to distribution center d ∈ V D ; and0 otherwise. Note that the variables x sd and q m sd have the same meaning as variables x 1 sd and q m sd , respectively, in the formulation F M C2DP . Variables y m di are introduced for the formulation of the SPC. The mathematical formulation that follows determines the quantities to transport from suppliers to distribution centers in such a way that all commodities requested by customers are shipped, and the availabilities at the suppliers and the truck capacity are not violated:

y m di : binary variable equal to 1 if the demand of commodity m ∈ M of customer i ∈ V C is assigned to distribution center d ∈ V D ,
min (s,d)∈A 1 csd x sd (17) s.t. d∈V D y m di = 1, ∀ i ∈ V C , m ∈ M i , ( 18
) i∈V C D im y m di ≤ s∈V S q m sd , ∀ d ∈ V D , m ∈ M, ( 19
) s∈V S q m sd ≥ U D dm , ∀ d ∈ V D , m ∈ M, ( 20
) m∈M q m sd ≤ Q S x sd , ∀ s ∈ V S , d ∈ V D , (21)
d∈V D q m sd ≤ O sm , ∀ s ∈ V S , m ∈ M, (22)
x sd ∈ N, ∀ s ∈ V S , d ∈ V D , (23)
y m di ∈ {0, 1}, ∀ i ∈ V C , d ∈ V D , m ∈ M, (24)
q m sd ≥ 0, ∀ s ∈ V S , d ∈ V D , m ∈ M. ( 25
)
The objective function ( 17) minimizes the transportation cost, that is the cost of the direct trips of the trucks used to supply the distribution centers. Constraints (18) impose that, for each customer, the demand of each commodity is assigned to one distribution center. Constraints (19) impose that the quantity of each commodity delivered to each distribution center satisfies the demand of the customers assigned to the same distribution center. Note that constraints ( 18) and ( 19) ensure that any solution of the SPC is feasible for the SPD. Constraints (20) ensure that the quantity transported to each distribution center is greater than the lower bound U D dm . Constraints (21) impose that the total volume of all commodities transported from a supplier to a distribution center cannot exceed the capacity of the trucks used on that arc. Constraints ( 22) impose not to exceed the available quantities of commodities at the suppliers. Constraints ( 23)-( 25) define the variables.

The above formulation may have several equivalent optimal solutions. To break ties among solutions with the same cost but delivering different quantities, we consider a small value ε and add to the objective function ( 17) the term:

ε d∈V D i∈V C m∈M i c di y m di , (26)
where c di is the travelling cost between distribution center d and customer i. With this term, solutions with different assignments of customer-commodities to distribution centers are evaluated differently. This term favours solutions that minimize the total distance between customer-commodities and the distribution center to which they are assigned.

We call F SP C the formulation ( 18)-( 25) with objective function:

min (s,d)∈A 1 csd x sd + ε d∈V D i∈V C m∈M i c di y m di . ( 27
)
An optimal solution to the formulation F SP C gives the available quantities U C dm of each commodity m at distribution center d as:

U C dm = s∈V S q m sd .
We will see in Section 4.3, how such quantities are used in the sequential approach for the solution of the MC2DP where the SPC is solved first. When the SPD is solved first, the assignment of customercommodities to distribution centers is known, that is the values of the y variables are known. In this case, constraints ( 18) and ( 19) are removed from F SP C , and only constraints (20) are used to link the two subproblems. It is noteworthy that when the SPC is solved first, the values U D dm are not set according to the solution of the SPD but according to the strategies defined in Section 4.3.2. Then, constraints ( 18) and ( 19) are necessary to ensure that the solution of the SPC is feasible for the SPD.

Solution of the SPD

The SPD deals with the delivery of commodities from distribution centers to customers. As already mentioned, when the SPD is solved after the SPC, the values U C dm are known. Instead, when the SPD is solved first, the values U C dm have to be set. Different strategies to determine these values are proposed in Section 4.3.2. In the remaining of this section we assume that these quantities U C dm are given, either from the solution of the SPC or from one of the strategies described in Section 4.3.1, when the SPD is solved firsst.

In the following, we describe the solution approach we propose for the SPD, which is an Adaptive Large Neighborhood Search (ALNS). Section 4.2.1 describes how we build an initial solution while the ALNS is described in Section 4.2.2.

Initial solution

To solve the SPD, we start by assigning customer-commodities to distribution centers. To this end, we solve a Generalized Assignment Problem (GAP) [START_REF] Ross | A branch and bound algorithm for the generalized assignment problem[END_REF], [START_REF] Cattrysse | A survey of algorithms for the generalized assignment problem[END_REF]) which aims at finding the minimum cost assignment of customer-commodities to distribution centers so that each customer-commodity is assigned to exactly one distribution center. The assignment is subject to the availability of each commodity at the distribution centers. The assignment cost of commodity m for customer i to distribution center d is c id that represents the traveling cost from customer i to distribution center d.

We now present the formulation of the GAP. Let x m id be the binary variables equal to 1 if and only if commodity m ∈ M required by customer i ∈ V C is served from distribution center d ∈ V D , and 0 otherwise. The GAP is formulated as follows:

min i∈V C m∈M i d∈V D c id x m id (28) s.t. i∈V C D im x m id ≤ U C dm , ∀ m ∈ M, d ∈ V D , ( 29
) d∈V D x m id = 1, ∀ i ∈ V C , m ∈ M i , (30)
x m id ∈ {0, 1}, ∀ i ∈ V C , m ∈ M, d ∈ V D . (31)
The objective function ( 28) minimizes the total assignment cost of customer-commodities to distribution centers. Constraints (29) impose not to exceed the quantity of commodity available at each distribution center. Constraints (30) ensure that each customer-commodity is assigned to exactly one distribution center. Constraints (31) define decision variables.

Given the assignment of customer-commodities to distribution centers provided by the solution of the GAP, the set of initial routes is obtained by applying the split algorithm to each distribution center. The split algorithm [START_REF] Beasley | Route first-cluster second methods for vehicle routing[END_REF], [START_REF] Prins | A simple and effective evolutionary algorithm for the vehicle routing problem[END_REF]) starts from a giant-tour that visits all the customers associated with a distribution center and decomposes the visiting sequence into a set of feasible routes. The solution obtained is the initial solution for the ALNS.

The Adaptive Large Neighborhood Search

The basic idea of an ALNS is to improve the current solution by destroying it and building a new one. The ALNS algorithm we present adopts the scheme proposed in [START_REF] Gu | Adaptive large neighborhood search for the commodity constrained split delivery VRP[END_REF] for the commodity constrained split delivery VRP with a single depot (distribution center). The presence, in the problem we solve, of multiple depots and different quantities of each commodity in each of them required substantial changes and the design of ad-hoc procedures. The basic scheme of the algorithm is given in Algorithm 1, where f (s) is the objective value of solution s.

Algorithm 1 The ALNS algorithm.

1: s ← initial solution 2: s best ← initial solution 3: repeat 4:
s ←Destroy and Repair(s)

5: s ←Local Search(s) 6: if f (s) < f (s best ) then 7: s ←Intensification(s) 8: s best ← s 9:
end if 10: until stopping criterion is met

In the following we present the main features of the algorithm. We allow and penalize violations of the vehicle capacity in the cost function when customer-commodities are inserted into existing routes. A maximum capacity violation on each route is imposed. Hence, it is possible that a customer-commodity cannot be inserted in any route of the current solution. In this case, we select one distribution center from which serving this customer-commodity is feasible with respect to the availability, and we create an additional route. If several distribution centers may be chosen, the one that minimizes the delivery cost is selected. We also allow violations of the limited quantities U C dm of commodities available at each distribution center. Both the violation of vehicle capacity and quantities U C dm are penalized in the objective function, proportionally to the violation. The penalty rates are denoted as λ and γ, respectively. Hence, if a solution violates the vehicle capacity (available quantities U C dm ) by an amount v, then a term λv (γv) is added to the cost function. Initially, λ (γ) is set to a minimum value λ min (γ min ) that is equal to the cost of the initial solution. The penalty rate λ (γ) is then dynamically modified during the search as follows. We keep track of the number of consecutive feasible and infeasible solutions visited during the ALNS algorithm. If E inf infeasible solutions are obtained consecutively, the value of λ (γ) is increased to 2λ (2γ). Similarly, if E f eas feasible solutions are generated consecutively, the value of λ (γ) is decreased to max {λ min ; λ/2} (max {γ min ; γ/2}).

Destroy and Repair. This procedure aims at diversifying the search. It relies on a set of removal and insertion operators which iteratively destroy and repair solutions. The removal and insertion operators are selected using a roulette wheel mechanism. The probability of selecting an operator is dynamically influenced by its performance in past iterations [START_REF] Ropke | An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[END_REF]. It uses two removal operators (Shaw removal and random removal of customers), and three insertion heuristics of customer-commodity based on greedy, regret-2 and regret-3 insertion paradigms.

Local search. The Local Search procedure (LS) considers classical operators [START_REF] Laporte | Fifty years of vehicle routing[END_REF], [START_REF] Vidal | Heuristics for multi-attribute vehicle routing problems: A survey and synthesis[END_REF], [START_REF] Laporte | Heuristics for the vehicle routing problem[END_REF]): insertion, swap and 2-opt for customers, and insertion and swap for customer-commodities. Insertion consists in relocating a customer or a customer-commodity from its current position in a different position of the same or another route. Swap consists in exchanging the position of two customers or customer-commodities. 2-opt replaces arcs (u, x) and (v, y) in a route by arcs (u, v) and (x, y), where u and v represent customers and x and y their successors. We do not consider the 2-opt operator based on customer-commodities. In fact this operator works on elements of the same route and it is never beneficial to split apart customer-commodities associated with the same customer. Note that when a move is applied on a customer (and not on a customercommodity), it means that all commodities delivered to the customer in the route are involved in the move. These operators consider moves in the same route, moves between different routes assigned to the same distribution center and moves between routes assigned to different distribution centers.

Intensification. When a new best solution is found, we intensify the search by applying a Mathematical Programming Operator (MPO). The main goal is to define a new assignment of the visits to a customer i by solving a capacitated facility location problem. The MPO has been introduced in [START_REF] Gu | Adaptive large neighborhood search for the commodity constrained split delivery VRP[END_REF] and we modified it for the solution of the SPD. For the sake of clarity, we provide in the following the formulation of the MPO. We introduce the following notation: s i : solution obtained from the current solution by removing all the visits to customer i;

R i : set of routes in s i ; C i r : cost for inserting customer i in route r ∈ R i (cheapest insertion); Q i r : remaining capacity in route r ∈ R i .
The decision variables are the following:

x i mr : binary variable equal to 1 if the delivery of commodity m ∈ M i of customer i ∈ V C is assigned to route r ∈ R i ;

x i r : binary variable equal to 1 if customer i ∈ V C is inserted in route r ∈ R i .
The formulation of the MPO is the following:

(IP M P O ) min r∈R i C i r x i r (32) s.t. r∈R i x i mr = 1, ∀ m ∈ M i , ( 33
)
m∈M i D im x i mr ≤ Q i r x i r , ∀ r ∈ R i , (34)
x i mr ∈ {0, 1}, ∀ m ∈ M i , r ∈ R i , (35)
x i r ∈ {0, 1}, ∀ r ∈ R i . ( 36
)
The objective function (32) aims at minimizing the total insertion cost. Constraints (33) require that each commodity is assigned to one route. Constraints (34) impose that the total quantity of commodities assigned to a selected vehicle does not exceed its capacity. Constraints ( 35)-( 36) define the decision variables. (IP M P O ) is solved for each i ∈ V C and only the reassignment of visits of customer i associated with the largest cost reduction is implemented. Formulation ( 32)-( 36) corresponds to the one proposed in [START_REF] Gu | Adaptive large neighborhood search for the commodity constrained split delivery VRP[END_REF]. In order to solve the SPD, we add another constraint ensuring that the distribution centers are not overloaded. Specifically, let Q i dm represent the remaining quantity of commodity m at depot d ∈ V D in s i . Then, the following constraints are added:

D im x i mr ≤ Q i dm , ∀ m ∈ M i , r ∈ R i , (37)
which ensure that the quantity of commodity assigned to each distribution center does not exceed its remaining availability.

Sequential solution approaches

In the previous two sections, we presented how the two subproblems, the SPC and the SPD, are solved. We now show how we combine the two approaches in order to obtain a solution method for the MC2DP. Different strategies are proposed, all based on the sequential solution of the two subproblems: the SPD and the SPC. In particular, we propose strategies where the SPD is solved first and the SPC second (indicated as SPD → SPC), or, vice-versa, first we solve the SPC and then we solve the SPD (indicated as SPC → SPD). In both cases, the solution of the first subproblem determines the quantity of each commodity at each distribution center. The second subproblem takes this information and deals with delivery or collection accordingly. Note that when the first subproblem is solved, the solution is such that the minimization of the transportation cost of that specific problem only is considered, regardless of the other subproblem. This may lead to solutions of poor quality for the MC2DP. As a consequence, we propose different strategies to guide the solution of the first subproblem and obtain better solutions of the MC2DP.

Sequential solution: SPD → SPC

When the SPD is solved first, we consider three strategies to determine the values of quantities U C dm available at the distribution centers. The SPD is then solved through the algorithm presented in Section 4.2. Note that a solution of the SPD gives the required quantities U D dm of each commodity m at each distribution center d, computed as the sum of the demands of the customer-commodities assigned to this distribution center. Afterward, the SPC is solved by fixing the values of y variables and the required quantities at the depots U D dm in F SP C according to the solution of the SPD. The three strategies are as follows.

SPD infinite → SPC. In this strategy, the values U C dm involved in the GAP formulation (Section 4.2.1) and in the ALNS algorithm (Section 4.2.2) are set to a valid upper bound as follows:

U C dm = i∈V C D im , ∀d ∈ V D , m ∈ M
and do not restrict the search.

SPD finite balanced → SPC. In this strategy, the values U C dm are restrictive and aim at balancing the quantity of commodities distributed from each distribution center. As a consequence, the quantity of each commodity available at each distribution center is determined as:

U C dm = i∈V C D im |V D | + max i∈V C {D im }, ∀d ∈ V D , m ∈ M.
Note that the second term involved in the computation of U C dm guarantees that the SPD has a feasible solution and it also allows some flexibility in the assignment of customer-commodities to distribution centers.

SPD finite supplier based → SPC. In this strategy, the values U C dm are determined taking into account the location of the distribution centers and the suppliers. The idea is to compute the available quantities U C dm at distribution center d based on the available quantities of the suppliers located close to d. First, we assign each supplier to its k closest distribution centers. Then, the quantity U C dm of commodity m available at distribution center d is computed as the sum of the available quantities O sm for commodity m over all suppliers assigned to distribution center d. Note that if there are few distribution centers, k will take value 1, but when there are several distribution centers, k can be larger than 1 to consider larger values for U C dm , providing more flexibility for the solution of the SPD.

Sequential solution: SPC → SPD

When the SPC is solved first, we consider three strategies. Based on the strategy chosen, we define different values for U D dm , and the formulation F SP C is solved to obtain a solution for the SPC. Then, in order to solve the SPD, the U C dm values are defined from the solution of F SP C as follows:

U C dm = s∈V S q m sd , ∀d ∈ V D , m ∈ M. (38)
Finally, the SPD is solved. The three strategies considered when the SPC is solved first are listed in the following.

SPC not full truck → SPD. In this strategy, the SPC is first solved using the model F SP C presented in Section 4.1 with values U D dm set to a non-binding value, i.e.:

U D dm = 0, ∀d ∈ V D , m ∈ M.
SPC full truck → SPD. In this strategy, the SPC is first solved using the model F SP C presented in Section 4.1 with values U D dm set to 0 as in the former strategy. Then, the solution of the SPC is updated by using the remaining capacity of the trucks to increase the quantities q m sd brought to the distribution centers. This does not modify the cost of the SPC, but offers more flexibility when solving the SPD due to larger availabilities (U C dm ) at distribution centers. More precisely, for each supplier s and each distribution center d, we divide the remaining capacity of the trucks traveling from s to d by the number of commodities available at supplier s. This gives an equal maximum quantity q f ill for each commodity in order to fill the trucks. If the availability of some commodity is less than q f ill , we fill the trucks as much as we can and we possibly repeat the procedure. Details of the procedure are given in Algorithm 2 in the Appendix A. This procedure increases the values of variables q m sd in formulation F SP C . Then, in order to solve the SPD, U C dm values are defined as in Equation ( 38).

SPC full truck customer based → SPD. This strategy solves the model F SP C in which quantities U D dm are determined on the basis of the locations of the customers. The idea is to compute the quantities U D dm required at distribution center d based on the demands of the customers located close to the distribution center d and far from other distribution centers. Customers close to several distribution centers are not included in the computation of U D dm to ensure some flexibility. Given two distribution centers d 1 and d 2 with a distance a between d 1 and d 2 , we say that a customer i is d 1 -d 2 compatible if one of the following two conditions is satisfied: (1) the distance between i and d 1 is less than a/3; or (2) the distance between i and d 1 is less than a, and the distance between i and d 2 is greater than a. An example is given in Figure 4. For each distribution center d, we say that a customer i is assigned to

d if for all other distribution centers d ∈ V D \ {d}, i is d-d compatible.
With the choice of a/3, customers at similar distance from two distribution centers are not assigned to any distribution center, as illustrated in Figure 4. Then, the quantity U D dm is computed as the sum of the demands of commodity m ∈ M of customers assigned to d ∈ V D . After solving F SP C , the strategy SPC full truck → SPD is applied to increase the quantities q m sd . Finally, values U C dm are calculated as in Equation (38).

Computational experiments

In this section, we compare the solution algorithms proposed in Section 4.3 to solve the MC2DP sequentially. An algorithm is determined by the sequence in which the two subproblems are solved and the strategy to solve the first subproblem.

In Section 5.1, we describe the generation of the sets of instances for the MC2DP based on instances for the C-SDVRP. Then, in Section 5.2, we report the results obtained when solving the instances with the different sequential algorithms. Then, we provide in Section 5.3 an analysis of the results to identify the instance characteristics that mostly impact the algorithm performance. Finally, in Section 5.4 we evaluate the quality of the solutions obtained with the sequential approach, with respect to the solving of the formulation F M C2DP with a commercial solver.

The algorithms have been implemented in C++ and run on an Intel (R) Core(TM) i7-4600U, 2.10GHz, and 16GB of RAM. We summarize the notation used to present the instances and the results in Table 1. Average CPU time for computing the SPC solution (in seconds)

Table 1: Notation for computational results.

Instances

First, we create a base set of instances that is indicated as S. Then, the other 11 sets are generated by modifying one of the characteristics of set S.

Generation of the base set of instances S

The delivery subproblem (SPD) of the MC2DP extends the C-SDVRP by considering multiple distribution centers. Hence, we build the base set of instances from instances of the C-SDVRP. More precisely, we consider the 64 small instances with 15 customers proposed by [START_REF] Archetti | Multicommodity vs. single-commodity routing[END_REF]. These instances are built from the customer locations of the R101 and C101 Solomon instances for the VRP with Time Windows [START_REF] Solomon | Algorithms for the vehicle routing and scheduling problems with time window constraints[END_REF]. Each instance is characterized by five parameters listed thereafter. I ∈ {R101, C101} indicates if the instance is based on R101 or C101. Only the depot and the first 15 customer locations are considered from the Solomon instances. The number of commodities, indicated by M , is equal to 2 or 3. A customer requires a commodity with probability p equal to 0.6 or 1. The quantity of each commodity required by a customer varies within the intervals ∆ = [1, 100] or ∆ = [40,60]. Last, parameter α ∈ {1.1, 1.5, 2, 2.5} determines the vehicle capacity by multiplying the vehicle capacity in the original Solomon instances. We indicate by P = (I, M, p, ∆, α) the set of parameters listed above.

For each instance I of the C-SDVRP, we create an instance I M C2DP for the MC2DP as follows. Given the coordinates (x d , y d ) of the distribution center in I, one distribution center of I M C2DP is located in (x d , y d ), while another one is located in (x d + δ, y d + δ). Given the coordinates (x, y) of a customer in I, one customer of I M C2DP is located in (x, y), while another customer is located in (-x+2x d +δ, -y+2y d +δ). Both customers have the same demand as in I. Hence, the instance I M C2DP contains one distribution center d 1 and a set V 1 C of 15 customers with the same locations as instance I. It contains as well another distribution center d 2 and a second set V 2 C of 15 customers. Customers in V 2 C are transposed by (δ, δ) from the original locations, and are also rotated by 180 degrees around the distribution center d 2 . After some preliminary experiments detailed in Appendix B, we set δ = 30.

To locate the 8 suppliers we proceeded as follows. We consider a circle of radius r centered at each distribution center. We randomly created inside each circle four suppliers. Should the two circles intersect, the intersection is not considered as a potential zone to locate suppliers. The value of the radius r has been fixed to 30. Note that the cost c ij associated with each arc (i, j) ∈ A is equal to the Euclidean distance between i and j.

The quantity of commodity m ∈ M available at each supplier is calculated as

O sm = ζ• i∈V C D im |V S |
, where ζ is a parameter that has been fixed to 1.2. Hence, all suppliers produce all commodities with the same amount. Globally, the total supply is 20% more than the total demand. The motivation for this characteristic of the instances is to avoid feasibility problems and always obtain a solution of the heuristics. We wanted to focus on the coordination aspect of the two echelons rather than on feasibility issues. When SP D → SP C, once the SPD is solved, the assignment of customercommodities to distribution centers is known, that is the quantity of the commodity delivered to each distribution center is known. Then the SPC is optimally solved by using the mathematical model.

Thus, the 20% flexibility of the supply does not impact this heuristic. When SP C → SP D, we should ensure that the solution of the SPC is feasible for the SPD. This is the reason why we allowed a larger than demand supply. However, note that having a larger supply than the total demand does not imply in practice a waste of products. Without being part of the system, the producers need to consecrate a consistent part of their working time to sell and deliver operations that are not their core business. The system would take care of a large segment of their production, freeing part of the working day. The remaining products may be sold across different channels, as on-site sales.

The capacities Q S and Q D of the trucks and vehicles are equal to the capacity of vehicles in I. Figure 5 shows the locations of customers, distribution centers and suppliers for C101 and R101 configurations. In order to ensure the diversity of the instances to evaluate the proposed sequential approach, we construct 11 additional sets of instances based on instances in S. Each of the 11 sets differs from S by the modification of one characteristic.

Modification of the supplier locations

In set S, four suppliers are generated around each distribution center. We generate two other sets of instances where we modify the location of suppliers by unbalancing the number of suppliers generated around each distribution center. These two sets of instances are named S S 1 and S S 2 . As for instance set S, we consider a circle of radius r = 30 centered at each distribution center, and no supplier is located in the intersection of the two circles. The characteristics of the new sets of instances are the following.

S S

1 : Around distribution center d 1 we randomly locate 6 suppliers. The other two suppliers are randomly located around d 2 .

S S 2 : Around distribution center d 1 we randomly locate 8 suppliers. No supplier is generated around

d 2 .
Examples of the two configurations are presented in Figures 6 and7.

Modification of the customer locations

In set S, each distribution center is surrounded by 15 customers. This makes the instances balanced from the point of view of the customer locations with respect to the distribution centers. We generate four sets of instances where we modified the location of customers by unbalancing the number of customers around each distribution center. These four sets of instances are named S C 1 , S C 2 , S C 3 and S C 4 . As with instance set S, given the coordinates (x, y) of a customer in I, one customer of I M C2DP is located in (x, y), while another customer is located in (-x + 2x d + δ, -y + 2y d + δ). For instances in S, the value δ = 30 has been considered. For the new sets of instances, the locations of the 15 duplicated customers are defined as follows.

S C

1 : For the first 5 customers in I, δ = -5; for the remaining 10 customers, δ = 30.

S C

2 : For the first 5 customers in I, δ = 10; for the remaining 10 customers, δ = 30.

S C

3 : For the first 10 customers in I, δ = -5; for the remaining 5 customers, δ = 30.

S C

4 : For the first 10 customers in I, δ = 10; for the remaining 5 customers, δ = 30.

An illustration of instances in S C

1 is given in Figure 8.

Modification of the available quantities at suppliers

In set S, given a commodity m ∈ M, all suppliers s ∈ V S have the same available quantity

O sm = ζ • i∈V C D im |V S |
, with ζ = 1.2. We generate a set of instances S O where we unbalance the available quantities at suppliers. For this set of instances, we only consider the 32 instances where the number of commodities is M =2. Half of the suppliers, all located around the same distribution center, have

O s1 = ζ • 1.8 i∈V C D i1 |V S | units of commodity 1 and O s2 = ζ • 0.2 i∈V C D i2 |V S |
units of commodity 2. On the contrary, the other suppliers, all located around the other distribution center,

have O s1 = ζ • 0.2 i∈V C D i1 |V S | units of commodity 1 and O s2 = ζ • 1.8 i∈V C D i2 |V S |
units of commodity 2. ζ is still fixed to 1.2.

Modification of the number of suppliers

The instances in S all contain 8 suppliers. Thus, we create other two sets of instances, indicated with S S add 1 and S S add 2 , that contain 10 and 12 suppliers, respectively. The number of customers is kept as in the base set S, i.e., equal to 30 for all instances. The new added suppliers are randomly placed around the two distribution centers, such that the same number of suppliers are placed around each distribution center.

Modification of the number of customers

The instances in S all contain 30 customers. We then create two sets of instances, indicated with S C add 1 and S C add 2 where the number of customers is increased to 50 and 70 respectively. The number of suppliers is kept as in S, i.e., equal to 8.

To locate the new customers, we randomly select customers in the original instance and we relocate them by translating the coordinates by a value that is randomly chosen in [-20, 20]. The demand of the new customer is equal to the demand of the original customer. The quantity of each commodity available at each supplier is determined as described in Section 5.1.1.

To sum up, in this work, we generate 12 sets of instances. Each set contains 64 instances except for set S O , which has 32 instances.

Comparison of the sequential heuristics to solve the MC2DP

The six heuristics presented in Section 4.3 for the solution of the MC2DP are tested on the 12 instance sets presented in Section 5.1. The mathematical programs presented in Section 4.2 are solved using Cplex 12.6. The ALNS algorithm is run with a limit of 5000 iterations and the values of the parameters used in [START_REF] Gu | Adaptive large neighborhood search for the commodity constrained split delivery VRP[END_REF]. The additional parameters introduced in Section 4.2.2 are set to E inf = 50 and E f eas = 50 after preliminary experiments. We recall that the values of γ min and λ min equal the cost of the initial solution. Moreover, for the algorithm SP D f inite supplier based → SP C, we set k = 1 since the instances contain few distribution centers.

In order to compare the algorithms, for each instance set we report: We also report the minimum average results for the collection cost, the delivery cost and the total cost in the last line of each table.

Table 2 reports the results for the instance set S. The best value obtained for the MC2DP, the SPC and the SPD are provided in bold. The table shows that the best algorithm is SP D f inite balanced → SP C. The other algorithms that solve first the SPD provide also good results, always better than the algorithms where the SPC is solved first. The worst algorithm is SP C not f ull truck → SP D, with an average increase in total cost of 2.35%. We also note that, when solving the SPD first, we have an increase in the cost of the SPC of more than 8%. Instead, when solving first the SPC, the increase on the SPD cost goes from 4.49% to 7.54%. However, the algorithms solving thhe SPD first provide better values of total cost. This is due to the unbalance in the total cost of the SPC and the SPD. Finally, it is interesting to note that the algorithm providing the best total cost is not the best for none of the two subproblems. On average, the CPU times are around 1 minute. Since computational times on the other sets

(S S 1 , S S 2 , S C 1 , S C 2 , S C 3 , S C 4 , S O
) of instances are similar, we do not report them in the following Tables 3, 4, 5 and6 Results on instance sets S S 1 and S S 2 with modification of the supplier locations are reported in Table 3. We note that, among the three algorithms where the SPD is solved first, the algorithm SP D f inite supplier based → SP C provides a high cost for the SPD. However this is compensated by a low cost for the SPC resulting in the lowest cost for the whole problem. When supplier locations around the distribution centers are unbalanced, the algorithm SP D f inite supplier based → SP C is very efficient in comparison with the other algorithms that solve first the SPD. We also note that, for these sets of instances, the sequence in which the subproblems are solved has a significant impact with respect to the instances in the base set S, providing a larger increase in the cost of the second subproblem, especially on the set S S 2 . The best algorithm is SP D f inite supplier based → SP C. On S S 2 , SP C not f ull truck → SP D has the same performance as SP D f inite supplier based → SP C. However, we note that the remaining algorithms in which the SPC is solved first perform better than the remaining algorithms where the SPD is solved first, especially S S 2 .

Instance 4 and5. These instances have unbalanced customer locations around the distribution centers. For these four sets, the algorithms SP D f inite balanced → SP C and SP D supplier based → SP C provide the best results for the whole problem. The total costs achieved with these two algorithms are very similar. It can be noticed that when applying the algorithm SP D inf inite → SP C, the results are not competitive with the two other algorithms where the SPD is solved first: the cost of the SPD is smaller but the cost of the SPC increases a lot, leading to a high value of the total cost. Moreover, for the three algorithms where the SPC is solved first, we observe a similar behaviour for these sets of instances and the base set S. The only difference is that the algorithm SP C f ull truck customer based → SP D provides the best results among the three algorithms where the SPC is solved first. Note that when the SPC is solved first and the customer locations are not taken into account (algorithms SP C not f ull truck → SP D and SP C f ull truck → SP D), the solutions that are obtained for the SPC are always the same and have the lowest SPC cost for all the considered instances. However, the overall solution is never the best. This clearly shows the importance of taking into account the location of final customers when bringing commodities to distribution centers. It can be observed that the results obtained by the different sequential heuristics are similar to the results obtained on the instance set S. In particular, the best results are generally obtained when the SPD is solved first. It can also be noted the the worst strategy is, in all cases, SP C not f ull truck → SP D, as it is the case for the instance set S. We can observe that the computational time increases with respect to the number of customers, while it is little impacted by the addition of suppliers. This can be explained by the greater difficulty in solving a larger SPD, where routes have to be determined, compared with solving a larger SPC, where direct trips only are considered.

Results on the different sets of randomly generated instances reveal that SP D f inite supplier based → SP C and SP C f ull truck customer based → SP D are the best algorithms. As a rule, SP D f inite supplier based → SP C identifies the best solutions in most cases except when the quantities available at the suppliers are unbalanced. In the latter case, SP D f inite supplier based → SP C has a better performance.

Analysis of the performance of the algorithms

In this section, we present an analysis of the results presented in Section 5.2 to identify the instance characteristics that mostly impact the algorithm performance. More specifically, we aim at finding .

rules to determine the best solution approach, among the ones we proposed, based on the instance characteristics. This is of crucial importance for the decision-maker. In fact, instance characteristics are known before determining a solution for the problem.

Starting from the results presented in Table 2, we already noticed that all algorithms in which the SPD is solved first perform better than the ones in which the SPC is solved first, even though the gap is not substantial. We note that the instances on which these results were obtained, set S, are well balanced in terms of location of customers and suppliers: two distribution centers are present, and customers and suppliers are evenly distributed in the neighborhood of the two. In such a case, the two sequential schemes tend to give similar solutions, in terms of assignment of customers and suppliers to distribution centers. We explain that all algorithms in which the SPD is solved first produce better solutions than when the SPC is solved first by the fact that the major cost component in the instances is the routing cost. The same is true in Tables 78910, where instances are still balanced.

From Tables 3-6 we see, instead, that when instances are unbalanced in terms of location of suppliers and/or customers or in terms of quantity requested/available, then it is important to take into account this unbalance when choosing the most appropriate solution method. The best strategy is the one that optimizes first the unbalanced part, i.e., the SPD first when customers are unbalanced and the SPC first when suppliers are unbalanced. In addition, the results also show that, in this case, it is important to consider a strategy that links the two subproblems. In fact, SP D f inite supplier based → SP C and SP C f ull truck customer based → SP D are the two more robust strategies. Even though each of them is not always the best strategy among those solving the SPD and the SPC first, respectively, their gap with respect to the best solution is always small and has lower variations with respect to the other strategies.

A summary of the results in Tables 3-10 is reported in Table 11. We see that the maximum gap of SP D f inite supplier based → SP C is 2.09% while the one of SP C f ull truck customer based → SP D is 1.25%. All other strategies present a gap that, in the worst case, is well above 3%. 345678910.

Strategy S S 1 S S 2 S C 1 S C 2 S C 3 S C 4 S O S S

Evaluation of the sequential heuristics

This section is devoted to the evaluation of the quality of the solutions obtained by the sequential schemes. To this end, we created four sets of small instances. The new instances have 10, 15, 20 and 25 customers, respectively. Instances with 10 to 20 customers have 4 suppliers while instances with 25 customers have 6 suppliers. Each set contains 9 instances.

To create these instances we randomly selected 3 instances from S, S S 1 and S S 2 . The original instances are all from the class C101 with α = 1.1 and ∆ = [1, 100]. From the selected instance we randomly removed customers and suppliers.

The compact formulation F M C2DP for the MC2DP, presented in Section 2.1, as well as the sequential heuristics to solve the MC2DP are evaluated over these instances. Formulation F M C2DP is solved using Cplex 12.8. A maximum computational time of 1 hour is given to Cplex.

The results are reported in Table 12. The first three columns of the table give the characteristics of the instance, where M indicates the number of commodities and p is the probability that a customer requires one commodity, as previously explained (see Section 5.1). Column set indicates the instance set from which the instance is created. The fourth, fifth and sixth columns report results obtained by solving formulation F M C2DP with Cplex 12.8. Column UB reports the value of the best feasible solution provided by Cplex, while Column LB reports the best lower bound. The symbol indicates that Cplex was not able to provide a feasible solution. Column t(s)/gap(%) is a hybrid column that reports the computational time, in seconds, when Cplex solves the instance to optimality in the given amount of time or the optimality percentage gap, computed as 100 • U B-LB LB . The last three columns report the performance of the sequential heuristics. Column best reports the value of the best solution obtained over the six sequential heuristics presented in Section 4.3, column t(s) reports the total time, in seconds, needed to run the six heuristics. The last column provides the percentage gap between the value of the solution obtained by Cplex and the value of the solution obtained by the sequential approaches. This is computed as 100

• best-U B U B
. Whenever columns UB and best report the same value, a symbol . is used to indicate that the sequential approaches succeed in finding the optimal solution, while the symbol indicates that the sequential approaches found the same solution as Cplex, but optimality has not been proved. As it can be seen from Table 12, on instances with 10 customers the sequential approaches can always find the optimal solution whenever Cplex is able to prove optimality. When the number of customers goes up to 20 or 25, the sequential approaches always find a better solution, with an average improvement of more than 15% for instances with 25 customers. As expected, the lower bounds that Cplex provides are too poor to draw any conclusions on the quality of the solutions that the sequential approach obtains. The only conclusion that can be drawn from the analysis of Table 12 is that, as the size of the instance increases, a heuristic approach is the only viable method, since Cplex begins to struggle to provide feasible solutions. On tests run with 30 customers and not reported in the table, Cplex identified a feasible solution for one instance only. In addition, we carried out additional tests by letting Cplex run for two hours instead of one, but this led to a very minor improvement of the lower bound. Thus, the corresponding results are not reported.

A case study

In this section, we present a study on instances generated from a real case application. The aim is to show how the sequential solution approaches behave on real-case applications.

Context

The case study was proposed by local authorities of the French department of Isère (General Council and Chamber of Agriculture). The aim is to increase the volume of fresh food products sold through short and local supply chains in the department of Isère. The department of Isère is an interesting location for fresh food supply chains since: i) there are many farmers producing a variety of fruits and vegetables, ii) these farmers have very low revenues when selling their products through classical distribution channels, iii) the inhabitants of the department are deeply interested in buying local fruits and vegetables through short and local supply chains.

Local authorities of Isère identified two kinds of customers for short and local supply chains: school canteens and supermarkets. For such customers, considering direct deliveries from the farmers is not acceptable as farmers should devote a significant part of their working time to carrying out deliveries. Hence, the idea is to use a set of distribution centers which would be jointly managed by associations of farmers.

Description of the data sets

In this case study, the commodities are fresh fruits and vegetables: apple, pear, kiwi, strawberry, carrot, lettuce, tomato, zucchini, cucumber, potato. In order to reflect the seasonality of these products, demand and supply are not constant over the year. Hence, we consider a set of patterns for demand and supply. Each pattern gives rise to one instance whose objective is to capture the availability of the products of the month.

Two sets of customers are considered: school canteens and supermarkets. A study conducted with the General Council of Isère has permitted to collect and estimate actual demands for school canteens. The demand associated with supermarkets has instead been generated according to the following procedure. The selected supermarkets are the ones selling fresh food products with a sales area of at least 300m 2 . Demands for each supermarket have been generated under the following hypotheses: i) the demands for each product has the same proportion as for school canteens (i.e. people have the same kind of food consumption at home and in school canteens), ii) demands are proportional to the sales area of the supermarket, and iii) the global demand of all commodities is proportional to the global revenue generated by the sales of the considered fresh products through supermarkets, for which the data are provided by a statistical study from the General Council of Isère. For school canteens, 8 patterns of demands and supply are considered, and for supermarkets 10 patterns are considered. Hence, there is a set of 18 instances for the case study.

The instances are divided in two sets: one considering canteens and one considering supermarkets. This is because the General Council of Isère is interested in evaluating the possibility of implementing a network that supplies school canteens or supermarkets from producers using distribution centers. However, the possibility of having a shared network to serve these two sets of customers is not taken into account. This is mainly due to the different demand of products in the two cases, with the supermarket demands being much more important. The effect of this difference is twofold. First, when school canteens are involved, producers could use their vehicle to bring commodities to the distribution centers since the daily demand is limited. On the other hand, when supermarkets are considered this is not anymore a viable option since producers would spend an important part of their working time performing round trips to the distribution centers. In this case, it is supposed that farmers may wish to purchase larger vehicles as a counterpart of participating in the collaborative system. Second, to deliver to supermarkets one can suppose that large trucks can be used efficiently due to the volume of the demand. In addition, dedicated docks are usually available in supermarkets to unload vehicles. On the other side, the demand of canteens is smaller and not sufficient to fill such large trucks, which are also unlikely to be able to access them. Due to these reasons, the General Council of Isère wishes to study the two cases separately in order to consider the possible implementation of one network.

In the school canteens instances, there are 103 customers and up to 61 suppliers. For each pattern of supply and demand, the number of commodities ranges from 5 to 8, and the number of suppliers producing at least one commodity ranges from 54 to 61. In the supermarket instances, there are 188 customers and up to 61 suppliers. For each pattern of supply and demand, the number of commodities ranges from 5 to 8, and the number of suppliers producing at least one commodity ranges from 45 to 61. In all instances, there are 5 distribution centers. Their locations have been proposed by the General Council and the Chamber of Agriculture of Isère. The sizes of the instances are reported in Tables 13 and14 Table 13: School canteens instances.

Analysis of the results

The instances are very large with respect to the ones described in Section 5.1 since there are up to 1500 customer-commodities. The computational time of the ALNS significantly increases with the size of the instances. Hence, when solving the SPD, the ALNS algorithm is run with a limit of 100 iterations. Moreover, due to the size of the instances, we set a time limit for solving mixed integer linear programs. More specifically, we set a 5 minutes time limit to solve the GAP model presented in Section 4.2.1 to obtain an initial solution of the SPD, and a 10 minutes time limit to solve the formulation F SP C . As there are 5 distribution centers, when applying the algorithm SP D f inite supplier based → SP C, we set k = 2, i.e., each supplier is assigned to its two nearest distribution centers.

The results obtained for each sequential approach are reported in Table 15 for the school canteens and in Table 16 for the supermarkets. The columns nbT and nbV indicate the numbers of trucks used for collection operations and the number of vehicles used for delivery operations, respectively. The columns ∆SP Ccost, ∆SP Dcost and ∆Cost report the percentage difference between the SPC cost and the minimum SPC cost, the SPD cost and the minimum SPD cost, the total cost and the minimum total cost, respectively.

When customers are school canteens, two algorithms outperform the others, namely: SP C f ull truck → SP D and SP D f inite supplier based → SP C. It is interesting to note that SP C f ull truck → SP D provides the best results on average. However, this algorithm gives low collection costs and high delivery costs. This is an interesting observation: in fact, local authorities might judge as inappropriate a solution where the cost is highly unbalanced, even if it provides the best cost for the overall system. On the contrary, the algorithm SP D f inite supplier based → SP C is a bit more costly on average, but has the advantage of balancing the costs between collection and delivery. It can also be noticed that the algorithms SP D f inite balanced → SP C and SP C f ull truck customer based → SP D do not provide good solutions. This could be explained by the fact that suppliers and customers are not located homogeneously around the distribution centers. For the instances with supermarkets, two algorithms outperform the others, namely: SP D f inite supplier based → SP C and SP D inf inite → SP C. SP D f inite supplier based → SP C provides the best results on 7 instances out of 10, and has the advantage of balancing the costs between collection and delivery operations. It can be noticed that some sequential algorithms lead to a very high cost, namely SP D f inite balanced → SP C and SP C not f ull truck → SP D.

We note that the algorithm SP D f inite supplier based → SP C again provides very good results on these additional sets of instances. However, depending on the instance setting, some approaches based on the SPC solution first can be competitive.

From a computational point of view, solving the SPD first takes much less time than solving the SPC first. Moreover, most of the time is spent on solving the SPD. When solving the SPC first, the available quantities at the distribution centers are very limited, which may generate a significant infeasibility when applying destroy and repair moves in the ALNS algorithm. This makes it more difficult to obtain good solutions with the local search. When customers are school canteens, few trucks are used. Their number is less than the number of suppliers. This means that some suppliers do not provide any commodity since they are far from each distribution center. When customers are supermarkets, the total supply is not very large compared to the total demand. Hence, more trucks are used for the delivery and several suppliers perform more than one trip to a distribution center.

On the benefit of consolidation

As explained in the previous section, delivery operations to school canteens and supermarkets should be kept separated due to different vehicles used to perform the delivery. However, collection operations may be consolidated and carried out only once for both school canteens and supermarkets.

To study this scenario, we created 5 new instances from the instances presented in the previous section. These new instances are obtained by merging one school canteen and one supermarket instance characterized by the same number of commodities, the same number of suppliers, and the same distance matrix with respect to suppliers and distribution centers. It should be noted that the distance between a canteen and a supermarket is assumed to be infinite. Indeed, the two sets of canteens and supermarket were considered separately, and we only have a distance matrix for each set. Hence, we were not able to recompute distances between the two sets of customers.

In order to keep the sequential nature of the solution approach, we tested three strategies and compared the results with total cost obtained by simply summing up the costs obtained by solving the two instances separately.

The three strategies are:

solve the SPD for canteens and supermarkets, determine the quantity of each commodity required at the distribution centers by summing up what is needed in each case, then solve the SPC with this requirement. This strategy is indicated by SP D → SP C;

simultaneously solve the SPC for canteens and supermarkets, then solve the SPD for canteens, update the available quantity at distribution centers, then solve the SPD for supermarkets. This strategy is indicated by SP C → SP DCanteens1st;

simultaneously solve the SPC for canteens and supermarkets, then solve the SPD for supermarkets, update the available quantity at distribution centers, then solve the SPD for canteens. This strategy is indicated by SP C → SP DSupermarkets1st

Each time an instance of the SPC or the SPD is solved, the three corresponding strategies, defined in Section 4.3, are run in order to solve the suproblem, and the best result is kept. The results are reported in Tables 1718. A dash means that the approach did not find a feasible solution for the corresponding instance. In Table 17, column Base reports the costs for the separated case. It is calculated as the sum of the costs of the two original instances corresponding to the merged instances, i.e., the sum of the costs of the canteen and supermarket instances. Columns SP D → SP C, SP C → SP DCanteens1st, and SP C → SP DSupermarkets1st report the costs for the three proposed strategies. In Table 18, we report the evolution in percentage, of the costs of the three strategies, with respect to the cost of the separated case. As an example, the value 9.71 means that for the instance merged1, when using the strategy SP D → SP C, the cost for the SPC increases by 9.71% with respect to the cost for the SPC in the separated case. As expected, consolidation of the collection reduces, in all the cases, the total cost of the solution with respect to the Base case. These reduction in total cost are important since the total cost is decreased by 13% to 36%. This cost reduction is often due to a very important cost reduction in the first subproblem solved. Table 18: Comparison of the results between separated and merged cases: percentage difference for the merged cases with respect to the separated case (Base).

From Tables 17 and18 one can observe that when the SPC is solved first, solving the SPD for school canteens before solving the SPD for the supermarkets brings to infeasibility. This is explained by the higher demands of supermarkets and the reduced flexibility that is left to the optimization after solving the SPD for school canteens.

We can also note that, in most of the cases, the best results are obtained when the SPC is solved first. In this case, larger savings are obtained from merging collection activities.

Conclusions and future research

In this paper, we presented a new and complex problem which occurs, for example, in local agrifood supply chains, the MC2DP (Multi-Commodity two-echelon Distribution Problem). The problem concerns the collection of commodities from suppliers to distribution centers and the delivery from distribution centers to final customers. The objective is to jointly optimize the transportation plan for the collection and delivery operations. In order to tackle this complex problem, we proposed two sequential approaches based on the decomposition of the problem in two subproblems: collection and delivery. For each sequential approach, three strategies are considered in order to take into account, in the first subproblem solved, the impact of its solution on the second subproblem solved.

The proposed algorithms have been compared on several sets of instances derived from instances from the literature. The best algorithm usually does not provide the lowest cost neither for the collection nor for the delivery subproblem. The algorithms are also tested on a case study of a short and local fresh food supply chain. Large size instances are considered with two types of customers, school canteens and supermarkets. We compared the different algorithms and provided some managerial insights about cost balancing between collection and delivery.

The MC2DP is a complex problem to solve. The proposed sequential approaches have the advantage of being easy to design and to be understood by decision makers. However, it is well known that sequential solution approaches may provide suboptimal solutions. Thus, the main future research direction is to develop an integrated solution approach solving the MC2DP as a whole instead of decomposing it in subproblems.

Future research will study the system in a multi-period horizon, allowing to take into account fairness aspects. In practical settings, the offer of products is larger than the demand. This implies that not all the producers may be involved in the supply of final customers during a given day. Conditions might be imposed on the quantity collected from producers on a multi-day basis, thus guaranteeing a fair treatment of each farmer.

A Algorithm for the full truck strategy Algorithm 2 Full truck strategy. Add Q m sd to q m sd 15:

Remove Q m sd units from R sd 16:

Remove Q m sd units from R sm 17:

end for 18:

Update nbR s 19:

end while 20:

end for 21: end for B Detailed results for setting the value of δ

We discuss here how we set the value of δ that determines the location of duplicated customers and distribution center. We solve the delivery subproblem (SPD) for each instance I M C2DP in the base set S. The collection subproblem is not considered, and the SPD is solved as discussed in Section 4.2. The ALNS is run with a limit of 5000 iterations. To evaluate the solutions, we compare the cost obtained for the SPD (SP Dcost) with twice the optimal value OP T for the corresponding instance of the C-SDVRP, as reported in [START_REF] Archetti | Multicommodity vs. single-commodity routing[END_REF]. By construction of the instances, 2OP T is a valid upper bound for the SPD. These tests are performed with values of δ: 100, 50, 30, 20, 10, and 5.

The results are presented in Table 19. We present results for each group of instances, where a group is defined by a triplet (I, M, p). Results for a group are averaged on the values of α and ∆. Each instance contains 30 customers and 2 distribution centers. Table 19 reports the average number of customer-commodities in each group of instances (avg.n cc ), the number of instances in the group (nbIns), the average deviation (avg.∆) of the cost obtained by solving the SPD and the upper bound 2OP T , the average CPU time in seconds (avg.t(s)). Moreover, the last three columns respectively report the number of solutions such that the cost obtained by solving the SPD is higher than, equal to or lower than 2OP T .

We observe that when δ is large (i.e., equal to 100), the solution value equals 2OP T most of the time. In this case, by construction of the instances, this value is most likely to be the optimal value. On the other side, when δ is smaller than 100, the value 2OP T is a valid upper bound that can be improved by running the algorithm for the SPD. When δ equals 5 or 10, for all instances we obtain a value lower than 2OP T since the distribution centers are then very close. We are interested in generating a set of instances where the average deviation from 2OP T is negative, but with some instances such that the cost of the SPD equals 2OP T . Hence, we set δ = 30.

Figure 1 :

 1 Figure 1: An instance of the MC2DP.

  a) Solution of the SPC. (b) Solution of the SPD.

Figure 3 :

 3 Figure 3: Solutions of the two subproblems based on the solution of the MC2DP in Figure 2.

Figure 4 :

 4 Figure 4: All customers in the grey zone are d 1 -d 2 compatible.

  Locations in instances obtained from C101. (b) Locations in instances obtained from R101.

Figure 5 :

 5 Figure 5: Locations in instances in S.

  in instances obtained from C101. (b) Locations in instances obtained from R101.

Figure 6 :

 6 Figure 6: Locations in instances of S S 1 .

Figure 7 :

 7 Figure 7: Locations in instances of S S 2 .

  Locations in instances obtained from C101. (b) Locations in instances obtained from R101.

Figure 8 :

 8 Figure 8: Locations in instances of S C 1 .

  . The locations of customers, suppliers and distribution centers in the department of Isère are shown in Figure 9. The capacity of the vehicles is set such that Q D = 2Q S , since farmers in short and local supply chains generally do not have large capacity vehicles while distribution centers may invest in vehicles with bigger capacity to visit several customers. instance id |V C | |V S | |V D | |M| 1

Figure 9 :

 9 Figure 9: Locations in the case study instances.

1:

  for each supplier s ∈ V S do 2:for each commodity m ∈ M do 3:Compute the remaining quantity R sm = O sm -∀d∈V D q Let nbR s be the number of commodities of supplier s such that R sm > 0 6: end for 7: for each distribution center d ∈ V D do 8:for each supplier s ∈ V S do 9:Compute the remaining capacity in the trucks R sd = x sd × Q S -m∈M q m sd 10:while nbR s > 0 and R sd > 0 do 11:Compute the average remaining capacity per commodity as avgR sd = R sd /nbR s 12:for each commodity m ∈ M do 13:Determine the maximum quantity of commodity m that supplier s can insert in the trucks sent to DC d as Q m sd = min{avgR sd , R sm } 14:

  Average CPU time for computing the MC2DP solution (in seconds) avg.SP Dt(s) Average CPU time for computing the SPD solution (in seconds) avg.SP Ct(s)

	Symbol	Meaning
	nbIns	Number of instances in each group
	SP Dcost	Best solution cost for the SPD
	SP Ccost	Best solution cost for the SPC
	Cost	Total cost for the MC2DP
	avg.t(s)

  ∆avg.SP Ccost: percentage difference between the average cost for collection (avg.SP Ccost) and the minimum average cost for collection (minavg.SP Ccost), i.e. avg.∆ SP Ccost = 100

* (avg.SP Ccost -minavg.SP Ccost)/minavg.SP Ccost; ∆avg.SP Dcost: percentage difference between the average cost for delivery (avg.SP Dcost) and the minimum average cost for delivery (minavg.SP Dcost), i.e. avg.∆ SP Dcost = 100 * (avg.SP Dcost -minavg.SP Dcost)/minavg.SP Dcost; ∆avg.Cost: percentage difference between the average total cost (avg.Cost) and the minimum average total cost (minavg.Cost), i.e. ∆avg.Cost = 100 * (avg.Costminavg.Cost)/minavg.Cost.

  .

	Strategy	∆avg.SP Ccost ∆avg.SP Dcost ∆avg.Cost avg.SP Ct(s) avg.SP Dt(s) avg.t(s)
	SP D inf inite → SP C	8.60	0.01	0.02	0.15	46.84	46.99
	SP D f inite balanced → SP C	8.55	0.01	0.00	0.15	54.27	54.42
	SP D f inite supplier based → SP C	8.71	0.00	0.04	0.16	50.59	50.75
	SP C not f ull truck → SP D	0.00	7.54	2.35	0.26	81.23	81.49
	SP C f ull truck → SP D	0.00	4.74	0.49	0.27	73.21	73.47
	SP C f ull truck customer based → SP D	0.00	4.49	0.33	0.27	74.96	75.23
	minimum average costs	331.92	711.99	1072.34	-	-	-

Table 2 :

 2 Average results on instance set S.

Table 3 :

 3 Strategy ∆avg.SP Ccost ∆avg.SP Dcost ∆avg.Cost ∆avg.SP Ccost ∆avg.SP Dcost ∆avg.Cost Average results on instance sets S S 1 and S S 2 .

	set		S S 1			S S 2
	SP D inf inite → SP C	45.36	0.00	6.55	100.57	0.00	9.78
	SP D f inite balanced → SP C	45.05	0.00	6.45	98.33	0.00	9.15
	SP D f inite supplier based → SP C	3.94	9.01	0.00	0.00	34.86	0.00
	SP C not f ull truck → SP D	0.00	17.57	4.27	0.00	34.86	0.00
	SP C f ull truck → SP D	0.00	13.44	1.65	0.00	34.89	0.01
	SP C f ull truck customer based → SP D	7.01	9.04	0.93	42.52	12.62	0.14
	minimum average costs	331.92	712.04	1121.17	376.85	712.08	1337.16

Results on sets S C

1 , S C 2 , S C 3 , and S C 4 are reported in Tables

Table 4 :

 4 Strategy ∆avg.SP Ccost ∆avg.SP Dcost ∆avg.Cost ∆avg.SP Ccost ∆avg.SP Dcost ∆avg.Cost Average results on instance sets S C 1 and S C 2 . Table 6 presents the results obtained on set S O where the quantities available at the suppliers are unbalanced. The results indicate that in this case, the algorithm SP C f ull truck customer based → SP D provides the lowest total cost. Hence, when the suppliers have unbalanced available quantities, Strategy ∆avg.SP Ccost ∆avg.SP Dcost ∆avg.Cost ∆avg.SP Ccost ∆avg.SP Dcost ∆avg.Cost

	Instance set		S C 1			S C 2
	SP D inf inite → SP C	28.61	0.00	3.24	25.47	0.00	2.78
	SP D f inite balanced → SP C	11.75	2.85	0.00	11.77	2.30	0.04
	SP D f inite supplier based → SP C	14.78	1.48	0.03	13.64	1.35	0.00
	SP C not f ull truck → SP D	0.00	14.62	4.05	0.00	12.82	3.15
	SP C f ull truck → SP D	0.00	10.11	1.14	0.00	8.42	0.33
	SP C f ull truck customer based → SP D	0.84	8.85	0.58	0.23	8.24	0.29
	minimum average costs	331.92	710.99	1102.21	331.92	690.85	1077.35

Table 5 :

 5 Average results on instance sets S C 3 and S C 4 .starting by solving the SPC in a sequential approach is the best choice.

	Strategy	∆avg.SP Ccost ∆avg.SP Dcost ∆avg.Cost
	SP D inf inite → SP C	112.24	0.00	9.06
	SP D f inite balanced → SP C	113.50	0.03	9.40
	SP D f inite supplier based → SP C	4.25	38.77	2.09
	SP C not f ull truck → SP D	0.00	45.59	4.68
	SP C f ull truck → SP D	0.00	43.39	3.49
	SP C f ull truck customer based → SP D	40.16	17.74	0.00
	minimum average costs	345.76	722.98	1335.83

Table 6 :

 6 Average results on instance set S O .

	The results on sets of instances S S add 1	, S S add 2	, S C add 1	and S C add 2	are reported in Tables 7, 8, 9 and
	10, respectively.
	SP D inf inite → SP C	10.70	0.01		0.23	0.04	52.45	52.48
	SP D f inite balanced → SP C	10.18	0.00		0.08	0.06	93.26	93.32
	SP D f inite supplier based → SP C	10.90	0.00		0.29	0.06	85.91	85.97
	SP C not f ull truck → SP D	0.00	8.29		2.75	0.45	134.97	135.43
	SP C f ull truck → SP D	0.00	4.54		0.20	0.46	107.30	107.76
	SP C f ull truck customer based → SP D	0.00	4.25		0.00	0.33	139.04	139.36
	minimum average costs	304.89	712.03	1047.15	-	-	-

Strategy ∆avg.SP Ccost ∆avg.SP Dcost ∆avg.Cost avg.SP Ct(s) avg.SP Dt(s) avg.t(s)

Table 7 :

 7 Average results on instance set S S add

1

.

  Strategy ∆avg.SP Ccost ∆avg.SP Dcost ∆avg.Cost avg.SP Ct(s) avg.SP Dt(s) avg.t(s)

	SP D inf inite → SP C	4.74	0.01	0.00	0.08	85.48	85.56
	SP D f inite balanced → SP C	4.86	0.00	0.03	0.07	93.44	93.51
	SP D f inite supplier based → SP C	4.78	0.00	0.01	0.07	88.58	88.65
	SP C not f ull truck → SP D	0.00	2.99	0.64	0.35	120.08	120.42
	SP C f ull truck → SP D	0.00	2.08	0.02	0.37	111.97	112.34
	SP C f ull truck customer based → SP D	0.00	2.18	0.09	0.39	113.24	113.63
	minimum average costs	308.52	712.03	1035.21	-	-	-

Table 8 :

 8 Average results on instance set S S add

	4.92	0.00	0.00	0.06	156.93	156.99

2 . Strategy ∆avg.SP Ccost ∆avg.SP Dcost ∆avg.Cost avg.SP Ct(s) avg.SP Dt(s) avg.t(s) SP D inf inite → SP C

Table 9 :

 9 Average results on instance set S C add

	Strategy	∆avg.SP Ccost ∆avg.SP Dcost ∆avg.Cost avg.SP Ct(s) avg.SP Dt(s) avg.t(s)
	SP D inf inite → SP C	7.09	0.00	0.00	0.20	617.93	618.13
	SP D f inite balanced → SP C	7.82	0.33	0.50	0.20	654.17	654.37
	SP D f inite supplier based → SP C	2.79	6.84	1.60	0.18	573.09	573.27
	SP C not f ull truck → SP D	0.00	12.06	3.03	0.75	1031.30	1032.04
	SP C f ull truck → SP D	0.00	9.66	1.79	0.76	853.73	854.49
	SP C f ull truck customer based → SP D	2.02	4.51	0.04	0.32	462.36	462.68
	minimum average costs	1384.20	1583.68	3066.04	-	-	-

1

.

Table 10 :

 10 Average results on instance set S C add 2

Table 11 :

 11 Summary of ∆avg.Cost from Tables

Table 12 :

 12 Comparison of the sequential approaches with results obtain from Cplex on F M C2DP (in 1 hour computation).

Table 14 :

 14 instance id |V C | |V S | |V D | |M| Supermarkets instances.

	1	188	61	5	6
	2	188	61	5	5
	3	188	61	5	6
	4	188	54	5	7
	5	188	45	5	5
	6	188	58	5	6
	7	188	61	5	8
	8	188	61	5	7
	9	188	61	5	7
	10	188	61	5	6
	Distribution center	Customer		Supplier (vegetables)	Supplier (fruits)

Table 15 :

 15 Detailed results for school canteens instances.

Table 16 :

 16 Detailed results for supermarkets.

Table 17 :

 17 Comparison of the results between separated and merged cases: solution cost.

			Base			SP D → SP C		SP C → SP DCanteens1st	SP C → SP DSupermarkets1st
	Instance	SPCcost	SPDcost	Cost	SPCcost	SPDcost	Cost	SPCcost	SPDcost	Cost	SPCcost	SPDcost	Cost
	merged1	5949.19	4787.02	10736.21	6526.92	2812.63	9339.55	2339.38	-	-	2339.38	5819.71	8159.09
	merged2	3513.41	7305.67	10819.08	6229.80	2770.40	9000.20	2216.94	-	-	2216.94	5259.22	7476.16
	merged3	4306.44	3979.17	8285.61	4564.18	2337.58	6901.77	1433.72	-	-	1433.72	3928.00	5361.72
	merged4	2163.38	6221.77	8385.15	4945.08	2184.41	7129.49	1486.66	-	-	1486.66	3844.91	5331.57
	merged5	4169.47	3287.29	7456.76	2623.92	3510.20	6134.12	1930.55	-	-	1930.55	4419.69	6350.24

Acknowledgments

This work is partially supported by supported by the CSC (China Scholarship Council) and by the ELSAT 2020 project. The authors thank Conseil Général de l'Isère and Chambre d'Agriculture de l'Isère for providing the case study instances.