Improvement of Hybrid Heuristic Algorithm for Solving Capacitated Vehicle Routing Problem
Mohammed Yaqub
____________________________________________
ABSTRACT
Capacitated Vehicle Routing Problem is the most elementary version of the vehicle routing problem, where it represents a generalization of vehicle routing problems. It is an important problem in the fields of distribution, transportation and logistics which involves finding a set of routes, starting and ends in a warehouse for, that together cover a range of clients. The proposed methodology in this research was based on ClusterFirst RouteSecond method. There are two proposed hybrid algorithms used to implement that methodology, the SweepNearest Neighbour algorithm and the SweepParticle Swarm Optimization algorithm. The Particle Swarm Optimization algorithm was used instead of Nearest Neighbour algorithm to enhance the performance in finding the shortest routes. The two hybrid proposed algorithms were applied in a real case study and the results were compared. From the experimental results, it observed that particle swarm optimization was added more enhancement for finding the best route with the minimum travelling costs.
Keywords: golden section, sweep algorithm, vehicle routing problem, nearest neighbour algorithm, particle swarm optimization.
INTRODUCTION
The Vehicle Routing Problem (VRP) is a very interesting combinatorial optimization problem to study for computer scientists, where it represents a generalized form of the Travelling Salesman Problem (TSP). VRP is the problem of serving a number of customers with a fleet of vehicles, minimizing the travelling cost under several variants. It has applications in the fields of transportation, distribution and logistics. Large package shipping companies benefit greatly from implementing the VRP as efficiently as possible: every percentage saved on transportation costs means saving tremendous amounts of money.
The Capacitated Vehicle Routing Problem (CVRP) is the most common and basic variant of the vehicle routing problem. In this variant, a fixed fleet of a delivery vehicles finding a set of routes with a minimum travelling cost to service the customer demands in different locations [9], where the route is considered feasible if the total demands of all customers on a route does not exceed the vehicle capacity.
The CVRP can be defined on a graph as : G = ( V , E), where 𝑉 = {𝑣0 , 𝑣1 , 𝑣2 , … , 𝑣𝑁 } are vertices or node set. 𝑣0 represents the depot and the other nodes are N customers that have a certain demand d. The edge set can be represented as E = { ( i , j ): i , j ∈ V } . The cost cij > 0 is the travelling cost between node i and j, and each vehicle have a capacity Q. The objective is to find a set of routes with the minimum cost (distance) that satisfy the following constraints:
 Each route start and end at the depot.
 Each vertex (customer) is visited by exactly one route.
 The sum of the vertices’ demands visited by the route does not exceed the vehicle capacity Q.
