# A Two-Stage Algorithm for the Closed-Loop Location-Inventory Problem Model Considering Returns in E-Commerce

Authors: Yanhui Li; Mengmeng Lu; Bailing Liu
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Facility location and inventory control are critical and highly related problems in the design of logistics system for e-commerce. Meanwhile, the return ratio in Internet sales was significantly higher than in the traditional business. Focusing on the existing problem in e-commerce logistics system, we formulate a closed-loop location-inventory problem model considering returned merchandise to minimize the total cost which is produced in both forward and reverse logistics networks. To solve this nonlinear mixed programming model, an effective two-stage heuristic algorithm named LRCAC is designed by combining Lagrangian relaxation with ant colony algorithm (AC). Results of numerical examples show that LRCAC outperforms ant colony algorithm (AC) on optimal solution and computing stability. The proposed model is able to help managers make the right decisions under e-commerce environment.


---

## Body

## 1. Introduction

The increasing progress of information and prevalence of internet in the 21st century has forced the e-commerce to develop in a world-wide range. In 2012, B2C e-commerce sales grew 21.1% to top $1 trillion for the first time in history in the whole world [1]. Comparing with traditional commerce, customers are more liable to return goods under e-commerce environment. Note that many customer returns online account for 35% of original orders [2, 3]. Therefore, logistics systems as an important support system in e-commerce need to be adjusted and improved. To adapt to the reality of e-commerce market environment, it is critical to conduct the research on the reverse logistics network and highly integrated logistics process.Facility location and inventory control are critical problems in the design of logistics system. There is much previous work in these two areas. In fact, there is a mutually dependent relationship among these problems in logistics system. Comprehensive optimizing and logistics activities management should be based on this relationship [4]. According to this idea, besides location allocation problem and inventory optimization, the location-inventory problem (LIP) starts to be researched.Many papers about the LIP are studied deeply and have made some abundant achievements. In recent years, intelligent algorithms and heuristic algorithm have been used to solve LIP model [5–7]. In the reverse logistics research field, LIP attracts researchers’ attention. Lieckens and Vandaele [8] applied a queuing mode in reverse logistics network to solve the facility location problem while considering the impact of inventory costs. Srivastava [9] established a reverse logistics network optimization model to optimize the location-allocation problem and capacity decisions, and he used heuristic algorithm to solve the model. Wang et al. [10] proposed a location-inventory policy in Chinese B2C electronic market as a bilevel programming model. Tancrez et al. [11] studied the LIP in three-level supply chain networks including reverse logistics; they developed an iterative heuristics approach to solve the model. Diabat et al. [12] built a mixed integer nonlinear programming (MINLP) model to minimize the total reverse logistics cost by finding out the number and location of initial collection point and centralized return center considering the inventory cost. Two solution approaches, namely, genetic algorithm (GA) and artificial immune system, are implemented and compared. However, research on the LIP of closed-loop logistics system is limited. Sahyouni et al. [13] designed three generic facility location models that account for the integrated distribution and collection of products in the closed-loop supply chain networks; the authors described a Lagrangian relaxation-based solution algorithm to solve the models. Easwaran and Üster [14] offered a mixed integer linear programming model to optimize the total cost that consists of location, processing, and transportation costs of the multimerchandise in closed-loop supply chains; they introduced a heuristics solution approach that combines Benders decomposition and tabu search to solve the model. Abdallah et al. [15] presented the uncapacitated closed-loop location-inventory model; a sensitivity analysis for different parameters of the model reveals that the value of recovered products is a major factor in the economic feasibility of the closed-loop network. For dealing with returned merchandise without quality problems in e-commerce, Li et al. [16] developed a practical LIP model with considering the vehicle routing under e-supply chain environment and provided a new hybrid heuristic algorithm to solve this model.Previous researches on the closed-loop logistics system optimization mainly focus on the minimization of the total cost of the network. To our best knowledge, few researches on manufacturing/remanufacturing system consider returns and concept of green logistics recycling in logistics network. Since customers may be dissatisfied with merchandise and return it, the cost of processing returns, the cost of inventory and shipping, order time, and size are changed. Furthermore, research on the LIP with return of closed-loop logistics system is limited.The aim of this study is to develop a practical LIP model with the consideration of returns in e-commerce and provide a new two-stage heuristics algorithm. To our best knowledge, this work is the first step to introduce returns into the LIP in e-commerce, which makes it become more practical. We also provide an effective algorithm named Lagrangian relaxation combined with ant colony algorithm (LRCAC) to solve this model. Lagrangian relaxation algorithm (LR) can obtain a near-optimal solution by analyzing the upper bound and lower bound of objective function. But its effectiveness mainly relies on the performance of subgradient optimization algorithm. On the other hand, AC has great ability of local searching. If there is an appropriate initial solution, the performance of AC will be good. To adopt their strong points while overcoming their weak points, we combine the two algorithms. Results of numerical examples show that LRCAC outperforms ant colony algorithm (AC) on optimal solution and computing stability.The remainder of the paper is structured as follows. In Section2, a nonlinear integrated programming model about LIP considering returns in e-commerce is designed. Section 3 proposes the heuristic algorithm named LRCAC based on Lagrangian relaxation and ant colony algorithm. Section 4 shows and analyzes the results of different experiments. Section 5 concludes this paper and discusses the future research directions.


## 2. Problem and Mathematic Model

### 2.1. Problem Description

