Method and system for providing alternate routes with a navigation system

• US 6,317,685 B1
• Filed: 03/13/2000
• Issued: 11/13/2001
• Est. Priority Date: 03/13/2000
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: Kaplan, Lawrence M., Kozak, Frank J.
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Mancho, Ronnie
• Application Number:
  US09/523,794
• Time in Patent Office: 610 Days
• Field of Search: 701/210, 701/200-209, 340/905, 340/989, 340/990, 340/993, 340/995, 235/91.H, 324/161, 324/160, 705/5, 705/6, 705/7, 705/8, 705/9
• US Class Current: 701/210
• CPC Class Codes: G01C 21/3407 specially adapted for specific applications
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events
• CPC Class Codes: G06Q 10/025 Coordination of plural reservations, e.g. plural trip segments, transportation combined with accommodation
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 30/0205 Location or geographical consideration

Abstract

A feature for a navigation system that provides an evaluation of alternate routes. According to this feature, the navigation system compares the actual time of travel along a route to the estimated time of travel along the route. If the actual time of travel exceeds the estimated time of travel, alternate routes to the destination are calculated and provided to the user. This feature enables driver-experienced traffic conditions to be taken into account.

Claims

1. A program, for use with a vehicle navigation system capable of calculating a route from an origin to a destination, estimating a time of travel from said origin to said destination, and determining a location of a vehicle and an actual time of travel of said vehicle along said route, comprising:

means for determining whether the actual time of travel of said vehicle to a position along said route exceeds an estimated time of travel to said position along said route by a threshold amount of time; and

means for automatically initiating calculation of one or more alternate routes to said destination when said actual time of travel exceeds said estimated time of travel by said threshold amount of time.

2. The program of claim 1 wherein said threshold amount is configurable.

3. The program of claim 1 wherein said threshold amount is based on a fixed amount of time.

4. The program of claim 1 wherein said threshold amount is based on a relative amount of time.

5. The program of claim 1 wherein said threshold amount is based on both a fixed amount of time and a relative amount of time.

6. The program of claim 1 wherein said means for determining whether the actual time of travel of said vehicle to a position along said route exceeds an estimated time of travel to said position along said route by a threshold amount is invoked only upon input by a user requesting such determination.

7. The program of claim 1 wherein said means for determining whether the actual time of travel of said vehicle to a position along said route exceeds an estimated time of travel to said position along said route by a threshold amount is invoked automatically on a periodic basis.

29. The invention of claim 1 wherein said threshold amount of time is 5 minutes.

30. The invention of claim 1 wherein said threshold amount of time is 10 minutes.

31. The invention of claim 1 wherein said threshold amount of time is 15 minutes.

32. The invention of claim 1 wherein said threshold amount of time is 10% of said estimated time of travel.

33. The invention of claim 1 wherein said threshold amount of time is 25% of said estimated time of travel.

34. The invention of claim 1 wherein said threshold amount of time is 50% of said estimated time of travel.

35. The invention of claim 1 wherein said threshold amount of time is 100% of said estimated time of travel.

8. A vehicle navigation system comprising:

a route calculator, capable of calculating a route of travel along roadways from an origin to a destination;

a route travel time estimator, capable of estimating a time of travel along roadways of a route calculated by said route calculator;

a vehicle position locator, capable of determining the position of a vehicle relative to a roadway;

an actual time of travel calculator, capable of determining the actual time of travel of said vehicle along a route calculated by said route calculator;

a threshold parameter;

a travel time deviation calculator, capable of determining with respect to at least a portion of a route calculated by said route calculator whether an actual time of travel determined by said actual time of travel calculator exceeds an estimated time of travel determined by said route travel time estimator by a given amount based on said threshold parameter; and

an alternate route calculator capable of calculating an alternate route of travel along roadways to said destination.

9. The navigation system of claim 8 wherein said travel time deviation calculator operates automatically on a periodic basis.

10. The navigation system of claim 8 wherein said travel time deviation calculator operates only upon input by a user requesting such operation.

11. The navigation system of claim 8 or 9 wherein said alternate route calculator is responsive to said travel time deviation calculator.

12. The navigation system of claim 9 wherein said alternate route calculator calculates an alternative route of travel along roadways to said destination automatically upon a determination by said travel time deviation calculator that said actual time of travel exceeds said estimated time of travel by said threshold parameter.

13. The navigation system of claim 11 wherein said alternate route calculator calculates an alternative route of travel along roadways to said destination automatically upon a determination by said travel time deviation calculator that said actual time of travel exceeds said estimated time of travel by said threshold parameter.

14. The navigation system of claim 8, 9 or 10 wherein said alternate route calculator is responsive only upon input by a user requesting calculation of an alternate route of travel along roadways to said destination.

15. The navigation system of claim 8 wherein said route travel time estimator estimates a time of travel along roadways of a route calculated by said route calculator based on one or both of distance and speed limit information relating to said roadways.

