A novel approach to combine the hierarchical and iterative techniques for solving capacitated location-routing problem

Figures & data

Figure. 1. Typical portray of multi hub network for LRP.

Table 1. Nomenclature of the notations used in this article

Notations	Description
N	Total number of customers
P	Number of candidate hubs in a problem statement
p	Minimum hubs required to satisfy the total demand of customers
p	Number of hubs to be opened for a solution
t	Current iteration number
T	Maximum number of iteration; Termination criteria
C	Customer Vector, a permutation of all customer nodes
H	Hub Vector, a binary vector representing opened hubs
CC	Customer cluster vector
g	Indices of particles
j	Indices of clusters
V	Velocity for any particle to move from current to new position
Z	Population size

Figure. 2. Sketch of the Tri-fold PSO in the proposed Hierarchical-Iterative approach.

Table

Algorithm 1. Pseudocode of the combined hierarchical-iterative framework.
/* Initialize the Swarm */
1. Find p , minimum number of hubs required to serve the total demand of customers
2. For i = 1 to Z do /* Z is the size of population */
A. Set C i(0) to a random permutation of customers
B. Set p to a random number in range [ p , |P|]
C. Set H i(0) to a random permutation of p hubs selected from P
D. Set $V_{i(0)}^C$ to a random SS
E. Set $V_{i(0)}^H$ to a random velocity
3. End for
/* Iteration phase */
4. Set t = 0
5. Repeat
A. For i = 1 to Z do
i. [C′ i(t) , S i(t) ] = decode(C i(t) , H i(t))
ii. For each cluster CC defined by C′ i(t) , H i(t) and S i(t) do
[CC ji(t), $R_{ji(t)}^{\mathit{CC}}$] = Solve VRP for cluster CC
iii. End for
iv. Calculate fitness of ith particle
v. Apply Local Search (LS) on particle i
vi. Update local best solution L i if necessary
B. End for
C. Update global best solution Γ if necessary
D. Add the best of the local best solutions to the pool
E. Refine and Apply local search on the pool
F. Update global best solution Γ if necessary
G. t = t + 1
H. if t > max_iter then return Γ
I. Update $V_{i(t)}^C$ and $V_{i(t)}^H$ using Equations (2) and (4).
J. Update $C_{i(t)}$ and $H_{i(t)}$ using Equations (1) and (3).
6. Until false

Table

Algorithm 2. Decoding a customer vector to make comprehensive representation of clusters
Inputs
C: customer vector
p: number of opened hubs, i.e. required clusters
Outputs
ClustersMade: a Boolean value Indicating whether clusters could successfully be made
cluster: the clusters made
Procedure
1. Put the first p nodes of C to the p clusters
2. i = p;
3. while i <= |C| do
4.  i = i+1; // index of the next node in C to insert in any cluster
5.  sortedClusters = cluster indices of sorted in non-increasing order based on distances from the hubs to C(i)
6.  assigned = 0;
7.  for j = 1 to | sortedClusters | do
8.   r = sortedClusters (j);
9.   if addition of C(i) to cluster(r) satisfies hub capacity constraint then
10.    add C(i) to cluster(r);
11.    assigned = 1;
12.    go to 15;
13.   end if
14.  end for
15.  if assigned == 0 then // C(i) was not assigned to any cluster in loop from line 7 to 14
16.   maxClusterSize = maximum number of nodes assigned to a cluster
17.   for k = maxClusterSize down to 1 do
18.    sortedClusters = indices of clusters sorted in non-increasing order based on the increases of the total distances if the kth nodes of the clusters are replaced by C(i)
19.    for j = 1 to | sortedClusters | do
20.     r = sortedClusters (j);
21.     if replacing k ^th node of cluster(r) by C(i) satisfies hub capacity constraint then
22.      add kth node of cluster(r) to the end of C; // to be assigned again
23.      replace kth node of cluster(r) by C(i);
24.      assigned = 1;
25.      go to 30;
26.     end if
27.    end for
28.   end for
29.  end if
30.  if assigned == 0 then
31.   ClustersMade = 0;
32.   return;
33.  end if
34. end while
35.   ClustersMade = 1;
36. return;

Table

