# Continuous and Discrete-Time Optimal Controls for an Isolated Signalized Intersection

Authors: Jiyuan Tan; Xiangyun Shi; Zhiheng Li; Kaidi Yang; Na Xie; Haiyang Yu; Li Wang; Zhengxi Li
Journal: Journal of Sensors
 (2017)

---

## Abstract

A classical control problem for an isolated oversaturated intersection is revisited with a focus on the optimal control policy to minimize total delay. The difference and connection between existing continuous-time planning models and recently proposed discrete-time planning models are studied. A gradient descent algorithm is proposed to convert the optimal control plan of the continuous-time model to the plan of the discrete-time model in many cases. Analytic proof and numerical tests for the algorithm are also presented. The findings shed light on the links between two kinds of models.


---

## Body

## 1. Introduction

Along with the fast increase of auto population, urban streets are becoming more crowded nowadays. To relieve congestions and reduce accidents, various traffic control methods have been proposed since the late 1950s [1].As a typical traffic scenario, oversaturated intersections attracted consistent interest during the last six decades [2, 3]. The term “oversaturated” means the following: the vehicles that remained since the last cycle plus the vehicles that newly arrived exceed the capacity of the intersection. This leads to the carryover of vehicle queues (at least in one leg of the intersection) to the next cycle.Discussions on the road networks that consist of many oversaturated intersections can be found in researches done by Chang and Sun [4], Di Febbraro and Sacco [5], Dotoli and Fanti [6], Ma [7, 8], and Sun et al. [9, 10]. In the research done by Varaiya [11] and Le et al. [12], the study of pressure-based signal control developed stability properties of a decentralized signal timing policy for networks with stochastic arrivals. But for a real-time signal timing optimization problem, the data that could be used is the arriving information of vehicles in the recent several signal cycles (data could be gotten by connecting vehicle technology, etc.). The optimization objects and scenarios are different between the model in this paper and pressure-based policies. This paper will focus on the isolated oversaturated intersection.Usually, researchers aim to find an optimal signal timing plan that minimizes the total delay of vehicles passing this intersection. The total delay is often defined as the time integral of the sum of all queue lengths for all legs of the intersection over a given time horizon. However, the total delay is a nonlinear and nonconvex function of control variables (e.g., green phases), which makes it difficult to optimize. One promising approach is to apply heuristic algorithms to solve the formulated optimization problem. For example, the genetic algorithm was applied by Park et al. [13] to optimize the total delay. An alternative approach is to first approximate the nonconvex total delay with some convex functions and then solve the newly formulated optimization problem. The rest of this paper will focus on the second approach within a typical traffic scenario: an isolated intersection with only two movements.There are mainly two kinds of convexified models for this scenario. The first kind of models originated from Gazis [3] who used continuous-time differential equations to describe the traffic dynamics. The cycle length, departing flow rates, and arriving flow rates in Gazis [3] were all assumed to be constant. Michalopoulos and Stephanopoulos [14, 15] extended the continuous-time model by including the maximum queue lengths constraints and time-variant arrival flow rates. Such formulations led to a classical control problem that can be solved via the Pontryagin Maximum Principle (PMP) [16]. However, the obtained continuous-time signal timing plan should be discretized into the corresponding discrete-time signal timing plan that can be executed in practice.The second kind of models uses discrete-time difference equations to describe the traffic dynamics [7, 8, 17–19]. The corresponding design problem can then be formulated as a linear programming (LP) problem [20–25]. One interesting question that naturally arises is how to depict the difference and connection between the discrete-time model and the continuous-time model.Recently, Ioslovich et al. [26] studied the formulated LP problem by considering the corresponding continuous-time approximation model and gave an elegant approximate solution in continuous-time forms. However, it was not verified how this approximate solution differs from the accurate solution (the solution obtained by the continuous-time model). Whether a discretized version of this continuous-time approximate solution is still optimal to the LP problem also needs further discussions.Zou et al. [27] have given a preliminary result on the relationship between the continuous-time model and the discrete-time model. Zou et al. applied a graphical method to adjust the continuous-time approximate solution to a discrete-time accurate solution. They assumed that both streams are dispatched simultaneously and the adjustment method does not influence the clearance cycle. It is shown that the approximate solution can be adjusted to the optimal solution by changing the green ratio in the switching cycle. However, the discrete-time LP problem in Ioslovich et al. [26] is more complex than the one considered in [27], since the two streams are allowed to be cleared at different times. Merely changing the green ratios at the switching cycle may not obtain the accurate solution.In this paper, the LP problems proposed by Ioslovich et al. [26] are directly attacked using the strong duality theorem [28]. It is first shown that the approximate solution and the accurate solution do not coincide in many situations. Then, the relationship between the approximate solution and the accurate solution will be discussed. The errors introduced by discretization are carefully studied. It is shown that, in many cases, the discretized approximate solution can be converted to the accurate solution within a few gradient descent adjustments. Finally, an algorithm is proposed to implement this conversion. These findings shed light on the connection between the continuous-time and discrete-time signal timing models.To give a detailed analysis, the rest of this paper is arranged as follows. Section2 introduces the LP problem proposed by Ioslovich et al. [26] and lists the nomenclature used in this paper. Section 3 proposes two counterexamples to show that the optimality of the discretized approximate solution may not hold. Section 4 discusses the difference and connection between the discrete-time model and the continuous-time model. Finally, Section 5 concludes the paper.


