TRAFFIC BOTTLENECK DETECTION AND CLASSIFICATION ON A TRANSPORTATION NETWORK GRAPH

• US 20150081196A1
• Filed: 09/18/2014
• Published: 03/19/2015
• Est. Priority Date: 09/18/2013
• Status: Active Grant

• Current Assignee: Iteris Incorporated
• Original Assignee: Iteris Incorporated
• Inventors: PETTY, KARL F., MOYLAN, ANDREW J.
• Granted Patent: US 9,330,565 B2
• Time in Patent Office: Days
• US Class Current: 701/118
• CPC Class Codes: G08G 1/0133 for classifying traffic situation
• CPC Class Codes: H04W 4/027 using movement velocity, acceleration information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services

Abstract

Traffic congestion detection, classification and identification includes analysis of link-speed data representative of vehicular speed and capacity on one or more roadway segments to determine non-linear, multi-segment traffic bottlenecks in a transportation network graph. Link-speed data is processed to detect bottleneck conditions, classify bottlenecks and bottleneck-like traffic features according to their complexity, and identify sustained or recurring bottlenecks. Such a system and method of traffic congestion detection, classification and identification provides a framework for using this link-speed data to detect the head and queue of bottlenecks on a directed graph representing the transportation network, classify the resulting bottlenecks and bottleneck-like traffic features according to the shape of their queue, and identify and measure sustained or recurrent bottlenecks even when the location, or head, of the bottleneck varies slightly across multiple time periods or across multiple days.

Claims

1. A method of analyzing traffic congestion, comprising:

within a computing environment comprised of a computer processor and at least one computer-readable storage medium operably coupled to the computer processor and having program instructions stored therein, the computer processor being operable to execute the program instructions to perform the steps of;

assigning, for a roadway network represented as a directed graph in which a plurality of link-nodes connect links downstream from each node and upstream from each node, a first condition in which a vehicular speed on at least one nearby upstream link is less than a congestion threshold speed, and a second condition in which a vehicular speed on all downstream links are greater than a bottleneck speed differential plus a minimum vehicular speed of all nearby upstream links;

detecting a bottleneck head condition at a particular node where the first condition and the second condition are both satisfied;

detecting at least one bottleneck queue by initially identifying all nearby upstream links satisfying the first condition and the second condition, and including all nearby upstream links whose vehicular speed is greater than the congestion threshold speed and, for a set of vehicular speeds for links downstream of a bottleneck head node, all nearby upstream links where the set of vehicular speeds less the vehicular speed is greater than the bottleneck speed differential; and

analyzing all links that are nearby upstream of any of links already in the at least one bottleneck queue to iteratively expand each bottleneck queue, so that if the vehicular speed of a link is greater than the congestion threshold speed, then the link is added to a bottleneck queue.

2. The method of claim 1, wherein an upstream link is defined for each link-node to include all immediately-connected non-null upstream nodes within the directed graph, and wherein links for which there is no vehicular speed in a given time period are defined as null links, and wherein road links that do have vehicular speeds are defined as non-null links.

3. The method of claim 1, wherein the congestion threshold speed and the bottleneck differential speed are derived by a proportional scaling relative to at least one of a speed limit or an observed free flow speed for each link comprising the roadway network.

4. The method of claim 1, wherein the vehicular speed is link-speed data representative of speed information for one or more links in the roadway network for each of several time periods.

5. The method of claim 4, wherein the link-speed data is derived from one or more of traffic data, weather data, incident data, pavement condition data, roadway operations data, and data generated by one or more integrated traffic state estimation systems.

6. The method of claim 2, wherein if a newly-added nearby upstream link is not immediately upstream so as to be connected to the bottleneck head node, then the sequence of null links by which the link is connected to one or more of the links already in the bottleneck queue is also added to the bottleneck queue.

7. The method of claim 1, further comprising:

identifying an existence of one or more bottleneck head nodes and one or more bottleneck tail nodes in each bottleneck queue; and

classifying the at least one bottleneck queue according to a shape of each queue, the shape of each queue categorized based upon a number of bottleneck head nodes and a number of bottleneck tail nodes, each bottleneck queue classified as either a linear bottleneck, a non-linear bottleneck, or a bottleneck complex to indicate whether congestion in each bottleneck queue can be hypothesized as being solely or mainly caused by conditions at the corresponding bottleneck head location.

8. The method of claim 7, wherein a linear bottleneck is a bottleneck with exactly one bottleneck head node, and exactly one bottleneck tail node, and that is not part of any bottleneck complex.

9. The method of claim 7, wherein a nonlinear bottleneck is a bottleneck with exactly one bottleneck head node, and more than one bottleneck tail node, and that is not part of any bottleneck complex.