Algorithm 3. Making routes for a cluster
Inputs
CC : customers cluster vector or customers in a hub
// decode for each hub
Outputs
routesMade: a Boolean value Indicating whether routes could successfully been made
routes: the routes made
Procedure
1. m = estimateRequiredRoutes(); // Number of vehicle required if we assign customers sequentially one after another to vehicles as they appear in the vector
2. for r = 1 to m do
3.  routes(r) = CC(r); // put the first m nodes in c as the starting nodes of the m routes
4. end for
5. i = m;
6. while i <= |CC| do
7.   i = i+1; // index of the next node in CC to insert in any route
8.   sortedRoutes = indices of routes sorted in non-increasing order based on distances of their last nodes to CC(i)
9.   assigned = 0;
10.  for j = 1 to |sortedRoutes| do
11.   r = sortedRoutes(j);
12.  if addition of CC(i) to the end of routes(r) satisfies capacity constraints then
13.   add CC(i) to the end of routes(r);
14.  assigned = 1;
15.  go to 18;
16.  end if
17.  end for
18.  if assigned == 0 // CC(i) was not assigned to any route in the loop from line 10 to 17
19.  maxRouteSize = maximum number of nodes assigned to a route
20.  for k = maxRouteSize down to 1 do
21.    sortedRoutes = indices of routes sorted in non-increasing order based on the increases of the distances if the kth nodes of the routes are replaced by CC(i)
22.   for j = 1 to |sortedRoutes| do
23.  r = sortedRoutes(j);
24.   if replacing kth node of routes(r) by CC(i) satisfies capacity constraints then
25.      replace kth node of routes(r) by CC(i);
26.     add kth node to the end of CC; // to be assigned again
27.    assigned = 1;
28.   go to 33;
29.  end if
30.  end for
31.  end for
32.  end if
33.    if assigned == 0 then
34.     routesMade = 0;
35.     return;
36.    end if
37.  end while
38.   routesMade = 1;
39. return;

Table 2. Properties of the Barreto instances (Barreto et al., 2007)

Number of hubs	Number of customers	Demand of customers	Capacity of hubs	Capacity of transports	Customer location
{5, 8, 10}	{21, 22, 27, 29, 32, 36, 50, 75, 88, 100, 134, 150}	Distribution mentioned in dataset Prodhon (2010)	Distribution mentioned in dataset Prodhon (2010)	{160, 200, 250, 850, 2,500, 4,500, 6,000, 8,000, 11,000, 8,000,000, 9,000,000}	Randomly generated

Table 3. Performances of different algorithms on Barreto instances

Algorithm		HybPSO-LRP ^a			Proposed tri-fold PSO
Problems	BKS	Cost	CPU	Gap (%)	Cost	CPU	Gap (%)
Christofides	565.65	582.7	0.05	3.01	587.81	0.66	3.9
69-50x5
Christofides	861.6	886.3	0.37	2.87	865.28	1.2	0.4
69-75x10
Christofides	842.9	889.4	0.58	5.52	841.97 *	1.15	−0.1
69-100x10
Daskin	355.8	384.9	1.11	8.18	356.66	1.75	0.24
95-88x8
Daskin	44,011.7	46,642.7	2.31	5.98	44,814.1	4.8	1.82
95-150x10
Gaskell	424.9	432.9	0.01	1.88	424.9	0.2	0.00
67-21x5
Gaskell	585.1	588.5	0.07	0.58	585.1	1.1	0.00
67-22x5
Gaskell	512.1	512.1	0.12	0.00	512.1	1.65	0.00
67-29x5
Gaskell	571.7	570.8	0.15	−0.16	562.22 *	1.3	−1.66
67-32x5
Gaskell	504.3	511.1	0.16	1.35	504.3	1.3	0.00
67-32x5
Gaskell	460.4	470.7	0.15	2.24	460.4	1.4	0.00
67-36x5
Min	3,062.0	3,062.0	3.18	0.00	3,062.0	2.1	0.00
92-27x5
Min	5,809.0	5,950.1	3.10	2.43	5,931.22	3.6	2.1
92-134x8
Average			0.81	2.42		1.59	0.48

Notes: Boldface Cost values are better fitness value than HybPSO-LRP.

* Marked fitness values are better than the best known results in the literature.

^a Results reprted in Marinakis and Marinaki (2008).

Figure. 3. Performance comparison between HybPSO-LRP and proposed TPSO.

Barreto, S. , Ferreira, C. , Paixao, J. , & Santos, B. S. (2007). Using clustering analysis in a capacitated location-routing problem. European Journal of Operational Research , 179 (3), 968–977.10.1016/j.ejor.2005.06.074

 Web of Science ®Google Scholar

Prodhon, C. (2010, February 25). Classical instances for LRP. Retrieved December 15, 2017, from http://prodhonc.free.fr/Instances/instances_us.htm

 Google Scholar

Marinakis, Y. , & Marinaki, M. (2008). A particle swarm optimization algorithm with path relinking for the location routing problem. Journal of Mathematical Modelling and Algorithms , 7 (1), 59–78.10.1007/s10852-007-9073-6

 Google Scholar