# Convergence Study of Minimizing the Nonconvex Total Delay Using the Lane-Based Optimization Method for Signal-Controlled Junctions

Authors: C. K. Wong; Y. Y. Lee
Journal: Discrete Dynamics in Nature and Society
 (2012)

---

## Abstract

This paper presents a 2D convergence density criterion for minimizing the total junction delay at isolated junctions in the lane-based optimization framework. The lane-based method integrates the design of lane markings and signal settings for traffic movements in a unified framework. The problem of delay minimization is formulated as a Binary Mix Integer Non Linear Program (BMINLP). A cutting plane algorithm can be applied to solve this difficult BMINLP problem by adding hyperplanes sequentially until sufficient numbers of planes are created in the form of solution constraints to replicate the original nonlinear surface in the solution space. A set of constraints is set up to ensure the feasibility and safety of the resultant optimized lane markings and signal settings. The main difficulty to solve this high-dimension nonlinear nonconvex delay minimization problem using cutting plane algorithm is the requirement of substantial computational efforts to reach a good-quality solution while approximating the nonlinear solution space. A new stopping criterion is proposed by monitoring a 2D convergence density to obtain a converged solution. A numerical example is given to demonstrate the effectiveness of the proposed methodology. The cutting-plane algorithm producing an effective signal design will become more computationally attractive with adopting the proposed stopping criterion.


---

## Body

## 1. Introduction

Over the past decades, various traffic modeling techniques have been developed and studied by many researchers (e.g., [1–8]). In the context of signal settings optimization at isolated junctions, it is always assumed that traffic pattern is arrived dynamically according to Poisson distribution. Pioneering works can be found in [9–11] for the stage-based signal timing design approach and incorporated into a commercial package called OSCADY. Improta and Cantarella [12] proposed a better phase-based approach to the problem of calculating signal settings. The cycle structure was specified by a set of binary variables relating to incompatible signal groups. A branch-and-bound technique was employed to solve the Binary Mixed Integer Linear Program (BMILP). Gallivan and Heydecker [13] developed a similar approach, in which the cycle structure was specified by one of the stage sequences. Heydecker [14] further reduced this problem difficulty by introducing a procedure to group all possibilities into a much smaller number of equivalence classes. The cycle structure of each equivalence class was represented by a “successor function” that makes the method computationally faster.Wong and Heydecker [15] and Wong and Wong [16] proposed a lane-based optimization method for determining the capacity-maximizing and cycle-length-minimizing signal settings for an isolated junction. The present study extends the lane-based optimization method for determining a combined set of lane markings and signal settings to minimize the traffic delay at an isolated signal-controlled junction. A cutting plane algorithm with a faster convergence criterion is proposed to solve the delay minimization problem. A numerical example is given to demonstrate the effectiveness of the proposed methodology. On the other hand, the concept of the convergence density in this paper originates from the posterior probability densities of the parameter values of a model in the probabilistic system identification method (e.g., [17–20]). Instead of pinpointing particular values assigned to the parameters of a model, the probabilistic identification method focuses on those parameter values with the highest posterior probability densities. This is similar to that the stopping criterion in this paper focuses on the subdomain formed by a set of gridlines with the highest density and the corresponding parameter values.


## 2. The Lane-Based Optimization Method

