# Research on Phase Combination and Signal Timing Based on Improved K-Medoids Algorithm for Intersection Signal Control

Authors: Guojiang Shen; Xiangyu Zhu; Wei Xu; Longfeng Tang; Xiangjie Kong
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

Aiming at the problem of intersection signal control, a method of traffic phase combination and signal timing optimization based on the improved K-medoids algorithm is proposed. Firstly, the improvement of the traditional K-medoids algorithm embodies in two aspects, namely, the selection of the initial medoids and the parameterk, which will be applied to the cluster analysis of historical saturation data. The algorithm determines the initial medoids based on a set of probabilities calculated from the distance and determines the number of clusters k based on an exponential function, weight adjustment, and elbow ideas. Secondly, a phase combination model is established based on the saturation and green split data, and the signal timing is optimized through a bilevel programming model. Finally, the algorithm is evaluated over a certain intersection in Hangzhou, and results show that this algorithm can reduce the average vehicle delay and queue length and improve the traffic capacity of the intersection in the peak hour.


---

## Body

## 1. Introduction

With the rapid development of urban construction and socioeconomy, traffic congestion, one of China’s urban diseases, not only brings tremendous pressure to urban traffic management but also seriously affects the harmonious development of cities. Many modern transportation facilities and applications can benefit from better performance of signal timing schemes [1–4]. For example, space-time road resources can be allocated more reasonably, the accuracy of traffic speed prediction can be improved [2], and the optimized signal cycle time and green split scheme can help make better-coordinated control [4]. In [5, 6], the authors studied the application of mobile crowdsourcing (MCS) in smart cities. In [7, 8], the authors integrate geographic and temporal influences into points of interest (POI) recommendations to help people find points of interest.In recent years, several algorithms have been presented in the literature for traffic signal phase combination and timing optimization. In [9], the authors studied the dynamic prediction traffic signal control framework for a single intersection and optimized the signal timing according to the predicted arrival flow. In [10], a queuing and dissipation model of the intersection traffic flow was presented, which provided a theoretical basis for optimizing the intersection phase and timing. In [11], the authors considered an adaptive traffic signal control method based on fuzzy logic. This method optimized the phase duration and phase sequence. The results showed that the average queue length, the maximum queue length, and the parking rate were significantly shortened, but only lower queue lengths were considered. In [12], fog calculation was used to process traffic data, and a phase combination method based on a genetic algorithm was presented. The authors in [13] studied dynamic programming algorithms to optimize signal timing and phase, thereby, reducing average vehicle latency. In [14], the Artificial Bee Colony algorithm was adopted to optimize the signal cycle time and the green split, reducing the average vehicle delay and the average queue length, but the algorithm needed to obtain the vehicle speed online and calculate it. In [15], the authors considered a dynamic phase control method based on traffic flow, but it needed real-time detection and calculation of road conditions, resulting in poor practical application effect. In [16], the clustering algorithm was applied to process vehicle motion information, which was the basis for subsequent optimization, but only optimized the signal timing, excluding phase combination. In [17], a traffic signal segmentation algorithm based on the two-dimensional clustering was presented. It matched the best timing scheme for the current traffic conditions through the clustering analysis. However, the intersection traffic flow model cannot distinguish between a left turn and straight vehicles.In [18], the authors studied the interval data-based K-means clustering method, and the clustering results can accurately describe the trend of traffic state evolution at an urban intersection. In [19], the K-means clustering algorithm was used to group traffic flows and divide the traffic condition level and provides a theoretical basis for matching the most suitable traffic signal control scheme in different situations. In [20], the author studies a dynamic traffic control method that predicts congestion by the clustering thought. In [21], a traffic signal control method based on the K-means clustering algorithm was presented, and the number of clusters was defined as two. The authors in [22] studied the improved affinity propagation (AP) clustering algorithm, which provided efficient and accurate traffic state information for traffic signal control. The average waiting time was effectively reduced. In [23], the authors studied the K-means clustering method to optimize the best switching time of time-of-day (TOD) control scheme, but the number of clusters needed to be specified in advance, which largely affected the effectiveness of the method. Similarly, the authors in [24] used the Kohonen cluster and K-means cluster to optimize TOD breakpoints and proved that K-means had a better performance. However, it was still necessary to specify the number of clusters and the initial cluster centers in advance, which was easy to fall into local optimum.The existing researches mainly have the following shortcomings:(1)
the intersection traffic flow model is established without considering all of the flow directions
(2)
the practical value of online data acquisition and frequent signal switching solutions is not high
(3)
the number of clusters depends heavily on prior or empirical knowledgeTo solve the problems above, this paper proposes a traffic phase combination and signal timing optimization method based on the improved K-medoids algorithm. Firstly, the improved K-medoids algorithm is used to cluster the historical saturation data, which can select the number of schemesk more quickly and accurately. Then, the phase combination model is established since K-medoids correspond to k pairs of saturation and green split data, which can combine the flow direction with similar traffic demand to improve the utilization of green time. Finally, the bilevel programming model is used to optimize the signal cycle time and green split of each phase, so that the timing scheme can be further optimized based on the phase combination. After clustering, each medoid composing a scheme library corresponds to a traffic scheme. In experiments, we choose an appropriate traffic scheme according to the Euclidean distance between the actual traffic saturation and medoids.The paper is organized as follows: Section2 introduces the traditional K-medoids clustering algorithm and its improvement. Section 3 designs the phase combination and signal timing optimization algorithm. Section 4 provides experimental results and comparisons with the traditional K-medoids algorithm. Section 5 provides conclusions and describes directions for future research.


## 2. Improved K-Medoids Algorithm

In this section, we first introduce the traditional k-medoids algorithm, then, to find better initial medoids and the appropriate parameterk, an improvement is introduced. Finally, we apply the improved k-medoids algorithm to the traffic saturation dataset into k clusters, and each cluster corresponds to one set of traffic scheme.


### 2.1. Traditional K-Medoids Algorithm

Clustering is an unsupervised learning algorithm that partitions the origin data into several clusters, where the data in the same cluster are similar to each other but different from the data in other clusters. K-medoids algorithm is a partition-based clustering algorithm. Compared with K-means clustering, it is less sensitive to outliers. Among many k-medoids algorithms, partitioning around medoids (PAM) is one of the most classical and powerful [25].K-medoids algorithm first randomly selectsk representative data points as the initial medoids, each medoid corresponds to one cluster. Secondly, Euclidean distance is applied to calculate the distance between all data and the chosen medoid, each data point will be assigned to the most similar medoid. Thirdly, such a new medoid in each cluster is found to minimize the criterion function within the cluster. The algorithm will stop until all of the medoids are equal to the previous ones, otherwise, assign each data to the nearest medoid and generate k new clusters. The Euclidean distance dxi,yi is used to measure the similarity between all of the data points and the medoids, which can be calculated as follows:
(1)dxi,yj=xi1−yj12+xi2−yj22+⋯+xin−yjn2,where xi and yi are both n-dimensional data objects.The criterion function in within-cluster can be calculated as:(2)Ei=∑bj∈Bidbj,ci2,where Bi is the cluster after clustering, bj is the data point in the cluster Bi, and ci is the medoid of the cluster Bi.The criterion function is described as follows:(3)E=∑i=1k∑bj∈Bidbj,ci2.where k is the number of clusters.