16. The navigation system of claim 8 wherein said route travel time estimator estimates a time of travel along roadways of a route calculated by said route calculator based on measured time of travel relating to said roadways.

17. The navigation system of claim 8 wherein said route calculator calculates a route of travel along roadways from an origin to a destination in consideration of broadcast traffic information.

18. The navigation system of claim 8 wherein said threshold parameter is configurable.

19. The navigation system of claim 8 wherein said threshold parameter is based on a fixed amount of time.

20. The navigation system of claim 8 wherein said threshold parameter is based on a relative amount of time.

21. The navigation system of claim 8 wherein said threshold parameter is based on both a fixed amount of time and a relative amount of time.

23. The navigation system of claim 8 wherein said alternate route calculator calculates one or more alternate routes upon a determination by said travel time deviation calculator that said actual time of travel exceeds said estimated time of travel by said given amount based on said threshold parameter.

24. The navigation system of claim 23 wherein at least one of said one or more alternate routes calculated by said alternate route calculator is offered to a user of the navigation system for selection.

25. The navigation system of claim 23 wherein an alternate route calculated by said alternate route calculator is not offered to a user of the navigation system for selection where the estimated time of travel for said alternate route exceeds the estimated time of travel for the remaining portion of the original route by a pre-determined amount.

26. The navigation system of claim 23 wherein at least one of said one or more alternate routes calculated by said alternate route calculator includes portions of the original route.

36. The system of claim 8 wherein said threshold parameter is 5 minutes.

37. The system of claim 8 wherein said threshold parameter is 10 minutes.

38. The system of claim 8 wherein said threshold parameter is 15 minutes.

39. The system of claim 8 wherein said threshold parameter is 10% of said estimated time of travel.

40. The system of claim 8 wherein said threshold parameter is 25% of said estimated time of travel.

41. The system of claim 8 wherein said threshold parameter is 50% of said estimated time of travel.

42. The system of claim 8 wherein said threshold parameter is 100% of said estimated time of travel.

22. A vehicle navigation system comprising:

a route calculator, capable of calculating a route of travel along roadways from an origin to a destination;

a route travel time estimator, capable of estimating a time of travel along roadways of a route calculated by said route calculator;

a vehicle position locator, capable of determining the position of a vehicle relative to a roadway;

an actual time of travel calculator, capable of determining the actual time of travel of said vehicle along a route calculated by said route calculator;

a threshold parameter;

a travel time deviation calculator, capable of determining with respect to at least a portion of a route calculated by said route calculator whether an actual time of travel determined by said actual time of travel calculator exceeds an estimated time of travel determined by said route travel time estimator by a given amount based on said threshold parameter; and

an alternate route calculator capable of calculating an alternate route of travel along roadways to said destination,

wherein said alternate route calculator is disabled where an estimated time of travel is less than a pre-determined amount.

27. A method in a navigation system, comprising:

calculating a route of travel for a vehicle along roadways from an origin to a destination;

estimating the time of travel to one or more points along said route;

calculating the actual time of travel of said vehicle to said one or more points along said route;

determining whether said actual time of travel of said vehicle to one of said one or more points along said route exceeds said estimated time of travel to said one of said one or more points by a given amount based on a threshold parameter; and

calculating one or more alternates routes to said destination upon a determination that said actual time of travel exceeds said estimated time of travel by a given amount based on said threshold parameter.

43. The method of claim 27 wherein said threshold parameter is 5 minutes.

44. The method of claim 27 wherein said threshold parameter is 10 minutes.

45. The method of claim 27 wherein said threshold parameter is 15 minutes.

46. The method of claim 27 wherein said threshold parameter is 10% of said estimated time of travel.

47. The method of claim 27 wherein said threshold parameter is 25% of said estimated time of travel.

48. The method of claim 27 wherein said threshold parameter is 50% of said estimated time of travel.

49. The method of claim 27 wherein said threshold parameter is 100% of said estimated time of travel.

28. A method in a navigation system, comprising:

identifying a destination selected by a user of said navigation system;

identifying the roadways traveled by said user between a first location and second location;

calculating the actual time of travel of said user from said first location to said second location;

estimating the time of travel along said identified roadways between said first location and said second location;

determining whether said actual time of travel of said vehicle exceeds said estimated time of travel by a given amount based on a threshold parameter; and

calculating two or more routes to said destination upon a determination that said actual time of travel exceeds said estimated time of travel by said given amount based on said threshold parameter.

50. The method of claim 28 wherein said threshold parameter is 5 minutes.

51. The method of claim 28 wherein said threshold parameter is 10 minutes.

52. The method of claim 28 wherein said threshold parameter is 15 minutes.

53. The method of claim 28 wherein said threshold parameter is 10% of said estimated time of travel.

54. The method of claim 28 wherein said threshold parameter is 25% of said estimated time of travel.

55. The method of claim 28 wherein said threshold parameter is 50% of said estimated time of travel.

56. The method of claim 28 wherein said threshold parameter is 100% of said estimated time of travel.