Vehicle routing problem using genetic algorithm / Shamini Nagaratnam
This dissertation studies and explores the potential of using Genetic Algorithms to find the shortest path in Vehicle Routing Problem. Routes for vehicles with known location from source to destination are designed where the total distance or time traveled is minimized. Although genetic algorithm...
Saved in:
| Main Author: | |
|---|---|
| Format: | Thesis |
| Published: |
2006
|
| Subjects: | |
| Online Access: | http://studentsrepo.um.edu.my/8079/2/cover_I_II_III.pdf http://studentsrepo.um.edu.my/8079/11/Thesis_Examiner_Ver6_06072006_10July.pdf http://studentsrepo.um.edu.my/8079/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Universiti Malaya |
| Summary: | This dissertation studies and explores the potential of using Genetic Algorithms to find
the shortest path in Vehicle Routing Problem. Routes for vehicles with known location
from source to destination are designed where the total distance or time traveled is
minimized. Although genetic algorithms have been used to solve the Vehicle Routing
Problem this research aims to create different a way of chromosome representation and
introduction of overlapping rate to determine the number of chromosome sent for crossover
and mutation. Fixed length chromosomes and their genes have been used for
encoding this problem. The proposed method uses proportional selection with two fixed
point crossover and random mutation. and discards the infeasible chromosomes by giving
high penalty values to the fitness function. The chosen method for crossover and
mutation together is shown to improve the rate of convergence as compared to the
Djikstra’s algorithm. Experimental results show that Genetic Algorithm is able to find a
near optimal solution for the sample data in our study.
|
|---|