Research on Queue Equilibrium Control Algorithm of Urban Traffic Based on Game Theory

Abstract

The intersection traffic signal control is an essential means of urban traffic. To solve the problem of urban congestion, it is necessary to consider the optimal signal control strategy for intersections. Using the store-and-forward method of traffic control modeling, the in-queue vehicle number of the key signal phase as the payoff index, this paper designs an optimal intersection signal-timing strategy based on the game theory method. In this strategy, each key phase is regarded as a game player, and each player competes for the release time to maximize their own payoff and minimize the queue. To optimize the intersection efficiency, a game strategy is designed to achieve the Nash equilibrium state, which is the queueing equilibrium of each key phase. Finally, by VISSIM simulation, the total number of stops can be decreased by 5% to 10% compared with the MA-DD-DACC method.

1. Introduction

The signal control is one of the key factors that impact road performance and traffic congestion. A reasonable optimization strategy of signal control at the intersection can alleviate urban road congestion and improve traffic efficiency.

To alleviate traffic pressure, researchers have proposed many advanced traffic signal control methods according to different control standards. In 1958, the famous Webster’s signal plan [1] was put forward, which was mainly used to calculate the green split to reduce the delay. Subsequently, SCAT [2] and SCOOT [3,4,5] adaptive traffic signal optimization systems were proposed and widely applied in the world. Choy et al. developed a new hybrid neural network (SPSA-NN) for distributed real-time control of intersections in road networks. The experimental results show that the algorithm can significantly reduce the delay and stop of vehicles in road networks. However, this algorithm requires a large number of training samples [6]. In recent years, reinforcement learning has become the mainstream method in urban traffic signal control research. Chen et al. proposed an adaptive traffic signal control scheme for urban road networks based on multi-agent reinforcement learning (MARL). A delay time estimation model was adopted to predict the total delay of vehicles in each road section, and traffic signals are adaptively controlled according to the computation [7]. Wade et al. proposed an adaptive traffic signal control system that is trained by the function approximation reinforcement learning technology. In the process, they developed a dynamic and random traffic simulation method that will slightly increase the delay of left-turning vehicles [8]. Ali et al. used an immune network algorithm to conduct an optimization study in the intersection after traffic disturbance events [9]. Based on data-driven intelligent transportation systems (D2ITSs), Zhang et al. designed the MA-DD-DACC method combined with real-time queue-length data to ensure queuing strength (the number of queuing vehicles/the length of its link) balance between multiple signal phases and proved that the algorithm could make the queue intensity balance error remain bounded by using Lyapunov’s stability analysis, but most of the time, the vehicles in the queues in each direction do not saturate the road and lane space, and the number of queuing-vehicles balance will have greater significance [10].

The traffic condition change of a local road network can be regarded as uncertain competition conditions in the game, so it is appropriate to use the Nash equilibrium to improve the existing intersection signal control strategy. Abdelghaffar et al. developed a Nash negotiation game theory framework for the intersection phase that uses each signal phase as a game player competing for the green light release and realized phase-free and cycle-free distributed real-time signal control. However, the algorithm is not friendly for driving and is not good for vehicle-to-infrastructure cooperative control [11]. Liu et al. designed a traffic signal control multi-agent coordination framework based on deep reinforcement learning methods, which corrected actions by using spatial difference coordination methods. They proved that the model could converge to the Nash equilibrium [12]. The Cournot and Stackelberg game theory models were used to balance the flow of a single intersection and road network in the previous study [13,14,15,16]. The cooperative game was utilized to optimize vehicles distribution among multiple intersections [17]. Tan et al. used the two-layer cooperation game model to control the single intersection, but this method is only applicable to the two-phase intersection [18].

In this paper, the game theory is introduced into the intersection signal control to realize the coordination and optimization of control. The single intersection is the research object, the store-and-forward method is used in the modeling, and the payoff index based on in-queue vehicle number equilibrium is proposed. By designing the game strategy, the Nash equilibrium state achieved by the game is the queuing payoff equilibrium of each key signal phase to optimize the green time.

