In this step, the goal is to define the graph connectivity between two signalized intersections in the network that takes into account both the shortest path distance and the spatial connectivity. As we mentioned, the connectivity between two intersections is ambiguous without clear definition. For instance, whether or not two signalized intersections that there is one or several unsignalized intersections located on the link between them have connectivity. Whether or not two signalized intersections that are spatial connected by a quite long link have connectivity. Therefore, the method to define the graph connectivity between two signalized intersections is needed and proposed here.

At first, we compute the distance of the shortest path between two signalized intersections. We model each intersection including signalized and unsignalized as a node and build their initial neighboring relationships based on their spatial connections. Specifically, the road network is abstracted as a directed graph G. Each node i in G represents an intersection in the network and the distance d(i,j) is denoted by the length of the shortest path r(i,j) from node i to j in g. The link matrix {a(i,j)} measures the spatial neighboring relation and length between each pair of nodes, with a(i,j) = 0.1 denoting that nodes i and j are adjacent and the length of directed link from i to j is 0.1 km. If nodes i and j are not adjacent or if there is only a link from j to i but no link from i to j, then a(i,j) = ∞. Thus the distance d(i,j) is calculated by Dijkstra's algorithm based on the link matrix.

Secondly, a distance threshold value θ is defined. If the distance d(i,j) ≤ θ, then there is graph connectivity from node i to j and they are neighboring nodes, and vice versa. Note that we only need compare the distance between two signalized intersections with the threshold, i.e. i, jS with S denoting the set of all the signalized intersections. The graph connectivity of neighboring nodes i and j can be defined by function w(i,j) as follows in Eq. (1):

(1)

Here w(i,j) denotes there is graph connectivity from the signalized intersection i to j, while w(i,j) = 0 denotes that i to j are not connected.

This yields the graph connectivity matrix {w(i,j)} (with only 0, 1 values) between each pair of neighboring signalized intersections. Finally, in order to further construct belief matrix of neighboring signalized intersections, we depict the connectivity by a graph. The neighboring signalized intersections that connected by a link are depicted in directed solid lines and the others are depicted in directed dotted lines. For example, a simple road network is displayed in (Fig. 1a), which including nine intersections with five signalized intersections 1, 2, 4, 6, 7, 9 and three unsignalized intersections 3, 5, 8. The lengths of all the edges between intersections are 0.4 km. We depicted the road network as a directed graph in Fig. (1b). We computed the shortest path and the distances between two signalized intersections. Suppose, the distance threshold was 0.8 km, then the connectivity of neighboring intersections is shown in Fig. (1c).

Fig. (1). A road network and its graph connectivity.

After completing the first step, we have connectivity shape of all the signalized intersections in a road network. A model to compute the intersection’s importance was proposed. The correlation between intersections shows that the importance of an intersection is not only related to its own importance but also to its neighboring intersections’. The entire network at time t is represented by a vector or matrix, and the importance index of each intersection is the element in the matrix.

Let r_i, r_j represent the Importance index of intersection i,j in the priority order; larger number of r represents a more important intersection. Let U_j represents the set of neighboring intersections of intersection j. Note that the neighboring intersection has been determined by the graph connectivity in the last section. Let b represents the conditional dependency or belief of importance indexes between neighboring intersections, i.e. b_ij is the belief of intersection j’s importance index depending on its neighboring intersection i’s importance index. If there is a directed link from node i to node j in the connectivity graph that has been depicted in last section, then the element in the i-th row and the j-th column of the belief matrix (transformation matrix) is b_i,j > 0; if there is no directed link from node i to node j, then b_ij = 0. And the element of the main diagonal of the belief matrix is b_ii = 0. Later on, it will be shown how the entries into the belief matrix can be computed from the spatial and the traffic volume of the network, right now it is assumed they have been given. Therefore, the importance indexes of all the nodes in the network can be expressed by the linear equation as follows in Eq. (2):

(2)

Intersections that are connected with more congested links should get a higher priority. The congestion can be reflected by the saturation degree which is the ratio of traffic volume and lane capacity q/c. Although there are models to compute the lane’s capacity, such as HCM [24], Akcelik [25], Kyte [26], Wu [27] etc., the error is unavoidable when use them in the field road. It means there are errors with the saturation degree. This fact will weaken the effect of the proposed sorting model here. Hence, we employ the more accurate parameter, traffic volume q, to increase the reliability of the sorting model by multiplying the lane’s saturation degree to traffic volume.

