Route calculation method for a vehicle navigation system

• US 20050222764A1
• Filed: 03/30/2005
• Published: 10/06/2005
• Est. Priority Date: 04/06/2004
• Status: Active Grant

• Current Assignee: Honda Motor Co., Ltd. (Honda Motor Company)
• Original Assignee: Honda Motor Co., Ltd. (Honda Motor Company)
• Inventors: Ohki, Eric Shigeru, Kurciska, Maja, Tamura, Kazuya, Uyeki, Robert
• Granted Patent: US 7,680,596 B2
• Time in Patent Office: Days
• US Class Current: 701/210
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• CPC Class Codes: G01C 21/3694 Output thereof on a road map
• CPC Class Codes: G08G 1/096811 where the route is computed offboard
• CPC Class Codes: G08G 1/096844 where the complete route is dynamically recomputed based on new data

Abstract

Traffic information, including flow information and incident information, obtained through a traffic management system for providing and facilitating the exchange of traffic information between a remote location and a vehicle may be used in route calculation by a navigation device. The navigation device may recalculate a route based on anticipated user error. Alternatively, the navigation device may recalculate a route using received traffic information triggered by the receipt of a traffic information update, or triggered by the passage of an amount of time. The broadcast rate of traffic information updates may vary temporally (providing more frequent updates during peak commute times) or geographically (providing more frequent updates to metropolitan areas with increased traffic information needs). If route calculation is triggered by an elapsed amount of time, the amount of time may vary to be shorter during peak commute times. Additional route calculation techniques allow the incorporation of historical traffic information or the use of the most recent traffic information if incomplete traffic information is available. Still further route calculation techniques may calculate a best route by avoiding zigzagging or evaluating an assigned cost of a potential route.

Claims

1. In a vehicle navigation system having an output screen, a method for optimizing a travel route between a first location and a second location based on traffic information from a remote location, comprising the steps of:

(a) displaying a travel route between the first and second locations in the output screen;

(b) determining whether to recalculate the travel route displayed in said step (a);

(c) calculating an alternative travel route, if the vehicle navigation system determines in said step (b) to recalculate the travel route;

(d) displaying the alternative travel route in the output screen;

(e) determining whether a traffic information update has been received from the remote location;

(f) recalculating the alternative travel route based upon the traffic information update received in said step (e);

(g) determining whether the alternative travel route recalculated in said step (f) has a shorter estimated travel time from the first location to the second location than the travel route displayed in said step (a); and

(h) displaying the alternative travel route recalculated in said step (f) in the output screen, if the determination in said step (g) favors the alternative travel route recalculated in said step (f).

2. The method as recited in claim 1, wherein determining whether to calculate the travel route in said step (b) is based upon anticipating an error by a user of the vehicle navigation system.

3. The method as recited in claim 2, wherein the error comprises missing a turn on the travel route displayed in said step (a).

4. The method as recited in claim 2, wherein the error comprises turning the wrong direction on the travel route displayed in said step (a).

5. The method as recited in claim 1, wherein calculating the travel route in said step (c) must be completed before the vehicle navigation system determines whether a traffic information update has been received in said step (e).

6. The method as recited in claim 1, wherein determining whether a traffic information update has been received in said step (e) comprises receiving traffic-related information from the remote location through a wireless communication network.

7. The method as recited in claim 6, wherein the remote location comprises a traffic information supplier.

8. The method as recited in claim 1, wherein determining whether a traffic information update has been received in said step (e) comprises receiving traffic-related information from the remote location through a broadcast communication network.

9. In a vehicle navigation system having an output screen, a method for optimizing a travel route between a first location and a second location using traffic information from a remote location, comprising the steps of:

(a) displaying a travel route from the first location to the second location in the output screen;

(b) determining whether a predetermined amount of time has elapsed;

(c) acquiring updated traffic information from a remote location, if it is determined in said step (b) that the predetermined amount of time has elapsed;

(d) calculating an alternative travel route based on the updated traffic information acquired in said step (c);

(e) determining whether the alternative travel route calculated in said step (d) has a shorter estimated travel time from the first location to the second location than the travel route displayed in said step (a); and

(f) displaying the alternative travel route in the output screen, if the determination in said step (e) favors the new alternative route calculated in said step (d).

10. The method as recited in claim 9, wherein the predetermined amount of time in said step (b) comprises a fixed time interval.

11. The method as recited in claim 9, wherein the predetermined amount of time in said step (b) comprises a variable time interval.

12. The method as recited in claim 10, wherein the fixed time interval comprises a time interval between thirty seconds and five minutes.

13. The method as recited in claim 9, further comprising:

(g) displaying traffic-related information pertaining to the alternative travel route displayed in said step (f) in the output screen.

