# Novel Encoding and Routing Balance Insertion Based Particle Swarm Optimization with Application to Optimal CVRP Depot Location Determination

Authors: Ruey-Maw Chen; Yin-Mou Shen
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

A depot location has a significant effect on the transportation cost in vehicle routing problems. This study proposes a hierarchical particle swarm optimization (PSO) including inner and outer layers to obtain the best location to establish a depot and the corresponding optimal vehicle routes using the determined depot location. The inner layer PSO is applied to obtain optimal vehicle routes while the outer layer PSO is to acquire the depot location. A novel particle encoding is suggested for the inner layer PSO, the novel PSO encoding facilitates solving the customer assignment and the visiting order determination simultaneously to greatly lower processing efforts and hence reduce the computation complexity. Meanwhile, a routing balance insertion (RBI) local search is designed to improve the solution quality. The RBI local search moves the nearest customer from the longest route to the shortest route to reduce the travel distance. Vehicle routing problems from an operation research library were tested and an average of 16% total routing distance improvement between having and not having planned the optimal depot locations is obtained. A real world case for finding the new plant location was also conducted and significantly reduced the cost by about 29%.


---

## Body

## 1. Introduction

The vehicle routing problem (VRP) is a scheduling problem encountered in logistic arrangement, an extension of the traveling salesman problem. As different restrictions (vehicle capacity limits, visit time limits, goods pick-, and delivery demands, etc.), there are also dissimilar types of VRPs, such as capacitated VRPs (CVRPs) involving only vehicle capacity limits, capacitated VRPs with time windows involving both vehicle capacity and visit time limits at the same time, VRPs with pickups and deliveries involving pickup and delivery demands, multiple depot VRPs involving multiple depots, and periodic VRPs involving customs with periodic demands. This study focuses on capacitated vehicle routing problems. In operation research, vehicle routing problems have been confirmed to be NP-hard. Accurate optimal solutions to this type of problem can be obtained with exact algorithms [1] within a limited time only when the problem scale is small. With problems of a larger scale, the amount and time of calculation required make it impossible to obtain optimal solutions with exact algorithms within a limited time. For this reason, many researchers have come up with a variety of heuristic and metaheuristic methods in recent years to cope with vehicle routing problems, including the evolution computation, memetic algorithm, genetic algorithm (GA), local search metaheuristic, artificial bee colony algorithm, ant colony optimization (ACO), and particle swarm optimization (PSO). Prins [2] used two memetic algorithms for heterogeneous fleet vehicle routing problems. Repoussis et al. [3] applied a hybrid evolution strategy for the open vehicle routing problem. Gajpal and Abad [4] proposed a saving-based algorithm for vehicle routing problem, in which a new route is created by merging two existing routes. Munawar et al. suggested a cellular genetic algorithm with local search to solve CVRP [5]. Pop et al. integrated a GA with a local search to globalize the approach to the CVRP [6]. In [7], a local search metaheuristic including the static move descriptor strategy for exploration and the promises concept for avoiding search cycling and inducing diversification was designed for the VRP with simultaneous pick-ups and deliveries. Fleszar et al. proposed an effective variable neighborhood search scheme based on reversing the routing segment and exchanging routing segments for solving the open VRP to minimize the number of vehicles as well as the total travelled distance [8]. Meanwhile, an adaptive variable neighborhood search together with diversification local search methods was utilized to investigate the homogeneous fleet VRP [9]. Artificial bee colony algorithm with a local optimization strategy based on a scanning strategy for an open VRP was studied by Yao et al. [10]. Szeto et al. also applied an enhanced version of artificial bee colony for solving the CVRP [11]. Ant colony optimization is a well-known metaheuristic for combinatorial optimization problems. An ant colony system based algorithm was proposed by Favaretto et al. [12] to solve VRP with multiple time window constraints. Yu et al. recommended an improved ACO, which implements a new ant-weight strategy to update the increasing trail pheromone and a mutation operation to solve VRP [13]. A PSO-based scheme with two solution encodings and the corresponding decodings for solving CVRP was investigated by Ai and Kachitvichyanukul [14]. In [15], a PSO-based approach in which a variable neighborhood descent local search is performed to solve the VRP with pickup and delivery at the same time. Meanwhile, Marinakis et al. [16] proposed a hybrid algorithm based on PSO for solving VRP with stochastic demand. Moreover, a VRP with fuzzy demands was solved by applying a PSO-based approach in which a novel encoding method was introduced [17].Among them, PSO has the advantage of requiring less parameters and faster convergence rates and has therefore been adopted by many researchers to solve various problems. Abido [18] employed PSO to solve the optimal setting of power flow. Kang and He [19] proposed a novel discrete particle swarm optimization algorithm for meta-task assignment in heterogeneous computing systems and used a migration mechanism to escape from possible local optimum. A flow shop sequence dependent group scheduling problem was resolved using PSO based on a ranked order value encoding scheme [20]. Meanwhile, Chen [21] presented PSO with justification technique integrated to solve resource-constrained project scheduling problems. Moreover, an application of PSO to solve task-resource assignment in a heterogeneous grid was provided by Chen and Wang [22]. Additionally, Chen and Sandnes [23] applied constriction PSO to solve man-day scheduling problems.Scholars have established different restriction databases to help solve VRP problems, but the objectives are mostly to plan the least costly vehicle routes when the locations of depots and customers are already known. A dynamic VRP which considers new customer requests while the vehicle routing is in progress was also investigated by using PSO [24]. In some industries, 25% of the company’s total revenue must be used to pay for materials delivery as well as shipping costs to ship products. Restated, the transportation cost is an extremely important consideration for many businesses. Therefore, efficient vehicle routing is crucial. Meanwhile, site selection has a significant impact on the fixed and changing costs and the impact of the company’s risk and profits. Hence, setting the operating site location is one of the most important decisions in many companies, such as FedEx. The goal of site selection is to allow the company to reduce the transportation cost so as to get the most benefit. Site selection can be any operating site selection including VRP depot location selection. However, most studies focus on solving VRP based on fixed depots. In logistic businesses, besides fine vehicle route planning, good choice of depot locations is also an important issue to reduce business costs and hence increase profits. Restated, solving both the optimal depot location as well as the optimal vehicle routes is necessary. Therefore, this investigation focuses on solving these two issues by a hierarchical PSO involving two PSO algorithms: one for the inner layer and the other for the outer layer. The outer-layer PSO is first applied to establish the optimal depot location; then, the inner PSO is used to produce the optimal vehicle routing. This optimal routing involves the customer-to-vehicle assignment and visit order determination issues. These two issues are commonly resolved by two separate PSOs in most studies, hence much effort is required. Therefore, a novel particle encoding scheme is proposed to deal with those two issues simultaneously to greatly reduce the processing effort. Meanwhile, a new local search strategy is also designed and employed to improve solution quality. This new designed local search is named routing balance insertion (RBI) local search herein, it is inspired by the well-used nearest neighborhood heuristic in TSP. The RBI local search selects the nearest customer on the longest routing cluster and inserts the selected node into the shortest routing cluster to reduce the total travel distance. The nearest customer is determined based on the distance between the customer and the centroid of the shortest routing cluster.The organization of this work is as follows. Section2 describes the interested capacitated vehicle routing problems. The proposed scheme, including novel particle encoding and routing balance insertion local search, is given in Section 3. Section 4 demonstrates the experimental results and analysis. Finally, conclusions are made in Section 5.


