# A Two-Level Rolling Optimization Model for Real-time Adaptive Signal Control
## 2 Traffic Signal Timing Optimization Algorithm
### Dynamic Programming Algorithm  
The upper optimization is a DP problem, and a forward and a backward recursion are used to solve this. Figure 2 shows the relation of some variables, and Table 1 lists the notation of parameters and variables used in the DP algorithm. In this paper, a forward and a backward recursion were used to solve the DP problem. The forward recursion calculates the performance measure (objective function) based on the decision and state variables and records the optimal value function for each stage. The backward recursion retrieves the optimal policy starting from the final stage and working backward. The details of the forward and backward recursion are described below. The forward recursion is based on the allocation of time to each barrier group as stages in the DP. Considering each barrier group as a stage, the algorithm plans as many stages as necessary to obtain the optimal solution. The ring and phase within one barrier group are defined in Figure 1. The phases in each barrier group are divided into two rings, and \(r\) represents the ring index and \(p\) represents the \begin{table}
\begin{tabular}{c l} \hline \hline
**Variable** & **Description** \\ \hline \(p\) & Phase index in each ring and barrier group, \(p=1,2\). \\ \(r\) & Ring index in each barrier group, \(r=1,2\). \\ \(j\) & Index of barrier groups/stages. \\ \(j\) & Last stage calculated by the DP before stopping. \\ \(x_{j}\) & Decision variable denoting the length of barrier group \(j\). \\ \(s_{j}\) & State variable denoting the total number of time steps from the start time to barrier group \(j\). \\ \(S_{j}\) & A set of state variable \(s_{j}\). \\ \(T\) & The total number of discrete time steps in the planning horizon, seconds. \\ \(\mathbf{X}_{j}\big{(}s_{j}\big{)}\) & A set of feasible control decisions, given barrier group state \(s_{j}\). \\ \(f\big{(}s_{j},x_{j}\big{)}\) & Performance measure (objective function) at stage \(j\), given barrier group state \(s_{j}\) and control variable \(x_{j}\). \\ \(v_{j}\big{(}s_{j}\big{)}\) & Value function (cumulative value of prior performance measures), given state variable \(s_{j}\). \\ \(R_{r,p}\) & Phase change interval which is the total of the yellow change and red clearance times of phase \(p\) in ring \(r\). \\ \(G_{r,p}^{\min}\) & Minimum green time of phase \(p\) in ring \(r\). \\ \(G_{r,p}^{\min}\) & Maximum green time of phase \(p\) in ring \(r\). \\ \(X_{j}^{\min}\) & Minimum possible barrier group length of stage \(j\). \\ \(X_{j}^{\max}\) & Maximum possible barrier group length of stage \(j\). \\ \(S_{r,p}\) & Green time of phase \(p\) in ring \(r\). \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Notation of key parameters and variables used in the dynamic programing (DP) algorithm. Figure 1: The standard NEMA dual-ring controller diagram. Figure 2: The relationship between the states, decisions, and the total number of discrete time-steps. phase index within the ring. Due to the variability of traffic demand, the algorithm will not produce a fixed cycle length. The minimum and maximum allowable barrier group lengths are calculated according to the signal timing parameters as shown in Equations (1) and (2). The parameters include the minimum green, maximum green, yellow change and red clearance times of each phase. \[X_{j}^{\min} =\max\Bigl{\{}G_{1,1}^{\min}+R_{1,1}+G_{1,2}^{\min}+R_{1,2},\,G_{2,1 }^{\min}+R_{2,1}+G_{2,2}^{\min}+R_{2,2}\Bigr{\}}, \tag{1}\] \[X_{j}^{\max} =\min\bigl{\{}G_{1,1}^{\max}+R_{1,1}+G_{1,2}^{\max}+R_{1,2},\,G_{2, 1}^{\max}+R_{2,1}+G_{2,2}^{\max}+R_{2,2}\bigr{\}}. \tag{2}\]  
Then, given the state \(j\) and the calculated minimum and maximum time for that barrier group, and the total discrete time-steps, the set of state variables is determined by Equation (3).