# Optimization of a Two-Echelon Location Lot-Sizing Routing Problem with Deterministic Demand

Authors: Laila Kechmane; Benayad Nsiri; Azeddine Baalal
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

This paper aims to solve a multiperiod location lot-sizing routing problem with deterministic demand in a two-echelon network composed of a single factory, a set of potential depots, and a set of customers. Solving this problem involves making strategic decisions such as location of depots as well as operational and tactical decisions which include customers’ assignment to the open depots, vehicle routing organization, and inventory management. A mathematical model is presented to describe the problem and a genetic algorithm combined with a local search procedure is proposed to solve it and is tested over three sets of instances.


---

## Body

## 1. Introduction

The design of a distribution network comprises three major problems: facility location, vehicle routing, and inventory control, these problems belong to different categories of decisions, and researchers classify the supply chain decisions into strategic, tactical, and operational: strategic level decisions are fixed for long periods time, which could be years, such as location of facilities, tactical decisions are made for medium periods of time such as inventory management, and operational level concerns short-term decisions which includes distribution decisions.Recently, many researchers have studied the benefit of combining two decision levels into a single model; the inventory location problem (ILP) combines the facility location problem (FLP) and inventory management; many studies have been done on the different variants of ILP such as Daskin et al. [1], Shen [2], Ozsen et al. [3], Shen and Qi [4], Miranda and Garrido [5], and Melo et al. [6].Many papers in the literature studied the location routing problem (LRP) which combines the facility location problem and the vehicle routing problem (VRP); the importance of tackling them simultaneously is studied by Salhi and Rand [7]. The LRP consists in determining the optimal number of facilities, their location, allocation of customers to the open facilities, and the vehicle routing organization. This problem has been studied by many researchers such as Prins et al. [8], Prins et al. [9], Duhamel et al. [10], Benlenger [11], Baldacci et al. [12], Ting et al. [13], Contardo et al. [14], and Kechmane et al. [15]. A recent survey on this problem is presented by Prodhon [16].The inventory-routing problem (IRP) integrates inventory management and the vehicle routing problem, and the deterministic version of this problem has been studied by Archetti et al. [17], Oppen [18], Archetti et al. [19], Moin et al. [20], Coelho et al. [21], and Coelho and Laporte [22]. Adelman [23], Hvattum and Lokketangen [24], Hvattum et al. [25], and Mete and Zabinsky [26] studied the stochastic version of the problem. A survey on IRP is presented by Vidovic et al. [27]. Other papers in the literature integrate inventory, lot-sizing, and vehicle routing decisions such as Nananukul [28]; the author developed a reactive Tabu search procedure for solving a production-distribution supply chain and improved results using a path relinking strategy; Cetinkaya et al. [29] studied an integrated multiproduct inventory lot-sizing and vehicle routing problem and presented an iterative solution approach in which the problem is decomposed into inventory and routing subproblems; Chen and Sarker [30] established an integrated optimal model of inventory lot-sizing vehicle routing of multisupplier single-manufacturer with milk-run JIT delivery and solved it using an ant colony optimization algorithm; and Kechmane et al. [31] proposed a mathematical model to optimize transport cost and delivery lot-sizing in a single level logistic network and solved it using a MILP solver.Few studies in the literature consider the strategic, operational, and tactical level decisions simultaneously, yet the vehicle routing organization depends on inventory control problem, which in turn depends on decisions taken in the location-allocation phase. The problem with the aim of facilities location, vehicle routing organization, and inventory management is known as location-inventory-routing problem (LIRP); inventory may be considered at plants, at final customers, or at both of them. Miranda and Garrido [32] studied the effect of ignoring inventory decisions while designing a supply chain network and the importance of managing inventories to reduce the total costs.Liu and Lee [33] proposed a single product, multidepot location routing problem taking inventory control decisions into consideration where customers have stochastic demand and applied a two-phase heuristic method to solve the problem. Liu and Lin [34] divided the proposed problem by Liu and Lee [33] into a location-allocation problem and inventory-routing problem; they proposed a hybrid heuristic combining Tabu search with simulated annealing to solve the problem. Ambrossino and Scutella [35] proposed a linear programming model for the LIRP with deterministic demand where inventories must be managed at both plants and customers.Shen and Qi [4] modified a LIRP model proposed by Daskin et al. [1] and used Lagrangian relaxation to solve subproblems. Ahmadi-Javid and Azad [36] proposed a stochastic model to simultaneously optimize location, allocation, inventory, and routing decisions; they proposed a hybrid algorithm of Tabu search and simulated annealing. Hiassat and Diabat [37] proposed a multiperiod model formulated as Mixed Integer Program for the LIRP with deterministic demand for perishable product. A multiphase heuristic algorithm based on simulated annealing and ant colony system (ACS) is proposed by Ahmadi-Javid and Seddighi [38] to solve a location-routing-inventory model with multisource distribution networks.Guerrero et al. [39] proposed an algorithm for multiperiod LIRP with deterministic demand in a three-layer supply chain composed of a single supplier, potential depots, and customers; a hybrid heuristic and exact solution method are developed to solve the problem as well as an intensification phase to investigate the inventory and routing decision where the location and customers assignments are fixed and a dynamic lot-sizing problem is solved using a MIP solver. Nekooghadirli et al. [40] studied a biobjective location-routing-inventory model with multiperiod, multiproduct, stochastic demand and probabilistic travelling time among customers; their model aims to minimize the total cost and maximize the average time for delivering commodities to customers; and Zhang et al. [41] presented a hybrid metaheuristic combined with simulated annealing method to solve a LIRP in a two-echelon network composed of multiple capacitated depots and final customers.Genetic algorithm (GA) is a stochastic optimization method proposed by J. Holland (1962) and then developed by D. Goldberg (1989); it is inspired by the natural evolution in genetics where a population of individuals each represented as a chromosome and representing a solution is subject to selection, crossover, and mutation operators at each generation to breed a new generation.GA have been successfully applied to a variety of optimization problems including transport problems combining two decision levels; Abdelmaguid and Dessouky [42] developed a genetic algorithm approach to the integrated inventory distribution problem. A biased random key genetic algorithm approach is developed by Chan et al. [43] to solve the inventory-based multi-item lot-sizing problem. Rungreunganaun and Woarawichai [44] applied genetic algorithms to solve an inventory lot-sizing problem with supplier selection under storage space; the objective of their research is to calculate the optimal inventory lot-sizing suppliers and minimize the inventory cost. Prins et al. [8] proposed a memetic algorithm combined with population management, which is a technique developed by Sorensen and Sevaux [45], to solve a capacitated location routing problem; Park et al. [46] presented a GA for the vendor-managed inventory-routing problem with lost sales; Marinakis and Marinaki [47] presented a bilevel genetic algorithm and applied it to a real life location routing problem; a hybrid GA for the multiproduct multiperiod inventory-routing problem is presented by Moin et al. [20]; Liao et al. [48] used a nondominated sorting genetic algorithm (NSGA-II) to optimize a multiobjective location-inventory problem; and Kechmane et al. [49] developed a memetic algorithm to solve a capacitated location routing problem.Recently, some genetic algorithms have been developed to solve problems combining location, inventory and routing decisions; Forouzanfar et al. [50] used a GA to optimize the total cost for a LIRP in a supply chain with risk pooling, a hybrid genetic-simulated annealing algorithm is proposed by Li et al. [51] for the LIRP considering returns under e-supply chain environment, and Hiassat et al. [52] developed a GA approach for a LIRP with perishable products.This paper deals with a multiperiod Location lot-sizing routing problem (LLSRP) with deterministic demand that aims to design a two-echelon supply chain network consisting of potential depots supplied by a factory and facing deterministic nonconstant demands of customers. The objective is to determine the location of depots to open, to assign customers to the opened depots, to organize the vehicles routing, and to manage inventories at depots and customers by determining quantities to send to them during each period of the planning horizon so that the overall cost is minimized and customers’ demands are satisfied, such problem arises in many domains such as food distribution for supermarket chains, military operations, and pharmaceutical industry, to solve the LLSRP, and a hybrid genetic algorithm is developed. This paper is organized as follows: the description of the problem and a mathematical model are presented in Section2, in Section 3 components of the proposed algorithm are presented in detail, computational results are given in Section 4, and a conclusion is given in the last section.


