Solving Vehicle Routing Problem using Ant Colony Optimization with Nodal Demand

Solving Vehicle Routing Problem using Ant Colony Optimization with Nodal Demand

Tejal Carwalo

Computer Engineering

St. Francis Institute of Technology Mumbai, Maharashtra

Vandana Patil

Information Technology

St. Francis Institute of Technology Mumbai, Maharashtra

AbstractRouting is the process of selecting best path and it can be performed on any type of the network. In a vehicle routing problem (VRP), different vehicles travel around a network, which start from and end to a depot node. Capacitated VRP deals with the maximum volume that individual vehicle can handle. Ant colony optimization algorithm is an effective approach to solve capacitated vehicle routing problem, Introducing clockwise partition clustering an improve the efficiency of finding the optimal path while considering the nodal demand of each vehicle.

KeywordsAnt Colony Optimization; Capacitated Vehicle Routing Problem; Partition Clustering; Vehicle Routing Problem;

1. INTRODUCTION

   Vehicle routing problem (VRP) has now become one of the key priority problem in the area of transportation. It deals with pickup or delivery activity management, which is an extension of a classic traveling salesman problem (TSP). In a VRP, different vehicles travel around a network and all vehicles start and end its tour to the depot point the main constraint of VRP is each customer should be visited by just one vehicle. Capacitated VRP have additional restriction on the capacity of each vehicle which means, each vehicle have certain capacity which should not be exceed. The aim of this study is to find the tour of the vehicle to minimize the total cost while considering the nodal demand of the each vehicle. For large area network performance can be improved by use of clustering algorithm. Clustering algorithm is used to divide the whole region into various sub-regions and then each sub- region can be solved as a separate routing problem. In a study we used partition clustering to form the clusters and while forming the clusters we considered capacity of vehicles. Beginning with the Clarke and Wright algorithm various heuristics algorithms have been used to solve VRP and to find shortest path[1] . but the problem of heuristics algorithm is it limit its use for large scale problem and to search global solution different metaheuristics algorithm have been developed. Metaheuristics algorithms such as ant colony optimization (ACO), firefly algorithm (FA), particle swarm optimization (PSO), and cuckoo search algorithm (CS) are used to solve capacitated VRP[2][3]. The most successful approach for VRP is aco[4].

   The ACO algorithm is a meta-heuristic algorithm that has been widely used for different optimization problems and has been inspired by real ant observations, i.e., the way in which ant find shortest path from its nest to the source of food. The

   first ant travel over the area until it find the source of food by laying pheromone trail on the ground which act as a signal to other ants. The main three steps of the ACO algorithm are pheromone initialization, tour construction and pheromone update. In the first step initial pheromone level is initialized on each edge and then ants simultaneously build the route from the starting node after that local pheromone update is performed by every ant that finds the route and global update is performed by only ant that produce best tour so far[8].

2. LITERATURE SURVEY

   Capacitated vehicle routing problem deals with maximum weight or volume that each vehicle can load. Silvia and Irebe[5] used ACO for capacitated vehicle routing, to define routes for vehicles starting and ending at the depot node that satisfy the clients demand at minimum total cost. For routes building, at each iteration of ACO each ant builds a solution for CVRP, tabu list is maintained to keep track of already visited nodes. Each ant start its solution determining the route for the first vehicle till capacity constraint is satisfied then it continues with others vehicles till the solution is complete.The algorithm obtained the optimal value for the problems where the number of nodes are less than 50 and the performance of ACO is very good compared to other evolutionary algorithms.

   Location Routing Problem(LRP) integrates both location and routing decision to minimize total route cost. Ting and chen[6] have used Multiple Ant Colony Optimization(MACO) to solve LRP with capacity constraints. MACO algorithm designed to optimize different sub problems like location selection, customer assignment and VRP. In location selection phase ant creates random locations. Customer assignment creates new assignment based on selected locations. After customer assignment phase, problem solved using ACO. MACO checks the capacity constraint after customer assignment phase therefore it required more computational time. Checking the capacity constraint during the customer assignment phase can reduce the computational time.

   Reed et al. [6] have solved capacitated VRP using ACO. Researcher has considered the scenario of waste collection from the house. The large area network, where the nodes are far away from each other, used of clustering algorithm can improve the performance of the algorithm therefore

   researchers have first used the k-means clustering algorithm to divide the entire area into sub regions and then applied the ACO algorithm to each sub region to decide the shortest path with minimum cost. The performance for a large problem is improved by a large number of iterations, but the major drawback of the k-means clustering algorithm is while forming the clusters algorithm does not check the capacity constraint therefore the number of nodes in each clusters are different which violated nodal demand condition of each vehicle so to adjust load of each cluster load balancing is required. And after balancing algorithm recalculate the cluster mean value and it iterates as in the k-means algorithm. However, more sophisticated clustering algorithms need to be developed, which will help to overcome the drawbacks of the k-means clustering algorithm and consider the nodal demand.

   The ACO algorithm process:

   1. Initialized algorithm parameter: k ants, number of cycles I, q0, , ,0 , also initialized iteration I and ant k to 1. The N*N is pheromone matrix with each ij corresponds to the level of pheromone trace present on edge (i, j). The initial value of ij 0. also ij = 1/dij corresponds to the

      desirability level of moving from node i to node j and dij is the distance from node i to j.

   2. Locate ant at starting point

   3. Take new variable q, and value for q is taken from a uniform distribution between 0 and 1 if q q0, then select the next stop using eq.(1) otherwise select the next move using eq.(2)

