Link promotion method and apparatus for improving route search performance for navigation system

• US 20100222995A1
• Filed: 02/28/2009
• Published: 09/02/2010
• Est. Priority Date: 02/28/2009
• Status: Active Grant

• Current Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Original Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Inventors: Zhao, Lei, Patel, Ashish, Orlov, Serge, Ren, Luoyi, Bhatia, Ankur, Vu, Tien, Tu, Ihung
• Granted Patent: US 8,175,801 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

Abstract

A method and apparatus for link promotion for a navigation system allows expansion of search in a lower layer to determine an optimum climbing point to an upper layer to search an optimum route. The link promotion procedure includes the steps of determining whether an upper link exists for a lower link, setting the upper link as a promoted link if such an upper link exists even if a climbing node point does not exist that connect the lower link and the upper link, and comparing a candidate normal route and a promoted route to find an optimum route.

Claims

1. A method of searching a route between a start point to a destination for a navigation system, comprising the following steps of:

executing 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 for creating a route between the start point and the destination and temporarily storing the candidate links in a data storage;

applying climbing criteria and promotion criteria to the candidate links retrieved from the data storage to find whether there is a link in a lower layer of the map data to be promoted to a corresponding link in a higher layer of the map data;

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

2. A method of searching a route as defined in claim 1, further comprising a step of shifting from the link in the lower layer to the corresponding link in the higher layer even when there is no climbing-up node between the two links when the relationship between the two links have satisfied the promotion criteria.

3. A method of searching a route as defined in claim 1, wherein the step of retrieving the candidate links from the map data includes a step of searching a successor link that is successive to a current link and calculating a cost of each successor link.

4. A method of searching a route as defined in claim 3, wherein the data storage includes an expansion link list for storing the candidate links, an expansion heap for storing the current link as a parent link of the successor link, and a climbing link list for storing the corresponding link in the higher layer as a climbing link when either there is a climbing-up node or the promotion criteria is satisfied, where the link in the lower layer that corresponds to the climbing link is stored in the expansion heap as a parent link of the climbing link.

5. A method of searching a route as defined in claim 1, wherein the step of searching the successor link that is successive to a current link includes a step of obtaining a successor link of lowest cost where the cost is determined by factors including a distance, time, and fees associated with the successor link.

6. A method of calculating a route as defined in claim 4, further comprising a step of deleting the data in the expansion link list every time when all of the candidate links within the predetermined search range have been examined.

7. A method of searching a route as defined in claim 1, wherein the promotion criteria is satisfied when there is a link in the higher layer of the map data that corresponds to a link in the lower layer, and the climbing criteria is satisfied when there is a climbing-up node between the lower layer and the upper layer within the predetermined search range.

8. A method of searching a route as defined in claim 4, wherein the step of building the path between the destination and the start point includes a step of removing copies of series of links in the lower layer from the start point to the parent link and a step of removing the climbing link corresponding to the parent link.

9. A method of searching a route as defined in claim 8, wherein the step of building the path between the destination and the start point further includes a step of merging links that have been remained after the removal of the links, thereby building a route that shifts the different layers of the map data via a climbing-up node.

10. A method of searching a route as defined in claim 1, further comprising a step of evaluating a cost associated with a route involving the links that have satisfied the promotion criteria in comparison with a cost associated with a route without using the link promotion.

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

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

means for retrieving candidate links from the map data for creating a route between the start point and the destination and temporarily storing the candidate links in a data storage;

means for applying climbing criteria and promotion criteria to the candidate links retrieved from the data storage to find whether there is a link in a lower layer of the map data to be promoted to a corresponding link in a higher layer of the map data;

means for storing data related to the links in the lower layer and the higher layer that have satisfied the climbing criteria and the promotion criteria; and

means for building a path between the destination and the start point by processing 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.

12. An apparatus for searching a route as defined in claim 11, further comprising means for shifting from the link in the lower layer to the corresponding link in the higher layer even when there is no climbing-up node between the two links when the relationship between the two links have satisfied the promotion criteria.

13. An apparatus for searching a route as defined in claim 11, wherein the means for retrieving the candidate links from the map data includes means for searching a successor link that is successive to a current link and calculating a cost of each successor link.

14. An apparatus for searching a route as defined in claim 13, wherein the data storage includes an expansion link list for storing the candidate links, an expansion heap for storing the current link as a parent link of the successor link, and a climbing link list for storing the corresponding link in the higher layer as a climbing link when either there is a climbing-up node or the promotion criteria is satisfied, where the link in the lower layer that corresponds to the climbing link is stored in the expansion heap as a parent link of the climbing link.

15. An apparatus for searching a route as defined in claim 11, wherein the means for searching the successor link that is successive to a current link includes a step of obtaining a successor link of lowest cost where the cost is determined by factors including a distance, time, and fees associated with the successor link.

16. An apparatus for calculating a route as defined in claim 14, further comprising means for deleting the data in the expansion link list every time when all of the candidate links within the predetermined search range have been examined.

17. An apparatus for searching a route as defined in claim 11, wherein the promotion criteria is satisfied when there is a link in the higher layer of the map data that corresponds to a link in the lower layer, and the climbing criteria is satisfied when there is a climbing-up node between the lower layer and the upper layer within the predetermined search range.

18. An apparatus for searching a route as defined in claim 14, wherein the means for building the path between the destination and the start point includes means for removing copies of series of links in the lower layer from the start point to the parent link and means for removing the climbing link corresponding to the parent link.

19. An apparatus for searching a route as defined in claim 18, wherein the means for building the path between the destination and the start point further includes means for merging links that have been remained after the removal of the links, thereby building a route that shifts the different layers of the map data via a climbing-up node.

20. An apparatus for searching a route as defined in claim 11, further comprising means for evaluating a cost associated with a route involving the links that have satisfied the promotion criteria in comparison with a cost associated with a route without using the link promotion.