Dynamic route planning for car navigation systems using virus genetic algorithms

Article type: Research Article

Authors: Kanoh, Hitoshi

Affiliations: Department of Computer Science, Graduate School of Systems and Information Engineering, University of Tsukuba, Tsukuba, Ibaraki, 305-8573, Japan. Tel.: +81 298 53 5344; Fax: +81 298 53 5206; E-mail: kanoh@cs.tsukuba.ac.jp

Abstract: This paper describes a practical dynamic route planning method using real road maps in a wide area. The maps include traffic signals, road classes, and the number of lanes. The proposed solution is using a genetic algorithm adopting viral infection. The method is to use viruses as domain specific knowledge. A part of an arterial road is regarded as a virus. A population of viruses is generated in addition to a population of routes. Crossover and infection determine the near-optimal combination of viruses. When traffic congestion frequently changes during driving, an alternative route can be selected using viruses and other routes in the population in a real time. Experiments in dynamic environments using a real road map with 28000 cars show that the proposed method is superior to the Dijkstra algorithm for use in practical car navigation devices.

Keywords: Intelligent transportation systems, navigation, genetic algorithms, cellular automata

DOI: 10.3233/KES-2007-11105

Journal: International Journal of Knowledge-based and Intelligent Engineering Systems, vol. 11, no. 1, pp. 65-78, 2007