3. PROPOSED WORK

   Due to the shortcomings mentioned in the literature survey, the more efficient clustering algorithm is needed for the large area network for appropriate outcomes. Hence, we proposed the partition clustering algorithm, which considers

   p (i, j) arg_ max ( k u j (i) ij

   k

   ).(

   ij

   ) ,

   (1)

   ij ij

   ( ).( )

   the nodal demand of each vehicle while forming the clusters.

   if s jk(i)

   (2)

   pk(i, j)

   After defining the number of customers (nodes) process will be start by region partitioning i.e. dividing the whole region into small sub-region using proposed partition clustering. Once the clusters are formed ACO will be applied

   k

   zj

   0

   (i)

   (iz

   ).(iz) ,

   Define the number of customers

   on each cluster to find the shortest path this is evident through fig.1.

   1. If all the stops are not visited by the ant then select the

      next stop using step 3 otherwise returns to the start point and calculate total traveled distance. Once the traveled distance is calculated ant locally update the pheromone level using eq. (3)

      Perform region partitioning

      ij (1 ) * ij * 0,

      (3)

      Apply ACO algorithm on individual cluster

      Fig. 1. Flowchart of the proposed work

   2. Once all the ants complete the tour of a particular iteration, then determine best route of the cycle and then update pheromone level globally using eq. (4).

      1. Region Partitioning

         ij (1 ) * ij (lmc)1

         (4)

         In region partitioning phase (partition clustering) whole are will be divided into small sub-region. While dividing the area capacity of the vehicles will be considered. The process will be start by taking one reference line and then increment the angle till the nodes in the clusters are equal to the capacity of the vehicle, Rotational matrix is useful to increment the angle with certain degree.

      2. ACO Algorithm

      After forming the clusters ACO algorithm will be applied to each clusters to find shortest tour The ACO algorithm emulates the behavior of real ants and the characteristics of their pheromone trails to determine the best route (i.e., the shortest path).

   3. Once the iterations are equal to the initialized iteration in step1 then algorithm will stop and return the best or optimal path.

   The process of ACO algorithm[7] can be seen in fig.2

4. RESULTS AND DISCUSSION

   To implement the proposed algorithm, we used MATLAB- based computer programs. First, we tested the ACO algorithm on a freely available TSP programs from the TSPLIB. Then, we created a dataset in a text file. The dataset consists of coordinates of nodes and depot coordinates.

   Description of problems: Problem 1, 2, and 3 contain 52, 54, and 75 nodes, respectively, and we assumed nodal demand

   Fig. 2. Flowchart of the ACO algorithm[7]

   for problems as 7, 8, and 9, respectively. The solution of problem 1, 2, and 3 is shown in Figs. 3, 4, and 5, respectively. The detailed description of the problems including the shortest path calculation of each cluster is shown in Table I.

   Fig. 3. Solution for problem 1

   Fig. 4. Solution for problem 2

   Nodal demand = 7 Total nodes = 53		Nodal demand = 8 Total nodes = 54		Nodal demand = 9 Total nodes = 75
   Cluster number	Shortest path (km)	Cluster number	Shortest path (km)	Cluster number	Shortest path (km)
   1	162	1	193	1	196
   2	136	2	138	2	123
   3	136	3	130	3	111
   4	131	4	134	4	131
   5	118	5	152	5	134
   6	143	6	152	6	111
   7	149	7	134	7	149
   8	103	–	–	8	158
   –	–	–	–	9	103

   Fig. 5. Solution for problem 3 TABLE I. DETAILED INFORMATION

5. CONCLUSION

The ACO algorithm is used to find the optimal path, and the use of region partitioning (partition clustering algorithm) can improve the performance for a large-scale problem. The proposed clustering algorithm will be useful to divide the entire area into small regions while considering capacity constraint(nodal demand), and the ACO algorithm will be applied on individual clusters to determine the shortest path from source to destination by visiting each customer exactly once. Proposed method accurately identifies the impact of nodal demand of each vehicle compared to other research work mentioned in the literature. It will also be helpful for the courier agencies to determine the shortest path so that traveled distance can be minimized and more customers can be visited by a courier person in less time.

REFERENCES

1. Anders Segerstedt, A simple heuristic for vehicle routing A variant of Clarke and Wright's saving method,elsevier, Int. J. Production Economics, Volume 157, pp.7479, November 2014

2. Bharat Bhushan and Sarath S. Pillai, Particle Swarm Optimization and Firefly Algorithm: Performance Analysis, IEEE,3rd International conference on advance pp. 746 751, 2013.

3. GilangKusumaJati, HisarMaruliManurung, Suyanto, Discrete Cuckoo Search for Traveling Salesman Problem, IEEE, 7th International conference on computing and convergence technology, pp. 993-997, 2012.

4. Martin Reed, AlikiYiannakou, Roxanne Evering, An ant colony algorithm for the multi-compartment vehicle routing problem, Elsevier, AppliedSoft Computing, Volume 15, pp. 169-176, February 2014,

5. Silvia Mazzeo, Irene Loiseau, An Ant Colony Algorithm for the Capacitated Vehicle Routing,Elsevier Electronic Notes in Discrete Mathematics, Volume 18, 1 December 2004, Pages 181186

6. Ching-Jung Ting, Chia-Ho Chen, A multiple ant colony optimization algorithm for the capacitated location routing problem Elsevier, International Journal of Production Economics Volume 141, Issue 1, pp 3444, January 2013

7. Juan S. Arias-Rojas, José Fernando Jiménez, Jairo R. Montoya- Torres, Solving Of School Bus Routing Problem By Ant Colony Optimization, Revista EIA17, pp 193-208, 2012.

8. http://mat.uab.cat/~alseda/MasterOpt/ACO_Intro, 14th august 2014.