Monitoring traffic congestion

The present disclosure relates generally to computer systems, and more specifically, to a framework for monitoring traffic congestion.

Traffic congestion is a common problem for big cities all over the world. To manage traffic congestion, many big cities have built information technology (IT) systems to interpret traffic situations based on average travel speed for each road section. Average travel speed is an intuitive way to illustrate the reduction of mobility experienced during congestion, and is widely used in interpreting meso-level and macro-level traffic congestion.

Different traffic sensor data may be used in speed calculation. One type of data is the floating car data (FCD), which typically includes global positioning system (GPS) data from onboard devices in taxicabs. FCD is widely used because such data collection is effective and economical, and can be easily integrated with a geographical information system and summarized at any level.

Taxicabs are typically not equally distributed in a road network, which means there are different sample sizes for calculating average travel speed for different road sections. For extreme cases, a recognized traffic congestion point may be totally wrong as there may be only a single abnormal taxicab available for speed calculation in a certain road section. If random errors are not taken into account in speed calculation, a stable and reliable outcome cannot be determined.

A framework for monitoring traffic congestion is described herein. In accordance with one aspect of the framework, the framework receives vehicle data from vehicle data sources located in a region of interest. The framework may determine a sample size and an average speed for an edge of the region of interest based on the vehicle data. Congestion probability may then be determined based on the sample size and average speed. A report may be presented based on the congestion probability.

With these and other advantages and features that will become hereinafter apparent, further information may be obtained by reference to the following detailed description and appended claims, and to the figures attached hereto.

Some embodiments are illustrated in the accompanying figures, in which like reference numerals designate like parts, and wherein:

FIG. 1 is a block diagram illustrating an exemplary architecture;

FIG. 2 shows an exemplary method for monitoring traffic congestion;

FIG. 3 shows an exemplary table that stores the results returned by congestion monitor;

FIG. 4 shows an exemplary speed-time series and its corresponding “smoothed” state-space model for a given edge;

FIG. 5 a shows the corresponding vehicle count graph;

FIG. 5 b shows the corresponding residual graph;

FIG. 6 is a scatter plot that illustrates the relationship between inverse variance and sample size;

FIGS. 7 a -7 e show scatter plots derived from vehicle data acquired by a similar vehicle data source at 5 different areas

FIG. 8 shows an edge-speed model with confidence band;

FIG. 9 a shows a conventional traffic congestion level map;

FIG. 9 b shows a corresponding traffic congestion probability map that may be generated by congestion monitor;

FIG. 10 a shows a map that displays severely congested roads without specifying the level of confidence;

FIG. 10 b shows a map that displays severely congested roads with confidence level 80%; and

FIG. 10 c shows a map that displays severely congested roads with confidence level 95%.

In the following description, for purposes of explanation, specific numbers, materials and configurations are set forth in order to provide a thorough understanding of the present frameworks and methods and in order to meet statutory written description, enablement, and best-mode requirements. However, it will be apparent to one skilled in the art that the present frameworks and methods may be practiced without the specific exemplary details. In other instances, well-known features are omitted or simplified to clarify the description of the exemplary implementations of the present framework and methods, and to thereby better explain the present framework and methods. Furthermore, for ease of understanding, certain method steps are delineated as separate steps; however, these separately delineated steps should not be construed as necessarily order dependent in their performance.

Questions surrounding the issue of the number of vehicles (e.g., taxis) needed for edge-wise speed calculation based on FCD may include: “How many vehicle data samples are enough for speed calculation?” or “How many vehicle data samples are necessary for the speed calculation to be believable?”. While such questions are quite subjective (i.e., based on personal judgments on “enough” or “trustable”), they can be addressed from the following two perspectives: (1) Accuracy: “How does the average edge speed calculation deviate from the true speed?”; and (2) Precision: “How does the random fluctuation affect the average edge speed calculation?”. Since it is not possible to define what a “true speed” is purely by data, accuracy cannot be improved by increasing the number of vehicle data samples.

A framework for monitoring traffic congestion is described herein. One aspect of the present framework addresses the precision issue by quantifying the correlation between vehicle sample size and random error, and enhancing speed calculation and traffic congestion interpretation by considering speed deviation from random error due to limited number of data points (i.e., data samples). Random errors from sample size is a big component of systematical errors that result in deviation for average speed calculation. Such random errors may be quantified, measured and considered when interpreting traffic situations. The present framework quantifies correlation between random error and sample size, which advantageously enhances the accuracy and reliability of speed calculation and traffic situation interpretation, thereby providing a better view of traffic congestion and a more accurate identification of critically congested roads.