### 2.2. The Improvement of K-Medoids Algorithm

For the K-medoids clustering algorithm, the number of clusters and the initialization have a great influence on the clustering process and results. In [26], a density peak clustering algorithm is proposed. This algorithm can select medoids and confirm the correct number of clusters. In [27], the author studied the K-medoids clustering algorithm based on a subset of candidate medoids and gradually increasing the number of clusters, thereby, improving the clustering performance of the algorithm. In order to reduce the negative impact when the initial medoids have a low dispersion degree, this paper proposes an initial point probability selection method based on the Euclidean distance. In addition, in order to reduce the artificial dependence for selecting initial medoids and avoid the excessive gap between each cluster, this paper proposes an optimization for selecting an optimal parameter k based on exponential function, weight adjustment, and elbow idea.


#### 2.2.1. Improved Method for Selecting Initial Medoids

After selecting a point in sample data as the first medoidc1 randomly, the Euclidean distance dbh,ci is applied to calculate the distance between each point bh and the nearest medoid ci, and the probability ph that point bh will be selected as the next cluster medoid can be calculated as:
(4)ph=dbh,ci2∑bj∈Bdbj,ci2,where B is the dataset, and the probability set P can be obtained as follows:
(5)P=0,p1,p1+p2,⋯,p1+p2+⋯+pn−1,1,where n is the number of samples in the dataset.The roulette wheel method is used to select the cluster medoidcii≥2 (see Figure 1):Step 1.
We generate a random numberr between 0,1, if r belongs to the interval p1+p2+⋯+pi−1,p1+p2+⋯+pi−1+pi in P, point bi will be the second cluster medoid c2.Step 2.
We recalculate the probabilities that each point in the dataset will be selected as the next medoid.Step 3.
We select the next medoid according to the probability setP and the roulette wheel method.Figure 1
Roulette wheel method.The steps mentioned above will be repeated untilk centers are selected. The purpose is to make the initial medoids more discrete, which are closer to the real cluster centers. The number of iterations can be reduced, but settle the problem of trapping in a local optimum.


#### 2.2.2. Improved Method for Selecting the Number of Clusters

The traditional criterion function in each cluster is the sum of all data within the cluster, which will make a big difference among clusters, and the classification will also be uneven. To settle the problem, this paper uses the exponential functionex to optimize the criterion function calculation method. The criterion function in within-cluster can be calculated as:
(6)Si=e∑bj∈Bidbj,ci2In order to avoid exponential explosion, the weight coefficientt is employed, and the criterion function S can be calculated as follows:
(7)S=∑i=1ke∑bj∈Bidbj,ci2e.With the optimization, the criterion functionS can be calculated for different k. Following the increasement of parameter k, S will decrease. According to the elbow idea, S drops dramatically at the beginning, then, S reaches an elbow, finally, the curve of S turns to a plateau. The value k corresponding to the elbow is regarded as the optimal number of clusters.


### 2.3. Clustering with Saturation Data

Traffic saturation data is a collection of saturation at intersections, a single piece of data can be described as:(8)Xi=xi1,xi2,⋯,xin,where n is the number of intersections.The improved K-medoids algorithm described in Section2.2 is then applied to the traffic saturation data, which divides the data into k clusters, and the initial cluster medoids are selected according to the distance probability ph. The phase and timing optimization can be performed according to the cluster medoids, and each cluster corresponds to one set of traffic scheme, which means there will be k sets of initial traffic schemes.


## 2.1. Traditional K-Medoids Algorithm

Clustering is an unsupervised learning algorithm that partitions the origin data into several clusters, where the data in the same cluster are similar to each other but different from the data in other clusters. K-medoids algorithm is a partition-based clustering algorithm. Compared with K-means clustering, it is less sensitive to outliers. Among many k-medoids algorithms, partitioning around medoids (PAM) is one of the most classical and powerful [25].K-medoids algorithm first randomly selectsk representative data points as the initial medoids, each medoid corresponds to one cluster. Secondly, Euclidean distance is applied to calculate the distance between all data and the chosen medoid, each data point will be assigned to the most similar medoid. Thirdly, such a new medoid in each cluster is found to minimize the criterion function within the cluster. The algorithm will stop until all of the medoids are equal to the previous ones, otherwise, assign each data to the nearest medoid and generate k new clusters. The Euclidean distance dxi,yi is used to measure the similarity between all of the data points and the medoids, which can be calculated as follows:
(1)dxi,yj=xi1−yj12+xi2−yj22+⋯+xin−yjn2,where xi and yi are both n-dimensional data objects.The criterion function in within-cluster can be calculated as:(2)Ei=∑bj∈Bidbj,ci2,where Bi is the cluster after clustering, bj is the data point in the cluster Bi, and ci is the medoid of the cluster Bi.The criterion function is described as follows:(3)E=∑i=1k∑bj∈Bidbj,ci2.where k is the number of clusters.


## 2.2. The Improvement of K-Medoids Algorithm

For the K-medoids clustering algorithm, the number of clusters and the initialization have a great influence on the clustering process and results. In [26], a density peak clustering algorithm is proposed. This algorithm can select medoids and confirm the correct number of clusters. In [27], the author studied the K-medoids clustering algorithm based on a subset of candidate medoids and gradually increasing the number of clusters, thereby, improving the clustering performance of the algorithm. In order to reduce the negative impact when the initial medoids have a low dispersion degree, this paper proposes an initial point probability selection method based on the Euclidean distance. In addition, in order to reduce the artificial dependence for selecting initial medoids and avoid the excessive gap between each cluster, this paper proposes an optimization for selecting an optimal parameter k based on exponential function, weight adjustment, and elbow idea.


### 2.2.1. Improved Method for Selecting Initial Medoids

After selecting a point in sample data as the first medoidc1 randomly, the Euclidean distance dbh,ci is applied to calculate the distance between each point bh and the nearest medoid ci, and the probability ph that point bh will be selected as the next cluster medoid can be calculated as:
(4)ph=dbh,ci2∑bj∈Bdbj,ci2,where B is the dataset, and the probability set P can be obtained as follows:
(5)P=0,p1,p1+p2,⋯,p1+p2+⋯+pn−1,1,where n is the number of samples in the dataset.The roulette wheel method is used to select the cluster medoidcii≥2 (see Figure 1):Step 1.
We generate a random numberr between 0,1, if r belongs to the interval p1+p2+⋯+pi−1,p1+p2+⋯+pi−1+pi in P, point bi will be the second cluster medoid c2.Step 2.
We recalculate the probabilities that each point in the dataset will be selected as the next medoid.Step 3.
We select the next medoid according to the probability setP and the roulette wheel method.Figure 1
Roulette wheel method.The steps mentioned above will be repeated untilk centers are selected. The purpose is to make the initial medoids more discrete, which are closer to the real cluster centers. The number of iterations can be reduced, but settle the problem of trapping in a local optimum.


### 2.2.2. Improved Method for Selecting the Number of Clusters