In e-commerce, some returned merchandise has a high integrity, which makes it usually not in need of being repaired and can reenter the sales channels after simply repackaging [17]. Some returned goods have quality problems; they have to be sent back to factory for repair. Therefore, we merge the recycling center with distribution center as merchandise centers (MCs) with an additional inspection function. MC is responsible for distributing normal goods to the sale regions; meanwhile the returned goods are collected to MCs. After inspecting at MCs, the returned goods with quality problems are sent back to factory, and the other returned goods are resalable as normal goods after simply repackaging. Customers can choose to return goods in e-commerce, and quantity of the returns is uncertain [18]. However, for a certain sale region (SR), the quantity of the returns can be usually seen as stochastic variable.The objective of this paper is to determine the quantity, locations, order times, and order size of MCs in the closed-loop logistics network in e-commerce. The final target is to minimize the total cost and improve the efficiency of logistics operations. The involved decisions are as follows: (1) location decisions, the optimal number of MCs, and their locations; (2) allocation decisions, the corresponding service relationship between MCs, and sale regions; (3) inventory decisions, the optimal order times, and order size.


### 2.2. Assumptions

(1) There is a single type of merchandise; (2) the capability of factory is unlimited; (3) the capability of MCs is unlimited; (4) the demand and return of each sale region comply with the normal distribution, whose parameters are fixed; (5) the demands of regions are mutually independent; (6) returned merchandise is inspected and repackaged at MCs.


### 2.3. Notations

Sets
I:
Set of SR;
J:
Set of candidate MC.Constants
fj:
Fixed cost (annual) administrative and operational cost ofMCj;
tj:
Shipping cost per unit of merchandise between factory andMCj;
cij:
The delivering cost per unit of merchandise betweenSRi and MCj;
hj:
The inventory holding cost per unit of merchandise per year atMCj;
pj:
Ordering cost per time atMCj;
lj:
Lead time atMCj;
μi:
Mean of annual demand atSRi;
σi2:
Variance of annual demand atSRi;
zαj:
Standard normal deviate such thatp(z≤zαj)=αj;
αj:
Service level ofMCj;
ri:
The quantity of return atSRi;
w:
The probability of quality problem product in return goods;
d:
Repacking cost per unit returned merchandise.Decision Variables
Xj:
1, if the candidateMCj is selected as a MC and 0 otherwise;
Yij:
1, ifSRi is served by MCj and 0 otherwise;
Qj:
Optimal order size atMCj;
Nj:
Optimal order times atMCj.


### 2.4. Model Formula

(
1) Location Cost. The construction cost of MCj is given by ∑j=1nfjXj.(
2) Inventory Cost. The total annual inventory cost consists of ordering cost and inventory holding cost, according to literatures [19, 20]; it is given by pjNj+hj(Dj/2Nj).(
3) Safety Stock Cost. The demand in the lead time lj at MCj is lj∑i∈Iσi2Yij, so the safety stock is zαjlj∑i∈Iσi2Yij, and the safety stock cost is given by hjzαjlj∑i∈Iσi2Yij.(
4) Transportation Cost. The transportation cost consists of cost from factory to MC, cost from MC to customer region for forward logistics, cost from customer region to MC, and cost from MC to factory for reverse logistics. So, the transportation cost is given by ∑j∈Jtj∑i∈I[μi-ri(1-w)]XjYij+∑j∈J∑i∈IcijwriXj+∑j∈J∑i∈ItjwriXj+∑j∈J∑i∈IcijμiYij.(
5) Repacking Cost. The returned goods without quality problems need to be repacked before reentering to sale channel, so the repacking cost is given by ∑j∈J∑i∈Id(1-w)riYij.To sum up, the location-inventory model with returned merchandise (RLIP) is(1)min⁡Z=∑j∈J(lj∑i∈Iσi2YijfjXj+pjNjXj+hjDj2NjXjiiiiiiiiiiiiiiiiiiiii+hjzαjlj∑i∈Iσi2Yij)&iiiiiiiiiiii+∑j∈Jtj∑i∈I[μi-ri(1-w)]XjYij&iiiiiiiiiiii+∑j∈J∑i∈IcijwriXj+∑j∈J∑i∈ItjwriXj&iiiiiiiiiiii+∑j∈J∑i∈IcijμiYij+∑j∈J∑i∈Id(1-w)riYij,
s.t. 								(2)∑j∈JYij=1,i∈I,(3)Yij-Xj≤0,i∈I,j∈J,(4)Xj={0,1},j∈J,(5)Yij={0,1},i∈I,j∈J,(6)Nj≥0,j∈J,(7)Qj≥0,j∈J.The objective function (1) is to minimize the system’s total cost. Constraint (2) ensures that each sale region must be assigned to a MC. Constraint (3) stipulates that the assignment can only be made to the selected MC. Constraints (4) and (5) are standard integrality constraints. Constraints (6) and (7) are nonnegative constraints.


## 2.1. Problem Description

In e-commerce, some returned merchandise has a high integrity, which makes it usually not in need of being repaired and can reenter the sales channels after simply repackaging [17]. Some returned goods have quality problems; they have to be sent back to factory for repair. Therefore, we merge the recycling center with distribution center as merchandise centers (MCs) with an additional inspection function. MC is responsible for distributing normal goods to the sale regions; meanwhile the returned goods are collected to MCs. After inspecting at MCs, the returned goods with quality problems are sent back to factory, and the other returned goods are resalable as normal goods after simply repackaging. Customers can choose to return goods in e-commerce, and quantity of the returns is uncertain [18]. However, for a certain sale region (SR), the quantity of the returns can be usually seen as stochastic variable.The objective of this paper is to determine the quantity, locations, order times, and order size of MCs in the closed-loop logistics network in e-commerce. The final target is to minimize the total cost and improve the efficiency of logistics operations. The involved decisions are as follows: (1) location decisions, the optimal number of MCs, and their locations; (2) allocation decisions, the corresponding service relationship between MCs, and sale regions; (3) inventory decisions, the optimal order times, and order size.