It should be appreciated that the framework described herein may be implemented as a method, a computer-controlled apparatus, a computer process, a computing system, or as an article of manufacture such as a computer-usable medium. These and various other features and advantages will be apparent from the following description.

FIG. 1 is a block diagram illustrating an exemplary architecture 100 in accordance with one aspect of the present framework. Generally, exemplary architecture 100 may include a computer system 106 , one or more vehicle data sources 155 and one or more client devices 156 .

Computer system 106 is capable of responding to and executing machine-readable instructions in a defined manner. Computer system 106 may include a processor 110 , input/output (I/O) devices 114 (e.g., touch screen, keypad, touch pad, display screen, speaker, etc.), a memory module 112 , and a communications card or device 116 (e.g., modem and/or network adapter) for exchanging data with a network (e.g., local area network or LAN, wide area network (WAN), Internet, etc.). It should be appreciated that the different components and sub-components of the computer system 106 may be located or executed on different machines or systems. For example, a component may be executed on many computer systems connected via the network at the same time (i.e., cloud computing).

Memory module 112 may be any form of non-transitory computer-readable media, including, but not limited to, dynamic random access memory (DRAM), static random access memory (SRAM), Erasable Programmable Read-Only Memory (EPROM), Electrically Erasable Programmable Read-Only Memory (EEPROM), flash memory devices, magnetic disks, internal hard disks, removable disks or cards, magneto-optical disks, Compact Disc Read-Only Memory (CD-ROM), any other volatile or non-volatile memory, or a combination thereof. Memory module 112 serves to store machine-executable instructions, data, and various software components for implementing the techniques described herein, all of which may be processed by processor 110 . As such, computer system 106 is a general-purpose computer system that becomes a specific-purpose computer system when executing the machine-executable instructions. Alternatively, the various techniques described herein may be implemented as part of a software product. Each computer program may be implemented in a high-level procedural or object-oriented programming language (e.g., C, C++, Java, JavaScript, Advanced Business Application Programming (ABAP™) from SAP® AG Structured Query Language (SQL), etc.), or in assembly of machine language if desired. The language may be a compiled or interpreted language. The machine-executable instructions are not intended to be limited to any particular programming language and implementation thereof. It will be appreciated that a variety of programming languages and coding thereof may be used to implement the teachings of the disclosure contained herein.

In some implementations, memory module 112 includes congestion monitor 124 and database 126 for monitoring traffic congestion. Database 126 may store, for example, vehicle data provided by one or more vehicle data sources 155 .

Computer system 106 may operate in a networked environment using logical connections to one or more vehicle data sources 155 and one or more client devices 156 . Computer system 106 may serve to collect, process and store vehicle data from one or more vehicle data sources 155 to generate vehicle-related information. Vehicle data sources 155 include devices onboard vehicles (e.g., taxis, cars, buses) that are capable of continuously streaming vehicle data to computer system 106 . In some implementations, vehicle data sources 155 include mobile devices (e.g., mobile phones) that are capable of transmitting cellular network data (e.g., code division multiple access (CDMA), global system for mobile communication (GSM), universal mobile telecommunication system (UMTS), and general packet radio service (GPRS)). Computer system 106 may distribute congestion-related information to one or more client devices 156 . Such client devices 156 may include client applications 158 configured to present a user interface (e.g., a graphical user interface) to access the congestion-related information and services, including services provided by computer system 106 .

FIG. 2 shows an exemplary method 200 for monitoring traffic congestion. The method 200 may be performed automatically or semi-automatically by the system 100 , as previously described with reference to FIG. 1 . It should be noted that in the following discussion, reference will be made, using like numerals, to the features described in FIG. 1 .

At 202 , congestion monitor 124 receives vehicle data sampled within time slot t by one or more vehicle data sources 155 located in a region of interest. The region of interest may be a neighborhood, town, city or any other area with a network of edges or road segments for traveling vehicles (e.g., taxis). Each vehicle data source 155 is located in a vehicle, and may sample one or more data records during time slot t. For example, within time slot t, a vehicle data source 155 may sample and send a sequence of data records GPS 1 , GPS 2 , GPS 3 to congestion monitor 124 . Such sequential data records may then be used to determine the velocity of the vehicle associated with the vehicle data source 155 within this time slot t. Each record of the vehicle data may include a device identifier, localization data (e.g., GPS location data), speed and time information. Other types of information may also be stored in each vehicle data record. Vehicle data sources 155 may sample vehicle data at frequent time points (e.g., every 5 seconds). Congestion monitor 124 may then collect the vehicle data at the end of regularly-spaced time slots t (e.g., every 5 minutes, hourly or daily). The data collection may be performed in response to a request sent by computer system 106 to the one or more vehicle data sources 155 .