The traditional criterion function in each cluster is the sum of all data within the cluster, which will make a big difference among clusters, and the classification will also be uneven. To settle the problem, this paper uses the exponential functionex to optimize the criterion function calculation method. The criterion function in within-cluster can be calculated as:
(6)Si=e∑bj∈Bidbj,ci2In order to avoid exponential explosion, the weight coefficientt is employed, and the criterion function S can be calculated as follows:
(7)S=∑i=1ke∑bj∈Bidbj,ci2e.With the optimization, the criterion functionS can be calculated for different k. Following the increasement of parameter k, S will decrease. According to the elbow idea, S drops dramatically at the beginning, then, S reaches an elbow, finally, the curve of S turns to a plateau. The value k corresponding to the elbow is regarded as the optimal number of clusters.


## 2.2.1. Improved Method for Selecting Initial Medoids

After selecting a point in sample data as the first medoidc1 randomly, the Euclidean distance dbh,ci is applied to calculate the distance between each point bh and the nearest medoid ci, and the probability ph that point bh will be selected as the next cluster medoid can be calculated as:
(4)ph=dbh,ci2∑bj∈Bdbj,ci2,where B is the dataset, and the probability set P can be obtained as follows:
(5)P=0,p1,p1+p2,⋯,p1+p2+⋯+pn−1,1,where n is the number of samples in the dataset.The roulette wheel method is used to select the cluster medoidcii≥2 (see Figure 1):Step 1.
We generate a random numberr between 0,1, if r belongs to the interval p1+p2+⋯+pi−1,p1+p2+⋯+pi−1+pi in P, point bi will be the second cluster medoid c2.Step 2.
We recalculate the probabilities that each point in the dataset will be selected as the next medoid.Step 3.
We select the next medoid according to the probability setP and the roulette wheel method.Figure 1
Roulette wheel method.The steps mentioned above will be repeated untilk centers are selected. The purpose is to make the initial medoids more discrete, which are closer to the real cluster centers. The number of iterations can be reduced, but settle the problem of trapping in a local optimum.


## 2.2.2. Improved Method for Selecting the Number of Clusters

The traditional criterion function in each cluster is the sum of all data within the cluster, which will make a big difference among clusters, and the classification will also be uneven. To settle the problem, this paper uses the exponential functionex to optimize the criterion function calculation method. The criterion function in within-cluster can be calculated as:
(6)Si=e∑bj∈Bidbj,ci2In order to avoid exponential explosion, the weight coefficientt is employed, and the criterion function S can be calculated as follows:
(7)S=∑i=1ke∑bj∈Bidbj,ci2e.With the optimization, the criterion functionS can be calculated for different k. Following the increasement of parameter k, S will decrease. According to the elbow idea, S drops dramatically at the beginning, then, S reaches an elbow, finally, the curve of S turns to a plateau. The value k corresponding to the elbow is regarded as the optimal number of clusters.


## 2.3. Clustering with Saturation Data

Traffic saturation data is a collection of saturation at intersections, a single piece of data can be described as:(8)Xi=xi1,xi2,⋯,xin,where n is the number of intersections.The improved K-medoids algorithm described in Section2.2 is then applied to the traffic saturation data, which divides the data into k clusters, and the initial cluster medoids are selected according to the distance probability ph. The phase and timing optimization can be performed according to the cluster medoids, and each cluster corresponds to one set of traffic scheme, which means there will be k sets of initial traffic schemes.


## 3. Phase Combination and Signal Timing

In order to improve the adaptability of the traffic schemes for maching different traffic conditions, we establish the phase combination model and optimize the signal timing using the bilevel programming model.


### 3.1. Phase Combination Model

Signal phase refers to one or more flow directions displayed by the same signal lamp in a signal cycle time. The phase combination model mainly analyzes the conflicts of traffic flows with different directions, and use clustering ideas to merge nonconflicting flows with similar traffic characteristics into one phase. A reasonable combination can effectively reduce the release time of the green light, improve the utilization of the green light, and ensure transportation safety.Two traffic flows are conflicting if there is a collision point of the vehicle travel path in these two directions. For example, the traffic flow in the east-west direction and the south-north direction are conflict, while the traffic flow in the east-west direction and the west-east direction are compatible. The conflict matrix can be constructed as follows:(9)C=0φ12φ13⋯φ1nφ210φ23⋯φ2nφ31φ320⋱⋮⋮⋮⋱⋱φn−1nφn1φn2⋯φnn−10,where φij indicates whether the flow direction and j is conflict. If not, the value is 0, otherwise, 1.The distance matrix is used to represent the difference between traffic flows, which can be constructed based on the saturation of flow directions, green signal split data, and the conflict matrix:(10)D=0d12d13⋯d1nd210d23⋯d2nd31d320⋱⋮⋮⋮⋱⋱dn−1ndn1dn2⋯dnn−10,where the element dij in the matrix can be calculated as follows:
(11)dij=yi−yj2+φij=xiλi−xjλj2+φij,where yi is the traffic flow ratio of the flow direction i, which reflecting the traffic demand not affected by the signal control scheme. xi is the saturation of the flow direction i, and λi is the initial green split of the flow direction i.Since the distance between the flow directioni and j is the same as the distance between the flow direction j and i, the distance matrix is symmetric, that is, dij=dji. To ensure the balance of traffic flows in each phase, we optimize the phase combination according to the distance matrix between flow directions to make the combination more rational. For a typical crossroad, four-phase schemes are usually used, each phase consists of two flow directions, and the same flow direction traffic must be released only once in one cycle. Considering the symmetry of the distance matrix and all-zero values on the main diagonal, only the lower triangle needs to be processed. Algorithm 1 shows the optimization of the phase combination. If the distance between two flows is equal to or greater than 1, these two flows are physically conflicting. Hence, we select all the flow pairs with their distances less than 1 to form the Dfirst vector. If one scheme in the Dfirst contains all flow direction and each direction ci only appears once, it will be saved as Deach to Dall. Then, we calculate the sum of the distances in Deach and insert it into the Sall as Seach, and the index z of the minimum Smin in Sall is selected. Finally, we choose the optimal scheme Dfinal according to z in Dall.Algorithm 1: Phase combination.
Input:
The distance matrixD
Output:
The final phase combination schemeDfinal
Begin
1. fori=1ton, do
2, Forj=1toi−1, do
3.   Ifdij<1 Then
4.Dfirst.adddij;
5.   End If
6.  End For
7.EndFor
8. Whilec1,c2,c3,⋯,cn!=eachother,do
9.Deach⟵dc1c2,dc3c4,dc5c6,⋯,dcn−1cn;
10.Dall.addDeach;
11.Seach⟵sumDeach;
12.Sall.addSeach;
13.EndWhile
14.Smin⟵SelectminSall;
15.z⟵TheindexofSmininSall;
16.Dfinal⟵Dallz;
EndFor example, there are two schemes here (see Figure2): Scheme A takes east left movement and east through movement as one phase, west left movement and west through movement as another phase. Scheme B takes east left movement and west left movement as one phase, east through movement and west through movement as another phase, the distances of above four combinations are 0.2, 0.1, 0.3, and 0.4, respectively. The scheme A is chosen because the sum of the first two values is smaller than that of the last two values.Figure 2
Schematic diagram of phase scheme comparison.


### 3.2. Traffic Signal Timing Bi-Level Programming Model