## 2. Problem Presentation

### 2.1. Nomenclature and Assumptions

For presentation simplicity, the nomenclature in this paper follows Ioslovich et al. [26] as shown in Nomenclature List. Similar to Ioslovich et al. [26], consider an isolated intersection with two one-way streams m1 and m2 governed by signal lights, as shown in Figure 1. Note that the two-stream isolated intersection is chosen as an initial building block to understand the connection between the continuous-time model and the discrete-time model. This is a widely applied treatment even in recent works (e.g., [23]). Nevertheless, this assumption can be relaxed to consider general intersections. Both the continuous model and the discrete model are able to handle cases with more generalized intersections. Although it is hard to directly compare the two types of models in generalized intersections, we expect that the findings in this paper can shed light on more generalized intersections.Figure 1
An isolated intersection with two one-way movementsm1 and m2.Likewise, the following assumptions are imposed as in Ioslovich et al. [26].Assumption 1.
(a) Each signal cycle starts with a green light form1.
(b) There is no lost time for each cycle. Suppose that the green ratio for streamm1 in cycle k is denoted as uk; the green ratio for stream m2 is then equal to 1-uk.
(c) The arrival flow rates and the saturation departure flow rates of both streams are constant over time. Denoteai as the arrival flow rates for mi and di as the departure flow rates.
(d) Without loss of generality,m1 is assumed to be the main stream (i.e., d1>d2).
(e) For some reasons (e.g., physical constraints), both streams are constrained by minimum green ratios. Defineumin and 1-umax as the minimum green ratios for m1 and m2, respectively; then, the constraint on uk is represented as umin≤uk≤umax.
(f) There exists a signal timing strategy such that queues in both streams can be cleared finally but may not be in the same cycle. DefineuL=a1/d1 and uH=1-a2/d2. This assumption is written as uL<uH, uL<umax, and umin<uH.
(g) Cycle lengths are known to be constantT.
In Assumption1, (a)–(f) are inherited from Ioslovich et al. [26] directly and (g) is added to simplify the discussion. In fact, if cycle lengths are not fixed, a similar conclusion can still be drawn but the detailed timing plan is much more complicated.


### 2.2. The Discrete-Time LP Model and Its PMP Solution

Similar to Ioslovich et al. [26], the discrete-time model is formulated as the following problem to minimize the total delay of vehicles:(1)min⁡JD=∑k=0Nq1k+q2k+a1+a22T∑k=0N-1uk(2)s.t.q1k+1≥max⁡q1k+d1Tuk-uL,a1T1-uk(3)q2k+1≥max⁡q2k+d2TuH-uk,0(4)umin≤uk≤umax(5)qi0=qi,int,i=1,2,for k=0,1,…,N-1.In (1)–(5), the objective function is a linear approximation for total delay. The decision variables are uk, k=0,1,…,N. For presentation convenience, it is assumed that the number of total cycles N is large enough such that both streams are cleared before cycle N. Equations (2) and (3) represent the evolution of both queues in time. Equation (4) gives the upper and lower bound of the green ratio in each cycle. Equation (5) is the initial queue lengths. It is easy to verify that this LP problem is equivalent to the Relaxed Discrete-Event Max-Plus Problem proposed by Haddad et al. [22].In Ioslovich et al. [26], the above LP (see (1)–(5)) was transformed into an equivalent continuous-time optimal control problem (see (6)) with free terminal timetf. The decision variable is vt.(6)minJC=∫0tfq1t+q2tdts.t.dq1tdt=d1uL-vt+w1tdq2tdt=d2vt-uH+w2tqiT≥0,i=1,2wit≥0,i=1,2umin≤vt≤umaxqi0=qi,int,qitf=0,i=1,2.Ioslovich et al. [26] applied Pontryagin Maximum Principle (PMP) to derive the optimal solution to the continuous-time model (see (6)).Particularly, the following four cases were discussed with respect to the order ofuL,uH,umin, and umax: (I) uL<umin<uH<umax; (II) uL<umin<umax<uH; (III) umin<uL<umax<uH; (IV) umin<uL<uH<umax.Table1 lists the solution. The optimal continuous-time solution is denoted asv∗(t). ts is the switching time where the optimal control switches. M and R are represented as(7)M=d1umax-uLd2uH-umax,R=umin-uLuH-umin.Table 1
The optimal solution to the continuous model.
Case
Condition
Solution
Switching time,ts
I(a)
q
1
,
i
n
t
q
2
,
i
n
t
>
R
v∗(t)=umax,t≤tsumin,t>ts
q
1
,
i
n
t
-
R
q
2
,
i
n
t
d
2
(
u
m
a
x
-
u
H
)
(
R
-
M
)
I(b)
q
1
,
i
n
t
q
2
,
i
n
t
<
R
v
∗
(
t
)
=
u
m
i
n
II(a)
R
<
q
1
,
i
n
t
q
2
,
i
n
t
<
M
v∗(t)=umax,t≤tsumin,t>ts
q
1
,
i
n
t
-
R
q
2
,
i
n
t
d
2
(
u
m
a
x
-
u
H
)
(
R
-
M
)
II(b)
q
1
,
i
n
t
q
2
,
i
n
t
<
R
v
∗
(
t
)
=
u
m
i
n
II(c)
q
1
,
i
n
t
q
2
,
i
n
t
>
M
v
∗
(
t
)
=
u
m
a
x
III(a)
q
1
,
i
n
t
q
2
,
i
n
t
>
M
v
∗
(
t
)
=
u
m
a
x
III(b)
q
1
,
i
n
t
q
2
,
i
n
t
<
M
v
∗
(
t
)
=
u
m
a
x
,
t
<
t
s
u
L
,
t
>
t
s
q
1
,
i
n
t
d
1
(
u
m
a
x
-
u
L
)
IV
v
∗
(
t
)
=
u
m
a
x
,
t
<
t
s
u
L
,
t
>
t
s
q
1
,
i
n
t
d
1
(
u
m
a
x
-
u
L
)For example, Figure2 illustrates the evolution of queue lengths under the optimal solution for Case I(a). It is observed that the optimal solution is a two-stage strategy, namely, bang-bang control. The green ratio remains umax at first, causing the length of stream m1 to decrease sharply and stream m2 to increase. After the switching time ts, the green ratio changes into umin and both streams start to decrease. The optimal switch-over point where the solution switches from maximum to minimum green split is given in Table 1.Figure 2
An illustration of the queue lengths and optimal timing plan in Case I(a).The discretized solution ofv∗t is obtained as follows. Suppose the cycle length is T; the discretization is done as(8)uDk=v∗kT,k=0,1,…,N-1.For presentation simplicity, the solutionuDk, k=0,1,…,N-1, is called the discretized approximate solution in the rest of this paper.