## 2. Problem Description and Mathematical Formulation

LetG=(V,E,C) be a complete, weighted, and directed graph, V=I∪J is the set of nodes in the graph where I is the set of potential depots and J is the set of customers. E=i;j:i∈V,j∈V,i≠j is the set of arcs linking the different nodes in the graph and C=cij/i∈V,j∈V with cij being the cost of the trip from node i to node j. T is a discrete and finite planning horizon. Each depot i∈I has an opening cost Oi and an ordering cost ordi. Each node i∈I∪J has a storage capacity capi. Each customer is assigned to a single depot. A homogenous unlimited fleet of vehicles K is available. A vehicle might serve multiple customers during its tour but a customer is served by only one vehicle. Vehicles have a limited capacity Q and a cost of use F. Kit is the number of vehicles used from depot i fleet during the period t. Each vehicle ends its tour at the depot it starts from.Before presenting the mathematical model for the LLSRP, let the decision variables bepi=1 if the depot i is opened, lijtk=1 if the vehicle k crosses the arc (i,j)∈E on period t, and l′it=1 if the depot i is replenished on period t. l′′ij=1 if customer j is affected to depot i. xit is the delivery quantity received by depot i on period t. yijtk is the delivery quantity received by customer j from depot i in period t via the vehicle k. bit is the quantity needed by node i∈I∪J in period t. stkit is the available stock at node i∈I∪J at the end of time period t, stki0 represents the initial stock at node i∈I∪J. qitl is the cost of holding a unit from period t to period l at node i∈I∪J.(1)min∑i∈IOipi+∑i∈I∑t∈TFKit+∑i∈I∪J∑j∈I∪J∑k∈K∑t∈Tlijktcij+∑i∈I∑t∈Tordil′it+∑i∈I∑j∈J∑t∈T∑k∈Kyijtk-bjt+stkjt-1qjtt+1+∑i∈I∑t∈Txit-bit+stkit-1qitt+1subject to(2)bit=∑j∈J∑k∈Kyijtk∀i∈I∀t∈T(3)stkjt=∑i∈I∑k∈Kyijtkl′′ij-bjt+stkjt-1∀j∈J∀t∈T(4)stkit=xitl′it-bit+stkit-1∀i∈I∀t∈T(5)bjt≤stkjt-1+∑i∈I∑k∈Kyijtk∀j∈J∀t∈T(6)bit≤stkit-1+xit∀i∈I∀t∈T(7)stkit≤picapi∀i∈I∀t∈T(8)stkjt≤capj∀j∈J∀t∈T(9)∑j∈Jyijtk≤Q∀i∈I∀k∈K∀t∈T(10)∑i∈Il′′ij=1∀j∈J(11)l′′ij≤pi∀i∈I∀j∈J(12)∑j∈I∪Jlijtk-∑j∈I∪Jljitk=0∀i∈I∪J∀t∈T∀k∈K(13)∑i∈I∪J∑k∈Klijtk≤1∀j∈J∀t∈T(14)∑i∈I∪J∑k∈Kljitk≤1∀j∈J∀t∈T(15)∑i∈I∑j∈Jlijtk≤1∀t∈T∀k∈K(16)∑i∈S∑j∈Slijtk≤S-1∀k∈K∀t∈T∀S⊆J(17)∑h∈Jlihtk-∑h∈I∪Jh≠jlhjtk≤1+l′′ij∀i∈I∀j∈J∀k∈K∀t∈T(18)lijtk=0∀i,j∈I∀k∈K∀t∈Ti≠j(19)∑j∈J∑k∈Klijtk=Kit∀i∈I∀t∈T(20)Kit∈N∀i∈I∀t∈T(21)pi∈0,1∀i∈I(22)lijtk∈0,1∀i∈I∪J∀j∈I∪J∀k∈K∀t∈T(23)l′it∈0,1∀i∈I∀t∈T(24)l′′ij∈0,1∀i∈I∀j∈J(25)xit∈R+∀i∈I∀t∈T(26)yijtk∈R+∀i∈I∀j∈J∀t∈T∀k∈K(27)stkjt∈R+∀j∈I∪J∀t∈T(28)bjt∈R+∀j∈I∪J∀t∈TThe objective function (1) sums the depots opening costs, the vehicles’ cost of use, the total routing costs, the ordering costs for every depot, and the holding costs at customers and depots over the planning horizon.Constraints (2) define the depots’ need for every period. Inventory balance equations are presented by (3) and (4). Constraints (5) and (6) guarantee the satisfaction of customers and depots demand for every period. Equations (7) and (8) ensure that opened depots and customers storage capacities are respected. Equations (9) force the respect of vehicles capacity.Constraints (10) ensure that each customer is assigned to a single depot and constraints (11) ensure that if a customer is assigned to a depot, the latter is opened. Constraints (12) force vehicles to leave every node they visit. Constraints (13) and (14) guarantee that each customer is visited by one vehicle at most per period. Constraints (15) ensure that each vehicle performs one route per period at the most.Equations (16) are subtour elimination constraints, they guarantee the presence of a depot in every route. Constraint (17) links the vehicle routing variables and the assignment variables; it states that if a vehicle leaves a depot and visits a customer, then this customer must be assigned to the depot. Constraints (18) ensure that travels from a depot to another one are not allowed. Equations (19) provide the number of vehicles used from every depot fleet in every period. Finally (20)–(28) are standard integrality and nonnegativity constraints.