The bilevel programming model is a system optimization model with a two-tier hierarchical structure. The upper and lower levels have their own objective functions and constraints [28, 29]. The objective functions and constraints of the upper-level problem are not only related to the upper decision variables but also depending on the optimal solution of the lower level problem, while the optimal solution of the lower level problem is affected by the upper decision variables.We establish a traffic signal timing optimization algorithm based on the bilevel programming model. The framework of the traffic signal timing optimization algorithm is shown in Figure3.Figure 3
The framework of the traffic signal timing optimization algorithm.


#### 3.2.1. Establishment of the Bilevel Programming Model

The signal cycle time is the key control parameter that determines the quality of traffic signal control in traffic signal timing, and the saturation can reflect the rationality of the signal cycle time to some extent. We establish the upper-level programming model with saturation as the decision target, which can be calculated as:(12)J=minx-−x~,where x- is the average saturation of each phase, and x~ is the target average saturation.Under the condition of fixed signal cycle time constraints, the mean square error (MSE) of the saturation is used to evaluate the rationality of green split distribution. With the MSE, the lower-level programming model can be established as:(13)σ=min1N∑i=1Nxi−x-2,where N is the number of signal phases. The saturation of each phase can be calculated as:
(14)xi=fiqiλi,where fi is the arrival traffic flow for phase i, qi is the average of each flow direction saturated flow in phase i, and λi is the initial green split of phase i.


#### 3.2.2. Solution of the Bilevel Programming Model

The single-step action set with signal cycle time changes is designed to obtain the optimal signal cycle time of the upper-level programming model, the action set can be expressed as follows:(15)action1=a1,−a1,0,where a1, in seconds, is the adjustment step size for cycle time.The three elements in action1 represent three operations, including addition, subtraction and invariance, respectively. For example, if the initial signal cycle time isT, the action1 is a1,−a1,0, and the signal cycle time after each adjustment according to action1 will be T+a1,T−a1,T.Algorithm2 shows the optimization for signal cycle time. Each action of Equation (15) is executed in the initial signal cycle time T0, and J is calculated by Equation (12) and (14), which will be inserted into Jall. The minimum Jmin in Jall is selected, if its corresponding action is nonzero, the action will be taken, and the signal cycle time after execution will be updated as the initial scheme T0 for the next iteration. The algorithm will loop until the action corresponding to Jmin is zero, and the signal cycle time at this time Noww is regarded as the optimal signal cycle time Tf.Algorithm 2: Signal cycle time optimization.
Input:
The initial signal cycle timeT0, the average arrival traffic flow for each phase f=f1,f2,⋯,fn, the average of each flow direction saturated flow in each phase q=q1,q2,⋯,qn, the initial green split of each phase λ=λ1,λ2,⋯,λn and the action set action1
Output:
The optimal signal cycle timeTf
Begin
1.w0⟵Theindexof0inaction1;
2.w⟵Anumber!=w0;
3.Whilew!=w0,do
4.Foreachaiinaction1,do
5.TNowi⟵CalculateAdjust_TT0,ai;
6.EndFor
7.Jall ⟵ [];
8.ForeachTNiinTNow,do
9.Jall.addCalculateJTNi,fi,qi,λi;
10.EndFor
11.Jmin⟵SelectminJall;
12.w⟵TheindexofJmininJall;
13.Ifw==w0Then
14.Tf⟵TNoww;
15.Else
16.T0⟵TNoww;
17.EndIf
18.EndWhile
EndSimilar to the upper level, to solve the optimal green split of the lower-level programming model, we design a set of single-step changes in the green time of each signal phase, the action set is(16)action2=a2,a2,−a2,−a2,a2,−a2,a2,−a2,a2,−a2,−a2,a2,−a2,a2,a2,−a2,−a2,a2,−a2,a2,−a2,−a2,a2,a2,a2,−a2,0,0,a2,0,−a2,0,a2,0,0,−a2,−a2,a2,0,0,0,a2,−a2,0,0,a2,0,−a2,−a2,0,a2,0,0,−a2,a2,0,0,0,a2,−a2,−a2,0,0,a2,0,−a2,0,a2,0,0,−a2,a2,0,0,0,0,where a2, in seconds, is the adjustment step size for green time.The four elements in action2 represent the adjustment of green time of each phase in the four-phase scheme. For example, if the initial green time isg1,g2,g3,g4, the action2 is a2,a2,−a2,−a2,⋯,0,0,0,0 and the green time of each phase after each adjustment according to action2 will be g1+a2,g2+a2,g3−a2,g4−a2,⋯,g1,g2,g3,g4.Algorithm3 shows the process for green split optimization. Considered the premise of the green split optimization algorithm that the signal cycle time is fixed, the sum of all elements in the action matrix is zero. According to the initial scheme of green split, the initial timing scheme is obtained by multiplying the signal cycle time. Each action of Equation (16) is executed, respectively, and then σ value of the corresponding action can be saved into σall according to Equation (13) and (14). Then we select the minimum σmin in σall, if its corresponding action is not 0,0,0,0, the action will be taken, and the green timing scheme after execution is updated as the initial scheme g0 for the next iteration. The algorithm will loop until the action corresponding to σmin is 0,0,0,0, and the green time of each signal phase at this time is converted into green split, and the optimal green split scheme λf is output.Algorithm 3: Green split optimization.
Input:
The signal cycle timeT, the arrival traffic flow for each phase f=f1,f2,⋯,fn, the average of each flow direction saturated flow in each phase q=q1,q2,⋯,qn, the initial green split of each phase λ0=λ01,λ02,⋯,λ0n, and the action set action2
Output:
The optimal green split schemeλf=λf1,λf2,⋯,λfn
1.I0⟵Theindexof0,0,0,0inaction2;
2.I⟵Anumber!=I0;
3.Foriinλ0,do
4.g0.addλ0iT;
5.WhileI!=I0,do
6.Foreachaiinaction2,do
7.GNowi⟵CalculateAdjust_gg0,ai;
8.EndFor
9.σall ⟵ [];
10.ForeachGNiinGNow,do
11.σall.addCalculateσGNi,fi,qi;
12.EndFor
13.σmin⟵Selectminσall;
14.I⟵Theindexofσmininσall;
15.IfI==I0,do
16.gf⟵GNowI;
17.Else
18.g0⟵GNowI;
19.  End If
20. End While
21. Foriingf,do
22.λf.addgfi/T;
EndWe complete the green split optimization in the lower-level programming model, which will be fed back to the upper level. While in the upper level, the signal cycle time is optimized heuristically and iteratively under the restriction of the green split, until the scheme is optimal or the cycle reaches the upper limit.


## 3.1. Phase Combination Model

