Integrating Uncomfortable Intersection-Turns to Subjectively Optimal Route Selection Using Genetic Algorithm

Route selection is one of the most important problems for a car navigation system. Given a pair of origin and destination, there are many possible routes. Most current car navigation systems propose the shortest path from the origin to the destination. Selecting the shortest path is not a hard problem, but the shortest path is not always what the user wants; what the user really wants to have is the most comfortable route for him or her to drive. In other words, the driver wants to have a car navigation system to propose the subjectively optimal route for him or her. Finding such a route requires enumerating all the possible routes, and is known as a NP-hard problem. In order to reduce computational complexity, we have employed a GA to find a (subjectively) quasi optimal route for the driver. In this paper, we report our attempt to integrate uncomfortable-turns in to the conditions of our GA-based route selection algorithm. The numerical experiments demonstrate the feasibility of our GA-based route selection method.