## 3. A Hybrid Genetic Algorithm for the Location Lot-Sizing Routing Problem

In order to solve the Location lot-sizing routing problem with deterministic demand, a hybrid genetic algorithm is proposed, and the different components of the algorithm are presented in the sequel.


### 3.1. Solution Representation

As mentioned earlier, in genetic algorithms, solutions are represented as chromosomes, this representation must be clearly defined; in the proposed algorithm, the encoding method for the location routing problem proposed by Prins et al. [8] is adopted; a chromosome consists of two parts; the first one relates to the depots; it indicates their status; if the gene corresponding to a depot is zero, it means that the depot is closed, else it contains the index of the first customer assigned to it. The second part of the chromosome indicates the set of customers assigned to each open depot. Figure 1 represents an example of a chromosome, the gene corresponding to depot 2 is zero, and this means that depot 2 is closed. The genes corresponding to depots 1 and 3 contain, respectively, the values 1 and 7, this means that both of them are open, and the sets of customers assigned to depots 1 and 3 are, respectively 4,2,6,8,1,10 and 3,9,7,5.Figure 1
A chromosome representation.


### 3.2. Initial Population

Initial population is composed of solutions obtained by InitialSol procedure presented in Algorithm1 as well as random solutions in order to better explore the solution space.Algorithm 1:Depots to open and customers’ assignment.
Procedure: InitialSol Input: Problem’ data values Output: Depots to open and customers’ assignment A r e t ← ⌀ repeat Select randomly an available depot d C d ← ⌀ V d ← J p d ← 1 repeat r ← arg ⁡ mi n j ∈ V d ⁡ { d d j / ∀ i ∈ I : l ′ ′ i j = 0 } if (Moy(Cd∪r)≤capd) then C d ← C d ∪ r l ′ ′ d r ← 1 A r e t ← A r e t ∪ r V d ← V d - r else V d ← V d - r end if until (Vd=⌀) until (Aret=J)As well as the adopted chromosome representation, InitialSol procedure allows determining depots to open and customers’ assignment to the open depots. Algorithm1 represents the steps of this procedure; as long as there are customers not yet affected to the open depots, the procedure randomly selects and opens a depot; the closest customer not yet assigned to a depot is selected. If the average demand of this customer and those assigned to the depot during the planning horizon does not exceed the storage capacity of the depot, he is assigned to the depot; else, this procedure is repeated until the possibility of adding a customer is verified for all the customers not yet assigned to a depot.FunctionMoy is defined as follows: (29)MoyCd=∑t∈T∑j∈CdbjtCardTwhere Cd represents the set of customers assigned to depot d.


### 3.3. Chromosome Decoding

Chromosomes, as well as InitialSol procedure, give the status of each depot and the set of customers assigned to it if it is open. In order to organize the vehicle routing, to manage the inventories at depots and customers over the planning horizon and to obtain a solution cost, two complementary procedures are proposed in the sequel.Once customers are assigned to the open depots, procedure SolOrg1 (Algorithm2) allows organizing the vehicles’ routing and determining quantities to send to each customer over the planning horizon. For each open depot, an available vehicle from its fleet starts its route by visiting the closest customer affected to the depot who needs to be replenished, i.e., his stock level does not respond to the need of the day; as long as the vehicle can serve, the closest customer to the last visited one, whose demand does not exceed the vehicle’s capacity, is added to the vehicle tour; once the vehicle’s capacity cannot serve more customers, it returns to the depot and another tour via another vehicle is organized in the same way. tmax represents the last day of the planning period and Dkt is the quantity that the vehicle k carries on day t, if this quantity is less than the vehicle’s capacity, in order to reduce the number of tours and the vehicles used, the vehicle left its departure depot fully loaded and the added quantity is sent to the customers, visited during the vehicle tour, whose the storage cost is the lowest and the storage capacity allows receiving this quantity.Algorithm 2:Routing organization and customers’ inventories management.
Procedure: SolOrg1 Input: Problem’ data values Output: Routing organization and customers’ inventory management S ← 0 for each  i∈I/pi=1  do S ← S + O i + s t k i 0 ∗ q i ( 0 ) 1 t ← 1 while  (t≺tmax)  do b i t ← 0 C ′ i ← C i repeat Select an available vehicle k S ← S + F D k t ← 0 C ′ ′ i ← C ′ i r ← i repeat r ′ ← arg ⁡ mi n j ∈ C '' i ⁡ { d r j / s t k j t - 1 ≤ b j t } if  (capk≥Dkt+br′t-stkr′t-1)  then D k t ← D k t + b r ′ t - s t k r ′ t - 1 l r r ′ t k ← 1 S ← S + c r r ′ r ← r ′ C ′ i ← C ′ i - { r ′ } C ′ ′ i ← C ′ ′ i - { r ′ } else C ′ ′ i ← C ′ ′ i - { r ′ } end if until  (C′′i=⌀) S ← S + c r i b i t ← b i t + D k t if  (Dkt≺Q)  then j ′ ← arg ⁡ mi n j ∈ C i ⁡ { q j t ( t + 1 ) / l d j t k = 1 ⁡ ⁡, d ∈ J ∪ i   a n d   s t k j t + Q - D k t ≤ c a p j } S ← S + ( Q - D k t ) ∗ q j ′ t ( t + 1 ) b i t ← b i t + Q - D k t end if until  (C′i=⌀) t ← t + 1 end while end for for each  j∈J  do S ← S + s t k j 0 q j ( 0 ) 1 + s t k j t m a x q j ( t m a x ) t m a x + 1 end for return SAs mentioned in Section2, every time a depot needs to be replenished there is an ordering cost to consider. Procedure SolOrg2 (Algorithm 3) aims to reduce this cost by checking if the ordering of a depot for every period could be distributed over the periods before; if it is feasible and the storage cost is less than the ordering cost, the total cost of the solution would be reduced. In addition to organizing the vehicle routing and the replenishment schedule, these procedures try to reduce the depots’ ordering costs.Algorithm 3:Depots’ inventory management.
Procedure: SolOrg2 Input: Problem’ data values, solution costS Output: Depots’ inventory management for each  i∈I/pi=1  do t ← 2 repeat S ′ ← 0 L ← 0 t ′ ← t - 1 while(L≺bit and t′≠0) do L ← L + c a p i - s t k i t ′ S ′ ← S ′ + c a p i - s t k i t ′ q i t ′ t t ′ ← t ′ - 1 end while if(L≥bitandordi≻S′)then S ← S + S ′ end if t ← t + 1 until  (t=tmax) end for for each  i∈I/pi=1  do t ← 1 while  (t≺tmax)  do if  (bit≻stkit-1)  then l ′ i t ← 1 S ← S + o r d i end if t ← t + 1 end while end for return the total cost of the solution,S