2. Queuing-Length Model

In this section, the store-and-forward mode of the intersection will be proposed to prepare for the design of an in-queue vehicle number equilibrium control strategy. The store-and-forward model of traffic networks was first proposed in 1963 and is still widely used in traffic signal control [19,20]. The mathematical queuing-length model of each direction at the cycle-changeable intersection is as follows:

$$d_i^j(k+1)=d_i^j(k)+C(k)q_i^j(k)-S_i^j{g}_i(k)$$

(1)

where $i=1,\dots ,N$ represents the ith phase of the intersection, and $N=4$ represents there are four phases at the intersection; $j=1,\dots ,M$ indicates the $j$th direction of the intersection, $M=4$ represents there are four directions at the intersection, $C(k)$ indicates the $k$th cycle of the intersection signal control, and $d_i^j(k)$ represents the in-queue vehicle number (pcu) of the $k$th cycle of the $i$th phase at the $j$th direction during the time period $[(k-1)C(k),kC(k)]$. $q_i^j(k)$ represents the vehicle arrival rate (veh/s) of the intersection in phase $i$, direction $j$, and cycle $k$; $S_i^j$ means the saturation flow rate (pcu/s) of phase $i$ at direction $j$; $g_i(k)$ indicates the effective green time (s) of the $k$th cycle of the $i$th phase.

To define the maximum queuing length of the specific phase at a single intersection, which is the maximum value of the queuing length at each direction in the same phase, the equation can be listed as follows:

$$D_i(k)=\max \left\{d_i^j\left(k\right),d_i^{j+2}\left(k\right),0\right\}$$

(2)

where direction $j$ and direction $j+2$ belong to phase $i$. The third item $0$ is to prevent negative values of the queue length during the calculation process, which is inconsistent with the actual situation.

The mathematical queuing-length model of the cycle-changeable intersection is as follows:

$$D_i(k+1)=D_i(k)+C(k)q_i^{\ast }(k)-S_i^{\ast }{g}_i(k)$$

(3)

where $D_i(k)$ represents the in-queue vehicle number (pcu) of the $i$th phase and the $k$th cycle during $[(k-1)C(k),kC(k)]$; $q_i^{\ast }(k)$ means the vehicle arrival rate (pcu/s) in the $k$th cycle of the longest queue direction in phase $i$ of the intersection; $S_i^{\ast }$ indicates the saturation flow rate (pcu/s) of the longest queue direction in phase $i$ of the intersection $j$.

The green time of each phase and the signal cycle at the intersection should be satisfied by the following constraints:

$$C(k)={\displaystyle \sum _{i=1}^N{g}_i(k)}+t_L$$

(4)

where $t_L$ indicates the lost time.

To avoid a too long or too short green time, the maximum and minimum green times need to be set. Therefore, the constraints for green time and the signal cycle in the $i$th phase and $k$th cycle of the intersection are defined as:

$${\overline{g}}_i(k)=\left\{\begin{array}{cc}\min \left\{g_i(k),g_{\max }\right\}& g_i(k)>g_{\max }\\ g_i(k)& g_{\min }\le g_i(k)\le g_{\max }\\ \max \left\{g_i(k),g_{\min }\right\}& g_i(k)<g_{\min }\end{array}\right.$$

(5)

$$C(k)={\displaystyle \sum _{i=1}^N{\overline{g}}_i(k)+t_L}$$

(6)

The queue length model with a green time constraint at a single intersection is considered as follows:

$$D_i(k+1)=D_i(k)+C(k)q_i^{\ast }(k)-S_i^{\ast }{\overline{g}}_i(k)$$

(7)

3. The Equilibrium Control

In the intersection signal control, the green time for each phase can be regarded as a game, where the phase acts as a participant, and each participant competes for the green time in a signal cycle. Suppose the queue length $D_i(k+1)$ at the beginning of the following cycle is the yield indicator, then the larger the queue number, the smaller the yield. In that case, each participant (phase) hopes to obtain as much green time as possible to maximize their own returns.

To facilitate calculation, Equation (7) and green time are split (${\overline{g}}_i(k)={\overline{g}}_i^1(k)+{\overline{g}}_i^2(k)$), and the final payoff function $a_i(k)$ is:

$$a_i(k)=S_i^{\ast }{\overline{g}}_i^1(k)-D_i(k)$$

(8)

$$C(k)q_i^{\ast }(k)=S_i^{\ast }{\overline{g}}_i^2(k)$$

(9)

Equation (8) indicates that each participant (signal phase) competed for the green time to clear the queue in each phase, and when the profit is 0, it means that the queue can be cleared just in time; Equation (9) suggests that each participant is assigned a fixed green time that can clear all the arrived vehicles in the current signal cycle.

Since all the variables except ${\overline{g}}_i^2(k)$ in Equation (9) are known, it can be set that:

$$W(k)={\displaystyle \sum _{i=1}^N{\overline{g}}_i^2(k)}+t_L$$

(10)

Substituting Equation (10) into (6) gives:

$$C(k)={\displaystyle \sum _{i=1}^N{\overline{g}}_i^1(k)}+W(k)$$

(11)

According to the cake game, it is easy to see that the Nash equilibrium state is reached when the participants’ benefits are equal. For example, if there are two participants in the cake splitting, one of whom cuts the cake and the other chooses the cut pieces first, then the one slicing the cake will cut it equally to prevent the other player from taking the larger piece first. In this case, the two players reach the Nash equilibrium state with the same amounts of benefits. According to the above analysis, when the intersection is a two-phase game, there are:

$${\overline{g}}_1^1(k)=\frac{S_2^{\ast }(C(k)-W(k))+D_1(k)-D_2(k)}{S_1^{\ast }+S_2^{\ast }}$$

(12)

Suppose ${\overline{g}}_1(k)\ge {\overline{g}}_2(k)$ and $a_1(k)=0$, combine Equations (8) and (12) to have:

$$C^{\ast }(k)={\displaystyle \sum _{i=1}^2\frac{D_i(k)}{S_i^{\ast }}}+W(k)$$

(13)

At this time, $C^{\ast }(k)$(s) indicates the $k$th cycle of the intersection signal control is just enough to clear the intersection. It can also be seen from Equation (13) that the cycle is the sum of the time to clear the original queue in each phase and the arriving vehicles in the current cycle and the lost time. Substitute Equations (9) and (10) into (13):

$$C^{\ast }(k)=\frac{{\displaystyle \sum _{i=1}^2\frac{D_i(k)}{S_i^{\ast }}}+t_L}{1-{\displaystyle \sum _{i=1}^2\frac{q_i^{\ast }(k)}{S_i^{\ast }}}}$$

(14)

In the actual calculation process, the queue may not be cleared; then the value of $C^{\ast }(k)$ is too high, so the maximum cycle $C_{\max }$ should be set according to practical experience. The period in the final substitution algorithm is $C(k)=\min (C^{\ast }(k),C_{\max })$.

When the intersection is a four-phase game:

$$\begin{array}{l}{\overline{g}}_1^1(k)=\frac{S_2^{\ast }{S}_3^{\ast }(D_1(k)-D_4(k))+S_2^{\ast }{S}_4^{\ast }(D_1(k)-D_3(k))+S_3^{\ast }{S}_4^{\ast }(D_1(k)-D_2(k)) }{S_1^{\ast }{S}_2^{\ast }{S}_3^{\ast }+S_1^{\ast }{S}_2^{\ast }{S}_4^{\ast }+S_1^{\ast }{S}_3^{\ast }{S}_4^{\ast }+S_2^{\ast }{S}_3^{\ast }{S}_4^{\ast }}\\ \begin{array}{cc}& \end{array}+\frac{S_2^{\ast }{S}_3^{\ast }{S}_4^{\ast }C(k) - S_2^{\ast }{S}_3^{\ast }{S}_4^{\ast }W(k)}{S_1^{\ast }{S}_2^{\ast }{S}_3^{\ast }+S_1^{\ast }{S}_2^{\ast }{S}_4^{\ast }+S_1^{\ast }{S}_3^{\ast }{S}_4^{\ast }+S_2^{\ast }{S}_3^{\ast }{S}_4^{\ast }}\end{array}$$

(15)

Other phases’ green times can be obtained similarly. Resembling the two-phase, let $a_x(k)=0$, where ${\overline{g}}_x(k)=\max ({\overline{g}}_i(k)),i=1,\dots ,N$, and the same two-phase case $C^{\ast }(k)$ can be obtained as follows:

$$C^{\ast }(k)=\frac{{\displaystyle \sum _{i=1}^4\frac{D_i(k)}{S_i^{\ast }}}+t_L}{1-{\displaystyle \sum _{i=1}^4\frac{q_i^{\ast }(k)}{S_i^{\ast }}}}$$

(16)

As in Section 2, to avoid a too long or too short green time, the green time calculated by the algorithm in this paper needs to set the maximum and minimum green-time constraints as shown in Equation (5), and then the corresponding signal cycle is updated according to Equation (6).

4. Simulation Verification

To verify the feasibility of the proposed algorithm, this paper implements the queuing equilibrium control algorithm based on game theory in Matlab and compares it with algorithms in other papers. Two groups of experiments are carried out: 1. using the queuing equilibrium game control algorithm in this paper; 2. using the MA-DD-DACC queuing strength balance control algorithm. As shown in Figure 1 and Figure 2, it can be found that MA-DD-DACC can ensure the balanced queuing strength (the number of queuing vehicles/the length of its link) and clear the intersection at the same time. The time taken is 651 s. However, most of the time, the line in each direction does not fill the lane, and the experience of each vehicle in the line will have greater significance. The algorithm in this paper takes the number of queues as the index. Each phase competes with the other over the green time and finally clears the entire intersection, which takes 639 s. The experimental parameters are shown in

Table 1. The equilibrium control simulation parameter table.

	East Import	North Import	West Import	South Import
Arrival flow $q$/pcu·h−1	(1.5 + cos(x * pi/4:0.2:(1 + x/4) * pi)) * 200
Initial cycle $C_0$/s (maximum cycle $C_{\max }$/s)	128 (120)
Initial queue $D_0$/pcu	10	20	30	40
Saturation flow $S$/pcu·h−1	1880	1880	1880	1880
Initial green light time $g$/s	10	10	10	10
Lost time $t_L$/s	2	2	2	2
Maximum queue length $l_{\max }$/pcu	100	200	300	400
Maximum green light time $g_{\max }$/s	70	70	70	70
Minimum green light time $g_{\min }$/s	10	10	10	10
Quotiely alpha	0.99	0.99	0.99	0.99

, where the flow rate of each phase is translated successively $\raisebox{1ex}{$pi$}\!\left/ \!\raisebox{-1ex}{$4$}\right.$ by the cosine function.

We use the traffic simulation software VISSIM to carry out the experiments. The intersection of Nanhuan Road and Yanping Road in Changping District in Beijing is selected as the simulation intersection, and the simulation time is 10 a.m. to 11 a.m. (during the off-peak period). The filed traffic data in the intersection is applied as the vehicle inputs and routes ratio of VISSIM, as shown in

Table 2. The vehicle inputs and routes ratio of VISSIM.

		East	North	West	South
Vehicle Inputs		974	306	998	285
Routes ratio	Straight	0.87	0.85	0.84	0.57
	Left-turn	0.09	0.05	0.14	0.14
	Right-turn	0.02	0.1	0.02	0.29
	U-turn	0.02	0	0	0

. The vehicle composition of all directions is similar in the intersection, as shown in

Table 3. The traffic composition of VISSIM.

	Rel.Flow	Des.Speed
100.Car	0.900	50(48.0, 58.0)
200.HGV	0.100	40(40.0, 45.0)

. The original signal timing and the magnetic detector data of the intersection are obtained by the traffic management department. The original intersection timing plan is shown in

Table 4. The original intersection timing plan.

Green time(s)	50	15	55
Yellow time(s)	4	4	4
All-red time(s)	4	4	4

. The magnetic detector is located 120 m from the stop line in the east–west direction and 50 m from the stop line in the north–south direction. The east–west direction is the main road, so the conflict zone in the priority of east–west is higher than that of north–south.

Model calibration is an important step in VISSIM simulation. The car-following model in this study is the Wiedemann-74, and the calibration parameters include average standstill distance (AvgSD), additive part of safety distance (AddSD), multiple part of safety distance (MulSD), look-ahead observed vehicles (LaVeh), and maximum look-ahead distance (MaxLD). The lane-change model is free lane selection, and the calibration parameters include minimum headway (MinHF), waiting time before diffusion (WaiBD), maximum cancellation (MaxDC), and maximum cancellation for cooperative braking (MaxDB). The detector is set at the corresponding position in VISSIM based on the position of the actual magnetic detector. The calibration parameters are optimized by using a learning algorithm (GA algorithm) with the goal of best matching the number of vehicles passing through the each direction of the intersection. The objective function is the mean absolute percentage error (MAPE) of the flow:

$$MAPE=\frac{1}{n}{\displaystyle \sum _{i=1}^n\left|\frac{q_i^r-q_i^s}{q_i^r}\right|}$$

where $n=4$ represents there being four directions in the intersection. $q_i^r$ indicates the flow of the actual magnetic detector. $q_i^s$ represents the flow of the VISSIM detector. Finally, the calibrated VISSIM model parameters are obtained, as shown in

Table 5. The calibration parameters of VISSIM.

Following Model (Wiedemann-74)		Lane Change (Free Lane Selection)
AvgSD/m	2.59	MinHF/m	0.90
AddSD/m	2.85	WaiBD/s	71.13
MulSD/m	3.04	MaxDC/m·s−2	Own:−4.56/Trail:−4.89
LaVeh/veh	1	MaxDB/m·s−2	−3
MaxLD/m	204.73

. The other VISSIM parameters are the default values. After calibration, the VISSIM detector data and the magnetic detector data are shown in Figure 3, and the MAPE is 4.7% (the random seed is 42).

The VISSIM-VB-MATLAB is used to simulate and compare the two groups of algorithms. The evaluation data of VISSIM are shown in Figure 4 and Figure 5. It can be seen that the proposed algorithm in this paper brings more balance in queuing in all directions. The average delay and stopping times of each vehicle are also more balanced. Generally, standard deviation is used to express the degree of data balance. The standard deviation of average delay and stopping times of each vehicle in all directions obtained by the proposed algorithm in this paper is 2.3 s and 0.18, respectively, and the corresponding standard deviations of MA-DD-DAC is 6.2 s and 0.56. The average delay and total number of stops in the four directions are summed up and compared. The total average delay and total number of stops of the proposed algorithm in this paper are 50.2 s and 2.74, respectively, and the corresponding total average delay and total number of stops of MA-DD-DAC are 51.8 s and 2.93. The above results show that the queuing equilibrium game algorithm in this paper can effectively reduce the delay and the number of stops at the intersection and improve the operation efficiency.

5. Conclusions

We propose a queuing equilibrium control algorithm based on game theory to help urban traffic controllers deal with control problems in different traffic environments. The VISSIM simulation results show that this algorithm has a good effect on the intersection queue balance control and improves the intersection operation efficiency. Although this is only a preliminary exploration, it can be expected that game theory can be well-applied in traffic signal control. At present, it is only used in a single intersection. Next, we will combine game theory with multi-agents at multiple intersections to further improve the operating environment of urban road traffic and improve the efficiency of traffic controllers.