METHOD AND STRUCTURE FOR VEHICULAR TRAFFIC PREDICTION WITH LINK INTERACTIONS AND MISSING REAL-TIME DATA

• US 20100063715A1
• Filed: 11/16/2009
• Published: 03/11/2010
• Est. Priority Date: 01/24/2007
• Status: Active Grant

• Current Assignee: Tomtom Global Content B.V (TomTom NV)
• Original Assignee: International Business Machines Corporation
• Inventors: Wynter, Laura, Morris, Benjamin G., Min, Wanli
• Granted Patent: US 8,755,991 B2
• Time in Patent Office: Days
• US Class Current: 701/118
• CPC Class Codes: G01C 21/3691 Retrieval, searching and output of information related to real-time traffic, weather, or environmental conditions arrangements for giving variable traffic instructions G08G1/09
• CPC Class Codes: G08G 1/0104 Measuring and analyzing of parameters relative to traffic conditions
• 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/096888 where input information is obtained using learning systems, e.g. history databases

Abstract

A method and apparatus for predicting traffic on a transportation network where real time data points are missing. In one embodiment, the missing data is estimated using a calibration model comprised of historical data that can be periodically updated, from select links constituting a relationship vector. The missing data can be estimated off-line whereafter it can be used to predict traffic for at least a part of the network, the traffic prediction being calculated by using a deviation from a historical traffic on the network. The invention further discloses a method for in-vehicle navigation; and a method for traffic prediction for a single lane.

Claims

1. A method for predicting traffic on a transportation network, said transportation network comprised of links, said links constituting a relationship vector, said method comprising:

a) providing data points related to real time traffic conditions on each link, wherein at least one data point is missing for a given link;

b) estimating the value of said missing data point; and

c) using said estimated value to predict traffic for at least a portion of said transportation network by deviation from a historical traffic pattern of said network.

2. The method of claim 1 wherein said missing data point in estimated in step (b) from a calibration model representative of historical data points.

3. The method of claim 1 wherein a plurality of data points are missing from a plurality of given links.

4. The method of claim 1 wherein said data points are provided from predetermined locations.

5. The method of claim 2 wherein in said historical data points comprise that for the preceding six or more weeks for the links constituting the calibration model.

6. The method of claim 5 wherein said calibration model is updated periodically.

7. The method of claim 1 wherein said estimating step is performed off-line.

8. An apparatus for predicting traffic on a transportation network, said transportation network comprised of links, said links constituting a relationship vector, said apparatus comprising:

a) a receiver to receive data points related to real time traffic conditions on each link, wherein at least one data point is missing from a given link;

b) an estimator to estimate the value of said missing data point; and

c) a calculator to calculate a traffic prediction by using said estimated value in a deviation from a historical traffic pattern of said network.

9. The apparatus of claim 8 wherein said estimator comprises a calibrated model constituted of historical data points from all links in the relationship vector, except those from said given link.

10. The apparatus of claim 8 wherein said data points are provided from predetermined locations.

11. A computer readable medium containing an executable program for predicting traffic on a transportation network, said transportation network comprised of links, said links constituting a relationship vector, where said program performs the steps of:

a) receiving data points related to real time traffic conditions on each link wherein at least one data point is missing from a given link;

b) estimating the value of said missing data point; and

c) calculating a traffic prediction by using said estimated value in a deviation from a historical traffic pattern of said network.

12. The computer readable medium of claim 11 wherein missing data point is estimated in step (b) from a calibration model representative of historical data points.

13. The computer readable medium of claim 12 wherein the historical data points in said calibration model are periodically updated.

14. A method of providing navigational guidance to a vehicle over a transportation network, said transportation network comprised of routes with traffic signals, the method comprising:

a) providing to a processor;

trip information, said trip information comprising an origin and a destination for said vehicle; and

a radius, said radius measured from said vehicle when said vehicle is on said transportation network;

b) obtaining data from one or more traffic signals within said radius, at intervals of time, said data relating to one or both of the following;

(i) information on the state of at least one of said traffic signals for a respective interval of time; and

(ii) routing table information, said routing table information indicative of state of traffic for routes to said destination on said transportation network