### 3.4. Selection and Crossover

Parents are selected using the binary tournament method; the first one is obtained by selecting randomly two chromosomes among the individuals of the best half of the population and the best one is kept. The second parent is selected with the same method but from the whole population except the first selected parent.A new chromosome “child” is obtained by crossing the selected parents; crossover for the depot sequence works as on a sequence of binary; a positive cut-off point less than the sequence length is generated randomly. The depot sequence of the child receives the part before the cut point of the first parent and the part after the cut point of the second parent. The classical order crossover is used to obtain the customers sequence; two cut-off points less than the sequence length are generated randomly; the part between the two cut points in the first parent is copied in the child in the same order and in the same position; then the second parent is scanned from the second cut point to the end and from the beginning to the second cut point while copying each element not yet in the child. Figure2 illustrates this operator.Figure 2
Example of chromosomes crossover.


### 3.5. Chromosome Repair

In order to check the validity of the obtained chromosome, the first step is to verify the existence of 1 in the depot sequence; this means that in the worst case all customers have been assigned to the same depot; then it shall be ensured that the average demand of customers assigned to a depot over the planning horizon does not exceed its storage capacity; this is verified by means of function Moy defined earlier.If the average demand of customers assigned to a depot exceeds its capacity, the last assigned customer to the depot is reassigned to another depot of which capacity allows serving him. Algorithm4 describes steps of this procedure.Algorithm 4:Chromosome repairing procedure.
Procedure: Chromrepair Input: A chromosome Output: Valid chromosome Findi∈I/ds(i)=1, if it fails, find the first closed depot i ′  and  ds(i′)←1 for each  i∈I/ds(i)≠0 if  (Moy(Ci)≻capi)  then repeat j ←last customer assigned to i i ′ ← arg ⁡ mi n d ∈ I ⁡ { d i d / M o y ( C d ∪ j ) ≺ c a p d } C i ← C i - j C i ′ ← C i ′ + j if  ({i′}=⌀)  then Find  i′′/ds(i′′)=0 C i ← C i - j C i ′ ′ ← C i ′ ′ + j end if until  (Moy(Ci)≤capi) end if end for


### 3.6. Local Search

