# A Location-Inventory-Routing Problem in Forward and Reverse Logistics Network Design

Authors: Qunli Yuchi; Zhengwen He; Zhen Yang; Nengmin Wang
Journal: Discrete Dynamics in Nature and Society
 (2016)

---

## Abstract

We study a new problem of location-inventory-routing in forward and reverse logistic (LIRP-FRL) network design, which simultaneously integrates the location decisions of distribution centers (DCs), the inventory policies of opened DCs, and the vehicle routing decision in serving customers, in which new goods are produced and damaged goods are repaired by a manufacturer and then returned to the market to satisfy customers’ demands as new ones. Our objective is to minimize the total costs of manufacturing and remanufacturing goods, building DCs, shipping goods (new or recovered) between the manufacturer and opened DCs, and distributing new or recovered goods to customers and ordering and storage costs of goods. A nonlinear integer programming model is proposed to formulate the LIRP-FRL. A new tabu search (NTS) algorithm is developed to achieve near optimal solution of the problem. Numerical experiments on the benchmark instances of a simplified version of the LIRP-FRL, the capacitated location routing problem, and the randomly generated LIRP-FRL instances demonstrate the effectiveness and efficiency of the proposed NTS algorithm in problem resolution.


---

## Body

## 1. Introduction

The need for designing distribution network to achieve a variety of the supply chain objects with the overall productivity has received considerable attentions and becomes more and more stronger in recent years. As Javid and Azad [1] said, location allocation problem, inventory control problem, and the vehicle routing problem are the most considered subproblems in designing a distribution network. Liu and Lee [2] showed that the routing and inventory decisions affect the location decision. Also, Viswanathan and Mathur [3] found that transportation costs will increase when the order quantity during each production runs decreases. Similar conclusions have also been found by Zhang et al. [4]; they pointed out that the above three subproblems are strongly correlated and mutually affect each other. Considering the three subproblems at the same time may provide a comprehensive estimation in constructing an efficient production-distribution network. This gives rise to the researches on the location-inventory-routing problem (LIRP).Differing in inventory policies used, the types of facilities located, and the vehicle routing strategies adopted, lots of researches on LIRP in forward logistics network design have been reported. Liu and Lee [2] studied a LIRP using order up to level inventory policy. A route-first and location-allocation second heuristic method was proposed by them to solve LIRP. Ambrosino and Scutella [5] studied a LIRP with the consideration of customers service level. Using (Q
,
R) inventory policy, Shen and Qi [6] proposed a Lagrangian relaxation and a rank and search algorithm to solve the LIRP. Following the researches of [6], Javid and Azad [1] solved the same problem by using a tabu search and simulated annealing. Guerrero et al. [7] proposed a column generation, Lagrangian relaxation, and local search combined heuristic for a multiperiod LIRP.As Ravi et al. [8] said, the forces of economic factors, legislation, corporate citizenship, and environmental protection problems are driving the increasing interests and investments of enterprises in reverse logistics. These motivate researchers to develop optimization models for reverse supply network design in the past decades (Vahdani and Naderi-Beni [9]).Chen et al. [10] concluded that the consideration of reverse logistics in distribution network design can greatly reduce the logistics costs without interrupting the forward flows. Taking both the forward logistics and reverse logistics into account, many researches on facility location, vehicle routing, and inventory management had been presented.Vahdani et al. [11] focused on a fuzzy facility location-allocation problem in closed loop logistics. Differing from [11], Vahdani et al. [12, 13] proposed a fuzzy possibility programming method to solve multiobjective facility problems in forward and reverse logistic.Under the background of forward and reverse logistic, different inventory models had also been developed in the literature. Richter [14] proposed the first inventory model in a closed logistic using EOQ model. It assumed that customers’ demands can be satisfied by newly made products or by repaired products. For a given fixed waste disposal rate, the optimal minimum cost expression was derived. Shi et al. [15] considered an inventory policy under uncertain customer demand. A Lagrangian relaxation based approach was proposed.Vehicle routing decision is another important research subject in forward and reverse logistic management. Zachariadis and Kiranoudis [16] studied a VRP problem under the background of forward and reverse logistic. A tabu search method was proposed. For a similar VRP problem, Goksal et al. [17] developed a particle swarm optimization (PSO) based approach for its resolution, in which a variable neighborhood descent (VND) algorithm was used as a local search to explore solution space.Different combination of facility location decision, inventory management decision, and vehicle routing decision gives rise to different research problems in forward and reverse logistics. For example, Liu et al. [18] proposed a hybrid particle swarm optimization to solve a location routing problem using grey systems theory in reverse logistics. Yu and Lin [19] presented a location routing problem with simultaneous pickup and delivery, which was solved via a multistart simulated annealing algorithm with multistart hill climbing. Modeling the problem as a bilevel programming problem, Wang et al. [20] studied realistic location-inventory problem in reverse logistic of a China B2C company. Li et al. [21] solved a location and inventory control problem by a two-stage heuristic algorithm that combined Lagrangian relaxation method with an ant colony algorithm.Due to the intrinsic complexity of the problem in mathematics, to our best knowledge, only a few researches, except that of Li et al. [22], simultaneously considered the decisions of the facility location, the inventory management, and vehicle routing in forward and reverse logistics in the literature. In their model, they consider retrieving those products that customers dislike to the DCs. As these products are new or unused, they can be sold to customers directly with no need to be returned to manufacturer for repair.However, as the work of Adler et al. [23] indicated, used (old or damaged) products (e.g., the engines of Caterpillar Company) can also be retrieved, recovered, and returned to the market to satisfy customers’ demands as new ones. This realistic new feature motivates us to focus on goods production, distribution, and recycling.A location-inventory-routing problem in forward and reverse logistic (LIRP-FRL) network design is studied in this paper. The LIRP-FRL simultaneously integrates the location decisions of distribution centers (DCs), the inventory policies of opened DCs, and the vehicle routing decision in serving customers, in which new goods are produced and damaged goods are repaired by a manufacturer and then transported to opened DCs. Vehicles that start from and end in the same DC distribute new or recovered goods to satisfy the demands of customers and retrieve damaged goods. Our objective is to minimize the total costs of manufacturing and remanufacturing goods, building DCs, shipping goods (new or recovered) between the manufacturer and opened DCs, distributing new or recovered goods to customers, and retrieving damaged goods from customers to DCs and the inventory costs of DCs including ordering new or recovered goods and holding these goods.Without taking the inventory strategy of DCs into account, our problem is simplified to the classicalcapacitated location routing problem (CLRP) [24], which is NP-hard in strong sense. Consequently, our problem is also NP-hard. Further, the LIRP-FRL is a nonlinear problem as the EOQ inventory policy is adopted. Due to its complexity, we focus on finding near optimal solutions for the LIRP-FRL. A new tabu search (NTS) algorithm is proposed to find approximately optimal solutions. This algorithm probabilistically accepts a second best solution to change search direction to achieve this goal. Numerical experiments of the CLRP benchmarks demonstrate the effectiveness and the efficiency of the proposed NTS method in obtaining high quality solutions in a very reasonable time. Computational and sensitivity analysis results on randomly generated LIRP-FRL instances are also reported.The rest of this paper is organized as follows. In Section2, a mathematical model is developed to describe the studied LIRP-FRL. A tabu search that seeks to search near optimal solution for the LIRP-FRL is proposed in Section 3. Algorithm performance evaluations are conducted in Section 4. Finally, we conclude the paper in Section 5.


## 2. Mathematical Model

Given a set of potential sites of distribution centers (DCs), the studied location-inventory-routing problem in forward and reverse logistic (LIRP-FRL) network design is to optimally determine the locations of DCs and their order quantities from a manufacturer, the product flows (forward and reverse) between the manufacturer and the opened DCs, and the paths of vehicles in serving customers. We assume that each route starts from and ends in the same DC, by which new or recovered products are delivered to satisfy the demands of customers for each cycle, and damaged products are retrieved. The objective of the LIRP-FRL is to minimize the sum of the opening costs and the inventory costs of DCs, the setup costs of vehicles, and the transportation costs of (new, repaired, and damaged) products. An example of the studied LIRP-FRL is illustrated in Figure1.Figure 1
Location-inventory-routing problem in forward and reverse logistic.


### 2.1. Notations

The notations are described as follows:I: the index set of customers,
J: the index set of potential distribution centers,
K: the index set of vehicles,
S: the merged set of customers and potential distribution centers I
∪
J,
V
j: the maximum capacity of the distribution center j, j
∈
J,
F
C
j: the fixed opening cost of establishing distribution center j, j
∈
J,
Q: the maximum capacity of homogeneous vehicle,
c
i
j: the transportation cost of a vehicle on a
r
c
i
,
j, i, j
∈
S, i
≠
j,
f
j: the setup cost of using a vehicle at distribution center j, j
∈
J,
c
j: the product unit transportation cost from the manufacturer to distribution center j, j
∈
J,
A
m: the order cost of new products of DCs per cycle,
A
r: the order cost of recovered or repaired products of DCs per cycle,
c
m: the cost of manufacturing a new product,
c
r: the cost of repairing a damaged product to a new product,
D
i: the demand of customers per cycle,
h
j: the unit holding cost of distribution center j, j
∈
J,
r: the rate of return in percentage,
c
d: the unit cost of disposal of useless retrieved products,
u: the percentage of reuse of retrieved products.


### 2.2. Decision Variables

The decision variables are described as follows:Q
j
m is the order quantity of new products of DC j
∈
J for each period,
Q
j
r is the order quantity of recovered products of DC j
∈
J for each period,
M
j is the order times of new products from DC j
∈
J during each period,
R
j is the order times of recovered products from DC j
∈
J during each period,
x
i
j
k
=
1
,
i
f
a
r
c
i
,
j
i
s
t
r
a
v
e
l
l
e
d
b
y
v
e
h
i
c
l
e
k
;
0, otherwise (i
,
j
∈
S, k
∈
K),
y
i
j
=
1
,
if  customer
i
∈
I
is  served  by  distribution  center
j
∈
J
;
0
,
otherwise,
Z
j
=
1
,
if  distribution  center
j
∈
J
is  established;
0
,
o
t
h
e
r
w
i
s
e.


### 2.3. Cost Analysis

To simplify the presentation, we first abbreviate the costs related to the LIRP-FRL as follows:(1)
The total fixed cost of opening distribution centers is(1)
F
I
X
C
O
S
T
=
∑
j
∈
J
F
C
j
·
z
j
.
(2)
The total cost of ordering new and recovered products is(2)
O
C
=
∑
j
∈
J
A
m
·
∑
i
∈
I
D
i
1
-
u
y
i
j
Q
j
m
+
A
r
·
∑
i
∈
I
D
i
u
y
i
j
Q
j
r
.
(3)
The total cost of producing new products and recovering retrieved products is(3)
M
R
=
∑
j
∈
J
∑
i
∈
I
D
i
·
1
-
u
·
c
m
+
u
·
c
r
·
y
i
j
.
(4)
The total cost of disposal of useless retrieved products is(4)
D
I
S
P
=
∑
j
∈
J
∑
i
∈
I
D
i
·
r
-
u
·
c
d
·
y
i
j
.
(5)
The transportation cost between the manufacturer and distribution centers is(5)
T
R
A
N
=
∑
j
∈
J
c
j
∑
i
∈
I
D
i
·
1
+
u
·
y
i
j
.
(6)
The transportation cost between distribution centers and customers is(6)
T
R
C
=
∑
k
∈
K
∑
j
∈
S
∑
i
∈
S
f
j
·
x
i
j
k
+
∑
k
∈
K
∑
j
∈
S
∑
i
∈
I
c
i
j
·
x
i
j
k
.Given the locations of DCs and the routes of vehicles, the LIRP-FRL is reduced to the inventory model of Teunter [25]. Some of their valuable conclusions can be directly applied to our LIRP-FRL.Proposition 1 (Teunter [25]).
“It is reasonable to restrict our attention to those policies with eitherM
=
1 or R
=
1.”Teunter [25] concluded that the policies with either M
=
1 or R
=
1 can obtain near optimal solution with less computational time by comparing with that of achieving optimal solution. Since our problem is more complicated than that of Teunter [25], to simplify the resolution of LIRP-FRL, we consider only the two cases in our implementation. The two cases are as follows.Case 1 (1,M).
That meansR
=
1; in this case the order times of recovered products for each DC are equal to one.Case 2 (R, 1).
That meansM
=
1; in this case the order times of new products for each DC are equal to one.
For Case1 (1,M), the holding cost is (7)
H
M
=
∑
j
∈
J
1
2
h
j
1
-
u
·
Q
j
m
+
u
·
Q
j
r
+
Q
j
r
·
u
r
·
z
j
.
Consequently, the total cost is denoted as(8)
T
C
M
=
F
I
X
C
O
S
T
+
O
C
+
M
R
+
D
I
S
P
+
T
R
A
N
+
T
R
C
+
H
M
.
For Case2 (R, 1), the holding cost is(9)
H
R
=
∑
j
∈
J
1
2
h
j
1
-
u
·
Q
j
m
+
u
·
Q
j
r
+
r
Q
j
m
+
Q
j
r
-
r
-
u
·
Q
j
m
+
u
1
-
u
Q
j
m
u
r
·
z
j
.The corresponding total cost is(10)
T
C
R
=
F
I
X
C
O
S
T
+
O
C
+
M
R
+
D
I
S
P
+
T
R
A
N
+
T
R
C
+
H
R
.


### 2.4. Mathematical Model