In the connectivity graph depicted in the last section, e.g. Fig. (1c), there are solid lines and dotted lines. The solid lines denote two neighboring nodes (signalized intersections) which are adjacent and connected by a link. So the saturation degree, traffic volume and capacity of approach lanes at downstream signalized intersections are the variables of belief. Let L_s represents the set of lanes of the direct paths (solid lines) from intersection i to intersection j; x_ij,l represents the lane’s saturation degree; q_ij,l represents the lane’s traffic volume; c_ij,l represents the lane’s capacity. Then, the belief of direct path from node i to node j is b_ijs and defined in Eq. (3 and 4) as:

(3)

i.e.

(4)

The dotted lines denote that there is no direct path between two neighboring nodes (signalized intersections) in the network, e.g. there are unsignalized intersections between them. So the turning traffic volumes, the saturation degrees and capacities of approach lanes at unsignalized intersections are variables of belief. If there are several unsignalized intersections between two neighboring nodes, the multiplication of beliefs of unsignalized intersections is needed. Let L_d represents the set of lanes of the indirect pathes (dotted lines) from intersection i to intersection j; k denotes the unsignalized intersection from node i to node j; x_ik,l represents the lane’s saturation degree of the unsignalized intersection k; q_ik,l represents the lane’s traffic volume of the unsignalized intersection k; β represents the proportion of turning movement at unsignalized intersections. Then, the belief of an indirect path from node i to node j is b_ijd and defined as (Eq. 5):

(5)

The belief of importance indexes from node i to node j (b_ij) is the sum of belief of direct path and indirect path, as follows in Eq. (6):

(6)

For instance, the node 5 in Fig. (1b) is an unsignalized intersection and located between node 2 and node 4, so the belief of directed link from node 2 to node 4 is defined in Eq. (7):

(7)

Where: x₁₄, x₇₄, x₂₅, x₆₅ are the saturation degrees of the northern and the southern approaches of intersection 4, and the northern and the eastern approaches of intersection 5;

q₁₄, q₇₄, q₂₅, q₆₅, are the traffic volumes of northern and southern approaches of intersection 4, northern and eastern approaches of intersection 5;

β_r, β_s, β_l are the proportion of right-turning, straight-going, left-turning traffic volumes, q₂₅ ∙ β_r and q₆₅ ∙ β_s are the right-turning traffic volumes of northern approaches and the straight-going traffic volumes of eastern approaches of intersection 5.

If the number of signalized intersections in the network is n, then the beliefs between neighboring intersections form a n × n matrix B. The importance indexes of all the intersections form a non-zero column vector or n × 1 matrix R. The total importance index between the neighboring intersections is defined as follows in Eq. (8):

(8)

The solutions of the equation set are the values of importance indexes. Then the priority order can be sorted by the importance index. Usually the matrix B is a singular matrix, so we use the eigenvector of matrix B to denote the importance index vector R, i.e. R is an eigenvector and 1 is its eigenvalue for B. But we are primarily interested in the dominant eigenpair, which can be computed by mathematical software, or the power method. To a dominant eigenvalue, if all the entries of its dominant eigenvector are negative, the absolute function or normalization function is needed before sorting. Now, the normalized dominant eigenvalue is the importance index of each signalized intersection. The priority order of signal coordination can be computed by sorting the importance index in descending order.

The hypothetical test network is a 6 by 8 grid network including 38 signalized intersections and 10 unsignalized intersections. All the link length is 0.3 km, and the number of lanes is 1 lane with the free flow speed of 60 km per hour. Traffic signals are all two phases fixed-time operating on a common cycle length, in which phase 1 is for all movements on western and eastern approaches and phase 2 is for all movements on northern and southern approaches. The phase to phase intergreen time is 4 seconds. The network cycle length is optimized by Synchro 7. The traffic volumes are generated randomly in uniform distribution over the range [0,100] vehicles per hour.

Fig. (2). Graph connectivity in distance threshold of 0.6 km and 0.4 km.

We computed the shortest path and the distances between two signalized intersections. According to the definition of the graph connectivity in section 2.1 and supposed the distance threshold is 0.6 km, the connectivity of neighboring intersections is shown in Fig. (2a). The points in red and green are the signalized intersections, and the points in grey are the unsignalized intersections. The solid line means that two nodes have connection without passing unsignalized intersections. The dotted line means two nodes have connection via an unsignalized intersection. The concise graph connectivity of all nodes and their connections is shown in Fig. (2b). If supposed the distance threshold is 0.4 km, the graph connectivity is the same with the graph connectivity by the method SMOO, shown in Figs. (2c and d). It means the distance threshold is critical to determine the graph connectivity.