10. The method of claim 7, wherein a bottleneck complex is any maximal set of two or more bottlenecks in which the queue of each bottleneck in the maximal set shares one or more links with the queue of one or more of the other bottlenecks in the maximal set, and wherein a bottleneck complex has two or more bottleneck head nodes, and has one or more bottleneck tail nodes.

11. The method of claim 1, further comprising:

tracking the at least one bottleneck queue on the roadway network by analyzing the vehicular speed to recognize bottlenecks occurring at different times or on different days as part of a common recurring bottleneck, by;

defining conditions for similar bottlenecks, wherein a first bottleneck comprised of a set of detected bottlenecks for vehicular speed from a first time period and a second bottleneck comprised of a set of detected bottlenecks for vehicular speed from a second time period are similar if

     1) neither of the first or second bottlenecks are in any bottleneck complex,

     2) either a bottleneck head node of the first bottleneck lies within a queue of the second bottleneck, or a bottleneck head node of the second bottleneck lies within a queue of the first bottleneck,

     3) no other bottleneck from the set of detected bottlenecks for vehicular speed from the first time period satisfies (1) and (2) with the second bottleneck, and

     4) no other bottleneck from the set of detected bottlenecks for vehicular speed from the second time period satisfies (1) and (2) with the first bottleneck;

identifying persistent bottleneck sets from the conditions defined for the similar bottlenecks occurring on identical or nearby locations on the roadway network over a range of time periods by analyzing vehicular speed over a specified time-period sequence, wherein during an nth time period, for each detected bottleneck, if there exists a similar bottleneck from the previous time period (n−

1), and neither of the bottlenecks is a part of any bottleneck complex, and if the similar bottleneck is part of a persistent bottleneck set, then the similar bottleneck is also similar to all other bottlenecks in the set, then group the bottlenecks into the same persistent bottleneck set, and proceeding with preceding time periods up to a defined limit; and

comparing persistent bottlenecks to each other across a specific period of time to identify recurrent bottlenecks by extending a similarity between that bottlenecks to apply to persistent bottleneck sets across that specific period of time.

12. The method of claim 11, further comprising developing a plurality of spatial and temporal values to measure an extent of the recurrent bottlenecks over an observed time period, such as the median, mean, maximum values, etc., of the duration, total length, and spatio-temporal extent minutes-per-mile of a particular recurrent bottleneck.

13. The method of claim 11, further comprising developing a plurality of traffic performance metrics from the persistent bottleneck sets, the traffic performance metrics including prediction of bottleneck duration, prediction of recurring bottlenecks on the same day, and modeling of conduct and impact of maintenance activities performed on links in the roadway network in conjunction with known speed conditions to improve one or more of commuter time, worker safety, and cost management.

14. A system comprising:

a plurality of input data including link-speed data representative of vehicular speed data for one or more links in a roadway network for each of several time periods, and link-node data reflective of the roadway network as a directed graph, in which a plurality of link-nodes connect links downstream from each node and upstream from each node;

a plurality of data processing modules, executed within a computing environment by at least one computer processor and at least one computer-readable storage medium operably coupled to the at least one computer processor, the computer processor being operable to analyze traffic congestion conditions within the plurality of data processing modules, the plurality of data processing modules including;

a bottleneck detection module configured to detect a bottleneck head condition and at least one bottleneck queue;

a bottleneck classification module configured to classify the one or more bottleneck queues according to a shape of each queue;

a bottleneck identification module configured to recognize bottlenecks occurring at different times or on different days as part of a common recurring bottleneck to identify persistent bottleneck sets and recurrent bottlenecks;

a traffic congestion reporting module configured to generate output data representative of traffic congestion information for the roadway network.

15. The system of claim 14, wherein the link-speed data is derived from one or more of traffic data, weather data, incident data, pavement condition data, roadway operations data, and data generated by one or more integrated traffic state estimation systems.

16. The system of claim 14, wherein the bottleneck detection module detects a bottleneck head condition at a particular node where a first condition in which vehicular speed on at least one nearby upstream link is less than a congestion threshold speed, and a second condition in which vehicular speed on all downstream links are greater than a bottleneck speed differential plus a minimum vehicular speed of all nearby upstream links, are both satisfied, and detects at least one bottleneck queue by initially identifying all nearby upstream links satisfying the first condition and the second condition, and including all nearby upstream links whose vehicular speed is greater than the congestion threshold speed and, for a set of vehicular speeds for links downstream of a bottleneck head node, all nearby upstream links where the set of reported speeds less the reported vehicular speed is greater than the bottleneck differential speed.

17. The system of claim 14, wherein the shape of each queue is categorized based upon a number of bottleneck head nodes and a number of bottleneck tail nodes, each bottleneck queue classified as either a linear bottleneck, a non-linear bottleneck, or a bottleneck complex to indicate whether congestion in each bottleneck queue can be hypothesized as being solely or mainly caused by conditions at the corresponding bottleneck head location.