In each generation of the hybrid genetic algorithm, a local search procedure is applied with a probabilitypls to improve the solution obtained by the crossover operator by exploring its neighborhood; Algorithm 5 describes steps of the proposed procedure, six moves are used, three of them operate on depots, and the others operate on customers. The proposed moves are presented in the sequel.Algorithm 5:The local search procedure.
Procedure: LocalSearch Input: A solutionS Output:Sbest S b e s t ← S;  S′←S;  S′′←S N C D ← S  neighborhood generated using CloseDepot move N R E ← S  neighborhood generated using RouteExchange move N R T ← S  neighborhood generated using RouteTrans move S ′ ← arg ⁡ min ⁡ { C o s t ( S ) / S ∈ N C D ∪ N R E ∪ N R T } if (Cost(S′)≺Cost(Sbest)) then S ′ ′ ← S ′ else S ′ ′ ← S b e s t end if N R T E ← S ′ ′  neighborhood generated using CustExchange move N R T T ← S ′ ′  neighborhood generated using CustTrans move N R R ← S ′ ′  neighborhood generated using CustRev move S m i n ← arg ⁡ min ⁡ { C o s t ( S ) / S ∈ N R T E ∪ N R T T ∪ N R R } if  (Cost(Smin)≺Cost(S′′))  then S b e s t ← S m i n else S b e s t ← S ′ ′ end if ReturnSbest  and  Cost(Sbest)CloseDepot. This move consists in closing a depot and reallocates its customers according to their proximity to other depots. Figure 3 illustrates this move. The steps of CloseDepot are as follows:(a)
Randomly select a depoti.(b)
Randomly select a customerj from Ci.(c)
LetDj be the set of open depots able to satisfy customer j need for the planning horizon.(d)
Find in the setDj the closest depot i′ to j.(e)
Assign customerj to depot i′.(f)
IfDj is empty, open a closed depot and assign j to it.(g)
Deletej from Ci.(h)
IfCi is empty close depot i, else go to (b).(i)
Build routes allocated to the concerned depots and determine the suitable inventory for both depot and customers using procedures SolOrg1 and SolOrg2.Figure 3
Example of a CloseDepot move.RouteExchange. Two depots exchange customers of two routes and tours and inventories are reorganized. An example of this move is given in Figure 4; the steps of RouteExchange are as follows:(a)
Randomly select two open depots.(b)
Randomly select two routes, one from each selected depot.(c)
Using functionMoy, check if changing customers of selected routes between depots is feasible, if yes change assignation of those customers, else exit from this move.(d)
Build routes allocated to the two depots and determine suitable inventories for both depots and customers using procedures SolOrg1 and SolOrg2.Figure 4
Example of a RouteExchange move.RouteTrans. A route’s customers are transferred to another depot that may be open or closed. Figure 5 presents an example of this move. The procedure of RouteTrans is as follows:(a)
Randomly select an opened depot.(b)
Randomly select a route from the selected depot.(c)
Randomly select another depot.(d)
Assign customers of the route selected in (b) to the depot selected in (c); if the depot is not able to serve the customers, go to (c).(e)
Build routes allocated to the two depots and determine suitable inventories for both depots and customers using procedures SolOrg1 and SolOrg2.Figure 5
Example of a RouteTrans move.Remark. In the proposed moves, to check the ability of a depot to serve a set of customers, function Moy defined in Section 3.2 is used.CustExchange. Two routes starting from the same depot over the same period exchange two customers. This move is shown in Figure 6; the procedure of CustExchange is as follows:(a)
Randomly choose a period.(b)
Randomly choose an open depot.(c)
Randomly choose two routes from the selected depot.(d)
Randomly select two customers, one in each route.(e)
If both selected customers can be exchanged without violating capacity of each route, exchange positions of the customers; else go to (d).Figure 6
Example of a CustExchange move.CustTrans. A customer is transferred from the route to which he belongs to another one starting from the same depot over the same period. This move is illustrated in Figure 7 and its steps are as follows:(a)
Select a period randomly.(b)
Select an open depot randomly.(c)
Choose randomly two routes 1 and 2 from the depot selected in (b).(d)
Select one customer on route 1.(e)
If capacity of route 2 allows, transfer the selected customer to it; else go to (c).Figure 7
Example of a CustTrans move.CustRev. A subsequence of customers in a route is inversed. Figure 8 illustrates this move and its steps are as follows:(a)
Choose a period randomly.(b)
Choose an open depot randomly.(c)
Choose randomly a route from the selected depot in (b).(d)
Choose randomly a subsequence of the route selected in (c) and inverse the order in which customers are visited.Figure 8
Example of a CustRev move.FunctionCost returns the cost of a solution, i.e., the value returned by procedures SolOrg1 and SolOrg2, when moves operating on depots are used. When moves operating on customers are used, the cost of a solution is modified by considering the applied change.


### 3.7. The Hybrid Genetic Algorithm

The overall hybrid genetic algorithm is presented in Algorithm6, the algorithm is obtained by gathering the components previously presented, and it starts by generating an initial population which includes solutions obtained by InitialSol procedure as well as random solutions in order to better explore the solution space.Algorithm 6:The overall hybrid genetic algorithm.
Procedure: HybridGeneticAlgorithm Input: Problem Data Output: Best solutionPbest t ← 0 Generate initial populationP(0)  using InitialSol procedure and random chromosomes while  (t≺max⁡gen)  do Select parents  p1  and  p2  using binary tournament fromP(t) Cross  p1  and  p2  to obtain child  c Repair c using Chromrepair procedure if  (c∈P(t))  then Repeat selection and crossover else Apply LocalSearch Procedure to c with a probabilitypls  to obtain  c′ end if if  (c′∉P(t))  then c ′  replaces the worst solution in  P(t) end if P ( t + 1 ) ← P ( t ) t ← t + 1 end while Return the best solPbest  in  P(max⁡gen)At each iteration, parents selected using binary tournament method are crossed to obtain a chromosome child which is repaired using Chromrepair procedure; if the current population already contains the obtained chromosome, the selection and the crossover are repeated; else, LocalSearch procedure is applied to the chromosome child to improve it; it is applied once to each offspring with a probabilitypls in order to avoid being trapped in a local optimum; if the obtained chromosome does not belong to the population, it replaces the worst chromosome of it. Once the maximum number of iterations is reached, the algorithm stops and returns the best solution of the last obtained population.


## 3.1. Solution Representation

As mentioned earlier, in genetic algorithms, solutions are represented as chromosomes, this representation must be clearly defined; in the proposed algorithm, the encoding method for the location routing problem proposed by Prins et al. [8] is adopted; a chromosome consists of two parts; the first one relates to the depots; it indicates their status; if the gene corresponding to a depot is zero, it means that the depot is closed, else it contains the index of the first customer assigned to it. The second part of the chromosome indicates the set of customers assigned to each open depot. Figure 1 represents an example of a chromosome, the gene corresponding to depot 2 is zero, and this means that depot 2 is closed. The genes corresponding to depots 1 and 3 contain, respectively, the values 1 and 7, this means that both of them are open, and the sets of customers assigned to depots 1 and 3 are, respectively 4,2,6,8,1,10 and 3,9,7,5.Figure 1
A chromosome representation.


## 3.2. Initial Population

Initial population is composed of solutions obtained by InitialSol procedure presented in Algorithm1 as well as random solutions in order to better explore the solution space.Algorithm 1:Depots to open and customers’ assignment.
Procedure: InitialSol Input: Problem’ data values Output: Depots to open and customers’ assignment A r e t ← ⌀ repeat Select randomly an available depot d C d ← ⌀ V d ← J p d ← 1 repeat r ← arg ⁡ mi n j ∈ V d ⁡ { d d j / ∀ i ∈ I : l ′ ′ i j = 0 } if (Moy(Cd∪r)≤capd) then C d ← C d ∪ r l ′ ′ d r ← 1 A r e t ← A r e t ∪ r V d ← V d - r else V d ← V d - r end if until (Vd=⌀) until (Aret=J)As well as the adopted chromosome representation, InitialSol procedure allows determining depots to open and customers’ assignment to the open depots. Algorithm1 represents the steps of this procedure; as long as there are customers not yet affected to the open depots, the procedure randomly selects and opens a depot; the closest customer not yet assigned to a depot is selected. If the average demand of this customer and those assigned to the depot during the planning horizon does not exceed the storage capacity of the depot, he is assigned to the depot; else, this procedure is repeated until the possibility of adding a customer is verified for all the customers not yet assigned to a depot.FunctionMoy is defined as follows: (29)MoyCd=∑t∈T∑j∈CdbjtCardTwhere Cd represents the set of customers assigned to depot d.


