Patent ID: 8175801

Claim:
A computer implemented method of searching a route between a start point to a destination for a navigation system, comprising the following steps of: executing, by a processor, a predetermined route search algorithm on map data having a layered structure for a predetermined direction between the start point and the destination for each predetermined search range; retrieving candidate links from the map data stored in a computer-readable medium for creating a route between the start point and the destination and temporarily storing the candidate links in a computer-readable data storage; applying, by the processor executing a program, climbing criteria that determine whether there is a climbing-up node between a lower layer and a higher layer within the predetermined search range, and promotion criteria that determine whether there is a higher layer link corresponding to the candidate links retrieved from the data storage to find whether there is a link in the lower layer of the map data to be promoted to a corresponding link in a the higher layer of the map data; storing, in the computer-readable medium, data related to the links in the lower layer and the higher layer that have satisfied the climbing criteria and the promotion criteria; and building a path between the destination and the start point by processing, by the processor executing a program, the data related to the links that have satisfied the criteria in a direction opposite to the predetermined direction executed for the route search algorithm.