21CS2109AA – AI FOR DATA SCIENCE

A Project Report

on

“GENETIC ALGORITHMS”

Under the Guidance of

SHASHI MEHAROTRA

Assistant Professor

SUBMITTED BY:

I.D NUMBER NAME

2100030136 Saranya Reddy

2100032432 Rohith Venkata Sai

2100032473 Vachaspathi Gnaneswar

KONERU LAKSHMAIAH EDUCATION FOUNDATION

DEPARTMENT OF COMPUTER SCIENCE AND ENIGNEERING

(DST-FIST Sponsored Department)
Green Fields, Vaddeswaram, Guntur District-522 502

November – 2022
 Declaration

We here by declare that this Project report entitled Genetic Algorithm

has been prepared by us in the course 21CS2213AA AI FOR DATA SCIENCE in

COMPUTER SCIENCE AND ENGINEERING during the Odd Semester of the academic year

2022-2023. We also declare that this project-based lab report is of our own effort.

Date: 21/11/2022

Place: KL University

Signature of the Student

Student Name Id Number

Saranya Reddy 2100030316

Rohith Venkata Sai 2100032432

Vachaspathi Gnaneswar 2100032473

 CERTIFICATE

This is to certify that the project based Lab report entitled “Genetic Algorithm” is a
bonafide work done [Link] Reddy, Mr. Rohith Venkata Sai, Mr. Vachaspathi
Gnaneswar bearing Regd. No. 2100030316, 2100032432, 2100032473 respectively to
the course 21CS2213AA AI FOR DATA SCIENCE in COMPUTER SCIENCE AND
ENGINEERING during the ODD Semester of Academic year 2022-2023.

FACULTY IN CHARGE

Dr. Shashi Mehrotra

 ACKNOWLEDGEMENTS

Our sincere thanks to Dr. Shashi Mehrotra in the lab sessions for her outstanding
support throughout the project for the successful completion of the work

We express our gratitude to Dr. M. KAVITHA, Course Co-Ordinator for the course
21CS2213AA AI FOR DATA SCIENCE in the Department of Computer Science and
Engineering for providing us with adequate planning and support and means by which
we can complete this project.

We express our gratitude to Prof. V. HARI KIRAN, Head of the Department for
Computer Science and Engineering for providing us with adequate facilities, ways and
means by which we can complete this project.

We would like to place on record the deep sense of gratitude to the Vice
Chancellor, K L University for providing the necessary facilities to carry out the project.

Last but not the least, we thank all Teaching and Non-Teaching Staff of our
department and especially our classmates and our friends for their support.

Name: G. Vachaspathi Gnaneswar

Reg. No: 2100032473

 INDEX

[Link] TITLE PAGE NO

1 Abstract <pageno>

2 Introduction <pageno>

3 Literature Work <pageno>

4 System Requirement Specification <pageno>

5 Methodology <pageno>

6 Coding and implementation <pageno>

7 Result Analysis <pageno>

8 Conclusion <pageno>

9 Future Enhancement <pageno>

10 Bibliography <pageno>
 ABSTRACT

The purpose of this research was to develop a version of a genetic algorithm (GA
) which would provide near optimal solutions for Vehicle Routing Problems (VRP) with both
time and weight constraints. The genetic algorithm used for the experimentation was adapted
from a GA which had been developed by James Bean at the University of Michigan to solve
machine scheduling problems. The VRP data sets used in this research were obtained from the
literature. Various aspects of the GA were experimented with in order to develop a version
which would perform consistently well for all the data sets. The results of the final version of
the genetic algorithm were then compared to the results presented in the original papers. The
results from this research indicated that the genetic algorithm seems to perform relatively well
for smaller problems with 50 or fewer customers. However, the results seem to become
progressively worse as the problem becomes larger.

