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

• US 20060176817A1
• Filed: 02/07/2005
• Published: 08/10/2006
• 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
• Granted Patent: US 7,894,980 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• 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 at least a first link and a second link, 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 data feed; and

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

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

obtaining one or more static transportation network parameters;

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

3. The method of claim 2, 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.

4. The method of claim 2, 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.

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

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

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

7. The method of claim 4, 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.

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

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

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

11. A computer readable medium containing an executable program for estimating a travel time over a transportation network comprising at least a first link and a second link, where the program performs the 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 data feed; and

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

12. The computer readable medium of claim 11, wherein estimating said first travel time and said second travel time comprises:

obtaining one or more static transportation network parameters;

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

13. The computer readable medium of claim 12, 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.

14. The computer readable medium of claim 12, 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.

15. The computer readable medium of claim 14, wherein said applying further comprises:

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

16. The computer readable medium of claim 15, wherein said propagation is performed in accordance with one or more flow balance equations.

17. The computer readable medium of claim 14, 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.

18. The computer readable medium of claim 17, wherein said link flows are derived from a traffic assignment computed for said at least one origin-destination trip table.

19. The computer readable medium of claim 11, wherein said data feed is received from a sensor placed in a location along said first link.

20. Apparatus for estimating a travel time over a transportation network comprising at least a first link and a second link, the apparatus comprising:

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

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

means for estimating a second travel time over said second link based at least in part on said data feed.