Patent ID: 7623963

Claim:
A navigation device provided in a vehicle, the navigation device comprising: a position detector for detecting a current position of the vehicle; a map data storing unit for storing road map data indicating a road using links; a setting unit for setting a starting position and a destination; a route retrieving unit for giving a cost to each of links included in routes from the starting position to the destination to obtain a total cost of costs of links included in each of the routes from the starting position to the destination and retrieving a route whose total cost is minimum among the routes from the starting position to the destination; a guiding unit for guiding the vehicle to the destination along the retrieved route; a determining unit for determining based on the current position whether the vehicle travels the retrieved route; a deviation route storing unit for storing (i) a deviation route that the vehicle travels after deviating from the retrieved route, (ii) a deviating position at which the vehicle deviates from the retrieved route to the deviation route and (iii) a returning position at which the vehicle comes back from the deviation route to the retrieved route, when the vehicle is determined to travel the deviation route; a comparing unit for extracting a route included in the retrieved route from the deviating position to the returning position and comparing a cost of the extracted route and a cost of the deviation route; and a detour coefficient assigning unit for assigning a detour coefficient to each of links included in the extracted route when the cost of the deviation route is larger than the cost of the extracted route, the detour coefficient indicating that the vehicle detoured around the links included in the extracted route, wherein the route retrieving unit increases a cost of a link to which the detour coefficient is assigned when retrieving a route.