# An evolutionary approach for shortest path problem--courier delivery system.

IntroductionDecision support for shortest route courier delivery system is defined as finding the shortest route with minimum distance, minimum time and type of route priority. There is a considerable amount of pressure on the dispatcher to make sound performance decisions within a minimum time frame. As a manual system human dispatchers are in a constant state of stress while operating in this high-pressure and ambiguous environment. The high burn-out rate of human operators creates the demand for a Decision Support System that can help to relieve human stress while simultaneously improving the level of dispatching performance. The courier deliver system is very complicated because of various constraints applied over it. The possible constraints are

* Minimum time to deliver the courier

* Shortest route to follow because of time and fuel consumption

* Fixed restrictions as no direct path between two or more than two destinations.

* Sudden change in route due to emergency or heavy traffic load

The courier dispatch domain is complicated and dynamic. To add further strain on the situation, the dispatcher's decisions are often determined by conflicting forces. For example, customers want fast delivery routes; management wants efficient delivery routes; and drivers want easy delivery routes. When taken together, the problems of dynamic context and compromise create a domain too complicated for a simple traditional operation research approach linear algorithm ineffective, [5] when it comes to developing solutions for the courier dispatch domain. In addition, even experienced dispatch operators could not convey a set of heuristics to describe how they make decisions on the job.

Therefore, an effective Decision Support System would require a programming technique that allows the software to acquire its own optimized solution. To develop the decision support system for courier dispatching, the problem is defined as finding the Hamiltonian circuit [3] with the minimum time, minimum distance and type of route travelled.

To determine the Hamiltonian circuit it self is a NP-complete problem and when shortest distance and minimum time is added with the Hamiltonian Cycle, it becomes a very hard optimization problem in the field of operations research. There are various approaches to solve this problem. One of the simple approaches is to try all the permutations and then select the cheapest one but given that the number of permutations O(n!) [4] is the factorial of the number of locations, this solution rapidly becomes impractical. Using the techniques of dynamic programming, one can solve the problem in time O([n.sup.2][2.sup.n]) other approaches include: Various branch-and-bound algorithms, and linear programming method which has the limitation.

A. Shortest Route Hamiltonian Circuit

Given a connected, undirected graph G with n nodes, a least cost Hamiltonian circuit H is a sub graph of a G that connects all of G's nodes and contains one cycle [4]. In this graph every edge (We, j) is associated with a numerical costs(distance) [c.sub.ij]. A shortest route Hamiltonian circuit is the graph of the smallest possible total distance travelled

C = [summation] [c.sub.ij]

Where (i, j). [member of] H

B. Genetic Algorithm

Genetic algorithms are typically implemented as a computer simulation in which a population of abstract representations (called chromosomes) of candidate solutions (called individuals) to an optimization[1] problem evolves toward better solution.

C. Work flow of GA

1. Initialisation of parent population

2. Evaluation

a) Self Loop

b) Hamiltonian Cycle with n edge.

c) Degree Constraint check (missing node)

d) Isolated node

3. Selection

4. Crossover/recombination

5. Mutation

6. Evaluate child and Go to step 3 until termination criteria satisfies

* Initialisation of parent population means to generate the M number of solution [2] string known as parent population which is mostly random

* Evaluation means give fitness to each of the solution. It is very important part of the algorithm based on the nature of problem and the requirement of the solution. It varies problem to problem.

* Selection means to select some of the best fit chromosomes from parent population according to some selection criteria (eg. Roulette wheel selection). Fit solution are likely to survive and bad solution are likely to die off

* Crossover/Recombination means to exchange partial solution between pair of selected solution with some probability

* Mutation means change the value of an allele of solution with some small probability value, it is a motivation to explore new point in the solution space

Shortest Route Courier Delivery Problem Presentation

The Shortest route Courier delivery problem is represented with the help of Fig 1. Where each small circles represents a location and the magnified circles are those location where the couriers are to deliver. The locations are 13, 20, 34, 49, 57, 63, 73, 84, 92 and 10. The distance and type of route between two locations has been shown in Table-1 and Table-2 respectively.

[FIGURE 1 OMITTED]

These locations are represented as a node of a undirected graph and it is represented in the form of a adjacency matrix in Table--1. This table contains the distance between two location.

