Implementation and Analysis of a CVRP Heuristic Algorithm

This project focuses on the Capacitated Vehicle Routing Problem (CVRP), a crucial area of study in logistics and operations research. The assignment details the problem of designing cost-effective routes for a fleet of vehicles with capacity constraints, originating from a central depot to a set of geographically dispersed customers. The solution uses a heuristic approach based on the Adaptive Large Neighborhood Search (ALNS) algorithm. It includes a mathematical formulation, constraints, and an objective function to minimize the total travel distance. The core of the project is the proposed heuristic algorithm, which involves steps to determine an initial solution and then refine it using relocation procedures and a movement list to prevent cycling. The algorithm's performance is tested on benchmark problems, and computational results are presented, comparing the proposed algorithm's solutions with optimal or best-known solutions. The project also includes a real-world application, describing a case study of a furniture company and comparing the algorithm's solutions with the company's existing solutions, demonstrating the algorithm's efficiency through a paired sample t-test. Overall, the project provides a comprehensive analysis of the CVRP and a practical application of a heuristic algorithm to solve it.

VEHICLE ROUTING
INTRODUCTION
The vehicle routing problem with capacity constraints is one of the common subject of study.The main
is to design the least cost routes for fleet of vehicles from one point to the set points.Vehicles belong to
a fleet located to the central depot and have a capacity .The cost of each customer’s travel depends on
the distance travelling .The algorithm in use here is the based on thr heuristic approach and is based on
Ropke pisinger in terms of ALNS
ABSTRACT
VRP consists of the problems in which a set of routes for a fleet of vehicles based at one or several
depots must be established for a number of geographically dispersed cities or customers .The aim here
is to find the set of routes at a minimal cost basically finding the shortest path,minimizing the number of
vehicles and others.
NOTE:CVRP is same as VRP
The mathematical formula would be;
A capacity of each vehicle
V maximum number of vehicles
Fij thye flow of cores from node i to j
Z total transportation cost
Di demand at node i
Cij Distance between node I and j
Xi,j{1,0 if vehicle moves from node I to j
0 otherwise
N number of nodes
The model constraints are:
\mathop \sum \limits_{l = 2, a\ne l}^{N} x_{la} + x_{1a} = 1\quad \quad \for all a
(2)
\mathop \sum \limits_{l = 2, a \ne l}^{N} x_{al} + x_{a1} = 1\quad \quad \for all a
(3)

\mathop \sum \limits_{a = 2}^{N} x_{1a} \le V
(4)
\mathop \sum \limits_{j = 1, j \ne i}^{N} x_{ij} = \mathop \sum \limits_{j = 1, j \ne i}^{N} x_{ji} \quad \
quad \for all i
(5)
x_{aa} = 0\quad \quad \forall a
(6)
x_{la} + x_{al} = 1\quad \quad \for all a, \, l_{a \ne 1}
(7)
\mathop \sum \limits_{j = 1,j \ne i}^{N} F_{ij} = \mathop \sum \limits_{j = 1,j \ne i}^{N} F_{ji} + d_{i} \
quad \quad \for all i_{i > 1}
(8)
d_{i} .x_{ij} \le F_{ij} \quad \quad \for all i,j_{i \ne j}
(9)
F_{ij} \le \left( {A - d_{j} } \right).x_{ij} \quad \quad \for all i,j_{i \ne j}
(10)
The objective function (1) of the model is to minimize the total traveled distance. The constraints (2) and
(3) state that there is exactly one departure from node i. The constraint (4) provides not to exceed the
total number of vehicles. Constraint (5) provides balance between incoming and outgoing arcs at a given
node. Constraint (6) eliminates flow from node i to node i. Constraint (7) is trivial sub-tour elimination
constraint. Constraints (8), (9) and (10) provide balance between total inflow and outflow at node.
This mathematical model can be used for only small-scale CVRP because it is quite difficult to achieve an
optimal solution with traditional optimization methods due to the high computational complexity for
large-scale problems. For this reason, we constructed a novel heuristic algorithm for CVRP in this study.
algorithm for CVRP
In this section, our proposed algorithm is explained. We used following notation in the algorithm. The
points to visit are denoted by a set of S which has number of p elements as S = \left\{ {1, \ldots , \, p} \
right\}. All the points are also denoted analytically by an arc set of P as P = \left\{ {\left( {x_{i} , \, y_{i} } \
right):\,\,i\,\, \in \,\,S} \right\}. \Delta_{ij} = \left( {\left( {x_{i} - x_{j} } \right)^{2} + \left( {y_{i} - y_{j} } \
right)^{2} } \right)^{0.5} is the distance matrix which states the distance between the elements of S set.
A solution is the sets R of k routes and also vehicles, Rk ⊆ S and k are less than and equal to the number

of free vehicle t. All the points to visit have a demand di and the capacity of free vehicles meeting the
total demand is assumed as \varSigma d_{i} \le tC. We determined the objective function asF = \var
Sigma_{a = 1}^{t} \var Sigma_{i = 1}^{p} \var Sigma_{j = 1}^{p} \pi_{ija} \Delta_{ij} \;{\text{for all}}\,\,i, \,
j\, \in S, \, i \ne j{\text{ and }}a \le t,where
\pi_{ija} = \left\{ {\begin{array}{*{20}l} 1 \hfill & {{\text{from}}\,\,i\,\,{\text{to}}\,\,j\,\,{\text{by}}\,\,{\
text{vehicle}}\,\,a} \hfill \\ 0 \hfill & {\text{otherwise}} \hfill \\ \end{array} } \right..
The capacity constraints must be kept down while searching for a solution. Therefore, we determined a
function to control the feasibility of the candidate solution as \sum\nolimits_{a= 1}^{t} {\pi_{ija} d_{j} \le
C }\;{\text{for all}}\;i, j \in S\;{\text{and}}\;i \ne j .
One of our motivations is that the quality of initial solution affected the performance of the algorithm.
Hence, we prefer to start the solution by these steps:
Step 1: Start from a random i point and determine the πijk as 1 considering the minimum value of Δij,
where the S = S* and Rk = Rk*.
Step 2: Calculate the \bar{C}_{a} = C_{a} + d_{j} and S* = S\backslash \left\{ j \right\} and R_{a} * =
R_{a} \, \cup \,\left\{ j \right\}.
Step 3: Repeat steps 1 and 2 up to \bar{C}_{a} \ge C. When this is met, increase the value of a as 1.
Step 4: Run the all previous steps until S* \in ∅. At last all of Rk* state us the solution.
After determining the initial solution, new solutions are determined by ALNS. In this study, we
constructed a relocation procedure to search neighborhoods. The steps of the procedure consist of
these steps:
Stage 1: Select one of each point i from each routes Rk* by roulette wheel principle using Eq.
p_{a} = \frac{{\sum\nolimits_{i = 1}^{p} {\sum\limits_{j = 1}^{p} {\pi_{ija} \Delta_{ij} } } }}{{\sum\
nolimits_{a = 1}^{t} {\sum\limits_{i = 1}^{p} {\sum\limits_{j = 1}^{p} {\pi_{ija} \Delta_{ij} } } } }}.
(11)
Stage 2: Determine the second closest points to each selected points according to the Δij matrix.
Stage 3: Start from the R1 and relocate the selected point with its second closest point. If the selected
point and its second point are in the same route, do not relocate them. So we can prevent to enhance
the solution space too much.
Stage 3 : While relocating, \bar{C}_{a} = C_{a} + d_{j} should be revised and route capacity should be′
controlled.
Stage 4: Stages 2 and 3 are repeated for all the points which were selected in Stage 1.

The relocation procedure is illustrated in the figures below D, H, J and P points were randomly selected.
The second closest points to them E, I, H and A were chosen respectively. Part (b) of the second figure
shows us a neighbor solution after relocation under condition of the capacity constraint in not exceeded.
Relocation
In addition, there is a movement list to prevent cycling in the proposed algorithm. This list prohibits the
use of some specific set of solutions for several iterations if one of them is used in recent iterations.
Therefore, the search does not travel around the local optimum points. We preferred to determine the
size of the list experimentally.
Finally, each iteration of the proposed algorithm that can be achieved by serving two vertices on the
same route instead of leaving them on separate routes is implemented to improve the solution and a
non-tabu solution is selected as a new solution. The algorithm after determining an initial solution steps
w

Pseudo codes of proposed algorithm
Computational results on benchmark problems
The proposed algorithm is tested on three (A, M and G) sets of benchmark instances with different
number of customers/points in the literature.
Table 1
Comparison between the solutions of proposed algorithm and best well-known solutions
Prob. # Prob. code Optimal/Best Current result Our result Difference % Difference CPU time (s)
1 A-n32-a5 Optimal 782 786 0 0.000 1.24
2 A-n33-a5 Optimal 660 662 0 0.000 1.30
3 A-n33-a6 Optimal 740 742 0 0.000 2.26
4 A-n34-a5 Optimal 780 776 0 0.000 2.96
5 A-n36-a5 Optimal 800 798 0 0.000 7.54
6 A-n37-a5 Optimal 670 668 0 0.000 12.63
7 A-n37-a6 Optimal 950 947 0 0.000 14.88
8 A-n38-a5 Optimal 728 731 0 0.000 22.30
9 A-n39-a5 Optimal 824 826 0 0.000 48.52
10 A-n39-a6 Optimal 830 828 0 0.000 44.60
11 A-n44-a6 Optimal 938 940 4 0.002 102.02
12 A-n45-a6 Optimal 940 954 10 0.013 97.86
13 A-n45-a7 Optimal 1144 1156 8 0.004 230.60
14 A-n46-a7 Optimal 912 914 1 0.001 201.94
15 A-n48-a7 Optimal 1075 1075 0 0.000 298.74
16 A-n53-a7 Optimal 1014 1024 12 0.010 1987.46
17 A-n54-a7 Optimal 1169 1169 2 0.002 2369.50
18 A-n55-a9 Optimal 1073 1074 1 0.001 3892.10

Prob. # Prob. code Optimal/Best Current result Our result Difference % Difference CPU time (s)
19 A-n60-a9 Optimal 1350 1365 12 0.009 7760.20
20 A-n61-a9 Optimal 1036 1043 10 0.011 7239.98
21 A-n62-a8 Optimal 1290 1300 16 0.011 12331.62
22 A-n63-a9 Optimal 1618 1642 30 0.018 11906.00
23 A-n63-a10 Optimal 1316 1327 10 0.010 11999.34
24 A-n64-a9 Optimal 1401 1442 41 0.029 17002.33
25 A-n65-a9 Optimal 1176 1188 15 0.013 18071.72
26 A-n69-a9 Optimal 1160 1169 12 0.009 18720.04
27 A-n80-a10 Optimal 1763 1790 27 0.015 20692.47
28 M-n151-a12 Best 1055 1050 −5 −0.005 37360.20
29 M-n200-a17 Best 1374 1330 −40 −0.032 42873.24
30 G-n262-a25 Best 6120 5877 −244 −0.04 45302.09
The proposed heuristic algorithm can find the optimal solution immediately for small-scale problems.
We mean with small scale that which has less than fifty points. When the scale of the problem gets
larger, the algorithm converged to the optimal solution with 0.01% difference approximately. In addition
to this, we found the new best solutions for the problems whose optimal solutions have not been found
yet.
Application in life
In this section, we will summarize a project which motivated us to study this problem. We studied on
the CVRP problem of a company which produces office furniture in NAIROBI City, Turkey. The company
produces and distributes the office furniture products (staff tables, meeting tables, workstations,
working chairs, guest chairs, many more.) to the customers. The company has sufficient number of
identical vehicles for carrying. The vehicles distribute orders from 08:00 a.m. to 18:00 p.m. That is to say,
there are only 8 h for distribution and assembly per day. Based on this, the vehicles can be loaded up to
16 customers’ orders. In addition, the weight capacity is 1600 kg and volumetric load capacity is 5000 L
of the vehicles.

We handled the 28-day transportation problem of the company and we solved these 30 different
problems and run up to 21,600 s by the proposed algorithm and compared with company’s previous
solutions. Then we applied paired sample t test to evaluate the performance of these solutions to
illustrate the efficiency of our algorithm.
T test is applied to compare the solutions . It illustrates that the company’s solutions and the proposed
algorithm’s solutions are different in a given confidence interval and proposed algorithm’s solutions are
better than company’s solutions.
H_{0} = \mu_{\text{A}} = \mu_{\text{B}}
H_{1} = \mu_{\text{A}} \ne \mu_{\text{B}}
where μA average cost of 30 problems solved by the companyμB average cost of 30 problems solved by
the proposed algorithm.
Table 2
Comparison between our solutions and company’s solutions for 30 days
customers vehicle
Distance in the
global world
Distance from
the algorithm customers vehicles Global
solution
Algorithm
solution
1 105 8 1732 1647 16 115 8 1819 1722
2 117 8 1912 1880 17 109 8 1752 1740
3 124 10 2601 2509 18 92 7 1057 1043
4 123 11 2405 2401 19 98 7 1204 1107
5 104 8 1427 1292 20 97 7 1187 1092
6 95 7 1176 1095 21 40 3 648 637
7 101 8 1397 1303 22 106 8 1460 1359
8 79 6 994 967 23 116 8 1843 1739
9 118 9 1926 1926 24 109 8 1633 1581
10 101 8 1320 1267 25 102 8 1335 1275
11 127 11 2731 2682 26 128 10 2691 2543
12 121 9 2541 2390 27 130 10 2978 2810

customers vehicle
Distance in the
global world
Distance from
the algorithm customers vehicles Global
solution
Algorithm
solution
13 120 9 2513 2441 28 132 9 2990 2903
14 99 7 1050 1012 29 114 8 1868 1769
15 110 8 1861 1798 30 106 8 1417 1301
First hypothesis is average cost of 28 problems solved by the company is equal to average cost of 30
problems solved by proposed algorithm. Second hypothesis is average cost of 28 problems solved by the
company is not equal to average cost of 28 problems solved by proposed algorithm.
95% CI for mean difference: (57.66; 91.47)
T test of mean difference = 0 (vs not = 0): T value = 9.02 P value = 0.000
According to the p value in Table 3, hypothesis H_{0} is rejected. Because it is less than 0.05 in 95%
confidence interval. This means that there is strong evidence that these two solutions are different.
Because of the positive of the value, company’s solutions are worse than our solutions. In conclusion,
this test shows that the solutions of our algorithm decrease the transportation cost of the company.
Conclusion
In this paper, we considered capacitated vehicle routing problem. There are various studies done and
tested on this problem. These studies highly succeeded in studying this NP-hard problem. Some features
of tabu search and ALNS providing this success are: allowing infeasible solutions, flexible parameters,
destroy/repair operators, diversification strategy, intensification strategy, and adaptive memory. To this
respect, we proposed a new heuristic algorithm based on tabu and ALNS for CVRP. We tested the
proposed algorithm and the algorithm provides compatible results on benchmark instances. For three of
benchmark instances, the proposed algorithm generated better solutions compared with best well-
known solutions in the literature. In the first 11 benchmark instances, our algorithm found optimal
solutions. However, it converged to the optimal solution with 0.01% difference approximately in the
case of not to find optimal solution. Finally, when we applied the algorithm on a real-life problem the
results satisfied us in terms of effectiveness and productiveness. Using the proposed algorithm
substituted for the current method provides advantage to the company because the results are better
than current methods and CPU time is allowable

Table 4
New solution of the three well-known instances
Problem # 28
Route # 1: 0, 7, 19, 107, 11, 64, 49, 143, 36, 47, 124, 46, 8, 114, 18, 0
Route # 2: 0, 122, 20, 128, 66, 71, 65, 136, 35, 135, 34, 78, 129, 79, 3, 77, 0
Route # 3: 0, 92, 98, 91, 141, 16, 86, 140, 38, 14, 119, 44, 100, 37, 0
Route # 4: 0, 53, 40, 21, 73, 72, 74, 23, 67, 39, 139, 4, 110, 0
Route # 5: 0, 58, 137, 144, 57, 15, 43, 142, 42, 87, 97, 95, 117, 13, 0
Route # 6: 0, 2, 115, 145, 41, 22, 133, 75, 56, 25, 55, 130, 54, 149, 26, 105, 0
Route # 7: 0, 28, 76, 116, 68, 121, 29, 24, 134, 80, 150, 109, 12, 138, 0
Route # 8: 0, 147, 60, 83, 125, 45, 17, 113, 61, 85, 93, 96, 6,0
Route # 9: 0, 111, 50, 102, 33, 81, 120, 9, 103, 51, 1, 132, 0
Route # 10: 0, 27, 127, 31, 10, 108, 126, 63, 90, 32, 131, 30, 70, 101, 69, 0
Route # 11: 0, 89, 118, 84, 5, 99, 104, 59, 94, 112, 0
Route # 12: 0, 146, 88, 148, 62, 123, 48, 82, 106, 52, 0
Problem # 29 Route # 1: 0, 154, 12, 150, 80, 68, 116, 184, 111, 0
Route # 2: 0, 82, 48, 123, 19, 107, 175, 11, 159, 62, 148, 0
Route # 3: 0, 146, 52, 153, 106, 194, 7, 182, 88, 190, 127, 167, 27, 0
Route # 4: 0, 198, 110, 4, 155, 139, 187, 39, 75, 133, 22, 41, 145, 0
Route # 5: 0, 50, 102, 157, 185, 79, 129, 169, 29, 121, 77, 196, 76, 28, 0
Route # 6: 0, 1, 51, 161, 71, 65, 136, 35, 135, 164, 34, 78, 158, 3, 0
Route # 7: 0, 138, 109, 177, 163, 24, 134, 54, 195, 26, 105, 0
Route # 8: 0, 31, 126, 63, 181, 64, 49, 143, 36, 47, 168, 124, 46, 0
Route # 9: 0, 156, 18, 114, 8, 174, 45, 125, 199, 83, 60, 166, 89, 0
Route # 10: 0, 137, 144, 172, 42, 142, 14, 140, 38, 119, 192, 100, 98, 37, 95, 94, 0

Route # 11: 0, 53, 180, 21, 72, 74, 171, 115, 178, 2, 152, 58, 0
Route # 12: 0, 147, 5, 173, 61, 16, 86, 113, 17, 84, 118, 0
Route # 13: 0, 112, 183, 96, 104, 99, 59, 151, 92, 97, 13, 0
Route # 14: 0, 149, 179, 130, 165, 55, 25, 170, 67, 23, 186, 56,197, 73, 40, 0
Route # 15: 0, 132, 69, 162, 10, 189, 108, 90, 32, 131, 160, 30,70, 101, 0
Route # 16: 0, 176, 122, 128, 20, 188, 66, 103, 9, 120, 81, 33, 0
Route # 17: 0, 6, 93, 85, 193, 91, 191, 141, 44, 43, 15, 57, 87,117, 0
Problem # 30 Route # 1: 0, 144, 218, 119, 94, 151, 86, 149, 247, 88, 50, 77,93, 200, 0
Route # 2: 0, 14, 117, 98, 240, 107, 212, 45, 91, 46, 0
Route # 3: 0, 158, 60, 110, 41, 210, 20, 109, 227, 29, 75, 237,0
Route # 4: 0, 115, 244, 99, 70, 108, 155, 76, 154, 87, 188, 256, 4, 164, 0
Route # 5: 0, 252, 234, 68, 142, 232, 231, 202, 139, 1, 229, 71, 31, 205, 211, 5, 204, 0
Route # 6: 0, 118, 44, 22, 120, 128, 143, 174, 196, 48, 23, 236, 111, 0
Route # 7: 0, 140, 160, 28, 182, 95, 34, 81, 186, 172, 0
Route # 8: 0, 165, 222, 85, 257, 253, 92, 178, 105, 97, 132, 52, 84, 0
Route # 9: 0, 74, 7, 156, 259, 35, 239, 184, 192, 152, 208, 246, 0
Route # 10: 0, 233, 67, 51, 134, 159, 147, 245, 40, 127, 24, 258, 122, 0
Route # 11: 0, 243, 169, 171, 181, 59, 162, 219, 0
Route # 12: 0, 102, 15, 136, 78, 201, 32, 226, 176, 56, 242, 0
Route # 13: 0, 254, 66, 175, 17, 55, 47, 168, 103, 113, 194, 80,42, 197, 0
Route # 14: 0, 255, 228, 53, 124, 49, 130, 129, 221, 90, 61, 12,133, 79, 261, 0
Route # 15: 0, 148, 26, 9, 153, 189, 106, 121, 248, 89, 167, 13,251, 0
Route # 16: 0, 213, 21, 100, 145, 209, 138, 33, 72, 166, 96, 0
Route # 17: 0, 135, 16, 6, 37, 25, 141, 104, 215, 0

Route # 18: 0, 43, 223, 38, 39, 146, 3, 123, 190, 0
Route # 19: 0, 8, 126, 250, 180, 63, 216, 161, 187, 179, 199, 116, 0
Route # 20: 0, 2, 170, 230, 58, 150, 183, 114, 0
Route # 21: 0, 235, 225, 241, 11, 10, 238, 131, 214, 57, 203, 0
Route # 22: 0, 27, 260, 173, 137, 18, 30, 191, 19, 185, 207, 0
Route # 23: 0, 195, 36, 220, 65, 206, 83, 217, 0
Route # 24: 0, 112, 73, 198, 54, 0
Route # 25: 0, 125, 101, 193, 82, 157, 62, 249, 177, 69, 0
Route # 26: 0, 163, 224, 64, 0
References
1. Ai TJ, Kachitvichyanukul V (2009) Particle swarm optimization and two solution representations
for solving the capacitated vehicle routing problem. Comput Ind Eng 56:380–387. doi:10.
2. Akpinar S (2016) Hybrid large neighbourhood search algorithm for capacitated vehicle routing
problem. Expert Syst Appl 61:28–38. doi:10.1016
3. Cui L, Wang L, Deng J, Zhang J (2013) A new improved quantum evolution algorithm with local
search procedure for capacitated vehicle routing problem. Math Probl Eng. doi:10.1155
4. Fukasawa R, Longo H, Lysgaard J, Aragao MP, Reis M, Uchoa E, Werneck RF (2006) Robust
branch-and-cut-and-price for the capacitated vehicle routing problem. Math Program Ser A
106:491–511.
5. Jin J, Crainic TG, Lokketangen A (2014) A cooperative parallel metaheuristic for capacitated
vehicle routing problem. Comput Oper Res 44:33–41.
6. Kao Y, Chen M (2013) Solving the CVRP Problem Using a Hybrid PSO Approach, ISBN: 978-3-642-
356
Cite this article as:
Kır, S., Yazgan, H.R. & Tüncel, E. J Ind Eng Int (2017) 13: 323. https://doi.org/10.1007/s40092-017-0187-9
 DOI https://doi.org/10.1007/s40092-017-0187-9
 Publisher Name Springer Berlin Heidelberg

 Print ISSN 1735-5702
 Online ISSN 2251-712X
IMPLEMENTING THE CODE
Instance:VRP class
Number of vehicles n = 4
at node I travelling to j
objective value :120.20
routes 0 2 5 0
0 6 9 0
0 8 0
n n n
   Ci,jXi,j,k
i=o j=0 k=1
clustering several customer points and finding the optimal path for each cluster