Method and apparatus for predicting future travel times over a transportation network

• US 7,363,144 B2
• Filed: 02/07/2005
• Issued: 04/22/2008
• Est. Priority Date: 02/07/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Liu, Zhen, Wynter, Laura, Zhang, Li
• Primary Examiner(s): ARTHUR JEANGLAUDE, GERTRUDE
• Application Number:
  US11/052,309
• Publication Number:
  US 20060178806A1
• Time in Patent Office: 1,170 Days
• Field of Search: 701/117, 701/118, 340/905, 340/906, 340/995.13
• US Class Current: 701/117
• CPC Class Codes: G08G 1/123 indicating the position of vehicles, e.g. scheduled vehicles; Managing passenger vehicles circulating according to a fixed timetable, e.g. buses, trains, tramstransmission of navigation instructions to vehicles G08G1/0968

Abstract

The present invention is a method and an apparatus for predicting future travel times over a transportation network. In one embodiment, a method for predicting future travel times over a transportation network includes receiving a data point indicating a real-time volume of traffic on the link at a given time and updating a template representative of an observed traffic pattern on the link in accordance with the received data point. A future travel time over the link can then be estimated in accordance with the updated template. Thus, the template is able to adapt to dynamically changing traffic patterns, taking these changing traffic patterns into account when making predictions of future traffic patterns.

Claims

1. A method for estimating a travel time over a link of a transportation network at a time in the future, the method comprising:

receiving at least one data point indicating a real-time volume of traffic on said link at a given time;

updating a template representative of a historical traffic pattern on said link in accordance with said data point; and

generating said estimated travel time for future travel over said link in accordance with said updated template.

2. The method of claim 1, wherein said template maps a traffic volume on said link versus time.

3. The method of claim 1, wherein said template represents a traffic patterns observed over at least one of:

a day, a week, a month or a year.

4. The method of claim 1, wherein said volume of traffic is a number of vehicles observed on said link per a unit of time.

5. The method of claim 1, wherein said updating comprises:

adjusting a future volume estimated for said link by said template to reflect said real-time volume indicated by said at least one data point.

6. The method of claim 5, wherein said adjustment is made in accordance with a moving average.

7. The method of claim 6, wherein said moving average is an exponentially weighted average.

8. The method of claim 5, further comprising:

generating a prediction indicative of a number of vehicles expected to be traveling on said link at said time in the future, said prediction being made in accordance with said adjusted estimated future volume.

9. The method of claim 1, wherein said estimated travel time is generated in accordance with a moving average.

10. The method of claim 9, wherein said moving average is an exponentially weighted average.

11. A computer readable medium containing an executable program for estimating a travel time over a link of a transportation network at a time in the future, where the program performs the steps of:

receiving at least one data point indicating a real-time volume of traffic on said link at a given time;

updating a template representative of a historical traffic pattern on said link in accordance with said data point; and

generating said estimated travel time for future travel over said link in accordance with said updated template.

12. The computer readable medium of claim 11, wherein said template maps a traffic volume on said link versus time.

13. The computer readable medium of claim 11, wherein said template represents a traffic patterns observed over at least one of:

a day, a week, a month or a year.

14. The computer readable medium of claim 11, wherein said volume of traffic is a number of vehicles observed on said link per a unit of time.

15. The computer readable medium of claim 11, wherein said updating comprises:

adjusting a future volume estimated for said link by said template to reflect said real-time volume indicated by said at least one data point.

16. The computer readable medium of claim 15, wherein said adjustment is made in accordance with a moving average.

17. The computer readable medium of claim 16, wherein said moving average is an exponentially weighted average.

18. The computer readable medium of claim 15, further comprising:

generating a prediction indicative of a number of vehicles expected to be traveling on said link at said time in the future, said prediction being made in accordance with said adjusted estimated future volume.

19. The computer readable medium of claim 11, wherein said estimated travel time is generated in accordance with a moving average.

20. Apparatus for estimating a travel time over a link of a transportation network at a time in the future, the apparatus comprising:

means for receiving at least one data point indicating a real-time volume of traffic on said link at a given time;

means for updating a template representative of a historical traffic pattern on said link in accordance with said data point; and

means for generating said estimated travel time for future travel over said link in accordance with said updated template.