The LIRP-FRL can be formulated as the following nonlinear mixed integer programming problem:(11)
m
i
n
T
C
M
,
T
C
R
,
(12)
s
.
t
.
∑
k
∈
K
∑
i
∈
S
x
i
j
k
=
1
,
j
∈
I
(13)
∑
j
∈
S
x
i
j
k
-
∑
j
∈
S
x
j
i
k
=
0
,
i
∈
S
,
k
∈
K
(14)
∑
j
∈
J
∑
i
∈
I
x
i
j
k
≤
1
,
k
∈
K
(15)
∑
j
∈
J
∑
i
∈
I
D
i
x
i
j
k
≤
Q
,
k
∈
K
(16)
∑
i
∈
I
D
i
y
i
j
-
V
j
·
z
j
≤
0
,
j
∈
J
(17)
y
i
j
+
1
≥
∑
g
∈
I
x
i
g
k
+
∑
g
∈
S
∖
j
x
g
j
k
,
i
∈
J
,
j
∈
I
,
k
∈
K
(18)
∑
j
∈
W
∑
i
∈
W
x
i
j
k
≤
W
-
1
,
W
⊆
I
,
k
∈
K
(19)
x
i
j
k
∈
0,1
,
i
∈
S
,
j
∈
S
,
k
∈
K
(20)
y
i
j
∈
0,1
,
i
∈
I
,
j
∈
J
(21)
z
j
∈
0,1
,
j
∈
J
.Constraints (12) state that each customer is exactly served by one vehicle. Constraints (13) are the equilibrium constraints of vehicle routes on nodes. Constraints (14) ensure that each vehicle can be used by at most one DC. Constraints (15) guarantee that the capacity of vehicle cannot be exceeded. Constraints (16) are the capacity constraints of distribution centers. Constraints (17) make sure that a customer can only be served by the vehicle which originates from the DC it is assigned to. Constraints (18) are the subtours elimination constraints of vehicle routes.Proposition 2.
For any distribution center,j
∈
J, its order quantities Q
j
m and Q
j
r can be represented as a function of customers’ demands, respectively.
We haveQ
j
m
=
2
A
m
∑
i
∈
I
D
i
·
y
i
j
/
h
j and Q
j
r
=
2
A
r
·
r
·
∑
i
∈
I
D
i
·
y
i
j
/
r
+
1
h
j for any j
∈
J.Proof.
It can be observed that, no matter case (1,M) or case (R, 1), decision variables Q
j
m and Q
j
r appear only in the objective function. For the case (R, 1), the optimal value of Q
j
m and Q
j
r can be obtained by checking the extreme conditions: ∂
T
C
M
/
∂
Q
j
m
=
0 and ∂
T
C
M
/
∂
Q
j
r
=
0.
Since∂
2
T
C
M
/
∂
Q
j
m
2
=
(
2
A
m
·
1
-
u
∑
i
∈
I
D
i
·
y
i
j
)
/
Q
j
m
3
≥
0 and ∂
2
T
C
M
/
∂
Q
j
r
2
=
(
2
A
r
·
u
∑
i
∈
I
D
i
·
y
i
j
)
/
Q
j
r
3
≥
0, consequently the extreme point is a minimum point. We obtain the optimal order quantities Q
j
m
=
(
2
A
m
∑
i
∈
I
D
i
·
1
-
u
y
i
j
)
/
h
j
1
-
(
(
r
-
u
)
/
(
1
-
u
)
)
·
(
u
/
r
) and Q
j
r
=
(
A
r
·
∑
i
∈
I
D
i
·
y
i
j
)
/
h
j and the corresponding order time R
j
=
(
u
·
Q
j
m
)
/
(
1
-
u
·
Q
j
r
).
For the same reason, for the case (1,M), we can derive that the order quantities Q
j
m
=
(
2
A
m
∑
i
∈
I
D
i
·
y
i
j
)
/
h
j and Q
j
r
=
(
2
A
r
·
r
·
∑
i
∈
I
D
i
·
y
i
j
)
/
r
+
1
h
j and the corresponding order time M
j
=
(
1
-
u
·
Q
j
r
)
/
(
u
·
Q
j
m
).
Observe that, without considering the inventory strategy of these two cases, Cases1 and 2, the LIRP-FRL is reduced to the classical capacitated location routing problem (CLRP), which is NP-hard in the strong sense. As a result, the LIRP-FRL is also NP-hard. As Belenguer et al. [24] reported, to find CLRP optimal solution, even for the median size CLRP instances (with 50 customers and 5 potential distribution centers), significant research efforts need to be expensed. Thus, in this paper, we focus on finding near optimal solutions for the LIRP-FRL.


## 2.1. Notations

The notations are described as follows:I: the index set of customers,
J: the index set of potential distribution centers,
K: the index set of vehicles,
S: the merged set of customers and potential distribution centers I
∪
J,
V
j: the maximum capacity of the distribution center j, j
∈
J,
F
C
j: the fixed opening cost of establishing distribution center j, j
∈
J,
Q: the maximum capacity of homogeneous vehicle,
c
i
j: the transportation cost of a vehicle on a
r
c
i
,
j, i, j
∈
S, i
≠
j,
f
j: the setup cost of using a vehicle at distribution center j, j
∈
J,
c
j: the product unit transportation cost from the manufacturer to distribution center j, j
∈
J,
A
m: the order cost of new products of DCs per cycle,
A
r: the order cost of recovered or repaired products of DCs per cycle,
c
m: the cost of manufacturing a new product,
c
r: the cost of repairing a damaged product to a new product,
D
i: the demand of customers per cycle,
h
j: the unit holding cost of distribution center j, j
∈
J,
r: the rate of return in percentage,
c
d: the unit cost of disposal of useless retrieved products,
u: the percentage of reuse of retrieved products.


## 2.2. Decision Variables

The decision variables are described as follows:Q
j
m is the order quantity of new products of DC j
∈
J for each period,
Q
j
r is the order quantity of recovered products of DC j
∈
J for each period,
M
j is the order times of new products from DC j
∈
J during each period,
R
j is the order times of recovered products from DC j
∈
J during each period,
x
i
j
k
=
1
,
i
f
a
r
c
i
,
j
i
s
t
r
a
v
e
l
l
e
d
b
y
v
e
h
i
c
l
e
k
;
0, otherwise (i
,
j
∈
S, k
∈
K),
y
i
j
=
1
,
if  customer
i
∈
I
is  served  by  distribution  center
j
∈
J
;
0
,
otherwise,
Z
j
=
1
,
if  distribution  center
j
∈
J
is  established;
0
,
o
t
h
e
r
w
i
s
e.


## 2.3. Cost Analysis

To simplify the presentation, we first abbreviate the costs related to the LIRP-FRL as follows:(1)
The total fixed cost of opening distribution centers is(1)
F
I
X
C
O
S
T
=
∑
j
∈
J
F
C
j
·
z
j
.
(2)
The total cost of ordering new and recovered products is(2)
O
C
=
∑
j
∈
J
A
m
·
∑
i
∈
I
D
i
1
-
u
y
i
j
Q
j
m
+
A
r
·
∑
i
∈
I
D
i
u
y
i
j
Q
j
r
.
(3)
The total cost of producing new products and recovering retrieved products is(3)
M
R
=
∑
j
∈
J
∑
i
∈
I
D
i
·
1
-
u
·
c
m
+
u
·
c
r
·
y
i
j
.
(4)
The total cost of disposal of useless retrieved products is(4)
D
I
S
P
=
∑
j
∈
J
∑
i
∈
I
D
i
·
r
-
u
·
c
d
·
y
i
j
.
(5)
The transportation cost between the manufacturer and distribution centers is(5)
T
R
A
N
=
∑
j
∈
J
c
j
∑
i
∈
I
D
i
·
1
+
u
·
y
i
j
.
(6)
The transportation cost between distribution centers and customers is(6)
T
R
C
=
∑
k
∈
K
∑
j
∈
S
∑
i
∈
S
f
j
·
x
i
j
k
+
∑
k
∈
K
∑
j
∈
S
∑
i
∈
I
c
i
j
·
x
i
j
k
.Given the locations of DCs and the routes of vehicles, the LIRP-FRL is reduced to the inventory model of Teunter [25]. Some of their valuable conclusions can be directly applied to our LIRP-FRL.Proposition 1 (Teunter [25]).
“It is reasonable to restrict our attention to those policies with eitherM
=
1 or R
=
1.”Teunter [25] concluded that the policies with either M
=
1 or R
=
1 can obtain near optimal solution with less computational time by comparing with that of achieving optimal solution. Since our problem is more complicated than that of Teunter [25], to simplify the resolution of LIRP-FRL, we consider only the two cases in our implementation. The two cases are as follows.Case 1 (1,M).
That meansR
=
1; in this case the order times of recovered products for each DC are equal to one.Case 2 (R, 1).
That meansM
=
1; in this case the order times of new products for each DC are equal to one.
For Case1 (1,M), the holding cost is (7)
H
M
=
∑
j
∈
J
1
2
h
j
1
-
u
·
Q
j
m
+
u
·
Q
j
r
+
Q
j
r
·
u
r
·
z
j
.
Consequently, the total cost is denoted as(8)
T
C
M
=
F
I
X
C
O
S
T
+
O
C
+
M
R
+
D
I
S
P
+
T
R
A
N
+
T
R
C
+
H
M
.
For Case2 (R, 1), the holding cost is(9)
H
R
=
∑
j
∈
J
1
2
h
j
1
-
u
·
Q
j
m
+
u
·
Q
j
r
+
r
Q
j
m
+
Q
j
r
-
r
-
u
·
Q
j
m
+
u
1
-
u
Q
j
m
u
r
·
z
j
.The corresponding total cost is(10)
T
C
R
=
F
I
X
C
O
S
T
+
O
C
+
M
R
+
D
I
S
P
+
T
R
A
N
+
T
R
C
+
H
R
.


## 2.4. Mathematical Model

The LIRP-FRL can be formulated as the following nonlinear mixed integer programming problem:(11)
m
i
n
T
C
M
,
T
C
R
,
(12)
s
.
t
.
∑
k
∈
K
∑
i
∈
S
x
i
j
k
=
1
,
j
∈
I
(13)
∑
j
∈
S
x
i
j
k
-
∑
j
∈
S
x
j
i
k
=
0
,
i
∈
S
,
k
∈
K
(14)
∑
j
∈
J
∑
i
∈
I
x
i
j
k
≤
1
,
k
∈
K
(15)
∑
j
∈
J
∑
i
∈
I
D
i
x
i
j
k
≤
Q
,
k
∈
K
(16)
∑
i
∈
I
D
i
y
i
j
-
V
j
·
z
j
≤
0
,
j
∈
J
(17)
y
i
j
+
1
≥
∑
g
∈
I
x
i
g
k
+
∑
g
∈
S
∖
j
x
g
j
k
,
i
∈
J
,
j
∈
I
,
k
∈
K
(18)
∑
j
∈
W
∑
i
∈
W
x
i
j
k
≤
W
-
1
,
W
⊆
I
,
k
∈
K
(19)
x
i
j
k
∈
0,1
,
i
∈
S
,
j
∈
S
,
k
∈
K
(20)
y
i
j
∈
0,1
,
i
∈
I
,
j
∈
J
(21)
z
j
∈
0,1
,
j
∈
J
.Constraints (12) state that each customer is exactly served by one vehicle. Constraints (13) are the equilibrium constraints of vehicle routes on nodes. Constraints (14) ensure that each vehicle can be used by at most one DC. Constraints (15) guarantee that the capacity of vehicle cannot be exceeded. Constraints (16) are the capacity constraints of distribution centers. Constraints (17) make sure that a customer can only be served by the vehicle which originates from the DC it is assigned to. Constraints (18) are the subtours elimination constraints of vehicle routes.Proposition 2.
For any distribution center,j
∈
J, its order quantities Q
j
m and Q
j
r can be represented as a function of customers’ demands, respectively.
We haveQ
j
m
=
2
A
m
∑
i
∈
I
D
i
·
y
i
j
/
h
j and Q
j
r
=
2
A
r
·
r
·
∑
i
∈
I
D
i
·
y
i
j
/
r
+
1
h
j for any j
∈
J.Proof.
It can be observed that, no matter case (1,M) or case (R, 1), decision variables Q
j
m and Q
j
r appear only in the objective function. For the case (R, 1), the optimal value of Q
j
m and Q
j
r can be obtained by checking the extreme conditions: ∂
T
C
M
/
∂
Q
j
m
=
0 and ∂
T
C
M
/
∂
Q
j
r
=
0.
Since∂
2
T
C
M
/
∂
Q
j
m
2
=
(
2
A
m
·
1
-
u
∑
i
∈
I
D
i
·
y
i
j
)
/
Q
j
m
3
≥
0 and ∂
2
T
C
M
/
∂
Q
j
r
2
=
(
2
A
r
·
u
∑
i
∈
I
D
i
·
y
i
j
)
/
Q
j
r
3
≥
0, consequently the extreme point is a minimum point. We obtain the optimal order quantities Q
j
m
=
(
2
A
m
∑
i
∈
I
D
i
·
1
-
u
y
i
j
)
/
h
j
1
-
(
(
r
-
u
)
/
(
1
-
u
)
)
·
(
u
/
r
) and Q
j
r
=
(
A
r
·
∑
i
∈
I
D
i
·
y
i
j
)
/
h
j and the corresponding order time R
j
=
(
u
·
Q
j
m
)
/
(
1
-
u
·
Q
j
r
).
For the same reason, for the case (1,M), we can derive that the order quantities Q
j
m
=
(
2
A
m
∑
i
∈
I
D
i
·
y
i
j
)
/
h
j and Q
j
r
=
(
2
A
r
·
r
·
∑
i
∈
I
D
i
·
y
i
j
)
/
r
+
1
h
j and the corresponding order time M
j
=
(
1
-
u
·
Q
j
r
)
/
(
u
·
Q
j
m
).
Observe that, without considering the inventory strategy of these two cases, Cases1 and 2, the LIRP-FRL is reduced to the classical capacitated location routing problem (CLRP), which is NP-hard in the strong sense. As a result, the LIRP-FRL is also NP-hard. As Belenguer et al. [24] reported, to find CLRP optimal solution, even for the median size CLRP instances (with 50 customers and 5 potential distribution centers), significant research efforts need to be expensed. Thus, in this paper, we focus on finding near optimal solutions for the LIRP-FRL.


## 3. New Tabu Search

Using tabu list to avoid visited solutions to be revisited, the tabu search proposed by Glover [26] is one of the most effective approaches for solving mixed integer programming problems, which has been successfully applied to a variety of distribution network design problems. For the detailed introduction and application of the tabu search, we refer readers to Glover [27] and Habet [28].In this section, a tabu search (NTS) algorithm that probabilistically accepts the second best solution in search process when a local optimum is reached is proposed to effectively solve the LIRP-FRL. The key components of the NTS, including a solution representation technique, an initial solution generation method, neighbourhood structures, and the general framework of the new tabu search, are presented in detail as follows.


### 3.1. Solution Representation

A good solution representation can not only describe the problem solutions clearly but also improve the performance of heuristics adopted. Similar to that of Yu et al. [29], in our implementation, solution {
x
1
,
x
2
,
…
,
x
n
,
x
n
+
1
,
…
,
x
n
+
m
} is represented by a permutation of number {
1,2
,
…
,
n
,
n
+
1
,
n
+
2
,
…
,
n
+
m
}, where x
j
∈
{
1,2
,
…
,
n
} indexes customer x
j and x
i
∈
{
n
+
1
,
n
+
2
,
…
,
n
+
m
} denotes potential DC x
i.An example was given in Figure2. In this example, the first number is distribution center 21, followed by distribution center 23. Since there are no customers between distribution center 21 and distribution center 23, distribution center 21 is closed. Customers (19, 16, 15, 14, 8, 11, and 6) between distribution center 23 and distribution center 22 are real customers; thus distribution center 23 is opened to service these customers. The first route of distribution center 23 services customers 19, 16, 15, and 14. Because adding customer 8 exceeds the vehicle capacity, the second route services customers 8, 11, and 6. Customer 6 is followed by distribution center 22, so the second route is terminated. For a similar reason as mentioned above, distribution centers 22 and 25 are open with two routes and one route, respectively.Figure 2
An example of solution representation.This representation has determined which distribution center is open and the customers on each route. With that decided, we can easily calculate the objective function value, because the inventory cost is related to LRP, which means when LRP is solved the inventory cost can be uniquely determined by Proposition2. Note that the capacity of distribution center is not taken into consideration. So during the decoding process, a per unit penalty cost M with a big value is added to the objective function value when the total demand serviced by a distribution center exceeds its capacity.To simplify the presentation of the algorithms proposed in following subsections, we say that an elementx
i of the solution isbefore another element x
j or element x
j isafter element x
i if and only if i
<
j. Further, with the smallest value |
i
-
j
|, if DC x
i isbefore DC x
j, we say that DC x
i isnearest before DC x
j, or DC x
j isnearest after DC
x
i.


### 3.2. Constructing Initial Solution