## 2. Problem Description

The vehicle routing problem was first proposed by Dantzig and Ramser in 1959 [25]. It was very similar to the concept of distribution of goods by logistic businesses in reality. The problem involved the demands of each of many customers scattered about different places. The depot had to assign vehicles to visit (service) all the customers and satisfy their needs by planning the shortest total travel distance without violating any restrictions.In a CVRP, there are a fixed number of customers and a depot. The locations of each customer and the depot are known (indicated with Cartesian coordinates). SetC={c1,c2,…,cn} stands for the set customers; c1,c2,…,cn are the customers. The depot will send out a fleet comprising several vehicles. The vehicle fleet V={v1,v2,…,vk}, in which k is the number of vehicles. Each customer has a different cargo demand and each vehicle has a carrying capacity limitation. Each vehicle must leave from the depot and return to the depot at the end. Each customer has to be visited once and once only. The objectives and restrictions of the CVRP are then defined as follows:(1)Fitness=min⁡⁡∑i=0n∑j=0n∑v=1kdijXijv+dn0Xn0vi≠j,(2)∑i=0n∑j=0nXijvri≤Qvi≠j,v∈V,(3)Xijv=1,a  customeritojis  on  the  route  of  vehiclev,0,otherwise.In (1), the objective function of the VRP is defined as to obtain the shortest total travel distance. The dij is the distance from the customer i to customer j and Xijv stands for whether vehicle v will go from customer i to customer j. When Xijv=1, it means vehicle v travels from a customer i to j. On the other hand, when Xijv=0, vehicle v does not travel from customer i to customer j. In (2), the total demands from customers served by vehicle v may not exceed the carrying capacity of vehicle v. The ri stands for the cargo demand of customer i while Qv is the maximum carrying capacity defined for vehicle v. The objective is to obtain the shortest total travel distance, but each vehicle may not violate the maximum capacity restriction throughout the tour.This investigation is interested in determining the optimal depot location as well as the optimal vehicle routing. This problem to obtain the optimal vehicle routes first needs allocation of then customers to k vehicles. Hence, there is a surjection from customer collection C={c1,c2,…,cn} to vehicle collection V={v1,v2,…,vk}, that is, customer to vehicle assignment as shown in Figure 1. Next, determination of the optimal visit order for each vehicle is needed as displayed in Figure 2.Figure 1
Customer-to-vehicle assignment.Figure 2
Visit order optimization.To acquire optimal customer-to-vehicle assignment and optimal visit order for each vehicle, a particle swarm optimization (PSO) with a novel particle encoding scheme is proposed to resolve these two issues at the same time. Restated, with the help of the novel particle encoding scheme, the customer assignment and the visiting order determination can be solved concurrently.Meanwhile, a depot has a very significant effect on the transportation cost. Therefore, a hierarchical PSO is utilized; the position of the depot is adjusted with the outer PSO and then the inner PSO is applied to determine the optimal customer assignment and optimal visit order with minimum total vehicle routes.


## 3. Particle Swarm Optimization with Proposed Designs

This study focuses on applying hierarchical PSO to obtain optimal depot location as well as the optimal vehicle routes. In this Section, PSO is first introduced; next, a novel particle encoding for the inner and outer layer PSOs are presented. To enhance the PSO performance routing balance insertion local search is designed.


### 3.1. Particle Swarm Optimization (PSO)