Signal phase refers to one or more flow directions displayed by the same signal lamp in a signal cycle time. The phase combination model mainly analyzes the conflicts of traffic flows with different directions, and use clustering ideas to merge nonconflicting flows with similar traffic characteristics into one phase. A reasonable combination can effectively reduce the release time of the green light, improve the utilization of the green light, and ensure transportation safety.Two traffic flows are conflicting if there is a collision point of the vehicle travel path in these two directions. For example, the traffic flow in the east-west direction and the south-north direction are conflict, while the traffic flow in the east-west direction and the west-east direction are compatible. The conflict matrix can be constructed as follows:(9)C=0φ12φ13⋯φ1nφ210φ23⋯φ2nφ31φ320⋱⋮⋮⋮⋱⋱φn−1nφn1φn2⋯φnn−10,where φij indicates whether the flow direction and j is conflict. If not, the value is 0, otherwise, 1.The distance matrix is used to represent the difference between traffic flows, which can be constructed based on the saturation of flow directions, green signal split data, and the conflict matrix:(10)D=0d12d13⋯d1nd210d23⋯d2nd31d320⋱⋮⋮⋮⋱⋱dn−1ndn1dn2⋯dnn−10,where the element dij in the matrix can be calculated as follows:
(11)dij=yi−yj2+φij=xiλi−xjλj2+φij,where yi is the traffic flow ratio of the flow direction i, which reflecting the traffic demand not affected by the signal control scheme. xi is the saturation of the flow direction i, and λi is the initial green split of the flow direction i.Since the distance between the flow directioni and j is the same as the distance between the flow direction j and i, the distance matrix is symmetric, that is, dij=dji. To ensure the balance of traffic flows in each phase, we optimize the phase combination according to the distance matrix between flow directions to make the combination more rational. For a typical crossroad, four-phase schemes are usually used, each phase consists of two flow directions, and the same flow direction traffic must be released only once in one cycle. Considering the symmetry of the distance matrix and all-zero values on the main diagonal, only the lower triangle needs to be processed. Algorithm 1 shows the optimization of the phase combination. If the distance between two flows is equal to or greater than 1, these two flows are physically conflicting. Hence, we select all the flow pairs with their distances less than 1 to form the Dfirst vector. If one scheme in the Dfirst contains all flow direction and each direction ci only appears once, it will be saved as Deach to Dall. Then, we calculate the sum of the distances in Deach and insert it into the Sall as Seach, and the index z of the minimum Smin in Sall is selected. Finally, we choose the optimal scheme Dfinal according to z in Dall.Algorithm 1: Phase combination.
Input:
The distance matrixD
Output:
The final phase combination schemeDfinal
Begin
1. fori=1ton, do
2, Forj=1toi−1, do
3.   Ifdij<1 Then
4.Dfirst.adddij;
5.   End If
6.  End For
7.EndFor
8. Whilec1,c2,c3,⋯,cn!=eachother,do
9.Deach⟵dc1c2,dc3c4,dc5c6,⋯,dcn−1cn;
10.Dall.addDeach;
11.Seach⟵sumDeach;
12.Sall.addSeach;
13.EndWhile
14.Smin⟵SelectminSall;
15.z⟵TheindexofSmininSall;
16.Dfinal⟵Dallz;
EndFor example, there are two schemes here (see Figure2): Scheme A takes east left movement and east through movement as one phase, west left movement and west through movement as another phase. Scheme B takes east left movement and west left movement as one phase, east through movement and west through movement as another phase, the distances of above four combinations are 0.2, 0.1, 0.3, and 0.4, respectively. The scheme A is chosen because the sum of the first two values is smaller than that of the last two values.Figure 2
Schematic diagram of phase scheme comparison.


## 3.2. Traffic Signal Timing Bi-Level Programming Model

The bilevel programming model is a system optimization model with a two-tier hierarchical structure. The upper and lower levels have their own objective functions and constraints [28, 29]. The objective functions and constraints of the upper-level problem are not only related to the upper decision variables but also depending on the optimal solution of the lower level problem, while the optimal solution of the lower level problem is affected by the upper decision variables.We establish a traffic signal timing optimization algorithm based on the bilevel programming model. The framework of the traffic signal timing optimization algorithm is shown in Figure3.Figure 3
The framework of the traffic signal timing optimization algorithm.


### 3.2.1. Establishment of the Bilevel Programming Model

The signal cycle time is the key control parameter that determines the quality of traffic signal control in traffic signal timing, and the saturation can reflect the rationality of the signal cycle time to some extent. We establish the upper-level programming model with saturation as the decision target, which can be calculated as:(12)J=minx-−x~,where x- is the average saturation of each phase, and x~ is the target average saturation.Under the condition of fixed signal cycle time constraints, the mean square error (MSE) of the saturation is used to evaluate the rationality of green split distribution. With the MSE, the lower-level programming model can be established as:(13)σ=min1N∑i=1Nxi−x-2,where N is the number of signal phases. The saturation of each phase can be calculated as:
(14)xi=fiqiλi,where fi is the arrival traffic flow for phase i, qi is the average of each flow direction saturated flow in phase i, and λi is the initial green split of phase i.


### 3.2.2. Solution of the Bilevel Programming Model

The single-step action set with signal cycle time changes is designed to obtain the optimal signal cycle time of the upper-level programming model, the action set can be expressed as follows:(15)action1=a1,−a1,0,where a1, in seconds, is the adjustment step size for cycle time.The three elements in action1 represent three operations, including addition, subtraction and invariance, respectively. For example, if the initial signal cycle time isT, the action1 is a1,−a1,0, and the signal cycle time after each adjustment according to action1 will be T+a1,T−a1,T.Algorithm2 shows the optimization for signal cycle time. Each action of Equation (15) is executed in the initial signal cycle time T0, and J is calculated by Equation (12) and (14), which will be inserted into Jall. The minimum Jmin in Jall is selected, if its corresponding action is nonzero, the action will be taken, and the signal cycle time after execution will be updated as the initial scheme T0 for the next iteration. The algorithm will loop until the action corresponding to Jmin is zero, and the signal cycle time at this time Noww is regarded as the optimal signal cycle time Tf.Algorithm 2: Signal cycle time optimization.
Input:
The initial signal cycle timeT0, the average arrival traffic flow for each phase f=f1,f2,⋯,fn, the average of each flow direction saturated flow in each phase q=q1,q2,⋯,qn, the initial green split of each phase λ=λ1,λ2,⋯,λn and the action set action1
Output:
The optimal signal cycle timeTf
Begin
1.w0⟵Theindexof0inaction1;
2.w⟵Anumber!=w0;
3.Whilew!=w0,do
4.Foreachaiinaction1,do
5.TNowi⟵CalculateAdjust_TT0,ai;
6.EndFor
7.Jall ⟵ [];
8.ForeachTNiinTNow,do
9.Jall.addCalculateJTNi,fi,qi,λi;
10.EndFor
11.Jmin⟵SelectminJall;
12.w⟵TheindexofJmininJall;
13.Ifw==w0Then
14.Tf⟵TNoww;
15.Else
16.T0⟵TNoww;
17.EndIf
18.EndWhile
EndSimilar to the upper level, to solve the optimal green split of the lower-level programming model, we design a set of single-step changes in the green time of each signal phase, the action set is(16)action2=a2,a2,−a2,−a2,a2,−a2,a2,−a2,a2,−a2,−a2,a2,−a2,a2,a2,−a2,−a2,a2,−a2,a2,−a2,−a2,a2,a2,a2,−a2,0,0,a2,0,−a2,0,a2,0,0,−a2,−a2,a2,0,0,0,a2,−a2,0,0,a2,0,−a2,−a2,0,a2,0,0,−a2,a2,0,0,0,a2,−a2,−a2,0,0,a2,0,−a2,0,a2,0,0,−a2,a2,0,0,0,0,where a2, in seconds, is the adjustment step size for green time.The four elements in action2 represent the adjustment of green time of each phase in the four-phase scheme. For example, if the initial green time isg1,g2,g3,g4, the action2 is a2,a2,−a2,−a2,⋯,0,0,0,0 and the green time of each phase after each adjustment according to action2 will be g1+a2,g2+a2,g3−a2,g4−a2,⋯,g1,g2,g3,g4.Algorithm3 shows the process for green split optimization. Considered the premise of the green split optimization algorithm that the signal cycle time is fixed, the sum of all elements in the action matrix is zero. According to the initial scheme of green split, the initial timing scheme is obtained by multiplying the signal cycle time. Each action of Equation (16) is executed, respectively, and then σ value of the corresponding action can be saved into σall according to Equation (13) and (14). Then we select the minimum σmin in σall, if its corresponding action is not 0,0,0,0, the action will be taken, and the green timing scheme after execution is updated as the initial scheme g0 for the next iteration. The algorithm will loop until the action corresponding to σmin is 0,0,0,0, and the green time of each signal phase at this time is converted into green split, and the optimal green split scheme λf is output.Algorithm 3: Green split optimization.
Input:
The signal cycle timeT, the arrival traffic flow for each phase f=f1,f2,⋯,fn, the average of each flow direction saturated flow in each phase q=q1,q2,⋯,qn, the initial green split of each phase λ0=λ01,λ02,⋯,λ0n, and the action set action2
Output:
The optimal green split schemeλf=λf1,λf2,⋯,λfn
1.I0⟵Theindexof0,0,0,0inaction2;
2.I⟵Anumber!=I0;
3.Foriinλ0,do
4.g0.addλ0iT;
5.WhileI!=I0,do
6.Foreachaiinaction2,do
7.GNowi⟵CalculateAdjust_gg0,ai;
8.EndFor
9.σall ⟵ [];
10.ForeachGNiinGNow,do
11.σall.addCalculateσGNi,fi,qi;
12.EndFor
13.σmin⟵Selectminσall;
14.I⟵Theindexofσmininσall;
15.IfI==I0,do
16.gf⟵GNowI;
17.Else
18.g0⟵GNowI;
19.  End If
20. End While
21. Foriingf,do
22.λf.addgfi/T;
EndWe complete the green split optimization in the lower-level programming model, which will be fed back to the upper level. While in the upper level, the signal cycle time is optimized heuristically and iteratively under the restriction of the green split, until the scheme is optimal or the cycle reaches the upper limit.