A greedy nearest neighbor method is proposed to construct an initial feasible solution of the LIRP-FRL, which is used as an input for the tabu search. Details of the greedy algorithm are given as follows.Algorithm 3 (greedy nearest neighbour method).
Step  0. Initialize Ω
0
≔
J, Ω
1
≔
⌀, Φ
0
≔
I, and Φ
1
≔
⌀.
Step  1. Assign each customer in Φ
0 to its closest DCs in Ω
0.
Step  2. Open the DC in Ω
0 with the largest number of customers assigned to say DCj
∗.
Step  3. Sort the customers of set Φ
0 in nondecreasing order of the distance between it and the DCj
∗.
Step  4. With the order, let Φ
=
{
s
1
,
s
2
,
…
,
s
|
Φ
0
|
} be the subset of customers of Φ
0 with the largest |
Φ
| and ∑
i
=
1
|
Φ
|
d
s
i
≤
V
j
∗. Renew Ω
1
≔
Ω
1
∪
{
j
∗
}, Ω
0
≔
J
/
Ω
1, Φ
1
≔
Φ
1
∪
Φ, and Φ
0
≔
I
/
Φ
1.
Step  5. If Φ
0
≠
⌀, then return to Step  1; Otherwise, open the DCs in Ω1 and assign each customer to a DC according to the customer-DC assignments determined in Step  4.
Step  6. For each opened DC, sort the customers assigned to it into sequence by using a nearest neighbor heuristic (refer to Rosenkrantz et al. [30]). Split the sequence into several feasible routes so that vehicle capacity constraints are satisfied.
Step  7. Output feasible solution.In our implementation of Step  2, if more than one DC has the largest number of customers assigned to, we select the DC with the highest capacity.


### 3.3. Neighborhoods

Given a solution(22)
X
=
x
1
,
x
2
,
…
,
x
i
-
1
,
x
i
,
x
i
+
1
,
…
,
x
j
-
1
,
x
j
,
x
j
+
1
,
…
,
x
n
,a permutation of {
1,2
,
…
,
n
,
n
+
1
,
…
,
n
+
m
}, three kinds of neighbourhoods are considered in our tabu search.


#### 3.3.1. Insertion Neighbourhood

The insertion neighborhood is defined as the set of solutions that can be reached by insertion move, which deletes one element of the solutionX and then inserts it to another place. For example, delete element x
i and insert it into the jth place; we obtain a new solution:(23)
X
′
=
x
1
,
x
2
,
…
,
x
i
-
1
,
x
i
+
1
,
…
,
x
j
-
1
,
x
j
,
x
i
,
x
j
+
1
,
…
,
x
n
.According to the element selected (customer or depot) and the position it is inserted in, there are four cases:(a)
Ifx
i and x
j are both customers, then customer x
i is reassigned to the DC that customer x
j is assigned to.
(b)
Ifx
i and x
j are both DCs, then reassign the customers previously assigned to the DC nearest before it. Close DC x
j and assign its customers to DC x
i.
(c)
Ifx
i is a customer and x
j is a DC, then customer x
i is reassigned to DC x
j.
(d)
Ifx
i is a DC and x
j is a customer, reassign customers that are nearest after customer x
j to DC x
i. All customers assigned to DC x
i are reassigned to the DC nearest before it.


#### 3.3.2. Swap Neighbourhood

The swap neighbourhood, a set of solutions, contains the solutions that can be reached by performing a swap move, which exchanges the places of two different elements of solutionX. For example, exchange element x
i and element x
j of X; the resulting new solution is (24)
X
′
=
x
1
,
x
2
,
…
,
x
i
-
1
,
x
j
,
x
i
+
1
,
…
,
x
j
-
1
,
x
i
,
x
j
+
1
,
…
,
x
n
.Similar to the insert move, the swap move has also four cases:(e)
Ifx
i and x
j are both customers, then we exchange the two DCs they are currently assigned to and obtain two new customer-DC assignments.
(f)
Ifx
i and x
j are both DCs, then we exchange all the customers currently assigned to them.
(g)
Ifx
i is a customer and x
j is a DC, then the customers after x
i assigned to the same DC are reassigned to DC x
j, and customer x
i is reassigned to the DC nearest before DC x
j. All customers previously assigned to DC x
j will be reassigned to the DC nearest before it.
(h)
Ifx
i is a DC and x
j is a customer, this case is similar to case g.


#### 3.3.3.2-Opt Neighbourhood

With the consideration of vehicle capacity, in our definition, the 2-opt neighbourhood contains the solutions that can be obtained by selecting two customers ofX (e.g., x
i and x
j) and then reversing the substring in the solution representation between them, the so-called 2-opt move. For example, applying 2-opt move to elements x
i and x
j, we obtain (25)
X
′
=
x
1
,
x
2
,
…
,
x
i
-
1
,
x
j
,
x
j
-
1
,
…
,
x
i
+
1
,
x
i
,
x
j
+
1
,
…
,
x
n
.


### 3.4. Tabu Search Framework

To increase the probability of obtaining high quality solutions, a diversification strategy is implemented. This strategy probabilistically accepts the second best solution in the search process while no better solution can be found in the neighborhoods of the current solution. By doing so, we can effectively diversify the search direction and thus more solution space will be explored. Consequently, better solution may be found. The computation results in Section4 prove this strategy. The proposed tabu search can be summarized as follows.Algorithm 4 (new tabu search).
Step  0. Input an initial feasible solution X
0 (see Section 3.2) and initialize I
t
e
r
≔
0, X
c
u
r
r
≔
X
0, and O
b
j
∗
≔
O
b
j
(
X
0
).Step  1. Explore the neighborhoods of X
c
u
r
r and denote the best solution in the neighborhoods, the best nontabu solution, and the second best nontabu solution as X
b
e
s
t, X
t
a
b
u
-
b
e
s
t, and X
t
a
b
u
-
2
n
d, respectively.Step  2. If O
b
j
(
X
b
e
s
t
)
<
O
b
j
∗, then set X
c
u
r
r
≔
X
b
e
s
t and add the corresponding move to tabu list; otherwise,ifO
b
j
(
X
t
a
b
u
-
b
e
s
t
)
<
O
b
j
(
X
c
u
r
r
), then X
c
u
r
r
≔
X
t
a
b
u
-
b
e
s
t and add the corresponding move to tabu list;
otherwise, probabilistically move to X
t
a
b
u
-
b
e
s
t or X
t
a
b
u
-
2
n
d, X
c
u
r
r
≔
P
r
o
b
{
X
t
a
b
u
-
b
e
s
t
,
X
t
a
b
u
-
2
n
d
}, and add the corresponding move to tabu list.Step  3. I
t
e
r
≔
I
t
e
r
+
1; If no stopping criterion is reached, return to Step  1.Step  4. Output the best solution objective function value O
b
j
∗.In the proposed tabu search algorithm, Iter counts the number of iterations andX
0 represents the initial solution obtained by greedy nearest neighbour method (Section 3.2). X
c
u
r
r denotes the current solution. O
b
j
∗ is the objective function value corresponding to the best solution found so far. The function O
b
j
(
X
) represents the objective function value of solution X.In Step  2, comparing with the current solutionX
c
u
r
r if no better solution can be found in its neighbourhood, we need to probabilistically move X
c
u
r
r to X
t
a
b
u
-
b
e
s
t or X
t
a
b
u
-
2
n
d. In implementation, we randomly generate a value β in interval [
0
,
1
]. If β
≥
λ, then X
c
u
r
r is moved to X
t
a
b
u
-
b
e
s
t; and otherwise X
c
u
r
r is moved to X
t
a
b
u
-
2
n
d, where λ is a given parameter.At each iteration of the tabu search procedure, the best admissible nontabu insertion, swap or 2-opt move is performed. The two elements of solutionX
c
u
r
r involved in such move are declared as tabu-active, which is forbidden to be removed in the next t iterations. t is the tabu-tenure parameter selected randomly from a range [T
m
i
n, T
m
a
x].The tabu search iteration is terminated if the maximum number of iterations maxIter is reached or if the best solution found so far has been improved in successive SucIter iteration.


## 3.1. Solution Representation

A good solution representation can not only describe the problem solutions clearly but also improve the performance of heuristics adopted. Similar to that of Yu et al. [29], in our implementation, solution {
x
1
,
x
2
,
…
,
x
n
,
x
n
+
1
,
…
,
x
n
+
m
} is represented by a permutation of number {
1,2
,
…
,
n
,
n
+
1
,
n
+
2
,
…
,
n
+
m
}, where x
j
∈
{
1,2
,
…
,
n
} indexes customer x
j and x
i
∈
{
n
+
1
,
n
+
2
,
…
,
n
+
m
} denotes potential DC x
i.An example was given in Figure2. In this example, the first number is distribution center 21, followed by distribution center 23. Since there are no customers between distribution center 21 and distribution center 23, distribution center 21 is closed. Customers (19, 16, 15, 14, 8, 11, and 6) between distribution center 23 and distribution center 22 are real customers; thus distribution center 23 is opened to service these customers. The first route of distribution center 23 services customers 19, 16, 15, and 14. Because adding customer 8 exceeds the vehicle capacity, the second route services customers 8, 11, and 6. Customer 6 is followed by distribution center 22, so the second route is terminated. For a similar reason as mentioned above, distribution centers 22 and 25 are open with two routes and one route, respectively.Figure 2
An example of solution representation.This representation has determined which distribution center is open and the customers on each route. With that decided, we can easily calculate the objective function value, because the inventory cost is related to LRP, which means when LRP is solved the inventory cost can be uniquely determined by Proposition2. Note that the capacity of distribution center is not taken into consideration. So during the decoding process, a per unit penalty cost M with a big value is added to the objective function value when the total demand serviced by a distribution center exceeds its capacity.To simplify the presentation of the algorithms proposed in following subsections, we say that an elementx
i of the solution isbefore another element x
j or element x
j isafter element x
i if and only if i
<
j. Further, with the smallest value |
i
-
j
|, if DC x
i isbefore DC x
j, we say that DC x
i isnearest before DC x
j, or DC x
j isnearest after DC
x
i.


## 3.2. Constructing Initial Solution

A greedy nearest neighbor method is proposed to construct an initial feasible solution of the LIRP-FRL, which is used as an input for the tabu search. Details of the greedy algorithm are given as follows.Algorithm 3 (greedy nearest neighbour method).
Step  0. Initialize Ω
0
≔
J, Ω
1
≔
⌀, Φ
0
≔
I, and Φ
1
≔
⌀.
Step  1. Assign each customer in Φ
0 to its closest DCs in Ω
0.
Step  2. Open the DC in Ω
0 with the largest number of customers assigned to say DCj
∗.
Step  3. Sort the customers of set Φ
0 in nondecreasing order of the distance between it and the DCj
∗.
Step  4. With the order, let Φ
=
{
s
1
,
s
2
,
…
,
s
|
Φ
0
|
} be the subset of customers of Φ
0 with the largest |
Φ
| and ∑
i
=
1
|
Φ
|
d
s
i
≤
V
j
∗. Renew Ω
1
≔
Ω
1
∪
{
j
∗
}, Ω
0
≔
J
/
Ω
1, Φ
1
≔
Φ
1
∪
Φ, and Φ
0
≔
I
/
Φ
1.
Step  5. If Φ
0
≠
⌀, then return to Step  1; Otherwise, open the DCs in Ω1 and assign each customer to a DC according to the customer-DC assignments determined in Step  4.
Step  6. For each opened DC, sort the customers assigned to it into sequence by using a nearest neighbor heuristic (refer to Rosenkrantz et al. [30]). Split the sequence into several feasible routes so that vehicle capacity constraints are satisfied.
Step  7. Output feasible solution.In our implementation of Step  2, if more than one DC has the largest number of customers assigned to, we select the DC with the highest capacity.


## 3.3. Neighborhoods

Given a solution(22)
X
=
x
1
,
x
2
,
…
,
x
i
-
1
,
x
i
,
x
i
+
1
,
…
,
x
j
-
1
,
x
j
,
x
j
+
1
,
…
,
x
n
,a permutation of {
1,2
,
…
,
n
,
n
+
1
,
…
,
n
+
m
}, three kinds of neighbourhoods are considered in our tabu search.


### 3.3.1. Insertion Neighbourhood

The insertion neighborhood is defined as the set of solutions that can be reached by insertion move, which deletes one element of the solutionX and then inserts it to another place. For example, delete element x
i and insert it into the jth place; we obtain a new solution:(23)
X
′
=
x
1
,
x
2
,
…
,
x
i
-
1
,
x
i
+
1
,
…
,
x
j
-
1
,
x
j
,
x
i
,
x
j
+
1
,
…
,
x
n
.According to the element selected (customer or depot) and the position it is inserted in, there are four cases:(a)
Ifx
i and x
j are both customers, then customer x
i is reassigned to the DC that customer x
j is assigned to.
(b)
Ifx
i and x
j are both DCs, then reassign the customers previously assigned to the DC nearest before it. Close DC x
j and assign its customers to DC x
i.
(c)
Ifx
i is a customer and x
j is a DC, then customer x
i is reassigned to DC x
j.
(d)
Ifx
i is a DC and x
j is a customer, reassign customers that are nearest after customer x
j to DC x
i. All customers assigned to DC x
i are reassigned to the DC nearest before it.


### 3.3.2. Swap Neighbourhood

The swap neighbourhood, a set of solutions, contains the solutions that can be reached by performing a swap move, which exchanges the places of two different elements of solutionX. For example, exchange element x
i and element x
j of X; the resulting new solution is (24)
X
′
=
x
1
,
x
2
,
…
,
x
i
-
1
,
x
j
,
x
i
+
1
,
…
,
x
j
-
1
,
x
i
,
x
j
+
1
,
…
,
x
n
.Similar to the insert move, the swap move has also four cases:(e)
Ifx
i and x
j are both customers, then we exchange the two DCs they are currently assigned to and obtain two new customer-DC assignments.
(f)
Ifx
i and x
j are both DCs, then we exchange all the customers currently assigned to them.
(g)
Ifx
i is a customer and x
j is a DC, then the customers after x
i assigned to the same DC are reassigned to DC x
j, and customer x
i is reassigned to the DC nearest before DC x
j. All customers previously assigned to DC x
j will be reassigned to the DC nearest before it.
(h)
Ifx
i is a DC and x
j is a customer, this case is similar to case g.


### 3.3.3.2-Opt Neighbourhood

With the consideration of vehicle capacity, in our definition, the 2-opt neighbourhood contains the solutions that can be obtained by selecting two customers ofX (e.g., x
i and x
j) and then reversing the substring in the solution representation between them, the so-called 2-opt move. For example, applying 2-opt move to elements x
i and x
j, we obtain (25)
X
′
=
x
1
,
x
2
,
…
,
x
i
-
1
,
x
j
,
x
j
-
1
,
…
,
x
i
+
1
,
x
i
,
x
j
+
1
,
…
,
x
n
.


## 3.3.1. Insertion Neighbourhood