At 204 , congestion monitor 124 determines the sample size and average vehicle speed v i for each edge i based on the vehicle data. An edge i is a predefined segment of the road network of the region of interest, and may be associated with a unique identifier (EDGE_ID). Congestion monitor 124 determines the average speed v i by dividing the sum of speeds of vehicles by the sample size (i.e., number of vehicles or VEHICLE_COUNT) along edge i.

FIG. 3 shows an exemplary table 302 that stores the results returned by congestion monitor 124 . Each row in table 302 stores an edge identifier 304 , a time stamp 306 , the average speed 308 and the vehicle count 310 . The vehicle count 310 is the number of vehicles traveling along a given edge at a particular time slot, and may be referred to as the “sample size”. Quantitative analysis of precision in relation to sample size (i.e., VEHICLE_COUNT) is based on the variances (in the statistical sense) of the average speed.

Returning to FIG. 2 , at 206 , congestion monitor 124 determines the congestion probability for each edge i based on the sample size and average speed. Congestion probability provides a measure of confidence for the estimated road congestion on a given edge i. Congestion probability may be derived based on the average speed and sample size associated with edge i. The relationship between congestion probability, average speed and sample size may be derived based on the following observations: (1) The inverse of the variance of average speed is linearly related to the sample size; and (2) The linearity (or slope) is established in a certain range of sample sizes, and the linearity and range may be different for different areas.

The easiest way for estimating variance of average speed is to directly return variance at the same time when the average speed is calculated for each edge i. However, this may not be a practical option as it is too computationally intensive. Instead, variance may be estimated from an edge-wise speed time series. More particularly, the variance for average speed may be estimated by the time series residuals between data and a state-space time series model.

FIG. 4 shows an exemplary speed-time series 404 and its corresponding “smoothed” state-space model 406 for a given edge. FIG. 5 a shows the corresponding vehicle count graph, while FIG. 5 b shows the corresponding residual graph. The variance σ 2 of the average speed is inversely proportional to the number of samples, as expressed in the following equation:

σ 2 ∝ σ 1 2 N ( 1 )

where σ 1 2 is the vehicle speed variance and N is the number of samples (i.e., vehicle count or sample size). Equivalently, the inverse of the variance σ 2 of average speed is linearly related with the sample size N.

FIG. 6 is a scatter plot 602 that illustrates the relationship between inverse variance (1/σ 2 ) and sample size N. Graph 602 includes dots representing the calculated residuals for all edges throughout the day. The line 604 is a fitted line for sample size N less than 30. As can be observed, for vehicle count N less than 30, the functional form of variance (or standard error) may be represented by a straight line 604 , which follows closely to the theoretical prediction. Specially, for N≤30,

σ 2 = 164.37 N ( 2 ) σ = 12.82 N ( 3 )

wherein the value “164.37” is the inverse of the slope (or gradient) of the line 604 .

As the calculation of average speed is subject to various steps of pre-processing, the nonlinearity of the variance-sample size relationship 606 for vehicle counts exceeding 30 may be attributed to many reasons. However, as a first-order approximation, the variance-sample size relationship expressed by equation (2) can still be used.

From the above analysis, the answer to the question of “how many vehicle samples are enough for speed calculation” is dependent on “how much random error of the speed calculation you can tolerate”. For example, if we require (with 95% confidence) that the “true” speed is within 5 km/h error to the “calculated” speed, at least

( 12.8 × 1.96 5 ) 2 = 25

vehicles are needed. This is based on the assumption of normal distribution of residual errors, where the number 1.96 is the approximate value of the 97.5 percentile point of the standard normal distribution. 95% of the area under a normal curve lies within roughly 1.96 standard deviations (σ) of the mean, and due to the central limit theorem, this number 1.96 is used in the construction of approximate 95% confidence intervals. The “true” speed only has 5% chance of falling outside the “measured” speed (+/− 1.96 σ). For 10 vehicles, the random error can be as high as 8 km/h.

Other geographical areas were studied to further prove that “the inverse of the variance of average speed is linearly related to the sample size” is a general pattern. FIGS. 7 a through 7 e show scatter plots derived from vehicle data acquired by a similar vehicle data source at 5 different areas. For these 5 areas, linear fitting results are obtained. FIG. 7 a shows a scatter plot 702 for the Qihuai area, where σ=11.90/√{square root over (N)}. FIG. 7 b shows a scatter plot 704 for the Gulou area, where σ=11.72/√{square root over (N)}. FIG. 7 c shows a scatter plot 706 for the Xuanwu area, where σ=11.90/√{square root over (N)}. FIG. 7 d shows a scatter plot 708 for the Jianye area, where σ=11.72/√{square root over (N)}. FIG. 7 e shows a scatter plot 710 for the Qixia area, where σ=12.96/√{square root over (N)}.

