Route search method and apparatus for navigation system utilizing map data of XML format

• US 8,150,620 B2
• Filed: 04/14/2009
• Issued: 04/03/2012
• Est. Priority Date: 04/14/2009
• Status: Active Grant

• Current Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Original Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Inventors: Motoyama, Masaki
• Primary Examiner(s): O'Connor, Gerald J.
• Assistant Examiner(s): Holcomb, Mark
• Application Number:
  US12/386,101
• Publication Number:
  US 20100262359A1
• Time in Patent Office: 1,085 Days
• Field of Search: 701200-202, 701208-209, 701/204, 701/207, 701/211, 701/213, 340/990, 340/995.1
• US Class Current: 701/410
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering

Abstract

A route search method for a navigation system using the XML map data that is layered based on administrative regions improves efficiency and accuracy of finding an optimum route. The method includes the steps of establishing boundary nodes on boundaries of administrative regions, creating cost information on virtual links that connect the boundary nodes on the administrative regions and physical links on a base layer, selecting candidate virtual links regions by evaluating the cost information, detecting candidate total routes between the start point and destination by connecting the candidate virtual links and other routes, and applying physical links in the base layer to the candidate total routes for further evaluating the costs of the total routes to select the most cost effective total route.

Claims

1. 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.

2. A method of searching a route as defined in claim 1, further comprising, under the control of the processor of the navigation system, a step of repeating the step of selecting the candidate virtual links corresponding to a layer of the XML map data different from said particular layer to detect candidate total routes for detecting the candidate total routes.

3. A method of searching a route as defined in claim 1, wherein the boundary nodes on the administrative regions in the XML map data are nodes of physical links establishing roads at the boundaries of the administrative regions.

4. A method of searching a route as defined in claim 1, wherein the cost information is computed based on a distance, a travel time, and predetermined cost space factors for each virtual link and physical link.

5. A method of searching a route as defined in claim 4, wherein said predetermined cost space factors for each virtual link and physical link are numerical values assigned to different attributes that affect the costs where the attributes include a season of a year, a time of a day, a structure of a road, traffic law, and a vehicle type.

6. A method of searching a route as defined in claim 5, wherein said predetermined cost space factors for each virtual link and physical link are numerical values assigned to different attributes that affect the costs where the attributes include traffic conditions and weather condition related to particular links that change dynamically.

7. A method of searching a route as defined in claim 6, wherein the overall cost related to the cost space factors for each virtual link and physical link is determined by averaging the numerical values assigned to different attributes through a root-means-square method.

8. A method of searching a route as defined in claim 1, wherein said administrative regions include cities, counties, states, and countries in the order of lower layer to higher layer in the layered structure of the XML map data.

9. A method of searching a route as defined in claim 8, wherein the layered structure of the XML map data is configured by an international layer for connecting the boundary nodes between two or more countries, a country layer for connecting the boundary nodes between two or more states within the country, a state layer for connecting the boundary nodes between two or more counties within the state, a county layer for connecting the boundary nodes between two or more cities within the county, and a city layer which is the base layer with the physical links.

10. A method of searching a route as defined in claim 8, wherein the layered structure of the XML map data is configured by a freeway backbone layer having physical links and nodes for connecting the freeway to nodes on other layers, a country layer for connecting the boundary nodes between two or more states within the country, a state layer for connecting the boundary nodes between two or more counties within the state, a county layer for connecting the boundary nodes between two or more cities within the county, and a city layer which is the base layer with the physical links.

11. A navigation system for searching a route between a start point to a destination point utilizing XML map data and guiding a user to the destination point via the searched route, comprising:

a data storage device which stores the XML map data related to determining a preferable route between a start point and a destination point;

an input device for selecting operational menus of the navigation system and specifying a destination point for a route guidance operation to the destination point;

a processor for controlling overall operations of the navigation system in a route search process and a route guidance process;

wherein the processor controls the following operations of the navigation system;

evaluating the XML map data stored in the 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 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;

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 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 the 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 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.

12. A navigation system as defined in claim 11, wherein said processor further controls an operation of repeating the function of selecting the candidate virtual links corresponding to a layer of the XML map data different from said particular layer to detect candidate total routes for detecting the candidate total routes.

13. A navigation system as defined in claim 11, wherein the boundary nodes on the administrative regions in the XML map data are nodes of physical links establishing roads at the boundaries of the administrative regions.

14. A navigation system as defined in claim 11, wherein the cost information is computed based on a distance, a travel time, and predetermined cost space factors for each virtual link and physical link.

15. A navigation system as defined in claim 14, wherein said predetermined cost space factors for each virtual link and physical link are numerical values assigned to different attributes that affect the costs where the attributes include a season of a year, a time of a day, a structure of a road, traffic law, and a vehicle type.

16. A navigation system as defined in claim 15, wherein said predetermined cost space factors for each virtual link and physical link are numerical values assigned to different attributes that affect the costs where the attributes include traffic conditions and weather condition related to particular links that change dynamically.

17. A navigation system as defined in claim 16, wherein the overall cost related to the cost space factors for each virtual link and physical link is determined by averaging the numerical values assigned to different attributes through a root-means-square method.

18. A navigation system as defined in claim 11, wherein said administrative regions include cities, counties, states, and countries in the order of lower layer to higher layer in the layered structure of the XML map data.

19. A navigation system as defined in claim 18, wherein the layered structure of the XML map data is configured by an international layer for connecting the boundary nodes between two or more countries, a country layer for connecting the boundary nodes between two or more states within the country, a state layer for connecting the boundary nodes between two or more counties within the state, a county layer for connecting the boundary nodes between two or more cities within the county, and a city layer which is the base layer with the physical links.

20. A navigation system as defined in claim 18, wherein the layered structure of the XML map data is configured by a freeway backbone layer having physical links and nodes for connecting the freeway to nodes on other layers, a country layer for connecting the boundary nodes between two or more states within the country, a state layer for connecting the boundary nodes between two or more counties within the state, a county layer for connecting the boundary nodes between two or more cities within the county, and a city layer which is the base layer with the physical links.