To solve the problem that a conventional learned route search device, searching for a route by storing an actually traveled route deviated from the optimum route, as a deviated section and by replacing a searched route with the deviated section, when the start point and the end point of the deviated section are included in the searched route, may cause a roundabout route which is not desired by a user to be searched, because such a device uniformly replaces it with the deviated section, and to provide a technique applying the learned route more properly, according to the searched route.

The route search device includes a deviation determination means determining whether the travel is deviated from a route searched by a route search means; when the travel is deviated from the route, a road link related to the position from which it is deviated, a road link related to the position at which it is returned to the route, and a traveled route deviated therefrom are stored in association with each other; and at least a part of the searched route is replaced with the stored route.