The insertion neighborhood is defined as the set of solutions that can be reached by insertion move, which deletes one element of the solutionX and then inserts it to another place. For example, delete element x
i and insert it into the jth place; we obtain a new solution:(23)
X
′
=
x
1
,
x
2
,
…
,
x
i
-
1
,
x
i
+
1
,
…
,
x
j
-
1
,
x
j
,
x
i
,
x
j
+
1
,
…
,
x
n
.According to the element selected (customer or depot) and the position it is inserted in, there are four cases:(a)
Ifx
i and x
j are both customers, then customer x
i is reassigned to the DC that customer x
j is assigned to.
(b)
Ifx
i and x
j are both DCs, then reassign the customers previously assigned to the DC nearest before it. Close DC x
j and assign its customers to DC x
i.
(c)
Ifx
i is a customer and x
j is a DC, then customer x
i is reassigned to DC x
j.
(d)
Ifx
i is a DC and x
j is a customer, reassign customers that are nearest after customer x
j to DC x
i. All customers assigned to DC x
i are reassigned to the DC nearest before it.


## 3.3.2. Swap Neighbourhood

The swap neighbourhood, a set of solutions, contains the solutions that can be reached by performing a swap move, which exchanges the places of two different elements of solutionX. For example, exchange element x
i and element x
j of X; the resulting new solution is (24)
X
′
=
x
1
,
x
2
,
…
,
x
i
-
1
,
x
j
,
x
i
+
1
,
…
,
x
j
-
1
,
x
i
,
x
j
+
1
,
…
,
x
n
.Similar to the insert move, the swap move has also four cases:(e)
Ifx
i and x
j are both customers, then we exchange the two DCs they are currently assigned to and obtain two new customer-DC assignments.
(f)
Ifx
i and x
j are both DCs, then we exchange all the customers currently assigned to them.
(g)
Ifx
i is a customer and x
j is a DC, then the customers after x
i assigned to the same DC are reassigned to DC x
j, and customer x
i is reassigned to the DC nearest before DC x
j. All customers previously assigned to DC x
j will be reassigned to the DC nearest before it.
(h)
Ifx
i is a DC and x
j is a customer, this case is similar to case g.


## 3.3.3.2-Opt Neighbourhood

With the consideration of vehicle capacity, in our definition, the 2-opt neighbourhood contains the solutions that can be obtained by selecting two customers ofX (e.g., x
i and x
j) and then reversing the substring in the solution representation between them, the so-called 2-opt move. For example, applying 2-opt move to elements x
i and x
j, we obtain (25)
X
′
=
x
1
,
x
2
,
…
,
x
i
-
1
,
x
j
,
x
j
-
1
,
…
,
x
i
+
1
,
x
i
,
x
j
+
1
,
…
,
x
n
.


## 3.4. Tabu Search Framework

To increase the probability of obtaining high quality solutions, a diversification strategy is implemented. This strategy probabilistically accepts the second best solution in the search process while no better solution can be found in the neighborhoods of the current solution. By doing so, we can effectively diversify the search direction and thus more solution space will be explored. Consequently, better solution may be found. The computation results in Section4 prove this strategy. The proposed tabu search can be summarized as follows.Algorithm 4 (new tabu search).
Step  0. Input an initial feasible solution X
0 (see Section 3.2) and initialize I
t
e
r
≔
0, X
c
u
r
r
≔
X
0, and O
b
j
∗
≔
O
b
j
(
X
0
).Step  1. Explore the neighborhoods of X
c
u
r
r and denote the best solution in the neighborhoods, the best nontabu solution, and the second best nontabu solution as X
b
e
s
t, X
t
a
b
u
-
b
e
s
t, and X
t
a
b
u
-
2
n
d, respectively.Step  2. If O
b
j
(
X
b
e
s
t
)
<
O
b
j
∗, then set X
c
u
r
r
≔
X
b
e
s
t and add the corresponding move to tabu list; otherwise,ifO
b
j
(
X
t
a
b
u
-
b
e
s
t
)
<
O
b
j
(
X
c
u
r
r
), then X
c
u
r
r
≔
X
t
a
b
u
-
b
e
s
t and add the corresponding move to tabu list;
otherwise, probabilistically move to X
t
a
b
u
-
b
e
s
t or X
t
a
b
u
-
2
n
d, X
c
u
r
r
≔
P
r
o
b
{
X
t
a
b
u
-
b
e
s
t
,
X
t
a
b
u
-
2
n
d
}, and add the corresponding move to tabu list.Step  3. I
t
e
r
≔
I
t
e
r
+
1; If no stopping criterion is reached, return to Step  1.Step  4. Output the best solution objective function value O
b
j
∗.In the proposed tabu search algorithm, Iter counts the number of iterations andX
0 represents the initial solution obtained by greedy nearest neighbour method (Section 3.2). X
c
u
r
r denotes the current solution. O
b
j
∗ is the objective function value corresponding to the best solution found so far. The function O
b
j
(
X
) represents the objective function value of solution X.In Step  2, comparing with the current solutionX
c
u
r
r if no better solution can be found in its neighbourhood, we need to probabilistically move X
c
u
r
r to X
t
a
b
u
-
b
e
s
t or X
t
a
b
u
-
2
n
d. In implementation, we randomly generate a value β in interval [
0
,
1
]. If β
≥
λ, then X
c
u
r
r is moved to X
t
a
b
u
-
b
e
s
t; and otherwise X
c
u
r
r is moved to X
t
a
b
u
-
2
n
d, where λ is a given parameter.At each iteration of the tabu search procedure, the best admissible nontabu insertion, swap or 2-opt move is performed. The two elements of solutionX
c
u
r
r involved in such move are declared as tabu-active, which is forbidden to be removed in the next t iterations. t is the tabu-tenure parameter selected randomly from a range [T
m
i
n, T
m
a
x].The tabu search iteration is terminated if the maximum number of iterations maxIter is reached or if the best solution found so far has been improved in successive SucIter iteration.


## 4. Computational Results

The proposed tabu search algorithm was coded in the C program and ran on a computer with Intel(R) Core(TM) CPU (3.2 GHz) with 4 GB of RAM under the Microsoft Windows 7 operation system.


### 4.1. Test Beds

Two test beds were used to evaluate the performance of the proposed tabu search algorithms:(1)
The benchmarks of CLRP (Prins et al. [31]), which contains 30 instances: two potential distribution center sizes |
J
|
=
5 or 10 are considered. The number of customers is |
I
|
=
20, 50, 100, and 200. The customers and DCs are uniformly distributed in a [
1,50
]
×
[
1,50
] square. The fixed opening costs of DCs are randomly generated from interval [
5000,125000
]. The traveling cost between two nodes equals their Euclidean distance multiplied by 100 and rounded up to the next integer. The setup cost of a vehicle is 1000. The vehicle capacity Q equals 70 or 150. Customers’ demands are randomly selected from interval [
11,20
].
(2)
Randomly generated LIRP-FRL instances: based on the data of CLRP benchmarks and using the setting of [25] for the parameters, such as the order cost of new products of DCs A
m (=200), the order cost of recovered products of DCs A
r (=100), the cost of manufacturing c
m (=60), recovering c
r (=50), disposal c
d (−10), and the return rate of product, we randomly generate the LIRP-FRL instances as follows:
(i)
The holding cost for each distribution center is uniformly distributed inU
[
5,10
].
(ii)
The transportation cost per unit product of the distribution center at sitej, j
∈
J, is uniformly distributed in U
[
1,10
].


### 4.2. Parameter Settings

The maximum number of iterations for NTS maxIter is set to 10000 and the search iteration is terminated if the best upper bound has not been improved in successive 800 iteration (SusIter = 800). Parameterλ is uniformly distributed in U
[
0.01,0.8
]. The lower and upper bound of tabu-tenure T
m
i
n and T
m
a
x are set to 5 and 12, respectively.


### 4.3. Numerical Results

To evaluate the performance of the proposed new tabu search (NTS), we compare it with the classical tabu search algorithm (denoted as TS in following discussion) in terms of the best upper bound (UB) found so far and the corresponding computational time in CPU seconds (time). Moreover, the parameter settings of TS is the same as NTS’s except parameterλ that TS did not have. Computational results on CLRP benchmarks are listed in Table 1. The column BKS is the best known solution objective function value reported in the literature. Gap is calculated by the following formula: G
a
p
=
100
∗
(
U
B
-
B
K
S
)
/
U
B. DEV is the deviation of the gap of NTS from the gap of TS; that is, D
E
V
=
G
a
p
N
T
S
-
G
a
p
T
S.Table 1
Computational results on CLRP benchmarks.
Problem
|
I
|
|
J
|
Q
BKS
TS
NTS
DEV
UB
Gap
Time
UB
Gap
Time
P1
20
5
70
54793
54793
0.00
0.12
54793
0.00
0.49
0.00
P2
20
5
150
39104
39104
0.00
0.12
39104
0.00
0.69
0.00
P3
20
5
70
48908
48908
0.00
0.50
48908
0.00
0.53
0.00
P4
20
5
150
37542
37611
0.18
0.37
37611
0.18
0.74
0.00
P5
50
5
70
90111
90806
0.77
2.58
90461
0.39
3.35
−0.38
P6
50
5
150
63242
65010
2.80
10.43
63242
0.00
11.73
−2.80
P7
50
5
70
88298
89688
1.57
22.07
88643
0.39
23.94
−1.18
P8
50
5
150
67340
68071
1.09
7.48
67340
0.00
11.16
−1.09
P9
50
5
70
84055
84227
0.20
14.13
84110
0.07
16.96
−0.13
P10
50
5
150
51822
51902
0.15
10.21
51883
0.12
13.49
−0.03
P11
50
5
70
86203
86223
0.02
9.20
86203
0.00
14.71
−0.02
P12
50
5
150
61830
61978
0.24
19.54
61830
0.00
21.49
−0.24
P13
100
5
70
275993
281229
1.90
11.51
278926
1.05
38.41
−0.85
P14
100
5
150
214392
218886
2.10
9.52
216802
1.11
29.74
−0.99
P15
100
5
70
194598
196587
1.02
145.25
196436
0.94
95.16
−0.08
P16
100
5
150
157173
159244
1.32
180.38
158720
0.97
124.63
−0.35
P17
100
5
70
200246
203297
1.52
126.12
202682
1.20
110.85
−0.32
P18
100
5
150
152586
157859
3.46
122.47
156049
2.22
105.26
−1.24
P19
100
10
70
290429
334486
15.17
97.80
294774
1.47
143.2
−13.70
P20
100
10
150
234641
285303
21.59
75.87
236217
0.67
113.6
−20.92
P21
100
10
70
244265
257455
5.40
103.49
248003
1.51
139.85
−3.89
P22
100
10
150
203988
216253
6.01
69.65
208455
2.14
107
−3.87
P23
100
10
70
253344
291153
14.92
169.98
258221
1.89
153.53
−13.03
P24
100
10
150
204597
220528
7.79
67.06
209390
2.29
131.52
−5.50
P25
200
10
70
479425
518815
8.22
347.64
491097
2.43
554.88
−5.79
P26
200
10
150
378773
408401
7.82
469.61
384126
1.39
799.75
−6.43
P27
200
10
70
450468
494247
9.72
491.36
461810
2.46
1101.8
−7.26
P28
200
10
150
374435
396998
6.03
339.17
380004
1.47
775.62
−4.56
P29
200
10
70
472898
485672
2.70
397.96
479708
1.42
776.73
−1.28
P30
200
10
150
364178
374923
2.95
358.23
372971
2.36
919.82
−0.59
Average
4.22
122.66
1.00
211.35
−3.22Using the diversification strategy of probabilistically accepting the second best solution, the NTS increases the probability of exploring more solution space. As a result, the NTS takes more computational time than the TS. However, from Table1, we can observe that although the average computational time of NTS is about two times that of TS, it is still in a very acceptable range. The NTS provides more competitive upper bound than the TS. The average gap between the best upper bound found so far by NTS and the best known upper bound in the literature is about 1.00%, compared to the 4.22% of the TS. The NTS outperforms the TS in the quality of solutions obtained with the average deviation of the gap DEV = −3.22%.Table2 reports the computational results on test bed of randomly generated LIRP-FRL instances. From the table, we can also find that the NTS performs better than the classic TS with an average gap between the best upper bound of NTS and that of TS, about −2.79%. The average computational time of NTS is slightly bigger than that of TS.Table 2
Computational results on LIRP-FRL instances.
Prob. ID
|
I
|
|
J
|
Q
TS
NTS
∗Gap 1 (%)
UB
Time
UB
Time
P1
20
5
70
67528
0.50
67528
0.53
0.00
P2
20
5
150
42867
0.55
42867
0.61
0.00
P3
20
5
70
60021
0.46
60021
0.65
0.00
P4
20
5
150
40255
0.57
40255
0.62
0.00
P5
50
5
70
115984
22.56
115534
22.95
−0.39
P6
50
5
150
84468
36.43
84401
34.18
−0.08
P7
50
5
70
117828
22.56
117530
24.06
−0.25
P8
50
5
150
96633
21.61
96161
21.64
−0.49
P9
50
5
70
112493
24.31
111625
24.51
−0.78
P10
50
5
150
82667
23.01
82392
24.66
−0.33
P11
50
5
70
108639
21.28
108568
20.32
−0.07
P12
50
5
150
82938
21.58
82804
22.07
−0.16
P13
100
5
70
342786
139.24
342309
139.97
−0.14
P14
100
5
150
276104
137.64
273409
138.72
−1.37
P15
100
5
70
239544
143.75
238937
158.07
−0.25
P16
100
5
150
201533
125.58
200708
135.06
−0.41
P17
100
5
70
250239
121.28
249565
124.88
−0.27
P18
100
5
150
198842
126.84
197310
128.30
−0.78
P19
100
10
70
406342
138.30
396469
161.50
−2.49
P20
100
10
150
368668
138.84
339644
157.86
−8.55
P21
100
10
70
328174
121.59
320363
151.15
−2.44
P22
100
10
150
278729
128.50
274026
134.76
−1.72
P23
100
10
70
388259
113.47
320651
143.94
−21.08
P24
100
10
150
339851
120.77
283008
136.13
−20.09
P25
200
10
70
645014
393.75
629604
525.43
−2.45
P26
200
10
150
558189
368.91
528721
510.52
−5.57
P27
200
10
70
627737
427.91
611151
542.92
−2.71
P28
200
10
150
543988
379.41
517132
432.50
−5.19
P29
200
10
70
607894
419.25
598889
428.33
−1.50
P30
200
10
150
530675
422.72
509796
563.14
−4.10
Average
138.77
163.67
−2.79
∗Gap 1 (%) = 100 ∗ (H2 solution value − H1 solution value)/H2 solution value.


### 4.4. Sensitivity Analysis