The proposed methodology for solving CVRP was based on a heuristic method (Cluster First – Route Second) that composed of two phases: Clustering phase that used to group customers into clusters and Route generation phase that used to find the best route for each cluster.
The hybrid algorithm that used for solving CVRP was combined Sweep Algorithm (SW) and Nearest Neighbour algorithm (NNA). The SW was used as a clustering technique and then using NNA to find the best route for each cluster. However, using the Nearest Neighbour algorithm in route generation phase was not sufficient enough, probably NNA is easy to implement and executes quickly, but it is sometimes missing shorter routes which are easily noticed with human insight. Therefore, we proposed to use the particle swarm optimization (PSO) as a route generation technique instead of nearest neighbour algorithm to enhance the performance in finding the shortest route for each cluster.
This paper is organized as follows: section 2 presents Related Work for solving CVRP. Section 3 presents Materials and Methods that used in solving CVRP, section 4 presents Results and Discussion, section 5 presents Conclusion, and the paper end with Acknowledgements and References.
RELATED WORK
There are tremendous efforts to improve heuristic and exact methods to solve VRP such in [3], also metaheuristic and hybrid heuristic methods developed to find the near optimal solution for VRP. A new method that provides a promising result based on particle swarm optimization (PSO) algorithm used to solve CVRP has presented by [6]. In [7], PSO combined with the crossover operation of genetic algorithm (GA), where it applied to single depot CVRP and it can avoid being trapped in a local optimum due to using probability searching. Another solution approach based on PSO presented by [4], in which a local search is performed by a variable neighbourhood descent algorithm (VND), the computational results of that solution indicated that the proposed algorithm produces a better result that competes with other heuristic approaches.
According to [2], a novel hybrid genetic algorithm (HGA) proposed to solve CVRP, the proposed HGA involves three stages. First, a diverse and wellstructured initial chromosome population was constructed. Second, response surface methodology (RSM) experiments were conducted to optimize the crossover and mutation probabilities in performing GA. Finally, a combined heuristic containing improved insertion algorithm and random insertion mutation operator were established to stir over gene permutations and enhance the exploration capability of GA diversely. In [12], Ant Colony Optimization (ACO) with swap and 3opt heuristic has the capability to tackle the CVRP with satisfactory solution quality and run time, where it represent a viable alternative for solving the CVRP. In that proposed approach, ACO combined with heuristic approaches that act as the route improvement strategies. The proposed ACO utilized a pheromone evaporation procedure of standard ant algorithm in order to introduce an evaporation rate that depends on the solutions found by the artificial ants.
Another proposed method introduced by [5], that combined particle swarm optimization algorithm and Genetic algorithm with crossover and mutation operators for solving capacitated vehicle routing problem with time windows (CVRPTW) efficiently. In [8], a developed PSO algorithm presented for solving CVRP by combined a different heuristic such as Two Optimal Exchange (TOE), Two Optimal Insertion (TOI) and TSP Optimal Exchange (TSPOE), that used to improve the solutions, which lead to enhanced solutions and obtain good results in both small and medium problem instances.
Materials and Methods
4.1 Methodology
The overall goal of this paper was to use the PSO algorithm instead of NNA to enhance the performance in finding the shortest routes, the proposed methodology used to solve CVRP based on ClusterFirst RouteSecond method composed of two main phases, the first phase is to group customers into clusters and the second phase is to find out the optimal solution (best route path) for each cluster. There are two hybrid algorithms used to implement that methodology, first hybrid algorithm is Sweep  Nearest Neighbour Algorithm (SW & NNA), the second hybrid algorithm is Sweep  Particle Swarm Optimization algorithm (SW & PSO), where the Sweep algorithm in both hybrids proposed algorithms was used for clustering phase, and the other algorithm is used for finding the best path for each cluster.
4.2 Sweep Algorithm
Sweep algorithm is one of the simplest heuristic algorithms that have been developed to route vehicles. It firstly proposed by Gillet and Miller in 1974 to find the shortest route in the vehicle routing problem [1]. Sweep algorithm consists of two main stages, the first stage is clustering nodes (customers) into groups, so all nodes in the same group are geographically close together and can be served by the same vehicle, nodes clustered based on their capacity where capacity represents the maximum number of goods that can be carried by vehicle in serving a route. Second stage is the route generation or finding path in each cluster based on different constraints such shortest distance and capacity constraint that repeated to obtain the optimal solution, in our methodology we used sweep algorithm for clustering stage to get the best customers’ clusters.
All nodes in sweep algorithm are represented by twodimensional plane, where the depot is located at the centred of that plane with (0,0) coordinates and 0 demands, then computing the polar coordinates of each node with respect to the depot. The sweep algorithm starts to sweep all nodes by increasing the polar angle, making a list of all nodes’ angles where it assigns each node encompassed by the sweep to the current cluster and sweeping is stopped when adding the next node (customer demand) would violate the maximum vehicle capacity. Create a new cluster by resuming the sweep where the last one left off, and repeat assigning steps to each cluster until all nodes have been included in a cluster.
Figure 1: Clustering process for customer nodes
Figure 1 illustrates nodes clustering process where the black dots represent the nodes and the straight lines represent the sweep hand when it moves anticlockwise.
 A general formula for calculating the polar coordinate:
ϕ = tan1 (y / x) (1)
Where
ϕ : angular value of a node (i.e., depot or customer).
x, y : coordinate values in degree.
 A general formula for calculating the Euclidean distance:
dij = (2)
Where
dij : distance between two nodes.
Xi : X coordinate value for node i.
Xj : X coordinate value for node j.
Yi : Y coordinate value for node i.
Yj : Y coordinate value for node j.
Clustering nodes into groups is established by joining nodes, beginning of the closest node that has the smallest angle. This process is repeated by joining the second closest, the third, and so forth until it satisfies the capacity constraint where the total demands for all nodes in each cluster not exceeding the vehicle capacity. The process is completed when all nodes are included in clusters.
4.3 Nearest Neighbor Algorithm
The route generation phase is aimed to optimize searching method to find the optimal solution that represents the shortest path between all nodes in each cluster. The Nearest Neighbour Algorithm (NNA) is used as a heuristic method to find the shortest path between each cluster nodes as a travelling salesman problem [11]. After nodes being clustered, the NNA is performed to reorder nodes on each cluster based on the distance of one node to another to generate the shortest routes. The distance matrix between all nodes in each cluster are created by using equation 2 for calculating the Euclidean distance. The first node to be linked in each cluster is the one that has the shortest distance to the depot, the next node to be linked is selected by searching a node that is closest to the first node. This procedure is repeated until all nodes in the same cluster are linked as a route. The same procedure is performed for all clusters until all routes are generated.
4.4 Particle Swarm Optimization
Particle swarm optimization was originally introduced by Eberhart and Kennedy in 1995 as an evolutionary computation technique which designed as a selfadaptive search optimization algorithm based on the simulation of the animal social behaviours such as fish schooling and bird flocking, that swarms work in a collaborative manner to search for foods as efficient and quick as possible [10].
In PSO, a solution of a specific problem is being represented (directly or indirectly) by the n dimensional position of a particle. The search is performed by moving the particle to a new position via a velocity vector. The PSO algorithm starts with a population of particles initialized with random position and velocity. The population of particles is usually called a swarm. In one iteration step, every particle is moved from previous position to the new position based on its velocity. The velocity of a particle is updated based on the particle’s personal best position (pBest) and the global best position found so far by the swarm (gBest). This allows the particles to exchange their experience to ensure the diversity of the search and lead to improvement of solutions.
PSO also has a fitness function that takes the particle’s position and assigns to it a fitness value. The position with the minimum fitness value in the entire run is called as social or global best. Each particle keeps track of its minimum fitness value, called its cognitive or local best. The velocity of the particle, each of dimensions, is accelerated towards the global best and its own local best. The inertia weight has a well balanced mechanism with the flexibility to enhance and adapt to both global and local exploration abilities. The formula for updating the velocity of each particle in the swarm are as follows.
Vid (t+1)= W Vid (t) + c1r1(Pid –Xid) + c2r2(Pgd  Xid) (3)
Where
Vid : velocity of dimension d of the i th particle.
Pid : personal best previous position of the i th Particle.
Pgd : the global best position for all particles.
Xid : current position of the i th particle.
c1 & c2 : are acceleration constants.
r1, r2 : random function in the range [0, 1].
W : Inertia weight.
The new velocity calculated in that iteration is used for updating the current position of each particle by using the following formula:
Xid (t+1)= Xid (t) + Vid (t+1) (4)
Where
Xid (t) : current position of the i th particle.
Xid (t+1) : new position of the i th particle.
Vid (t+1) : New velocity of the i th particle.
The process of updating the velocity and the position of each particle in the swarm is repeated until it reached a specific number of iterations as a termination criteria or reaching to the same final solution.
4.5 Case Study
Tiba Company for Trade and Distribution is one of Juhayna Group companies that owns 24 distribution centers spread across the majority of the provinces of Egypt, where the distribution network covering 27 provinces, nearly 36,000 retail outlets, through more than 800 car and truck distribution.
Our case study applied in the Tiba Company for Trade and Distribution  Mansoura branch which deliver dairy products from their distribution center to about 850 retail outlets in Mansoura city. The company splits their customers into 3 levels, level1 represents customers with high demand, level2 represents customers with medium demand and level3 represents customers with low demand, we will focus on Level1 where it services about 20 high demand supermarkets where the company owns a fleet of 4 refrigerated trucks used to serve that level of customers. The objective is to minimize cost by minimizing the total distance travelled and under the following constraints:
 Each customer is visited exactly once.
 Each vehicle route starts and ends at the depot.
 Each customer is serviced by one and only one vehicle.
 Customers have grouped into clusters and the total customer’s demands of each cluster not exceeding the vehicle capacity.
 Demand at each customer is known.
 The cost is measured by the total distance of all routes.