Saturation flow of a traffic lane prescribes the maximum number of vehicles that can leave a junction if full-green signal is given, and this discharge rate is defined by the following expression, which is generalized from that of Kimber et al. [21], that gives the maximum discharge flow rate of traffic flow on a traffic lane of different lane type, width, turning traffic proportion, and physical turning radius:(2.1)si,k=s̅i,k1+1.5∑j=1NT-1Pi,j,k/ri,j,k,
where si,k is the saturation flow of lane k in arm i, ri,j,k and Pi,j,k are the radius of the turning trajectory (= ∞ for straight-ahead movement) and the proportion of flow from arm i to arm j via lane k, and s̅i,k is the saturation flow of the lane if it is for straight-ahead movement only. In the lane-based optimization method, the control variables can be specified as follows. Let Λ=(Λb,Λc) be the set of control variables, where Λb and Λc are the subsets of binary and continuous variables, respectively.The subsetΛb consists of the following binary variables.Permitted movements:δ=(δi,j,k,j=1,…,NT-1;k=1,…,Li;i=1,…,Ni).Successor functions:Ω=(Ωi,j,l,m,((i,j),(l,m))∈Ψs).The subsetΛc consists of the following continuous variables.Designed lane flows:q=(qi,j,k,j=1,…,NT-1;k=1,…,Li;i=1,…,NT).Common flow multiplier:μ.Cycle length:ζ.Starts of green for movements:θ=(θi,j,j=1,…,NT-1;i=1,…,NT and j=1;i=1,…,NP).Durations of green for movements:φ=(ϕi,j,j=1,…,NT-1;i=1,…,NT and j=1;i=1,…,NP).Starts of green for traffic lanes:Θ=(Θi,k,k=1,…,Li;i=1,…,NT).Durations of green for traffic lanes:Φ=(Φi,k,k=1,…,Li;i=1,…,NT),wherei,m,j are subscripts denoting arms connecting to a junction, k is subscript denoting a traffic lane, NT is total number of traffic arms in a junction, Li is number of traffic lane from arm i,qi,j,k is assigned lane flow on traffic lane k for the traffic turning from arm i to arm j, Qi,j is given demand of traffic flow turning from arm i to arm j, μ is the common flow multiplier, δi,j,k is the permitted movement on a traffic lane k for the traffic turning from arm i to arm jin the form of a lane marking (= 1 exists/permitted or = 0 otherwise), Γ(i,j) is a user-defined mathematical function to find out the exit direction (i.e., which arm the approach traffic is leaving) from the jth destination arm counting from arm i, EΓ(i,j) is maximum number of exit lane for leaving traffic toward arm Γ(i,j), ζ is the operating cycle length (=reciprocal of cycle time), cmax is the maximum allowable limit of cycle time, cmin is the minimum allowable limit of cycle time, M is an arbitrary large integral number, θi,j is the start of green for a signal phase controlling the traffic turn from arm i to arm j, Θi,k is the start of green for a signal phase controlling the traffic turn from arm i on lane k, ϕi,j is the duration of green for a signal phase controlling the traffic turn from arm i to arm j, Φi,k is the duration of green for a signal phase controlling the traffic turn from arm i on lane k, gi,j is the minimum duration of green for a signal phase for the traffic turn from arm i to arm j, Ωi,j,l,m is a successor function governing the sequence of signal display within a signal cycle (= 1 if start of green of signal group (i,j) follows that of signal group (l,m) or = 0 if the opposite is true), Ψs is set of incompatible signal groups, Ψ is set of incompatible traffic movements, s̅i,k is saturation flow (maximum discharge flow rate) for straight-ahead movement on a traffic lane k from arm i, ri,j,k is turning radius for traffic turning from arm i to arm j one lane k, e is difference between effective green time and display green time durations (usually 1 second), and pi,k is maximum allowable degree of saturation (demand flow to saturation flow ratio) on a traffic lane k from arm i (usually take 90%).To formulate the present total delay optimization problem in the form of a Binary Mixed Integer Linear Program, linear constraint sets below are required to outline the feasible solution region ensuring safe operation of traffic signal plans and logical sequence of signal timings.Flow Conservation Balancing the Traffic Demand and Optimal Lane Flow Pattern
Consider(2.2)μQi,j=∑k=1Liqi,j,k,∀j=1,…,NT-1;i=1,…,NT.
Equation (2.2) is an equality constraint set mainly to ensure the sum of all optimized lane flows to be assigned on each traffic lane that will eventually be equal to the input turning demand flows.Minimum Permitted Movement on a Lane
Consider(2.3)∑j=1NT-1δi,j,k≥1,∀k=1,…,Li;i=1,…,NT.
This set of constraint is developed to ensure each traffic lane will be utilized to let through at least one traffic movement.Maximum Permitted Movements at the Exit
Consider(2.4)EΓ(i,j)≥∑k=1Liδi,j,k,∀j=1,…,NT-1;i=1,…,NT.
Equation (2.4) is a constraint set to make sure that there is sufficient number of traffic lanes at downstream exit to manage the vehicles leaving from upstream approach lanes for various turning directions.Permitted Movements Across Adjacent Lanes
Consider(2.5)1-δi,j,k+1≥δi,m,k,∀m=j+1,…,NT-1;j=1,…,NT-2;k=1,…,Li-1;i=1,…,NT.
To prevent internal conflicts, for example, a right turn on left-hand lane and a left turn on a right-hand lane in which vehicles will be clashed during green signal phases, constraint set in (2.5) is necessary to restrict the formation of lane marking on adjacent traffic lane from the same approach.Cycle Length
Consider(2.6)1cmin⁡≥ζ≥1cmax⁡.
Practically, all signal timings will be repeated in cycles in which a signal cycle should be selected within maximum and minimum bounds.Identical lane signal settings for common turns on lanes:
(2.7)M(1-δi,j,k)≥Θi,k-θi,j≥-M(1-δi,j,k),M(1-δi,j,k)≥Φi,k-ϕi,j≥-M(1-δi,j,k).
In the present formulation, green times will be defined on both lane basis or turning basis. Once a specific traffic turn is assigned on a particular traffic lane, their signal settings should be identical and constraint sets in (2.7) should be included.Start of Green
Consider(2.8)1≥θi,j≥0,∀j=1,…,NT-1;i=1,…,NT.
Having said that all signal timings will be repeated in signal cycles and thus the start of green time should always be chosen within a signal cycle, (2.8) is given to maintain this design criteria.Duration of Green
Consider(2.9)1≥ϕi,j≥gi,jζ,∀j=1,…,NT-1;i=1,…,NT.
Similarly, the assigned green time duration for a turning movement should always be less than the duration of a signal cycle. For safety concern, traffic signals should not be changed too frequently so that the assigned green time should always be greater than a user-defined minimum green time. Equation (2.9) is developed for this purpose.Order of Signal Displays
Consider(2.10)Ωi,j,l,m+Ωl,m,i,j=1,∀((i,j),(l,m))∈Ψs.
Since conflicting traffic movements from different approaches cannot receive green times simultaneously, a successor function and constraint set in (2.10) should be defined to order the signal display in a safe sequence.Clearance Time
Consider(2.11)θl,m+Ωi,j,l,m+M(2-δi,j,k-δl,m,n)≥θi,j+ϕi,j+ωu,vζ,∀(u,v)∈Ψ.
With the introduction of a successor function, the order of signal displays can be designed. For those conflicting movements, a clearance time should be given so that the traffic in the common area of a junction can be cleared before other conflicting traffic movement can enter the junction for discharging.Prohibited Movement
Consider(2.12)Mδi,j,k≥qi,j,k≥0,∀k=1,…,Li;j=1,…,NT-1;i=1,…,NT.
To design optimal lane marking pattern, some vehicle turnings will be banned on different traffic lanes. If the lane marking for a particular vehicle turn is prohibited, the corresponding assigned lane flow must be forced to be zero. Hence, (2.12) is formulated as one of the design constraint sets.Flow Factor
Consider(2.13)M(2-δi,j,k-δi,j,k+1)≥1s̅i,k∑j=1,…,NT-1(1+1.5ri,j,k)qi,j,k-1s̅i,k+1∑j=1,…,NT-1(1+1.5ri,j,k+1)qi,j,k+1≥-M(2-δi,j,k-δi,j,k+1),∀k=1,…,Li-1;i=1,…,NT.
If an identical lane marking is assigned on two adjacent lanes, the flow factors for the two traffic lanes must be identical to ensure the queue lengths are equal. Equation (2.13) should be included to prevent unequal vehicle queue development.Maximum Acceptable Degree of Saturation
Consider(2.14)Φi,k+eζ≥1pi,ks̅i,k∑j=1,…,NT-1(1+1.5ri,j,k)qi,j,k,∀k=1,…,Li;i=1,…,NT.
In the present design framework, it is necessary to provide sufficient green time for different traffic movements such that their demand flow to capacity ratios are always within a user acceptable level. Equation (2.14) is developed to ensure the assignment of enough green time to handle the demand traffic.For isolated signal control junctions, there are three common criteria for optimizing the signal settings: capacity maximization, cycle length minimization, and delay minimization. Alternative signal settings can be generated to fulfill specific operating requirements if different optimizing objectives are chosen. In general, the delay function D that is used as the objective for optimization is nonlinear. The problem has to be formulated as the BMINLP that is shown as follows:
(2.15)MinimizeΛ=(Λb,Λc)D
subject to the linear constraints in (2.2)–(2.14) and μ=1, where D defines the total delay of the junction.


