Keywords

1 Introduction

Traffic congestion is an increasing serious problem in many metropolises all over the world. For the instance of Beijing, as the number of automobiles approaching 5.4 million in 2014, the average speeds on urban expressways are just 37.1 km/h and 32.2 km/h for the early and the late peak respectively [1], which are significantly lower than the design speed (80 km/h).

In order to effectively alleviate traffic congestion, many cities have paid large efforts to establish Intelligent Transportation Systems (ITS) in the last decade. After years of operation, a large amount of traffic data is accumulated from loop detectors, Global Positioning Systems (GPS) devices or Remote Traffic Microwave Sensors (RTMS). Such traffic data can be seen as spatio-temporal series, which is a set of continuous observations of traffic flow on roads correlated with each in the network [2,3,4,5].

However, with the devices and facilities of ITS getting mature and completed, the lack of effective methods on information fusion and exaction based on traffic data restricts the development and effectiveness of ITS. The success of ITS is very dependent on the quality of traffic information, and one of the critical needs is to recognize traffic condition [6]. Especially, traffic condition identification is also a crucial foundation to improve the managerial level and effectiveness for traffic management departments.

Most traffic operation centers classify traffic conditions into congested traffic and uncongested traffic, while congestion can be further divided into two types by many researchers: recurrent congestion and non-recurrent congestion [7,8,9]. According to the physical characteristics, traffic conditions can also be classified into three groups: free flow, wide moving jam and synchronized flow [10, 11]. As traffic congestion usually spreads from a certain road to others in the network, it’s more meaningful for traffic managers how traffic conditions on different roads are correlated and distributed in space and time than what the traffic condition it is at a certain location and time.

Spatio-temporal object whose characteristics are various over space and time has got extensive applications in space and time study [12]. In spatial econometrics, it is thought that the properties of a spatio-temporal object are always related to that of the others adjacent to it in space-time, which can be called spatio-temporal autocorrelation and measured by indicators such as space-time autocorrelation index [13], spatio-temporal Moran’s I [14, 15], Spatio-temporal autocorrelation and partial autocorrelation functions [16]; Kamarianakis and Prastacos [17]. So, the spatio-temporal autocorrelation analysis of traffic can provide an insight into the correlative structure of urban traffic condition.