Particle swarm optimization is a type of collective intelligence. It was first put forward in 1995 by Kennedy and Eberhart [26] who were inspired by the group behavior of biological creatures looking for food together. In the operation of a PSO algorithm, the position of a particle stands for the solution to the problem. In PSO, a particle moves in the solution space and uses two experiences as references for further motion, namely, the optimal individual experience and the optimal group experience. The optimal group experience indicates that the entire group has been placed in the best position and the optimal individual experience means each particle has been placed in its best position. When calculating the new moving speed of a particle in each iteration, besides the original speed, the positions of the optimal group experience and the optimal individual experience are also referred to. Suppose that an N number of particles are scattered in an L-dimensional space. The position vector of the ith particle (i=1,…,N) is composed of L vector components. Xi={Xi1,…,XiL} indicates the position vector of particle i, in which Xij stands for the jth vector component of the ith particle. The velocity vector of the ith particle is also composed of L components Vi={Vi1,…,ViL}. The optimal individual experience of the ith particle is thus represented as Pi={Pi1,…,PiL}, whereas the optimal swarm experience (Gbest) is G={G1,…,GL}. These velocity and position update rules are shown below: (4)Vijnew=w×Vij+c1×r1×Pij-Xij+c2×r2×Gj-Xij,Xijnew=Xij+Vijnew.In (4), w is the inertia weight used to determine the level of effect of the previous velocity on the new velocity. In PSO algorithms, inertia weight is an important factor that has influence on the search ranges of particles. When w increases, the searching movement of a particle is broader and global exploration is suitable. On the other hand, when the search space is narrower, local exploitation will be more appropriate. Therefore, proper adjustment of w to balance global exploration and local exploitation is required and important. Meanwhile, c1 and c2 are learning factors which have an effect on particles’ learning of global experience and individual experience, whereas r1 and r2 represent random numbers within [0,1].


### 3.2. Novel Particle Encoding for Inner Layer PSO

The particle position vector represents the solution of a studied problem and the particle position encoding is the core step in PSO. Before the inner layer PSO performs visit order decision-making and fitness calculations, the position vector (XiV) has to be converted into the visit sequence of a vehicle. Restated, each customer the vehicle is assigned to have to be determined before an assessment can be conducted. Hence, to facilitate finding the optimal solution and reduce the processing effort, this work designs a novel compound particle encoding scheme to reduce the customer-to-vehicle assignment and visit order determination effort for the inner layer PSO. Herein, a particle of the inner-layer PSO includes customers and vehicles assigned, as shown in Table 1. In Table 1, the position vector includes n+(k-1) components; that is, XiV={Xi1V,…,XinV,…,Xin+k-1V}. Meanwhile, each component is associated with a key (Key={Cus1,Cus2,…,Cusn,Veh1,Veh2,…,Vehk-1}). For customer-to-vehicle assignment, n customers are to be assigned to k vehicles; that is, n customers can be regarded as being clustered into k groups. Therefore, (k-1) dividing points are needed, that is the reason Veh1–Vehk-1 (k-1 components) are added.Table 1
Novel compound particle encoding (inner layer PSO).
Index
1
2
⋯
n
n
+
1
n
+
2
⋯
n
+
k
-
1
X
i
V
X
i
1
V
X
i
2
V
⋯
X
i
n
V
X
i
n
+
1
V
X
i
n
+
2
V
⋯
X
i
n
+
k
-
1
V
Key
Cus1
Cus2
⋯
Cusn
Veh1
Veh2
⋯
Vehk-1The visit sequence of each vehicle and each customer a vehicle is assigned to are determined simultaneously by using a random key scheme. Take six customers and three vehicles, for example. Figure3 shows a solution (XiV) obtained with PSO. The components of the position vector are sorted in ascending order; then, the key values are rearranged according to the sorted values of XiV to generate a key sequence set. This key sequence is then defined as the vehicle assignment with the Vehj as the dividing point. Restated, all customers before the dividing point Veh1 are assigned to vehicle 1, all customers between Veh1 and Veh2 are assigned to vehicle 2, and so forth. Finally, customers after Vehk-1 are assigned to vehicle k. Moreover, the customers visit sequence for a vehicle is then defined as the visiting order for that vehicle. The total travel distance can then be calculated according to (1) after the vehicle assignment and visiting order are resolved. For example, customers 1, 2, and 5 are assigned to vehicle 2, and the visiting order for vehicle 2 would be from customer 2 to customer 5 then customer 1, as indicated in Figure 3. Hence, the proposed novel PSO encoding scheme in inner layer PSO can facilitate solving the customer assignment and the visiting order determination at the same time to greatly lower processing effort and hence reduce the computational complexity.Figure 3
The solution decoding process (inner layer PSO).


### 3.3. Particle Encoding for the Outer Layer PSO

The particle encoding for the outer layer PSO solutions is conducted by using a position vector consisting of two components representing theX and Y coordinates of the depot location. The outer layer PSO solution (XD={X1D,X2D}) is shown in Table 2. The fitness calculation is then performed by transferring the depot coordinates (XD) to the inner layer PSO for optimal routing calculation and the resulting total routing distance is adopted as the fitness value of the outer layer PSO.Table 2
Solution representation (outer layer PSO).
X
D
X
1
D
X
2
D
Depot location
X coordinate
Y coordinate


### 3.4. Routing Balance Insertion Local Search