18. The system of claim 14, wherein the input data is analyzed to recognize bottlenecks occurring at different times or on different days as part of a common recurring bottleneck, and persistent bottleneck sets are identified from conditions defined for the similar bottlenecks occurring on identical or nearby locations on the roadway network over a range of time periods by evaluating the link-speed data over a specified time-period sequence.

19. The system of claim 18, wherein the bottleneck classification compares persistent bottlenecks across a specific period of time to identify recurrent bottlenecks by extending a similarity between bottlenecks to apply to persistent bottleneck sets across that specific period of time.

20. The system of claim 14, wherein the output data enables development of a plurality of traffic performance metrics, the traffic performance metrics including prediction of bottleneck duration, prediction of recurring bottlenecks on the same day, and modeling of conduct and impact of maintenance activities performed on links in the roadway network in conjunction with known speed conditions to improve one or more of commuter time, worker safety, and cost management.

21. A method of analyzing traffic congestion, comprising:

ingesting, as input data, link-speed data derived from one or more of traffic data, weather data, incident data, pavement condition data, roadway operations data, and data generated by one or more integrated traffic state estimation systems, the link-speed data indicative of vehicular speed data for one or more links in the roadway network for each of several time periods;

modeling the input data in a plurality of data processing modules within a computing environment in which the plurality of data processing modules are executed in conjunction with at least one processor, the data processing modules configured to analyze traffic congestion conditions by

1) detecting a bottleneck head condition at a particular node where a first condition in which vehicular speed on at least one nearby upstream link is less than a congestion threshold speed, and a second condition in which vehicular speed on all downstream links are greater than a bottleneck speed differential plus a minimum vehicular speed of all nearby upstream links, are both satisfied, and detecting at least one bottleneck queue by initially identifying all nearby upstream links satisfying the first condition and the second condition, and including all nearby upstream links whose vehicular speed is greater than the congestion threshold speed and, for a set of vehicular speeds for links downstream of a bottleneck head node, all nearby upstream links where the set of vehicular speeds less the vehicular speed is greater than the bottleneck differential speed,

2) classifying the at least one bottleneck queue according to a shape of each queue, the shape of each queue categorized based upon a number of bottleneck head nodes and a number of bottleneck tail nodes, each bottleneck queue classified as either a linear bottleneck, a non-linear bottleneck, or a bottleneck complex to indicate whether congestion in each bottleneck queue can be hypothesized as being solely or mainly caused by conditions at the corresponding bottleneck head location,

3) analyzing the input data to recognize bottlenecks occurring at different times or on different days as part of a common recurring bottleneck, by identifying persistent bottleneck sets from conditions defined for the similar bottlenecks occurring on identical or nearby locations on the roadway network over a range of time periods by evaluating the link-speed data over a specified time-period sequence, and comparing persistent bottlenecks to each other across a specific period of time to identify recurrent bottlenecks by extending a similarity between bottlenecks to apply to persistent bottleneck sets across that specific period of time; and

generating output data representative of traffic congestion information for the roadway network.

22. The method of claim 21, wherein the classifying further comprises identifying the number of bottleneck head nodes and the number of bottleneck tail nodes in each bottleneck queue.

23. The method of claim 21, wherein the identifying persistent bottleneck sets further comprises defining conditions for similar bottlenecks, wherein a first bottleneck comprised of a set of detected bottlenecks for vehicular speed from a first time period and a second bottleneck comprised of a set of detected bottlenecks for vehicular speed from a second time period are similar if 1) neither of the first or second bottlenecks are in any bottleneck complex, 2) either a bottleneck head node of the first bottleneck lies within a queue of the second bottleneck, or a bottleneck head node of the second bottleneck lies within a queue of the first bottleneck, 3) no other bottleneck from the set of detected bottlenecks for vehicular speed from the first time period satisfies (1) and (2) with the second bottleneck, and 4) no other bottleneck from the set of detected bottlenecks for vehicular speed from the second time period satisfies (1) and (2) with the first bottleneck,

25. The method of claim 21, wherein the output data enables traffic performance metrics from the persistent bottleneck sets, the traffic performance metrics including prediction of bottleneck duration, prediction of recurring bottlenecks on the same day, and modeling of conduct and impact of maintenance activities performed on links in the roadway network in conjunction with known speed conditions to improve one or more of commuter time, worker safety, and cost management.

24. The method of claim 24, wherein the identifying persistent bottleneck sets further comprises analyzing vehicular speed over a specified time-period sequence, wherein during an nth time period, for each detected bottleneck, if there exists a similar bottleneck from the previous time period (n−

1), and neither of the bottlenecks is a part of any bottleneck complex, and if the similar bottleneck is part of a persistent bottleneck set, then the similar bottleneck is also similar to all other bottlenecks in the set, then group the bottlenecks into the same persistent bottleneck set, and proceeding with preceding time periods up to a defined limit.