Near Real-time Traffic Routing

• US 20090043486A1
• Filed: 07/28/2008
• Published: 02/12/2009
• Est. Priority Date: 07/27/2007
• Status: Active Grant

• Current Assignee: George Mason Intellectual Properties, Inc.
• Original Assignee: George Mason Intellectual Properties, Inc.
• Inventors: Cao, Ying, Xie, Jibo, Zhou, Bin, Yang, Chaowei
• Granted Patent: US 8,103,435 B2
• Time in Patent Office: Days
• US Class Current: 701/117
• 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

A near real-time physical transportation network routing system comprising: a traffic simulation computing grid and a dynamic traffic routing service computing grid. The traffic simulator produces traffic network travel time predictions for a physical transportation network using a traffic simulation model and common input data. The physical transportation network is divided into a multiple sections. Each section has a primary zone and a buffer zone. The traffic simulation computing grid includes multiple of traffic simulation computing nodes. The common input data includes static network characteristics, an origin-destination data table, dynamic traffic information data and historical traffic data. The dynamic traffic routing service computing grid includes multiple dynamic traffic routing computing nodes and generates traffic route(s) using the traffic network travel time predictions.

Claims

1. A near real-time physical transportation network routing system comprising:

(a) a traffic simulation computing grid, the traffic simulator configured to produce traffic network travel time predictions for a physical transportation network using a traffic simulation model and common input data, the traffic simulation computing grid including a multitude of traffic simulation computing nodes, the common input data including;

(1) static network characteristics, the static network characteristics including network link information related to a multitude of road links, the multitude of road links covering at least part of the physical transportation network;

(2) an origin-destination data table, the origin-destination data table including a multitude of origin-destination travel time entries, each of the multitude of origin-destination travel time entries having;

(i) a travel time for one of the multitude of road links; and

(ii) a timestamp associated with the travel time;

(3) dynamic traffic information data, the dynamic traffic information data including data that could cause traffic delays for at least one of the multitude of road links; and

(4) historical traffic data, the historical traffic data including data related to past traffic conditions for at least one of the multitude of road links; and

(b) a dynamic traffic routing service computing grid, the dynamic traffic routing service computing grid configured to generate at least one traffic route using the traffic network travel time predictions, each of the at least one traffic route including an origin and a destination at a particular time, the dynamic traffic routing service computing grid including a multitude of dynamic traffic routing computing nodes.

2. The near real-time physical network routing system according to claim 1, wherein the physical transportation network is divided into a multitude of sections, each of the multitude of sections including:

(a) a primary zone, the primary zone covering at least one of the multitude of road links; and

(b) a buffer zone, the buffer zone covering at least one of the multitude of road links that are adjacent to the primary zone.

3. The near real-time physical network routing system according to claim 2, wherein one of the multitude of traffic simulation computing nodes is configured to predict travel times for at least one of the multitude of road links in the primary zone of a section of interest, the section of interest being at least one of the multitude of sections, using:

(a) the common input data associated with the primary zone of the section of interest; and

(b) the common input data associated with the buffer zone of the section of interest.

4. The near real-time physical network routing system according to claim 2, wherein predicted travel times for at least two of the multitude of sections are predicted using different traffic simulation computing nodes within the multitude of traffic simulation computing nodes.

5. The near real-time physical network routing system according to claim 2, further including a traffic simulation computer node coordination module configured to coordinate the assignment of at least one of the multitude of traffic simulation computing nodes to at least one of the multitude of sections.

6. The near real-time physical network routing system according to claim 2, further including a traffic simulation computer node combination module configured to combine the results from at least two of the multitude of traffic simulation computing nodes.

7. The near real-time physical network routing system according to claim 1, wherein the dynamic traffic routing service computing grid uses an extended Dijkstra'"'"'s algorithm when generating the at least one traffic route, the extended Dijkstra'"'"'s algorithm extending the Dijkstra'"'"'s algorithm.