The local search is a search tactic to generate new solutions in the neighborhood of the current solution to attempt to find a solution with better quality. A new local search is designed and conducted to generate a new solution and is selected to be the starting point of the algorithm when the next iteration takes place if it is a better solution.The new local search tactic named routing balance insertion (RBI) local search is applied in the inner layer PSO, which is inspired from the well-used nearest neighborhood heuristic in TSP. The RBI local search moves the nearest customer from the longest route to the shortest route to reduce the travel distance; the nearest customer is determined based on the distance between the customer and the centroid of the shortest routing cluster. The operations of the designed RBI local search are as follows.Step 1.
Select the longest routing path and the shortest routing path. Figure4 shows the resulting CVRP results, Route-1 is the routing path starting from depot (O) and visiting A, B, C, D, E, and F then back to O; Route-2 is the routing path starting from O and visiting G, H, and I then back to the depot. Assuming the travel distances of the corresponding vehicle routes are d1, d2, and d3, respectively. Suppose the max⁡{d1,d2,d3} is d1 and the min⁡{d1,d2,d3} is d2.Figure 4
Obtained CVRP results.Step 2.
Calculate the centroid position of the customers consisting of the shortest route (Route-2). The centroid position (CC=(xC,yC)) can be yielded by (5)xC=∑i=1kxiv+xOk+1,yC=∑i=1kyiv+yOk+1.In (5), xC and yC are the coordinates of the centroid position of route v (vehicle v). The xiv and yiv are the coordinates of the customers assigned to the vehicle v; xO and yO are the coordinates of the depot position.Step 3.
Calculate the distances from the customers assigned to the longest route (Route-1) to the centroid. AssumingdA,dB,… and dF are the distances from customers A,B,… and F to the centroid, as displayed in Figure 5. Suppose dB is the minimum distance, that is, customer B is the nearest one to the shortest route.Figure 5
The centroid and the distances from customer on the longest route.Step 4.
Delete customerB from Route-1 and insert B into Router-2. The travel distance of the Route-1 decreases after the customer B is removed, the decreased distance is d=AB+BC-AC. Meanwhile, there are four possible positions for inserting B as illustrated in Figure 6. The increased distances after inserting B to the four possible positions are d1=OB+BG-OG, d2=GB+BH-GH, d3=HB+BI-HI, and d4=IB+BO-IO, respectively. The insertion position is then determined by comparing d1, d2, d3, and d4. Restated, the insertion position decision is based on the min⁡{d1,d2,d3,d4}. For example, the customer B is being inserted between G and H if the d2 is the minimum increased distance as in Figure 6(b).Figure 6
Four possible insertion positions.
(a)
d
1
=
O
B
+
B
G
-
O
G
(b)
d
2
=
G
B
+
B
H
-
G
H
(c)
d
3
=
H
B
+
B
I
-
H
I
(d)
d
4
=
I
B
+
B
O
-
I
O


### 3.5. Optimal Depot Location Determination

The optimal depot location is determined using the outer layer PSO. The determined particle solution,XD, is passed to the inner layer PSO as the depot location. The inner layer PSO solves the CVRP problem on the basis of this depot location, and the minimum total vehicle routing distances (Fitness in (1)) are returned to the outer PSO. This returned Fitness is then used as the objective corresponding to XD. Accordingly, particle experience and swarm experience can be obtained. Thereafter, the velocity in the outer layer PSO is updated; a new position XD is generated and will be the new depot location. After alternating evolutions of the inner layer and outer layer PSO, an optimal depot location can be acquired.


### 3.6. Hierarchical PSO

The collaboration operation of the proposed inner and outer layer PSOs is as follows.(1)
Outer layer PSO: outputs determined depot location (XD) to the inner layer PSO.(2)
Inner layer PSO: determines total travel distance (TTD) based onXD; returns the total travel distance to the outer layer PSO.(3)
Outer layer PSO:
(i)
evaluates the quality of the depot location (XD), that is, fitness(XD) = TTD;(ii)
updates individual and swarm experience;(iii)
updates velocity and position vector;(iv)
outputs new depot location (XD) to the inner layer PSO.(4)
Repeats Steps3 and 4 until termination condition is met.(5)
Outer layer PSO: outputs the optimal depot location and the corresponding vehicle routes.The detailed flowchart of the proposed hierarchical PSO for optimal CVRP depot location and optimal vehicle routes is summarized in Figure 7.Figure 7
Flowchart of the proposed hierarchical PSO.


## 3.1. Particle Swarm Optimization (PSO)

Particle swarm optimization is a type of collective intelligence. It was first put forward in 1995 by Kennedy and Eberhart [26] who were inspired by the group behavior of biological creatures looking for food together. In the operation of a PSO algorithm, the position of a particle stands for the solution to the problem. In PSO, a particle moves in the solution space and uses two experiences as references for further motion, namely, the optimal individual experience and the optimal group experience. The optimal group experience indicates that the entire group has been placed in the best position and the optimal individual experience means each particle has been placed in its best position. When calculating the new moving speed of a particle in each iteration, besides the original speed, the positions of the optimal group experience and the optimal individual experience are also referred to. Suppose that an N number of particles are scattered in an L-dimensional space. The position vector of the ith particle (i=1,…,N) is composed of L vector components. Xi={Xi1,…,XiL} indicates the position vector of particle i, in which Xij stands for the jth vector component of the ith particle. The velocity vector of the ith particle is also composed of L components Vi={Vi1,…,ViL}. The optimal individual experience of the ith particle is thus represented as Pi={Pi1,…,PiL}, whereas the optimal swarm experience (Gbest) is G={G1,…,GL}. These velocity and position update rules are shown below: (4)Vijnew=w×Vij+c1×r1×Pij-Xij+c2×r2×Gj-Xij,Xijnew=Xij+Vijnew.In (4), w is the inertia weight used to determine the level of effect of the previous velocity on the new velocity. In PSO algorithms, inertia weight is an important factor that has influence on the search ranges of particles. When w increases, the searching movement of a particle is broader and global exploration is suitable. On the other hand, when the search space is narrower, local exploitation will be more appropriate. Therefore, proper adjustment of w to balance global exploration and local exploitation is required and important. Meanwhile, c1 and c2 are learning factors which have an effect on particles’ learning of global experience and individual experience, whereas r1 and r2 represent random numbers within [0,1].