Sensitivity analysis is also conducted to investigate the effects on the total costs when the input parameters such as the return rate(r) or the rate between the unit producing cost of new products and recovered products (c
m
:
c
r) changes.Table3 reports the computational results when the product return rate is changed for each randomly generated instance. To manifest the trend more clearly, for each return rate value, we calculate the arithmetic average objective function values of all tested instances. The results are shown in Figure 3. From the figure, we can find that the total costs decrease with the increase of return rate r. Focusing on those products with high return rate can effectively reduce the system costs.Table 3
Results of different return rates.
Prob. ID
r
|
I
|
|
J
|
Q
TS
NTS
Gap 1 (%)
UB
Time
UB
Time
P1
0.1
20
5
70
67617
3.22
67617
2.66
0.00
0.2
67522
3.38
67522
3.48
0.00
0.3
67423
3.64
67423
3.14
0.00
0.4
67568
2.73
67320
3.28
−0.37
0.5
67293
4.69
67211
3.22
−0.12
0.6
67094
3.26
67094
2.95
0.00
0.7
66966
3.19
66966
2.77
0.00
0.8
66904
3.15
66822
3.67
−0.12
0.9
66646
2.68
66646
3.15
0.00
P2
0.1
20
5
150
42972
2.54
42972
2.87
0.00
0.2
42969
2.43
42969
2.96
0.00
0.3
42965
3.07
42965
2.57
0.00
0.4
42961
3.40
42961
2.66
0.00
0.5
42955
3.00
42955
3.18
0.00
0.6
42948
2.63
42948
2.92
0.00
0.7
42939
2.68
42939
3.08
0.00
0.8
42927
2.66
42927
3.02
0.00
0.9
42908
2.47
42908
3.04
0.00
P3
0.1
20
5
70
61544
2.70
61296
2.68
−0.40
0.2
61175
3.14
61175
3.40
0.00
0.3
61050
2.68
61050
2.99
0.00
0.4
61011
3.16
60921
2.91
−0.15
0.5
60786
2.62
60786
2.98
0.00
0.6
60733
2.55
60644
2.81
−0.15
0.7
60492
2.99
60492
3.23
0.00
0.8
60325
2.87
60325
3.10
0.00
0.9
60308
3.18
60127
3.19
−0.30
P4
0.1
20
5
150
40396
2.56
40396
2.71
0.00
0.2
40395
2.58
40395
2.63
0.00
0.3
40393
2.64
40393
2.94
0.00
0.4
40390
2.68
40390
2.41
0.00
0.5
40386
2.66
40386
3.12
0.00
0.6
40381
2.53
40381
2.46
0.00
0.7
40373
2.68
40373
2.66
0.00
0.8
40363
2.46
40363
2.63
0.00
0.9
40346
2.88
40346
2.61
0.00
P5
0.1
50
5
70
117680
36.19
116409
34.62
−1.08
0.2
115813
32.65
115115
31.58
−0.60
0.3
114965
30.64
114542
31.43
−0.37
0.4
115279
30.7
114927
31.34
−0.31
0.5
116446
26.22
115078
30.92
−1.17
0.6
114151
30.48
114039
31.18
−0.10
0.7
114504
31.34
114190
32.04
−0.27
0.8
115578
28.66
114239
26.56
−1.16
0.9
112326
31.31
112310
33.62
−0.01
P6
0.1
50
5
150
87885
20.30
87678
24.04
−0.24
0.2
87289
23.82
86748
27.87
−0.62
0.3
88191
23.95
87140
24.59
−1.19
0.4
89497
20.47
86970
23.87
−2.82
0.5
87240
21.81
86955
24.84
−0.33
0.6
87233
24.34
86283
24.26
−1.09
0.7
86366
24.17
86173
21.05
−0.22
0.8
85494
22.81
84771
24.78
−0.85
0.9
84673
23.93
84358
24.24
−0.37
P7
0.1
50
5
70
122232
26.84
121605
22.23
−0.51
0.2
121038
26.14
120826
26.16
−0.18
0.3
121147
26.17
120530
26.66
−0.51
0.4
120239
26.41
119945
26.86
−0.24
0.5
120223
26.11
119788
26.03
−0.36
0.6
119636
26.05
119545
28.81
−0.08
0.7
119795
25.50
119440
32.04
−0.30
0.8
119994
26.05
119100
27.80
−0.75
0.9
119728
25.72
118222
27.31
−1.26
P8
0.1
50
5
150
99470
26.38
99178
27.75
−0.29
0.2
99455
25.21
99319
25.61
−0.14
0.3
100163
28.65
98682
21.78
−1.48
0.4
98722
25.14
98642
25.32
−0.08
0.5
98930
25.27
98617
27.10
−0.32
0.6
98131
24.90
98056
26.23
−0.08
0.7
98723
25.60
97815
23.55
−0.92
0.8
97633
25.78
97296
33.13
−0.35
0.9
97752
25.43
96882
26.07
−0.89
P9
0.1
50
5
70
86438
25.22
86398
29.74
−0.05
0.2
86031
22.20
85926
28.47
−0.12
0.3
86300
25.01
85635
21.50
−0.77
0.4
85292
21.61
85283
22.87
−0.01
0.5
85084
24.46
84834
28.05
−0.29
0.6
84628
23.10
84495
28.72
−0.16
0.7
84358
24.98
84116
22.87
−0.29
0.8
83239
21.88
83103
21.64
−0.16
0.9
83386
22.48
82806
25.97
−0.70
P10
0.1
50
5
150
115321
25.76
115143
28.26
−0.15
0.2
114968
26.16
114609
21.55
−0.31
0.3
114628
27.12
114347
24.59
−0.25
0.4
114620
26.62
113993
27.86
−0.55
0.5
114243
25.93
113821
27.95
−0.37
0.6
113720
26.05
113461
29.29
−0.23
0.7
113367
22.95
113204
28.36
−0.14
0.8
113157
26.73
112657
28.41
−0.44
0.9
112518
32.52
111908
26.90
−0.54
P11
0.1
50
5
70
112376
26.82
111843
32.35
−0.47
0.2
111582
25.94
111286
27.18
−0.27
0.3
111920
23.13
111054
29.51
−0.77
0.4
111642
24.91
110986
28.05
−0.59
0.5
111345
23.08
110891
27.75
−0.41
0.6
110712
26.11
110203
28.93
−0.46
0.7
110789
25.79
109949
29.03
−0.76
0.8
110232
25.79
109923
28.18
−0.28
0.9
109797
24.80
109042
32.89
−0.69
P12
0.1
50
5
150
85505
24.69
85246
27.45
−0.30
0.2
85187
24.25
85019
23.92
−0.20
0.3
84879
24.73
84757
24.78
−0.14
0.4
84797
28.33
84337
30.83
−0.54
0.5
84312
25.84
83955
28.38
−0.42
0.6
84053
26.65
83933
21.82
−0.14
0.7
83933
26.31
83358
31.33
−0.69
0.8
83651
26.92
82897
29.92
−0.90
0.9
82655
23.22
82439
26.95
−0.26
P13
0.1
100
5
70
343359
189.12
341812
146.89
−0.45
0.2
346569
187.44
343870
187.75
−0.78
0.3
345210
169.49
342124
141.65
−0.89
0.4
348100
180.08
345668
190.9
−0.70
0.5
349269
159.25
343318
184.88
−1.70
0.6
347719
182.23
343891
162.19
−1.10
0.7
349525
182.84
342643
169.88
−1.97
0.8
349171
160.17
341151
158.68
−2.30
0.9
351251
182.08
349382
186.92
−0.53
P14
0.1
100
5
150
282054
135.84
281389
190.02
−0.24
0.2
281199
128.94
279541
151.39
−0.59
0.3
279903
155.98
279153
160.32
−0.27
0.4
278748
161.52
277988
130.87
−0.27
0.5
279806
152.32
278460
162.29
−0.48
0.6
280003
188.32
279155
127.99
−0.30
0.7
280823
126.66
278542
171.61
−0.81
0.8
276206
136.94
275974
138.12
−0.08
0.9
276528
157.65
275917
163.14
−0.22
P15
0.1
100
5
70
246010
156.28
245337
148.54
−0.27
0.2
245120
175.84
244537
172.42
−0.24
0.3
244563
154.52
243754
154.32
−0.33
0.4
243537
154.53
243124
133.88
−0.17
0.5
242570
120.21
241529
192.88
−0.43
0.6
241778
171.75
241435
150.70
−0.14
0.7
240726
153.04
240237
138.58
−0.20
0.8
239819
149.01
239716
153.79
−0.04
0.9
238793
145.75
238624
144.34
−0.07
P16
0.1
100
5
150
209027
131.28
208711
153.17
−0.15
0.2
208060
149.78
207229
157.39
−0.40
0.3
206328
167.99
205454
200.44
−0.42
0.4
207220
154.39
205877
195.70
−0.65
0.5
206676
163.29
205654
172.25
−0.49
0.6
204833
137.78
204547
168.87
−0.14
0.7
204402
137.86
204284
153.95
−0.06
0.8
203509
173.04
203068
191.72
−0.22
0.9
203695
153.95
201648
146.62
−1.00
P17
0.1
100
5
70
259816
195.04
258025
149.48
−0.69
0.2
258004
164.99
256937
193.31
−0.41
0.3
256120
124.51
256057
123.60
−0.02
0.4
254658
130.21
254594
150.79
−0.03
0.5
254764
133.42
253722
165.32
−0.41
0.6
255047
155.20
252587
151.01
−0.96
0.7
250732
153.72
249812
149.22
−0.37
0.8
253732
182.23
249612
167.72
−1.62
0.9
252906
168.49
249337
157.79
−1.41
P18
0.1
100
5
150
204826
145.28
204678
191.50
−0.07
0.2
205474
172.75
204621
193.28
−0.42
0.3
203254
167.53
202691
155.11
−0.28
0.4
203120
148.82
201380
121.34
−0.86
0.5
202003
122.00
201329
145.70
−0.33
0.6
200401
145.62
199858
151.80
−0.27
0.7
199032
147.58
198618
155.51
−0.21
0.8
198858
153.76
197776
145.95
−0.54
0.9
199502
134.57
197513
150.85
−1.00
P19
0.1
100
10
70
414613
171.01
401365
198.5
−3.20
0.2
413680
164.18
400546
204.34
−3.17
0.3
420538
167.47
399896
195.42
−4.91
0.4
414460
154.11
394054
202.68
−4.92
0.5
411688
158.96
395828
211.36
−3.85
0.6
412339
162.17
394750
213.73
−4.27
0.7
410641
163.97
394617
210.72
−3.90
0.8
409561
181.48
394513
218.27
−3.67
0.9
408967
178.1
394294
201.13
−3.59
P20
0.1
100
10
150
365982
113.65
362144
114.33
−1.05
0.2
365164
111.79
361157
142.29
−1.10
0.3
365868
117.97
349578
113.22
−4.45
0.4
365307
145.30
349277
144.62
−4.39
0.5
366266
115.01
348378
158.55
−4.88
0.6
363989
151.05
348198
117.37
−4.34
0.7
113367
22.95
113204
28.36
−0.14
0.8
113157
26.73
112657
28.41
−0.44
0.9
112518
32.52
111908
26.90
−0.54
P21
0.1
100
10
70
330001
132.05
323564
131.91
−1.95
0.2
329657
155.75
322848
178.39
−2.07
0.3
329303
166.30
322162
176.31
−2.17
0.4
328939
160.91
321756
167.07
−2.18
0.5
328561
167.71
321589
152.01
−2.12
0.6
328166
166.06
321183
182.85
−2.13
0.7
327744
132.12
321102
174.83
−2.03
0.8
327281
133.30
320160
179.93
−2.18
0.9
326742
134.59
319244
188.47
−2.29
P22
0.1
100
10
150
281700
140.71
278464
129.13
−1.15
0.2
285498
140.01
278181
179.95
−2.56
0.3
285035
128.87
277760
184.58
−2.55
0.4
282821
157.09
277349
159.42
−1.93
0.5
284563
129.31
277133
181.07
−2.61
0.6
284057
152.07
276776
183.34
−2.56
0.7
280960
129.57
276530
172.01
−1.58
0.8
282955
157.32
276208
181.27
−2.38
0.9
278306
132.02
273261
178.52
−1.81
P23
0.1
100
10
70
399113
125.10
375576
164.77
−5.90
0.2
396761
146.84
371533
160.97
−6.36
0.3
397280
168.97
360348
155.58
−9.30
0.4
396341
139.25
347788
175.99
−12.25
0.5
393942
143.91
346723
183.96
−11.99
0.6
392957
153.30
344273
145.58
−12.39
0.7
393378
159.10
325508
172.95
−17.25
0.8
390858
130.43
325392
172.15
−16.75
0.9
391111
140.30
322910
167.81
−17.44
P24
0.1
100
10
150
297873
126.28
296530
138.04
−0.45
0.2
295735
139.68
294394
164.50
−0.45
0.3
334584
138.60
292118
173.75
−12.69
0.4
334011
152.64
288251
183.57
−13.70
0.5
345871
130.23
287245
142.65
−16.95
0.6
343622
150.07
286258
149.21
−16.69
0.7
344063
132.18
285833
132.30
−16.92
0.8
343388
151.00
285505
145.31
−16.86
0.9
342624
161.02
276622
165.18
−19.26
P25
0.1
200
10
70
665405
1003.37
646837
1358.56
−2.79
0.2
663368
1022.24
646011
1275.81
−2.62
0.3
662357
840.78
645933
1052.16
−2.48
0.4
660795
819.73
643790
900.59
−2.57
0.5
660155
819.55
641200
1170.31
−2.87
0.6
657577
835.74
640619
1172.54
−2.58
0.7
655423
831.23
640582
851.98
−2.26
0.8
654409
830.95
637338
858.12
−2.61
0.9
653286
792.33
622908
836.45
−4.65
P26
0.1
200
10
150
573667
753.47
553421
1069.24
−3.53
0.2
570023
765.06
551891
1297.82
−3.18
0.3
569666
776.15
537807
1069.80
−5.59
0.4
567939
797.95
535782
1163.39
−5.66
0.5
564777
900.56
535225
1108.99
−5.23
0.6
564413
887.18
535083
1195.13
−5.20
0.7
562167
849.13
531505
1236.66
−5.45
0.8
560098
799.95
514584
1157.03
−8.13
0.9
557554
864.90
513652
1023.90
−7.87
P27
0.1
200
10
70
661785
1384.45
631700
1228.42
−4.55
0.2
662602
1317.90
630853
969.39
−4.79
0.3
647333
1144.41
630036
1119.12
−2.67
0.4
647377
1238.22
625782
1060.19
−3.34
0.5
647837
955.81
625659
1159.76
−3.42
0.6
651234
972.11
624175
1104.26
−4.16
0.7
643657
994.18
623635
1203.08
−3.11
0.8
648507
1007.51
618926
1251.66
−4.56
0.9
640631
974.55
617253
1352.17
−3.65
P28
0.1
200
10
150
560151
1039.68
554838
901.12
−0.95
0.2
567066
805.96
552250
1205.61
−2.61
0.3
565177
1107.27
551150
1429.66
−2.48
0.4
551554
1150.46
546455
1283.46
−0.92
0.5
550006
845.09
546211
901.12
−0.69
0.6
548151
679.59
543161
850.63
−0.91
0.7
546181
835.08
539990
965.50
−1.13
0.8
545049
869.30
538293
1444.22
−1.24
0.9
543203
937.76
522946
1065.27
−3.73
P29
0.1
200
10
70
621423
1031.98
619749
810.58
−0.27
0.2
624921
755.35
618833
817.09
−0.97
0.3
620040
711.57
617782
991.29
−0.36
0.4
617601
867.88
615738
958.45
−0.30
0.5
623408
1135.24
614301
1168.53
−1.46
0.6
614480
799.56
612048
1337.13
−0.40
0.7
612960
1095.73
611365
948.58
−0.26
0.8
611261
1126.74
609791
969.75
−0.24
0.9
609581
846.60
608927
712.33
−0.11
P30
0.1
200
10
150
522946
935.56
520709
1214.20
−0.43
0.2
521952
696.92
518710
871.10
−0.62
0.3
520505
730.31
516812
1182.22
−0.71
0.4
519262
780.89
516352
1289.81
−0.56
0.5
517999
707.29
516019
1335.97
−0.38
0.6
516930
1052.88
515388
1212.71
−0.30
0.7
515604
954.61
513938
1054.47
−0.32
0.8
514221
687.26
511705
1073.18
−0.49
0.9
497335
1020.75
492080
1113.48
−1.06Figure 3
Results of different return rates.Table4 shows the numerical results when the rate between the cost of producing a new product and that of recovering a damaged or old product varies. For each rate, we average the best upper bound obtained for all tested instances. The results are depicted in Figure 4. From the figure, we can observe that the total costs decrease with the increase of the rate. That means reducing the unit recovering cost of product can effectively reduce the total costs, which indicates us to retrieve those subnew products or to improve repairing technique so as to reduce recovering cost.Table 4
Results of different rate between the cost of recovered products and the cost of new products.
Prob. ID
c
m
:
c
r
|
I
|
|
J
|
Q
TS
NTS
Gap 1 (%)
UB
Time
UB
Time
P1
1
20
5
70
68142
3.00
68142
2.78
0.00
1.25
67402
2.68
67402
2.39
0.00
1.5
67211
2.14
66964
2.61
−0.37
1.75
66898
3.15
66649
2.54
−0.37
2
66496
2.76
66414
2.79
−0.12
P2
1
20
5
150
43008
3.33
43008
2.35
0.00
1.25
42964
3.11
42964
2.54
0.00
1.5
42934
2.49
42934
2.22
0.00
1.75
42913
2.40
42913
3.15
0.00
2
42897
3.55
42897
3.19
0.00
P3
1
20
5
70
61680
2.72
61680
2.82
0.00
1.25
61028
2.46
61028
2.81
0.00
1.5
60595
2.47
60595
2.54
0.00
1.75
60367
2.59
60285
2.71
−0.14
2
60132
2.52
60052
2.50
−0.13
P4
1
20
5
150
40458
2.45
40458
2.05
0.00
1.25
40391
2.18
40391
2.36
0.00
1.5
40346
2.86
40346
2.96
0.00
1.75
40314
2.69
40314
2.32
0.00
2
40290
1.92
40290
2.28
0.00
P5
1
50
5
70
117832
26.39
116378
25.98
−1.23
1.25
117029
25.68
114692
26.63
−2.00
1.5
115617
26.14
114374
25.88
−1.08
1.75
115126
26.70
114022
26.30
−0.96
2
113413
25.84
112590
25.75
−0.73
P6
1
50
5
150
90053
22.94
87484
20.19
−2.85
1.25
88307
24.22
86991
20.15
−1.49
1.5
87796
23.82
86910
23.21
−1.01
1.75
86976
20.81
86535
22.24
−0.51
2
86703
22.88
86394
17.23
−0.36
P7
1
50
5
70
123939
18.23
122295
21.88
−1.33
1.25
121637
19.25
120958
16.91
−0.56
1.5
120474
18.75
119532
20.84
−0.78
1.75
119790
21.88
118308
21.61
−1.24
2
118183
16.95
117858
21.77
−0.27
P8
1
50
5
150
100524
17.41
100439
25.51
−0.08
1.25
99371
28.59
99067
29.73
−0.31
1.5
98231
24.37
97807
29.53
−0.43
1.75
97514
24.48
96608
22.80
−0.93
2
96942
25.15
96560
17.95
−0.39
P9
1
50
5
70
117880
27.00
115956
22.17
−1.63
1.25
116053
30.39
114876
35.22
−1.01
1.5
114690
24.03
113420
28.06
−1.11
1.75
113128
19.20
112769
28.95
−0.32
2
112006
28.62
111756
26.96
−0.22
P10
1
50
5
150
88057
23.26
87883
31.21
−0.20
1.25
86485
25.83
86222
31.48
−0.30
1.5
85367
31.62
84589
19.58
−0.91
1.75
83386
26.10
83478
22.37
0.11
2
83455
25.45
83235
21.90
−0.26
P11
1
50
5
70
114793
20.04
112544
25.68
−1.96
1.25
112136
19.99
111395
27.60
−0.66
1.5
111087
20.16
111062
29.96
−0.02
1.75
110640
27.13
109472
22.12
−1.06
2
110405
22.60
108934
26.43
−1.33
P12
1
50
5
150
87232
24.63
86433
29.55
−0.04
1.25
86410
22.09
86199
18.89
−0.57
1.5
85173
27.98
83868
19.14
−1.94
1.75
84523
21.53
83656
15.63
−2.18
2
83027
18.38
82912
20.22
−1.46
P13
1
100
5
70
364895
155.68
361755
159.32
−0.86
1.25
363309
160.69
360230
160.93
−0.85
1.5
362096
163.84
359999
168.78
−0.58
1.75
359974
157.96
356857
141.78
−0.87
2
355624
156.57
339404
161.89
−4.56
P14
1
100
5
150
305053
164.11
300033
139.62
−1.65
1.25
303135
141.89
296364
121.95
−2.23
1.5
301834
139.24
295118
121.68
−2.23
1.75
298777
139.76
294442
133.88
−1.45
2
291740
133.99
276706
135.66
−5.15
P15
1
100
5
70
296619
124.99
258199
125.21
−12.95
1.25
260317
137.47
254461
128.82
−2.25
1.5
249922
115.05
247152
183.34
−1.11
1.75
249195
132.22
244535
154.43
−1.87
2
247529
149.44
241351
171.13
−2.50
P16
1
100
5
150
233346
120.31
223398
126.11
−4.26
1.25
229687
129.75
220760
114.91
−3.89
1.5
226932
127.63
218861
117.39
−3.56
1.75
216624
137.42
214174
115.09
−1.13
2
211223
128.79
205238
122.39
−2.83
P17
1
100
5
70
267713
134.93
265309
110.60
−0.90
1.25
266067
132.17
262547
122.34
−1.32
1.5
263994
130.92
260267
110.49
−1.41
1.75
261711
116.78
259735
150.61
−0.76
2
260804
170.99
252673
124.40
−3.12
P18
1
100
5
150
226178
124.86
224348
139.70
−0.81
1.25
223053
127.08
219578
134.79
−1.56
1.5
220970
115.28
218823
184.85
−0.97
1.75
219154
158.19
216341
129.00
−1.28
2
217751
159.37
209257
182.73
−3.90
P19
1
100
10
70
412240
135.46
409643
141.11
−0.63
1.25
406518
139.13
403969
173.98
−0.63
1.5
404199
137.06
401006
167.12
−0.79
1.75
403475
136.64
400046
178.88
−0.85
2
401608
136.54
394231
149.81
−1.84
P20
1
100
10
150
366576
105.10
364188
166.50
−0.65
1.25
364342
123.15
362564
100.25
−0.49
1.5
360397
153.27
358732
143.08
−0.46
1.75
357502
158.04
356178
114.59
−0.37
2
350419
100.43
345948
154.21
−1.28
P21
1
100
10
70
337749
113.31
334240
100.11
−1.04
1.25
333248
114.45
330768
112.04
−0.74
1.5
330981
127.66
329900
133.01
−0.33
1.75
329982
143.46
325218
139.32
−1.44
2
327911
189.02
322382
150.34
−1.69
P22
1
100
10
150
300245
112.22
297406
94.24
−0.95
1.25
293642
127.66
291212
119.95
−0.83
1.5
290938
186.05
287471
192.95
−1.19
1.75
288716
183.72
285885
127.07
−0.98
2
286473
132.29
281933
125.07
−1.58
P23
1
100
10
70
369343
127.38
364871
132.22
−1.21
1.25
364871
152.70
359677
141.96
−1.42
1.5
359613
147.70
355286
152.78
−1.20
1.75
358094
155.05
354980
142.97
−0.87
2
341610
146.96
320343
172.26
−6.23
P24
1
100
10
150
328663
124.91
299018
132.71
−9.02
1.25
325042
125.13
295553
137.29
−9.07
1.5
323847
156.83
291860
135.43
−9.88
1.75
299214
135.60
288433
157.16
−3.60
2
294706
121.22
281938
168.67
−4.33
P25
1
200
10
70
665281
829.11
653633
1026.07
−1.75
1.25
657935
834.27
652114
1061.26
−0.88
1.5
655818
823.79
651574
984.23
−0.65
1.75
649604
820.10
646761
1055.81
−0.44
2
642489
820.87
641864
1139.61
−0.10
P26
1
200
10
150
581623
611.52
580270
618.26
−0.23
1.25
579961
608.25
569283
626.20
−1.84
1.5
574684
604.60
536008
613.79
−6.73
1.75
556955
621.66
535570
623.55
−3.84
2
554052
621.92
528999
622.53
−4.52
P27
1
200
10
70
773781
793.09
662523
778.08
−14.38
1.25
713012
819.64
655573
803.25
−8.06
1.5
681260
804.27
642081
739.51
−5.75
1.75
635834
770.17
632602
723.11
−0.51
2
632061
739.14
623493
704.85
−1.36
P28
1
200
10
150
576983
666.69
555923
987.24
−3.65
1.25
568736
675.82
546433
859.83
−3.92
1.5
564064
674.70
543330
859.83
−3.68
1.75
560726
914.60
535818
761.02
−4.44
2
534830
977.03
522356
795.76
−2.33
P29
1
200
10
70
666957
790.82
636582
820.80
−4.55
1.25
658832
832.47
633813
1119.70
−3.80
1.5
653454
1149.63
621988
965.82
−4.82
1.75
622078
801.89
619907
825.17
−0.35
2
616051
863.47
608644
1080.37
−1.20
P30
1
200
10
150
542071
734.01
540384
705.36
−0.31
1.25
525159
727.55
524172
786.56
−0.19
1.5
521758
716.37
510933
763.03
−2.07
1.75
518474
787.04
506479
752.31
−2.31
2
515142
755.66
502884
698.85
−2.38Figure 4
Results of different rate between the cost of recovered products and the cost of new products.


