Method and structure for vehicular traffic prediction with link interactions and missing real-time data

• US 8,755,991 B2
• Filed: 11/16/2009
• Issued: 06/17/2014
• Est. Priority Date: 01/24/2007
• Status: Active Grant

• Current Assignee: Tomtom Global Content B.V (TomTom NV)
• Original Assignee: Tomtom Global Assets BV (TomTom NV)
• Inventors: Wynter, Laura, Min, Wanli, Morris, Benjamin G.
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): Figueroa, Jaime
• Application Number:
  US12/619,226
• Publication Number:
  US 20100063715A1
• Time in Patent Office: 1,674 Days
• Field of Search: 701/117, 701/118, 701/423, 701/119, 701/414, 702/179, 342/454, 340/934, 340/995.13, 714/E11.197
• US Class Current: 701/119
• 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 from a calibrated model representative of historical data points from all links in the relationship vector, except those from the given link; 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, wherein said estimating said value of said missing data point comprises;

running a plurality of models for the given link having a missing data point at a most recent time, wherein a model provides either estimating a value for said missing data point of said given link at a most recent time when all other neighboring links of said relationship vector have data at said most recent time, or estimating a value for said missing data point when one or more other neighboring links of said relationship vector is missing a respective data point at said most recent time,

generating from each said run model a respective associated weight matrix for said given link;

storing each respective associated weight matrix for said given link;

determining an applicable model corresponding to a current real-time traffic network condition of said links of said relationship vector; and

choosing an associated estimated weight matrix of said plurality based on said applicable model, said chosen associated estimated weight matrix used by said calibrated model to determine said missing data point value for real-time traffic prediction, wherein at least one of the steps is performed by at least one processor.

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

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

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

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

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

7. 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 using a calibrated model comprising historical data points from all links in the relationship vector, except those from the given link; 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, wherein said estimator is configured to perform a method to;

run a plurality of models for the given link having a missing data point at a most recent time, wherein a model provides either estimating a value for said missing data point of said given link at a most recent time when all other neighboring links of said relationship vector have data at said most recent time, or estimating a value for said missing data point when one or more other neighboring links of said relationship vector is missing a respective data point at said most recent time,

generate from each said run model a respective associated weight matrix for said given link; and

store each respective associated weight matrix for said given link; and

said calculator is further configured to;

determine an applicable model corresponding to a current real-time traffic network condition of said links of said relationship vector; and

choose an associated estimated weight matrix of said plurality based on said applicable model, said chosen associated estimated weight matrix used by said calibrated model to determine said missing data point value for real-time traffic prediction.

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

9. A non-transitory 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 from a calibrated model representative of historical data points from all links in the relationship vector, except those from the given link; and

c) calculating a traffic prediction by using said estimated value in a deviation from a historical traffic pattern of said network, wherein the program performs the steps of;

running a plurality of models for the given link having a missing data point at a most recent time, wherein a model provides either estimating a value for said missing data point of said given link at a most recent time when all other neighboring links of said relationship vector have data at said most recent time, or estimating a value for said missing data point when one or more other neighboring links of said relationship vector is missing a respective data point at said most recent time,

generating from each said run model a respective associated weight matrix for said given link;

storing each respective associated weight matrix for said given link;

determining an applicable model corresponding to a current real-time traffic network condition of said links of said relationship vector; and

choosing an associated estimated weight matrix of said plurality based on said applicable model, said chosen associated estimated weight matrix used by said calibrated model to determine said missing data point value for real-time traffic prediction.

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

11. A non-transitory 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 from a calibrated model representative of historical data points from all links in the relationship vector, except those from the given link; 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, wherein the program performs the steps of;

running a plurality of models for the given link having a missing data point at a most recent time, wherein a model provides either estimating a value for said missing data point of said given link at a most recent time when all other neighboring links of said relationship vector have data at said most recent time, or estimating a value for said missing data point when one or more other neighboring links of said relationship vector is missing a respective data point at said most recent time,

generating from each said run model a respective associated weight matrix for said given link;

storing each respective associated weight matrix for said given link;

determining an applicable model corresponding to a current real-time traffic network condition of said links of said relationship vector; and

choosing an associated estimated weight matrix of said plurality based on said applicable model, said chosen associated estimated weight matrix used by said calibrated model to determine said missing data point value for real-time traffic prediction.