## 3.2. Novel Particle Encoding for Inner Layer PSO

The particle position vector represents the solution of a studied problem and the particle position encoding is the core step in PSO. Before the inner layer PSO performs visit order decision-making and fitness calculations, the position vector (XiV) has to be converted into the visit sequence of a vehicle. Restated, each customer the vehicle is assigned to have to be determined before an assessment can be conducted. Hence, to facilitate finding the optimal solution and reduce the processing effort, this work designs a novel compound particle encoding scheme to reduce the customer-to-vehicle assignment and visit order determination effort for the inner layer PSO. Herein, a particle of the inner-layer PSO includes customers and vehicles assigned, as shown in Table 1. In Table 1, the position vector includes n+(k-1) components; that is, XiV={Xi1V,…,XinV,…,Xin+k-1V}. Meanwhile, each component is associated with a key (Key={Cus1,Cus2,…,Cusn,Veh1,Veh2,…,Vehk-1}). For customer-to-vehicle assignment, n customers are to be assigned to k vehicles; that is, n customers can be regarded as being clustered into k groups. Therefore, (k-1) dividing points are needed, that is the reason Veh1–Vehk-1 (k-1 components) are added.Table 1
Novel compound particle encoding (inner layer PSO).
Index
1
2
⋯
n
n
+
1
n
+
2
⋯
n
+
k
-
1
X
i
V
X
i
1
V
X
i
2
V
⋯
X
i
n
V
X
i
n
+
1
V
X
i
n
+
2
V
⋯
X
i
n
+
k
-
1
V
Key
Cus1
Cus2
⋯
Cusn
Veh1
Veh2
⋯
Vehk-1The visit sequence of each vehicle and each customer a vehicle is assigned to are determined simultaneously by using a random key scheme. Take six customers and three vehicles, for example. Figure3 shows a solution (XiV) obtained with PSO. The components of the position vector are sorted in ascending order; then, the key values are rearranged according to the sorted values of XiV to generate a key sequence set. This key sequence is then defined as the vehicle assignment with the Vehj as the dividing point. Restated, all customers before the dividing point Veh1 are assigned to vehicle 1, all customers between Veh1 and Veh2 are assigned to vehicle 2, and so forth. Finally, customers after Vehk-1 are assigned to vehicle k. Moreover, the customers visit sequence for a vehicle is then defined as the visiting order for that vehicle. The total travel distance can then be calculated according to (1) after the vehicle assignment and visiting order are resolved. For example, customers 1, 2, and 5 are assigned to vehicle 2, and the visiting order for vehicle 2 would be from customer 2 to customer 5 then customer 1, as indicated in Figure 3. Hence, the proposed novel PSO encoding scheme in inner layer PSO can facilitate solving the customer assignment and the visiting order determination at the same time to greatly lower processing effort and hence reduce the computational complexity.Figure 3
The solution decoding process (inner layer PSO).


## 3.3. Particle Encoding for the Outer Layer PSO

The particle encoding for the outer layer PSO solutions is conducted by using a position vector consisting of two components representing theX and Y coordinates of the depot location. The outer layer PSO solution (XD={X1D,X2D}) is shown in Table 2. The fitness calculation is then performed by transferring the depot coordinates (XD) to the inner layer PSO for optimal routing calculation and the resulting total routing distance is adopted as the fitness value of the outer layer PSO.Table 2
Solution representation (outer layer PSO).
X
D
X
1
D
X
2
D
Depot location
X coordinate
Y coordinate


## 3.4. Routing Balance Insertion Local Search