In this table, non zero numbers represent the distance between two locations. Zero (0) represents no path between two locations and strikethrough numbers represent the path constraint between two locations due to sudden change in route or due to emergency or heavy traffic load. Table-2 is used here to show the type of route between two locations.

This table contains three types of route: Heavy, Smooth and Difficult. These three types represent three speed range which is used to calculate the time between two locations. Table -3 represents the behaviour of three types of route--

Genetic Algorithm Approach to Solve the Problem

A. Initialisation of parent population

Here 5 chromosomes (parent solutions) a, b, c, d and e are generated randomly with the help of a function. The function has the constraint that an allele of each chromosome must not be repeated in that chromosome. It is called parent population. Each chromosome is the combination of ten numbers (allele). Each chromosome represents a Courier delivery tour (Hamiltonian cycle) [3] where an each allele represents itself as a location and a path between location and its fixed position. All these Locations are numbered in a sequence. 1,2,3.... 10. where 1 represent location 13, 2 represent 20 and so on.

[FIGURE 2 OMITTED]

[FIGURE 3 OMITTED]

[FIGURE 4 OMITTED]

[FIGURE 5 OMITTED]

[FIGURE 6 OMITTED]

B. Evaluation

Evaluation is based on fitness function and total minimum distance travelled in each tour. All these tours are evaluated with fitness functions. The tour represented by each chromosome, may be illegal due to four reasons-

(1) Self Loop

(2) Violation of degree constraint or missing node

(3) Hamiltonian Cycle

(4) Isolated edge or path.

C. Fitness function

There are four reasons for the Illegality of the tour; therefore four Fitness functions have been developed here to check the fitness. 1 mark is assigned to pass each fitness function, while 0 marks are assigned in the case of failure. Chromosome is implemented in the form of array of size [10], where array index shows the fixed position and its value is an allele of generated chromosome. The representation of chromosome is as following

Chromo [1] = 2;Chromo [2] = 3;Chromo [3] = 5;

Chromo [4] = 7;Chromo [5] = 10;Chromo [6] = 1;

Chromo [7] = 6;Chromo [8] = 4;Chromo [9] = 8;

Chromo [10] = 9;

(1) Self Loop

For the undirected connected graph

G = (V, E)

Where V = {[v.sub.1] [v.sub.2]...... [V.sub.n]}

E = {[e.sub.1], [e.sub.2]....... [e.sub.n-1]}, each edge [e.sub.k] is associated with vertices ([v.sub.i], [v.sub.j]) ([v.sub.i], [v.sub.j]) [member of] [e.sub.k]

If (We == j) then it is called self loop for vertex v.

Function self_loop() Begin Set WE = 1 and N = 10 (where N is total no of location) for WE = 1 to N by 1 do If chromo[WE] == WE Print: " self loop", Terminate fr endif endfor End.

(2) Degree constraint (missing node or repeated node)

Since each location has to be visited once, the location will be connected with two other cities. In-degree and out-degree for each location will be 1. If an allele of a chromosome is not repeated then it ensures that there each location is connected with two other locations.

d([v.sub.i]) == 2; where d denotes the degree of vertex We.

Function degree_constraint() Begin Set WE = 1 and N = 10 (where N is total no of location) for WE = 1 to N by 1 do Set C = 0 for J = 1 to N by 1 do If chromo[WE] == WE Increment C by 1 terminate the inner loop endif endfor if (C = 0) print: "missing node" terminate the outer loop endif endfor End.

(3) Isolated edge

If the pair of locus (array index) and allele (value) is same with other locus and allele in the same chromosome, then the edge will be isolated.

For any generated chromosome, pair of its locus and allele is defined as Chromo( We [left arrow] v)

Where We is locus and v is the allele at this locus and its value vary from 1> = We < = N and 1> = v < = N

where N is the total no of node. Chromo( We [left arrow] v) = Chromo( j [left arrow] z) If ( We = z) and (v = j) then edge [e.sub.iv] or [e.sub.jz] is isolated.

Function isolated_edge() Begin Set WE = 1 and N = 10 (where N is total no of location) for WE = 1 to N by 1 do Set v = chromo [WE] If chromo[v] == WE Print : "isolated edge" Terminate from the loop endif endfor End.

