A Combination of Intelligent Water Drop and Genetic Algorithm for Resolving Vehicle Routing Problem

A Combination of Intelligent Water Drop and Genetic Algorithm for Resolving Vehicle Routing Problem

Rupinder Kaur

M.Tech Scholar ,

Deptt. of Electronics & Communication Engg.

,BBSBEC,FGS Punjab

Navpreet Kaur

Prof.,

Electronics & Communication Engg.

BBSBEC,FGS Punjab

AbstractThis paper work is to done to find a solution of Vehicle Routing Problem. We use Intelligent Water Drops and genetic algorithms with crossover and mutation properties to find solution. Vehicle Routing Problem (VRP) is a complex combinatorial optimization problem. It belongs to the NP- complete class. It is not possible to use exact methods for large distances of the VRP. Genetic Algorithms provide approximate solution to problems. Genetic algorithms mainly depend on type of genetic operators Crossover operators are used to bring diversity in the population intelligent water drop algorithm (IWD) is fastest algorithm; it selects the minimum distance among all the available Iterates by the shortest way. IWD is a nature-inspired optimization algorithm, which has been inspired from natural rivers that how they find optimal paths to reach their destination. These paths follow from actions and reactions occurring among the water and riverbeds. Iintelligent water drop algorithm (IWD) is consist of two parts: a graph that have soils of different edges. and the moving part of the intelligent water drop algorithm (IWD), which is a few number of intelligent water drops.

Genetic Algorithm:

Comparison between this algorithm and a normal GA clearly shows the advantage of population diversity control. It automatically gets the crossover and the mutation rate to the changing population dynamics. The adaptive control means population diversity at user levels, and therefore prevents premature convergence in search. Existing experiments performed with 56 Solomon benchmark problems indicate this algorithm is competitive.[3]

Keywords: Vehicle Routing Problem, Intelligent Water drops, Ant Colony Optimization, Genetic Algorithm.

I. INTRODUCTION

GA properties: Crossovers

Fig.1 Genetic Algorithm

Vehicle routing problem:

The VRP can be defined as a fleet of Vehicles with a common depot, and with several Customer demands, with overall Minimum route cost which serve all the demands [3]. It is designed in a way that each customer is served only once by one vehicle. Genetic algorithms have been introduced by Darwin. They apply certain operators to a population solutions, in a way that new population will be improved compared with the old one. In some cases, the best solution can be found during the evolution of the algorithm. Unsuitable code may lead to poor performance. Operators used by genetic algorithms debug the process as natural selection is carried out. The operators used are in this are mutation and crossover operators.

Vehicle Routing Problem is famous combinatorial optimization problem [1].The aim is to find paths for vehicles to attend all the customers at a minimal cost without disturbing the capacity and time constraints of the vehicles. (2)

It is a genetic operator. In this it is used to fluctuate the programming of a chromosome. It is the way to reproduce and to biological crossover. Crossovers dont perform Mutual exchange of genes between two parents. They take data from one parent and put it in other to create a child. And then probability is calculated to check the features of child. As given below:

Fig.2 crossover property of GA

Above Fig. shows the crossover process of characteristics of parents to child. It shows how children adopt the properties of parents.

Mutation

Mutation is a genetic operator used to maintain genetic diversity from one generation to the next. It is analogous to biological mutation. It can be understand easily from the fig.

Fig. 3 Mutation property of GA

Child or Parent(s)

After the features and drawbacks have been intended for a new child, the scheme decides if the child is accepted or not. The process compares the properties of parents with the child. If the child does better, it will be accepted. If the child has a penalty more than their parent then another selection process will be performed, which provides special treatment the parents depending on their features.[3]

Fig.4 Child or Parents of GA

Intelligent Water Drop Algorithm:

Nowadays systems that are nature inspired are highly i demand they are one of the rich sources of inspiration for developing the systems for solving the present problems.IWD is one of the scientific fields that are closely related to nature, such as ant colonies, brain, bee colonies, and rivers. Problem solving techniques inspired from nature are time adaptive , neural networks ant colony optimization, computation, self-organizing maps, bee colony optimization, particle swarm optimization, electromagnetism.[5]