## 3.3. Chromosome Decoding

Chromosomes, as well as InitialSol procedure, give the status of each depot and the set of customers assigned to it if it is open. In order to organize the vehicle routing, to manage the inventories at depots and customers over the planning horizon and to obtain a solution cost, two complementary procedures are proposed in the sequel.Once customers are assigned to the open depots, procedure SolOrg1 (Algorithm2) allows organizing the vehicles’ routing and determining quantities to send to each customer over the planning horizon. For each open depot, an available vehicle from its fleet starts its route by visiting the closest customer affected to the depot who needs to be replenished, i.e., his stock level does not respond to the need of the day; as long as the vehicle can serve, the closest customer to the last visited one, whose demand does not exceed the vehicle’s capacity, is added to the vehicle tour; once the vehicle’s capacity cannot serve more customers, it returns to the depot and another tour via another vehicle is organized in the same way. tmax represents the last day of the planning period and Dkt is the quantity that the vehicle k carries on day t, if this quantity is less than the vehicle’s capacity, in order to reduce the number of tours and the vehicles used, the vehicle left its departure depot fully loaded and the added quantity is sent to the customers, visited during the vehicle tour, whose the storage cost is the lowest and the storage capacity allows receiving this quantity.Algorithm 2:Routing organization and customers’ inventories management.
Procedure: SolOrg1 Input: Problem’ data values Output: Routing organization and customers’ inventory management S ← 0 for each  i∈I/pi=1  do S ← S + O i + s t k i 0 ∗ q i ( 0 ) 1 t ← 1 while  (t≺tmax)  do b i t ← 0 C ′ i ← C i repeat Select an available vehicle k S ← S + F D k t ← 0 C ′ ′ i ← C ′ i r ← i repeat r ′ ← arg ⁡ mi n j ∈ C '' i ⁡ { d r j / s t k j t - 1 ≤ b j t } if  (capk≥Dkt+br′t-stkr′t-1)  then D k t ← D k t + b r ′ t - s t k r ′ t - 1 l r r ′ t k ← 1 S ← S + c r r ′ r ← r ′ C ′ i ← C ′ i - { r ′ } C ′ ′ i ← C ′ ′ i - { r ′ } else C ′ ′ i ← C ′ ′ i - { r ′ } end if until  (C′′i=⌀) S ← S + c r i b i t ← b i t + D k t if  (Dkt≺Q)  then j ′ ← arg ⁡ mi n j ∈ C i ⁡ { q j t ( t + 1 ) / l d j t k = 1 ⁡ ⁡, d ∈ J ∪ i   a n d   s t k j t + Q - D k t ≤ c a p j } S ← S + ( Q - D k t ) ∗ q j ′ t ( t + 1 ) b i t ← b i t + Q - D k t end if until  (C′i=⌀) t ← t + 1 end while end for for each  j∈J  do S ← S + s t k j 0 q j ( 0 ) 1 + s t k j t m a x q j ( t m a x ) t m a x + 1 end for return SAs mentioned in Section2, every time a depot needs to be replenished there is an ordering cost to consider. Procedure SolOrg2 (Algorithm 3) aims to reduce this cost by checking if the ordering of a depot for every period could be distributed over the periods before; if it is feasible and the storage cost is less than the ordering cost, the total cost of the solution would be reduced. In addition to organizing the vehicle routing and the replenishment schedule, these procedures try to reduce the depots’ ordering costs.Algorithm 3:Depots’ inventory management.
Procedure: SolOrg2 Input: Problem’ data values, solution costS Output: Depots’ inventory management for each  i∈I/pi=1  do t ← 2 repeat S ′ ← 0 L ← 0 t ′ ← t - 1 while(L≺bit and t′≠0) do L ← L + c a p i - s t k i t ′ S ′ ← S ′ + c a p i - s t k i t ′ q i t ′ t t ′ ← t ′ - 1 end while if(L≥bitandordi≻S′)then S ← S + S ′ end if t ← t + 1 until  (t=tmax) end for for each  i∈I/pi=1  do t ← 1 while  (t≺tmax)  do if  (bit≻stkit-1)  then l ′ i t ← 1 S ← S + o r d i end if t ← t + 1 end while end for return the total cost of the solution,S


## 3.4. Selection and Crossover

Parents are selected using the binary tournament method; the first one is obtained by selecting randomly two chromosomes among the individuals of the best half of the population and the best one is kept. The second parent is selected with the same method but from the whole population except the first selected parent.A new chromosome “child” is obtained by crossing the selected parents; crossover for the depot sequence works as on a sequence of binary; a positive cut-off point less than the sequence length is generated randomly. The depot sequence of the child receives the part before the cut point of the first parent and the part after the cut point of the second parent. The classical order crossover is used to obtain the customers sequence; two cut-off points less than the sequence length are generated randomly; the part between the two cut points in the first parent is copied in the child in the same order and in the same position; then the second parent is scanned from the second cut point to the end and from the beginning to the second cut point while copying each element not yet in the child. Figure2 illustrates this operator.Figure 2
Example of chromosomes crossover.


## 3.5. Chromosome Repair