14. The method as recited in claim 11, wherein the variable time interval is based on commute times such that the variable time interval is shorter during peak commute time than the variable time interval during non-peak commute times.

15. In a vehicle navigation system having an output screen, a method for optimizing a travel route between a first location and a second location using traffic-related information provided from a remote location, comprising the steps of:

(a) displaying a travel route between the first location and the second location in the output screen;

(b) determining whether a traffic information update has been received from the remote location;

(c) calculating an alternative travel route based on the traffic information update, if it is determined in said step (b) that a traffic information update was received from the remote location;

(d) determining whether the alternative travel route calculated in said step (c) has a shorter estimated travel time between the first and second locations than the travel route displayed in said step (a); and

(e) displaying the alternative travel route in the output screen, if the determination in said step (d) favors the alternative travel route.

16. The method as recited in claim 15, further comprising:

(f) displaying traffic-related information in the output screen that pertains to the alternative travel route displayed in said step (e).

17. The method as recited in claim 15, wherein determining whether a traffic information update has been received in said step (b) comprises receiving traffic-related information from the remote location through a wireless communication network.

18. The method as recited in claim 15, wherein the remote location comprises a traffic information supplier.

19. The method as recited in claim 15, wherein determining whether a traffic information update has been received in said step (b) comprises receiving traffic-related information from the remote location through a broadcast communication network.

20. In a vehicle navigation system having an output screen, a method for optimizing a travel route between a first location and a second location using actual traffic information and historical traffic information supplied from a remote location, comprising the steps of:

(a) calculating a travel route between the first location and the second location based on the traffic information received from the remote location;

(b) determining whether the travel route calculated in said step (a) is based at least in part on actual traffic flow information received from the remote location;

(c) displaying the travel route calculated in said step (a) in the output screen, if it is determined in said step (b) that the travel route is based at least in part on actual traffic flow information received from the remote location;

(d) acquiring historical traffic information from the remote location, if it is determined in said step (b) that the travel route calculated in said step (a) is not based at least in part on actual traffic flow information received from the remote location;

(e) recalculating the travel route calculated in said step (a) based on the historical traffic information acquired in said step (d); and

(f) displaying the travel route recalculated in said step (e) in the output screen.

21. The method as recited in claim 20, wherein acquiring historical traffic information in said step (d) comprises receiving/transmitting communications between the navigation system and the remote location through a broadcast communication network.

22. The method as recited in claim 20, wherein the historical traffic information acquired in said step (d) is limited to a coverage area that includes the first location and the second location.

23. The method as recited in claim 20, wherein acquiring historical traffic information in said step (d) comprises receiving/transmitting communications between the navigation system and a traffic information supplier through a wireless communication network.

24. The method as recited in claim 21, wherein said broadcast communication network comprises television network.

25. The method as recited in claim 21, wherein said broadcast communication network comprises a radio network.

26. The method as recited in claim 21, wherein said broadcast communication network comprises a satellite network.

27. In a vehicle navigation system having an output screen, a method for optimizing a travel route between a first location and a second location using traffic flow information and traffic incident information supplied from a remote location, comprising the steps of:

(a) acquiring traffic flow information and traffic incident information from the remote location;

(b) calculating a travel route between the first location and the second location based on the traffic flow information and traffic incident information acquired in said step (a) that pertains to the travel route;

(c) determining whether the traffic flow information or traffic incident information used in calculating the travel route in said step (b) includes extent information;

(d) displaying the travel route calculated in said step (b) in the output screen, if it is determined in said step (c) that the traffic flow information or traffic incident information includes extent information;

(e) determining the amount of time that has passed for each traffic incident that was used in calculating the travel route in said step (b), if it is determined in said step (c) that the traffic incident information did not include extent information;

(f) calculating an alternative travel route based on the determination in said step (e); and

(g) displaying the alternative travel route calculated in said step (f) in the output screen.

28. The method as recited in claim 27, wherein calculating an alternative travel route in said step (f) comprises:

(i) determining a plurality of alternative travel routes between the first location and the second location;

(ii) locating the traffic incidents on each one of said plurality of alternative travel routes determined in said step (i);

(iii) determining an elapsed time for each traffic incident located in said step (ii);

(iv) calculating a total elapsed time for each one of the plurality of travel routes determined in said step (i); and

(v) selecting the alternative travel route determined that has the greatest total elapsed time calculated in said step (iv).

29. In a vehicle navigation system having an output screen, a method for providing an option to a user of the vehicle navigation system for requesting a new travel route between a first location and a second location, comprising the steps of:

(a) calculating a travel route between the first location and the second location;

(b) displaying the travel route calculated in said step (a) in the output screen;

(c) acquiring traffic information from a remote location;

(d) displaying traffic information acquired in said step (c) that is located along the travel route displayed in said step (b);

