Date of Award

7-1-2006

Thesis Type

masters

Document Type

Thesis

Divisions

fsktm

Department

Faculty of Computer Sciences & Information Technology

Institution

University of Malaya

Abstract

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.

Note

Dissertation (M.A.) – Faculty of Computer Sciences & Information Technology, University of Malaya, 2006.

Download

Share

COinS