In order to check the validity of the obtained chromosome, the first step is to verify the existence of 1 in the depot sequence; this means that in the worst case all customers have been assigned to the same depot; then it shall be ensured that the average demand of customers assigned to a depot over the planning horizon does not exceed its storage capacity; this is verified by means of function Moy defined earlier.If the average demand of customers assigned to a depot exceeds its capacity, the last assigned customer to the depot is reassigned to another depot of which capacity allows serving him. Algorithm4 describes steps of this procedure.Algorithm 4:Chromosome repairing procedure.
Procedure: Chromrepair Input: A chromosome Output: Valid chromosome Findi∈I/ds(i)=1, if it fails, find the first closed depot i ′  and  ds(i′)←1 for each  i∈I/ds(i)≠0 if  (Moy(Ci)≻capi)  then repeat j ←last customer assigned to i i ′ ← arg ⁡ mi n d ∈ I ⁡ { d i d / M o y ( C d ∪ j ) ≺ c a p d } C i ← C i - j C i ′ ← C i ′ + j if  ({i′}=⌀)  then Find  i′′/ds(i′′)=0 C i ← C i - j C i ′ ′ ← C i ′ ′ + j end if until  (Moy(Ci)≤capi) end if end for


## 3.6. Local Search

In each generation of the hybrid genetic algorithm, a local search procedure is applied with a probabilitypls to improve the solution obtained by the crossover operator by exploring its neighborhood; Algorithm 5 describes steps of the proposed procedure, six moves are used, three of them operate on depots, and the others operate on customers. The proposed moves are presented in the sequel.Algorithm 5:The local search procedure.
Procedure: LocalSearch Input: A solutionS Output:Sbest S b e s t ← S;  S′←S;  S′′←S N C D ← S  neighborhood generated using CloseDepot move N R E ← S  neighborhood generated using RouteExchange move N R T ← S  neighborhood generated using RouteTrans move S ′ ← arg ⁡ min ⁡ { C o s t ( S ) / S ∈ N C D ∪ N R E ∪ N R T } if (Cost(S′)≺Cost(Sbest)) then S ′ ′ ← S ′ else S ′ ′ ← S b e s t end if N R T E ← S ′ ′  neighborhood generated using CustExchange move N R T T ← S ′ ′  neighborhood generated using CustTrans move N R R ← S ′ ′  neighborhood generated using CustRev move S m i n ← arg ⁡ min ⁡ { C o s t ( S ) / S ∈ N R T E ∪ N R T T ∪ N R R } if  (Cost(Smin)≺Cost(S′′))  then S b e s t ← S m i n else S b e s t ← S ′ ′ end if ReturnSbest  and  Cost(Sbest)CloseDepot. This move consists in closing a depot and reallocates its customers according to their proximity to other depots. Figure 3 illustrates this move. The steps of CloseDepot are as follows:(a)
Randomly select a depoti.(b)
Randomly select a customerj from Ci.(c)
LetDj be the set of open depots able to satisfy customer j need for the planning horizon.(d)
Find in the setDj the closest depot i′ to j.(e)
Assign customerj to depot i′.(f)
IfDj is empty, open a closed depot and assign j to it.(g)
Deletej from Ci.(h)
IfCi is empty close depot i, else go to (b).(i)
Build routes allocated to the concerned depots and determine the suitable inventory for both depot and customers using procedures SolOrg1 and SolOrg2.Figure 3
Example of a CloseDepot move.RouteExchange. Two depots exchange customers of two routes and tours and inventories are reorganized. An example of this move is given in Figure 4; the steps of RouteExchange are as follows:(a)
Randomly select two open depots.(b)
Randomly select two routes, one from each selected depot.(c)
Using functionMoy, check if changing customers of selected routes between depots is feasible, if yes change assignation of those customers, else exit from this move.(d)
Build routes allocated to the two depots and determine suitable inventories for both depots and customers using procedures SolOrg1 and SolOrg2.Figure 4
Example of a RouteExchange move.RouteTrans. A route’s customers are transferred to another depot that may be open or closed. Figure 5 presents an example of this move. The procedure of RouteTrans is as follows:(a)
Randomly select an opened depot.(b)
Randomly select a route from the selected depot.(c)
Randomly select another depot.(d)
Assign customers of the route selected in (b) to the depot selected in (c); if the depot is not able to serve the customers, go to (c).(e)
Build routes allocated to the two depots and determine suitable inventories for both depots and customers using procedures SolOrg1 and SolOrg2.Figure 5
Example of a RouteTrans move.Remark. In the proposed moves, to check the ability of a depot to serve a set of customers, function Moy defined in Section 3.2 is used.CustExchange. Two routes starting from the same depot over the same period exchange two customers. This move is shown in Figure 6; the procedure of CustExchange is as follows:(a)
Randomly choose a period.(b)
Randomly choose an open depot.(c)
Randomly choose two routes from the selected depot.(d)
Randomly select two customers, one in each route.(e)
If both selected customers can be exchanged without violating capacity of each route, exchange positions of the customers; else go to (d).Figure 6
Example of a CustExchange move.CustTrans. A customer is transferred from the route to which he belongs to another one starting from the same depot over the same period. This move is illustrated in Figure 7 and its steps are as follows:(a)
Select a period randomly.(b)
Select an open depot randomly.(c)
Choose randomly two routes 1 and 2 from the depot selected in (b).(d)
Select one customer on route 1.(e)
If capacity of route 2 allows, transfer the selected customer to it; else go to (c).Figure 7
Example of a CustTrans move.CustRev. A subsequence of customers in a route is inversed. Figure 8 illustrates this move and its steps are as follows:(a)
Choose a period randomly.(b)
Choose an open depot randomly.(c)
Choose randomly a route from the selected depot in (b).(d)
Choose randomly a subsequence of the route selected in (c) and inverse the order in which customers are visited.Figure 8
Example of a CustRev move.FunctionCost returns the cost of a solution, i.e., the value returned by procedures SolOrg1 and SolOrg2, when moves operating on depots are used. When moves operating on customers are used, the cost of a solution is modified by considering the applied change.


## 3.7. The Hybrid Genetic Algorithm