8. The near real-time physical network routing system according to claim 1, wherein the dynamic traffic routing service computing grid utilizes at least one of the multitude of dynamic traffic routing computing nodes to respond to at least one routing request.

9. The near real-time physical network routing system according to claim 8, wherein the quantity of the at least one of the multitude of dynamic traffic routing computing nodes utilized increases with an increase in the quantity of the at least one routing request.

10. The near real-time physical network routing system according to claim 8, further in including a dynamic traffic routing computing node coordination module configured to coordinate at least one of the at least one routing request with at least one of the at least one of the multitude of dynamic traffic routing computing nodes.

11. The near real-time physical network routing system according to claim 1, wherein the physical network is a transportation network.

12. The near real-time physical network routing system according to claim 1, further including an application server, the application server configured to pass at least one of the at least one traffic route to a client.

13. The near real-time physical network routing system according to claim 1, further including a weather adjustment service, the weather adjustment service configured to use weather data from a weather effect service to update the traffic simulation model.

14. The near real-time physical network routing system according to claim 1, wherein the application server passes the traffic route to the client through a web server, the web server including:

(a) a request parser; and

(b) a response generator.

15. A tangible computer readable media, the tangible computer readable media containing a multitude of computer readable instructions that when executed by one or more processors causes the one or more processors to perform a method for determining a near real-time physical transportation network route, the method comprising:

(a) generating traffic network travel time predictions for a physical transportation network using a traffic simulation computing grid, a traffic simulation model and common input data, the traffic simulation computing grid including a multitude of traffic simulation computing nodes, the common input data including;

(1) static network characteristics, the static network characteristics including network link information related to a multitude of road links, the multitude of road links covering at least part of the transportation network;

(2) an origin-destination data table, the origin-destination data table including a multitude of origin-destination travel time entries, each of the multitude of origin-destination travel time entries having;

(i) a travel time for one of the multitude of road links; and

(ii) a timestamp associated with the travel time; and

(3) dynamic traffic information data, the dynamic traffic information data including data that could cause traffic delays for at least one of the multitude of road links; and

(4) historical traffic data, the historical traffic data including data related to past traffic conditions for at least one of the multitude of road links; and

(b) generating at least one traffic route using a dynamic traffic routing service computing grid and the traffic network travel time prediction, each of the at least one traffic route including an origin and a destination at a particular time, the dynamic traffic routing service computing grid including a multitude of dynamic traffic routing computing nodes.

16. The tangible computer readable media according to claim 15, wherein the physical transportation network is divided into a multitude of sections, each of the multitude of sections including:

(a) a primary zone, the primary zone covering at least one of the multitude of road links; and

(b) a buffer zone, the buffer zone covering at least one of the multitude of road links that are adjacent to the primary zone.

17. The tangible computer readable media according to claim 16, wherein one of the multitude of traffic simulation computing nodes is configured to predict travel times for at least one of the multitude of road links in the primary zone of a section of interest, the section of interest being at least one of the multitude of sections, using:

(a) the common input data associated with the primary zone of the section of interest; and

(b) the common input data associated with the buffer zone of the section of interest.

18. The tangible computer readable media according to claim 16, wherein predicted travel times for at least two of the multitude of sections are predicted using different traffic simulation computing nodes within the multitude of traffic simulation computing nodes.

19. The tangible computer readable media according to claim 15, wherein the dynamic traffic routing service computing grid uses an extended Dijkstra'"'"'s algorithm when generating the at least one traffic route, the extended Dijkstra'"'"'s algorithm extending the Dijkstra'"'"'s algorithm.

20. The tangible computer readable media according to claim 15, wherein the physical network is a transportation network.

21. The tangible computer readable media according to claim 15, further including to update the traffic simulation model using weather data from a weather effect service.

22. The tangible computer readable media according to claim 15, wherein the at least one traffic route is generated and forwarded to a client in response to a client request.