Patent ID: 8150620

Claim:
A method of searching a route between a start point to a destination point for a navigation system utilizing XML map data, comprising the following steps of: evaluating the XML map data stored in a data storage device and establishing boundary nodes on boundaries of administrative regions represented by the XML map data, said administrative regions are arranged by a layered structure in the XML map data; creating cost information on virtual links that connect the boundary nodes on the administrative regions on layers higher than a base layer in the layered structure of the XML map data and storing the cost information on the virtual links in the data storage device; creating cost information on physical links on the base layer of the layered structure of the XML map data and storing the cost information on the physical links in the data storage device; searching routes, under control of a processor of the navigation system, by evaluating the XML map data with the cost information, between a start point and boundary nodes of an administrative region to which the start point belongs and searching routes between a destination point set to the navigation system via an input device and boundary nodes of an administrative region to which the destination point belongs; selecting candidate virtual links that connect the boundary nodes of different administrative regions on a particular layer of the XML map data by evaluating the cost information on the virtual links under the control of the processor of the navigation system; detecting candidate total routes between the start point and the destination point, under the control of the processor of the navigation system, by connecting the candidate virtual links and the routes between the start point and the destination point to the boundary nodes of the corresponding administrative regions; and applying physical links in the base layer of the map data to the candidate total routes, under the control of the processor of the navigation system, for further evaluating costs of the total routes to select the most cost effective total route; wherein the cost information is established on each of said administrative region layer of the XML map data, and the cost information on the virtual links on a particular administrative region layer is included in an administrative region layer of the XML map data that is immediately higher than the particular administrative region layer in a form of cost tables.