### 2.3. The Steady State and the Steady-State Solution

According to Haddad et al. [22], the steady state is defined as the state where the queue lengths are the same in the beginning and end of each cycle. This means, given the green ratio for a certain stream, the queue lengths of this stream keep the same in a certain period. Denote the queue lengths in the steady state as qi,ss,i=1,2, and the green ratio in the steady state as uss. So, considering a single-cycle version of discrete-time model (see (1)–(5)), the steady state can be formulated into the following model:(9)minq1,ss+q2,ss+a1+a22Tuss(10)s.t.q1,ss≥maxq1,ss-d1Tuss-uL,a11-ussT(11)q2,ss≥maxq2,ss-d2TuH-uss,0(12)umin≤uss≤umax.The objective equation (9) is a linear approximation of delay in a single cycle. Equations (10) and (11) depict the queue evolution. Equation (12) gives the bound of the green ratio.The optimal green ratiouss is called the steady-state solution. Haddad et al. [22] gave a neat analytical form of uss as follows:(13)uss=maxuL,umin,a1<a2,minuH,umax,a1>a2.According to Haddad et al. [22], the two streams that follow the discrete-time model (see (1)–(5)) will eventually enter the steady state under Assumptions (a)–(g). Therefore, in the accurate solution, the green ratios in the steady state are the steady-state solution uss.


## 2.1. Nomenclature and Assumptions

For presentation simplicity, the nomenclature in this paper follows Ioslovich et al. [26] as shown in Nomenclature List. Similar to Ioslovich et al. [26], consider an isolated intersection with two one-way streams m1 and m2 governed by signal lights, as shown in Figure 1. Note that the two-stream isolated intersection is chosen as an initial building block to understand the connection between the continuous-time model and the discrete-time model. This is a widely applied treatment even in recent works (e.g., [23]). Nevertheless, this assumption can be relaxed to consider general intersections. Both the continuous model and the discrete model are able to handle cases with more generalized intersections. Although it is hard to directly compare the two types of models in generalized intersections, we expect that the findings in this paper can shed light on more generalized intersections.Figure 1
An isolated intersection with two one-way movementsm1 and m2.Likewise, the following assumptions are imposed as in Ioslovich et al. [26].Assumption 1.
(a) Each signal cycle starts with a green light form1.
(b) There is no lost time for each cycle. Suppose that the green ratio for streamm1 in cycle k is denoted as uk; the green ratio for stream m2 is then equal to 1-uk.
(c) The arrival flow rates and the saturation departure flow rates of both streams are constant over time. Denoteai as the arrival flow rates for mi and di as the departure flow rates.
(d) Without loss of generality,m1 is assumed to be the main stream (i.e., d1>d2).
(e) For some reasons (e.g., physical constraints), both streams are constrained by minimum green ratios. Defineumin and 1-umax as the minimum green ratios for m1 and m2, respectively; then, the constraint on uk is represented as umin≤uk≤umax.
(f) There exists a signal timing strategy such that queues in both streams can be cleared finally but may not be in the same cycle. DefineuL=a1/d1 and uH=1-a2/d2. This assumption is written as uL<uH, uL<umax, and umin<uH.
(g) Cycle lengths are known to be constantT.
In Assumption1, (a)–(f) are inherited from Ioslovich et al. [26] directly and (g) is added to simplify the discussion. In fact, if cycle lengths are not fixed, a similar conclusion can still be drawn but the detailed timing plan is much more complicated.


