Method and apparatus for establishing optimum route to intersection destination for navigation system

• US 20090259394A1
• Filed: 04/14/2008
• Published: 10/15/2009
• Est. Priority Date: 04/14/2008
• Status: Active Grant

• Current Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Original Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Inventors: Zhao, Lei, Vu, Tien
• Granted Patent: US 8,560,224 B2
• Time in Patent Office: Days
• US Class Current: 701/202
• 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 a navigation system for calculating a route to an intersection destination establishes an optimum route to the intersection. The method and apparatus creates a virtual zero-length dummy link, connects one end of the virtual zero-length dummy link to all link-spot pairs indicating an original intersection destination, sets another end of the virtual zero-length dummy link as a temporary destination, calculates possible routes between the temporary destination and a current vehicle position and selects the optimum route. After determining the optimum route, the navigation system removes the virtual zero-length dummy link and starts the route guidance operation to the intersection destination.

Claims

1. A method of calculating a route to a destination for a navigation system, comprising the steps of:

creating data indicating a virtual zero-length dummy link and storing the data in a memory of the navigation system;

retrieving the data indicating the virtual zero-length dummy link when a specified destination is an intersection (intersection destination);

connecting one end of the virtual zero-length dummy link to the intersection destination and setting another end of said virtual zero-length dummy link as a temporary destination;

calculating possible routes between the temporary destination and a current position of a user; and

selecting a most preferable route to the temporary destination for a route guidance operation to the intersection destination.

2. A method of calculating a route to a destination as defined in claim 1, further comprising a step of retrieving all map data from a map database of the navigation system that are necessary for calculating the possible routes between the destination and the current position of the user.

3. A method of calculating a route to a destination as defined in claim 2, further comprising a step of retrieving all link-spot pairs that indicate the intersection destination from the map database of the navigation system.

4. A method of calculating a route to a destination as defined in claim 3, wherein said step of connecting the end of the virtual zero-length dummy link to the intersection destination further includes a step of connecting the end of the virtual zero-length dummy link to all of the link-spot pairs that indicate the intersection destination.

5. A method of calculating a route to a destination as defined in claim 4, wherein said step of selecting the most preferable route to the temporary destination includes a step of selecting the preferable route that includes one of the link-spot pairs indicating the intersection destination of least cost.

6. A method of calculating a route to a destination as defined in claim 1, further comprising a step of removing the virtual zero-length dummy link from the intersection destination after the step of selecting the most preferable route to the temporary destination.

7. A method of calculating a route to a destination as defined in claim 1, further comprising a step of replacing the temporary destination with the intersection destination.

8. A method of calculating a route to a destination as defined in claim 7, further comprising a step of starting the route guidance operation to the intersection destination through the selected route.

9. A method of calculating a route to a destination as defined in claim 2, wherein said virtual zero-length dummy link is a single link of no length that is used solely in a process of calculating a route to a destination when the destination is an intersection.

10. A method of calculating a route to a destination as defined in claim 9, wherein said data indicating the virtual zero-length dummy link differs from the map data indicating link-spot pairs in that it lacks information on absolute positions and attributes.

11. An apparatus of calculating a route to a destination for a navigation system, comprising:

means for creating data indicating a virtual zero-length dummy link and storing the data in a memory of the navigation system;

means for retrieving the data indicating the virtual zero-length dummy link when a specified destination is an intersection (intersection destination);

means for connecting one end of the virtual zero-length dummy link to the intersection destination and setting another end of said virtual zero-length dummy link as a temporary destination;

means for calculating possible routes between the temporary destination and a current position of a user; and

means for selecting a most preferable route to the temporary destination for a route guidance operation to the intersection destination.

12. An apparatus of calculating a route to a destination as defined in claim 11, further comprising means for retrieving all map data from a map database of the navigation system that are necessary for calculating the possible routes between the destination and the current position of the user.

13. An apparatus of calculating a route to a destination as defined in claim 12, further comprising means for retrieving all link-spot pairs that indicate the intersection destination from the map database of the navigation system.

14. An apparatus of calculating a route to a destination as defined in claim 13, wherein said means for connecting the end of the virtual zero-length dummy link to the intersection destination further includes means for connecting the end of the virtual zero-length dummy link to all of the link-spot pairs that indicate the intersection destination.

15. An apparatus of calculating a route to a destination as defined in claim 14, wherein said means for selecting the most preferable route to the temporary destination includes means for selecting the preferable route that includes one of the link-spot pairs indicating the intersection destination of least cost.

16. An apparatus of calculating a route to a destination as defined in claim 11, further comprising means for removing the virtual zero-length dummy link from the intersection destination after selecting the most preferable route to the temporary destination.

17. An apparatus of calculating a route to a destination as defined in claim 11, further comprising means for replacing the temporary destination with the intersection destination.

18. An apparatus of calculating a route to a destination as defined in claim 17, further comprising means for starting the route guidance operation to the intersection destination through the selected route.

19. An apparatus of calculating a route to a destination as defined in claim 12, wherein said virtual zero-length dummy link is a single link of no length that is used solely in a process of calculating a route to a destination when the destination is an intersection.

20. An apparatus of calculating a route to a destination as defined in claim 19, wherein said data indicating the virtual zero-length dummy link differs from the map data indicating link-spot pairs in that it lacks information on absolute positions and attributes.