The local search is a search tactic to generate new solutions in the neighborhood of the current solution to attempt to find a solution with better quality. A new local search is designed and conducted to generate a new solution and is selected to be the starting point of the algorithm when the next iteration takes place if it is a better solution.The new local search tactic named routing balance insertion (RBI) local search is applied in the inner layer PSO, which is inspired from the well-used nearest neighborhood heuristic in TSP. The RBI local search moves the nearest customer from the longest route to the shortest route to reduce the travel distance; the nearest customer is determined based on the distance between the customer and the centroid of the shortest routing cluster. The operations of the designed RBI local search are as follows.Step 1.
Select the longest routing path and the shortest routing path. Figure4 shows the resulting CVRP results, Route-1 is the routing path starting from depot (O) and visiting A, B, C, D, E, and F then back to O; Route-2 is the routing path starting from O and visiting G, H, and I then back to the depot. Assuming the travel distances of the corresponding vehicle routes are d1, d2, and d3, respectively. Suppose the max⁡{d1,d2,d3} is d1 and the min⁡{d1,d2,d3} is d2.Figure 4
Obtained CVRP results.Step 2.
Calculate the centroid position of the customers consisting of the shortest route (Route-2). The centroid position (CC=(xC,yC)) can be yielded by (5)xC=∑i=1kxiv+xOk+1,yC=∑i=1kyiv+yOk+1.In (5), xC and yC are the coordinates of the centroid position of route v (vehicle v). The xiv and yiv are the coordinates of the customers assigned to the vehicle v; xO and yO are the coordinates of the depot position.Step 3.
Calculate the distances from the customers assigned to the longest route (Route-1) to the centroid. AssumingdA,dB,… and dF are the distances from customers A,B,… and F to the centroid, as displayed in Figure 5. Suppose dB is the minimum distance, that is, customer B is the nearest one to the shortest route.Figure 5
The centroid and the distances from customer on the longest route.Step 4.
Delete customerB from Route-1 and insert B into Router-2. The travel distance of the Route-1 decreases after the customer B is removed, the decreased distance is d=AB+BC-AC. Meanwhile, there are four possible positions for inserting B as illustrated in Figure 6. The increased distances after inserting B to the four possible positions are d1=OB+BG-OG, d2=GB+BH-GH, d3=HB+BI-HI, and d4=IB+BO-IO, respectively. The insertion position is then determined by comparing d1, d2, d3, and d4. Restated, the insertion position decision is based on the min⁡{d1,d2,d3,d4}. For example, the customer B is being inserted between G and H if the d2 is the minimum increased distance as in Figure 6(b).Figure 6
Four possible insertion positions.
(a)
d
1
=
O
B
+
B
G
-
O
G
(b)
d
2
=
G
B
+
B
H
-
G
H
(c)
d
3
=
H
B
+
B
I
-
H
I
(d)
d
4
=
I
B
+
B
O
-
I
O


## 3.5. Optimal Depot Location Determination

The optimal depot location is determined using the outer layer PSO. The determined particle solution,XD, is passed to the inner layer PSO as the depot location. The inner layer PSO solves the CVRP problem on the basis of this depot location, and the minimum total vehicle routing distances (Fitness in (1)) are returned to the outer PSO. This returned Fitness is then used as the objective corresponding to XD. Accordingly, particle experience and swarm experience can be obtained. Thereafter, the velocity in the outer layer PSO is updated; a new position XD is generated and will be the new depot location. After alternating evolutions of the inner layer and outer layer PSO, an optimal depot location can be acquired.


## 3.6. Hierarchical PSO

The collaboration operation of the proposed inner and outer layer PSOs is as follows.(1)
Outer layer PSO: outputs determined depot location (XD) to the inner layer PSO.(2)
Inner layer PSO: determines total travel distance (TTD) based onXD; returns the total travel distance to the outer layer PSO.(3)
Outer layer PSO:
(i)
evaluates the quality of the depot location (XD), that is, fitness(XD) = TTD;(ii)
updates individual and swarm experience;(iii)
updates velocity and position vector;(iv)
outputs new depot location (XD) to the inner layer PSO.(4)
Repeats Steps3 and 4 until termination condition is met.(5)
Outer layer PSO: outputs the optimal depot location and the corresponding vehicle routes.The detailed flowchart of the proposed hierarchical PSO for optimal CVRP depot location and optimal vehicle routes is summarized in Figure 7.Figure 7
Flowchart of the proposed hierarchical PSO.


## 4. Experimental Results

To verify the performance of the method proposed in this work to establish the optimal depot location, simulations on a famous benchmark were conducted. The instances tested are those designed by Augerat aiming at capacitated vehicle routing problems. There are 9 instances selected from the database athttp://www.branchandcut.org/VRP/data; they are A-n32-k5, A-n33-k5, A-n36-k5, A-n45-k6, A-n45-k7, A-n55-k9, A-n60-k9, A-n62-k8, and A-n64-k9. An instance is expressed by A-nXX-kY, where XX stands for the number of customers plus depots and Y indicates the number of vehicles.Table3 demonstrates the difficulty of solving the studied CVRP problems. Assuming n customers are serviced by m vehicles, in average every vehicle needs to visit n/m customers. Therefore, the time required by exhaustive search for the A-n32-k5 instance would be 1.67 × 1025  × 10−8 seconds ≈ 1.9 × 1012 days, with a solution that can be found in 0.01 μsec (10−8 sec) is assumed. For another example case, the time required by exhaustive search for the A-n64-k8 instance would be 2.53 × 1062  × 10−8 seconds ≈ 3.69 × 1049 days. Hence, a PSO metaheuristic algorithm is applied in this study.Table 3
Complexity of the VRP scheduling problem.
Customers
Vehicles
Solution space
n
=
X
X
-
1
m
m
×
(
n
/
m
)
!
×
m
n
31
5
5 × 6! × 531 ≈ 1.67 × 1025
54
9
9 × 6! × 954 ≈ 2.19 ×   1055
63
8
8 × 8! × 863 ≈ 2.53 × 1062Table4 lists the required number of component velocity and position vectors for the inner PSO to find the optimal routes. To solve the two issues encountered in obtaining the CVRP optimal routes, there is one commonly used design when applying PSO: two PSOs are dedicated to solve corresponding issues. However, the required number of components in either the velocity or position vector is n+n components in total; however, only n+(m-1) components are required in the proposed novel particle encoding scheme. Hence, the computational complexity is decreased dramatically for large scale problems.Table 4
Particle complexity on finding optimal routes.
Two PSOs
Proposed PSO
Number of component
n + n
n + (m-1)
Example
A-n32-k5
31
+
31
31
+
4
A-n54-k9
53
+
53
53
+
8
A-n64-k8
63
+
63
63
+
7In this work, the experiments were processed in two stages. The first stage is to find out the best mechanisms employed in the inner layer PSO, including the local search. The second stage is to check the improvements when the depot location is determined by using the outer layer PSO. Restated, the resulting fitnesses after and before outer layer PSO application are compared to observe the level of improvement. During the test in the first stage, the customers provided in the benchmark were divided into small, medium, and large scales. Three instances for each scale were adopted to run the test. The inner layer PSO parameters were 100 particles, the learning factorsc1=2 and c2=1, and the number of iterations was 1000. The outer layer PSO involved 8 particles, the learning factors were set to c1=c2=2 and 100 iterations were conducted. The comparison criterion is on the basis of deviation. The deviation (DEV) is defined in (6)DEV%=Makespansol-BKSBKS×100%,where BKS is the best known solution provided in the benchmark, Makespansol is the shortest total routing distance obtained by the proposed method. The best deviation from 10 trials was selected for comparison. Moreover, the average deviation (Avg. Dev) is also defined as in(7)Avg.Dev%=∑i=1nDEVin,where n is the trial runs for a specific test problem instance; 10 trial runs were conducted in this work, that is, n=10.The testing environment of the experiment included the Windows 7 SP1 operating system running on an Intel Core i7 CPU 4770 3.40 GHz CPU with 4 GB RAM. C# was applied to implement the method proposed in this study.


