Patent ID: 8219313

Claim:
A navigation device that searches for a route from a departure point to a destination, comprising: an information storage unit that stores map data in a hierarchical structure, the hierarchical structure being defined such that: a lowest level of the hierarchical structure includes the map data for all roads, including local roads, a highest level of the hierarchical structure includes the map data for only major roads, and one or more middle levels of the hierarchical structure includes the map data for the major roads and the map data for one or more categories intermediate roads, but not the map data for the local roads, map data being excluded from at least one of the defined middle levels of the hierarchical structure in order to reduce the overall size of the map data stored in the information storage unit; and a controller that: reads the map data from the information storage unit; performs a route search within a predetermined area of each level of the hierarchical structure that includes map data and acquires a shortest cost route; the predetermined area within each hierarchical level having map data that exists immediately below a hierarchical level having no map data being expanded into an expanded search area having a size equal to a predetermined area that would have been searched in the hierarchical level having no map data if it had had map data; performs a route search in the expanded search area to acquire a first route; performs a route search in a hierarchy level higher than the hierarchy level including the first route to acquire a second route; determines whether the first route or the second route has a smaller cost; and identifies the one of the first route and the second route having the smallest cost as a shortest cost route.