Design of a Route Guidance System with Shortest Driving Time Based on Genetic Algorithm

摘要

Nowadays, with the advancement of the technology on mobile devices, route guidance systems that assist drivers on the traffic have become widespread in daily life. For an accurate routing, a route guidance system should consider the effectual factors of traffic flow such as density and allowable velocity limits of the roads. With the increase of effectual factors and amount of nodes in road network, the computational cost increases. It is not proper to find exact optimal solution in real time for the road networks with excessive number of nodes using some well known deterministic methods such as Dijkstra's algorithm on navigation systems using mobile devices with limited processing speed and memory capacity. This paper proposes a route guidance system and a Genetic Algorithm (GA) approach applied on this routing system to find the shortest driving time. Excluding classical methods, a gene search method of chromosomes named "first-matched-genes" on crossover operation had been introduced. The efficiency of the genetic algorithm was tested by applying on the networks with different sizes and a mobile application on the traffic network of Ankara was presented.