This paper deals with generating of an optimized route for multiple Vehicle routing
Problems (mVRP). We used a methodology of clustering the given cities depending upon the
number of vehicles and each cluster is allotted to a vehicle. K means clustering algorithm has
been used for easy clustering of the cities. In this way the mVRP has been converted into VRP
which is simple in computation compared to mVRP. After clustering, an optimized route is
generated for each vehicle in its allotted cluster. Once the clustering had been done and after
the cities were allocated to the various vehicles, each cluster/tour was taken as an individual
Vehicle Routing problem and the steps of Genetic Algorithm were applied to the cluster and
iterated to obtain the most optimal value of the distance after convergence takes place. After
the application of the various heuristic techniques, it was found that the Genetic algorithm gave
a better result and a more optimal tour for mVRPs in short computational time than other
Algorithms due to the extensive search and constructive nature of the algorithm. Keywords:
Multiple vehicle routing problem, k-means clustering, genetic algorithm, and combinatorial
optimization.
 INTRODUCTION
The traveling salesman problem (TSP) consists of the need to visit many places
in the shortest, safest, and least expensive way and then return to the starting point, so that the
route does not take too much time, wasting company resources. Usually this problem is
presented with the help of a graph or map whose points are expressed by cities and the edges
connecting them—roads.

This problem has a special feature—it is not possible to solve it any other way
than by comparing all possible routes. This feature makes this problem NP-hard. In practice
(that is, having a limited amount of available time), heuristic methods are used to solve NP-
diffificult problem. These methods do not guarantee fifinding the optimal solution but offer an
acceptable approximate solution in a reasonable time. In addition to heuristic methods, which
are created to solve one specifific problem, there are metaheuristic methods. Their main
advantage is that they can be used for more than one problem and do not require prior
knowledge of the space available solutions. Most often they combine the features of random
search algorithms (random search) and algorithms that use gradient navigation in the space of
solutions (for example, in the hill-climbing algorithm). They demand only a measure by which
it will be possible to assess how optimal the found solution so. This measure usually has the
form of a polynomial function value, whose arguments belong to the searched solution space.

The Vehicle Routing Problem (VRP) is a generic name given to a set of problems
in which a set of routes for a flfleet of vehicles based on one or several depots are to be formed
to serve the customers dispersed geographically. The objective of the VRP is to form a route
with the lowest cost to serve all customers.

The vehicle routing problem is a major problem in distribution and logistics. The
VRP was fifirst described in 1959, by Dantizg and Ramser, and was called The Truck Dispatch
Problem. It may be considered a more broad and generalized variation of the traveling salesman
Problem, which has a large number of possible solutions (for 15 locations that have to be
visited, there exist 15! solution, in other words, 653,837,184,000 valid and proper routes that
can be created); therefore, it is diffificult to determine the best and optimal solution. In the
original traveling salesman problem, the optimization was performed to minimize mileage, but
in modern times, values such as time or petrol usage can be also used as main optimization
values, as they are usually somehow correlated with distance. VRP is a combinatorial integer
programming problem, which is NP-hard. There are some domains of business, with
transportation regarded as added value to the product, where the optimization of vehicle routing
can lower costs up to 25% in total. The economic benefifits of more open markets are a key
point for VRP. In addition, current technology makes it possible to use VRP solutions in more
a dynamic environment, working from live data and performing calculations in realtime. This
paper discusses the usage of genetic algorithms for the vehicle routing problem. The genetic
algorithm, as an algorithm of natural selection, searches space for an approximate solution to
problems with multiple solutions. One of the applications is the search for the optimal path;
here, it is a more complex problem, as the limitations of route selection defifined in the VRP
problem are imposed. The paper analyzes the inflfluence of genetic operators on the
effificiency of the algorithm, demonstrating their inflfluence on the search for a solution.