## 3. Delay Optimization and 2D Convergence Density

Due to the complicated high dimension solution space and the nonconvexity of the objective delay function, the piecewise linearization approach is not applicable to the present problem. A classical cutting plane algorithm with a 2D convergence density is proposed and discussed in the following sections to solve the BMINLP problem. Now, consider the auxiliary continuous variableλ as the objective function which is the approximated delay found in the cutting plane algorithm (it is approximated as the solution is from the set of linearized hyperplane but not from the original nonlinear delay function), with the following additional nonlinear constraint:(3.1)D-λ≤0.
Then, the stopping criterion is considered and the 2D convergence density function is defined by(3.2)π(Δ,xo,yo)=Count(xo≤xκ≤xo+Δ⋀yo≤yκ≤yo+Δ)κ¯,forκ=1toκ¯,
where xκ=λ̃κ and yκ=D̃κ; κ¯ is the number of iterations; Count is a function which counts the times of xκ and yκ that match the specified criteria. xo and yo are the coordinates of any grid point within the domains of λ and D.D̃κ and λ̃κ are the numerical values at the solution point. Note that the domains λ and D are divided by a set of rectangular grid lines; the interval between any two grid lines is Δ. The stopping requirement is that there is one grid box ofxoandyowith the highest convergence density value for the last n iterations.If the interval of Δ is smaller (i.e., the grid box size is smaller), it requires more iterations for the coordinates of xκ and yκ staying the same grid box in the last n iterations to achieve the highest convergence density value. It is noted that the nonlinear constraint is linearized by a first-order Taylor’s series expansion to form a linear function Lκ, where(3.3)Lκ=[(∑i=1NT∑k=1LiDi,kκ-λκ)+ακ({∑j=1NT-1(∂Di,k∂qi,j,k)κ(qi,j,k-qi,j,kκ)}∑i=1NT∑k=1Li({∑j=1NT-1(∂Di,k∂qi,j,k)κ(qi,j,k-qi,j,kκ)}(∂Di,k∂γi,k)κ(γi,k-γi,kκ)+(∂Di,k∂ζ)κ(ζ-ζκ)+∑j=1NT-1(∂Di,k∂qi,j,k)κ(qi,j,k-qi,j,kκ))-(λ-λκ){∑j=1NT-1(∂Di,k∂qi,j,k)κ(qi,j,k-qi,j,kκ)}){∑j=1NT-1(∂Di,k∂qi,j,k)κ(qi,j,k-qi,j,kκ)}]≤0,
in which κ specifies the κth linearization point, γi,k=Φi,k+eζ, and ακ is a parameter that controls the degree of a cut in the feasible region. The lane-based delay minimization problem becomes the minimization of λ,subject to constraints in (2.2)–(3.1), μ=1, and all of the constraints (3.3) that were generated in previous iterations.