c) processing said data with said trip information to identify optimal route choices to said destination on said transportation network for said vehicle; and

d) providing said optimal route choices to said vehicle.

15. The method of claim 14 wherein said intervals of time are the same or different for data relating to (b)(i) and (b)(ii).

16. The method of claim 15 wherein said intervals of time are regular or irregular.

17. The method of claim 14 wherein the information on the state of said one or more traffic signals includes any one or more of the following:

the point in a stop-go cycle a particular signal is at during said respective interval of time, how much time remains for said cycle, and the duration of said cycle.

18. The method of claim 14 wherein said optimal route choices is based on any one or more of the following:

remaining duration to said destination, average speed on said optimal route choices, number of starts and stops at said one or more traffic signals.

19. The method of claim 14 wherein said routing table information indicative of state of traffic includes real or predicted travel time on one or more of the following:

(i) routes to said destination; and

(ii) routes in the vicinity of said one or more traffic signals.

20. The method of claim 19 wherein for (i) said travel time on routes to said destination includes real or predicted travel time from one location on said route to a second location on said route.

21. The method of claim 14 wherein said routing table information includes real or predicted travel time from said one or more traffic signals to one or more of the following:

(i) a location on a route to said destination; and

(ii) a location in the vicinity of said one or more traffic signals.

22. The method of claim 14 wherein said optimal route choices are updated throughout the duration to said destination.

23. The method of claim 14 wherein the processor is in said vehicle and said processing of step (c) is performed in whole or in part at any one or more of the following:

at said one or more traffic signals, at the processor, or at a remote location.

24. The method of claim 14 wherein the data of step (b) includes at least one missing data point, and said at least one missing data point is estimated to predict to predict traffic for a least a portion of said transportation network by deviation from a historical pattern of said transportation network.

25. A method of predicting traffic for a specific lane on a transportation network comprised of links wherein said links constitute a relationship vector, which method comprises:

a) providing data points related to real time traffic conditions for a specific lane in a link of a transportation network;

b) updating a template representative of a historical traffic pattern for said specific lane in accordance with said data points; and

c) providing a prediction of traffic for said specific lane in accordance with said updated template.

26. The method of claim 25 wherein said prediction of traffic includes any one or more of travel time, speed, density, flow, and occupation of said specific lane.

27. The method of claim 25 wherein at least one of said real time data points for sais missing.

28. The method of claim 27 wherein the value of said at least one missing data point is estimated.

29. The method of claim 28 wherein the value is estimated from a calibration model representative of historical data points from said specific lane.

30. A computer readable medium containing an executable program for predicting traffic on a transportation network, said transportation network comprised of links, said links constituting a relationship vector, wherein the program performs the steps of

a) providing data points related to real time traffic conditions on each link, wherein at least one data point is missing for a given link;

b) estimating the value of said missing data point; and

c) using said estimated value to predict traffic for at least a portion of said transportation network by deviation from a historical traffic pattern of said network.

31. A computer readable medium containing an executable program for providing navigational guidance to a vehicle over a transportation network, said transportation network comprised of routes with traffic signals, wherein the program performs the steps of:

a) providing to a processor;

trip information, said trip information comprising an origin and a destination for said vehicle; and

a radius, said radius measured from said vehicle when said vehicle is on said transportation network;

b) obtaining data from one or more traffic signals within said radius, at intervals of time, said data relating to one or both of the following;

(i) information on the state of at least one of said traffic signals for a respective interval of time; and

(ii) routing table information, said routing table information indicative of state of traffic for routes to said destination on said transportation network

c) processing said data with said trip information to identify optimal route choices to said destination on said transportation network for said vehicle; and

d) providing said optimal route choices to said vehicle.

32. A computer readable medium containing an executable program for predicting traffic for a specific lane on a transportation network comprised of links wherein said links constitute a relationship vector, wherein said program performs the steps of

a) providing data points related to real time traffic conditions for a specific lane in a link of a transportation network;

b) updating a template representative of a historical traffic pattern for said specific lane in accordance with said data points; and

c) providing a prediction of traffic for said specific lane in accordance with said updated template.