## 2.2. Assumptions

(1) There is a single type of merchandise; (2) the capability of factory is unlimited; (3) the capability of MCs is unlimited; (4) the demand and return of each sale region comply with the normal distribution, whose parameters are fixed; (5) the demands of regions are mutually independent; (6) returned merchandise is inspected and repackaged at MCs.


## 2.3. Notations

Sets
I:
Set of SR;
J:
Set of candidate MC.Constants
fj:
Fixed cost (annual) administrative and operational cost ofMCj;
tj:
Shipping cost per unit of merchandise between factory andMCj;
cij:
The delivering cost per unit of merchandise betweenSRi and MCj;
hj:
The inventory holding cost per unit of merchandise per year atMCj;
pj:
Ordering cost per time atMCj;
lj:
Lead time atMCj;
μi:
Mean of annual demand atSRi;
σi2:
Variance of annual demand atSRi;
zαj:
Standard normal deviate such thatp(z≤zαj)=αj;
αj:
Service level ofMCj;
ri:
The quantity of return atSRi;
w:
The probability of quality problem product in return goods;
d:
Repacking cost per unit returned merchandise.Decision Variables
Xj:
1, if the candidateMCj is selected as a MC and 0 otherwise;
Yij:
1, ifSRi is served by MCj and 0 otherwise;
Qj:
Optimal order size atMCj;
Nj:
Optimal order times atMCj.


## 2.4. Model Formula

(
1) Location Cost. The construction cost of MCj is given by ∑j=1nfjXj.(
2) Inventory Cost. The total annual inventory cost consists of ordering cost and inventory holding cost, according to literatures [19, 20]; it is given by pjNj+hj(Dj/2Nj).(
3) Safety Stock Cost. The demand in the lead time lj at MCj is lj∑i∈Iσi2Yij, so the safety stock is zαjlj∑i∈Iσi2Yij, and the safety stock cost is given by hjzαjlj∑i∈Iσi2Yij.(
4) Transportation Cost. The transportation cost consists of cost from factory to MC, cost from MC to customer region for forward logistics, cost from customer region to MC, and cost from MC to factory for reverse logistics. So, the transportation cost is given by ∑j∈Jtj∑i∈I[μi-ri(1-w)]XjYij+∑j∈J∑i∈IcijwriXj+∑j∈J∑i∈ItjwriXj+∑j∈J∑i∈IcijμiYij.(
5) Repacking Cost. The returned goods without quality problems need to be repacked before reentering to sale channel, so the repacking cost is given by ∑j∈J∑i∈Id(1-w)riYij.To sum up, the location-inventory model with returned merchandise (RLIP) is(1)min⁡Z=∑j∈J(lj∑i∈Iσi2YijfjXj+pjNjXj+hjDj2NjXjiiiiiiiiiiiiiiiiiiiii+hjzαjlj∑i∈Iσi2Yij)&iiiiiiiiiiii+∑j∈Jtj∑i∈I[μi-ri(1-w)]XjYij&iiiiiiiiiiii+∑j∈J∑i∈IcijwriXj+∑j∈J∑i∈ItjwriXj&iiiiiiiiiiii+∑j∈J∑i∈IcijμiYij+∑j∈J∑i∈Id(1-w)riYij,
s.t. 								(2)∑j∈JYij=1,i∈I,(3)Yij-Xj≤0,i∈I,j∈J,(4)Xj={0,1},j∈J,(5)Yij={0,1},i∈I,j∈J,(6)Nj≥0,j∈J,(7)Qj≥0,j∈J.The objective function (1) is to minimize the system’s total cost. Constraint (2) ensures that each sale region must be assigned to a MC. Constraint (3) stipulates that the assignment can only be made to the selected MC. Constraints (4) and (5) are standard integrality constraints. Constraints (6) and (7) are nonnegative constraints.


## 3. Solution Approach

On the one hand, Lagrangian relaxation algorithm (LR) is used to solve the complex optimization problem very often. It can obtain a near-optimal solution by analyzing the upper bound and lower bound of objective function. But its effectiveness mainly relies on the performance of subgradient optimization algorithm. The speed of convergence becomes more and more slow with the increasing of the number of iterations. On the other hand, AC has great ability of local searching. If there is an appropriate initial solution, the performance of AC will be good. To adopt their strong points while overcoming their weak points, we design a two-stage algorithm. In the first stage, we use LR algorithm to get a near-optimum solution. In the second stage, let the solution obtained from the first stage be the initial solution; we use AC to further improve it.The abstract idea of solution approach is described as follows. Firstly, we give the formula for solving optimal order quantityQj and optimal order times Nj, which also rely on the decision variables Xj and Yij. Secondly, we use LR algorithm to get a near-optimal solution by computing the lower bound and upper bound of objective function. Then, let the near-optimum solution obtained from LR be the initial solution; we use AC to further improve it.


### 3.1. Finding the Optimal Order Quantity and Optimal Order Times

