Genetic algorithm based route planner for large urban street networks

Abstract

Finding the shortest path from a given source to a given destination is a well known and widely applicable problem. Most of the work done in the area have used static route planning algorithms such as A*, Dijkstra's, BellmanFord algorithm etc. Although these algorithms are said to be optimum, they are not capable of dealing with certain real life scenarios. For example, most of these single objective optimizations fails to find the equally good solutions when there is more than one optimum (shortest distance path, least congested path). We believe that the Genetic Algorithm (GA) based route planning algorithm proposed in this paper has the ability to tackle the above problems. In this paper, the proposed GA based route planning algorithm is successfully tested on the entire Singapore map with more than 10,000 nodes. Performance of the proposed GA is compared with an ant based path planning algorithm. Simulation results demonstrate the effectiveness of the proposed algorithm over ant based algorithm. Moreover, the proposed GA may be used as a basis for developing an intelligent route planning system. © 2007 IEEE.