MMRL Publication List
Genetic Algorithm Based Route Planner for Large Urban Street Networks
Suranga Chandima Nanayakkara, Dipti Srinivasan, Mu Jun, Elizabeth Taylor, Ong Sim Heng
IEEE Congress on Evolutionary Computation (CEC), September 25-28, 2007
Abstract
Finding the shortest path from a given source to a given destination is a well known and widely applicable problem. However, most published work uses static route planning algorithms such as A*, Dijkstra’s, Bellman-Ford algorithm etc. These algorithms are not capable of dealing with dynamic information and congestion in, for example, city roads, and they do not offer many choices to the users. We believe that the Genetic Algorithm (GA) based route planning algorithm proposed in this paper it has the ability to tackle these two 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 and Dijkstra’s algorithm. Simulation results demonstrate the effectiveness of the proposed algorithm over other algorithms. Moreover, the proposed GA may be used as a basis for developing an intelligent route planning system.