Navigation device

A navigation device comprising:

• an input device;
• a computer processor;
• and
• a memory on which are stored instructions which, when executed, causes said computer processor to perform a process comprising:
• setting a destination based on input received from the input device,
• detecting a current position of a vehicle based on a received GPS signal,
• acquiring map data including road data in which a High Occupancy Vehicle (HOV) lane and a non-HOV lane are shown by a link, and
• searching for a route leading from said current position to said destination by using said map data, and
• causing data indicating a route that guides said vehicle from said current position to said destination to be outputted to a user, wherein
• said route searching is performed by:
• initially searching only for a route leading from said current position to said destination and not using any HOV lane, thereby obtaining an initial route, and, after obtaining said initial route,
• determining whether said initial route includes a highway, and
• only when said initial route is determined to include a highway, conducting a re-search only in the highway on said initial route to obtain a finalized route on a basis of whether an HOV lane on the highway is usable or unusable on the basis of at least one of the following criteria:
• a distance required to make a lane change into the HOV lane on the highway, a search mode inputted from the input device, and a traffic condition of the highway, and
• said finalized route enters and exits said highway at same places, respectively, as said initial route, wherein said initial route or said finalized route is displayed by a display device.