(e) providing an option to calculate an alternative travel route that avoids the traffic information displayed in said step (d);

(f) calculating the alternative travel route, if the user of the vehicle navigation system selects the option provided in said step (e); and

(g) displaying the alternative travel route calculated in said step (f) in the output screen, if the alternative travel route is calculated in said step (f).

30. The method as recited in claim 29, wherein the traffic information acquired in said step (c) comprises traffic-related information for a coverage area.

31. The method as recited in claim 30, wherein the coverage area includes the first location and the second location.

32. The method as recited in claim 29, wherein providing an option to calculate an alternative travel route in said step (e) comprises a touch sensitive button on the output screen.

33. In a vehicle navigation system having an output screen, a method for reducing the zigzag effect of rerouting a user of the vehicle navigation system to a new route between a first location and a second location, comprising the steps of:

(a) calculating a travel route between the first location and the second location;

(b) displaying the travel route calculated in said step (a) in the output screen;

(c) acquiring traffic information from a remote location;

(d) determining whether to reroute a user of the vehicle navigation system to a new route based on the traffic information acquired in said step (c);

(e) calculating the new route based on the traffic information acquired in said step (c), if it is determined in said step (d) to reroute the user of the vehicle navigation system to the new route;

(f) comparing the new route calculated in said step (e) with the travel route displayed in said step (b) to determine how many times the new route has been rerouted back to the travel route;

(g) continuing to display the travel route displayed in said step (b), if the comparison in said step (f) determines that the new route has been rerouted back to the travel route more than a predetermined number of times; and

(h) displaying the new route in the output screen, if the comparison in said step (f) determines that the new route has been rerouted back to the travel route less than or equal to the predetermined number of times.

34. The method as recited in claim 33, wherein the predetermined number of times comprises two times.

35. The method as recited in claim 33, wherein the predetermined number of times comprises between two and five times.

36. The method as recited in claim 33, wherein the traffic information acquired in said step (c) is limited to a geographic area that includes the first and second locations.

37. The method as recited in claim 33, wherein calculating the new route in said step (e) is based upon at least one factor selected from a list consisting of (i) the vehicle'"'"'s position, (ii) the vehicle'"'"'s speed, (iii) the direction the vehicle is heading, (iv) the second location, (v) the severity of any traffic incidents acquired in said step (c), (vi) the time the traffic information was acquired in said step (c), and (vii) estimated time for a traffic incident acquired in said step (c) to clear.

38. The method of claim 33, wherein determining whether to reroute a user in said step (d) comprises:

(i) determining whether the traffic information acquired in said step (c) includes a traffic incident;

(ii) identifying if the traffic incident is located along the travel route displayed in said step (b); and

(iii) determining whether the traffic incident identified in said step (ii) is severe enough to reroute the user of the vehicle navigation system.

39. In a vehicle navigation system having an output screen, a method for rerouting a user of the vehicle navigation system driving along a travel route between a first location and a second location, comprising the steps of:

(a) acquiring traffic information from a remote location;

(b) determining whether to reroute the user of the vehicle navigation system to a new route based on the traffic information acquired in said step (a);

(c) calculating the new route based on the traffic information acquired in said step (a), if it is determined in said step (b) to reroute the user of the vehicle navigation system to a new route; and

(d) displaying the new route in the output screen, if the new route is calculated in said step (c).

40. The method as recited in claim 39, wherein acquiring traffic information in said step (a) includes identifying traffic incidents located along the travel route.

41. The method as recited in claim 40, wherein determining whether to reroute the user of the vehicle navigation system in said step (b) comprises:

(i) identifying the location of a traffic incident;

(ii) assigning an expiration time to the traffic incident identified in said step (i);

(iii) calculating a distance threshold value based on the location of the traffic incident identified in said step (i) and the expiration time assigned to the traffic incident in said step (ii);

(iv) determining whether the location of the traffic incident should be included in calculating the new route in said step (c) based on the distance threshold value calculated in said step (iii).

42. The method as recited in claim 41, wherein the distance threshold value calculated in said step (iii) signifies a predetermined distance in which it is likely that a traffic incident identified in said step (i) will expire before the user of the vehicle navigation system reaches the traffic incident.

43. The method as recited in claim 40, wherein determining whether to reroute the user of the vehicle navigation system in said step (b) comprises:

(i) identifying the location of a traffic incident;

(ii) determining the density of the road where the traffic incident is identified in said step (i);

(iii) calculating a distance threshold value based on the location of the traffic incident identified in said step (i) and the density of the road determined in said step (ii);

(iv)determining whether the traffic incident should be included in calculating the new route in said step (c) based on the distance threshold value calculated in said step (iii).

44. The method as recited in claim 41, wherein the expiration time assigned in said step (ii) calculated from historical data for similar types of traffic incidents in similar types of road conditions.