(4) Hamiltonian Cycle

For each chromosome Chromo[N] there must be a Hamiltonian cycle., Two vectors Chromo and A of size N are considered and initialized with value null.

For a chromosome Chromo[N]

Function Hamiltonian_cycle() Begin Set j = 1, p = 1, t = 1 and N = 10 (where N is total no of location) for WE = 1 to N-1 by 1 do If (chromo[j] == 1) Terminate the loop Endif Set j = chromo[j] If ( p > 1) For l = 1 to p-1 by 1 do If (a[l] == j) Set t = 0 Terminate the loop Endif Endfor Endif If( t == 0) Terminate the loop endif Set A[p] = j Increment p by 1 Endfor If ( We < 10) Print : NO Hamiltonian Cycle Else Print : Hamiltonian Cycle exist End

D. Result of fitness function

After applying the fitness function it is found that all these tours are legal and have some cost which is in the form of total distance travelled. For passing each fitness function, 1 point will be given and in the case of failure 0. Following fitness point and distance earned by each chromosome (TABLE -4)

E. Selection

In genetic algorithm fit solution are likely to survive and bad solution are likely to die off. So some of the best fit chromosomes are selected from parent population according to some selection criteria (e.g. Roulette wheel selection). we have used here simply maximum point and minimum distance criteria. Selected chromosomes are a, b, c, and d.

F. Crossover/Recombination Selected solutions are used for crossover. WE have considered 1 point cross over. (a.) 2 3 5 7 10 1 6 4 8 9 (b.) 10 3 7 5 2 4 1 6 8 9 After crossover of a and b following child solutions x and y are found. (x) 2 3 5 7 10 4 1 6 8 9 (y) 10 3 7 5 2 1 6 4 8 9 Similarly c and d populations are used for crossover (c) 7 3 5 2 9 4 6 1 10 8 (d) 4 3 5 2 10 9 1 7 8 6 After crossover of c and d following child solutions p and q are found. (p) 7 3 5 2 9 9 1 7 8 6 (q) 4 3 5 2 10 4 6 1 10 8

G. Mutation

It is the process to change the value of an allele of solution with some small probability value e.g. 1% Motivation is to explore new point in the solution space. WE have applied here a new concept to mutate all those allele which are repeated a chromosome and it will be mutated (replaced) with the missing value in low to high order of the missing value.

Missing values (a1, a2, a3........ an)

where a1<a2<a3............ <an

Repeated allele (x1, y1, z1...... x1 ..... y1 ........ N)

Replace x1 with a1 and y1 with a2, where x1<y1.

Since there are no repetition of an allele in chromosome x and y , no any allele will be replaced while chromosome p and q will be mutated with their missing values.

For chromosome p, missing values are 4 and 10 and repeated alleles are 7 and 9 which will be replaced with 4 and 10 respectively. Similarly chromosome q will be mutated.

(x) 2 3 5 7 10 4 1 6 8 9 (y) 10 3 7 5 2 1 6 4 8 9 (p) 7 3 5 2 9 10 1 4 8 6 (q) 4 3 5 2 10 7 6 1 9 8

These four chromosomes x, y, p, and q (child solutions) are used to draw 4 different routes.

[FIGURE 7 OMITTED]

[FIGURE 8 OMITTED]

[FIGURE 9 OMITTED]

[FIGURE 10 OMITTED]

H. Evaluation of child population

After applying the fitness function, WE found the following fitness value for each of the child population

Decision Support

From Table -5, It is found that child population x has the maximum fitness value 4 and total minimum distance travelled is 54 and at the same time p and q are illegal chromosomes. On the basis of all these fit chromosomes from Table-4 and Table-5, following possible path can be displayed and recommended on the basis of the preference of the courier delivery system.

On the basis of Table-6, if the selection criteria of the path is minimum time and driver's comfort, Path No. 2 is the best recommended option. If this Path No 2 is selected, its detail is shown in Figure-11 Table-7.

[FIGURE 11 OMITTED]

Conclusions