### 4.1. Inner-Layer PSO: Local Searches

To test the efficiency of different local searches, interchange (LS1), RBI (LS2), combining interchange, and RBI (LS3) were tested. The results are as shown in Figure 8. It indicates that either swap or RBI local search is able to improve the efficiency. The proposed RBI local search (Avg. Dev. = 18%) outperforms swap local search (Avg. Dev. = 20%) and without the local search (Avg. Dev. = 28%). Moreover, both swap and RBI involved in the algorithm are able to further enhance the performance (Avg. Dev. = 14%). Therefore, the inner layer PSO involving swap local search and RBI local search was included while searching for the optimal depot location by the outer layer PSO.Figure 8
Simulation results of applying local searches.


### 4.2. Outer Layer PSO

In this section, the experimental results with and without applying the outer layer PSO to find the optimal depot location are compared. The depot locations provided in the benchmark were used as the default depot locations, the fitness (Fit) based on (1) was calculated. Figure 9 shows the inner layer PSO and outer layer PSO evolution curves for the A-32-k5 instance. Figures 10(a) and 10(b) display the resulting vehicle routes before and after applying outer layer PSO, respectively. The fitness of using the default depot is 784, but the fitness of using a determined depot by the proposed outer layer PSO is 660. Restated, the determined depot would greatly reduce the vehicle routing cost.Figure 9
PSO evolution example for instance A-32-k5: (a) inner layer PSO and (b) outer layer PSO.
(a)
(b)Figure 10
Resulting vehicle routes example for case A-32-k5: (a) without depot determination and (b) with depot determination by outer layer PSO.
(a)
(b)Table5 displays the experimental results of using default depot location (without adjustment of the depot location, i.e., before the outer layer PSO was applied) and determined depot location (with adjustment of the depot location after outer layer PSO application). Ten trials were conducted; the minimum fitness (Min. Fit) and average fitness (Avg. Fit) are provided. Meanwhile, the improvement was calculated according to (8)Imp(%)=Fitnessw/o-FitnessdepotFitnessw/o×100%,where Fitnessw/o is the fitness without the depot location adjustment and the Fitnessdepot is the fitness with the depot location adjustment. Restated, the Imp represents the percentage of the reduced fitness (total routing distance decreased). According to the experimental results, up to 18% average minimum Imp (Min. Imp) and 16% averaged Imp (Avg. Imp) of trial runs were acquired. Therefore, the proposed scheme in this work is able to additionally allow companies to determine the optimal depot or plant site setting.Table 5
Improvement of the proposed scheme.
Instance
Default
Determined depot
Improvement
Min. Fit
Min. Fit
Avg. Fit
Min. Imp
Avg. Imp
A-n32-k5
784
660
660
19%
19%
A-n33-k5
661
627
632
5%
5%
A-n36-k5
799
685
696
17%
15%
A-n45-k6
944
842
931
4%
1%
A-n45-k7
1146
829
864
38%
33%
A-n55-k9
1073
1063
1078
1%
0%
A-n60-k9
1408
1096
1118
28%
26%
A-n62-k8
1315
1187
1098
19%
18%
A-n64-k9
1177
1140
1081
33%
30%
Average
18%
16%Finally, a real world case was implemented. The real world case includes 15 cooperation factories and a new assembly plant is planned to set up to produce commodities. The location of this assembly plant needs to be determined to reduce the costs. The requirement is that the assembly plant needs to send out 3 trucks to carry all needed parts from all cooperation factories and back to the assembly plant for further processes. The vehicle routing based on the original plant location is displayed in Figure11(a), the vehicle routing on the basis of the determined new plant location using the proposed scheme is illustrated in Figure 11(b). The travel distances of the original plant vehicle routes and new plant vehicle routes are about 52.2 Km and 37.1 Km, respectively.Figure 11
Vehicle routes based on: (a) original plant location and (b) determined new plant location by the proposed PSO scheme.
(a)
(b)


## 4.1. Inner-Layer PSO: Local Searches