## 4.1. Test Beds

Two test beds were used to evaluate the performance of the proposed tabu search algorithms:(1)
The benchmarks of CLRP (Prins et al. [31]), which contains 30 instances: two potential distribution center sizes |
J
|
=
5 or 10 are considered. The number of customers is |
I
|
=
20, 50, 100, and 200. The customers and DCs are uniformly distributed in a [
1,50
]
×
[
1,50
] square. The fixed opening costs of DCs are randomly generated from interval [
5000,125000
]. The traveling cost between two nodes equals their Euclidean distance multiplied by 100 and rounded up to the next integer. The setup cost of a vehicle is 1000. The vehicle capacity Q equals 70 or 150. Customers’ demands are randomly selected from interval [
11,20
].
(2)
Randomly generated LIRP-FRL instances: based on the data of CLRP benchmarks and using the setting of [25] for the parameters, such as the order cost of new products of DCs A
m (=200), the order cost of recovered products of DCs A
r (=100), the cost of manufacturing c
m (=60), recovering c
r (=50), disposal c
d (−10), and the return rate of product, we randomly generate the LIRP-FRL instances as follows:
(i)
The holding cost for each distribution center is uniformly distributed inU
[
5,10
].
(ii)
The transportation cost per unit product of the distribution center at sitej, j
∈
J, is uniformly distributed in U
[
1,10
].


## 4.2. Parameter Settings

The maximum number of iterations for NTS maxIter is set to 10000 and the search iteration is terminated if the best upper bound has not been improved in successive 800 iteration (SusIter = 800). Parameterλ is uniformly distributed in U
[
0.01,0.8
]. The lower and upper bound of tabu-tenure T
m
i
n and T
m
a
x are set to 5 and 12, respectively.


## 4.3. Numerical Results