One of planned algorithm in the ground of the swarm intelligence is intelligent water drops algorithm. The IWD algorithm is based on the variations and motion of river systems, actions reactions that occurs among the water drops in rivers. The water drops are used to develop IWD .IWDs cooperate to reach to a better solution for a given problem. IWD algorithm may be used for maximization or minimization problems. These Intelligent Water Drops both compete and cooperate to find better solutions. By altering soils of the chart, the lane to improved solutions become more reachable. And already using IWD algorithm for early detection of nasal cyst during pregnancy scanning.

Therefore, the IWD algorithm is a population-based constructive optimization algorithm. IWD algorithm has already used for salesmans problem and multiple knapsack problems with impressive results. Both the MKP and TSP are NP-hard combinatorial optimization problems. [5] In the TSP, a map of cities is given to the salesman .He has to visit all the cities only once to complete a tour such that the length of the tour must be the shortest among all possible tours for that particular map.

The IWD algorithm, have two main Properties:

1. Velocity

2. Soil

Both of the two properties may change during the lifetime of an IWD. Both are inverse of each other An IWD flows from a starting point to a end point. The IWD start its tour with an early velocity and zero soil. During its tour, it removes a little soil and it gains a little speed. IWD is invented to flow in discrete steps. From its present site to its next site, the IWD velocity is enlarged by the quantity non-linearly proportional to the contrary of the soil between the two locations. Therefore, a lane with less soil lets the IWD become faster than a lane with more soil. Approximately every IWD algorithm is poised of two parts:

1. A graph that plays the role of distributed memory on which soils of different edges are preserved,