## 3.2.1. Establishment of the Bilevel Programming Model

The signal cycle time is the key control parameter that determines the quality of traffic signal control in traffic signal timing, and the saturation can reflect the rationality of the signal cycle time to some extent. We establish the upper-level programming model with saturation as the decision target, which can be calculated as:(12)J=minx-−x~,where x- is the average saturation of each phase, and x~ is the target average saturation.Under the condition of fixed signal cycle time constraints, the mean square error (MSE) of the saturation is used to evaluate the rationality of green split distribution. With the MSE, the lower-level programming model can be established as:(13)σ=min1N∑i=1Nxi−x-2,where N is the number of signal phases. The saturation of each phase can be calculated as:
(14)xi=fiqiλi,where fi is the arrival traffic flow for phase i, qi is the average of each flow direction saturated flow in phase i, and λi is the initial green split of phase i.


## 3.2.2. Solution of the Bilevel Programming Model

The single-step action set with signal cycle time changes is designed to obtain the optimal signal cycle time of the upper-level programming model, the action set can be expressed as follows:(15)action1=a1,−a1,0,where a1, in seconds, is the adjustment step size for cycle time.The three elements in action1 represent three operations, including addition, subtraction and invariance, respectively. For example, if the initial signal cycle time isT, the action1 is a1,−a1,0, and the signal cycle time after each adjustment according to action1 will be T+a1,T−a1,T.Algorithm2 shows the optimization for signal cycle time. Each action of Equation (15) is executed in the initial signal cycle time T0, and J is calculated by Equation (12) and (14), which will be inserted into Jall. The minimum Jmin in Jall is selected, if its corresponding action is nonzero, the action will be taken, and the signal cycle time after execution will be updated as the initial scheme T0 for the next iteration. The algorithm will loop until the action corresponding to Jmin is zero, and the signal cycle time at this time Noww is regarded as the optimal signal cycle time Tf.Algorithm 2: Signal cycle time optimization.
Input:
The initial signal cycle timeT0, the average arrival traffic flow for each phase f=f1,f2,⋯,fn, the average of each flow direction saturated flow in each phase q=q1,q2,⋯,qn, the initial green split of each phase λ=λ1,λ2,⋯,λn and the action set action1
Output:
The optimal signal cycle timeTf
Begin
1.w0⟵Theindexof0inaction1;
2.w⟵Anumber!=w0;
3.Whilew!=w0,do
4.Foreachaiinaction1,do
5.TNowi⟵CalculateAdjust_TT0,ai;
6.EndFor
7.Jall ⟵ [];
8.ForeachTNiinTNow,do
9.Jall.addCalculateJTNi,fi,qi,λi;
10.EndFor
11.Jmin⟵SelectminJall;
12.w⟵TheindexofJmininJall;
13.Ifw==w0Then
14.Tf⟵TNoww;
15.Else
16.T0⟵TNoww;
17.EndIf
18.EndWhile
EndSimilar to the upper level, to solve the optimal green split of the lower-level programming model, we design a set of single-step changes in the green time of each signal phase, the action set is(16)action2=a2,a2,−a2,−a2,a2,−a2,a2,−a2,a2,−a2,−a2,a2,−a2,a2,a2,−a2,−a2,a2,−a2,a2,−a2,−a2,a2,a2,a2,−a2,0,0,a2,0,−a2,0,a2,0,0,−a2,−a2,a2,0,0,0,a2,−a2,0,0,a2,0,−a2,−a2,0,a2,0,0,−a2,a2,0,0,0,a2,−a2,−a2,0,0,a2,0,−a2,0,a2,0,0,−a2,a2,0,0,0,0,where a2, in seconds, is the adjustment step size for green time.The four elements in action2 represent the adjustment of green time of each phase in the four-phase scheme. For example, if the initial green time isg1,g2,g3,g4, the action2 is a2,a2,−a2,−a2,⋯,0,0,0,0 and the green time of each phase after each adjustment according to action2 will be g1+a2,g2+a2,g3−a2,g4−a2,⋯,g1,g2,g3,g4.Algorithm3 shows the process for green split optimization. Considered the premise of the green split optimization algorithm that the signal cycle time is fixed, the sum of all elements in the action matrix is zero. According to the initial scheme of green split, the initial timing scheme is obtained by multiplying the signal cycle time. Each action of Equation (16) is executed, respectively, and then σ value of the corresponding action can be saved into σall according to Equation (13) and (14). Then we select the minimum σmin in σall, if its corresponding action is not 0,0,0,0, the action will be taken, and the green timing scheme after execution is updated as the initial scheme g0 for the next iteration. The algorithm will loop until the action corresponding to σmin is 0,0,0,0, and the green time of each signal phase at this time is converted into green split, and the optimal green split scheme λf is output.Algorithm 3: Green split optimization.
Input:
The signal cycle timeT, the arrival traffic flow for each phase f=f1,f2,⋯,fn, the average of each flow direction saturated flow in each phase q=q1,q2,⋯,qn, the initial green split of each phase λ0=λ01,λ02,⋯,λ0n, and the action set action2
Output:
The optimal green split schemeλf=λf1,λf2,⋯,λfn
1.I0⟵Theindexof0,0,0,0inaction2;
2.I⟵Anumber!=I0;
3.Foriinλ0,do
4.g0.addλ0iT;
5.WhileI!=I0,do
6.Foreachaiinaction2,do
7.GNowi⟵CalculateAdjust_gg0,ai;
8.EndFor
9.σall ⟵ [];
10.ForeachGNiinGNow,do
11.σall.addCalculateσGNi,fi,qi;
12.EndFor
13.σmin⟵Selectminσall;
14.I⟵Theindexofσmininσall;
15.IfI==I0,do
16.gf⟵GNowI;
17.Else
18.g0⟵GNowI;
19.  End If
20. End While
21. Foriingf,do
22.λf.addgfi/T;
EndWe complete the green split optimization in the lower-level programming model, which will be fed back to the upper level. While in the upper level, the signal cycle time is optimized heuristically and iteratively under the restriction of the green split, until the scheme is optimal or the cycle reaches the upper limit.