To test the efficiency of different local searches, interchange (LS1), RBI (LS2), combining interchange, and RBI (LS3) were tested. The results are as shown in Figure 8. It indicates that either swap or RBI local search is able to improve the efficiency. The proposed RBI local search (Avg. Dev. = 18%) outperforms swap local search (Avg. Dev. = 20%) and without the local search (Avg. Dev. = 28%). Moreover, both swap and RBI involved in the algorithm are able to further enhance the performance (Avg. Dev. = 14%). Therefore, the inner layer PSO involving swap local search and RBI local search was included while searching for the optimal depot location by the outer layer PSO.Figure 8
Simulation results of applying local searches.


## 4.2. Outer Layer PSO

In this section, the experimental results with and without applying the outer layer PSO to find the optimal depot location are compared. The depot locations provided in the benchmark were used as the default depot locations, the fitness (Fit) based on (1) was calculated. Figure 9 shows the inner layer PSO and outer layer PSO evolution curves for the A-32-k5 instance. Figures 10(a) and 10(b) display the resulting vehicle routes before and after applying outer layer PSO, respectively. The fitness of using the default depot is 784, but the fitness of using a determined depot by the proposed outer layer PSO is 660. Restated, the determined depot would greatly reduce the vehicle routing cost.Figure 9
PSO evolution example for instance A-32-k5: (a) inner layer PSO and (b) outer layer PSO.
(a)
(b)Figure 10
Resulting vehicle routes example for case A-32-k5: (a) without depot determination and (b) with depot determination by outer layer PSO.
(a)
(b)Table5 displays the experimental results of using default depot location (without adjustment of the depot location, i.e., before the outer layer PSO was applied) and determined depot location (with adjustment of the depot location after outer layer PSO application). Ten trials were conducted; the minimum fitness (Min. Fit) and average fitness (Avg. Fit) are provided. Meanwhile, the improvement was calculated according to (8)Imp(%)=Fitnessw/o-FitnessdepotFitnessw/o×100%,where Fitnessw/o is the fitness without the depot location adjustment and the Fitnessdepot is the fitness with the depot location adjustment. Restated, the Imp represents the percentage of the reduced fitness (total routing distance decreased). According to the experimental results, up to 18% average minimum Imp (Min. Imp) and 16% averaged Imp (Avg. Imp) of trial runs were acquired. Therefore, the proposed scheme in this work is able to additionally allow companies to determine the optimal depot or plant site setting.Table 5
Improvement of the proposed scheme.
Instance
Default
Determined depot
Improvement
Min. Fit
Min. Fit
Avg. Fit
Min. Imp
Avg. Imp
A-n32-k5
784
660
660
19%
19%
A-n33-k5
661
627
632
5%
5%
A-n36-k5
799
685
696
17%
15%
A-n45-k6
944
842
931
4%
1%
A-n45-k7
1146
829
864
38%
33%
A-n55-k9
1073
1063
1078
1%
0%
A-n60-k9
1408
1096
1118
28%
26%
A-n62-k8
1315
1187
1098
19%
18%
A-n64-k9
1177
1140
1081
33%
30%
Average
18%
16%Finally, a real world case was implemented. The real world case includes 15 cooperation factories and a new assembly plant is planned to set up to produce commodities. The location of this assembly plant needs to be determined to reduce the costs. The requirement is that the assembly plant needs to send out 3 trucks to carry all needed parts from all cooperation factories and back to the assembly plant for further processes. The vehicle routing based on the original plant location is displayed in Figure11(a), the vehicle routing on the basis of the determined new plant location using the proposed scheme is illustrated in Figure 11(b). The travel distances of the original plant vehicle routes and new plant vehicle routes are about 52.2 Km and 37.1 Km, respectively.Figure 11
Vehicle routes based on: (a) original plant location and (b) determined new plant location by the proposed PSO scheme.
(a)
(b)


## 5. Conclusions

This study proposes a hierarchical PSO consisting of an inner layer PSO and an outer layer PSO to obtain the optimal depot location and the corresponding vehicle routing to minimize the total routing distance. The inner layer PSO is used to find the optimal vehicle routing while the outer layer is used to determine the optimal depot location. In the inner layer PSO, a new designed routing balance insertion (RBI) local search is suggested to improve solution quality. The RBI local search moves the nearest customer from the longest route to the shortest route to reduce the travel distance; the nearest customer selection is based on the distance between a customer and the centroid of the shortest routing cluster. The experimental results with and without local search schemes are demonstrated in Figure8, in which the average deviation can be lowered (Avg. Dev = 14%) while applying local searches. Meanwhile, a novel particle encoding scheme is designed to handle customer-to-vehicle assignment and customer visiting order issues simultaneously to greatly lower processing efforts and hence reduce the computational complexity as indicated in Table 4.The experimental results indicate that the total vehicle routing distance of the tested instances is significantly reduced, up to an average improvement of 16%. In the A-n45-k7 instance, the minimum and average fitnesses of ten trials can be improved up to 38% and 33%, respectively. Therefore, the location of a depot can indeed affect vehicle routing costs, which can be greatly lowered by the proposed hierarchical PSO with the novel encoding scheme and the RBI local search in this study. Restated, the suggested PSO is able to effectively establish the optimal location to set up a depot thus increasing profits. According to the real-world case simulation as indicated in Figure11, the new plant location is able to significantly reduce the cost ((52.2-37.1)/52.2)×100%≅29%. However, to further enhance the performance, local search heuristics such as insertion, exchange and other local searches can be integrated into the proposed scheme. Meanwhile, different metaheuristic algorithms such as genetic algorithm and ant colony optimization can be utilized to solve this studied problem in the future.



---

*Source: 743507-2015-10-19.xml*