Navigation system using forward-looking origin selection for route re-calculation

• US 6,405,130 B1
• Filed: 12/11/1996
• Issued: 06/11/2002
• Est. Priority Date: 12/11/1996
• Status: Expired due to Term

• Current Assignee: MiTAC International Corporation (MiTAC Holdings Corp.)
• Original Assignee: Magellan DIS, Inc.
• Inventors: Piwowarski, Jim J.
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Donnelly, Arthur D.
• Application Number:
  US08/762,012
• Time in Patent Office: 2,008 Days
• Field of Search: 701/208, 701/209, 701/210, 701/23, 701/25, 701/26, 701/200, 701/201, 701/202, 340/988, 340/990, 340/995, 731/78.R
• US Class Current: 701/210
• CPC Class Codes: G01C 21/3407 specially adapted for specific applications
• CPC Class Codes: G08G 1/096827 where the route is computed onboard
• CPC Class Codes: G08G 1/096844 where the complete route is dynamically recomputed based on new data
• CPC Class Codes: G08G 1/096861 where the immediate route instructions are output to the driver, e.g. arrow signs for next turn

Abstract

A navigation system calculates a first route to a first destination. If the navigation system determines while en route that a second route would result in a significant time saving, the navigation system selects a point along the first route between the current vehicle location and the first destination as a new “origin” for the second route. The navigation system guides the user to the intermediate point along the first route. The navigation system then guides the user from the intermediate point along the second route. The second route can be an alternate route to the same destination or an alternate route to a second destination.

Claims

1. A navigation system comprising:

a database of roads to be traveled by a vehicle, said database includes road segments, each said road segment having an associated travel time stored in said database;

a system for selecting a first origin relative to said database;

a user input device for selecting a first destination relative to said database;

a system for determining a first route from said database from said first origin to said first destination;

a system for determining the current location of the navigation system relative to said database; and

a system for determining a second route from said database from a second origin on said first route between said current location and said first destination said system for determining said first route utilizing said associated travel times to determine said first route and for determining said second route utilizing said associated travel times to determine said second route, said system comparing said first route to said second route.

2. The navigation system of claim 1 further including a system for selecting a second destination from said database, said system for determining a second route calculating said second route from said second origin to said second destination.

3. The navigation system of claim 1 wherein said system for determining a second route calculates said second route from said second origin to said first destination, said first route including a road segment not included in said second route.

4. The navigation system of claim 1 further including a system for receiving congestion information, said system for determining said first route utilizing said congestion information to calculate said first route.

5. The navigation system of claim 1 wherein said database includes road segments, each said road segment having an associated travel time stored in said database, said system for determining a first route utilizing said associated travel times to determine said first route, said navigation system further including a system for adjusting for receiving congestion information about road segments, said system for determining a second route utilizing congestion information to determine said second route.

14. The navigation system of claim 1 wherein said second origin is selected on said first route at a non-zero distance from said current location.

15. The navigation system of claim 14 wherein said distance is determined based upon vehicle speed.

20. The navigation system of claim 14 wherein said system for determining said second route ensures that said second origin is selected on said first route between said current location and said first destination.

6. A method for planning a route including the steps of:

a) selecting a first origin relative to a database of roads;

b) selecting a first destination relative to said database of roads;

c) determining a first route from said database of roads from said first origin to said first destination;

d) determining a current location on said first route;

e) determining a second route from a second origin lying on said first route between said current location and said first destination;

f) associating an estimated travel time with each of a plurality of road segments of said roads in said database;

g) determining said first route and said second route based at least in part upon said travel times; and

h) comparing said first route and said second route in response to said travel times.

7. The method for planning a route according to claim 6 further including the steps of:

providing guidance instructions from said first origin along said first route; and

providing guidance instructions from said second origin along said second route.

8. The method for planning a route according to claim 6 wherein said step d) includes the steps of installing a position-determining device on a vehicle, said current location being the current location of the vehicle.

9. The method for planning a route according to claim 6 further including the steps of:

associating an estimated travel time with each of a plurality of road segments of said roads in said database; and

determining said first route and said second route based upon said travel times.

10. The method for planning a route according to claim 6 further including the steps of:

travelling along said first route;

selecting a second destination while travelling said first route; and

determining said second route to said second destination.

11. The method for planning a route according to claim 6 further including the steps of:

receiving traffic congestion information associated with a road segment; and

determining said second route based upon said traffic congestion information.

16. The method of claim 6 further including the step of selecting said second origin at a nonzero distance from said current location.

17. The method of claim 16 further including the step of determining said distance based upon vehicle speed.

18. The method of claim 6 further including the steps of:

f) determining a distance from the current location; and

g) selecting said second origin at said distance from said current location after said step f).

19. The method of claim 18 wherein said distance is determined in said step f) based upon vehicle speed.

21. The method of claim 16 further including the step of ensuring that said second origin is selected between said first origin and said first destination.

12. A method for planning a route including the steps of:

a) associating a travel time with each of a plurality of road segments in a database of roads;

b) selecting a first origin relative to said database of roads;

c) selecting a first destination relative to said database of roads;

d) determining a first route from said database of roads from said first origin to said first destination;

e) providing guidance instructions from said first origin along said first route;

f) determining a current location on said first route relative to said database of roads;

g) receiving congestion information associated with a congested road segment included in said first route;

h) determining a second route from a second origin lying on said first route between said current location and said first destination, said second route not including said congested road segment;

i) estimating the time to be saved by travelling said second route rather than said first route;

j) selecting to travel said second route rather than said first route based upon said estimated time to be saved; and

k) providing guidance instructions from said second origin along said second route.

13. A method for planning a route according to claim 12 wherein said step k) includes the step of providing guidance instructions to said first destination.