## 4. Simulation Experiment and Result Analysis

### 4.1. Experimental Methods and Experimental Data

The experiment is simulated in SUMO (Simulation of Urban Mobility), which is an open-source, highly portable, microscopic, and continuous traffic simulation software. The real-world intersection, Jianshe 4th Rd and Shixin N Rd in Xiaoshan District, Hangzhou, China (see Figure4) is chosen as the operating environment.Figure 4
The actual layout of the intersection.According to the traffic laws and regulations in our country, the right turn movement can pass the intersection at any time without being controlled by the signal light; thus, only the left turn and the straight vehicles are considered in the simulation. Figure5 shows the simulation structure of the intersection.Figure 5
The simulation layout of the intersection.The traffic flow data were provided by the traffic control department of Xiaoshan District, Hangzhou, from 7 : 00 a.m. to 9 : 00 a.m. on November 20th, 2018. The original data was the traffic flow data of the signal cycle time and the timing scheme of the corresponding time, which was processed into saturation data set for clustering, and then, timing optimization was carried out based on the original timing scheme. Then, the data were divided into 5 periods, and flows of each direction were calculated every half an hour. The traffic flow data at a certain point in time is the average flow of the adjacent 15 minutes, that is, the traffic flow at 8 : 00 a.m. is the average traffic flow from 7 : 45 a.m. to 8 : 15 a.m. The flow data were divided into eight flow directions, such as the left turn for eastbound movement, the through for eastbound and so on. The average traffic flow of all lanes in each flow direction is recorded in Table1, which has been converted into the hourly traffic flow to the inlet, and the through flow of each flow direction is also recorded. In this table, “E, ” “S,” “W,” and “N” refer to eastbound, southbound, westbound, and northbound, respectively. “L” and “S” mean left turn and straight vehicles. For example, “LE” represents the traffic flow of the left turn in the eastbound movement.Table 1
Traffic flow data of each flow direction in each time period of the intersection (veh/h).
Time
LE
SE
LS
SS
LW
SW
LN
SN
7 : 00
128
242
168
476
92
186
266
368
7 : 30
202
364
150
980
96
198
320
798
8 : 00
124
240
184
758
88
164
238
662
8 : 30
138
275
143
752
98
150
282
760
9 : 00
118
220
186
576
102
148
224
448
Saturation flow
1529
1641
1347
2360
1286
1606
1722
2228The signal timing scheme generated by the improved K-medoids clustering algorithm is compared with the scheme generated by the traditional one to ensure the fairness of the experiment. In order to avoid the exponential explosion and make the criterion functionE and S be in the same order of magnitude, the weight coefficient t is set as 11000. Additionally, we set the target average saturation δx to 70 according to the actual intersection traffic demand. In order to avoid missing the optimal timing scheme due to overlarge step size, the signal cycle time adjustment step a1 and the green time adjustment step a2 are both set as 1.In addition, the proposed algorithm is compared to the fixed phase scheme and the traffic flow and vector angle based on the optimization scheme [17].


### 4.2. Analysis of Results

The criterion functions of differentk using traditional and improved K-medoids algorithm are shown, expressed by E and S, respectively. As k increases, the criterion functions decrease, and the rate of decline also stabilizes. In both cases, the optimal k is 3, while using the improved K-medoids, it is easier to reach the result, and the elbow point can be identified more unambiguously. Figure 6 shows the curves of both algorithms, which is more intuitive.Figure 6
Algorithm comparison on the saturation dataset.Table2 shows the different performances of the traditional and improved K-medoids algorithm. As for the number of clusters, in different iterations, the traditional K-medoids may reach the elbow when k is in range of 3 and 6, which is ambiguous to identify, while the improved K-medoids can always reach the elbow when k=3. In addition, the improved K-medoids runs faster than the traditional version, and that may because we optimize the selection of initial optimizing, which reduces the number of interactions.Table 2
Performance comparison of the traditional and improved K-medoids algorithm.
Algorithm
Number of clusters
Average execution time(s)
Traditional K-medoids
[3–6]
1.764
Improved K-medoids
3
1.623Average vehicle delay and average queue length are used to evaluate the performance of the proposed algorithm.Figures7 and 8 show the curves of optimized phase and timing schemes under different conditions compared to fixed schemes that optimize only timing and vector angle-based schemes. The outperformance of our proposed method can be seen in all time periods. Table 3 shows the averaged values of the above two evaluation indexes, we can see that the proposed method outperforms the fixed phase method with improvements of 2.462 s (7.07%), and 1.542 m (11.38%) on the vehicle delay and the queue length, and also shows improvements of 3.924 s (10.81%) and 1.656 m (12.16%) compared to the traffic flow and vector angle-based optimization scheme.Figure 7
Comparison of average vehicle delays at intersection.Figure 8
Comparison of average queue length at intersection.Table 3
Comparison of three optimization schemes at intersection.
Average vehicle delays (s)
Average queue length (m)
Fixed phase
34.842
13.554
Vector angle
36.304
13.668
Optimized phase
32.380
12.012Table4 shows the delay comparison of three optimization schemes in SS, SW, and LE. We can see that the method proposed by us has a great improvement on the average vehicle delays in each flow direction compared to the traffic flow and vector angle-based optimization scheme. In our proposed method, the average vehicle delays of SW and LE is different from that of the fixed phase method, this is because the phase of SW and LE has changed. Compared with the fixed phase method, the average vehicle delays of LE in our method are reduced, but the average vehicle delays of SW are increased. The main reason is that our method improves the overall traffic capacity of the intersection rather than the single flow direction.Table 4
Delay comparison of three optimization schemes in flow direction.
Time
Fixed phase
Vector angle
Optimized phase
SS
SW
LE
SS
SW
LE
SS
SW
LE
7 : 00
14.44
23.89
35.57
20.66
45.82
37.62
15.91
28.88
27.28
7 : 30
29.81
24.04
40.20
21.35
53.38
41.17
29.82
24.05
40.19
8 : 00
22.74
23.61
32.67
29.84
55.28
44.68
22.73
23.62
32.67
8 : 30
35.35
20.92
39.16
27.55
55.99
50.72
29.18
26.45
30.31
9 : 00
12.21
25.20
34.72
11.79
31.85
29.78
14.92
30.91
21.41
Average
22.91
23.53
36.46
22.24
48.46
40.79
22.51
26.78
30.37