To evaluate the performance of the proposed new tabu search (NTS), we compare it with the classical tabu search algorithm (denoted as TS in following discussion) in terms of the best upper bound (UB) found so far and the corresponding computational time in CPU seconds (time). Moreover, the parameter settings of TS is the same as NTS’s except parameterλ that TS did not have. Computational results on CLRP benchmarks are listed in Table 1. The column BKS is the best known solution objective function value reported in the literature. Gap is calculated by the following formula: G
a
p
=
100
∗
(
U
B
-
B
K
S
)
/
U
B. DEV is the deviation of the gap of NTS from the gap of TS; that is, D
E
V
=
G
a
p
N
T
S
-
G
a
p
T
S.Table 1
Computational results on CLRP benchmarks.
Problem
|
I
|
|
J
|
Q
BKS
TS
NTS
DEV
UB
Gap
Time
UB
Gap
Time
P1
20
5
70
54793
54793
0.00
0.12
54793
0.00
0.49
0.00
P2
20
5
150
39104
39104
0.00
0.12
39104
0.00
0.69
0.00
P3
20
5
70
48908
48908
0.00
0.50
48908
0.00
0.53
0.00
P4
20
5
150
37542
37611
0.18
0.37
37611
0.18
0.74
0.00
P5
50
5
70
90111
90806
0.77
2.58
90461
0.39
3.35
−0.38
P6
50
5
150
63242
65010
2.80
10.43
63242
0.00
11.73
−2.80
P7
50
5
70
88298
89688
1.57
22.07
88643
0.39
23.94
−1.18
P8
50
5
150
67340
68071
1.09
7.48
67340
0.00
11.16
−1.09
P9
50
5
70
84055
84227
0.20
14.13
84110
0.07
16.96
−0.13
P10
50
5
150
51822
51902
0.15
10.21
51883
0.12
13.49
−0.03
P11
50
5
70
86203
86223
0.02
9.20
86203
0.00
14.71
−0.02
P12
50
5
150
61830
61978
0.24
19.54
61830
0.00
21.49
−0.24
P13
100
5
70
275993
281229
1.90
11.51
278926
1.05
38.41
−0.85
P14
100
5
150
214392
218886
2.10
9.52
216802
1.11
29.74
−0.99
P15
100
5
70
194598
196587
1.02
145.25
196436
0.94
95.16
−0.08
P16
100
5
150
157173
159244
1.32
180.38
158720
0.97
124.63
−0.35
P17
100
5
70
200246
203297
1.52
126.12
202682
1.20
110.85
−0.32
P18
100
5
150
152586
157859
3.46
122.47
156049
2.22
105.26
−1.24
P19
100
10
70
290429
334486
15.17
97.80
294774
1.47
143.2
−13.70
P20
100
10
150
234641
285303
21.59
75.87
236217
0.67
113.6
−20.92
P21
100
10
70
244265
257455
5.40
103.49
248003
1.51
139.85
−3.89
P22
100
10
150
203988
216253
6.01
69.65
208455
2.14
107
−3.87
P23
100
10
70
253344
291153
14.92
169.98
258221
1.89
153.53
−13.03
P24
100
10
150
204597
220528
7.79
67.06
209390
2.29
131.52
−5.50
P25
200
10
70
479425
518815
8.22
347.64
491097
2.43
554.88
−5.79
P26
200
10
150
378773
408401
7.82
469.61
384126
1.39
799.75
−6.43
P27
200
10
70
450468
494247
9.72
491.36
461810
2.46
1101.8
−7.26
P28
200
10
150
374435
396998
6.03
339.17
380004
1.47
775.62
−4.56
P29
200
10
70
472898
485672
2.70
397.96
479708
1.42
776.73
−1.28
P30
200
10
150
364178
374923
2.95
358.23
372971
2.36
919.82
−0.59
Average
4.22
122.66
1.00
211.35
−3.22Using the diversification strategy of probabilistically accepting the second best solution, the NTS increases the probability of exploring more solution space. As a result, the NTS takes more computational time than the TS. However, from Table1, we can observe that although the average computational time of NTS is about two times that of TS, it is still in a very acceptable range. The NTS provides more competitive upper bound than the TS. The average gap between the best upper bound found so far by NTS and the best known upper bound in the literature is about 1.00%, compared to the 4.22% of the TS. The NTS outperforms the TS in the quality of solutions obtained with the average deviation of the gap DEV = −3.22%.Table2 reports the computational results on test bed of randomly generated LIRP-FRL instances. From the table, we can also find that the NTS performs better than the classic TS with an average gap between the best upper bound of NTS and that of TS, about −2.79%. The average computational time of NTS is slightly bigger than that of TS.Table 2
Computational results on LIRP-FRL instances.
Prob. ID
|
I
|
|
J
|
Q
TS
NTS
∗Gap 1 (%)
UB
Time
UB
Time
P1
20
5
70
67528
0.50
67528
0.53
0.00
P2
20
5
150
42867
0.55
42867
0.61
0.00
P3
20
5
70
60021
0.46
60021
0.65
0.00
P4
20
5
150
40255
0.57
40255
0.62
0.00
P5
50
5
70
115984
22.56
115534
22.95
−0.39
P6
50
5
150
84468
36.43
84401
34.18
−0.08
P7
50
5
70
117828
22.56
117530
24.06
−0.25
P8
50
5
150
96633
21.61
96161
21.64
−0.49
P9
50
5
70
112493
24.31
111625
24.51
−0.78
P10
50
5
150
82667
23.01
82392
24.66
−0.33
P11
50
5
70
108639
21.28
108568
20.32
−0.07
P12
50
5
150
82938
21.58
82804
22.07
−0.16
P13
100
5
70
342786
139.24
342309
139.97
−0.14
P14
100
5
150
276104
137.64
273409
138.72
−1.37
P15
100
5
70
239544
143.75
238937
158.07
−0.25
P16
100
5
150
201533
125.58
200708
135.06
−0.41
P17
100
5
70
250239
121.28
249565
124.88
−0.27
P18
100
5
150
198842
126.84
197310
128.30
−0.78
P19
100
10
70
406342
138.30
396469
161.50
−2.49
P20
100
10
150
368668
138.84
339644
157.86
−8.55
P21
100
10
70
328174
121.59
320363
151.15
−2.44
P22
100
10
150
278729
128.50
274026
134.76
−1.72
P23
100
10
70
388259
113.47
320651
143.94
−21.08
P24
100
10
150
339851
120.77
283008
136.13
−20.09
P25
200
10
70
645014
393.75
629604
525.43
−2.45
P26
200
10
150
558189
368.91
528721
510.52
−5.57
P27
200
10
70
627737
427.91
611151
542.92
−2.71
P28
200
10
150
543988
379.41
517132
432.50
−5.19
P29
200
10
70
607894
419.25
598889
428.33
−1.50
P30
200
10
150
530675
422.72
509796
563.14
−4.10
Average
138.77
163.67
−2.79
∗Gap 1 (%) = 100 ∗ (H2 solution value − H1 solution value)/H2 solution value.


## 4.4. Sensitivity Analysis