The overall hybrid genetic algorithm is presented in Algorithm6, the algorithm is obtained by gathering the components previously presented, and it starts by generating an initial population which includes solutions obtained by InitialSol procedure as well as random solutions in order to better explore the solution space.Algorithm 6:The overall hybrid genetic algorithm.
Procedure: HybridGeneticAlgorithm Input: Problem Data Output: Best solutionPbest t ← 0 Generate initial populationP(0)  using InitialSol procedure and random chromosomes while  (t≺max⁡gen)  do Select parents  p1  and  p2  using binary tournament fromP(t) Cross  p1  and  p2  to obtain child  c Repair c using Chromrepair procedure if  (c∈P(t))  then Repeat selection and crossover else Apply LocalSearch Procedure to c with a probabilitypls  to obtain  c′ end if if  (c′∉P(t))  then c ′  replaces the worst solution in  P(t) end if P ( t + 1 ) ← P ( t ) t ← t + 1 end while Return the best solPbest  in  P(max⁡gen)At each iteration, parents selected using binary tournament method are crossed to obtain a chromosome child which is repaired using Chromrepair procedure; if the current population already contains the obtained chromosome, the selection and the crossover are repeated; else, LocalSearch procedure is applied to the chromosome child to improve it; it is applied once to each offspring with a probabilitypls in order to avoid being trapped in a local optimum; if the obtained chromosome does not belong to the population, it replaces the worst chromosome of it. Once the maximum number of iterations is reached, the algorithm stops and returns the best solution of the last obtained population.


## 4. Computational Experiments

In order to test the proposed hybrid genetic algorithm, three sets of instances for the LLSRP are created, the number of customers in instances of the first and second sets is, respectively,5 and 8 and the last set contains instances with 12 customers and others with 16 customers. This section reports the results obtained by the proposed algorithm. The number of potential depots m∈{3,5}, the number of customers n∈{5,8,12,16}, and the number of periods p∈{3,5,7}; a period refers to a week; orders are made once a week by depots and customers. Depots opening costs and replenishment costs vary for each depot. All vehicles have the same capacity and the same cost of use. Depots, as well as customers, have different storage costs and different capacities.After preliminary testingmax⁡gen is fixed to 500, and the population size is 100. Procedures are implemented in C language on an Acer Aspire ONE D255 1.00 GHz machine, running Windows 7 Starter Edition.To investigate the effect of local search probability on solutions’ quality and the computational time, the algorithm is tested with two local search probability values; Table1 provides comparison between the obtained results; the first column corresponds to the names of the instances; they are labeled as n-m-p; the name of each one indicates its size. The second column corresponds, for each instance, to the best solution obtained by the hybrid genetic algorithm using two local search probability values: 0.3 and 0.5.Table 1
Comparison of HGA results on LLSRP instances.
Ins tan ces BKS Cost 0.3 Gap (%) CPU (s) Cost 0.5 Gap (%) CPU (s)  3 – 5 – 3 68734.4 68734.4 0 32.4 68734.4 0 38.4 3 – 5 – 5 78976.8 78976.8 0 30 78976.8 0 44.9 3 – 5 – 7 78905 78905 0 39.6 79045.8 0.18 56.3 3 – 8 – 3 85674.7 87163.4 1.74 50.4 85674.7 0 59.9 3 – 8 – 5 86785.9 86943.3 0.18 68.3 86785.9 0 70.5 3 – 8 – 7 86889.6 86889.6 0 49.4 87004.8 0.13 81.9 5 – 8 – 3 85543.1 86065.8 0.61 70.1 85543.1 0 96.8 5 – 8 – 5 86675.7 87529.5 0.98 88.2 86675.7 0 105.4 5 – 8 – 7 85548.9 86170.8 0.73 83.3 85548.9 0 140.8 5 – 12 – 3 97249.7 97249.7 0 127.5 97496 0.25 198.5 5 – 12 – 5 99082.7 99082.7 0 180.7 100165.3 1.09 210.6 5 – 12 – 7 101536.6 101734.4 0.19 178.3 101536.6 0 201.7 5 – 16 – 3 110764.1 110764.1 0 207.7 110928.3 0.15 309.6 5 – 16 – 5 130785.3 131707.1 0.7 253.6 130785.3 0 283 5 – 16 – 7 131786.9 131929.8 0.11 361.9 131786.9 0 317.4 Average 94329.29 94656.43 0.35 121.43 94445.9 0.12 147.71Columns three to eight indicate, for each of the probability values and for each instance, the obtained solution cost, the gap with BKS, and the computation time in seconds. The gap is obtained by calculatingGap=Cost-BKS/BKS∗100.The algorithm found the same solutions for two instances with3 potential depots and 5 customers. The average gap for HGA when pls=0.3 is 0.35%, the average computational time is 121.43 seconds and the algorithm found 7 of the best solutions with this local search probability value. Better solutions are found when pls=0.5; the average gap to BKS is 0.12%, the average computational time is 147.71 seconds, and 10 of the best solutions are found with this probability value, this can be explained by the fact that locale search procedure is applied to more chromosomes, consequently more solutions have been improved, and this also explains why the computational time is higher when pls=0.5.Table2 provides a comparison of solutions’ quality for each set of instances as a well as the computational time for both local search probability values.Table 2
Comparison of HGA results on each LLSRP instance size.
p l s = 0.3 p l s = 0.5  Ins tan ces  size Average cost Average Gap (%) Average CPU (s) Average cost Average Gap (%) Average CPU (s)  1st set 75538.73 0 34.03 75585.67 0.06 46.53  2nd set 86793.73 0.71 68.28 86205.52 0.02 92.55  3rd set 112077.97 0.17 218.28 112116.4 0.25 253.47The algorithm found the best solutions for the first and third sets of instances withpls=0.3; however the difference in the average gaps is small; their respective gaps are 0.06% and 0.8%. For the second set, the best solutions are found when pls=0.5 and the difference in the average gaps is 0.69%. On average, the algorithm provides better results when pls=0.5 and for all sets of instances, the average computational time when pls=0.5 is higher than pls=0.3.


## 5. Conclusions

In this paper, a mixed integer linear programming model is proposed for a multiperiod location lot-sizing routing problem in a two-echelon network; the objective is to determine the set of depots to open, allocation of customers to open depots, the vehicle routing organization, quantities to ship to depots, and those to ship from depots to customers in every period in a way that minimizes the total distribution cost and satisfies customers need. To solve this problem, a genetic algorithm combined with a local search procedure is proposed; it is tested over three sets of instances with two local search probability values. In the proposed mathematical model, customers have a deterministic demand, for future research, it would be interesting to consider uncertain demand of customers, and also, some other constraints can be considered such as time window to visit the final customers and a heterogeneous fleet of vehicles at depots.



---

*Source: 2745437-2018-06-14.xml*