In this paper, we have proposed a simple Genetic Algorithm approach with strong fitness function to provide Decision support for shortest route courier delivery system, which is one of the hardest problems in the class NP (non-deterministic polynomial problems). We have described the problem and GA that encodes the candidate solution to the problem in a simple way and included all the important constraints and developed functions which are required for the solution of Network Optimization Problem. We have also included a new mutation approach to change allele of the chromosome with the missing one. The effectiveness of the methodology however can be increased by applying the various genetic operators with variations and the densely connected locations.

Acknowledgements

Our thanks to the reviewers for their cogent and insightful comments.

References

[1] David E. Goldberg. 1989. Genetic Algorithms in search, optimisation and machine learning. Addison-Wesley.0-201-15767-5

[2] Mitchell, M. (1998). An Introduction to genetic Algorithm. MIT Press. 0-262 113316-4(HB)

[3] Anand Kumar, Dr. N.N. Jani (2009). A Genetic Algorithm Approach to solve Hamiltonian Circuit Problem. IEEE conference proceeding (IACC' 09) ISBN NO: : 978-981-08-2465-5

[4] NarsinghDeo, 2000. Graph Theory with Applications to Engineering and Computer science: (PHI)

[5] I. Benyahia and J. Potvin 1998: Decision Support System, IEEE Transactions on Systems, Man and Cybernetics; Vol 28, No 3.

(1) Anand Kumar and (2) N.N. Jani

(1) AMC Engineering College, Bangalore E-mail: kumaranandkumar@gmail.com

(2) Kadi Sarva Vishwavidyalya, Gandhinagar E-mail: drnnjanics@gmail.com

Table 1: Adjacency Matrix of the Graph. 13 20 34 49 57 63 73 84 92 10 13 * 5 0 8 17 12 6 21 30 25 20 5 * 4 7 15 0 0 23 31 24 34 0 4 * 0 7 0 12 15 17 0 49 8 7 0 * 6 4 9 13 15 0 57 17 15 7 6 * 0 13 0 7 4 63 12 0 0 4 0 * 5 5 7 4 73 6 0 12 9 13 5 * 8 12 10 84 21 23 15 13 0 5 8 * 7 6 92 30 31 17 15 7 7 12 7 * 3 10 25 24 0 0 4 4 10 6 3 * Table 2: Types of Route. 13 20 34 49 57 63 73 84 92 10 13 * D 0 S D S D D S H 20 D * H S S 0 0 S H D 34 0 H * 0 S 0 S D D 0 49 S S 0 * H D H S D 0 57 D S S H * 0 S 0 S D 63 S 0 0 D 0 * S S S D 73 D 0 S H S S * H H S 84 D S D S 0 S H * D S 92 S H D D S S H D * D 10 H D 0 0 D D S S D * Table 3: Behaviour of Each Types of Route. Type Description Speed Range Average (KM/H) Speed (KM/H) H Heavy Traffic 10-30 20 D Difficult 30-50 35 S Smooth 50-70 60 Table 4: Fitness of Parent Population. Chromosome Fitness Distance a 4 69 b 4 87 c 4 70 d 4 62 e 4 157 Table 5: Fitness of Child Population. Chromosome Fitness Distance x 4 54 y 4 102 p 2 -- q 0 -- Table 6: Possible Path. Type(km) Path No. Distance(km) Time(hour) H D S 1. 69 1.8 13 19 37 2. 87 2.85 35 20 32 3. 70 1.7 04 34 32 4. 62 1.6 12 15 35 5. 157 3.55 00 79 78 6. 54 1.67 13 29 12 7. 102 3.78 35 10 57 Table 7: Selected Path Description. Distance Type Distance Average Time (hour) Total (km) speed(km/h) time Difficult 15 35 0.42 Heavy Traffic 12 20 0.6 1.60 hr Smooth 35 60 0.58

Printer friendly Cite/link Email Feedback | |

Author: | Kumar, Anand; Jani, N.N. |
---|---|

Publication: | International Journal of Computational Intelligence Research |

Date: | Apr 1, 2010 |

Words: | 3015 |

Previous Article: | Combination of RBF algorithm and filters applied to prevent attacks in a web server. |

Next Article: | Pixcals statistical based algorithm to detect microcalcifications on mammograms. |