Improvement of Hybrid Heuristic Algorithm for Solving Capacitated Vehicle Routing Problem

London Journal of Research in Computer Science and Technology
Volume | Issue | Compilation
Authored by Mohammed Yaqub , NA
Classification: B.7.2, C.2.2
Keywords: golden section, sweep algorithm, vehicle routing problem, nearest neighbour algorithm, particle swarm optimization.
Language: English

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 Cluster-First Route-Second method. There are two proposed hybrid algorithms used to implement that methodology, the Sweep-Nearest Neighbour algorithm and the Sweep-Particle 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.

               

Improvement of Hybrid Heuristic Algorithm for Solving Capacitated Vehicle Routing Problem

Mohammed Yaqub

____________________________________________

  1. 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 Cluster-First Route-Second method. There are two proposed hybrid algorithms used to implement that methodology, the Sweep-Nearest Neighbour algorithm and the Sweep-Particle 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.

  1. 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:

  1. Each route start and end at the depot.
  2. Each vertex (customer) is visited by exactly one route.
  3. 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.

  1. RELATED WORK

There are tremendous efforts to improve heuristic and exact methods to solve VRP such in  [3], also meta-heuristic 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 well-structured 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 3-opt 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.

  1. 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 Cluster-First Route-Second 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 two-dimensional 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 anti-clockwise.

  • A general formula for calculating the polar coordinate:

ϕ = tan-1 (y / x)            (1)

Where

ϕ : angular value of a node (i.e., depot or customer).

x, y : coordinate values in degree.

  1. 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 self-adaptive 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, level-1 represents customers with high demand, level-2 represents customers with medium demand and level-3 represents customers with low demand, we will focus on Level-1 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:

  1. Each customer is visited exactly once.
  2. Each vehicle route starts and ends at the depot.
  3. Each customer is serviced by one and only one vehicle.
  4. Customers have grouped into clusters and the total customer’s demands of each cluster not exceeding the vehicle capacity.
  5. Demand at each customer is known.
  6. 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 Sweep-Nearest Neighbour Algorithm              (SW & NNA)  and hybrid Sweep-Particle Swarm Optimization (SW & PSO) was coded in C# on an Intel Core i3-2350M CPU 230 GHz with 3.00 GB 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

  1. CONCLUSION

In this paper, Cluster-First Route-Second 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 Sweep-Nearest Neighbour Algorithm (SW & NNA) and the hybrid Sweep-Particle 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

  1. B. Gillett, and L. Miller, “A Heuristic for the Vehicle Dispatching Problem”, Operations Research, 22, 340-349, 1974.
  2. C-H Wang  ,and J-Z Lu ,” An effective evolutionary algorithm for the practical capacitated vehicle routing problems”, Springer, Journal of Intelligent Manufacturing, Volume 21, Issue 4, pp 363-375, 2010.
  3. 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.
  4. 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), 2010-40th International Conference, 2010.
  5. 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.
  6. J. Ai, and V. Kachitvichyanukul, “Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem”, Computers & Industrial Engineering, 56 (1), 380-387, 2009.b .
  7. 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, 26-28, pp. 266-269, 2009.
  8. 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: 2089-3191, 2013.
  9. P. Toth, and D.Vigo, “The Vehicle Routing Problem“, SIAM Monographs on Discrete Mathematics and Applications, 2001 .
  10. 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: 39-43, 1995.
  11. 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. 989-1003, Sep 1997, doi: 10.1109/34. 615448, 1997.
  12. 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. 846-852. ISSN 1549-3636, 2013.
  13. Z. Ying, Z. Guangjie , and YU. Feihong, “particle swarm optimization-based approach for optical finite impulse response filter design”, applied optics issn 0003-6935 coden apopai, vol. 42, no8, pp. 1503- 1507, 2003.



author

For Authors

Author Membership provide access to scientific innovation, next generation tools, access to conferences/seminars
/symposiums/webinars, networking opportunities, and privileged benefits.
Authors may submit research manuscript or paper without being an existing member of LJP. Once a non-member author submits a research paper he/she becomes a part of "Provisional Author Membership".

Know more

institutes

For Institutions

Society flourish when two institutions come together." Organizations, research institutes, and universities can join LJP Subscription membership or privileged "Fellow Membership" membership facilitating researchers to publish their work with us, become peer reviewers and join us on Advisory Board.

Know more

subsribe

For Subscribers

Subscribe to distinguished STM (scientific, technical, and medical) publisher. Subscription membership is available for individuals universities and institutions (print & online). Subscribers can access journals from our libraries, published in different formats like Printed Hardcopy, Interactive PDFs, EPUBs, eBooks, indexable documents and the author managed dynamic live web page articles, LaTeX, PDFs etc.

Know more