## 2.2. The Discrete-Time LP Model and Its PMP Solution

Similar to Ioslovich et al. [26], the discrete-time model is formulated as the following problem to minimize the total delay of vehicles:(1)min⁡JD=∑k=0Nq1k+q2k+a1+a22T∑k=0N-1uk(2)s.t.q1k+1≥max⁡q1k+d1Tuk-uL,a1T1-uk(3)q2k+1≥max⁡q2k+d2TuH-uk,0(4)umin≤uk≤umax(5)qi0=qi,int,i=1,2,for k=0,1,…,N-1.In (1)–(5), the objective function is a linear approximation for total delay. The decision variables are uk, k=0,1,…,N. For presentation convenience, it is assumed that the number of total cycles N is large enough such that both streams are cleared before cycle N. Equations (2) and (3) represent the evolution of both queues in time. Equation (4) gives the upper and lower bound of the green ratio in each cycle. Equation (5) is the initial queue lengths. It is easy to verify that this LP problem is equivalent to the Relaxed Discrete-Event Max-Plus Problem proposed by Haddad et al. [22].In Ioslovich et al. [26], the above LP (see (1)–(5)) was transformed into an equivalent continuous-time optimal control problem (see (6)) with free terminal timetf. The decision variable is vt.(6)minJC=∫0tfq1t+q2tdts.t.dq1tdt=d1uL-vt+w1tdq2tdt=d2vt-uH+w2tqiT≥0,i=1,2wit≥0,i=1,2umin≤vt≤umaxqi0=qi,int,qitf=0,i=1,2.Ioslovich et al. [26] applied Pontryagin Maximum Principle (PMP) to derive the optimal solution to the continuous-time model (see (6)).Particularly, the following four cases were discussed with respect to the order ofuL,uH,umin, and umax: (I) uL<umin<uH<umax; (II) uL<umin<umax<uH; (III) umin<uL<umax<uH; (IV) umin<uL<uH<umax.Table1 lists the solution. The optimal continuous-time solution is denoted asv∗(t). ts is the switching time where the optimal control switches. M and R are represented as(7)M=d1umax-uLd2uH-umax,R=umin-uLuH-umin.Table 1
The optimal solution to the continuous model.
Case
Condition
Solution
Switching time,ts
I(a)
q
1
,
i
n
t
q
2
,
i
n
t
>
R
v∗(t)=umax,t≤tsumin,t>ts
q
1
,
i
n
t
-
R
q
2
,
i
n
t
d
2
(
u
m
a
x
-
u
H
)
(
R
-
M
)
I(b)
q
1
,
i
n
t
q
2
,
i
n
t
<
R
v
∗
(
t
)
=
u
m
i
n
II(a)
R
<
q
1
,
i
n
t
q
2
,
i
n
t
<
M
v∗(t)=umax,t≤tsumin,t>ts
q
1
,
i
n
t
-
R
q
2
,
i
n
t
d
2
(
u
m
a
x
-
u
H
)
(
R
-
M
)
II(b)
q
1
,
i
n
t
q
2
,
i
n
t
<
R
v
∗
(
t
)
=
u
m
i
n
II(c)
q
1
,
i
n
t
q
2
,
i
n
t
>
M
v
∗
(
t
)
=
u
m
a
x
III(a)
q
1
,
i
n
t
q
2
,
i
n
t
>
M
v
∗
(
t
)
=
u
m
a
x
III(b)
q
1
,
i
n
t
q
2
,
i
n
t
<
M
v
∗
(
t
)
=
u
m
a
x
,
t
<
t
s
u
L
,
t
>
t
s
q
1
,
i
n
t
d
1
(
u
m
a
x
-
u
L
)
IV
v
∗
(
t
)
=
u
m
a
x
,
t
<
t
s
u
L
,
t
>
t
s
q
1
,
i
n
t
d
1
(
u
m
a
x
-
u
L
)For example, Figure2 illustrates the evolution of queue lengths under the optimal solution for Case I(a). It is observed that the optimal solution is a two-stage strategy, namely, bang-bang control. The green ratio remains umax at first, causing the length of stream m1 to decrease sharply and stream m2 to increase. After the switching time ts, the green ratio changes into umin and both streams start to decrease. The optimal switch-over point where the solution switches from maximum to minimum green split is given in Table 1.Figure 2
An illustration of the queue lengths and optimal timing plan in Case I(a).The discretized solution ofv∗t is obtained as follows. Suppose the cycle length is T; the discretization is done as(8)uDk=v∗kT,k=0,1,…,N-1.For presentation simplicity, the solutionuDk, k=0,1,…,N-1, is called the discretized approximate solution in the rest of this paper.


## 2.3. The Steady State and the Steady-State Solution

