Route guidance with unspecified staging posts using genetic algorithm for car navigation systems

This paper addresses the problem of selecting a route to a given destination that traverses several nonspecific sites (e.g. 'a bank') as requested by a driver. The proposed solution uses a genetic algorithm that includes viral infection. A road that includes a site is regarded as a virus. An infection occurs between two points common to a candidate route and the virus, and involves the substitution of the intersections carried by the virus for those on the existing candidate route. Crossover and infection determine the easiest-to-drive and quasi-shortest route through the objective landmarks. Experiments using actual road maps show that this infection-based mechanism is an effective way of solving the problem.