The idea is to fifind the solution to the NP-hard vehicle routing problem with
the use of metaheuristics. The chosen metaheuristic was a genetic algorithm, that belongs to
the group of evolutionary strategies as a part of Artifificial Intelligence. The paper presents the
analysis of metaheuristics usage for solving the vehicle routing problem with special attention
toward genetic algorithms. The created prototype implements different genetic operators,
modifified for usage with vehicle routing problem. Set experiment series were performed to
determine which combination of genetic operators is best for solving vehicle routing problem,
to determine how much participation certain genetic operators should have in the process of
producing results for the vehicle routing problem, and fifinally, which one will enable fifinding
the optimal solution for large-scale real-life instances of the vehicle routing problem.
• First, we analyze the use of the GA along with other metaheuristic algorithms to solve the
VRP. Here, a prototype modular and flflexible general purpose GA is implemented.
• Second, we show the implementation of different GA operators that are modifified to solve
the VRP. Designing and running experiments enable determination of the best combination of
genetic operators for solving the VPR.
• Third, we analyze the impact and participation of GA operators through simulations of the
selected problem.
• Finally, experiments are conducted to fifind an optimal solution for a large-scale real-life
instance of the VRP.
 LITERATURE WORK
The genetic algorithm belongs to the family of evolutionary algorithms, along with
genetic programming, evolution strategies, and evolutionary programming. Evolutionary
algorithms can be considered as a broad class of stochastic optimization techniques. An
evolutionary algorithm maintains a population of candidate solutions for the problem at hand.
The population is then evolved by the iterative application of a set of stochastic operators. The
set of operators usually consists of mutation, recombination, and selection or something very
similar. Let’s discuss some of the papers published that is related to the Genetic Algorithm in
the past.

Bryant [BRY00], here in this paper compared the results, which come after
applying many different crossover and mutation operators devised for the traveling salesman
problem and it is concluded that operators that use heuristic information or a matrix
representation of the graph give the best results. Genetic algorithms are an evolutionary
technique thatuses crossover and mutation operators to solve optimization problems using a
survival of the fittest idea. They have been used successfully in a variety of different problems,
including the traveling salesman problem. In the traveling salesman problem the aim is to find
a tour of all nodes in a weighted graph so that the total weight is minimized. The traveling
salesman problem is NP-hard but has many real world applications so a good solution would
be useful. Enrietch [ERA00] in this paper “Evolutionary algorithms” introduced that
Evolutionary Algorithms are stochastic optimization techniques based on the principles of
natural evolution. An overview of these techniques is provided with the general functioning of
EA’s, and gives an outline of the main families into which they be divided. Subsequently, it
analyzes the different components of an EA, and provides some examples on how these can be
instantiated. In the end it finished with a glimpse of the numerous applications of these
techniques. Various techniques are Evolutionary Programming, Evolutionary strategies,
Genetic programming and Genetic Algorithms. The basic differences between these paradigms
lie in the nature of the representation schemes, the reproduction operators and selection
methods. 9Madureira [MAD02], suggested GA for the resolution of real world scheduling
problems, and proposed a coordination mechanism. Because of frequently changing dynamic
environments, providing efficient production management and timely delivery are one of the
hard to solve problems.

Scheduling is to allocate a set of machines to perform a set of jobs within a certain

