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

• US 20100262359A1
• Filed: 04/14/2009
• Published: 10/14/2010
• 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
• Granted Patent: US 8,150,620 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• 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 for a navigation system utilizing XML map data, comprising the following steps of:

establishing boundary nodes on boundaries of administrative regions represented by the XML map data having a layered structure;

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;

creating cost information on physical links on the base layer of the layered structure of the XML map data;

searching routes between a start point and boundary nodes of an administrative region to which the start point belongs and searching routes between a destination point 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 map data by evaluating the cost information on the virtual links;

detecting candidate total routes between the start point and destination by connecting the candidate virtual links and the routes between the start point and the destination 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.

2. A method of searching a route as defined in claim 1, further comprising 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 cost information is computed based on a distance, a travel time, and predetermined cost space factors for each virtual link and physical link where the cost information on the virtual links on a particular layer is established on a layer of the map data that is immediately higher than the particular layer and stored in a form of cost tables.

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

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

6. A method of searching a route as defined in claim 4, 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.

7. A method of searching a route as defined in claim 4, 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.

8. A method of searching a route as defined in claim 3, 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.

9. A method of searching a route as defined in claim 8, 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.

10. A method of searching a route as defined in claim 9, 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.

11. An apparatus for searching a route between a start point to a destination for a navigation system utilizing XML map data, comprising:

means for establishing boundary nodes on boundaries of administrative regions represented by the XML map data having a layered structure;

means for 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;

means for creating cost information on physical links on the base layer of the layered structure of the XML map data;

means for searching routes between a start point and boundary nodes of an administrative region to which the start point belongs and searching routes between a destination point and boundary nodes of an administrative region to which the destination point belongs;

means for selecting candidate virtual links that connect the boundary nodes of different administrative regions on a particular layer of the map data by evaluating the cost information on the virtual links;

means for detecting candidate total routes between the start point and destination by connecting the candidate virtual links and the routes between the start point and the destination to the boundary nodes of the corresponding administrative regions; and

means for 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.

12. An apparatus for searching a route as defined in claim 11, further comprising means for 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. An apparatus for searching a route 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 where the cost information on the virtual links on a particular layer is established on a layer of the map data that is immediately higher than the particular layer and stored in a form of cost tables.

14. An apparatus for searching a route 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.

15. An apparatus for searching a route 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.

16. An apparatus for searching a route as defined in claim 14, 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.

17. An apparatus for searching a route as defined in claim 14, 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.

18. An apparatus for searching a route as defined in claim 13, 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.

19. An apparatus for searching a route as defined in claim 18, 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.

20. An apparatus for searching a route as defined in claim 19, 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.