2. And the moving part of the IWD algorithm, which is few number of intelligent water drops.

   1. RELATED WORK

      Genetic Algorithms

      It is a parallel search mechanism. The solution for the optimization process is generated in three basic steps [6].that steps are shown in diagram. GA has received great attention in solving vehicle routing problems, Due to its global optimization. In VRP the customers are listed in order in which they are visited.

      The motive of the MDVRP is to reduce total delivery time as less as possible ,hence customers are connected to the nearest centers. In the given figure, there are two main centers A and B, each customer is connected to single centre exctly. This process is grouping process which is done on the basis of distance computation .Flow chart of GA is given below:

      Various techniques have already been proposed to solve the problem of VRP in August 2002 by Pascal Van Hentenryck, Russell Bent [1] like A Two stage Hybrid Local Search for VRP with Time Windows. The vehicle routing problem with time windows is also hard optimization problem that has got noticeable attention in last decades. This paper

      proposed by Pascal Van gives a two stage hybrid algorithm for transportation problem.

      Fig.5 Example of 10 customers in 2 deports.

      In the above figure, customers 1, 5,9,4,8 are connected to center A whereas customers 7, 10,3,6,2 are connected to center B. Figure 1. Example of an MDVRP with 2 centers and 10 customers.

      It firstly reduces the number of vehicles in use , using simulated annealing. After that It reduces travel cost. To reduce cost it uses large neighborhood search that relocate a number of customers, the results of experiments explains the effectiveness of algorithm, More important, the algorithm is very robust .With its parameters, it returns either best solutions or solutions very close to best in quality

      Ant colony Optimization Algorithm:

      Source of ACO is the behavior of ants. Ants initially discover area surrounding their nest When searching for food, in random manner. As soon as an ant finds a food source, it generates an idea about the quantity and the quality of the food and carries some of it to the nest. During their return, ants deposit chemical pheromone trail on the ground. The quantity of pheromone deposited, depends on the quantity ,quality of the food, It will guide other ants towards the food source. These interactions are called stigmergy, or communication through environment.

      This causes an autocatalytic reaction, i.e., the one that is started by itself. Ants attracted by the pheromone will follow the same path, causing more ants to be attracted see Fig.

      Fig.6 Optimization by Ant Colony

      N-Queen Puzzle:

      It is way for assigning the various position to queens of chess. The example of 8- queens is given in figure .It was proposed by chess player in 1948.It is a problem in which eight chess queens are put in such a way that no two queens are able to oppose each other .Therefore the solution requires that the no two queens can occupy the same row , or the same column, or the diagonal. This puzzle is called N-

      queen because any number of queens can be put in the place of N, and solution can be calculated.

      The IWD algorithm for the n-queen problem is called IWD- NQ algorithm[5]. IWD algorithm uses local heuristic. Such local optima takes no. of iterations of the algorithm. A local algorithm called N-Queen Local Search has been given by (ShahHosseini, 2008(b).

      Fig.7 showing 4*4 chess board

      Multidimensional Knapsack Problem (MKP):

      The MKP, is a generalization of KP. MKP is standard NP- hard problem. In this, the aim is to include some of the items in the knapsacks to get maximum profit with the thought that none of knapsacks becomes overflowed. To solve the MKP using IWD algorithm, problem can be viewed as a graph (N,

      E) The IWD-MKP algorithm is proposed by Shah-Hosseini, in 2008. [5]

      MDVRP GA :

      .

      Fig.8 Multi depot vehicle routing problem with single depot

      The above fig shows the various routes from the single depot. The purpose of the problem is to discover routes for vehicles to examine all the customers at a negligible cost in requisites of number of routes and total travel space [6]. The solution to the MDVRP, is obtained through Genetic Algorithm (GA). The clientele are grouped based on distance to their nearest centers and then in retreat with Clarke and Wright saving method. Further routes are scheduled and optimized using GA. The results were evaluated in terms of depots route length, optimal distance, optimal route, computational time, average distance, and number of vehicles.

   2. OBJECTIVES AND PROBLEM FORMULATION

      The intention of the VRP is to diminish the total route cost. Intelligent Water Drops algorithm is a swarm-based optimization algorithm. It uses two types of parameters. Static parameters are constant during the process. Dynamic parameters are reinitialized after each iteration.The Capacited VRP identifies the best path to deliver goods by a limited number of vehicles with a fixed amount of load. It is not possible Due to the nature of problem to use exact

      methods.. The technique of VRP using IWD is the old technique which is less efficient. So we introduce a new technique which is the combination of two techniques .It overcomes all the problems appears in the conventional technique. The main problems are efficiency and the adjacent route to be chosen and all the customers to be enclosed in that adjoining path.

      Deploy the customers in area defined

      Deploy the customers in area defined

      Each vehicle has a limit like the work in some time window, carrying capacity, work within the restricted range of vehicle etc. All the Important parameters are measured in this research work. The key plan is to defeat the drawbacks of reporting.

      1. But if the fitness of the old population is smaller or lesser then the new population selected then the population is again up graded using GA. After the up gradation using GA the steps 7-9 are repeated. This process is repeated until the fitness of old population does not exceeds the fitness of the new population selected.

      2. When the fitness of new population comes out to be greater than the fitness of new population selected, the result is saved and the parameters are calculated.

      Initialize the count of customers and location.

      Initialize the count of customers and location.

      Block Diagram:

   3. METHODOLOGY

Calculate the individual distance of customer with others

Calculate the individual distance of customer with others

In this process the VRP is solved combining the IWD and GA algorithm. The IWD is used for selecting and GA is used for updating. This process is more effective and efficient than the conventional one. The process takes certain steps to complete. The methodology of this technique is described as below:

1. To start the process, first thing needs to be known is the number of customers and the locations as these are the basic things that are to be known while choosing the shortest route. So, the first step in the methodology would be initializing the count of customers and the location. The number of the customers and the numbers will be counted

2. Then the area will be defined and the customers in that defined area will be calculated. The customers in the defined area will then be deployed.

3. These customers in the defined area are located at some distance to each other. After calculating the number of customers in the defined area the individual distance of each customer will be calculated with others.

4. As the distance of each customer with others is calculated individually, we will now have the shortest route. The initial population will be generated.

5. After the generation of initial population the best population is to be selected. The best population is selected on the basis of shortest route. For selection IWD algorithm is used. So, now select the best population with IWD.

6. After selection the next step is up gradation. The up gradation in this method is done using Genetic Algorithm (GA). So, in this step upgrade the population using GA

7. Now, the best population is selected and up graded using IWD and GA algorithm. Reselect the population with best fitness.

8. Now compare the fitness of the population earlier selected and the population re selected. The next step purely depends on the difference between the fitness of the newly selected population and the previously selected population.

9. If the fitness of the new population selected is lesser then the fitness of the old population selected then the result is saved and the parameters are to be calculated.

No

Save result & calculate parameter

Save result & calculate parameter

Yes

Generate initial population for routing

Generate initial population for routing

Select best population with IWD

Select best population with IWD

Upgrade the population with GA

Upgrade the population with GA

no

Reselect the population with best fitness

Reselect the population with best fitness

If New fit< old fit

1. EXPERIMENTAL RESULTS

   Mat lab version 7.10.0.499(R2010a) is used to put into practice the algorithm. It provide assemblage of the customers. It also used to pick the best path to reach the end spot. Fig. 5 shows the assemblage of the 20 customers. In assemblage the customers are assigned to the nearby end spot. So that the space travelled by the medium is straight. The customers are clustered based on the least space between customers and end points. Distance between the customer and the end point is calculated and based on the minimum space customers are assembled and the results are shown below .

   Location Of Customers

   100

   90

   80

   70

   60

   50

   40

   30

   20

   10

   Total Route Distance = 903.4426, Iteration = 5

   100

   90

   80

   70

   60

   50

   40

   30

   20

   10

   0

   3 16

   6 7

   11

   17 5

   8

   14

   19 4

   1

   18

   15

   2

   9

   13

   10

   2012

   0

   10 20 30 40 50 60 70 80 90 100

   Fig.11 total distance calculated by algorithm is shown

   Graph shows the total distance calculated by the algorithm. It is 903.44 which is achieved by iteration no. 5.This is shortest path choosen between 20 customers by the algorithm.

   Individual Iteration Result

   10 20 30 40 50 60 70 80 90 100

   Fig.9 Location of 20 customers in xy coordinate

   Fig shows the various locations of 20 customers. In routing the customers the customers are assigned the route in such a way that each customer is attended only once by only one vehicle. Randomly chosen location of customers are shown.

   6

   6

   x 10 Choosed Velocity Of Iteration No:- 10

   2.019

   2.018

   2.017

   950

   945

   940

   935

   Distance

   Distance

   930

   925

   920

   915

   910

   905

   900

   1 2 3 4 5 6 7 8 9 10

   Iterations

   Fig. 12 shows individual iteration result

   2.016

   950

   Best Distance Achieved Iteration Result

   Velocity

   Velocity

   945

   2.015

   940

   2.014

   2.013

   2.012

   2.011

   1 2 3 4 5 6 7 8 9 10

   population

   Fig.10 Choosed Velocity of iteration no. 10

   935

   Distance

   Distance

   930

   925

   920

   915

   910

   905

   900

   1 1.5 2 2.5 3 3.5 4 4.5 5

   Iterations

   Fig.13 Best distance achieved iteration result

   The fig shows the velocity of iteration no. 10. As explained above IWD algorithm is iteration based algorithm, given below fig shows the velocity of one iteration

   Above Fig shows the best distance achieved by all iterations results. The graph is between distance and various iterations.graph shows only the best solution.

2. CONCLUSION AND FUTURE SCOPE

We all know that VRP that is The Vehicle Routing Problem (VRP) is a problem of hard optimization. It assemble a number of customers with restricted number of vehicles. It has implemented algorithm that attain minimum distance, maximum coverage of customers with low cost. It has introduced IWD optimization algorithm with genetic algorithm. It has mixed IWD optimization with GA to update data and then this has analyzed it with the previous system IWD which leads to maximum customer coverage with less distance coverage .This algorithm is fast algorithm

. The future scope of using this algorithm in vehicle routing trouble is that we can put into practice the same problem with the real time data and more objectives except distance, time and cost.

REFERENCES

1. Kenny Q. Zhu Singapore 119260 kzhu@comp.nus.edu.sg A Diversity-controlling Adaptive Genetic Algorithm for the Vehicle Routing Problem with Time Windows

2. Russell Bent ,Pascal Van Hentenryck,August 2002,"A Two stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows

3. Abdul Kadar Muhammad Masum1, Md. Faisal Faruque, Mohammad Shahjalal, , Md. Iqbal Hasan Sarker, Chittagong Solving the Vehicle Routing Problem using Genetic Algorithm

4. Laheeb M. Alzubaidy , Baraa S. Alhafid Proposed Software Testing Using Intelligent techniques Intelligent Water Drop (IWD) and Ant Colony Optimization Algorithm (ACO))

5. Neeraj Singla, Sugandha Sharma

   Study on Selection of Intelligent Waterdrop Algorithm for Solving Multiple Problems: A Review

6. A.L. Kok, E.W. Hans, J.M.J. Schutten, Vehicle routing under time- dependent travel times: the impact of congestion avoidance

7. Surekha P* Dr.S.Sumathi Solution To Multi-Depot Vehicle Routing Problem Using Genetic Algorithms

8. Suresh Nanda Kumar, Ramasamy Panneerselvam March 12, 2012. A Survey on the Vehicle Routing Problem and Its Variants