time period, and the goal of scheduling is to find an appropriate allocation schedule which
maximizes certain performance measure. For the implementation issues, the solutions are
encoded by natural representation, and the order crossover operator is used. They used the
inversion mechanism as mutation operator. Finally, Madureia et al. solved dynamic scheduling
problem using a set of static scheduling schemes by GA, and they showed the feasibility of GA
in Job-Shop scheduling problem. Sandstrom [SAN02] suggested the GA which is applied for
assigning task priorities and offset to guarantees that real time timing constraints. Assigning
timing constraint to task is not trivial problem in real-time system. They showed how timing
constraints be mapped to attributes of periodic tasks running on standard preemptive RTOS
(Real-Time Operating generate a result that satisfies a subset of the timing constraints in cases
where it is impossible to fulfill all constraints. GA, the mechanism of natural selection,
gradually improves individuals timing constraints test cases and showed good result. Molga
[MOL05] suggested in this paper on “Test functions for optimization needs” provides the
review of literature benchmarks (test functions) commonly used in order to test optimization
procedures dedicated for multidimensional, continuous optimization task. Special attention has
been paid to multiple-extreme functions, treated as the quality test for opposing optimization
methods (GA, SA, TS etc.). Quality of optimization procedures (those already known and those
newly proposed) are frequently evaluated by using common standard literature benchmarks.
There are several classes of such test functions, all of them are continuous, which are, first is
unimodal, convex,multidimensional, second is multimodal, two-dimensional with a small
number of local extremes, third is multimodal, two-dimensional with huge number of local
extremes and the last is multimodal, multidimensional with huge number of local extremes.
Where, class first contains nice functions as well as malicious cases, causing poor or slow
convergence to single global extreme. Class second is intervening between first and third and
last is used to test quality of standard optimization procedures in the unfriendly environment,
namely that having few local extremes 1011 with single global one. Classes third and fourth
are recommended to test quality of intelligent resistant optimization methods.
 SYSTEM REQUIREMENT SPECIVICATION

➢ SOFTWARE REQUIREMENTS:
The major software requirements of the project are as follows:

Language : Python, Python Libraries

Tools : Microsoft Word and Jupiter Notebook

➢ HARDWARE REQUIREMENTS:

The hardware requirements that map towards the software are as follows:

• Intel (or AMD equivalent) i5 or better processor, 7th generation

or newer (Virtualization must be supported)
• Windows 10 Operating System
• 1920 x 1080 or greater screen resolution
• 500 GB or larger SSD
• Minimum 8 GB of RAM (12GB -16GB RAM recommended)
• Access to High Speed Internet
 METHODOLOGY
Number 0 represents a starting point in a graph, or in other words, a depot in a real
life. Clients or delivery points are assigned an integer number from 1 to n, where n is the number

—Cars in the fleet are assigned to the numbers from n + 1 to m

of deliveries to be performed. −
1.
Obviously the quantity of the vehicles in a fleet is equal to m n, but one truck is always skipped.
Given all of the above, the proper solution can be constructed in modular manner. A string of
integers is built with as many blocks as there are vehicles performing the task. The basic structure
of a single module consists of an integer assigned to the vehicle and two zeroes, as each routes
starts and ends in the depot. Each customer’s number that is being serviced by that vehicle is
placed in between the zeroes, in order of the delivery. All modules are put together to create a
final solution representation. Zeroes can be removed to increase readability. An exception exists,
as the first module in the whole representation does not need to have a vehicle representing an
integer in the first position. After that operation, if two integers representing vehicles are adjacent
to each other, or a string ends with such an integer, that means that not all vehicles take part in the
solution, and can be safely removed too, if all vehicles have the same capacity. Figure 2 shows a
proper way to encode the solution to the VRP with 10 deliveries and 4 trucks.

Selection
Selection is a step where the population part that will be reproduced and alive in next step
is chosen. Generally, the only formal requirement that has to be met is the fact that
the fittest individuals must have a higher probability of being chosen. Some examples
of possible selection methods are [37]:

• Roulette wheel selection (RWS)—chances of an individual being chosen are propor-

tional to its fitness value; thus, selection may be imagined as a spinning roulette,
where each individual takes an amount of space on the roulette wheel according to its
fitness.
• Elitism selection (ES)—a certain percentage of the population, ordered by fitness, is
always transferred to the next population. In that scenario, the algorithm makes sure that
best so far known solutions would not be lost in the process of selection.
• Rank selection (RS)—similar to RWS, but each individual solution’s space on the
roulette wheel is not proportional to its fitness, but to its rank in the list of all individ-
uals, ordered by fitness.
• Stochastic universal sampling selection (SUSS)—instead of spinning the wheel of the
roulette for a certain amount of times, spin it once. If selecting n individuals, there
must exist n spaces on the wheel, and the chosen individual is copied n times to the
next generation.
• Tournament selection (TS)—as many times as required, choose two individuals ran-
domly, and let the more fit one be chosen.
 Crossover Operators
With the change in chromosome representation, all genetic operators must be adjusted accordingly. Firstly,
simple crossover operators that incorporate swapping parts of two parent chromosomes to produce offspring
no longer suffice for the needs of the new representation [4]. Figure 3 shows the problem.

Swapping parts of a chromosome can introduce unwanted pathology in the form of doubling
delivery points or trucks. Such a solution can be automatically marked as invalid. There exist many different
solutions to that problem, but this paper only focus on the simple solution derived from crossover operators for
TSP, as VRP is nothing else than generalized version of a problem described in the literature as the traveling
salesman problem.

Order Crossover
One of the most simple, yet effective ideas for TSP crossover is order crossover, and its variation for the VRP
is presented in Figure. To perform order crossover, certain actions have to be taken:

1. Label parents randomly as male and female.

2. Take both parents and randomly choose two crossover points, the same for both of them.
3. Copy the integers in between the crossover points, from male parent to child, keeping them at the same
positions.
4. Take the female parent, and starting from the gene after the second crossover point, iterate through all
genes. If the end is met, start from the beginning.
5. Take the child and starting from the gene after the second crossover point, copy the female parent gene
that is considered in the current iteration, only if it is not present yet in the child’s chromosome. If the
end is met, start from the beginning.
6. The operation is finished if all empty spaces in the child chromosome are filled.
7. Optionally, swap the roles of female and male parents, and repeat the whole process to produce a second
 offspring.
Such a simple technique enables creation of valid chromosomes for the next popula- tion, where the order
of the parent’s vertices is preserved .

Partially Mapped Crossover

Start the same as order crossover, with choosing two crossing points and copying part of the first parent to
the new child.

Then, to preserve as much order as possible from the second parent, integers that are not included in the part
copied from first parent are inherited from second one, together with their positions.
 Edge Recombination Crossover

This is based on the idea of randomly inheriting as many parent’s edges as possible,
promoting edges that are common for both parents, by introducing the idea of neighbor- hood. For each
integer in the representation, a neighborhood vector can be created, by choosing vertices that are adjacent to
this integer in both parents’ representations.

Cycle Crossover

Cycle crossover performs two operations for copying a single element. First, the
ele- ment itself is chosen from one parent, then the element’s position in the child is determined by the
element’s position in the other parent. One parent is always used to determine the choice of elements,
and the other one is always responsible for position choices. Let us assume parents p1 and p2. The
process starts with copying the first element from p1 to the first position of the child, then, a loop
starts. In the loop, from p2, the first integer is nominated, but it is copied to the child in the fourth
position, as this is the position it takes in p1. Then, in p2, integer 8 is nominated, as it lies in position
four, but it is copied to the child in position eight, as in p1,

Mutation Operator Changes in Regard to Integer Solution Representation

Mutation operators do not need to be completely reinvented. Swap mutation is still valid, but
instead of swapping two bits, two integer values are swapped in the entire solution. It does not matter what
these values represented, it is safe to mutate by swapping location and vehicle integers. The negation mutator
can be replaced by a very similar remove-and-reinsert operation, as shown in Figure.
 The idea behind this kind of mutation is simple. Take a vertex at a certain posi- tion,
reduce its representation size, and randomly place it in another spot, restoring the original size.

It is worth noting at this point that it is believed that simple mutation operators should act as a
secondary entropy source in the algorithm and not provide as many perturbations to produce competitive
results as compared to other techniques. Based on that fact, hybrid genetic algorithms have been designed
that incorporate local search methods that act as mutation operators
 CODING AND IMPLEMENTATION
# encoding: utf-8
import sys
import random
import math

vrp = {}

## First reading the VRP from the input ##

def readinput():
try:
line = raw_input().strip()
while line == '' or [Link]('#'):
line = raw_input().strip()
return line
except EOFError:
return None

line = readinput()
if line == None:
print >> [Link], 'Empty input!'
exit(1)

if [Link]() != 'params:':
print >> [Link], 'Invalid input: it must be the VRP initial params at first!'
exit(1)

line = readinput()
if line == None:
print >> [Link], 'Invalid input: missing VRP inital params and nodes!'
exit(1)
while [Link]() != 'nodes:':
inputs = [Link]()
if len(inputs) < 2:
print >> [Link], 'Invalid input: too few arguments for a param!'
exit(1)
if inputs[0].lower() == 'capacity':
vrp['capacity'] = float(inputs[1])
# Validating positive non-zero capacity
if vrp['capacity'] <= 0:
19
 print >> [Link], 'Invalid input: capacity must be neither negative nor
zero!'
exit(1)
else:
print >> [Link], 'Invalid input: invalid VRP initial param!'
exit(1)
line = readinput()
if line == None:
print >> [Link], 'Invalid input: missing nodes!'
exit(1)

if not set(vrp).issuperset({'capacity'}):
print >> [Link], 'Invalid input: missing some required VRP initial params!'
exit(1)

line = readinput()
vrp['nodes'] = [{'label' : 'depot', 'demand' : 0, 'posX' : 0, 'posY' : 0}]
while line != None:
inputs = [Link]()
if len(inputs) < 4:
print >> [Link], 'Invalid input: too few arguments for a node!'
exit(1)
node = {'label' : inputs[0], 'demand' : float(inputs[1]), 'posX' : float(inputs[2]), 'posY' :
float(inputs[3])}
# Validating demand neither negative nor zero
if node['demand'] <= 0:
print >> [Link], 'Invalid input: the demand if the node %s is negative or zero!'
% node['label']
exit(1)
# Validating demand not greater than capacity
if node['demand'] > vrp['capacity']:
print >> [Link], 'Invalid input: the demand of the node %s is greater than the
vehicle capacity!' % node['label']
exit(1)
vrp['nodes'].append(node)
line = readinput()

# Validating no such nodes

if len(vrp['nodes']) == 0:
print >> [Link], 'Invalid input: no such nodes!'
exit(1)

## After inputting and validating it, now computing the algorithm ##

20
def distance(n1, n2):
dx = n2['posX'] - n1['posX']
dy = n2['posY'] - n1['posY']
return [Link](dx * dx + dy * dy)

def fitness(p):
# The first distance is from depot to the first node of the first route
s = distance(vrp['nodes'][0], vrp['nodes'][p[0]])
# Then calculating the distances between the nodes
for i in range(len(p) - 1):
prev = vrp['nodes'][p[i]]
next = vrp['nodes'][p[i + 1]]
s += distance(prev, next)
# The last distance is from the last node of the last route to the depot
s += distance(vrp['nodes'][p[len(p) - 1]], vrp['nodes'][0])
return s

def adjust(p):
# Adjust repeated
repeated = True
while repeated:
repeated = False
for i1 in range(len(p)):
for i2 in range(i1):
if p[i1] == p[i2]:
haveAll = True
for nodeId in range(len(vrp['nodes'])):
if nodeId not in p:
p[i1] = nodeId
haveAll = False
break
if haveAll:
del p[i1]
repeated = True
if repeated: break
if repeated: break
# Adjust capacity exceed
i=0
s = 0.0
cap = vrp['capacity']
while i < len(p):
s += vrp['nodes'][p[i]]['demand']
21
 if s > cap:
[Link](i, 0)
s = 0.0
i += 1
i = len(p) - 2
# Adjust two consective depots
while i >= 0:
if p[i] == 0 and p[i + 1] == 0:
del p[i]
i -= 1

popsize = int([Link][1])
iterations = int([Link][2])

pop = []

# Generating random initial population

for i in range(popsize):
p = range(1, len(vrp['nodes']))
[Link](p)
[Link](p)
for p in pop:
adjust(p)

# Running the genetic algorithm

for i in range(iterations):
nextPop = []
# Each one of this iteration will generate two descendants individuals. Therefore, to
guarantee same population size, this will iterate half population size times
for j in range(int(len(pop) / 2)):
# Selecting randomly 4 individuals to select 2 parents by a binary tournament
parentIds = set()
while len(parentIds) < 4:
parentIds |= {[Link](0, len(pop) - 1)}
parentIds = list(parentIds)
# Selecting 2 parents with the binary tournament
parent1 = pop[parentIds[0]] if fitness(pop[parentIds[0]]) <
fitness(pop[parentIds[1]]) else pop[parentIds[1]]
parent2 = pop[parentIds[2]] if fitness(pop[parentIds[2]]) <
fitness(pop[parentIds[3]]) else pop[parentIds[3]]
# Selecting two random cutting points for crossover, with the same points
(indexes) for both parents, based on the shortest parent

22
 cutIdx1, cutIdx2 = [Link](1, min(len(parent1), len(parent2)) - 1),
[Link](1, min(len(parent1), len(parent2)) - 1)
cutIdx1, cutIdx2 = min(cutIdx1, cutIdx2), max(cutIdx1, cutIdx2)
# Doing crossover and generating two children
child1 = parent1[:cutIdx1] + parent2[cutIdx1:cutIdx2] + parent1[cutIdx2:]
child2 = parent2[:cutIdx1] + parent1[cutIdx1:cutIdx2] + parent2[cutIdx2:]
nextPop += [child1, child2]
# Doing mutation: swapping two positions in one of the individuals, with 1:15
probability
if [Link](1, 15) == 1:
ptomutate = nextPop[[Link](0, len(nextPop) - 1)]
i1 = [Link](0, len(ptomutate) - 1)
i2 = [Link](0, len(ptomutate) - 1)
ptomutate[i1], ptomutate[i2] = ptomutate[i2], ptomutate[i1]
# Adjusting individuals
for p in nextPop:
adjust(p)
# Updating population generation
pop = nextPop

# Selecting the best individual, which is the final solution

better = None
bf = float('inf')
for p in pop:
f = fitness(p)
if f < bf:
bf = f
better = p

## After processing the algorithm, now outputting it ##

# Printing the solution

print ' route:'
print 'depot'
for nodeIdx in better:
print vrp['nodes'][nodeIdx]['label']
print 'depot'
print ' cost:'
print '%f' % bf

23
RESULT ANALYSIS

24
 CONCLUSION

The genetic algorithm seemed to be a good choice for solving the vehicle
routing problem. The results revealed that GA converged to the global optimum quickly, which
reduced the cost of computation. It was noted that selection operators, searching operators,
along with chromosome representation had an impact in finding the global solution without
getting trapped at a local optimum. The results revealed that a large domination of either of the
genetic operators was not positive for the final results. In general, for the VRP and possibly
other problems that revolve around finding paths in large graphs, operators that pay attention
to whole edges rather than single vertexes are far more superior. It was noted that GA is capable
of finding good results for large examples of the VRP. However, instances based on real life
problems tended to be less trivial than randomly generated ones, and for them, the GA needs
to be altered or modified to provide competitive solutions.

Without any modifications to the implementation, experiments could be run

multiple times again, possibly for extended amounts of iterations. Promising results from
executed runs are an indicator that more close to optimal or even better solutions can be
possibly found. However, this task revolves around luck, as the function of best fitted individual
through generations flattens dramatically.

The fitness function and instances representation could be altered to enable capability
of testing examples that are not only based on euclidean two-dimensional space but also,
for example, on explicit graph representation with weights. With costs of journey from one
point to another, additional crossover operators from group of heuristic crossovers could
be implemented and used. The fitness function and genetic operators could be modified to
enable testing of other vehicle routing problem variants such as ones with time windows
or split delivery.

25
 FUTURE ENHANCEMENT
GAs have been applied in different fields by modifying the basic structure of GA. The
optimality of a solution obtained from GA can be made better by overcoming the current
challenges. Some future possibilities for GA are as follows:

1. There should be some way to choose the appropriate degree of crossover and mutation
operators. For example Self-Organizing GA adapt the crossover and mutation operators
according to the given problem. It can save computation time that make it faster.
2. Future work can also be considered for reducing premature convergence problem. Some
researchers are working in this direction. However, it is suggested that new methods of
crossover and mutation techniques are required to tackle the premature convergence problem.
3. Genetic algorithms mimic the natural evolution process. There can be a possible scope for
simulating the natural evolution process such as the responses of human immune system and
the mutations in viruses.
4. In real-life problems, the mapping from genotype to phenotype is complex. In this situation,
the problem has no obvious building blocks or building blocks are not adjacent groups of
genes. Hence, there is a possibility to develop novel encoding schemes to different problems
that does not exhibit same degree of difficulty.
5. Genetic algorithms have survived for 40+ years already, and they are still go-to algorithms in
engineering and optimization problems in which computational time isn't a big issue.
6. Genetic algorithms provide global solutions to optimization problems, which aren't easy to
come by in the slew of optimization algorithms.
7. New developments and extensions of genetic algorithms (such as quantum-inspired genetic
algorithms, or QIGA) are gaining ground these days, and I'd assume that they will continue
to be refined and explored to improve compute times and accuracy.
8. QIGA is an interesting avenue of research, and I think this approach has potential to solve
some of the downsides of genetic algorithms.
9. Bottom line, genetic algorithms and their extended cousins (like QIGA) are going to play an
important role in optimization for years to come.

26
 BIBLIOGRAPHY
• R. Bent and P. Van Hentenryck. A two stage hybrid local search for the vehicle routing problem
with time windows. In Transportation Science, volume 38, pages 515–530, 2004.
• O. Braysy and M. Gendreau. Vehicle routing problem with time windows, part i:Route
construction and local search algorithms. Transportation Science, 39(1):104–118, 2005.
• K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A Fast and Elitist Multiobjective Genetic
Algorithm: NSGA–II. IEEE Transactions on Evolutionary Computation,6(2):182– 197, April
2002.
• [Link] and [Link]. Exploiting the Trade-Off—The Benefits of Multiple Objectives in Data
Clustering. In Evolutionary Multi-Criterion Optimization. Third International Conference, EMO
2005, pages 547–560, 2005.
• [Link]. Multi-Objective Optimization using Evolutionary Algorithms. Chichester, UK:Wiley,
2001. Vehicle Routing Problem 124
• [Link], R.F. Hartl, and M. Lucka. A parallel version of the d-ant algorithm for the vehicle
routing problem. In Theory an Applications, pages 109–118, 2005.
• D. Knowles, A. Watson, and W. Corne. Reducing local optima in single-objective problems by
multi-objectivization. In Evolutionary Multi-Criterion Optimization. First International
Conference, EMO 2001, pages 268–282, 2001.
• W. P. Nanry and J. W. Barnes. Solving the pickup and delivery problem with time windows
using reactive tabu search. Transportation Research Part B, 34:107–121,2000.
• [Link], [Link], and [Link]. Parallel and Hybrid Models for Multiobjective
Optimization: Application to the Vehicle Routing Problem. In Parallel Problem Solving from
Nature—PPSN VII, pages 271–280, 2002.
• J.Y. Potvin and S. Bengio. The vehicle routing problem with time windows - partII: Genetic
search. In INFORMS Journal on Computing, volume 8, pages 165–172,1996.
• S. Watanabe and K. Sakakibara. Multi-objective approaches in a single-objective optimization
environment, 2005 IEEE Congress on Evolutionary Computation (CEC2005),pp.1714-1721,
2005

27