Stream Processing Based Intelligent Transport Systems

• US 20090048776A1
• Filed: 06/02/2008
• Published: 02/19/2009
• Est. Priority Date: 06/01/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines SA (International Business Machines Corporation)
• Inventors: Feblowitz, Mark David, Liu, Zhen, Ranganathan, Anand, Bouillet, Eric
• Granted Patent: US 8,768,612 B2
• Time in Patent Office: Days
• US Class Current: 701/210
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G08G 1/0969 having a display in the form of a map

Abstract

A stream processing system for processing a routing request specifying a first location and a destination location in a network of interconnected locations includes a plurality of data processing elements, a memory connected to the plurality of data processing elements for storing a plurality of maps having different scopes, wherein each of the data processing elements is associated with one of the plurality of maps and determines a section of a path from the first location to the destination location in the network of interconnected locations, and a routing selection element for merging the sections of the path as a solution to the routing request.

Claims

1. A stream processing system for processing a routing request specifying a first location and a destination location in a network of interconnected locations, comprising:

a plurality of data processing elements;

a memory connected to the plurality of data processing elements for storing a plurality of maps having different scopes, wherein each of the data processing elements is associated with one of the plurality of maps and determines a section of a path from the first location to the destination location in the network of interconnected locations; and

a routing selection element for merging the sections of the path as a solution to the routing request.

2. The stream processing system of claim 1, wherein the data processing elements annotate the sections with summary information that can be used by subsequent ones of the plurality of data processing elements to select path sections for improvement.

3. The stream processing system of claim 1, wherein the data processing elements approximate the sections for a scope having greater detail than the associated map.

4. The stream processing system of claim 1, wherein the data processing elements compute the sections in predetermined regions of the network.

5. The stream processing system of claim 1, wherein the data processing elements delineate a corridor in the network and compute path sections only within the corridor.

6. The stream processing system of claim 1, wherein the path is selected for one of a shortest path, a min-congestion path, a plurality of diverse paths, a constrained path.

7. The stream processing system of claim 1, wherein the data processing elements are connected in groups, wherein each group shares maps having a substantially similar scope.

8. A computer readable medium embodying instructions executable by a processor to perform a method for processing a routing request, the method steps comprising:

receiving the routing request from an input stream, wherein the routing request specifies a unique request identification, a first location and a destination location in a network of interconnected locations;

computing, by a first routing module, an initial path between the first location and the destination location in the road network using a first map have a first scope;

transmitting the initial path to a subsequent routing module;

refining, by the subsequent routing module, the initial path using a subsequent map having a second scope comprising greater detail than the first scope to determine a refined path;

transmitting the initial path and the refined path to a routing selection module;

computing, by the routing selection module, a final end-to-end path as a merge of the initial map and the refined path; and

outputting the final end-to-end path.

9. A computer readable medium of claim 8, wherein the method further comprises distributing a plurality of routing requests including the routing request between duplicated modules.

10. A computer readable medium of claim 8, wherein

the initial path comprises a set of virtual links, the method further comprising replacing the virtual links with physical links to determine the refined path.

11. A computer readable medium of claim 8, wherein the method further comprises computing alternate paths for at least one of the initial path, the refined path, and the final end-to-end path.

12. A computer readable medium of claim 8, wherein the method further comprises computing the final end-to-end path after a predetermined time to receive additional refined paths.

13. A computer readable medium of claim 12, wherein the predetermined time is no longer than a timeout value after receiving the initial path and the refined path at the routing selection module.

14. A computer readable medium embodying instructions executable by a processor to perform a method for processing a routing request, the method steps comprising:

receiving the routing request wherein the routing request specifies a first location and a destination location in a network of interconnected locations;

determining an initial path between the first location and the destination location in the network using a first map of a first scope;

refining the initial path using a subsequent map having a second scope comprising greater detail than the first scope to determine a refined path;

determining an end-to-end path as a merge of the initial path and the refined path; and

outputting the end-to-end path.

15. A computer readable medium of claim 14, wherein the method further comprises distributing a plurality of routing requests including the routing request between duplicated modules.

16. A computer readable medium of claim 14, wherein the initial path comprises a set of virtual links, the method further comprising replacing the virtual links with physical links to determine the refined path.

17. A computer readable medium of claim 14, wherein the method further comprises computing alternate paths for at least one of the initial path, the refined path, and the end-to-end path.

18. A computer readable medium of claim 14, wherein the method further comprises computing the end-to-end path after a predetermined time to receive additional refined paths.

19. A computer readable medium of claim 14, wherein refining the initial path further comprises receiving a route condition, wherein the refined path is determined according to the subsequent map and the route condition.