Conventionally, there has been a learning route-search device that stores therein, as deviation sections, actual traveling routes deviated from optimum routes, and performs route search by substituting, with any one of the deviation sections, a route found by the device if a starting point and an ending point of this deviation section are included in the found route. Such a device substitutes a route with a corresponding one of the deviation sections without exception, and therefore, may sometimes find a circuitous route that is not desired by a user. Provided is a technology by which learned routes are applied in a more appropriate manner in accordance with routes to be found. A route search device is provided with a deviation determining unit adapted to determine whether or not a route deviated from a route found by a route search unit has been taken in travelling. If a route deviated from the route has been taken in travelling, the route search device stores, in association with one another, a road link relating to a position at which the deviated route has started, a road link relating to a position at which retaking of the found route has started, and the deviated route taken in the travelling. The route search device then substitutes at least a part of the foregoing found route with the thus stored route.