Figure 2 shows the case study customers that located on the Mansoura city map.
Figure 2: Customers locations on map
Table 1 shows node name, Cartesian coordinates for each node and demand, which are the required data to apply the clustering process in sweep algorithm.
Table 1: Node name, X, Y coordinates value of each customer and their demands
Node  X Coordinate  Y Coordinate  Demand  Node  X Coordinate  Y Coordinate  Demand 
Depot  0  0    11  4  16  450 
1  3  17.5  462  12  7  17.5  480 
2  6  19  510  13  15  19  462 
3  14  16.5  606  14  33  27.5  510 
4  18  20.5  720  15  34.5  11  624 
5  22.5  21  624  16  40.5  33  414 
6  27.5  34  450  17  50  15.5  510 
7  9  43  420  18  76  23  582 
8  24  17  750  19  5  14  612 
9  52  7  810  20  10  21.5  762 
10  76  9  846 




Input parameters that represent the constraints required to clustering process are presented in table 2.
Table 2: Input parameters
No. of Vehicles  4 
Maximum Vehicle capacity  3500 (units) 
Total Demand  11604 (units) 
V. Results and Discussion
The two proposed approaches that's based on hybrid SweepNearest Neighbour Algorithm (SW & NNA) and hybrid SweepParticle Swarm Optimization (SW & PSO) was coded in C# on an Intel Core i32350M CPU 230 GHz with 3.00GB of RAM under Windows 8 platform. After clustering process is performed by using the sweep algorithm, the optimal routes achieved by using a nearest neighbour algorithm in the first hybrid algorithm and in the second hybrid algorithm, the optimal routes achieved by using particle swarm optimization. The resulted clusters and their total travelling distances were compared in table 3.
Table 3: Resulted clusters and the total travelling distances
No.  Sweep & Particle Swarm Optimization (SW&PSO)  Sweep & Nearest Neighbour Algorithm (SW&NNA) 
 Vehicle Route  Total distances travelled  Vehicle Route  Total distances travelled 
