ABSTRACT

Vehicle routing involves searching for efficient routes for vehicles along transportation networks in an attempt to reduce travel time, route length, service cost. For vehicle drivers, the idea of getting to their destination in the shortest time possible is very appealing especially by taking the shortest path to their destination but the shortest route may not always be the optimal route. Drivers might need multiple and distinct good (near optimal routes) options which are based on multiple criteria that can make the search space too large to get the solution in real time by detenninistic algorithms. This project proposes a genetic based algorithm that combines the flexibility (producing more than one solution) of genetic algorithm and the speed of Dijkstra algorithm. This algorithm uses genetic operators including selection, crossover and incorporates Dijkstra algorithm mutation to produce optimal solutions. The processes involved include converting an actual road map into weighted graph, get origin and destination nodes, initialize the population, continue to perfonn genetic operation until the termination criteria is met and return best solutions. The termination criteria is implemented as the number of times the proposed algorithm performs genetic operation before returning the solutions found, at each iteration mutation and crossover operation will be performed. The developed system was evaluated using processing time and distance. Genetic-Dijkstra algorithm has an average processing time of 5.83 seconds and average distance of 2059.09 meters compared to Genetic algorithm with processing time of 6.89 seconds and average distance of 2364.65 meters. The result gotten shows that the developed system is efficient and can be implemented in any other routing application.