When a vehicle deviates from an initial route, a deviation route is memorized. Thereafter, when the vehicle comes back to the initial route, a cost is compared between the deviation route and a non-traveled route included in the initial route. When the cost of the deviation route is larger, the non-traveled route is supposed to be impassable due to road traffic closure or the like and then a detour coefficient is assigned to links included in the non-traveled route. When a route retrieval is conducted next, a cost of a link to which the detour coefficient is assigned is increased based on the detour coefficient. The detour coefficient is increased depending on a frequency of detouring.