## 4.1. Experimental Methods and Experimental Data

The experiment is simulated in SUMO (Simulation of Urban Mobility), which is an open-source, highly portable, microscopic, and continuous traffic simulation software. The real-world intersection, Jianshe 4th Rd and Shixin N Rd in Xiaoshan District, Hangzhou, China (see Figure4) is chosen as the operating environment.Figure 4
The actual layout of the intersection.According to the traffic laws and regulations in our country, the right turn movement can pass the intersection at any time without being controlled by the signal light; thus, only the left turn and the straight vehicles are considered in the simulation. Figure5 shows the simulation structure of the intersection.Figure 5
The simulation layout of the intersection.The traffic flow data were provided by the traffic control department of Xiaoshan District, Hangzhou, from 7 : 00 a.m. to 9 : 00 a.m. on November 20th, 2018. The original data was the traffic flow data of the signal cycle time and the timing scheme of the corresponding time, which was processed into saturation data set for clustering, and then, timing optimization was carried out based on the original timing scheme. Then, the data were divided into 5 periods, and flows of each direction were calculated every half an hour. The traffic flow data at a certain point in time is the average flow of the adjacent 15 minutes, that is, the traffic flow at 8 : 00 a.m. is the average traffic flow from 7 : 45 a.m. to 8 : 15 a.m. The flow data were divided into eight flow directions, such as the left turn for eastbound movement, the through for eastbound and so on. The average traffic flow of all lanes in each flow direction is recorded in Table1, which has been converted into the hourly traffic flow to the inlet, and the through flow of each flow direction is also recorded. In this table, “E, ” “S,” “W,” and “N” refer to eastbound, southbound, westbound, and northbound, respectively. “L” and “S” mean left turn and straight vehicles. For example, “LE” represents the traffic flow of the left turn in the eastbound movement.Table 1
Traffic flow data of each flow direction in each time period of the intersection (veh/h).
Time
LE
SE
LS
SS
LW
SW
LN
SN
7 : 00
128
242
168
476
92
186
266
368
7 : 30
202
364
150
980
96
198
320
798
8 : 00
124
240
184
758
88
164
238
662
8 : 30
138
275
143
752
98
150
282
760
9 : 00
118
220
186
576
102
148
224
448
Saturation flow
1529
1641
1347
2360
1286
1606
1722
2228The signal timing scheme generated by the improved K-medoids clustering algorithm is compared with the scheme generated by the traditional one to ensure the fairness of the experiment. In order to avoid the exponential explosion and make the criterion functionE and S be in the same order of magnitude, the weight coefficient t is set as 11000. Additionally, we set the target average saturation δx to 70 according to the actual intersection traffic demand. In order to avoid missing the optimal timing scheme due to overlarge step size, the signal cycle time adjustment step a1 and the green time adjustment step a2 are both set as 1.In addition, the proposed algorithm is compared to the fixed phase scheme and the traffic flow and vector angle based on the optimization scheme [17].


## 4.2. Analysis of Results

The criterion functions of differentk using traditional and improved K-medoids algorithm are shown, expressed by E and S, respectively. As k increases, the criterion functions decrease, and the rate of decline also stabilizes. In both cases, the optimal k is 3, while using the improved K-medoids, it is easier to reach the result, and the elbow point can be identified more unambiguously. Figure 6 shows the curves of both algorithms, which is more intuitive.Figure 6
Algorithm comparison on the saturation dataset.Table2 shows the different performances of the traditional and improved K-medoids algorithm. As for the number of clusters, in different iterations, the traditional K-medoids may reach the elbow when k is in range of 3 and 6, which is ambiguous to identify, while the improved K-medoids can always reach the elbow when k=3. In addition, the improved K-medoids runs faster than the traditional version, and that may because we optimize the selection of initial optimizing, which reduces the number of interactions.Table 2
Performance comparison of the traditional and improved K-medoids algorithm.
Algorithm
Number of clusters
Average execution time(s)
Traditional K-medoids
[3–6]
1.764
Improved K-medoids
3
1.623Average vehicle delay and average queue length are used to evaluate the performance of the proposed algorithm.Figures7 and 8 show the curves of optimized phase and timing schemes under different conditions compared to fixed schemes that optimize only timing and vector angle-based schemes. The outperformance of our proposed method can be seen in all time periods. Table 3 shows the averaged values of the above two evaluation indexes, we can see that the proposed method outperforms the fixed phase method with improvements of 2.462 s (7.07%), and 1.542 m (11.38%) on the vehicle delay and the queue length, and also shows improvements of 3.924 s (10.81%) and 1.656 m (12.16%) compared to the traffic flow and vector angle-based optimization scheme.Figure 7
Comparison of average vehicle delays at intersection.Figure 8
Comparison of average queue length at intersection.Table 3
Comparison of three optimization schemes at intersection.
Average vehicle delays (s)
Average queue length (m)
Fixed phase
34.842
13.554
Vector angle
36.304
13.668
Optimized phase
32.380
12.012Table4 shows the delay comparison of three optimization schemes in SS, SW, and LE. We can see that the method proposed by us has a great improvement on the average vehicle delays in each flow direction compared to the traffic flow and vector angle-based optimization scheme. In our proposed method, the average vehicle delays of SW and LE is different from that of the fixed phase method, this is because the phase of SW and LE has changed. Compared with the fixed phase method, the average vehicle delays of LE in our method are reduced, but the average vehicle delays of SW are increased. The main reason is that our method improves the overall traffic capacity of the intersection rather than the single flow direction.Table 4
Delay comparison of three optimization schemes in flow direction.
Time
Fixed phase
Vector angle
Optimized phase
SS
SW
LE
SS
SW
LE
SS
SW
LE
7 : 00
14.44
23.89
35.57
20.66
45.82
37.62
15.91
28.88
27.28
7 : 30
29.81
24.04
40.20
21.35
53.38
41.17
29.82
24.05
40.19
8 : 00
22.74
23.61
32.67
29.84
55.28
44.68
22.73
23.62
32.67
8 : 30
35.35
20.92
39.16
27.55
55.99
50.72
29.18
26.45
30.31
9 : 00
12.21
25.20
34.72
11.79
31.85
29.78
14.92
30.91
21.41
Average
22.91
23.53
36.46
22.24
48.46
40.79
22.51
26.78
30.37


## 5. Conclusions

In this paper, we optimize the traditional K-medoids clustering algorithm in terms of the clustering number and initial medoids selection. In order to match the changes of traffic flow in different time periods adaptively, the phase combination optimization model is established to optimize the phase, and the bilevel programming model aims to optimize the signal timing, which can maximize the utilization of green time. The proposed algorithm is optimized for each flow direction. Whereas the flow saturation may be different when the overall situation is similar, we will study the difference of different flow saturation to achieve the optimal control effect of the intersection.



---

*Source: 3240675-2020-05-09.xml*