Vehicle routing problem using genetic algorithm / Shamini Nagaratnam

• Main Author: Shamini , Nagaratnam
• Format: Thesis
• Published: 2006
• Subjects: QA75 Electronic computers. Computer science
• 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/
• Institution: Universiti Malaya

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.