In the model (1)–(7), the decision variable Nj only has appeared in the objective function. Also, the objective function is convex for Nj>0. Consequently, we can obtain the optimal value of Nj by taking the derivative of the objective function with respect to Nj as Nj=hjDj/2pjXj, where Dj=∑i∈I[μi-ri(1-w)]Yij.As we know the optimal order quantityQj=Dj/Nj, so there is
(8)Qj=DjNj=DjhjDj/2pj=2pjDjhj=2pj∑i∈I[μi-ri(1-w)]Yijhj.


### 3.2. Transforming the Objective Function

In order to apply the LR algorithm, we transform the objective function as linear teams and nonlinear teams separately. The objective function can be rearranged as follows:(9)min⁡Z=∑j∈J[fj+(tj+cij)∑i∈Iwri]Xjiiiiiiiiiiiii+∑j∈J(pjNj+hjDj2Nj)Xjiiiiiiiiiiiii+∑j∈J∑i∈I[cijμi+d(1-w)riiiiiiiiiiiiiiiiiiiiiiiiiiii+tjμi-tjri(1-w)]Yijiiiiiiiiiiiii+∑j∈Jhjzαjlj∑i∈Iσi2Yijmin⁡Z=∑j∈J(fj′Xj+∑i∈Icij′Yij+hj′Xj+πj∑i∈Iσi2Yij),
where fj′=fj+(tj+cij)∑i∈Iwri, cij′=cijμi+d(1-w)ri+tjμi-tjri(1-w), hj′=pjNj+hj(Dj/2Nj), and πj=hjzαjlj.


### 3.3. Lagrangian Relaxation

#### 3.3.1. Finding a Lower Bound

