Method and apparatus for determining a route on a digitized road network stored in the memory of a navigation system

• US 6,112,154 A
• Filed: 05/22/1997
• Issued: 08/29/2000
• Est. Priority Date: 05/22/1997
• Status: Expired due to Term

• Current Assignee: Continental Automotive GmbH (Continental AG)
• Original Assignee: Siemens AG
• Inventors: Schupfner, Markus
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Pipala, Edward
• Application Number:
  US08/861,855
• Time in Patent Office: 1,195 Days
• Field of Search: 701/200, 701/201, 701/202, 701/204, 701/206, 701/208, 701/209, 701/210, 340/990, 340/995
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

A navigation system utilizes a digitized road network stored in a non-volatile memory and determines therefrom a travel route from a starting point to a destination point. A partial route is calculated from the starting point to an intermediate destination point and maneuvers for this partial route are generated and output to the user in order to guide the user even before the complete route to the destination point has been fully calculated. When a complete route from the starting point to the destination point has been calculated, the calculated complete route is overlapped with the partial route to define an intersection point between the two routes. The proposed maneuvers for that complete route are then output beginning from the intersection point.

Claims

1. A method of determining a travel route from a starting point to a destination point located on a digitized road network stored in a non-volatile memory of a navigation system, the method which comprises:

defining an intermediate destination point between a starting point and a destination point;

calculating an original partial route from the starting point to the intermediate destination point, and outputting partial route information to a user interface;

calculating a complete route from the starting point to the destination point;

overlapping the complete route with the original partial route and defining an intersection point between the complete route and the original partial route; and

outputting complete route information beginning from the intersection point.

2. The method according to claim 1, which further comprises generating maneuvers for the original partial route and displaying the original partial route maneuvers as the partial route information, and generating maneuvers for the complete route and displaying the complete route maneuvers as the complete route information.

3. The method according to claim 2, wherein the complete route maneuvers are output starting from the intersection point, if the original partial route and the complete route intersect in a segment of the travel route which has not been passed yet by the user.

4. The method according to claim 1, which further comprises, if no intersection point between the original partial route and the complete route is found in the overlapping step:

tracking back a temporary destination point towards the starting point, but no farther than to a present position of the user, and determining a new starting point;

subsequently calculating a new partial route beginning from the new starting point to a new temporary destination point and outputting new partial route information to the user;

calculating a new complete route from the new starting point to the destination point and overlapping the new complete route with the new partial route; and

if the new partial route and the new complete route have at least one intersection point, outputting new complete route information from the intersection point onward.

5. The method according to claim 4, which further comprises overlapping the new partial route with the original partial route, and, if the new partial route and the original partial route have an intersection point, dismissing the new partial route and calculating a different new partial route without such intersection point.

6. The method according to claim 4, which comprises:

if the new partial route and the original partial route have an intersection point, but a different partial route without intersection point cannot be calculated, generating and outputting maneuvers for the new partial route.

7. The method according to claim 1, which further comprises calculating a further partial route beginning from the intermediate destination point to a further destination point, if the calculation of the complete route is not finished before arrival at the intermediate destination point.

8. The method according to claim 1, which comprises determining a distance from the starting point to the intermediate destination point as a function of a statistical speed for route calculation, a route type and a current speed, such that a probable travel time to the intermediate destination is longer than a probable period of time for calculating the complete route.

9. The method according to claim 1, which further comprises outputting the original partial route information to a user interface before a complete route from the starting point to the destination point is available.

10. A navigation system for determining a travel route from a starting point to a destination point, comprising:

a non-volatile memory storing a digitized road network;

a microprocessor connected to said non-volatile memory, said microprocessor being programmed to determine a route from a starting point to a destination point by;

calculating a partial route from the starting point to an intermediate destination point and calculating a complete route from the starting point to the destination point; and

overlapping the partial route from the starting point to the intermediate destination point with the complete route from the starting point to the destination point;

and a user interface for providing a user partial route information until the complete route is calculated and overlapped with the partial route and for providing the user with complete route information connecting from the partial route to the destination point.