1  0 , 14 , 13 , 12 , 11 , 20 , 19 , 0  113.28  0 , 19 , 20 , 11 , 12 , 13 , 14 , 0  113.28 
2  0 , 15 , 17 , 10 , 18 , 16 , 0  209.2  0 , 15 , 17 , 16 , 18 , 10 , 0  217.68 
3  0 , 9 , 8 , 7 , 6 , 2 , 1 , 0  192.11  0 , 1 , 2 , 7 , 6 , 8 , 9 , 0  202.3 
4  0 , 5 , 4 , 3 , 0  62.6  0 , 3 , 4 , 5 , 0  62.6 
Total  577.19  Total  595.86 
In PSO, the inertia weight is taken as 0.47 and the acceleration constants are set as c1 = c2 = 2 as proposed in [13].
The optimum routes that resulted from using (SW & PSO) are as bellows:
Vehicle 1# : 0  14  13  12  11  20  19  0.
Vehicle 2# : 0  15  17  10  18  16  0.
Vehicle 3# : 0  9  8  7  6  2  1  0.
Vehicle 4# : 0  5  4  3  0.
Total travelling distances: 577.19.
Figure 3 shows the optimal routes by using (SW & PSO) in the graph:
Figure 3: Resulted optimal routes by using (SW & PSO) algorithm
The optimum routes that resulted from using (SW & NNA) are as bellows:
Vehicle 1# : 0  19  20  11  12  13  14  0.
Vehicle 2# : 0  15  17  16  18  10  0.
Vehicle 3# : 0  1  2  7  6  8  9  0.
Vehicle 4# : 0  3  4  5  0.
Total travelling distances: 595.86.
Figure 4 shows the optimal routes by using (SW & NNA) in the graph:
Figure 4: Resulted optimal routes by using (SW & NNA) algorithm
CONCLUSION
In this paper, ClusterFirst RouteSecond method proposed as a methodology to reduce the total cost of capacitated vehicle routing problem (CVRP), where it’s based on grouping customers into clusters and then finding out the shortest path for each cluster. The CVRP was solved by using two hybrid algorithms, the hybrid SweepNearest Neighbour Algorithm (SW & NNA) and the hybrid SweepParticle Swarm Algorithm (SW & PSO). This work proposed to group the customers and to find out the optimal path of each group/cluster thereby minimizing the transportation costs. The disadvantage of the nearest neighbour algorithm that it sometimes missing shorter routes which are easily noticed with human insight. Therefore, it replaced by PSO to improve the route generation phase. By consolidating the travelling cost as directionally proportional to total distance travelled by the vehicle. The two hybrid algorithms were compared and from the experimental results, it observed that the total costs (travelling distance) were reduced by using the hybrid SW& PSO. Therefore, the PSO added more enhancement in finding out the best route for each cluster compared to the nearest neighbour algorithm.
REFERENCES
 B. Gillett, and L. Miller, “A Heuristic for the Vehicle Dispatching Problem”, Operations Research, 22, 340349, 1974.
 CH Wang ,and JZ Lu ,” An effective evolutionary algorithm for the practical capacitated vehicle routing problems”, Springer, Journal of Intelligent Manufacturing, Volume 21, Issue 4, pp 363375, 2010.
 F. Tricoire, K. Doerner, R. Hartl, and M. Iori, “Heuristic and exact algorithms for the multiple vehicle routing problem”, OR Spectrum, 33(4): 931 – 959, 2011.
 F. P. Goksal, F. Altiparmak , and I. Karaoglan, “A hybrid particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery”, Computers and Industrial Engineering (CIE), 201040th International Conference, 2010.
 G. Qureshi , P. R. Bajaj , and P. V. Puranik , “Particle Swarm Optimization with Genetic Operators for Vehicle Routing Problem”, International Journal of Engineering Science and Technology (IJEST), Vol. 4 No.07, 2013.
 J. Ai, and V. Kachitvichyanukul, “Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem”, Computers & Industrial Engineering, 56 (1), 380387, 2009.b .
 L. Yin , and X. Liu, “ A Single–depot Complex Vehicle Routing Problem and its PSO Solution”, Proceedings of the Second Symposium International Computer Science and Computational Technology (ISCSCT ’09), Huangshan, P. R. China, 2628, pp. 266269, 2009.
 M. M. Tavakoli, , and A. Sami, “Particle Swarm Optimization in Solving Capacitated Vehicle Routing Problem”, Bulletin of Electrical Engineering and Informatics, Vol. 2, No. 4, December 2013, pp. 252~257. ISSN: 20893191, 2013.
 P. Toth, and D.Vigo, “The Vehicle Routing Problem“, SIAM Monographs on Discrete Mathematics and Applications, 2001 .
 R. Eberhart, J. Kennedy, ”A New Optimizer Using Particle Swarm Theory”, Proc of 6th International Symposium on Micro Machine and Human Science, Nagoya, Japan. IEEE Service Center Piscataway NJ, 1995: 3943, 1995.
 S. A. Nene, and S. K. Nayar, "A simple algorithm for nearest neighbor search in high dimensions", Pattern Analysis and Machine Intelligence, IEEE Transactions, vol. 19, no. 9, pp. 9891003, Sep 1997, doi: 10.1109/34. 615448, 1997.
 W. F. Tan, L. S. Lee, Z. Abdul Majid, and H. V. Seow, “Ant colony optimization for capacitated vehicle routing problem”, Journal of Computer Science, 8 (6). pp. 846852. ISSN 15493636, 2013.
 Z. Ying, Z. Guangjie , and YU. Feihong, “particle swarm optimizationbased approach for optical finite impulse response filter design”, applied optics issn 00036935 coden apopai, vol. 42, no8, pp. 1503 1507, 2003.