To solve this problem, we intend to use Lagrangian relaxation embedded in branch and bound. In particular, we relax constraint (2) to obtain the following Lagrangian dual problem:
(10)max⁡λmin⁡Z⟶∑j∈J(fj′Xj+∑i∈Icij′Yij+hj′Xjiiiiiiiiiiiiiiiiiiiiiiiiiiiii+πj∑i∈Iσi2Yij)+λi∑i∈I(1-∑j∈JYij)iiiiiiiiiiiiiiiiiiii=∑j=1n(fj′Xj+∑i∈I(cij′-λi)Yijiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii+hj′Xj+πj∑i∈Iσi2Yij)+∑i∈Iλis.t.(3)–(7).For fixed values of the Lagrange multipliersλi, we want to minimize (10) over the location variables Xj and the assignment variables Yij. We separate the linear teams and nonlinear teams.(1)
For eachMCj,   let Vj=fj′+∑i∈Imin⁡(0,cij′-λi)+hj′, and let
(11)Xj={1Vj≤00Vj>0.
If all Vj values are positive, we identify the smallest positive Vj and set the corresponding Xj = 1. The assignment variables are then easy to determine, setting as follows:
(12)Yij={1Xj=1,cij′-λi≤00otherwise.(2)
However, the presence of the nonlinear terms makes finding an appropriate value ofVj difficult. So, we need to solve a subproblem as the following form for each candidate MCj:
(13)SP(j):Vj′=min⁡∑i∈IbiZi+∑i∈IφiZiiiiiiiiiiiiiiiiiiiiiis.t.Zi∈{0,1},i∈I,
where bi=cij′-λi, φi=πj2σi2≥0.In (13), we use Zi to substitute Yij.The solution of subproblem SP(j) refers to literature [19]; the solution of (10) is the summary of SP(j) and fj′. To get the lower bound, we need to find the optimal Lagrange multipliers. We do so using a standard subgradient optimization procedure as illustrated in literatures [21, 22]. The optimal value of (10) is a lower bound of the objective function (1).


#### 3.3.2. Finding an Upper Bound

We find an upper bound as follows.We initially fix the MC locations at those sites for whichXj=1 in the current Lagrangian solution. Then we assign SR to MCs in a two-phased process.S
t
e
p
1. For each SRi, for which ∑j∈JYij≥1, we assign the SRi to the MCj for which Yij=1 and that increases the least cost based on the assignments made so far.S
t
e
p
2. We process SRi, for which ∑j∈JYij=0; we assign each SR to the open MC which increases the least total cost based on the assignments made so far.Hence, for these SRs, we consider all possible assignments to open MCs, and the cost of this stage is the upper bound.


### 3.4. Ant Colony Clustering

According to the clustering behavior of ant colony, we set the clustering probabilitypijk(t) to represent the probability of the SRi and clustering center j at time t. The formula of pijk(t) is shown as follows:
(14)pijk(t)={τijαηijβ∑Tubks(t)=0τisαηsjβ,Tubkj(t)=0;0,otherwise,
where Tubkj(t)=0 represents that ant k can cluster SRi in next step; τijα is the amount of pheromone deposited for transition from state i to j; α is the parameter used to control the influence of τijα; ηijβ is the desirability of state transition i and j; β is the parameter of controlling the influence of ηijβ; dij is the distance from i to j.And the following relationship exists:(15)ηij={1dij,ifdij≠0,1,ifdij=0.


### 3.5. Algorithm Step

The integral two-stagealgorithm steps are shown below.S
t
e
p
0. We give the formula for solving Qj and Nj, which also rely on the decision variables Xj and Yij;First StageS
t
e
p
1. Transform the objective function as linear teams and nonlinear teams separately.S
t
e
p
2. Find the lower bound of objective function by using the LR.S
t
e
p
3. Find the upper bound of objective function by using the LR.S
t
e
p
4. Select the solution whose value is equal or approximately equal to the average value of the lower bound and upper bound as near-optimum solution.Second StageS
t
e
p
5. Let the near-optimum solution be the initial solution of AC.S
t
e
p
6. Initialize the tabu search matrix Tub(t), which is used to record the served SRs in the time [t,t+1]. Additionally, the Tub(t) is a 0-1 matrix, Tubki(t) = 1, and SRi is tabooed; Tubki(t) = 0; SRi is free.S
t
e
p
7. Set the MCj as the ant nest zj. Ant k selects a SRi to its ant nest zj with pijk(t) and taboos the SR. If Tubki(t) is full, go to Step 8; else repeat Step 7.S
t
e
p
8. If all the SRs are clustered to MC, the Tubki(t) updates to null matrix and goes to Step 9; else go to Step 6.S
t
e
p
9. Update the amount of pheromone τij(t+h)=ρτij(t)+Δτij,Δτij=∑k=1mΔτijk and record the optimal solution.S
t
e
p
10. If the conditions of convergence are meeting, terminate the procedure and output the optimal solution; else remove the MC of the least SRs and go to Step 6.The flowchart for our algorithm is shown in Figure1.Figure 1
The working process of the integral two-stage algorithm.


## 3.1. Finding the Optimal Order Quantity and Optimal Order Times

In the model (1)–(7), the decision variable Nj only has appeared in the objective function. Also, the objective function is convex for Nj>0. Consequently, we can obtain the optimal value of Nj by taking the derivative of the objective function with respect to Nj as Nj=hjDj/2pjXj, where Dj=∑i∈I[μi-ri(1-w)]Yij.As we know the optimal order quantityQj=Dj/Nj, so there is
(8)Qj=DjNj=DjhjDj/2pj=2pjDjhj=2pj∑i∈I[μi-ri(1-w)]Yijhj.


## 3.2. Transforming the Objective Function

In order to apply the LR algorithm, we transform the objective function as linear teams and nonlinear teams separately. The objective function can be rearranged as follows:(9)min⁡Z=∑j∈J[fj+(tj+cij)∑i∈Iwri]Xjiiiiiiiiiiiii+∑j∈J(pjNj+hjDj2Nj)Xjiiiiiiiiiiiii+∑j∈J∑i∈I[cijμi+d(1-w)riiiiiiiiiiiiiiiiiiiiiiiiiiii+tjμi-tjri(1-w)]Yijiiiiiiiiiiiii+∑j∈Jhjzαjlj∑i∈Iσi2Yijmin⁡Z=∑j∈J(fj′Xj+∑i∈Icij′Yij+hj′Xj+πj∑i∈Iσi2Yij),
where fj′=fj+(tj+cij)∑i∈Iwri, cij′=cijμi+d(1-w)ri+tjμi-tjri(1-w), hj′=pjNj+hj(Dj/2Nj), and πj=hjzαjlj.


## 3.3. Lagrangian Relaxation

### 3.3.1. Finding a Lower Bound

To solve this problem, we intend to use Lagrangian relaxation embedded in branch and bound. In particular, we relax constraint (2) to obtain the following Lagrangian dual problem:
(10)max⁡λmin⁡Z⟶∑j∈J(fj′Xj+∑i∈Icij′Yij+hj′Xjiiiiiiiiiiiiiiiiiiiiiiiiiiiii+πj∑i∈Iσi2Yij)+λi∑i∈I(1-∑j∈JYij)iiiiiiiiiiiiiiiiiiii=∑j=1n(fj′Xj+∑i∈I(cij′-λi)Yijiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii+hj′Xj+πj∑i∈Iσi2Yij)+∑i∈Iλis.t.(3)–(7).For fixed values of the Lagrange multipliersλi, we want to minimize (10) over the location variables Xj and the assignment variables Yij. We separate the linear teams and nonlinear teams.(1)
For eachMCj,   let Vj=fj′+∑i∈Imin⁡(0,cij′-λi)+hj′, and let
(11)Xj={1Vj≤00Vj>0.
If all Vj values are positive, we identify the smallest positive Vj and set the corresponding Xj = 1. The assignment variables are then easy to determine, setting as follows:
(12)Yij={1Xj=1,cij′-λi≤00otherwise.(2)
However, the presence of the nonlinear terms makes finding an appropriate value ofVj difficult. So, we need to solve a subproblem as the following form for each candidate MCj:
(13)SP(j):Vj′=min⁡∑i∈IbiZi+∑i∈IφiZiiiiiiiiiiiiiiiiiiiiiis.t.Zi∈{0,1},i∈I,
where bi=cij′-λi, φi=πj2σi2≥0.In (13), we use Zi to substitute Yij.The solution of subproblem SP(j) refers to literature [19]; the solution of (10) is the summary of SP(j) and fj′. To get the lower bound, we need to find the optimal Lagrange multipliers. We do so using a standard subgradient optimization procedure as illustrated in literatures [21, 22]. The optimal value of (10) is a lower bound of the objective function (1).


### 3.3.2. Finding an Upper Bound

We find an upper bound as follows.We initially fix the MC locations at those sites for whichXj=1 in the current Lagrangian solution. Then we assign SR to MCs in a two-phased process.S
t
e
p
1. For each SRi, for which ∑j∈JYij≥1, we assign the SRi to the MCj for which Yij=1 and that increases the least cost based on the assignments made so far.S
t
e
p
2. We process SRi, for which ∑j∈JYij=0; we assign each SR to the open MC which increases the least total cost based on the assignments made so far.Hence, for these SRs, we consider all possible assignments to open MCs, and the cost of this stage is the upper bound.


## 3.3.1. Finding a Lower Bound

To solve this problem, we intend to use Lagrangian relaxation embedded in branch and bound. In particular, we relax constraint (2) to obtain the following Lagrangian dual problem:
(10)max⁡λmin⁡Z⟶∑j∈J(fj′Xj+∑i∈Icij′Yij+hj′Xjiiiiiiiiiiiiiiiiiiiiiiiiiiiii+πj∑i∈Iσi2Yij)+λi∑i∈I(1-∑j∈JYij)iiiiiiiiiiiiiiiiiiii=∑j=1n(fj′Xj+∑i∈I(cij′-λi)Yijiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii+hj′Xj+πj∑i∈Iσi2Yij)+∑i∈Iλis.t.(3)–(7).For fixed values of the Lagrange multipliersλi, we want to minimize (10) over the location variables Xj and the assignment variables Yij. We separate the linear teams and nonlinear teams.(1)
For eachMCj,   let Vj=fj′+∑i∈Imin⁡(0,cij′-λi)+hj′, and let
(11)Xj={1Vj≤00Vj>0.
If all Vj values are positive, we identify the smallest positive Vj and set the corresponding Xj = 1. The assignment variables are then easy to determine, setting as follows:
(12)Yij={1Xj=1,cij′-λi≤00otherwise.(2)
However, the presence of the nonlinear terms makes finding an appropriate value ofVj difficult. So, we need to solve a subproblem as the following form for each candidate MCj:
(13)SP(j):Vj′=min⁡∑i∈IbiZi+∑i∈IφiZiiiiiiiiiiiiiiiiiiiiiis.t.Zi∈{0,1},i∈I,
where bi=cij′-λi, φi=πj2σi2≥0.In (13), we use Zi to substitute Yij.The solution of subproblem SP(j) refers to literature [19]; the solution of (10) is the summary of SP(j) and fj′. To get the lower bound, we need to find the optimal Lagrange multipliers. We do so using a standard subgradient optimization procedure as illustrated in literatures [21, 22]. The optimal value of (10) is a lower bound of the objective function (1).


## 3.3.2. Finding an Upper Bound

We find an upper bound as follows.We initially fix the MC locations at those sites for whichXj=1 in the current Lagrangian solution. Then we assign SR to MCs in a two-phased process.S
t
e
p
1. For each SRi, for which ∑j∈JYij≥1, we assign the SRi to the MCj for which Yij=1 and that increases the least cost based on the assignments made so far.S
t
e
p
2. We process SRi, for which ∑j∈JYij=0; we assign each SR to the open MC which increases the least total cost based on the assignments made so far.Hence, for these SRs, we consider all possible assignments to open MCs, and the cost of this stage is the upper bound.


## 3.4. Ant Colony Clustering

According to the clustering behavior of ant colony, we set the clustering probabilitypijk(t) to represent the probability of the SRi and clustering center j at time t. The formula of pijk(t) is shown as follows:
(14)pijk(t)={τijαηijβ∑Tubks(t)=0τisαηsjβ,Tubkj(t)=0;0,otherwise,
where Tubkj(t)=0 represents that ant k can cluster SRi in next step; τijα is the amount of pheromone deposited for transition from state i to j; α is the parameter used to control the influence of τijα; ηijβ is the desirability of state transition i and j; β is the parameter of controlling the influence of ηijβ; dij is the distance from i to j.And the following relationship exists:(15)ηij={1dij,ifdij≠0,1,ifdij=0.


## 3.5. Algorithm Step

The integral two-stagealgorithm steps are shown below.S
t
e
p
0. We give the formula for solving Qj and Nj, which also rely on the decision variables Xj and Yij;First StageS
t
e
p
1. Transform the objective function as linear teams and nonlinear teams separately.S
t
e
p
2. Find the lower bound of objective function by using the LR.S
t
e
p
3. Find the upper bound of objective function by using the LR.S
t
e
p
4. Select the solution whose value is equal or approximately equal to the average value of the lower bound and upper bound as near-optimum solution.Second StageS
t
e
p
5. Let the near-optimum solution be the initial solution of AC.S
t
e
p
6. Initialize the tabu search matrix Tub(t), which is used to record the served SRs in the time [t,t+1]. Additionally, the Tub(t) is a 0-1 matrix, Tubki(t) = 1, and SRi is tabooed; Tubki(t) = 0; SRi is free.S
t
e
p
7. Set the MCj as the ant nest zj. Ant k selects a SRi to its ant nest zj with pijk(t) and taboos the SR. If Tubki(t) is full, go to Step 8; else repeat Step 7.S
t
e
p
8. If all the SRs are clustered to MC, the Tubki(t) updates to null matrix and goes to Step 9; else go to Step 6.S
t
e
p
9. Update the amount of pheromone τij(t+h)=ρτij(t)+Δτij,Δτij=∑k=1mΔτijk and record the optimal solution.S
t
e
p
10. If the conditions of convergence are meeting, terminate the procedure and output the optimal solution; else remove the MC of the least SRs and go to Step 6.The flowchart for our algorithm is shown in Figure1.Figure 1
The working process of the integral two-stage algorithm.


## 4. Computational Experiments and Algorithm Analysis

### 4.1. Computational Experiment

We refer to the logistics network of companyK in Hubei province of China as an example. We convert the latitude and longitude coordinates of some cities in Hubei province and the central meridian to Xi'an 80 geographic coordinate. They are shown in Tables 1 and 2, in which the values represent the actual kilometers. And other parameters’ values are as follows: randomly generate the values between 100 and 160 as the μi, and assume that the σi2 is equal to μi, tj=1,pj=2,hj=1,lj=7 (day), αj=97.5%, w=0.2,    and d=2.Table 1
Parameters of MCs.
MC
Coordinate (km)
Fixed construction cost (Yuan)
Wuhan (j1)
(3342, 38529)
50
Xiangyang (j2)
(3322, 37609)
45
Xiaogan (j3)
(3533, 38491)
40
Yichang (j4)
(3397, 37528)
45
Jingzhou (j5)
(3356, 37619)
40
Huanggang (j6)
(3369, 38583)
35Table 2
Parameters of SRs.
SR
Coordinate (km)
Demand (unit)
Wuhan (i1)
(3342, 38529)
673
Xiangyang (i2)
(3322, 37609)
514
Xiaogan (i3)
(3533, 38491)
500
Yichang (i4)
(3397, 37528)
465
Jingzhou (i5)
(3356, 37619)
520
Huanggang (i6)
(3369, 38583)
440
Huangshi (i7)
(3342, 38604)
360
Shiyan (i8)
(3614, 37480)
400
Suizhou (i9)
(3468, 38361)
350
Xianning (i10)
(3305, 38527)
400
Enshi (i11)
(3271, 37357)
410
Jingmen (i12)
(3433, 37613)
510
Ezhou (i13)
(3362, 38583)
400Based on MATLAB 7.0 platform, we programmed the LRCAC algorithm and run it 30 times on the computer (CPU: Intel Core2 P7570 @2.26 GHz 2.27 GHz; RAM: 2.0 GB; OS: Windows 7); the optimal result is in Table3.Table 3
Optimal results.
Number of MCs
N (unit)
Q (unit)
The SRs assigned to MC
j
1
2
1410
i
1,i3, i6, i7, i10, i13
j
2
2
930
i
2, i8, i9
j
4
2
642
i
4, i11
j
5
4
776
i
5, i12The optimal cost is 224965 yuan, and logistics network is shown in Figure2.Figure 2
The logistics network obtained by LRCAC.For comparison, we programmed AC algorithm in the same platform and run 30 times on the same computer. The optimal objective function values of these two algorithms are shown in Table4.Table 4
Statistical results of optimal objective function value of two algorithms.
Max
Min
Mean
Standard deviation
Coefficient of variation
AC
263678
235791
244118
135673
0.56
LRCAC
231104
224965
230092
93876
0.41The two optimization trends of the two algorithms are shown in Figures3 and 4.Figure 3
Trends of optimal objective function value by LRCAC.Figure 4
Trends of optimal objective function value by AC.The fluctuation curves of optimal objective function in 30 times are shown in Figures5 and 6, respectively.Figure 5
Fluctuation curve of total cost by LRCAC algorithm.Figure 6
Fluctuation curve of total cost by AC.We can see that the LRCAC algorithm can converge more quickly than AC from Figures3 and 4. Moreover, LRCAC has better stability than AC, which can be easily found from Table 4 and Figures 5 and 6.


### 4.2. Algorithms Analysis

In this section, all the data in our experiments come from LRP database of the University of Aveiro [23]. A series of experiments show that LRCAC is more efficient and stable than AC. Results of numerical example in Section 4.1 show that the related parameters of LRCAC are reasonable. Thus, we employ these parameters in the remainder of this section. Each instance was calculated 30 times by LRCAC and AC, respectively; the results are shown in Table 5. In this table,Srivastava 86 is the name of this instance; 8×2 means there are 8 SRs and 2 candidate MCs, so do others. The coordinate of all nodes and the demands of SRs are given by the database. Table 5 shows that LRCAC can obtain better objective function value and stability than AC.Table 5
Optimal objective function values of two algorithms.
Instance
Algorithm
Max
Min
Mean
Standard deviation
Coefficient of variation
Srivastava 86-8×2
AC
402316
336543
365784
196736
0.537847
LRCAC
355215
306842
335765
158962
0.473432
Perl 183-12×2
AC
598173
528538
563184
257649
0.457486
LRCAC
553785
498037
528764
149717
0.283145
Christofides 69-50×5
AC
696271
620975
667864
456287
0.683203
LRCAC
633762
582867
619458
287392
0.4639411
Christofides 69-75×10
AC
890756
821789
867246
564782
0.651236
LRCAC
843685
783804
810473
395647
0.488168
Daskin 95-88×8
AC
1102873
898483
926586
537862
0.5804771
LRCAC
921587
873672
896926
407816
0.4546819
Daskin 95-150×10
AC
1516428
1256731
1478356
624638
0.422522
LRCAC
1258904
1078396
1157832
428373
0.3699785


## 4.1. Computational Experiment

We refer to the logistics network of companyK in Hubei province of China as an example. We convert the latitude and longitude coordinates of some cities in Hubei province and the central meridian to Xi'an 80 geographic coordinate. They are shown in Tables 1 and 2, in which the values represent the actual kilometers. And other parameters’ values are as follows: randomly generate the values between 100 and 160 as the μi, and assume that the σi2 is equal to μi, tj=1,pj=2,hj=1,lj=7 (day), αj=97.5%, w=0.2,    and d=2.Table 1
Parameters of MCs.
MC
Coordinate (km)
Fixed construction cost (Yuan)
Wuhan (j1)
(3342, 38529)
50
Xiangyang (j2)
(3322, 37609)
45
Xiaogan (j3)
(3533, 38491)
40
Yichang (j4)
(3397, 37528)
45
Jingzhou (j5)
(3356, 37619)
40
Huanggang (j6)
(3369, 38583)
35Table 2
Parameters of SRs.
SR
Coordinate (km)
Demand (unit)
Wuhan (i1)
(3342, 38529)
673
Xiangyang (i2)
(3322, 37609)
514
Xiaogan (i3)
(3533, 38491)
500
Yichang (i4)
(3397, 37528)
465
Jingzhou (i5)
(3356, 37619)
520
Huanggang (i6)
(3369, 38583)
440
Huangshi (i7)
(3342, 38604)
360
Shiyan (i8)
(3614, 37480)
400
Suizhou (i9)
(3468, 38361)
350
Xianning (i10)
(3305, 38527)
400
Enshi (i11)
(3271, 37357)
410
Jingmen (i12)
(3433, 37613)
510
Ezhou (i13)
(3362, 38583)
400Based on MATLAB 7.0 platform, we programmed the LRCAC algorithm and run it 30 times on the computer (CPU: Intel Core2 P7570 @2.26 GHz 2.27 GHz; RAM: 2.0 GB; OS: Windows 7); the optimal result is in Table3.Table 3
Optimal results.
Number of MCs
N (unit)
Q (unit)
The SRs assigned to MC
j
1
2
1410
i
1,i3, i6, i7, i10, i13
j
2
2
930
i
2, i8, i9
j
4
2
642
i
4, i11
j
5
4
776
i
5, i12The optimal cost is 224965 yuan, and logistics network is shown in Figure2.Figure 2
The logistics network obtained by LRCAC.For comparison, we programmed AC algorithm in the same platform and run 30 times on the same computer. The optimal objective function values of these two algorithms are shown in Table4.Table 4
Statistical results of optimal objective function value of two algorithms.
Max
Min
Mean
Standard deviation
Coefficient of variation
AC
263678
235791
244118
135673
0.56
LRCAC
231104
224965
230092
93876
0.41The two optimization trends of the two algorithms are shown in Figures3 and 4.Figure 3
Trends of optimal objective function value by LRCAC.Figure 4
Trends of optimal objective function value by AC.The fluctuation curves of optimal objective function in 30 times are shown in Figures5 and 6, respectively.Figure 5
Fluctuation curve of total cost by LRCAC algorithm.Figure 6
Fluctuation curve of total cost by AC.We can see that the LRCAC algorithm can converge more quickly than AC from Figures3 and 4. Moreover, LRCAC has better stability than AC, which can be easily found from Table 4 and Figures 5 and 6.


## 4.2. Algorithms Analysis

In this section, all the data in our experiments come from LRP database of the University of Aveiro [23]. A series of experiments show that LRCAC is more efficient and stable than AC. Results of numerical example in Section 4.1 show that the related parameters of LRCAC are reasonable. Thus, we employ these parameters in the remainder of this section. Each instance was calculated 30 times by LRCAC and AC, respectively; the results are shown in Table 5. In this table,Srivastava 86 is the name of this instance; 8×2 means there are 8 SRs and 2 candidate MCs, so do others. The coordinate of all nodes and the demands of SRs are given by the database. Table 5 shows that LRCAC can obtain better objective function value and stability than AC.Table 5
Optimal objective function values of two algorithms.
Instance
Algorithm
Max
Min
Mean
Standard deviation
Coefficient of variation
Srivastava 86-8×2
AC
402316
336543
365784
196736
0.537847
LRCAC
355215
306842
335765
158962
0.473432
Perl 183-12×2
AC
598173
528538
563184
257649
0.457486
LRCAC
553785
498037
528764
149717
0.283145
Christofides 69-50×5
AC
696271
620975
667864
456287
0.683203
LRCAC
633762
582867
619458
287392
0.4639411
Christofides 69-75×10
AC
890756
821789
867246
564782
0.651236
LRCAC
843685
783804
810473
395647
0.488168
Daskin 95-88×8
AC
1102873
898483
926586
537862
0.5804771
LRCAC
921587
873672
896926
407816
0.4546819
Daskin 95-150×10
AC
1516428
1256731
1478356
624638
0.422522
LRCAC
1258904
1078396
1157832
428373
0.3699785


## 5. Conclusion

Customers have a higher return rate in the e-commerce environment. Some returned goods have quality problems and need to be sent back to the factory for repair. The others without quality problems can be reentered in the sales channels just after a simple repackaging process. This phenomenon puts forward high requirements to the logistics system that supports the operation of e-commerce. This study handles the above interesting problem and provides an effective heuristic. The main contributions are as follows.(1)
In reality, the cost of processing returned merchandise is produced by considering the condition that customers are not satisfied with products and return them. We firstly design a closed-loop LIP model to minimize the total cost which is produced in both forward and reverse logistics networks. It is able to help managers make the right decision in e-commerce, decreasing the cost of logistics and improving the operational efficiency of e-commerce.(2)
The above closed-loop LIP model with returns is difficult to be solved by analytical method. Thus, a two-stage heuristic algorithm named LRCAC is designed by integrating Lagrangian relaxation with AC to solve the model.(3)
Results of our experiments show that LRCAC outperforms AC on both optimal solution and computing stability. LRCAC is a good candidate to effectively solve the proposed LIP model with returns.However, some extensions should be considered in further work. Considering the dynamic of the demand, a dynamic model should be established. Considering the fuzzy demand of customs or related fuzzy costs, more practical LIP model should be developed. Moreover, differential evolution algorithms (DEs) have turned out to be one of the best evolutionary algorithms in a variety of fields [24, 25]. In the future, we may use an improved DE to find better solutions for the LIPs. The integration research and practice of the management of e-commerce logistics system can be constantly improved.



---

*Source: 260869-2014-09-28.xml*