Dynamic route planning for car navigation systems using virus genetic algorithms

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.