According to Haddad et al. [22], the steady state is defined as the state where the queue lengths are the same in the beginning and end of each cycle. This means, given the green ratio for a certain stream, the queue lengths of this stream keep the same in a certain period. Denote the queue lengths in the steady state as qi,ss,i=1,2, and the green ratio in the steady state as uss. So, considering a single-cycle version of discrete-time model (see (1)–(5)), the steady state can be formulated into the following model:(9)minq1,ss+q2,ss+a1+a22Tuss(10)s.t.q1,ss≥maxq1,ss-d1Tuss-uL,a11-ussT(11)q2,ss≥maxq2,ss-d2TuH-uss,0(12)umin≤uss≤umax.The objective equation (9) is a linear approximation of delay in a single cycle. Equations (10) and (11) depict the queue evolution. Equation (12) gives the bound of the green ratio.The optimal green ratiouss is called the steady-state solution. Haddad et al. [22] gave a neat analytical form of uss as follows:(13)uss=maxuL,umin,a1<a2,minuH,umax,a1>a2.According to Haddad et al. [22], the two streams that follow the discrete-time model (see (1)–(5)) will eventually enter the steady state under Assumptions (a)–(g). Therefore, in the accurate solution, the green ratios in the steady state are the steady-state solution uss.


## 3. The Nonoptimality of the Discretized Approximate Solution

In this section, it is shown that the discretized approximate solution does not always coincide with the accurate solution. The term “coincide” here means that the discretized approximate solution is not always optimal for the discrete-time model. In particular, two counterexamples are constructed. The first counterexample is used to deal with Case I and Case II where the minimum green ratioumin plays an important role in the approximate solution. In contrast, the second counterexample is used to handle Case III and Case IV where the minimum green ratio umin does not influence the approximate solution. The two counterexamples are as follows.Counterexample 1 (for Case I and Case II).
The parameters are set asq1,int = 60, q2,int = 20, d1 = 0.55, d2 = 0.30, a1 = 0.15, a1 = 0.10, umin = 0.40, umax = 0.80, T = 160, and N = 6. Then, the accurate solution and the discretized approximate solution are shown in Figure 3(a).Figure 3
The two counterexamples. The dotted line represents the discretized approximate solution. The solid line represents the accurate solution.
(a)
(b)Counterexample 2 (for Case III and Case IV).
The parameters are set asq1,int = 40, q2,int = 40, d1 = 0.60, d2 = 0.35, a1 = 0.15, a1 = 0.10, umin = 0.15, umax = 0.80, T = 100, and N = 25. Then, the accurate solution and the discretized approximate solution are shown in Figure 3(b).As is shown in Figure3, the accurate solution deviates from the discretized approximate solution in two ways. In Counterexample 1, the accurate solution roughly remains as a bang-bang form before the system enters steady state. The difference concentrates around the switching cycle and steady state. However, in Counterexample 2, the accurate solution exhibits oscillation and differs from the discretized approximation solution in almost every cycle.Such deviations are caused by discretization and can be classified into two categories.The first category of deviations is caused by the discretization of the model constraints. For the continuous-time model, the queue length for streammi is lower-bounded by the constraint q1k≥0, while for the discrete-time model, the corresponding constraint is q1k≥a1T1-uk. When cycle length T is large, the discretization of model constraints may introduce huge errors. In Counterexample 1, the switching time locates in the middle of a cycle. As shown in Figure 4, the discretization leads to waste of green ratio around the switching cycle due to the restriction of the minimum green ratio. When T is small enough, the solution of the continuous-time model and the solution of the discrete-time model are coherent. A proper T should be selected to ensure consistency.Figure 4
An illustration of the error caused by discretization. The dotted line represents the queue lengths in the continuous-time model. The solid line represents the queue lengths in the discrete-time model.The second category deviation is caused by the discretization of the approximate solution. In Counterexample2, the clearance time of stream m1 locates in the middle of a cycle. So, the discretization causes oscillation in the accurate solution.


## 4. The Relationship between the Discretized Approximate Solution and the Accurate Solution