## 4. Numerical Example

The following steady-state delay formula, based on random arrivals and regular departure patterns, is used [9, 10]:(4.1)Di,k=910(∑jqi,j,k(1-γi,k)22ζ(1-yi,k)+(yi,k/γi,k)22(1-yi,k/γi,k)),
where Di,k is the rate of delay for the traffic lane k on arm i of a signal junction. The total rate of delay of the junction,D, is the sum of the delays for all traffic lanes on all arms D=∑i=1NT∑k=1LiDi,k. This formula is widely used for the estimation of junction delay.Consider a four-arm junction with four traffic lanes on each arm, as shown in Figure1. The maximum cycle length is set at 120 seconds, and the maximum acceptable degree of saturation is 90% in all lanes. The minimum greens are 5 seconds for traffic movements. The traffic demands are given in Table 1. The required clearance time for any two conflicting movements (including both traffic and pedestrian movements) is 6 seconds. We also take the solution of capacity maximization as the starting point for linearization in the cutting plane algorithm. Set all initial α’s = 1.0, and a multiplication factor 10.0 is applied to update the α’s each time there is an invalid underestimator. The cutting plane algorithm is then solved by a commercial package called “The mathematical programming language” in which a CPLEX solver is installed to solving the Binary Mixed Integer Linear Program.Table 1
The traffic demand for the example junction.
Traffic demand  in veh/hrTo arm1234From arm1—5002001002100—1005003300300—3004100400400—Figure 1
The layout of the four-arm example junction.Now, consider the stopping requirements in (3.2). In this example (see Figure 2), n=10 and Δ = 2 (the domain of λ and D are 0 to 50). The two-dimensional plot of the convergence density is shown in Figure 3. It can be seen that from 84th to 93rd iterations, the convergence density value of the marked grid box is the highest. The minimum delay from the cutting plane algorithm is 26.683 veh-s/s, and the corresponding optimized cycle length to operate the junction is 71.24 seconds.Two-dimensional plot of the convergence density.
(a)(b)(c)(d)Figure 3
Optimized lane markings for the example problem.Typical results of the proposed solution algorithms, including the lane permitted movements, designed lane flows, and the signal settings, are given in Table2. The total delays, based on Webster’s delay function, are calculated and put in the last column of the tables. It can also be verified that the degrees of saturation for all traffic lanes are within the specified upper limit of 90%. Corresponding optimized lane marking pattern is given in Figure 3 diagrammatically. A summary of the model statistics for the example calculations is presented in Table 3.Table 2
Optimization results from the cutting plane algorithm.
Optimal cycle length = 71.24 seconds(2.1)(2.2)(2.3)–(2.6)(2.7)(8)(2.8)(2.9)(2.10)(2.11)(2.12)(2.13)From armLaneTo armSum of lane flowTurning proportionSaturation flowyEffective greenDegree of sat.Green startTotal delay123411241.4241.41.001746.70.138227.80.35410.01.014812258.6258.61.001871.10.138227.80.35410.01.080813200.0200.00.002105.00.095011.00.612916.81.841914100.0100.01.001871.10.05346.00.634635.41.28492148.348.31.001746.70.02769.40.208656.80.35752251.751.71.001871.10.02769.40.208656.80.381223500.0500.00.002105.00.237519.90.851446.45.231624100.0100.01.001871.10.053411.80.32380.00.725631300.0300.01.001746.70.171830.40.40290.01.184232300.0300.00.002105.00.142513.60.746216.83.026133150.0150.01.001871.10.08028.60.666932.81.725034150.0150.01.001871.10.08028.60.666932.81.725041100.0100.01.001746.70.057330.90.132135.40.312342400.0400.00.002105.00.190019.90.681146.42.941143200.0200.01.001871.10.106911.80.647571.21.925544200.0200.01.001871.10.106911.80.647571.21.925526.6830Table 3
Statistics of the example problem.
Model variablesNumber of variablesConstraintsNumber of constraintsBinary variables142Cutting planes93Permitted movements40Starts of green58Successor functions102Durations of green60Order of signal displays51Continuous variables110Clearance times68Lane flows48Cycle length1Starts of green29Maximum acceptable degree of saturation16Durations of green30Flow conservations12Cycle length1Minimum permitted movements in a lane8Common flow multiplier1Maximum permitted movements at exits3Auxiliary variable1Prohibited movements40Permitted movements across adjacent lanes72Flow factors72Lane signal settings176Others53Total number252783Figures4(a) and 4(b) show the number of all iterations and the minimum delay against the number of iterations in the highest density box, respectively. It can be seen that the smaller the grid size is, the higher the number of all iterations is; the higher the number of iterations required in the highest density box is, the higher the number of all iterations is. Figures 4(c) and 4(d) show the number of all iterations and the minimum delay against the relative error which is the main parameter in the stopping criteria in [22]. Similar to the observation in Figures 4(a) and 4(b), the minimum delay can converge to a certain value when the number of all iterations increases. The main differences between the convergence patterns in the present study and [22] are that the curves representing the numbers of all iterations in Figure 4(a) are more linear; the minimum delay in Figure 4(b) can converge faster to a certain value against the number of iterations required in the highest density box (the curve looks more concave).(a) The number of all iterations against the number of iterations in the highest density box. (b) The minimum delay against the number of iterations in the highest density box. (c) The number of all iterations plotted against the relative error (the stop criteria in [22]). (d) The minimum delay against the relative error.
(a)(b)(c)(d)


## 5. Conclusions

Lane-based optimization models have been presented in this paper. While the capacity maximization and cycle length minimization for isolated signal-control junctions are formulated as BMILP problems that can be solved by the standard branch-and-bound technique [16], the delay minimization problem for isolated junctions is a BMINLP because of the nonlinear delay function [22]. The cutting plane algorithms with a 2D convergence density stopping criterion have been proposed to solve the problem. The nonlinear delay function is approximated by successive linearizations. The BMINLP problem is transformed into a series of BMILP problems that are solved by the standard branch-and-bound technique. To achieve a more cost-effective method for the lane-based optimization of delay at isolated signalized junctions, the cutting plane algorithm should be applied together with the new proposed stopping criterion taking the 2D convergence density into considerations.



---

*Source: 858731-2012-06-14.xml*