FIG. 8 shows an edge-speed model 804 with confidence band 806 . More particularly, a speed time series 802 and an edge-speed model 804 are shown. The confidence band 806 may be directly inferred from the vehicle count. The edge-speed model 804 with confidence band 806 may be used to identify random fluctuation of speed caused by sample size difference.

Given the number of vehicle samples N i and the “calculated” speed v i , for edge i at any calculation time slot t, the distribution of “true” speed m i may be modeled by a normal probability model N as follows:

m i ∼ N ⁡ ( v i , 12.8 N i ) ( 4 )

wherein the mean of the normal distribution N is v i , and standard deviation of the normal distribution N is

12.8 N i

(see Equation (3)). The value “12.8” is the square root of “164.37”, which is the inverse of the slope (or gradient) of the line 604 (see Equations 2 and 3). In some implementations, the value “12.8” is predetermined based on historical vehicle data. This value may vary slightly for different regions. For example, in FIGS. 7 a through 7 e , the slopes of the scatter plots ( 702 to 710 ) are very close. The value “12.8” may also be estimated online based on current vehicle data of the region of interest, and be adapted to different regions of interest.

Congestion probability may be derived by the cumulative distribution of the normal probability model N, as follows:

Pr ⁡ ( m i ≤ C ) = 1 2 [ 1 + erf ( N i 2 ⁢ C - v i 12.8 ) ] ( 5 )

wherein v i is the average speed and N i is the sample size for edge i, erf is the error function, m i is the “true” speed and C is the congestion threshold speed. Error function erf may be calculated with numerical integral techniques. C may be selected based on the standardized grade level of the edge (or road). For example, for road of grade level 1, according to the China National Standard, C is chosen to be 20 km/h.

Returning to FIG. 2 , at 210 , congestion monitor 124 presents a report of congestion probabilities. In some implementations, the report is displayed as a map of the region of interest indicating different levels of congestion according to the congestion probabilities. The map may be updated in substantially real-time by congestion monitor 124 in response to receiving and processing new vehicle data. FIG. 9 a shows a conventional traffic congestion level map 902 . Different traffic congestion levels may be indicated by a range of colors (e.g., from green to red, with red indicating severe congestion) or shades 903 (e.g., from light to dark shades, with dark shade indicating severe congestion). For example, traffic congestion levels may be classified into 5 levels according to severities: Grade 1 (red) to Grade 5 (green) corresponding to severe congestion and no congestion.

FIG. 9 b shows a corresponding traffic congestion probability map 904 that may be generated by congestion monitor 124 . The traffic congestion probability map 904 represents the same geographical area during the same time slot as map 902 . Traffic congestion probabilities for all roads over the urban network may be represented as numerical values 905 ranging from 0 to 1.

In some implementations, the traffic congestion probability map may be generated and displayed based on a user-specified or predetermined confidence level M for the most severely congested edges (e.g., congestion level 1). When no confidence level is specified, all severely congested edges are marked in the traffic congestion probability map, but the confidence levels of the edges may be a mixture of different values (from 0% to 100%); this may be distracting to traffic managers because some of these “severely congested” edges are only marked “severe” due to random fluctuations. When a predetermined confidence level M is specified (e.g., 95%), edges with confidence levels greater than and/or equal to M are marked as congested in the map. The marked edges in the map are quite likely to be congested, and traffic managers should be more focused in these regions.

FIGS. 10 a - c show various exemplary traffic congestion probability maps 1002 a - c that may be generated by congestion monitor 124 . More particularly, FIG. 10 a shows an exemplary map that displays severely congested roads 1004 a (according to the traffic condition labelling shown in FIG. 9 a ) overlaid together without specifying the level of confidence, while FIGS. 10 b and 10 c show exemplary maps that display severely congested roads 1004 b and 1004 c with confidence levels M at 80% and 95% respectively.

Returning to FIG. 2 , at 212 , congestion monitor 124 determines if it should continue to process vehicle data acquired in the next time slot (t+1). If so, the method 200 continues to 202 to receive such vehicle data and repeat steps 204 through 210 . If not, the method 200 ends.

Although the one or more above-described implementations have been described in language specific to structural features and/or methodological steps, it is to be understood that other implementations may be practiced without the specific features or steps described. Rather, the specific features and steps are disclosed as preferred forms of one or more implementations.