Spatio-temporal clustering aims at recognizing the groups of spatio-temporal objects with similar characteristics and features [18]. The spatio-temporal clustering algorithm mainly falls into three types: scan statistics method [19, 20], density-based method [21, 22] and distance-based method (Kulldrff and Hialmars [23, 24]. There are widespread applications of spatio-temporal clustering in many fields such as public health and safety [19, 20], earthquake monitoring [21, 22] and climate change [25, 26].

The purpose of this paper is to develop a spatio-temporal clustering method to study the distribution of different traffic condition. As traffic conditions on different roads are generally correlated in space and time, we use an improved spatio-temporal Moran scatterplot (STMS) to make a classification of urban traffic conditions firstly. A novel spatio-temporal clustering method combining pre-classified with STMS is then developed. Finally, the case studies of Beijing are conducted to demonstrate the feasibility and effectiveness of proposed method.

2 Urban Traffic Condition Classification

Generally, traffic congestions are not local or static phenomena, they do spread from a certain road to others in the network. Therefore, for traffic managers, it’s more meaningful how traffic conditions on different roads are correlated in space and time than what the traffic condition it is at a certain location and time. In this section, an improved spatio-temporal Moran scatterplot (STMS) is proposed to explore the local spatio-temporal correlation of urban traffic, and further to make a classification.

2.1 Improved Spatio-Temporal Moran Scatterplot

Moran’s I is proposed by Moran in [27] to study spatial autocorrelation, which has got extensive application with the contribution of researchers latter [14, 15, 28,29,30,31]. As a local analysis method of spatial autocorrelation, Moran scatterplot (MS) was derived from Moran’s I by Anselin in [32]. We extend spatial MS to the aspect of space-time, called spatio-temporal Moran scatterplot (STMS), to study the local spatio-temporal correlation of urban traffic conditions.

The condition at a specific spatial unit p and a particular time point i can be defined as a spatio-temporal object \(ST_{{\left( {p,i} \right)}}\). According to traditional MS, \(Wz_{(p,i)}\) and \(Z_{(p,i)}\) in the improved STMS can be formulated as follows.

$$Wz_{(p,i)} = \frac{{\mathop \sum \nolimits_{q = 0}^{N} \mathop \sum \nolimits_{j = 0}^{T} w_{{\left( {p,i} \right)\left( {q,j} \right)}} Z_{(q,j)} }}{{\mathop \sum \nolimits_{q = 0}^{N} \mathop \sum \nolimits_{j = 0}^{T} w_{{\left( {p,i} \right)\left( {q,j} \right)}} }}$$
(1)
$$Z_{(p,i)} = \frac{{(y_{{\left( {p,i} \right)}} - \bar{y})}}{{\sqrt {\frac{{\mathop \sum \nolimits_{p = 0}^{N} \mathop \sum \nolimits_{i = 0}^{T} \left( {y_{{\left( {p,i} \right)}} - \bar{y}} \right)^{2} }}{NT - 1}} }}$$
(2)

where \(Z_{{\left( {p,i} \right)}}\) is the standardized attribute value of \(ST_{{\left( {p,i} \right)}}\), and \(Wz_{{\left( {p,i} \right)}}\) is the weighted standardized attribute value of its spatio-temporal neighbors. N and T define the number of spatial units and time points studied respectively. \(w_{{\left( {p,i} \right)\left( {q,j} \right)}}\) is a binary variable which denotes the spatio-temporal adjacent relationship between spatio-temporal object \(ST_{{\left( {p,i} \right)}}\) and \(ST_{{\left( {q,j} \right)}}\). \(y_{{\left( {p,i} \right)}}\) represents the studied attribute of \(ST_{{\left( {p,i} \right)}}\) and \(\bar{y}\) indicates the average value of all spatio-temporal objects.

Using \(Z_{{\left( {p,i} \right)}}\) and \(Wz_{{\left( {p,i} \right)}}\) as abscissa and ordinate respectively, spatio-temporal object can be mapped to a point in this two-dimensional coordinates plane, which forms the spatio-temporal Moran scatterplot (STMS). In STMS, point located in the first quadrant means that the studied attribute value of both spatio-temporal object and its neighbors are significantly higher than the average, and point in the third quadrant means that spatio-temporal object and its neighbors are both relatively lower than the average level in studied attribute. The second quadrant shows that spatio-temporal object takes low value of studied attribute with its neighbors having high values, while the forth quadrant illustrates the opposite.

2.2 Traffic Condition Classification with STMS

The speed of traffic flow can quantitatively reflect the performance of urban road traffic, and is strongly related to travel time at a certain road section. Compared with the travel time data that are relatively difficult to be directly measured in a large-scale network, speed data are readily collected by monitoring system [6]. Considering the variance of travel speed on different type of road, a relative speed through the hundredfold ratio of the actual speed to design speed is used as indicator to evaluate traffic condition.

For urban traffic, spatio-temporal object can be defined as the traffic condition at a certain road and time. Taking the relative speed ratio as the studied attribute of spatio-temporal object, traffic condition can be preliminarily divided into two types: congested traffic and uncongested traffic. According to STMS, traffic conditions can be further divided into 4 types as shown in Table 1.

Table 1 Traffic condition classification with STMS
Full size table

To further explain the classification above, the distribution of 4 kinds of traffic condition for the Second Ring Road in Beijing are shown as Fig. 1. As seen in Fig. 1, the homogenous uncongested traffic clusters at the midnight. While during the peak hours, there are mainly spatio-temporal objects with homogenous congested traffic.

Fig. 1
figure 1

Distribution of 4 kinds of traffic condition of the second ring road in Beijing

Full size image

In the off-peak hours of the day, heterogeneous uncongested and congested traffic are majority. Roads with heterogeneous uncongested traffic tend to become congested earlier and get uncongested later than its neighbours during peak hours, which are bottlenecks in the network. While roads with heterogeneous congested traffic become congested later and get uncongested earlier, which play the role of dredging congestion in the network. So, the STMS can effectively reveal the spatio-temporal correlation structure of traffic condition and recognize road where congestion originates or gets alleviated in the road network.

3 Spatio-Temporal Clustering Method Combining Pre-classification

Spatio-temporal objects with the same kind of traffic condition tend to aggregate in space and time in Fig. 1, so we can use spatio-temporal clustering to further analyze the distribution of urban traffic. According to STMS, as each kind of traffic condition has distinct characteristics, it is more reasonable to take traffic condition classification as clustering basis rather than the raw traffic data. In this section, an automatic clustering method combining pre-classification with STMS is proposed.

3.1 Pre-classification of Traffic Condition

On the basis of STMS, traffic conditions can be pre-classified into four classes: homogenous uncongested traffic, heterogeneous uncongested traffic, homogenous congested traffic and heterogeneous congested traffic, represented by the integer value from 1 to 4 of \(m_{(p,i)}\) respectively:

$$m_{{\left( {p,i} \right)}} = \left\{ {\begin{array}{*{20}l} 1 \hfill & {Z_{{\left( {p,i} \right)}} \ge 0\,and\,Wz_{{\left( {p,i} \right)}} \ge 0} \hfill \\ 2 \hfill & {Z_{{\left( {p,i} \right)}} < 0\,and\,Wz_{{\left( {p,i} \right)}} \ge 0} \hfill \\ 3 \hfill & {Z_{{\left( {p,i} \right)}} < 0\,and\,Wz_{{\left( {p,i} \right)}} < 0} \hfill \\ 4 \hfill & {Z_{{\left( {p,i} \right)}} \ge 0\,and\,Wz_{{\left( {p,i} \right)}} < 0} \hfill \\ \end{array} } \right.$$
(3)

For the purpose of making adjacent spatio-temporal objects with similar characteristics one cluster, the distance in similarity sense between pair of spatio-temporal objects should be computed firstly. For \(ST_{{\left( {p,i} \right)}}\) and \(ST_{{\left( {q,j} \right)}}\), their distance \(d_{(p,i)(q,j)}\) can be calculated as Eq. (4).

$$\begin{array}{*{20}l} {d_{(p,i)(q,j)} = 1 - w_{(p,i)(q,j)} \, \times \,\delta_{k} (m_{(p,i)} ,m_{(q,j)} )} \hfill \\ {\delta_{k} (m_{(p,i)} ,m_{(q,j)} ) = \left\{ {\begin{array}{*{20}l} 1 \hfill & {if\,m_{(p,i)} = m_{(q,j)} } \hfill \\ 0 \hfill & {else} \hfill \\ \end{array} } \right.} \hfill \\ \end{array}$$
(4)

In Eq. (4), \(d_{(p,i)(q,j)}\) is a binary variable because \(w_{(p,i)(q,j)}\) and \(\delta_{k} (m_{(p,i)} ,m_{(q,j)} )\) are both binary. \(w_{(p,i)(q,j)}\) represents the spatio-temporal adjacent relation between \(ST_{{\left( {p,i} \right)}}\) and \(ST_{{\left( {q,j} \right)}}\) as mentioned earlier, while \(\delta_{k} (m_{(p,i)} ,m_{(q,j)} )\) denotes the consistency of traffic condition classification between \(ST_{{\left( {p,i} \right)}}\) and \(ST_{{\left( {q,j} \right)}}\).

3.2 Spatio-Temperal Clustering Method

To facilitate clustering calculation, the logical operations: spatio-temporal link and spatio-temporal subordination are introduced.

Spatio-temporal link: if \(d_{(p,i)(q,j)} = 0\), spatio-temporal object \(ST_{{\left( {p,i} \right)}}\) and \(ST_{{\left( {q,j} \right)}}\) are spatio-temporally linked to each other, represented by \(ST_{{\left( {p,i} \right)}} \leftrightarrow ST_{{\left( {q,j} \right)}}\).

Spatio-temporal subordination: For spatio-temporal object \(ST_{{\left( {p,i} \right)}}\) and a collection \(SP\_Set\) of spatio-temporal objects \((ST_{{\left( {p,i} \right)}} \notin SP\_Set)\), if there is any spatio-temporal object \(ST_{{\left( {q,j} \right)}}\) in \(SP\_Set\) satisfying \(ST_{{\left( {p,i} \right)}} \leftrightarrow ST_{{\left( {q,j} \right)}}\), then \(ST_{{\left( {p,i} \right)}}\) subordinates to \(SP\_Set\), denoted by \(ST_{{\left( {p,i} \right)}} \to SP\_Set\).

Meanwhile, in the process of clustering, the spatio-temporal object chosen as the first element of a new cluster is called spatio-temporal kernel. Not all spatio-temporal objects can be chosen as spatio-temporal kernel, and only those spatio-temporally linked to a larger number of spatio-temporal objects than a certain lower limit value ε can possibly become spatio-temporal kernel, called candidate spatio-temporal kernel.

3.2.1 Algorithm Flowchart of Spatio-Temporal Clustering

The automatic clustering process combining pre-classification with STMS is schematized as Fig. 2, and the main steps are as follows.

Fig. 2
figure 2

Spatio-temporal clustering process combining pre-classification with STMS

Full size image

  • Step 1: Determine the pre-classification value \(m_{(p,i)}\) of every spatio-temporal object based on STMS.

  • Step 2: Calculate the distance \(d_{(p,i)(q,j)}\) in similarity sense between each pair of spatio-temporal objects.

  • Step 3: Build the distance matrix of all spatio-temporal objects with \(d_{(p,i)(q,j)}\), and count the number of other spatio-temporal objects each spatio-temporal object \(ST_{{\left( {p,i} \right)}}\) spatio-temporally linked to, denoted by \(Ln_{{\left( {p,i} \right)}}\).

  • Step 4: Find the largest \(Ln_{{\left( {p,i} \right)}}\) value \(\hbox{max} (Ln_{{\left( {p,i} \right)}} )\), and compare it to the threshold value ε. There will be two conditions:

  1. (1)

    If \(\hbox{max} (Ln_{{\left( {p,i} \right)}} )\) is greater than or equals ε, set the spatio-temporal object (or any one of spatio-temporal objects) with the largest \(Ln_{{\left( {p,i} \right)}}\) value as the spatio-temporal kernel of a new spatio-temporal cluster \(SP\_Set\). And then, add all spatio-temporal objects spatio-temporally subordinating to the new cluster in it recurrently. Restart this step to construct another cluster.

  2. (2)

    If \(\hbox{max} (Ln_{{\left( {p,i} \right)}} )\) is less than ε, no candidate spatio-temporal kernel remains. So the clustering process is finished with all the spatio-temporal objects left considered to be discrete points.

3.2.2 Parameter Calibration

As a threshold to determine whether a spatio-temporal object is an candidate spatio-temporal kernel or not, with the increase of ε value, there are fewer candidate spatio-temporal kernels, which decreases the spatio-temporal clusters and increases the discrete points in clustering result. While in clustering analysis, it’s usually wished that some kind of stable patterns with both few clusters and discrete points are found, so a series of exploratory clustering computations with different values of ε are conducted to find the proper value of it.

Assume that B is the collection of all possible values of ε. C and O represent the collections of clusters and discrete points numbers respectively through exploratory clustering computations. When ε taking value of \(B_{i}\) in B, the corresponding numbers of clusters and discrete points are \(C_{i}\) and \(O_{i}\) respectively, so the utility of this exploratory clustering with ε taking value of \(B_{i}\) can be calculated as Eq. (5).

$$U_{{(B_{i} )}} = \frac{{C_{i} - Mean(C)}}{Sd(C)} + \frac{{O_{i} - Mean(O)}}{Sd(O)}$$
(5)

where \(Mean(C)\) and \(Sd(C)\) are the average value and standard deviation of cluster numbers respectively. Similarly, \(Mean(O)\) and \(Sd(O)\) are average value and standard deviation of the numbers of discrete points. The utility of clustering result is hoped to be as small as possible, so there will be few clusters and discrete points.

4 Case Studies

Case studies of three urban expressways from the Second Ring Road to Fourth Ring Road in Beijing are carried out with the proposed spatio-temporal clustering method. The parameter ε is firstly calibrated through a series of exploratory clustering computations. And then, the clusters for 4 kind of traffic condition are presented and discussed.

4.1 Setup and Parameter Calibration

For each of the 3 expressways, two directions including the inner-ring (clockwise direction) and the outer-ring (counterclockwise direction) are studied respectively. The studied attribute is the average relative speed of Mondays in 2012. The studied expressways are all consist of road sections laid end to end, so every spatio-temporal object may have 8 spatio-temporal neighbors at least as shown in Fig. 3. Then the parameter ε can possibly take integer values from 1 to 8 to ensure that there is no spatio-temporal object certainly to become a single cluster or discrete point.

Fig. 3
figure 3

Spatio-temporal object and its neighbors in space-time

Full size image

The results of exploratory clustering are presented in Table 2. For the average number of clusters or discrete points, there are no significant differences between the inner-ring and outer-ring of each expressway. However, the average numbers of clusters and discrete points show a tendency of increase from urban center to surrounding suburbs (from the Second Ring Road to Fourth Ring Road). This is because that, the land utilization is usually more intensive in urban centers, so there is a higher spatio-temporal aggregation for same kinds of traffic condition in urban centers than the suburbs.

Table 2 Results of exploratory clustering for the studied three urban expressways
Full size table

On the other hand, the proper ε value in Table 2 decreases with the location away from urban centers, which is contrary to the rule of the average number of clusters or discrete points. This is because that in suburbs with low spatio-temporal aggregation of traffic, a low ε value is enough to get the best clustering result, while a strict condition with high ε value can also get effective clustering result in urban centers where there are high spatio-temporal aggregation of traffic condition.

4.2 Clustering Results Combining Pre-classification

On the basis of the calibrated ε values for both directions of the 3 urban expressways, spatio-temporal clustering analyses are conducted. The spatio-temporal cloud maps of clustering results are shown in Fig. 4. According to STMS, traffic conditions are pre-classified into four types: homogenous uncongested traffic, heterogeneous uncongested traffic, homogenous congested traffic and heterogeneous congested traffic.

Fig. 4
figure 4

Spatio-temporal cloud maps of traffic condition clusters for 3 expressways

Full size image

In Fig. 4, clusters of homogenous uncongested traffic are mainly distributed at the midnight between 0:00 and 6:00, while homogenous congested traffic clusters congregate in peak hours. The heterogeneous traffic clusters scatter around the rush hours in the daytime as some kind of transitional state between homogenous uncongested and congested traffic. While in space, with the location getting away from urban centers, the cluster size of homogenous congested traffic decreases, with the sizes of the clusters for discrete point and homogenous uncongested traffic increasing. This illustrates that, with the location away from urban centers with intensive land utilization, the spatio-temporal correlation of traffic condition gradually becomes weakened, and the traffic congestion getting alleviated too.

Furthermore, road sections with heterogeneous uncongested traffic in Fig. 4 tend to become congested earlier and get uncongested later than others, which are bottlenecks in the road network. While road sections with heterogeneous congested traffic become congested later and get uncongested earlier, which play the role of dredging congestion during peak hours. Through a closer inspection, almost every road section presents only one kind of heterogeneous traffic (the congested and uncongested) in the whole day, which illustrates that each road section in the network plays a relatively stable role in undertaking the daily traffic load.

4.3 Analysis and Discussion

In order to compare 4 kinds of traffic condition clusters with the realistic travel behaviors in the road network of Beijing, the moving trajectories of taxis with passenger on Mondays in November 2012 are also studied, as shown in Fig. 5. In detail, the trajectories of taxis in 4 durations: midnight, morning peak, noon and evening peak, are selected to study the daily change of travel behavior distribution.

Fig. 5
figure 5

Moving trajectories of taxis with passenger in the road network of Beijing

Full size image

In Fig. 5a, it can be found that travel behaviors are sparse between 0:00 and 2:00, so almost all road sections present homogenous uncongested traffic in Fig. 4. On the other hand, the aggregation of travel behaviors at peak hours in Fig. 5b and d is stronger than other times, which causes that clusters of homogenous congested traffic are mainly distributed in the peak hours in Fig. 4. While between 11:00 and 13:00, travel behaviors become less congregated than peak hours, so the spatio-temporal correlation of traffic condition becomes weakened and traffic congestion gets alleviated.

While in space, according to the urban land use characteristics, there are more intensive points of traffic generation and attraction at urban centers than the suburbs, so a large amount of trajectory points congregate at the urban centers in Fig. 5b and d. Consequently, in urban centers, the correlation of traffic condition is higher than the suburbs. With the location away from urban centers, travel behaviors get sparser, so the spatio-temporal correlation of traffic condition becomes weakened gradually, and the traffic congestion gets alleviated as well in Fig. 4.

At the midnight (Fig. 5a), the volume of taxis in two hours is less than 25 at most road sections, but it may exceed 75 at some road sections in the east of the city. Further investigation reveals that, these road sections are near the famous Sanlitun Bar Street, where intensive travel behaviors last late into wee hours. This explains why road Sect. 5 (from Dongzhimenqiao to Dongsishitiaoqiao) and road Sect. 10 (from Guangqumenqiao to Guangmingqiao) at the east of the Second Ring Road in Fig. 4a are with heterogeneous uncongested traffic, whose traffic capacities should be improved to alleviate congestion.

5 Conclusions

Research on the traffic condition and its spatio-temporal distribution are crucial issues for Advanced Traffic Management Systems. A spatio-temporal clustering method combining pre-classification of traffic condition with STMS is proposed. Then the case studies of 3 urban expressways in Beijing are performed to verify the effectiveness of the proposed methodology. Through the case studies, some findings can be summarized as follows.

  1. (1)

    With the location away from the urban centers, travel behaviors become more sparse, so traffic congestion get alleviated and the spatio-temporal correlation of traffic condition becomes weakened as well.

  2. (2)

    When congestion forming and dissipating, travel behaviors become less congregated, so the traffic conditions of the whole network get heterogeneous in space-time. Road sections with heterogeneous uncongested traffic are bottlenecks of the network whose traffic capacities should be improved, while others with heterogeneous congested traffic can play congestion dredging role during peak hours.

So, the spatio-temporal clustering method combining STMS can not only effectively reveal the relation of traffic demand to road network facilities, but also recognize the road sections where congestion originates or gets alleviated in the network. This provides foundations for traffic managers to alleviate congestion and improve urban transport services. Further studies are being considered to construct the quantitative model for the degree of traffic dredging or bottleneck effect of specific road section.