Method and apparatus for estimating real-time travel times over a transportation network based on limited real-time data

• US 7,894,980 B2
• Filed: 02/07/2005
• Issued: 02/22/2011
• Est. Priority Date: 02/07/2005
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Wynter, Laura, Zhang, Li, Liu, Zhen
• Primary Examiner(s): Keith; Jack
• Assistant Examiner(s): Dager; Jonathan M
• Application Number:
  US11/052,310
• Publication Number:
  US 20060176817A1
• Time in Patent Office: 2,206 Days
• Field of Search: 340/988, 340/995.1, 340/995.12, 340/995.13, 342/454, 342/456, 701117-119, 701200-214
• US Class Current: 701/118
• CPC Class Codes: G08G 1/0104 Measuring and analyzing of parameters relative to traffic conditions
• CPC Class Codes: G08G 1/096816 where the complete route is transmitted to the vehicle at once
• CPC Class Codes: G08G 1/096827 where the route is computed onboard
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]

Abstract

The present invention is a method and an apparatus for estimating real-time travel times or traffic loads (e.g., traffic flows or densities) over a transportation network based on limited real-time data. In one embodiment, a method for estimating a travel time over a transportation network comprising at least a first link and a second link includes receiving a data feed associated with a real-time traffic flow over the first link, estimating a first travel time over the first link based at least in part on the data feed, and estimating a second travel time over the second link, also based at least in part on the data feed. The method assumes that a real-time data feed is not available for the second link, and thus estimates the traffic flow over the second link based on the known traffic flow over the first link and other known data, such as historical traffic patterns and physical parameters of the transportation network.

Claims

1. A method for estimating a travel time over a transportation network comprising a plurality of links including at least a first link and a second link and a plurality of nodes at which two or more of the plurality of links intersect, the method comprising:

receiving at least one data feed associated with a real-time traffic flow over said first link;

estimating a first travel time over said first link based at least in part on said at least one data feed;

estimating a second travel time over said second link based at least in part on said at least one data feed;

observing data representative of an inconsistent traffic flow on one or more of said first link and said second; and

responsive to said observing, using said data representative of said inconsistent traffic flow to generate an artificial node in said transportation network that is different from said plurality of nodes, where said artificial node merges one or more characteristics of two or more of said plurality of nodes and incorporates said one or more of said first link and said second link.

2. The method of claim 1, wherein a real-time data feed is not available for said second link.

3. The method of claim 1, wherein said estimating said first travel time and said second travel time comprises:

obtaining one or more static transportation network parameters; and

applying said real-time traffic flow to said one or more static transportation network parameters.

4. The method of claim 3, wherein said one or more static transportation network parameters comprise at least one of:

a number of links in said transportation network, locations of said links in said transportation network, a number of nodes in said transportation network, locations of said nodes in said transportation network, free-flow speeds in said transportation network, likely origins in said transportation network and likely destinations in said transportation network.

5. The method of claim 3, wherein said receiving further comprises:

obtaining link flows for all links in said transportation network for an average time period in said transportation network;

determining splitting probabilities for all nodes in said transportation network in accordance with said link flows; and

applying said real-time traffic flow to said splitting probabilities for each of said nodes.

6. The method of claim 5, wherein said applying further comprises:

propagating said real-time traffic flows throughout said transportation network.

7. The method of claim 6, wherein said propagating is performed in accordance with one or more flow balance equations.

8. The method of claim 5, wherein said link flows are derived from at least one origin-destination trip table representative of traffic patterns during said average time period in said transportation network.

9. The method of claim 8, wherein said link flows are derived from a traffic assignment computed for said at least one origin-destination trip table.

10. The method of claim 1, wherein the artificial node suppresses all links between said two or more of said plurality of nodes.

11. The method of claim 1, wherein the artificial node is generated dynamically in accordance with said real-time traffic flow.

12. The method of claim 1, further comprising:

updating said first travel time and said second travel time in accordance with said artificial node.

13. The method of claim 12, wherein said updating comprises:

calculating one or more updated splitting probabilities at said artificial node; and

applying said one or more updated splitting probabilities to said inconsistent traffic flow.

14. The method of claim 1, wherein data regarding a real-time traffic flow over said second link is unavailable.

15. The method of claim 1, wherein said at least one data feed is received from a sensor placed in a location along said first link.

17. The method of claim 1, wherein the artificial node is generated using only observed data relating to said real-time traffic flow.

16. A computer readable storage medium containing an executable program for estimating a travel time over a transportation network comprising a plurality of links including at least a first link and a second link and a plurality of nodes at which two or more of the plurality of links intersect, where the program performs steps of:

receiving at least one data feed associated with a real-time traffic flow over said first link;

estimating a first travel time over said first link based at least in part on said at least one data feed;

estimating a second travel time over said second link based at least in part on said at least one data feed;

observing data representative of an inconsistent traffic flow on one or more of said first link and said second link; and

responsive to said observing, using said data representative of said inconsistent traffic flow to generate an artificial node in said transportation network that is different from said plurality of nodes, where said artificial node merges one or more characteristics of two or more of said plurality of nodes and incorporates said one or more of said first link and said second link.