A deviant position detector that determines whether or not a vehicle deviated from a set route, detects route deviation information such as a route deviated position when a vehicle deviated, and stores it as past route deviation information in a route deviant position memory. A route searching device searches a route to a destination based on information obtained by a position detector and a map information acquiring device, and further searches past route deviation information obtained from the route deviant position memory. A route guidance changing device determines whichever route guidance method is the best based on information obtained by the route searching device and from the route deviant position memory, and instructs a route guidance outputting device to output the best route guidance method.