In this section, the connection between the discrete approximate solution and the accurate solution is further discussed.For Case I and Case II, the errors are relatively concentrated. The discretized approximate solution does not deviate largely from the accurate solution in many cases. In fact, the discretized approximate solution can be modified to the accurate solution by some minor adjustments; see Algorithm1. The details of adjustments will be discussed in Sections 4.1–4.3.Algorithm 1:The adjusting algorithm for the discretized approximate solution in Case  I(a).
(1) Set u(k) as the discretized approximate solution. Calculate k^1,k^2,k^s by Eq. (15)-(16);
(2) ifk^1<k^2then
(3)  Set uk^s-1←min⁡{q1k^s-1/T/d1-a1,umax} and set uk←umin,k≥k^s;
(4)  Update k^2 by Eq. (16) and set k^1←k^s;
(5)  ifuk^s-1≤umin  then
(6)   uk^s-1←umin,k^s←k^1-1 and update k^1 and k^2 by Eq. (15) and (16);
(
7
)  end
(
8
)  end
(
9
)  whileQk^1,k^2,k^s-1>0do;
(
10
)  k^2←k^2-1. Update uk^s-1 such that stream m2 is cleared exactly in cycle k^2;
(
11
)  Update k^1 by Eq. (15);
(
12
)  ifQk^1,k^2+1,k^s-1<0then
(
13
)   k^2←k^2+1. Find the minimum k^1 such that Qk^1+1,k^2,k^s-1<0;
(
14
)   Update uk^s-1 such that stream m1 is cleared exactly in cycle k^1;
(
15
)   Set k^1←k^1+1;
(
16
)  end
(
17
) ifuk^s-1<uminthen
(
18
)    uk^s-1←umin,k^s←k^s-1 and update k^1 and k^2 by Eq. (15) and (16);
(
19
) end
(
20
)  end
(
21
)  whileQk^1,k^2,k^s<0do
(
22
)   k^2←k^2+1. Update uk^s such that stream m2 is cleared exactly in cycle k^2;
(
23
)  Update k^1 by Eq. (15);
(
24
)  ifQk^1,k^2,k^s>0then
(
25
)    k^2←k^2-1. Find the maximum k^1 such that Qk^1,k^2,k^s≥0;
(
26
)    Update uk^s such that stream m1 is cleared exactly in cycle k^1;
(
27
)  else ifQk^1,k^2+1,k^s>0 and uk^s≤umaxthen
(
28
)     break;
(
29
)  end
(
30
)  ifuk^s>umax  then
(31)uk^s←umax,k^s←k^s+1 and update k^1 and k^2 by Eq. (15)-(16);
(32)end
(33) end
(34)ifa1>a2 and umax>uHthen
(35)  Calculateq1k,q2k, by Eq. (2)-Eq. (3);
(36)  Setuk^2←uH-q2k^2/d2T;
(37)fork∈k^2,Ndo  uk=uH;
(38)endFor Case III and Case IV, however, the dispersed errors make it hard to adjust the solution in a few steps. However, for some carefully chosen cycle length, the accurate solution coincides with the discretized approximate solution.For example, in Case III, if the cycle length is chosen asT=q1,int/nd1umax-uL+d1-a1uL, where n is any positive integer, the accurate solution can be written as(14)uk=umax,k≤n,uL,k>n.It is easy to show that this accurate solution coincides with the corresponding discretized approximate solution.In the rest of this section, the discussion will focus on the adjustments for Case I, and the adjustments for Case II are similar.For presentation simplicity, define several denotations before starting the discussion. Definek^1 and k^2, respectively, as the clearance cycle indices in which streams m1 and m2 are cleared exactly:(15)k^1≔max⁡k:q1k>a1T1-uk,(16)k^2≔max⁡k:q2k>0.Apparently, in Case I(a), it holds thatk^1≤k^2. So, both streams enter steady state after cycle k^2. Note that there is also a switch in the discretized approximate solution. Define k^s as the switching cycle index where switch occurs; that is,(17)k^s:min⁡k:uk<umax.The adjustments contain two parts. Section4.1 deals with the adjustment in the steady state. Section 4.2 includes the adjustment around the switching cycle. Both parts are summarized as Algorithm 1. The optimality of Algorithm 1 will be proven in the Appendix. Finally, Counterexample 1 in Section 3 is revisited to better illustrate the adjustments.


### 4.1. The Steady-State Adjustment

The adjustment for the steady state is shown in lines (34)–(38) in Algorithm1. Since the steady-state solution is optimal for the discrete-time model after the two streams enter steady state, uk can be set as(18)uk=uss,k>k^2.However, in the clearance cyclek^2, the optimal green ratio is not uss due to discretization. So, uk^2 can be set as follows:(19)uk^2=uH-q2k^2d2T,a1>a2,umin,a1<a2.


### 4.2. The Adjustment around the Switch