The priority orders by the four methods are plotted in Fig. (3). Here the IEM means the priority order sorted by the current paper, SMOO means the method in work of Lu and Wagner [12], the volume method means by the traffic volume entering intersection in descending order, and the saturation method means by the intersection’s saturation degree in descending order and the saturation degree is the maximum of intersection’s entering lanes’ saturation. The size of the point indicates intersections’ importance, the larger the size, the higher the importance. The number on the point is the exact priority order of the intersection. Fig. (3) shows that the intersection with the highest priority by IEM and SMOO are the same, which is intersection 31. The intersection with the highest priority by the volume method and is the same with the second highest priority by the saturation method, which is intersection 45.

Fig. (3). Priority order by different methods.

Fig. (4) displays the correlation of the priority order between the Importance Estimation Method (IEM) and the other methods. It shows that there is no high correlation among these methods. The method SMOO is closer to the revised one (R² = 0.73) than to the volume method (R² = 0.44) and the saturation method (R² = 0.54), respectively. This would also explain the importance of intersection has a lot to do with the graph connectivity.

The total delay, the number of stops, and the sum of weighted cost of delay and stops (the Performance Index) are taken as the Measures of Effectiveness (MOEs). Table 1 compares MOEs of the different methods. It shows that the Importation Estimation Model (IEM) has the least delay, stops, and Performance Index. The method SMOO created more delay than the Importance Estimation Model (IEM) by 5.8%, more stops by 2.4%, more Performance Index by 5.2%. The volume method created more delay than the revised model by 7.6%, more stops by 3.3%, more Performance Index by 6.7%. The saturation method created more delay than the Importance Estimation Model (IEM) by 5.6%, more stops by 3.6%, more Performance Index by 5.5%.

Fig. (4). Correlation between the IEM and other methods.

We present the histograms of the frequency of entering lane’s max queue in different methods in Fig. (5). It shows that the Importance Estimation Model (IEM) created a higher frequency of small queues. The mean value of max queue (μ) by the Importance Estimation Model (IEM) is the smallest, which is 0.2729 vehicles, and the variance (σ) is the smallest too, which is 0.0352. The mean values of max queue by the method SMOO, volume method, saturation method are 0.2781, 0.2812, and 0.2736, respectively; the variances are 0.0424, 0.0397, and 0.0427, respectively. It demonstrates that the revised method improves the queue length as compared to the other methods in the road network.

Fig. (5). Frequency of entering lane’s max queue.

Until now we have discussed the sorting of priority of signalized intersections in a road network at a certain time period based on both traffic flow characteristics and graph connectivity. However, traffic conditions are changing during a day and the congested area may grow or shrink with time. In order to capture congestion spreading phenomena, we extend our method to the dynamic cases by repeatedly applying the Importance Estimation Model (IEM) to the next time period based on the priority sorting results of the current time period. This simple extension is based on the fact that the traffic conditions of two close time periods might be very similar. Our aim is to provide some initial evidence that the distribution of priority order can capture congestion spreading. Nevertheless, this is a difficult problem that deserves further attention.

We first sort the signalized intersection’s priority at time t by the network’s graph connectivity and the importance estimation model (IEM). Then we optimize the signal plans by TRANSYT 15, and update the signal plans in simulation software of Synchro. After running simulation in SimTraffic in Synchro, we get the renewed traffic volume and saturation degree of links. Thirdly, we apply only the Importance Estimation Model (IEM) to the network with renewed volume and saturation, since the graph connectivity of network keeps the same, to get the priority order at the next period. Generally, the priority sorting result at t + i is obtained by applying the importance estimation model (IEM) to the sorting results at t + i - 1 with the renewed link volumes and saturation at t + i. In simulations, we set the initial sorting at t = 7h and repeatedly run the priority sorting model with increase step of 20 minutes until t = 8h, when the network tends to be homogeneously uncongested. The saturation degrees of links of network from t = 7h to t = 8h are shown in Fig. (6). We see clearly that the links’ saturation degree decreases with time from Fig. (6a to c). It means that the optimal priority order can help decrease the saturation of links. It also shows that the Importance Estimation Model (IEM) can capture the shift of the congested intersection.

Fig. (6). Saturation degree of links in network.