Method and apparatus for end-to-end travel time estimation using dynamic traffic data

• US 7,236,881 B2
• Filed: 02/07/2005
• Issued: 06/26/2007
• 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
• Primary Examiner(s): Zanelli; Michael J.
• Application Number:
  US11/052,308
• Publication Number:
  US 20060178811A1
• Time in Patent Office: 869 Days
• Field of Search: None
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968

Abstract

The present invention is a method and an apparatus for end-to-end travel time estimation using dynamic traffic data. In one embodiment, a method for estimating a fastest route between a first point in a transportation network and a second point in the transportation network includes receiving static data relating to static characteristics of a first zone and a second zone in the transportation network. In addition, real-time data relating to real-time traffic conditions in the first zone is also received. The static and real-time data is processed in accordance with at least one fine-grained load-generation technique to generate a first load for the first zone, and the static data is generated in accordance with at least one coarse-grained load-generation technique to generate a second load for the second zone. These first and second loads are then combined, converted to travel times, and scaled to facilitate the identification of a best or fastest route.

Claims

1. A method for estimating a fastest route between a first point in a transportation network and a second point in the transportation network, the method comprising:

receiving static data relating to static characteristics of a first zone and at least a second zone in said transportation network;

receiving real-time data relating to real-time traffic conditions in said first zone;

processing said static data and said real-time data in accordance with at least one fine-grained load-generation technique to generate a first load for said first zone, said first load comprising a number of vehicles traveling in said first zone per a unit of time; and

processing said static data in accordance with at least one coarse-grained load-generation technique to generate a second load for said second zone, said second load comprising a number of vehicles traveling in said second zone per a unit of time,

wherein said fastest route is estimated based on said first load and said second load.

2. The method of claim 1, wherein said static data comprises at least one of:

link load estimates, statistical traffic patterns, static origin-destination trip tables and static maps.

3. The method of claim 1, wherein said real-time data comprises at least one of:

current traffic condition data, real-time traffic condition data, environmental data and radio-based incident data.

4. The method of claim 1, wherein said at least one fine-grained load-generation technique is at least one of:

dynamic traffic assignment, a queuing network, simulation, a probabilistic local technique and flow propagation.

5. The method of claim 1, wherein said at least one coarse-grained load-generation technique is at least one of:

a template method, statistical traffic classification, traffic assignment, simulation and a probabilistic local technique.

6. The method of claim 1, wherein said first zone is an urban zone or a regional zone.

7. The method of claim 1, wherein said second zone is a rural zone or an inter-urban zone.

8. The method of claim 1, further comprising:

combining said first load and said second load to generate network-wide loads.

9. The method of claim 8, wherein said combining further comprises:

converting said network-wide loads to corresponding estimated travel times.

10. The method of claim 9, further comprising:

scaling said estimated travel times in accordance with at least one relevant incident in said transportation network.

11. The method of claim 10, wherein said at least one relevant incident is at least one of:

a traffic accident in said transportation network, occurrence at a point of interest in said transportation network, construction occurring in said transportation network and a weather condition in said transportation network.

12. The method of claim 10, further comprising:

identifying said fastest route in accordance with said scaled travel times.

13. A computer readable medium containing an executable program for estimating a fastest route between a first point in a transportation network and a second point in the transportation network, where the program performs the steps of:

receiving static data relating to static characteristics of a first zone and at least a second zone in said transportation network;

receiving real-time data relating to real-time traffic conditions in said first zone;

processing said static data and said real-time data in accordance with at least one fine-grained load-generation technique to generate a first load for said first zone, said first load comprising a number of vehicles traveling in said first zone per a unit of time; and

processing said static data in accordance with at least one coarse-grained load-generation technique to generate a second load for said second zone, said second load comprising a number of vehicles traveling in said second zone per a unit of time,

wherein said fastest route is estimated based on said first load and said second load.

14. The computer readable medium of claim 13, wherein said static data comprises at least one of:

link load estimates, statistical traffic patterns, static origin-destination trip tables and static maps.

15. The computer readable medium of claim 13, herein said real-time data comprises at least one of:

current traffic condition data, real-time traffic condition data, environmental data and radio-based incident data.

16. The computer readable medium of claim 13, wherein said at least one fine-grained load-generation technique is at least one of:

dynamic traffic assignment, a queuing network, simulation, a probabilistic local technique and flow propagation.

17. The computer readable medium of claim 13, wherein said at least one coarse-grained load-generation technique is at least one of:

a template method, statistical traffic classification, traffic assignment, simulation and a probabilistic local technique.

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

combining said first load and said second load to generate network-wide loads;

converting said network-wide loads to corresponding estimated travel times; and

scaling said estimated travel times in accordance with at least one relevant incident in said transportation network.

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

identifying said fastest route in accordance with said scaled travel times.

20. Apparatus for estimating a fastest route between a first point in a transportation network and a second point in the transportation network, the apparatus comprising:

means for receiving static data relating to static characteristics of a first zone and at least a second zone in said transportation network;

means for receiving real-time data relating to real-time traffic conditions in said first zone;

means for processing said static data and said real-time data in accordance with at least one fine-grained load-generation technique to generate a first load for said first zone, said first load comprising a number of vehicles traveling in said first zone per a unit of time; and

means for processing said static data in accordance with at least one coarse-grained load-generation technique to generate a second load for said second zone, said second load comprising a number of vehicles traveling in said second zone per a unit of time,

wherein said fastest route is estimated based on said first load and said second load.