The adjustment around the switching cycle is shown in lines (2)–(33) in Algorithm 1. There are two cases of adjustment: increasing the green ratios after the switch and decreasing the green ratios before the switch. For presentation simplicity, this subsection only handles the case of increasing the green ratios after the switch. The adjustment to the other case is similar except for some details; see Algorithm 1, lines (9)–(20).This adjustment can be viewed as a gradient descent approach to gradually reduce the total delay. It operates in three steps: (1) determine the direction of adjustment; (2) update the green ratio; (3) check feasibility of the new green ratio. It will be proven in the Appendix that such adjustment operations can be finished in a few steps.Due to constraint equations (3) and (4), the discrete-time model is a nonsmooth model. Thus, a subdifferential will be used instead of a gradient. Without loss of generality, assume that both streams are cleared after the switching cycle (i.e., k^1≥k^s). The case of k^1<k^s can be transformed easily to the case of k^1>k^s (Algorithm 1, lines (2)–(8)).In the first step, the direction of adjustment is determined by calculating the subdifferential. Denote the subdifferential of the total delayJD with respect to uk^s as ∂JD. Define the function Qk^1,k^2,k^s as(20)Qk^1,k^2,k^s=d2k^2-k^s-d1k^1-k^s+a1+a22T,a1<a2,d2k^2-k^s-d1k^1-k^s+a1T,a1>a2,so as to represent the subdifferential in a more convenient way.Clearly, the case of increasing the green ratios after the switch corresponds to the condition ofQk^1,k^2,k^s<0. There are three situations based on the queue evolution in clearance cycles k^1 and k^2.(1) Stream m1 is cleared exactly in cycle k^1; that is, qk^1+1=a1T1-uk^1=q1k^1-d1Tuk^1-uL. The subdifferential in this situation is calculated as(21)∂JD=Qk^1+1,k^2,k^s,Qk^1,k^2,k^s,where “a,b” means the closed interval between real numbers a and b.The physical meaning of the subdifferentialJD is shown as follows. The total delay changes if a slight disturbance is imposed on uk^s. Denote Δuk^s as the increment in uk^s and ΔJD as the corresponding change in total delay. If Δuk^s>0, then ΔJD can be calculated as(22)ΔJD=d2k^2-k^s-d1k^1-k^s+a1+a22TΔuk^s=Qk^1,k^2,k^sΔuk^s.Similarly, ifΔuk^s<0, the corresponding changes in total delay are written as ΔJD=Qk^1+1,k^2,k^sΔuk^s.Therefore, ifQk^1,k^2,k^s<0, the total delay can be reduced by increasing uk^s. If Qk^1,k^2,k^s≥0 and Qk^1+1,k^2,k^s<0, neither increasing nor decreasing uk^s will render a better total delay and thus the optimal uk^s is achieved.(2) Stream m2 is cleared exactly in cycle k^2; that is, q2k^2+1=0=q2k^2-d2TuH-uk^2. The subdifferential can be calculated similarly as ∂JD=Qk^1,k^2,k^s,Qk^1,k^2+1,k^s.Then, ifQk^1,k^2+1,k^s<0, the total delay can be reduced by increasing uk^s. If Qk^1,k^2+1,k^s≥0 and Qk^1,k^2,k^s<0, the optimal choice of uk^s is obtained.(3) Both streams are not cleared exactly in their clearance cycles. Then, the subdifferential is ∂JD=Qk^1,k^2,k^s. If Qk^1,k^2,k^s<0, the total delay can be reduced by increasing uk^s.In the second step, the green ratiouk^s is updated by reducing k^1 and increasing k^2. The green ratio uk^s is calculated such that either stream m1 or stream m2 is cleared exactly in its clearance cycle. The detailed calculation is shown in Algorithm 1 (lines (24)–(29)).The third step is the feasibility check of whether the new green ratiouk^s satisfies the constraint equation (4). In the case of increasing uk^s, the only possible violation is uk^s>umax. Therefore, if the feasibility check fails, uk^s is set as umax and a new bang-bang solution is obtained. Then, the algorithm goes back to the first step and determines the direction of adjustment.


### 4.3. The Numerical Examples

In this subsection, Counterexample1 in Section 3 is revisited to illustrate the steps of Algorithm 1. Recall that the parameters are d1 = 0.55, d2 = 0.3, a1 = 0.15, a2 = 0.10, umin = 0.4, umax = 0.8, q1,int = 60, q1,int = 20, T=160, and N=6. Algorithm 1 will be applied to adjust the discretized approximate solution. The detailed operation is shown in Table 2.Table 2
The operation of the algorithm.
Cyclek
0
1
2
3
4
5
Discretized solution
0.8000
0.8000
0.4000
0.4000
0.4000
0.4000
Step  1
0.8000
0.4000
0.4000
0.4000
0.4000
0.4000
Step  2
0.8000
0.3833 (0.400)
0.4000
0.4000
0.4000
0.4000
Step  3
0.7833
0.4000
0.4000
0.4000
0.4000
0.4000
Step  4
0.5167
0.4000
0.4000
0.4000
0.4000
0.4000
Step  5
0.6636
0.4000
0.4000
0.4000
0.4000
0.4000
Optimal solution
0.6636
0.4000
0.5197
0.6667
0.6667
0.6667The adjustment of the discretized approximate solution is also shown in Figure5.Figure 5
The adjustment of the discretized approximate solution.


## 4.1. The Steady-State Adjustment

The adjustment for the steady state is shown in lines (34)–(38) in Algorithm1. Since the steady-state solution is optimal for the discrete-time model after the two streams enter steady state, uk can be set as(18)uk=uss,k>k^2.However, in the clearance cyclek^2, the optimal green ratio is not uss due to discretization. So, uk^2 can be set as follows:(19)uk^2=uH-q2k^2d2T,a1>a2,umin,a1<a2.


## 4.2. The Adjustment around the Switch