Sensitivity analysis is also conducted to investigate the effects on the total costs when the input parameters such as the return rate(r) or the rate between the unit producing cost of new products and recovered products (c
m
:
c
r) changes.Table3 reports the computational results when the product return rate is changed for each randomly generated instance. To manifest the trend more clearly, for each return rate value, we calculate the arithmetic average objective function values of all tested instances. The results are shown in Figure 3. From the figure, we can find that the total costs decrease with the increase of return rate r. Focusing on those products with high return rate can effectively reduce the system costs.Table 3
Results of different return rates.
Prob. ID
r
|
I
|
|
J
|
Q
TS
NTS
Gap 1 (%)
UB
Time
UB
Time
P1
0.1
20
5
70
67617
3.22
67617
2.66
0.00
0.2
67522
3.38
67522
3.48
0.00
0.3
67423
3.64
67423
3.14
0.00
0.4
67568
2.73
67320
3.28
−0.37
0.5
67293
4.69
67211
3.22
−0.12
0.6
67094
3.26
67094
2.95
0.00
0.7
66966
3.19
66966
2.77
0.00
0.8
66904
3.15
66822
3.67
−0.12
0.9
66646
2.68
66646
3.15
0.00
P2
0.1
20
5
150
42972
2.54
42972
2.87
0.00
0.2
42969
2.43
42969
2.96
0.00
0.3
42965
3.07
42965
2.57
0.00
0.4
42961
3.40
42961
2.66
0.00
0.5
42955
3.00
42955
3.18
0.00
0.6
42948
2.63
42948
2.92
0.00
0.7
42939
2.68
42939
3.08
0.00
0.8
42927
2.66
42927
3.02
0.00
0.9
42908
2.47
42908
3.04
0.00
P3
0.1
20
5
70
61544
2.70
61296
2.68
−0.40
0.2
61175
3.14
61175
3.40
0.00
0.3
61050
2.68
61050
2.99
0.00
0.4
61011
3.16
60921
2.91
−0.15
0.5
60786
2.62
60786
2.98
0.00
0.6
60733
2.55
60644
2.81
−0.15
0.7
60492
2.99
60492
3.23
0.00
0.8
60325
2.87
60325
3.10
0.00
0.9
60308
3.18
60127
3.19
−0.30
P4
0.1
20
5
150
40396
2.56
40396
2.71
0.00
0.2
40395
2.58
40395
2.63
0.00
0.3
40393
2.64
40393
2.94
0.00
0.4
40390
2.68
40390
2.41
0.00
0.5
40386
2.66
40386
3.12
0.00
0.6
40381
2.53
40381
2.46
0.00
0.7
40373
2.68
40373
2.66
0.00
0.8
40363
2.46
40363
2.63
0.00
0.9
40346
2.88
40346
2.61
0.00
P5
0.1
50
5
70
117680
36.19
116409
34.62
−1.08
0.2
115813
32.65
115115
31.58
−0.60
0.3
114965
30.64
114542
31.43
−0.37
0.4
115279
30.7
114927
31.34
−0.31
0.5
116446
26.22
115078
30.92
−1.17
0.6
114151
30.48
114039
31.18
−0.10
0.7
114504
31.34
114190
32.04
−0.27
0.8
115578
28.66
114239
26.56
−1.16
0.9
112326
31.31
112310
33.62
−0.01
P6
0.1
50
5
150
87885
20.30
87678
24.04
−0.24
0.2
87289
23.82
86748
27.87
−0.62
0.3
88191
23.95
87140
24.59
−1.19
0.4
89497
20.47
86970
23.87
−2.82
0.5
87240
21.81
86955
24.84
−0.33
0.6
87233
24.34
86283
24.26
−1.09
0.7
86366
24.17
86173
21.05
−0.22
0.8
85494
22.81
84771
24.78
−0.85
0.9
84673
23.93
84358
24.24
−0.37
P7
0.1
50
5
70
122232
26.84
121605
22.23
−0.51
0.2
121038
26.14
120826
26.16
−0.18
0.3
121147
26.17
120530
26.66
−0.51
0.4
120239
26.41
119945
26.86
−0.24
0.5
120223
26.11
119788
26.03
−0.36
0.6
119636
26.05
119545
28.81
−0.08
0.7
119795
25.50
119440
32.04
−0.30
0.8
119994
26.05
119100
27.80
−0.75
0.9
119728
25.72
118222
27.31
−1.26
P8
0.1
50
5
150
99470
26.38
99178
27.75
−0.29
0.2
99455
25.21
99319
25.61
−0.14
0.3
100163
28.65
98682
21.78
−1.48
0.4
98722
25.14
98642
25.32
−0.08
0.5
98930
25.27
98617
27.10
−0.32
0.6
98131
24.90
98056
26.23
−0.08
0.7
98723
25.60
97815
23.55
−0.92
0.8
97633
25.78
97296
33.13
−0.35
0.9
97752
25.43
96882
26.07
−0.89
P9
0.1
50
5
70
86438
25.22
86398
29.74
−0.05
0.2
86031
22.20
85926
28.47
−0.12
0.3
86300
25.01
85635
21.50
−0.77
0.4
85292
21.61
85283
22.87
−0.01
0.5
85084
24.46
84834
28.05
−0.29
0.6
84628
23.10
84495
28.72
−0.16
0.7
84358
24.98
84116
22.87
−0.29
0.8
83239
21.88
83103
21.64
−0.16
0.9
83386
22.48
82806
25.97
−0.70
P10
0.1
50
5
150
115321
25.76
115143
28.26
−0.15
0.2
114968
26.16
114609
21.55
−0.31
0.3
114628
27.12
114347
24.59
−0.25
0.4
114620
26.62
113993
27.86
−0.55
0.5
114243
25.93
113821
27.95
−0.37
0.6
113720
26.05
113461
29.29
−0.23
0.7
113367
22.95
113204
28.36
−0.14
0.8
113157
26.73
112657
28.41
−0.44
0.9
112518
32.52
111908
26.90
−0.54
P11
0.1
50
5
70
112376
26.82
111843
32.35
−0.47
0.2
111582
25.94
111286
27.18
−0.27
0.3
111920
23.13
111054
29.51
−0.77
0.4
111642
24.91
110986
28.05
−0.59
0.5
111345
23.08
110891
27.75
−0.41
0.6
110712
26.11
110203
28.93
−0.46
0.7
110789
25.79
109949
29.03
−0.76
0.8
110232
25.79
109923
28.18
−0.28
0.9
109797
24.80
109042
32.89
−0.69
P12
0.1
50
5
150
85505
24.69
85246
27.45
−0.30
0.2
85187
24.25
85019
23.92
−0.20
0.3
84879
24.73
84757
24.78
−0.14
0.4
84797
28.33
84337
30.83
−0.54
0.5
84312
25.84
83955
28.38
−0.42
0.6
84053
26.65
83933
21.82
−0.14
0.7
83933
26.31
83358
31.33
−0.69
0.8
83651
26.92
82897
29.92
−0.90
0.9
82655
23.22
82439
26.95
−0.26
P13
0.1
100
5
70
343359
189.12
341812
146.89
−0.45
0.2
346569
187.44
343870
187.75
−0.78
0.3
345210
169.49
342124
141.65
−0.89
0.4
348100
180.08
345668
190.9
−0.70
0.5
349269
159.25
343318
184.88
−1.70
0.6
347719
182.23
343891
162.19
−1.10
0.7
349525
182.84
342643
169.88
−1.97
0.8
349171
160.17
341151
158.68
−2.30
0.9
351251
182.08
349382
186.92
−0.53
P14
0.1
100
5
150
282054
135.84
281389
190.02
−0.24
0.2
281199
128.94
279541
151.39
−0.59
0.3
279903
155.98
279153
160.32
−0.27
0.4
278748
161.52
277988
130.87
−0.27
0.5
279806
152.32
278460
162.29
−0.48
0.6
280003
188.32
279155
127.99
−0.30
0.7
280823
126.66
278542
171.61
−0.81
0.8
276206
136.94
275974
138.12
−0.08
0.9
276528
157.65
275917
163.14
−0.22
P15
0.1
100
5
70
246010
156.28
245337
148.54
−0.27
0.2
245120
175.84
244537
172.42
−0.24
0.3
244563
154.52
243754
154.32
−0.33
0.4
243537
154.53
243124
133.88
−0.17
0.5
242570
120.21
241529
192.88
−0.43
0.6
241778
171.75
241435
150.70
−0.14
0.7
240726
153.04
240237
138.58
−0.20
0.8
239819
149.01
239716
153.79
−0.04
0.9
238793
145.75
238624
144.34
−0.07
P16
0.1
100
5
150
209027
131.28
208711
153.17
−0.15
0.2
208060
149.78
207229
157.39
−0.40
0.3
206328
167.99
205454
200.44
−0.42
0.4
207220
154.39
205877
195.70
−0.65
0.5
206676
163.29
205654
172.25
−0.49
0.6
204833
137.78
204547
168.87
−0.14
0.7
204402
137.86
204284
153.95
−0.06
0.8
203509
173.04
203068
191.72
−0.22
0.9
203695
153.95
201648
146.62
−1.00
P17
0.1
100
5
70
259816
195.04
258025
149.48
−0.69
0.2
258004
164.99
256937
193.31
−0.41
0.3
256120
124.51
256057
123.60
−0.02
0.4
254658
130.21
254594
150.79
−0.03
0.5
254764
133.42
253722
165.32
−0.41
0.6
255047
155.20
252587
151.01
−0.96
0.7
250732
153.72
249812
149.22
−0.37
0.8
253732
182.23
249612
167.72
−1.62
0.9
252906
168.49
249337
157.79
−1.41
P18
0.1
100
5
150
204826
145.28
204678
191.50
−0.07
0.2
205474
172.75
204621
193.28
−0.42
0.3
203254
167.53
202691
155.11
−0.28
0.4
203120
148.82
201380
121.34
−0.86
0.5
202003
122.00
201329
145.70
−0.33
0.6
200401
145.62
199858
151.80
−0.27
0.7
199032
147.58
198618
155.51
−0.21
0.8
198858
153.76
197776
145.95
−0.54
0.9
199502
134.57
197513
150.85
−1.00
P19
0.1
100
10
70
414613
171.01
401365
198.5
−3.20
0.2
413680
164.18
400546
204.34
−3.17
0.3
420538
167.47
399896
195.42
−4.91
0.4
414460
154.11
394054
202.68
−4.92
0.5
411688
158.96
395828
211.36
−3.85
0.6
412339
162.17
394750
213.73
−4.27
0.7
410641
163.97
394617
210.72
−3.90
0.8
409561
181.48
394513
218.27
−3.67
0.9
408967
178.1
394294
201.13
−3.59
P20
0.1
100
10
150
365982
113.65
362144
114.33
−1.05
0.2
365164
111.79
361157
142.29
−1.10
0.3
365868
117.97
349578
113.22
−4.45
0.4
365307
145.30
349277
144.62
−4.39
0.5
366266
115.01
348378
158.55
−4.88
0.6
363989
151.05
348198
117.37
−4.34
0.7
113367
22.95
113204
28.36
−0.14
0.8
113157
26.73
112657
28.41
−0.44
0.9
112518
32.52
111908
26.90
−0.54
P21
0.1
100
10
70
330001
132.05
323564
131.91
−1.95
0.2
329657
155.75
322848
178.39
−2.07
0.3
329303
166.30
322162
176.31
−2.17
0.4
328939
160.91
321756
167.07
−2.18
0.5
328561
167.71
321589
152.01
−2.12
0.6
328166
166.06
321183
182.85
−2.13
0.7
327744
132.12
321102
174.83
−2.03
0.8
327281
133.30
320160
179.93
−2.18
0.9
326742
134.59
319244
188.47
−2.29
P22
0.1
100
10
150
281700
140.71
278464
129.13
−1.15
0.2
285498
140.01
278181
179.95
−2.56
0.3
285035
128.87
277760
184.58
−2.55
0.4
282821
157.09
277349
159.42
−1.93
0.5
284563
129.31
277133
181.07
−2.61
0.6
284057
152.07
276776
183.34
−2.56
0.7
280960
129.57
276530
172.01
−1.58
0.8
282955
157.32
276208
181.27
−2.38
0.9
278306
132.02
273261
178.52
−1.81
P23
0.1
100
10
70
399113
125.10
375576
164.77
−5.90
0.2
396761
146.84
371533
160.97
−6.36
0.3
397280
168.97
360348
155.58
−9.30
0.4
396341
139.25
347788
175.99
−12.25
0.5
393942
143.91
346723
183.96
−11.99
0.6
392957
153.30
344273
145.58
−12.39
0.7
393378
159.10
325508
172.95
−17.25
0.8
390858
130.43
325392
172.15
−16.75
0.9
391111
140.30
322910
167.81
−17.44
P24
0.1
100
10
150
297873
126.28
296530
138.04
−0.45
0.2
295735
139.68
294394
164.50
−0.45
0.3
334584
138.60
292118
173.75
−12.69
0.4
334011
152.64
288251
183.57
−13.70
0.5
345871
130.23
287245
142.65
−16.95
0.6
343622
150.07
286258
149.21
−16.69
0.7
344063
132.18
285833
132.30
−16.92
0.8
343388
151.00
285505
145.31
−16.86
0.9
342624
161.02
276622
165.18
−19.26
P25
0.1
200
10
70
665405
1003.37
646837
1358.56
−2.79
0.2
663368
1022.24
646011
1275.81
−2.62
0.3
662357
840.78
645933
1052.16
−2.48
0.4
660795
819.73
643790
900.59
−2.57
0.5
660155
819.55
641200
1170.31
−2.87
0.6
657577
835.74
640619
1172.54
−2.58
0.7
655423
831.23
640582
851.98
−2.26
0.8
654409
830.95
637338
858.12
−2.61
0.9
653286
792.33
622908
836.45
−4.65
P26
0.1
200
10
150
573667
753.47
553421
1069.24
−3.53
0.2
570023
765.06
551891
1297.82
−3.18
0.3
569666
776.15
537807
1069.80
−5.59
0.4
567939
797.95
535782
1163.39
−5.66
0.5
564777
900.56
535225
1108.99
−5.23
0.6
564413
887.18
535083
1195.13
−5.20
0.7
562167
849.13
531505
1236.66
−5.45
0.8
560098
799.95
514584
1157.03
−8.13
0.9
557554
864.90
513652
1023.90
−7.87
P27
0.1
200
10
70
661785
1384.45
631700
1228.42
−4.55
0.2
662602
1317.90
630853
969.39
−4.79
0.3
647333
1144.41
630036
1119.12
−2.67
0.4
647377
1238.22
625782
1060.19
−3.34
0.5
647837
955.81
625659
1159.76
−3.42
0.6
651234
972.11
624175
1104.26
−4.16
0.7
643657
994.18
623635
1203.08
−3.11
0.8
648507
1007.51
618926
1251.66
−4.56
0.9
640631
974.55
617253
1352.17
−3.65
P28
0.1
200
10
150
560151
1039.68
554838
901.12
−0.95
0.2
567066
805.96
552250
1205.61
−2.61
0.3
565177
1107.27
551150
1429.66
−2.48
0.4
551554
1150.46
546455
1283.46
−0.92
0.5
550006
845.09
546211
901.12
−0.69
0.6
548151
679.59
543161
850.63
−0.91
0.7
546181
835.08
539990
965.50
−1.13
0.8
545049
869.30
538293
1444.22
−1.24
0.9
543203
937.76
522946
1065.27
−3.73
P29
0.1
200
10
70
621423
1031.98
619749
810.58
−0.27
0.2
624921
755.35
618833
817.09
−0.97
0.3
620040
711.57
617782
991.29
−0.36
0.4
617601
867.88
615738
958.45
−0.30
0.5
623408
1135.24
614301
1168.53
−1.46
0.6
614480
799.56
612048
1337.13
−0.40
0.7
612960
1095.73
611365
948.58
−0.26
0.8
611261
1126.74
609791
969.75
−0.24
0.9
609581
846.60
608927
712.33
−0.11
P30
0.1
200
10
150
522946
935.56
520709
1214.20
−0.43
0.2
521952
696.92
518710
871.10
−0.62
0.3
520505
730.31
516812
1182.22
−0.71
0.4
519262
780.89
516352
1289.81
−0.56
0.5
517999
707.29
516019
1335.97
−0.38
0.6
516930
1052.88
515388
1212.71
−0.30
0.7
515604
954.61
513938
1054.47
−0.32
0.8
514221
687.26
511705
1073.18
−0.49
0.9
497335
1020.75
492080
1113.48
−1.06Figure 3
Results of different return rates.Table4 shows the numerical results when the rate between the cost of producing a new product and that of recovering a damaged or old product varies. For each rate, we average the best upper bound obtained for all tested instances. The results are depicted in Figure 4. From the figure, we can observe that the total costs decrease with the increase of the rate. That means reducing the unit recovering cost of product can effectively reduce the total costs, which indicates us to retrieve those subnew products or to improve repairing technique so as to reduce recovering cost.Table 4
Results of different rate between the cost of recovered products and the cost of new products.
Prob. ID
c
m
:
c
r
|
I
|
|
J
|
Q
TS
NTS
Gap 1 (%)
UB
Time
UB
Time
P1
1
20
5
70
68142
3.00
68142
2.78
0.00
1.25
67402
2.68
67402
2.39
0.00
1.5
67211
2.14
66964
2.61
−0.37
1.75
66898
3.15
66649
2.54
−0.37
2
66496
2.76
66414
2.79
−0.12
P2
1
20
5
150
43008
3.33
43008
2.35
0.00
1.25
42964
3.11
42964
2.54
0.00
1.5
42934
2.49
42934
2.22
0.00
1.75
42913
2.40
42913
3.15
0.00
2
42897
3.55
42897
3.19
0.00
P3
1
20
5
70
61680
2.72
61680
2.82
0.00
1.25
61028
2.46
61028
2.81
0.00
1.5
60595
2.47
60595
2.54
0.00
1.75
60367
2.59
60285
2.71
−0.14
2
60132
2.52
60052
2.50
−0.13
P4
1
20
5
150
40458
2.45
40458
2.05
0.00
1.25
40391
2.18
40391
2.36
0.00
1.5
40346
2.86
40346
2.96
0.00
1.75
40314
2.69
40314
2.32
0.00
2
40290
1.92
40290
2.28
0.00
P5
1
50
5
70
117832
26.39
116378
25.98
−1.23
1.25
117029
25.68
114692
26.63
−2.00
1.5
115617
26.14
114374
25.88
−1.08
1.75
115126
26.70
114022
26.30
−0.96
2
113413
25.84
112590
25.75
−0.73
P6
1
50
5
150
90053
22.94
87484
20.19
−2.85
1.25
88307
24.22
86991
20.15
−1.49
1.5
87796
23.82
86910
23.21
−1.01
1.75
86976
20.81
86535
22.24
−0.51
2
86703
22.88
86394
17.23
−0.36
P7
1
50
5
70
123939
18.23
122295
21.88
−1.33
1.25
121637
19.25
120958
16.91
−0.56
1.5
120474
18.75
119532
20.84
−0.78
1.75
119790
21.88
118308
21.61
−1.24
2
118183
16.95
117858
21.77
−0.27
P8
1
50
5
150
100524
17.41
100439
25.51
−0.08
1.25
99371
28.59
99067
29.73
−0.31
1.5
98231
24.37
97807
29.53
−0.43
1.75
97514
24.48
96608
22.80
−0.93
2
96942
25.15
96560
17.95
−0.39
P9
1
50
5
70
117880
27.00
115956
22.17
−1.63
1.25
116053
30.39
114876
35.22
−1.01
1.5
114690
24.03
113420
28.06
−1.11
1.75
113128
19.20
112769
28.95
−0.32
2
112006
28.62
111756
26.96
−0.22
P10
1
50
5
150
88057
23.26
87883
31.21
−0.20
1.25
86485
25.83
86222
31.48
−0.30
1.5
85367
31.62
84589
19.58
−0.91
1.75
83386
26.10
83478
22.37
0.11
2
83455
25.45
83235
21.90
−0.26
P11
1
50
5
70
114793
20.04
112544
25.68
−1.96
1.25
112136
19.99
111395
27.60
−0.66
1.5
111087
20.16
111062
29.96
−0.02
1.75
110640
27.13
109472
22.12
−1.06
2
110405
22.60
108934
26.43
−1.33
P12
1
50
5
150
87232
24.63
86433
29.55
−0.04
1.25
86410
22.09
86199
18.89
−0.57
1.5
85173
27.98
83868
19.14
−1.94
1.75
84523
21.53
83656
15.63
−2.18
2
83027
18.38
82912
20.22
−1.46
P13
1
100
5
70
364895
155.68
361755
159.32
−0.86
1.25
363309
160.69
360230
160.93
−0.85
1.5
362096
163.84
359999
168.78
−0.58
1.75
359974
157.96
356857
141.78
−0.87
2
355624
156.57
339404
161.89
−4.56
P14
1
100
5
150
305053
164.11
300033
139.62
−1.65
1.25
303135
141.89
296364
121.95
−2.23
1.5
301834
139.24
295118
121.68
−2.23
1.75
298777
139.76
294442
133.88
−1.45
2
291740
133.99
276706
135.66
−5.15
P15
1
100
5
70
296619
124.99
258199
125.21
−12.95
1.25
260317
137.47
254461
128.82
−2.25
1.5
249922
115.05
247152
183.34
−1.11
1.75
249195
132.22
244535
154.43
−1.87
2
247529
149.44
241351
171.13
−2.50
P16
1
100
5
150
233346
120.31
223398
126.11
−4.26
1.25
229687
129.75
220760
114.91
−3.89
1.5
226932
127.63
218861
117.39
−3.56
1.75
216624
137.42
214174
115.09
−1.13
2
211223
128.79
205238
122.39
−2.83
P17
1
100
5
70
267713
134.93
265309
110.60
−0.90
1.25
266067
132.17
262547
122.34
−1.32
1.5
263994
130.92
260267
110.49
−1.41
1.75
261711
116.78
259735
150.61
−0.76
2
260804
170.99
252673
124.40
−3.12
P18
1
100
5
150
226178
124.86
224348
139.70
−0.81
1.25
223053
127.08
219578
134.79
−1.56
1.5
220970
115.28
218823
184.85
−0.97
1.75
219154
158.19
216341
129.00
−1.28
2
217751
159.37
209257
182.73
−3.90
P19
1
100
10
70
412240
135.46
409643
141.11
−0.63
1.25
406518
139.13
403969
173.98
−0.63
1.5
404199
137.06
401006
167.12
−0.79
1.75
403475
136.64
400046
178.88
−0.85
2
401608
136.54
394231
149.81
−1.84
P20
1
100
10
150
366576
105.10
364188
166.50
−0.65
1.25
364342
123.15
362564
100.25
−0.49
1.5
360397
153.27
358732
143.08
−0.46
1.75
357502
158.04
356178
114.59
−0.37
2
350419
100.43
345948
154.21
−1.28
P21
1
100
10
70
337749
113.31
334240
100.11
−1.04
1.25
333248
114.45
330768
112.04
−0.74
1.5
330981
127.66
329900
133.01
−0.33
1.75
329982
143.46
325218
139.32
−1.44
2
327911
189.02
322382
150.34
−1.69
P22
1
100
10
150
300245
112.22
297406
94.24
−0.95
1.25
293642
127.66
291212
119.95
−0.83
1.5
290938
186.05
287471
192.95
−1.19
1.75
288716
183.72
285885
127.07
−0.98
2
286473
132.29
281933
125.07
−1.58
P23
1
100
10
70
369343
127.38
364871
132.22
−1.21
1.25
364871
152.70
359677
141.96
−1.42
1.5
359613
147.70
355286
152.78
−1.20
1.75
358094
155.05
354980
142.97
−0.87
2
341610
146.96
320343
172.26
−6.23
P24
1
100
10
150
328663
124.91
299018
132.71
−9.02
1.25
325042
125.13
295553
137.29
−9.07
1.5
323847
156.83
291860
135.43
−9.88
1.75
299214
135.60
288433
157.16
−3.60
2
294706
121.22
281938
168.67
−4.33
P25
1
200
10
70
665281
829.11
653633
1026.07
−1.75
1.25
657935
834.27
652114
1061.26
−0.88
1.5
655818
823.79
651574
984.23
−0.65
1.75
649604
820.10
646761
1055.81
−0.44
2
642489
820.87
641864
1139.61
−0.10
P26
1
200
10
150
581623
611.52
580270
618.26
−0.23
1.25
579961
608.25
569283
626.20
−1.84
1.5
574684
604.60
536008
613.79
−6.73
1.75
556955
621.66
535570
623.55
−3.84
2
554052
621.92
528999
622.53
−4.52
P27
1
200
10
70
773781
793.09
662523
778.08
−14.38
1.25
713012
819.64
655573
803.25
−8.06
1.5
681260
804.27
642081
739.51
−5.75
1.75
635834
770.17
632602
723.11
−0.51
2
632061
739.14
623493
704.85
−1.36
P28
1
200
10
150
576983
666.69
555923
987.24
−3.65
1.25
568736
675.82
546433
859.83
−3.92
1.5
564064
674.70
543330
859.83
−3.68
1.75
560726
914.60
535818
761.02
−4.44
2
534830
977.03
522356
795.76
−2.33
P29
1
200
10
70
666957
790.82
636582
820.80
−4.55
1.25
658832
832.47
633813
1119.70
−3.80
1.5
653454
1149.63
621988
965.82
−4.82
1.75
622078
801.89
619907
825.17
−0.35
2
616051
863.47
608644
1080.37
−1.20
P30
1
200
10
150
542071
734.01
540384
705.36
−0.31
1.25
525159
727.55
524172
786.56
−0.19
1.5
521758
716.37
510933
763.03
−2.07
1.75
518474
787.04
506479
752.31
−2.31
2
515142
755.66
502884
698.85
−2.38Figure 4
Results of different rate between the cost of recovered products and the cost of new products.


## 5. Conclusions and Future Works

We study a location-inventory-routing problem in forward and reverse logistics (LIRP-FRL) in this paper. A nonlinear mixed integer programming model is proposed to formulate the LIRP-FRL. Based on this model, a new tabu search that probabilistically accepts the second best solution in its neighborhoods is proposed to find near optimal solution for the problem. Numerical experiments on CLRP benchmarks and randomly generated instances of LIRP-FRL with various problem sizes demonstrate the effectiveness and the efficiency of the new tabu search, which can find high quality solution with a reasonable time. Sensitivity analyses are also conducted to investigate the intrinsic management insights of the problems.For future research, to be more close to the reality, the stochastic demand of customer should also be considered in the LIRP-FRL.



---

*Source: 3475369-2016-07-20.xml*