The adjustment around the switching cycle is shown in lines (2)–(33) in Algorithm 1. There are two cases of adjustment: increasing the green ratios after the switch and decreasing the green ratios before the switch. For presentation simplicity, this subsection only handles the case of increasing the green ratios after the switch. The adjustment to the other case is similar except for some details; see Algorithm 1, lines (9)–(20).This adjustment can be viewed as a gradient descent approach to gradually reduce the total delay. It operates in three steps: (1) determine the direction of adjustment; (2) update the green ratio; (3) check feasibility of the new green ratio. It will be proven in the Appendix that such adjustment operations can be finished in a few steps.Due to constraint equations (3) and (4), the discrete-time model is a nonsmooth model. Thus, a subdifferential will be used instead of a gradient. Without loss of generality, assume that both streams are cleared after the switching cycle (i.e., k^1≥k^s). The case of k^1<k^s can be transformed easily to the case of k^1>k^s (Algorithm 1, lines (2)–(8)).In the first step, the direction of adjustment is determined by calculating the subdifferential. Denote the subdifferential of the total delayJD with respect to uk^s as ∂JD. Define the function Qk^1,k^2,k^s as(20)Qk^1,k^2,k^s=d2k^2-k^s-d1k^1-k^s+a1+a22T,a1<a2,d2k^2-k^s-d1k^1-k^s+a1T,a1>a2,so as to represent the subdifferential in a more convenient way.Clearly, the case of increasing the green ratios after the switch corresponds to the condition ofQk^1,k^2,k^s<0. There are three situations based on the queue evolution in clearance cycles k^1 and k^2.(1) Stream m1 is cleared exactly in cycle k^1; that is, qk^1+1=a1T1-uk^1=q1k^1-d1Tuk^1-uL. The subdifferential in this situation is calculated as(21)∂JD=Qk^1+1,k^2,k^s,Qk^1,k^2,k^s,where “a,b” means the closed interval between real numbers a and b.The physical meaning of the subdifferentialJD is shown as follows. The total delay changes if a slight disturbance is imposed on uk^s. Denote Δuk^s as the increment in uk^s and ΔJD as the corresponding change in total delay. If Δuk^s>0, then ΔJD can be calculated as(22)ΔJD=d2k^2-k^s-d1k^1-k^s+a1+a22TΔuk^s=Qk^1,k^2,k^sΔuk^s.Similarly, ifΔuk^s<0, the corresponding changes in total delay are written as ΔJD=Qk^1+1,k^2,k^sΔuk^s.Therefore, ifQk^1,k^2,k^s<0, the total delay can be reduced by increasing uk^s. If Qk^1,k^2,k^s≥0 and Qk^1+1,k^2,k^s<0, neither increasing nor decreasing uk^s will render a better total delay and thus the optimal uk^s is achieved.(2) Stream m2 is cleared exactly in cycle k^2; that is, q2k^2+1=0=q2k^2-d2TuH-uk^2. The subdifferential can be calculated similarly as ∂JD=Qk^1,k^2,k^s,Qk^1,k^2+1,k^s.Then, ifQk^1,k^2+1,k^s<0, the total delay can be reduced by increasing uk^s. If Qk^1,k^2+1,k^s≥0 and Qk^1,k^2,k^s<0, the optimal choice of uk^s is obtained.(3) Both streams are not cleared exactly in their clearance cycles. Then, the subdifferential is ∂JD=Qk^1,k^2,k^s. If Qk^1,k^2,k^s<0, the total delay can be reduced by increasing uk^s.In the second step, the green ratiouk^s is updated by reducing k^1 and increasing k^2. The green ratio uk^s is calculated such that either stream m1 or stream m2 is cleared exactly in its clearance cycle. The detailed calculation is shown in Algorithm 1 (lines (24)–(29)).The third step is the feasibility check of whether the new green ratiouk^s satisfies the constraint equation (4). In the case of increasing uk^s, the only possible violation is uk^s>umax. Therefore, if the feasibility check fails, uk^s is set as umax and a new bang-bang solution is obtained. Then, the algorithm goes back to the first step and determines the direction of adjustment.


## 4.3. The Numerical Examples

In this subsection, Counterexample1 in Section 3 is revisited to illustrate the steps of Algorithm 1. Recall that the parameters are d1 = 0.55, d2 = 0.3, a1 = 0.15, a2 = 0.10, umin = 0.4, umax = 0.8, q1,int = 60, q1,int = 20, T=160, and N=6. Algorithm 1 will be applied to adjust the discretized approximate solution. The detailed operation is shown in Table 2.Table 2
The operation of the algorithm.
Cyclek
0
1
2
3
4
5
Discretized solution
0.8000
0.8000
0.4000
0.4000
0.4000
0.4000
Step  1
0.8000
0.4000
0.4000
0.4000
0.4000
0.4000
Step  2
0.8000
0.3833 (0.400)
0.4000
0.4000
0.4000
0.4000
Step  3
0.7833
0.4000
0.4000
0.4000
0.4000
0.4000
Step  4
0.5167
0.4000
0.4000
0.4000
0.4000
0.4000
Step  5
0.6636
0.4000
0.4000
0.4000
0.4000
0.4000
Optimal solution
0.6636
0.4000
0.5197
0.6667
0.6667
0.6667The adjustment of the discretized approximate solution is also shown in Figure5.Figure 5
The adjustment of the discretized approximate solution.


## 5. Conclusion

This paper studies the continuous-time and discrete-time signal timing models for the classical isolated signalized intersection with only two one-way vehicle flows. Against intuitions, the nonequivalence between the solutions of the two models is first shown by two counterexamples. Then, the differences between the solutions of the two models are explained. Finally, an algorithm is proposed to transform the discretized continuous-time solution to the discrete-time solution for many cases. Via this gradient descent based algorithm, a more concrete link is set up between the continuous-time and discrete-time signal timing models.



---

*Source: 6290248-2017-09-07.xml*