# Solving Signal Control Problems with Second-Order Sensitivity Information of Equilibrium Network Flows

Authors: Hsun-Jung Cho; You-Heng Huang
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

The equilibrium network signal control problem is represented as a Stackelberg game. Due to the characteristics of a Stackelberg game, solving the upper-level problem and lower-level problem iteratively cannot be expected to converge to the solution. The reaction function of the lower-level problem is the key information to solve a Stackelberg game. Usually, the reaction function is approximated by the network sensitivity information. This paper firstly presents the general form of the second-order sensitivity formula for equilibrium network flows. The second-order sensitivity information can be applied to the second-order reaction function to solve the network signal control problem efficiently. Finally, this paper also demonstrates two numerical examples that show the computation of second-order sensitivity and the speed of convergence of the nonlinear approximation algorithm.


---

## Body

## 1. Introduction

The network signal control problem (NSCP) is to find the optimal signal setting which improves the performance of existing facilities in a transportation network. Conventional methods for optimizing signal settings can be divided into two types: stage-based and group-based approaches [1–6]. The stage-based approach divided the signal cycle into separate stages and solved the optimal signal settings for each group of compatible traffic movements in stages. This approach is regarded as superior in the concern for safety and loss of capacity with phase switching [6]. The group-based approach considered each group of traffic streams having right-of-way in the time domain directly. Compared with the stage-based approach, the group-based approach has a higher degree of flexibility in signal timing arrangement [3, 7]. However, the most optimization models proposed so far usually converged to a local optimal solution and without taking traffic rerouting effects into account when solving NSCP [5]. The equilibrium network signal control problem (ENSCP) is used to find an optimal network signal design when the network flow pattern is constrained to be equilibrium. Friesz [8] points out that this is a problem of interest because of Braess’ paradox [9]. This paradox shows that the congestion of the network may be severer when adding capacity to a congested network without taking the reaction of network users into consideration. Hence, in practice, the equilibrium network signal design problem must be solved by constraining the network flow pattern to meet user equilibrium. The user equilibrium network design with fixed transportation demand has been studied in both discrete [10] and continuous [11] versions. To help solve the signal control problem, Allsop [12] pointed out that the route choices of road users should be considered the impacts of signal settings changing. Gartner et al. [13] and Fisk [14] described the signal control problem as a Stackelberg or leader-follower game between road users and the administration. The Stackelberg game can be represented as a bilevel problem, where the upper-level problem aims to find the optimal signal setting or link capacity expansions which maximizes system performance, and the lower-level problem aims to solve the user equilibrium (UE) flows, respectively [15, 16].Marcotte [17], Sheffi and Powell [18], Heydecker and Khoo [19], Smith and van Vuren [20], Tan et al. [21], Cantarella et al. [22], Gartner et al. [13], Smith et al. [23], van Vuren and van Vliet [24], and others proposed algorithms to solve the network problem. However, when calculating optimal settings in general road networks, there were no efficient solution algorithms that are combined with anticipating the reactions of road users. Moreover, the iterative optimization assignment (IOA) procedure which solves signal settings and equilibrium flows cannot be expected to converge to the true solution and might lead to a decline in network performance [14, 25]. The sensitivity analysis-based algorithm evaluates the influence factors as the derivatives of the reaction functions with respect to the upper-level decision variables. The derivative information is obtained by implementing sensitivity analysis for a given solution of the user equilibrium problem [26–30]. For the singularity, algorithms can only solve a small network problem. Cho [31] proposed a generalized inverse method, Cho et al. [32] proposed a row reduction method, Patriksson [33], Josefsson, and Patriksson [34] proposed directional derivative method, and Yang and Bell [35] proposed a column reduction method to overcome the singularity problem. In the sensitivity analysis-based linear approximation algorithm, the sensitivity information is used to create a linear approximation of the reaction function and is then inserted into the upper-level problem, iterated until the solutions converge [34, 36, 37]. Recently, Chiou has conducted several studies related to optimal design of area traffic control with equilibrium network flows and proposed a number of computational algorithms to solve the problem, such as the projected Quasi-Newton method and the bundle subgradient projection method [38–41]. Moreover, the ENSCP, combined with an explicit traffic model, TRANSYT, was proposed to evaluate the performance index of the system more precisely [4, 38, 42–44].The remainder of this paper is organized as follows: Section2 introduces the equilibrium network flow models and the first-order sensitivity formula obtained by row reduction method. Section 3 introduces the matrix calculus theory and the second-order sensitivity formula. The network signal control model and solution algorithm are presented in Section 4. Finally, a numerical example and conclusion are presented in Sections 5 and 6, respectively.


## 2. Sensitivity Analysis of Equilibrium Network Flows

### 2.1. Equilibrium Network Flow Models

Consider a transportation network consisting of a finite set of nodesi
∈
N and a finite set of arcs a
∈
A together with a nonempty set of origin-destination (OD) pairs w
∈
W. For each w
∈
W, there is a nonempty finite set of paths, p
∈
P
w. Let real numbers, nonnegative reals, and positive reals be denoted by R, R
+, and R
+
+, respectively. The path flow vector, h, arc flow vector, f, and travel demand vector, T, are denoted in the following equations:
(1)
h
=
(
h
p
:
p
∈
P
,
P
=
⋃
w
∈
W
P
w
)
∈
R
+
|
P
|
,
f
=
(
f
a
:
a
∈
A
)
∈
R
+
|
A
|
,
T
=
(
T
w
:
w
∈
W
)
∈
R
+
+
|
W
|
,
where |
P
|, |
A
|, and |
W
| denote the cardinalities of P, A, and W, respectively. The relationship between arc flow, path flow, and travel demand is given by
(2)
Δ
h
=
f
,
Λ
h
=
T
,
where Δ is a |
A
|
×
|
P
| matrix, with Δ
a
p
=
1, if arc a belongs to path p and Δ
a
p
=
0 otherwise; Λ is a |
W
|
×
|
P
| matrix, with Λ
w
p
=
1, if OD pair w belongs to path p and Λ
w
p
=
0 otherwise. In general, Δ is called arc/path incidence matrix and Λ is called OD/path incidence matrix.In sensitivity analysis, a vector of perturbation parameters with dimensionρ, s
∈
R
ρ, is introduced. The arc cost function and travel demand function are supposed to be influenced by s. Let t
(
f
,
s
) be the arc cost function vector and let T
(
s
) be the travel demand function vector. The path cost function vector is given by c
(
h
,
s
)
=
Δ
T
t
(
f
,
s
). When the network equilibrium is reached, the following equations must be satisfied:
(3)
h
p
>
0
⟹
c
p
(
h
,
s
)
=
μ
w
,
p
∈
P
w
,
w
∈
W
,
h
p
=
0
⟹
c
p
(
h
,
s
)
≥
μ
w
,
p
∈
P
w
,
w
∈
W
,
where μ
w is the equilibrium path cost of OD pair w. Equations (3) are recognized as Wardrop equilibrium conditions; say, there is no traveler can change path unilaterally to improve his travel time [45]. Generally, the equilibrium network flow problem can be written in the form of variational inequality (VI) problem as follows [46]. Find f
∈
Ω
(
s
) such that
(4)
t
(
f
(
s
)
,
s
)
T
(
u
-
f
)
≥
0
,
∀
u
∈
Ω
(
s
)
,
Ω
(
s
)
=
{
f
∣
Δ
h
=
f
,
Λ
h
=
T
(
s
)
,
h
≥
0
}
,
where Ω is the feasible arc flow solution set of the network flow problems.An equivalent VI can be written with the cost function in terms of path flow variableh rather than arc flow variable f as follows. Find h
∈
Γ
(
s
) such that
(5)
c
(
h
,
s
)
T
(
u
-
h
)
≥
0
,
∀
u
∈
Γ
(
s
)
,
Γ
(
s
)
=
{
h
∣
Λ
h
=
T
(
s
)
,
h
≥
0
}
,
where Γ is the feasible path flow solution set of the network flow problems.


### 2.2. First-Order Sensitivity Formula for Equilibrium Network Flows

The classical first-order sensitivity analysis for equilibrium network flows was proposed by Tobin and Friesz [47]. However, Tobin and Friesz method had a strong requirement on the topology of network which may not hold in practical networks [48]. Cho et al. proposed the row reduction method to overcome this issue [32]. In this paper, we only summarize the key results of the row reduction method, and the readers are encouraged to refer to the original paper [32] for more details.In the row reduction method, a maximal set of rows fromΔ, say Δ
1, is selected for which the combined matrix [
Δ
1
,
Λ
]
T is of full row rank. Hence, Δ can be partitioned as [
Δ
1
;
Δ
2
]. Assume that the number of independent arcs is α
1and the number of dependent arcs is α
2, respectively. Therefore, |
A
|
=
α
=
α
1
+
α
2. For a differentiable function, f
:
S
→
R
m, let the partial derivative of f with respect to s (the Jacobian matrix of f) be denoted by D
s
f. Let the second-order partial derivative of f with respect to s be denoted by H
s
f. The first-order sensitivity formula can be expressed as
(6)
[
D
s
f
(
s
)
D
s
μ
(
s
)
]
=
[
D
f
t
(
f
,
s
)
-
M
T
M
0
]
-
1
[
-
D
s
t
(
f
,
s
)
Δ
2
N
2
D
s
T
(
s
)
]
,
where
(7)
M
=
[
Δ
2
N
1
-
I
]
,
N
1
=
Δ
1
T
M
11
+
Λ
T
M
21
,
N
2
=
Δ
1
T
M
12
+
Λ
T
M
22
,
(
[
Δ
1
Λ
]
[
Δ
1
Λ
]
T
)
-
1
=
[
M
11
M
12
M
21
M
22
]
.


## 2.1. Equilibrium Network Flow Models

Consider a transportation network consisting of a finite set of nodesi
∈
N and a finite set of arcs a
∈
A together with a nonempty set of origin-destination (OD) pairs w
∈
W. For each w
∈
W, there is a nonempty finite set of paths, p
∈
P
w. Let real numbers, nonnegative reals, and positive reals be denoted by R, R
+, and R
+
+, respectively. The path flow vector, h, arc flow vector, f, and travel demand vector, T, are denoted in the following equations:
(1)
h
=
(
h
p
:
p
∈
P
,
P
=
⋃
w
∈
W
P
w
)
∈
R
+
|
P
|
,
f
=
(
f
a
:
a
∈
A
)
∈
R
+
|
A
|
,
T
=
(
T
w
:
w
∈
W
)
∈
R
+
+
|
W
|
,
where |
P
|, |
A
|, and |
W
| denote the cardinalities of P, A, and W, respectively. The relationship between arc flow, path flow, and travel demand is given by
(2)
Δ
h
=
f
,
Λ
h
=
T
,
where Δ is a |
A
|
×
|
P
| matrix, with Δ
a
p
=
1, if arc a belongs to path p and Δ
a
p
=
0 otherwise; Λ is a |
W
|
×
|
P
| matrix, with Λ
w
p
=
1, if OD pair w belongs to path p and Λ
w
p
=
0 otherwise. In general, Δ is called arc/path incidence matrix and Λ is called OD/path incidence matrix.In sensitivity analysis, a vector of perturbation parameters with dimensionρ, s
∈
R
ρ, is introduced. The arc cost function and travel demand function are supposed to be influenced by s. Let t
(
f
,
s
) be the arc cost function vector and let T
(
s
) be the travel demand function vector. The path cost function vector is given by c
(
h
,
s
)
=
Δ
T
t
(
f
,
s
). When the network equilibrium is reached, the following equations must be satisfied:
(3)
h
p
>
0
⟹
c
p
(
h
,
s
)
=
μ
w
,
p
∈
P
w
,
w
∈
W
,
h
p
=
0
⟹
c
p
(
h
,
s
)
≥
μ
w
,
p
∈
P
w
,
w
∈
W
,
where μ
w is the equilibrium path cost of OD pair w. Equations (3) are recognized as Wardrop equilibrium conditions; say, there is no traveler can change path unilaterally to improve his travel time [45]. Generally, the equilibrium network flow problem can be written in the form of variational inequality (VI) problem as follows [46]. Find f
∈
Ω
(
s
) such that
(4)
t
(
f
(
s
)
,
s
)
T
(
u
-
f
)
≥
0
,
∀
u
∈
Ω
(
s
)
,
Ω
(
s
)
=
{
f
∣
Δ
h
=
f
,
Λ
h
=
T
(
s
)
,
h
≥
0
}
,
where Ω is the feasible arc flow solution set of the network flow problems.An equivalent VI can be written with the cost function in terms of path flow variableh rather than arc flow variable f as follows. Find h
∈
Γ
(
s
) such that
(5)
c
(
h
,
s
)
T
(
u
-
h
)
≥
0
,
∀
u
∈
Γ
(
s
)
,
Γ
(
s
)
=
{
h
∣
Λ
h
=
T
(
s
)
,
h
≥
0
}
,
where Γ is the feasible path flow solution set of the network flow problems.


## 2.2. First-Order Sensitivity Formula for Equilibrium Network Flows

The classical first-order sensitivity analysis for equilibrium network flows was proposed by Tobin and Friesz [47]. However, Tobin and Friesz method had a strong requirement on the topology of network which may not hold in practical networks [48]. Cho et al. proposed the row reduction method to overcome this issue [32]. In this paper, we only summarize the key results of the row reduction method, and the readers are encouraged to refer to the original paper [32] for more details.In the row reduction method, a maximal set of rows fromΔ, say Δ
1, is selected for which the combined matrix [
Δ
1
,
Λ
]
T is of full row rank. Hence, Δ can be partitioned as [
Δ
1
;
Δ
2
]. Assume that the number of independent arcs is α
1and the number of dependent arcs is α
2, respectively. Therefore, |
A
|
=
α
=
α
1
+
α
2. For a differentiable function, f
:
S
→
R
m, let the partial derivative of f with respect to s (the Jacobian matrix of f) be denoted by D
s
f. Let the second-order partial derivative of f with respect to s be denoted by H
s
f. The first-order sensitivity formula can be expressed as
(6)
[
D
s
f
(
s
)
D
s
μ
(
s
)
]
=
[
D
f
t
(
f
,
s
)
-
M
T
M
0
]
-
1
[
-
D
s
t
(
f
,
s
)
Δ
2
N
2
D
s
T
(
s
)
]
,
where
(7)
M
=
[
Δ
2
N
1
-
I
]
,
N
1
=
Δ
1
T
M
11
+
Λ
T
M
21
,
N
2
=
Δ
1
T
M
12
+
Λ
T
M
22
,
(
[
Δ
1
Λ
]
[
Δ
1
Λ
]
T
)
-
1
=
[
M
11
M
12
M
21
M
22
]
.


## 3. Second-Order Sensitivity Formula for Equilibrium Network Flows

The sensitivity analysis-based nonlinear approximation heuristic algorithm (NLAA) was firstly proposed by Cho and Lin [37]. With the first-order and the second-order sensitivity information, the reaction function of the lower-level problem can be approximated by a nonlinear function. However, Cho and Lin did not provide the general form of the second-order sensitivity information. In this section, we will introduce the preliminary of matrix calculus theory and derive the general form of the second-order sensitivity formula for equilibrium network flows.


### 3.1. Preliminary Definitions and Theorems

To derive the second-order sensitivity formula, we introduce some definitions and theorems of matrix calculus as follows [49, 50].Definition 1 (Kronecker product).
LetU be an m
×
n matrix and let V be a p
×
q matrix; then the Kronecker product of U and V, denoted by U
⊗
V, is an m
p
×
n
q matrix defined by
(8)
U
⊗
V
=
[
u
11
V
⋯
u
1
n
V
⋮
⋱
⋮
u
m
1
V
⋯
u
m
n
V
]
.Definition 2 (Vector operator).
LetU be an m
×
n matrix and U
j is the jth column of U; then vec
⁡
U is the m
n
×
1 vector:
(9)
vec
⁡
U
=
[
U
1
U
2
⋮
U
n
]
.Definition 3.
LetU be an m
×
n real matrix function of a p
×
q matrix of real variables s. The derivative of U with respect to s is the m
n
×
p
q matrix:
(10)
D
s
U
=
∂
vec
⁡
U
∂
(
vec
⁡
s
)
T
.Theorem 4 (chain rule for matrix functions, Magnus and Neudecker, 1985 [49]).
LetS be a subset of R
m
×
n and assume that U
:
S
→
R
p
×
q is differentiable at an interior point y of S. Let P be a subset of R
p
×
q such that U
(
x
)
∈
P for all x
∈
S and assume that V
:
P
→
R
r
×
s is differentiable at an interior point z
=
U
(
y
) of P. Then the composite function F
:
S
→
R
r
×
s defined by F
(
x
)
=
V
(
U
(
x
)
) is differentiable at y and
(11)
D
y
F
=
(
D
z
V
)
(
D
y
U
)
.Theorem 5 (Magnus and Neudecker, 1985 [49]).
LetU
:
S
→
R
m
×
r and V
:
S
→
R
r
×
n be two matrix functions defined and differentiable on an open set S in R
p
×
q. Then the simple product U
V is differentiable on S and the Jacobian matrix is the m
n
×
p
q matrix:
(12)
D
s
(
U
V
)
=
∂
vec
⁡
U
V
∂
(
vec
⁡
s
)
T
=
(
V
T
⊗
I
m
)
D
s
U
+
(
I
n
⊗
U
)
D
s
V
,
where I
m and I
n are the identity matrices of size m and n, respectively.Theorem 6 (Magnus and Neudecker, 1999 [50]).
Letf
:
S
→
R
m be a function defined on a set S in R
n. Let r be an interior point of S and let B
(
s
0
;
r
) be an n-ball lying in S. Let s be a point in R
n with ∥
s
∥
<
r, so that s
0
+
s
∈
B
(
s
0
;
r
). If f is twice differentiable at s
0, then the second-order Taylor expansion of function f at s
0
+
s is
(13)
f
(
s
0
+
s
)
=
f
(
s
0
)
+
d
f
(
s
0
;
s
)
+
1
2
d
2
f
(
s
0
;
s
)
,
where d
f
(
s
0
;
s
) and d
2
f
(
s
0
;
s
) are the first differential and the second differential of f at s
0, respectively, and
(14)
d
f
(
s
0
;
s
)
=
D
s
f
(
s
0
)
·
(
s
-
s
0
)
,
d
2
f
(
s
0
;
s
)
=
(
(
s
-
s
0
)
T
⊗
I
m
)
·
H
s
f
(
s
0
)
·
(
s
-
s
0
)
.


### 3.2. Second-Order Sensitivity Formula for Equilibrium Network Flows

To derive the second-order sensitivity formula for equilibrium network flows, it is intuitive to take derivative of (6) with respect to s. For convenience, let
(15)
[
D
f
t
(
f
(
s
)
,
s
)
-
M
T
M
0
]
-
1
=
U
(
f
(
s
)
,
s
)
,
[
-
D
s
t
(
f
(
s
)
,
s
)
Δ
2
N
2
D
s
T
(
s
)
]
=
V
(
f
(
s
)
,
s
)
,
where U is an (
α
+
α
2
)
×
(
α
+
α
2
) matrix and V is an (
α
+
α
2
)
×
ρ matrix, respectively.Lemma 7.
The second-order sensitivity for equilibrium network flows is(16)
[
H
s
f
H
s
μ
]
=
(
V
T
⊗
I
(
α
+
α
2
)
)
D
s
U
+
(
I
k
⊗
U
)
D
s
V
,
where
(17)
U
(
f
(
s
)
,
s
)
=
[
D
f
t
(
f
(
s
)
,
s
)
-
M
T
M
0
]
-
1
,
V
(
f
(
s
)
,
s
)
=
[
-
D
s
t
(
f
(
s
)
,
s
)
Δ
2
N
2
D
s
T
(
s
)
]
.Proof.
Since the first-order sensitivity is the product of (17), the second-order sensitivity can be obtained by taking derivative of the product with respect to s directly. According to Theorem 5, the formula of the second-order sensitivity is expressed as (16) and the proof is complete.


## 3.1. Preliminary Definitions and Theorems

To derive the second-order sensitivity formula, we introduce some definitions and theorems of matrix calculus as follows [49, 50].Definition 1 (Kronecker product).
LetU be an m
×
n matrix and let V be a p
×
q matrix; then the Kronecker product of U and V, denoted by U
⊗
V, is an m
p
×
n
q matrix defined by
(8)
U
⊗
V
=
[
u
11
V
⋯
u
1
n
V
⋮
⋱
⋮
u
m
1
V
⋯
u
m
n
V
]
.Definition 2 (Vector operator).
LetU be an m
×
n matrix and U
j is the jth column of U; then vec
⁡
U is the m
n
×
1 vector:
(9)
vec
⁡
U
=
[
U
1
U
2
⋮
U
n
]
.Definition 3.
LetU be an m
×
n real matrix function of a p
×
q matrix of real variables s. The derivative of U with respect to s is the m
n
×
p
q matrix:
(10)
D
s
U
=
∂
vec
⁡
U
∂
(
vec
⁡
s
)
T
.Theorem 4 (chain rule for matrix functions, Magnus and Neudecker, 1985 [49]).
LetS be a subset of R
m
×
n and assume that U
:
S
→
R
p
×
q is differentiable at an interior point y of S. Let P be a subset of R
p
×
q such that U
(
x
)
∈
P for all x
∈
S and assume that V
:
P
→
R
r
×
s is differentiable at an interior point z
=
U
(
y
) of P. Then the composite function F
:
S
→
R
r
×
s defined by F
(
x
)
=
V
(
U
(
x
)
) is differentiable at y and
(11)
D
y
F
=
(
D
z
V
)
(
D
y
U
)
.Theorem 5 (Magnus and Neudecker, 1985 [49]).
LetU
:
S
→
R
m
×
r and V
:
S
→
R
r
×
n be two matrix functions defined and differentiable on an open set S in R
p
×
q. Then the simple product U
V is differentiable on S and the Jacobian matrix is the m
n
×
p
q matrix:
(12)
D
s
(
U
V
)
=
∂
vec
⁡
U
V
∂
(
vec
⁡
s
)
T
=
(
V
T
⊗
I
m
)
D
s
U
+
(
I
n
⊗
U
)
D
s
V
,
where I
m and I
n are the identity matrices of size m and n, respectively.Theorem 6 (Magnus and Neudecker, 1999 [50]).
Letf
:
S
→
R
m be a function defined on a set S in R
n. Let r be an interior point of S and let B
(
s
0
;
r
) be an n-ball lying in S. Let s be a point in R
n with ∥
s
∥
<
r, so that s
0
+
s
∈
B
(
s
0
;
r
). If f is twice differentiable at s
0, then the second-order Taylor expansion of function f at s
0
+
s is
(13)
f
(
s
0
+
s
)
=
f
(
s
0
)
+
d
f
(
s
0
;
s
)
+
1
2
d
2
f
(
s
0
;
s
)
,
where d
f
(
s
0
;
s
) and d
2
f
(
s
0
;
s
) are the first differential and the second differential of f at s
0, respectively, and
(14)
d
f
(
s
0
;
s
)
=
D
s
f
(
s
0
)
·
(
s
-
s
0
)
,
d
2
f
(
s
0
;
s
)
=
(
(
s
-
s
0
)
T
⊗
I
m
)
·
H
s
f
(
s
0
)
·
(
s
-
s
0
)
.


## 3.2. Second-Order Sensitivity Formula for Equilibrium Network Flows

To derive the second-order sensitivity formula for equilibrium network flows, it is intuitive to take derivative of (6) with respect to s. For convenience, let
(15)
[
D
f
t
(
f
(
s
)
,
s
)
-
M
T
M
0
]
-
1
=
U
(
f
(
s
)
,
s
)
,
[
-
D
s
t
(
f
(
s
)
,
s
)
Δ
2
N
2
D
s
T
(
s
)
]
=
V
(
f
(
s
)
,
s
)
,
where U is an (
α
+
α
2
)
×
(
α
+
α
2
) matrix and V is an (
α
+
α
2
)
×
ρ matrix, respectively.Lemma 7.
The second-order sensitivity for equilibrium network flows is(16)
[
H
s
f
H
s
μ
]
=
(
V
T
⊗
I
(
α
+
α
2
)
)
D
s
U
+
(
I
k
⊗
U
)
D
s
V
,
where
(17)
U
(
f
(
s
)
,
s
)
=
[
D
f
t
(
f
(
s
)
,
s
)
-
M
T
M
0
]
-
1
,
V
(
f
(
s
)
,
s
)
=
[
-
D
s
t
(
f
(
s
)
,
s
)
Δ
2
N
2
D
s
T
(
s
)
]
.Proof.
Since the first-order sensitivity is the product of (17), the second-order sensitivity can be obtained by taking derivative of the product with respect to s directly. According to Theorem 5, the formula of the second-order sensitivity is expressed as (16) and the proof is complete.


## 4. Network Signal Control Model and Solution Algorithm

### 4.1. Network Signal Control Model

Consider the signal optimization problem, where the aim of the regulating agency is to minimize a network performance functionZ
(
s
) such as total travel time or gas consumption, with fixed OD travel demand, where travelers select routes on the network in an optimal user fashion. Notably, S denotes the set of feasible signal control variables. For any given s
∈
S, a user optimal arc flow solution f
(
s
)
∈
Ω exists and the problem of the regulator is to solve
(18)
P
1
:
min
⁡
s
∈
X
1
Z
(
s
)
=
P
(
f
(
s
)
,
s
)
s
.
t
.
user
equilibrium
.In the general problem, the signal variable that can be set by the controlling agent is green time. By specifying the cost functionst
a for each network arc a in terms of these variables and assuming that the behavioral hypothesis for route choice follows the first principle of Wardrop [45], problem P
1 can be presented as
(19)
P
2
:
min
⁡
s
∈
X
1
Z
(
s
)
=
∑
a
∈
A
t
a
(
f
(
s
)
,
s
)
f
a
(
s
)
(20)
s
.
t
.
t
(
f
(
s
)
,
s
)
·
(
u
-
f
)
≥
0
,
∀
u
∈
Ω
.Ift
(
s
,
f
) is strictly monotone, then, for each s
≥
0, (20) has a unique solution and function f
(
s
) is (continuously) differentiable at every point s
≥
0. Thus, P
2 can be rewritten as P
3:
(21)
P
3
:
min
⁡
s
∈
X
1
Z
(
s
)
=
∑
a
t
a
(
f
(
s
)
,
s
)
f
a
(
s
)
s
.
t
.
s
≥
0
.
Also, given R
(
s
,
f
(
s
)
)
=
min
⁡
t
(
f
(
s
)
,
s
)
·
(
u
-
f
), then P
2 is equivalent to P
4:
(22)
P
4


:
min
⁡
s
∈
X
1
Z
(
s
)
=
∑
a
t
a
(
f
(
s
)
,
s
)
f
a
(
s
)
s
.
t
.
R
(
f
(
s
)
,
s
)
=
0
.


### 4.2. Solution Algorithms

The iterative optimization assignment (IOA) method described by Tan et al. [21] is proceeded as follows. First, fix s and solve (20) for f; then fix f and solve (19) for s, continuing this process until s
k
+
1
-
s
k
→
0 or f
k
+
1
-
f
k
→
0. The final solution (
f
N
,
s
N
) is termed the Nash solution. Notably, that the solution obtained using the IOA algorithm is not necessarily an optimal solution of the equilibrium network control problem [14]. The sensitivity analysis of equilibrium network flows [32, 47] was used to solve the equilibrium network signal design problem [26, 36, 51].


#### 4.2.1. A Sensitivity Analysis-Based Linear Approximation Heuristic Algorithm

The challenge in solving problemP
2 is that, since the lower level of the problem cannot be represented in closed form, it is impossible to obtain an explicit reaction function that can be plugged into the upper level. In the sensitivity analysis-based linear approximation heuristic algorithm, the sensitivity information is used to create a linear approximation of the reaction function and is then inserted into the upper-level problem, iterated until the solutions converge (abbreviated as LAA) [36].The heuristic is detailed as follows.Algorithm A1.Step 0.
Determine a fixed small valueδ
>
0 and an initial value s
0. Set k
=
0.Step 1.
Solve (18) given s
k and yielding f
k.Step 2.
Calculate the sensitivity informationD
s
f by (6).Step 3.
UsingD
s
f, Taylor expansion and Theorem 6 form the linear approximation f
k
+
1
,
f
k
+
1
=
f
k
+
D
s
f
·
(
s
k
+
1
-
s
k
). Since f
k, s
k, and D
s
f are known, f
k
+
1 can be replaced by a function of s
k
+
1. Thus, f
k
+
1
=
A
+
B
s
k
+
1.Step 4.
Reformulate (21) as
(23)
min
⁡
s
∑
a
t
a
(
A
+
B
s
k
+
1
,
s
)
·
(
A
+
B
s
k
+
1
)
s
.
t
.
s
≥
0
.Step 5.
Solve the problem in Step4 using any software package which can solve the optimal solution for s
k
+
1. If |
s
k
+
1
-
s
k
|
≤
δ, then stop; otherwise set k
=
k
+
1 and go to Step 1.


#### 4.2.2. A Sensitivity Analysis-Based Nonlinear Approximation Heuristic Algorithm

In the sensitivity analysis-based linear approximation heuristic algorithm, the reaction function of the lower level is based on approximation by a linear function. In this section, the reaction function of the lower-level problem is based on approximation by a nonlinear function and is plugged into the upper-level problem and is iterated until the solutions converge (abbreviated as NLAA) [37].Algorithm A2.Step 0.
Determine a fixed small valueδ
>
0 and an initial value s
0. Set k
=
0.Step 1.
Solve (20) given s
k and yielding f
k.Step 2.
Calculate the sensitivity informationD
s
f and H
s
f by (6) and (16).Step 3.
UsingD
s
f and H
s
f, Taylor expansion and Theorem 6 form the nonlinear approximation f
k
+
1:
(24)
f
k
+
1
=
f
k
+
D
s
f
·
(
s
k
+
1
-
s
k
)
+
1
2
·
(
(
s
k
+
1
-
s
k
)
T
⊗
I
m
)
·
H
s
f
·
(
s
k
+
1
-
s
k
)
.
Since f
k, s
k, D
s
f, and H
s
f are known, f
k
+
1 can be replaced by a function of s
k
+
1. Thus, f
k
+
1
=
A
+
B
s
k
+
1
+
C
(
s
k
+
1
)
2.Step 4.
Reformulate (21) as
(25)
min
⁡
s
∑
a
t
a
(
A
+
B
s
k
+
1
+
C
(
s
k
+
1
)
2
,
s
)
·
(
A
+
B
s
k
+
1
+
C
(
s
k
+
1
)
2
)
s
.
t
.
s
≥
0
.Step 5.
Solve the problem in Step4 using any software package which can solve the optimal solution for s
k
+
1. If |
s
k
+
1
-
s
k
|
≤
δ; then stop; otherwise set k
=
k
+
1 and go to Step 1.In addition to describing the algorithm in more detail, we will provide a proof that if this algorithm converges, it converges to an optimal solution of problemP
2.Lemma 8.
If algorithm A2 converges, it converges to a critical point ofP
2.Proof.
If the sequences
k converges to s
*, s
k
→
s
*, then we know that(1)
if we sets
0
=
s
*, f
0
=
f
*, then s
1
=
s
*, f
1
=
f
*; and
(2)
let(26)
Z
^
(
s
)
=
∑
a
∈
A
t
a
(
A
+
B
s
+
C
s
2
,
s
)
f
a
(
s
)
.Then, by the Karush-Kuhn-Tucker necessary conditions for optimality of vectors s
*
≥
0, we know that the following must be true:(i)
(27)
∂
Z
^
(
s
*
)
∂
s
i
=
0
if
s
*
i
>
0
,
i
=
1
,
…
,
n
,
(ii)
(28)
∂
Z
^
(
s
*
)
∂
s
i
≥
0
if
s
*
i
=
0
,
i
=
1
,
…
,
n
.So, taking the derivative with respect to s, we get
(29)
∂
∂
s
i
[
∑
a
t
a
(
A
+
B
s
+
C
s
2
,
s
)
(
A
+
B
s
+
C
s
2
)
]
|
s
=
s
*
=
∑
a
t
a
(
A
+
B
s
+
C
s
2
,
s
)
·
(
B
+
2
C
s
)
|
s
=
s
*
+
∑
a
[
∂
t
a
(
A
+
B
s
+
C
s
2
,
s
)
∂
(
A
+
B
s
+
C
s
2
)
·
(
B
+
2
C
s
)
+
∂
t
a
(
A
+
B
s
+
C
s
2
,
s
)
∂
s
]
·
(
A
+
B
s
+
C
s
2
)
|
s
=
s
*
.
Further, we know
(30)
B
=
D
s
f
|
s
=
s
*
,
C
=
1
2
·
H
s
f
|
s
=
s
*
,
f
(
s
)
=
A
+
B
s
+
C
s
2
.
So, substituting (29), we know
(31)
∂
∂
s
i
[
∑
a
t
a
(
A
+
B
s
+
C
s
2
,
s
)
(
A
+
B
s
+
C
s
2
)
]
|
s
=
s
*
=
∑
a
t
a
(
f
(
s
)
,
s
)
·
(
D
s
f
+
H
s
f
·
s
)
|
s
=
s
*
+
∑
a
[
∂
t
a
(
f
(
s
)
,
s
)
∂
f
·
(
D
s
f
+
H
s
f
·
s
)
+
∂
t
a
(
f
(
s
)
,
s
)
∂
s
]
·
f
a
|
s
=
s
*
,
f
=
f
*
=
∑
a
t
a
(
f
(
s
)
,
s
)
·
D
s
f
(
s
)
|
s
=
s
*
+
∑
a
[
∂
t
a
(
f
(
s
)
,
s
)
∂
f
·
D
s
f
(
s
)
+
∂
t
a
(
f
(
s
)
,
s
)
∂
s
]
·
f
a
|
s
=
s
*
,
f
=
f
*
=
∂
∂
s
[
∑
a
t
a
(
f
(
s
)
,
s
)
·
f
a
(
s
)
]
|
s
=
s
*
,
f
=
f
*
.
So, we know if conditions (i) and (ii) are satisfied, then the following should also be satisfied:(iii)
(32)
∂
Z
(
s
*
)
∂
s
i
=
0
if
s
*
i
>
0
,
i
=
1
,
…
,
n
,
(iv)
(33)
∂
Z
(
s
*
)
∂
s
i
≥
0
if
s
*
i
=
0
,
i
=
1
,
…
,
n
.


## 4.1. Network Signal Control Model

Consider the signal optimization problem, where the aim of the regulating agency is to minimize a network performance functionZ
(
s
) such as total travel time or gas consumption, with fixed OD travel demand, where travelers select routes on the network in an optimal user fashion. Notably, S denotes the set of feasible signal control variables. For any given s
∈
S, a user optimal arc flow solution f
(
s
)
∈
Ω exists and the problem of the regulator is to solve
(18)
P
1
:
min
⁡
s
∈
X
1
Z
(
s
)
=
P
(
f
(
s
)
,
s
)
s
.
t
.
user
equilibrium
.In the general problem, the signal variable that can be set by the controlling agent is green time. By specifying the cost functionst
a for each network arc a in terms of these variables and assuming that the behavioral hypothesis for route choice follows the first principle of Wardrop [45], problem P
1 can be presented as
(19)
P
2
:
min
⁡
s
∈
X
1
Z
(
s
)
=
∑
a
∈
A
t
a
(
f
(
s
)
,
s
)
f
a
(
s
)
(20)
s
.
t
.
t
(
f
(
s
)
,
s
)
·
(
u
-
f
)
≥
0
,
∀
u
∈
Ω
.Ift
(
s
,
f
) is strictly monotone, then, for each s
≥
0, (20) has a unique solution and function f
(
s
) is (continuously) differentiable at every point s
≥
0. Thus, P
2 can be rewritten as P
3:
(21)
P
3
:
min
⁡
s
∈
X
1
Z
(
s
)
=
∑
a
t
a
(
f
(
s
)
,
s
)
f
a
(
s
)
s
.
t
.
s
≥
0
.
Also, given R
(
s
,
f
(
s
)
)
=
min
⁡
t
(
f
(
s
)
,
s
)
·
(
u
-
f
), then P
2 is equivalent to P
4:
(22)
P
4


:
min
⁡
s
∈
X
1
Z
(
s
)
=
∑
a
t
a
(
f
(
s
)
,
s
)
f
a
(
s
)
s
.
t
.
R
(
f
(
s
)
,
s
)
=
0
.


## 4.2. Solution Algorithms

The iterative optimization assignment (IOA) method described by Tan et al. [21] is proceeded as follows. First, fix s and solve (20) for f; then fix f and solve (19) for s, continuing this process until s
k
+
1
-
s
k
→
0 or f
k
+
1
-
f
k
→
0. The final solution (
f
N
,
s
N
) is termed the Nash solution. Notably, that the solution obtained using the IOA algorithm is not necessarily an optimal solution of the equilibrium network control problem [14]. The sensitivity analysis of equilibrium network flows [32, 47] was used to solve the equilibrium network signal design problem [26, 36, 51].


### 4.2.1. A Sensitivity Analysis-Based Linear Approximation Heuristic Algorithm

The challenge in solving problemP
2 is that, since the lower level of the problem cannot be represented in closed form, it is impossible to obtain an explicit reaction function that can be plugged into the upper level. In the sensitivity analysis-based linear approximation heuristic algorithm, the sensitivity information is used to create a linear approximation of the reaction function and is then inserted into the upper-level problem, iterated until the solutions converge (abbreviated as LAA) [36].The heuristic is detailed as follows.Algorithm A1.Step 0.
Determine a fixed small valueδ
>
0 and an initial value s
0. Set k
=
0.Step 1.
Solve (18) given s
k and yielding f
k.Step 2.
Calculate the sensitivity informationD
s
f by (6).Step 3.
UsingD
s
f, Taylor expansion and Theorem 6 form the linear approximation f
k
+
1
,
f
k
+
1
=
f
k
+
D
s
f
·
(
s
k
+
1
-
s
k
). Since f
k, s
k, and D
s
f are known, f
k
+
1 can be replaced by a function of s
k
+
1. Thus, f
k
+
1
=
A
+
B
s
k
+
1.Step 4.
Reformulate (21) as
(23)
min
⁡
s
∑
a
t
a
(
A
+
B
s
k
+
1
,
s
)
·
(
A
+
B
s
k
+
1
)
s
.
t
.
s
≥
0
.Step 5.
Solve the problem in Step4 using any software package which can solve the optimal solution for s
k
+
1. If |
s
k
+
1
-
s
k
|
≤
δ, then stop; otherwise set k
=
k
+
1 and go to Step 1.


### 4.2.2. A Sensitivity Analysis-Based Nonlinear Approximation Heuristic Algorithm

In the sensitivity analysis-based linear approximation heuristic algorithm, the reaction function of the lower level is based on approximation by a linear function. In this section, the reaction function of the lower-level problem is based on approximation by a nonlinear function and is plugged into the upper-level problem and is iterated until the solutions converge (abbreviated as NLAA) [37].Algorithm A2.Step 0.
Determine a fixed small valueδ
>
0 and an initial value s
0. Set k
=
0.Step 1.
Solve (20) given s
k and yielding f
k.Step 2.
Calculate the sensitivity informationD
s
f and H
s
f by (6) and (16).Step 3.
UsingD
s
f and H
s
f, Taylor expansion and Theorem 6 form the nonlinear approximation f
k
+
1:
(24)
f
k
+
1
=
f
k
+
D
s
f
·
(
s
k
+
1
-
s
k
)
+
1
2
·
(
(
s
k
+
1
-
s
k
)
T
⊗
I
m
)
·
H
s
f
·
(
s
k
+
1
-
s
k
)
.
Since f
k, s
k, D
s
f, and H
s
f are known, f
k
+
1 can be replaced by a function of s
k
+
1. Thus, f
k
+
1
=
A
+
B
s
k
+
1
+
C
(
s
k
+
1
)
2.Step 4.
Reformulate (21) as
(25)
min
⁡
s
∑
a
t
a
(
A
+
B
s
k
+
1
+
C
(
s
k
+
1
)
2
,
s
)
·
(
A
+
B
s
k
+
1
+
C
(
s
k
+
1
)
2
)
s
.
t
.
s
≥
0
.Step 5.
Solve the problem in Step4 using any software package which can solve the optimal solution for s
k
+
1. If |
s
k
+
1
-
s
k
|
≤
δ; then stop; otherwise set k
=
k
+
1 and go to Step 1.In addition to describing the algorithm in more detail, we will provide a proof that if this algorithm converges, it converges to an optimal solution of problemP
2.Lemma 8.
If algorithm A2 converges, it converges to a critical point ofP
2.Proof.
If the sequences
k converges to s
*, s
k
→
s
*, then we know that(1)
if we sets
0
=
s
*, f
0
=
f
*, then s
1
=
s
*, f
1
=
f
*; and
(2)
let(26)
Z
^
(
s
)
=
∑
a
∈
A
t
a
(
A
+
B
s
+
C
s
2
,
s
)
f
a
(
s
)
.Then, by the Karush-Kuhn-Tucker necessary conditions for optimality of vectors s
*
≥
0, we know that the following must be true:(i)
(27)
∂
Z
^
(
s
*
)
∂
s
i
=
0
if
s
*
i
>
0
,
i
=
1
,
…
,
n
,
(ii)
(28)
∂
Z
^
(
s
*
)
∂
s
i
≥
0
if
s
*
i
=
0
,
i
=
1
,
…
,
n
.So, taking the derivative with respect to s, we get
(29)
∂
∂
s
i
[
∑
a
t
a
(
A
+
B
s
+
C
s
2
,
s
)
(
A
+
B
s
+
C
s
2
)
]
|
s
=
s
*
=
∑
a
t
a
(
A
+
B
s
+
C
s
2
,
s
)
·
(
B
+
2
C
s
)
|
s
=
s
*
+
∑
a
[
∂
t
a
(
A
+
B
s
+
C
s
2
,
s
)
∂
(
A
+
B
s
+
C
s
2
)
·
(
B
+
2
C
s
)
+
∂
t
a
(
A
+
B
s
+
C
s
2
,
s
)
∂
s
]
·
(
A
+
B
s
+
C
s
2
)
|
s
=
s
*
.
Further, we know
(30)
B
=
D
s
f
|
s
=
s
*
,
C
=
1
2
·
H
s
f
|
s
=
s
*
,
f
(
s
)
=
A
+
B
s
+
C
s
2
.
So, substituting (29), we know
(31)
∂
∂
s
i
[
∑
a
t
a
(
A
+
B
s
+
C
s
2
,
s
)
(
A
+
B
s
+
C
s
2
)
]
|
s
=
s
*
=
∑
a
t
a
(
f
(
s
)
,
s
)
·
(
D
s
f
+
H
s
f
·
s
)
|
s
=
s
*
+
∑
a
[
∂
t
a
(
f
(
s
)
,
s
)
∂
f
·
(
D
s
f
+
H
s
f
·
s
)
+
∂
t
a
(
f
(
s
)
,
s
)
∂
s
]
·
f
a
|
s
=
s
*
,
f
=
f
*
=
∑
a
t
a
(
f
(
s
)
,
s
)
·
D
s
f
(
s
)
|
s
=
s
*
+
∑
a
[
∂
t
a
(
f
(
s
)
,
s
)
∂
f
·
D
s
f
(
s
)
+
∂
t
a
(
f
(
s
)
,
s
)
∂
s
]
·
f
a
|
s
=
s
*
,
f
=
f
*
=
∂
∂
s
[
∑
a
t
a
(
f
(
s
)
,
s
)
·
f
a
(
s
)
]
|
s
=
s
*
,
f
=
f
*
.
So, we know if conditions (i) and (ii) are satisfied, then the following should also be satisfied:(iii)
(32)
∂
Z
(
s
*
)
∂
s
i
=
0
if
s
*
i
>
0
,
i
=
1
,
…
,
n
,
(iv)
(33)
∂
Z
(
s
*
)
∂
s
i
≥
0
if
s
*
i
=
0
,
i
=
1
,
…
,
n
.


## 4.2.1. A Sensitivity Analysis-Based Linear Approximation Heuristic Algorithm

The challenge in solving problemP
2 is that, since the lower level of the problem cannot be represented in closed form, it is impossible to obtain an explicit reaction function that can be plugged into the upper level. In the sensitivity analysis-based linear approximation heuristic algorithm, the sensitivity information is used to create a linear approximation of the reaction function and is then inserted into the upper-level problem, iterated until the solutions converge (abbreviated as LAA) [36].The heuristic is detailed as follows.Algorithm A1.Step 0.
Determine a fixed small valueδ
>
0 and an initial value s
0. Set k
=
0.Step 1.
Solve (18) given s
k and yielding f
k.Step 2.
Calculate the sensitivity informationD
s
f by (6).Step 3.
UsingD
s
f, Taylor expansion and Theorem 6 form the linear approximation f
k
+
1
,
f
k
+
1
=
f
k
+
D
s
f
·
(
s
k
+
1
-
s
k
). Since f
k, s
k, and D
s
f are known, f
k
+
1 can be replaced by a function of s
k
+
1. Thus, f
k
+
1
=
A
+
B
s
k
+
1.Step 4.
Reformulate (21) as
(23)
min
⁡
s
∑
a
t
a
(
A
+
B
s
k
+
1
,
s
)
·
(
A
+
B
s
k
+
1
)
s
.
t
.
s
≥
0
.Step 5.
Solve the problem in Step4 using any software package which can solve the optimal solution for s
k
+
1. If |
s
k
+
1
-
s
k
|
≤
δ, then stop; otherwise set k
=
k
+
1 and go to Step 1.


## 4.2.2. A Sensitivity Analysis-Based Nonlinear Approximation Heuristic Algorithm

In the sensitivity analysis-based linear approximation heuristic algorithm, the reaction function of the lower level is based on approximation by a linear function. In this section, the reaction function of the lower-level problem is based on approximation by a nonlinear function and is plugged into the upper-level problem and is iterated until the solutions converge (abbreviated as NLAA) [37].Algorithm A2.Step 0.
Determine a fixed small valueδ
>
0 and an initial value s
0. Set k
=
0.Step 1.
Solve (20) given s
k and yielding f
k.Step 2.
Calculate the sensitivity informationD
s
f and H
s
f by (6) and (16).Step 3.
UsingD
s
f and H
s
f, Taylor expansion and Theorem 6 form the nonlinear approximation f
k
+
1:
(24)
f
k
+
1
=
f
k
+
D
s
f
·
(
s
k
+
1
-
s
k
)
+
1
2
·
(
(
s
k
+
1
-
s
k
)
T
⊗
I
m
)
·
H
s
f
·
(
s
k
+
1
-
s
k
)
.
Since f
k, s
k, D
s
f, and H
s
f are known, f
k
+
1 can be replaced by a function of s
k
+
1. Thus, f
k
+
1
=
A
+
B
s
k
+
1
+
C
(
s
k
+
1
)
2.Step 4.
Reformulate (21) as
(25)
min
⁡
s
∑
a
t
a
(
A
+
B
s
k
+
1
+
C
(
s
k
+
1
)
2
,
s
)
·
(
A
+
B
s
k
+
1
+
C
(
s
k
+
1
)
2
)
s
.
t
.
s
≥
0
.Step 5.
Solve the problem in Step4 using any software package which can solve the optimal solution for s
k
+
1. If |
s
k
+
1
-
s
k
|
≤
δ; then stop; otherwise set k
=
k
+
1 and go to Step 1.In addition to describing the algorithm in more detail, we will provide a proof that if this algorithm converges, it converges to an optimal solution of problemP
2.Lemma 8.
If algorithm A2 converges, it converges to a critical point ofP
2.Proof.
If the sequences
k converges to s
*, s
k
→
s
*, then we know that(1)
if we sets
0
=
s
*, f
0
=
f
*, then s
1
=
s
*, f
1
=
f
*; and
(2)
let(26)
Z
^
(
s
)
=
∑
a
∈
A
t
a
(
A
+
B
s
+
C
s
2
,
s
)
f
a
(
s
)
.Then, by the Karush-Kuhn-Tucker necessary conditions for optimality of vectors s
*
≥
0, we know that the following must be true:(i)
(27)
∂
Z
^
(
s
*
)
∂
s
i
=
0
if
s
*
i
>
0
,
i
=
1
,
…
,
n
,
(ii)
(28)
∂
Z
^
(
s
*
)
∂
s
i
≥
0
if
s
*
i
=
0
,
i
=
1
,
…
,
n
.So, taking the derivative with respect to s, we get
(29)
∂
∂
s
i
[
∑
a
t
a
(
A
+
B
s
+
C
s
2
,
s
)
(
A
+
B
s
+
C
s
2
)
]
|
s
=
s
*
=
∑
a
t
a
(
A
+
B
s
+
C
s
2
,
s
)
·
(
B
+
2
C
s
)
|
s
=
s
*
+
∑
a
[
∂
t
a
(
A
+
B
s
+
C
s
2
,
s
)
∂
(
A
+
B
s
+
C
s
2
)
·
(
B
+
2
C
s
)
+
∂
t
a
(
A
+
B
s
+
C
s
2
,
s
)
∂
s
]
·
(
A
+
B
s
+
C
s
2
)
|
s
=
s
*
.
Further, we know
(30)
B
=
D
s
f
|
s
=
s
*
,
C
=
1
2
·
H
s
f
|
s
=
s
*
,
f
(
s
)
=
A
+
B
s
+
C
s
2
.
So, substituting (29), we know
(31)
∂
∂
s
i
[
∑
a
t
a
(
A
+
B
s
+
C
s
2
,
s
)
(
A
+
B
s
+
C
s
2
)
]
|
s
=
s
*
=
∑
a
t
a
(
f
(
s
)
,
s
)
·
(
D
s
f
+
H
s
f
·
s
)
|
s
=
s
*
+
∑
a
[
∂
t
a
(
f
(
s
)
,
s
)
∂
f
·
(
D
s
f
+
H
s
f
·
s
)
+
∂
t
a
(
f
(
s
)
,
s
)
∂
s
]
·
f
a
|
s
=
s
*
,
f
=
f
*
=
∑
a
t
a
(
f
(
s
)
,
s
)
·
D
s
f
(
s
)
|
s
=
s
*
+
∑
a
[
∂
t
a
(
f
(
s
)
,
s
)
∂
f
·
D
s
f
(
s
)
+
∂
t
a
(
f
(
s
)
,
s
)
∂
s
]
·
f
a
|
s
=
s
*
,
f
=
f
*
=
∂
∂
s
[
∑
a
t
a
(
f
(
s
)
,
s
)
·
f
a
(
s
)
]
|
s
=
s
*
,
f
=
f
*
.
So, we know if conditions (i) and (ii) are satisfied, then the following should also be satisfied:(iii)
(32)
∂
Z
(
s
*
)
∂
s
i
=
0
if
s
*
i
>
0
,
i
=
1
,
…
,
n
,
(iv)
(33)
∂
Z
(
s
*
)
∂
s
i
≥
0
if
s
*
i
=
0
,
i
=
1
,
…
,
n
.


## 5. Numerical Example

This section provides two numerical examples which illustrate the computation of second-order sensitivity and the performance of NLAA. The first example demonstrates the computation of second-order sensitivity in detail. The second example focuses on the speed of convergence between LAA and NLAA.Example 1.
The first example is chosen from Dickson [25] and Fisk [14]. The network topology is shown in Figure 1. The set of OD pairs is {
(
1,2
)
,
(
3,4
)
} and a signal exists at the intersection of arcs 1 and 3. The cost functions used are
(34)
t
1
=
f
1
s
1
,
t
2
=
2
f
2
,
t
3
=
2
f
3
s
3
,
where s
a denotes the green time on arc a and the cycle time, s
1
+
s
3, is equal to 20.Figure 1
The network topology in Example1.Additionally, the travel demandT
1 from node 1 to node 2 is 10 and the travel demand T
2 from node 3 to node 4 is 10. Table 1 lists the arc cost functions t
a
(
f
a
,
s
a
) and the system objective function Z
(
s
).Table 1
Arc cost functions and the system objective function in Example1.
t
a
(
f
a
,
s
a
)
=
P
a
+
Q
a
(
f
a
/
s
a
)
Z
(
s
)
=
∑
a
(
t
a
(
f
a
,
s
a
)
·
f
a
)
Arc number
P
a
Q
a
1
2
1
2
0
2
3
0
2


### 5.1. First-Order and Second-Order Sensitivity Formulas

In this example,s
3 can be replaced by 20-s
1, and s
1 that is the only perturbation parameter (control variable) should be considered. Therefore, ρ is equal to 1. Together with (6) and (15), the first-order sensitivity with respect to s
1 can be rewritten as
(35)
[
D
s
f
D
s
μ
]
=
U
·
V
=
[
s
1
1
+
2
s
1
-
s
1
1
+
2
s
1
0
-
2
s
1
1
+
2
s
1
0
-
s
1
1
+
2
s
1
s
1
1
+
2
s
1
0
-
s
1
1
+
2
s
1
0
0
0
0
0
-
1
2
s
1
1
+
2
s
1
1
1
+
2
s
1
0
2
1
+
2
s
1
0
0
0
1
0
-
1
-
20
+
s
1
]
×
[
f
1
s
1
2
0
-
2
f
3
(
20
-
s
1
)
2
0
0
]
=
[
f
1
s
1
(
1
+
2
s
1
)
-
f
1
s
1
(
1
+
2
s
1
)
0
2
f
1
s
1
(
1
+
2
s
1
)
-
2
f
3
(
20
-
s
1
)
2
]
,
where
(36)
D
s
f
=
[
f
1
s
1
(
1
+
2
s
1
)
-
f
1
s
1
(
1
+
2
s
1
)
0
]
,
D
s
μ
=
[
2
f
1
s
1
(
1
+
2
s
1
)
-
2
f
3
(
20
-
s
1
)
2
]
.In (36), the sensitivity information of arc flow represents the change of arc flow on arc a, respectively, when the control variable s
1 increases one unit. Since f
1
≥
0 and s
1
>
0, the equilibrium flow on arc 1 will increase when s
1 increases one unit. In the meanwhile, the equilibrium flow on arc 2 will decrease. Because OD pair (3, 4) has only one path (arc 3), s
1 will not affect the equilibrium flow on arc 3.From Lemma7, the second-order sensitivity with respect to control variable is
(37)
[
H
s
f
H
s
μ
]
=
(
V
T
⊗
I
(
α
+
α
2
)
)
D
s
U
+
(
I
k
⊗
U
)
D
s
V
.
By Theorem 4, D
s
U can be derived by the chain rule for matrix functions as follows:
(38)
D
s
U
=
(
D
f
,
μ
U
)
[
D
s
f
D
s
μ
]
+
(
D
s
U
)
=
[
∂
vec
⁡
U
∂
vec
⁡
f
∂
vec
⁡
U
∂
vec
⁡
μ
]
[
D
s
f
D
s
μ
]
+
[
∂
vec
⁡
U
∂
vec
⁡
s
1
]
.In this example, the matrixU is only dependent on s
1. Hence, D
f
,
μ
U
=
0 and (38) can be rewritten as
(39)
D
s
U
=
[
∂
vec
⁡
U
∂
vec
⁡
s
1
]
=
[
∂
U
1
∂
s
1
∂
U
2
∂
s
1
∂
U
3
∂
s
1
∂
U
4
∂
s
1
∂
U
5
∂
s
1
]
,
where U
j represents the jth column of matrix U, and
(40)
∂
U
1
∂
s
1
=
[
1
(
1
+
2
s
1
)
2
-
1
(
1
+
2
s
1
)
2
0
2
(
1
+
2
s
1
)
2
0
]
,
∂
U
2
∂
s
1
=
[
-
1
(
1
+
2
s
1
)
2
1
(
1
+
2
s
1
)
2
0
-
2
(
1
+
2
s
1
)
2
0
]
,
∂
U
3
∂
s
1
=
[
0
0
0
0
0
]
,
∂
U
4
∂
s
1
=
[
-
2
(
1
+
2
s
1
)
2
2
(
1
+
2
s
1
)
2
0
-
4
(
1
+
2
s
1
)
2
0
]
,
∂
U
5
∂
s
1
=
[
0
0
0
0
2
(
-
20
+
s
1
)
2
]
.
Similarly, D
s
V can be derived as
(41)
D
s
V
=
(
D
f
,
μ
V
)
[
D
s
f
D
s
μ
]
+
(
D
s
V
)
=
[
∂
vec
⁡
V
∂
vec
⁡
f
∂
vec
⁡
V
∂
vec
⁡
μ
]
[
D
s
f
D
s
μ
]
+
[
∂
vec
⁡
V
∂
vec
⁡
s
1
]
=
[
1
s
1
2
0
0
0
0
0
0
0
0
0
0
0
-
2
(
20
-
s
1
)
2
0
0
0
0
0
0
0
0
0
0
0
0
]
[
f
1
s
1
(
1
+
2
s
1
)
-
f
1
s
1
(
1
+
2
s
1
)
0
2
f
1
s
1
(
1
+
2
s
1
)
-
2
f
3
(
20
-
s
1
)
2
]
+
[
-
2
f
1
s
1
3
0
-
4
f
3
(
20
-
s
1
)
3
0
0
]
=
[
f
1
s
1
3
(
1
+
2
s
1
)
-
2
f
1
s
1
3
0
-
4
f
3
(
20
-
s
1
)
3
0
0
]
.
According to Definition 1, (39), (40), and (38), (37) can be rewritten as
(42)
[
H
s
f
H
s
μ
]
=
(
V
T
⊗
I
5
)
D
s
U
+
(
I
1
⊗
U
)
D
s
V
=
[
f
1
s
1
2
·
I
5
0
·
I
5
-
2
f
3
(
20
-
s
1
)
2
·
I
5
0
·
I
5
0
·
I
5
]
T
[
∂
U
1
∂
s
1
∂
U
2
∂
s
1
∂
U
3
∂
s
1
∂
U
4
∂
s
1
∂
U
5
∂
s
1
]
+
(
1
·
U
)
[
f
1
s
1
3
(
1
+
2
s
1
)
-
2
f
1
s
1
3
0
-
4
f
3
(
20
-
s
1
)
3
0
0
]
=
[
-
4
f
1
s
1
(
1
+
2
s
1
)
2
4
f
1
s
1
(
1
+
2
s
1
)
2
0
-
8
f
1
s
1
(
1
+
2
s
1
)
2
4
f
3
(
-
20
+
s
1
)
3
]
.
Therefore,
(43)
H
s
f
=
[
-
4
f
1
s
1
(
1
+
2
s
1
)
2
4
f
1
s
1
(
1
+
2
s
1
)
2
0
]
,
H
s
μ
=
[
-
8
f
1
s
1
(
1
+
2
s
1
)
2
4
f
3
(
-
20
+
s
1
)
3
]
.


### 5.2. Computational Results of LAA and NLAA

Based on (36) and (43), the first differential and the second differential of equilibrium arc flow f
a can be obtained by (14). At iteration k,
(44)
B
s
k
+
1
=
d
f
(
s
0
;
s
)
=
D
s
f
|
f
=
f
k
,
s
1
=
s
1
k
·
(
s
1
k
+
1
-
s
1
k
)
=
[
f
1
k
s
1
k
(
1
+
2
s
1
k
)
-
f
1
k
s
1
k
(
1
+
2
s
1
k
)
0
]
·
(
s
1
k
+
1
-
s
1
k
)
=
[
f
1
k
(
s
1
k
+
1
-
s
1
k
)
s
1
k
(
1
+
2
s
1
k
)
-
f
1
k
(
s
1
k
+
1
-
s
1
k
)
s
1
k
(
1
+
2
s
1
k
)
0
]
,
C
(
s
k
+
1
)
2
=
1
2
d
2
f
(
s
0
;
s
)
=
1
2
(
(
s
1
k
+
1
-
s
1
k
)
T
⊗
I
3
)
·
H
s
f
|
f
=
f
k
,
s
1
=
s
1
k
·
(
s
1
k
+
1
-
s
1
k
)
=
1
2
(
(
s
1
k
+
1
-
s
1
k
)
⊗
[
1
0
0
0
1
0
0
0
1
]
)
·
[
-
4
f
1
k
s
1
k
(
1
+
2
s
1
k
)
2
4
f
1
k
s
1
k
(
1
+
2
s
1
k
)
2
0
]
·
(
s
1
k
+
1
-
s
1
k
)
=
[
-
4
f
1
k
(
s
1
k
+
1
-
s
1
k
)
2
2
s
1
k
(
1
+
2
s
1
k
)
2
4
f
1
k
(
s
1
k
+
1
-
s
1
k
)
2
2
s
1
k
(
1
+
2
s
1
k
)
2
0
]
.In this example, both LAA and NLAA are implemented in the MATLAB environment. Setδ
=
0.001 and the initial s
1
=
10; Table 2 lists the computational results of LAA and NLAA approaches, and it shows that NLAA is more efficient than LAA.Table 2
Computational results of LAA and NLAA in Example1.
Iteration
LAA
NLAA
f
1
s
1
Z
f
1
s
1
Z
1
8.44693
7.63647
47.23792
8.45125
7.70052
47.23576
2
8.45366
7.73667
47.23553
8.45326
7.73055
47.23552
3
8.45323
7.73019
47.23552
8.45326
7.73056
47.23552
4
8.45325
7.73040
47.23552Example 2.
This example is a simplified real network which represents the afternoon rush hour traffic between the working area Hsinchu Science-Based Industrial Park (HSIP) and the residential area Jhubei city. The network topology follows Figure2. In this period, there is a large amount of travel demand from HSIP (node 1) to Jhubei city (node 16). There are two parallel paths from HSIP to Jhubei city. One is a freeway (arc 2-arc 4-arc 16) and the other is a highway with 5 signal-controlled intersections (arc 1-arc 6-arc 8-arc 10-arc 12-arc 14). The objective of this problem is to find the optimal signal settings which minimize the system cost. The arc cost functions t
a
(
f
a
,
s
a
) and the system objective function Z
(
s
) are listed in Table 3. Table 4 lists the origin-destination demand. For the signal-controlled intersections, the arcs entering the same intersection share the same cycle time and the minimum green time for each approach is 10 sec.
In this example, we setδ
=
0.1 and the initial s
a
=
C
y
c
a
/
2 for each signalized arc. Table 5 lists the computational results of LAA and NLAA, respectively. Two parallel paths from node 1 to node 16 (2-4-16 and 1-6-8-10-12-14) have the same equilibrium travel time 13.4069 min. Table 5 shows that NLAA only takes 6% iterations, compared with LAA, to attain the same level of precision. Figure 3 shows the convergence curves of LAA and NLAA, respectively. The convergence rate of LAA is slower than NLAA due to the zigzag effect. Compared with Example 1, NLAA has more improvement in the speed of convergence than in Example 2. It may imply that NLAA is more efficient to deal with more nonlinear problems.Table 3
Arc cost functions and the system objective function in Example2.
Signalized arc cost function
t
a
(
f
a
,
s
a
)
=
t
0
a
(
1
+
α
a
(
f
a
C
a
(
s
a
/
Cy
c
a
)
)
β
a
)
Nonsignalized arc cost function
t
a
(
f
a
,
s
a
)
=
t
0
a
(
1
+
α
a
(
f
a
C
a
)
β
a
)
System objective function
Z
(
s
)
=
∑
a
(
t
a
(
f
a
,
s
a
)
·
f
a
)
Arc number
t
0
a (min)
α
a
β
a
C
a (veh/min)
Cyc
a (sec)
1
1.8545
0.9200
3.5800
56.6667
300
2
0.8667
0.9200
3.5800
40.0000
—
3
1.8000
1.2700
3.9600
115.0000
—
4
2.2364
1.2700
3.9600
115.0000
—
5
0.2945
1.2100
2.3900
28.3333
300
6
0.1964
1.4200
2.3200
85.0000
300
7
0.3818
0.8600
4.3400
85.0000
300
8
1.0154
1.2700
3.9600
68.3333
—
9
1.0000
1.2100
2.3900
20.0000
—
10
1.0154
1.2700
3.9600
68.3333
180
11
0.3273
0.9200
3.5800
56.6667
180
12
0.9818
1.4200
2.3200
85.0000
150
13
0.6545
0.8600
4.3400
113.3333
150
14
1.2000
1.5000
2.4400
113.3333
150
15
3.8727
1.2700
3.9600
115.0000
—
16
0.4909
0.9200
3.5800
40.0000
150Table 4
Origin-destination demand table in Example2 (unit: veh/hr).
Destination
4
6
8
11
13
14
16
Origin
1
50
275
475
400
1250
275
2250
2
0
0
0
0
2550
0
1400
5
0
150
250
200
0
150
250
7
0
0
500
400
0
300
450
9
0
0
0
325
0
225
350
12
0
0
0
0
0
125
175
15
0
0
0
0
0
0
900Table 5
Computational results of LAA and NLAA in Example2.
Arc number
LAA
NLAA
s
a (sec)
f
a (veh/min)
t
a (min)
s
a (sec)
f
a (veh/min)
t
a (min)
1
195.9103
31.4891
2.8118
195.8881
31.4901
2.8123
2
—
51.4275
2.8272
—
51.4266
2.8271
3
—
65.8333
2.0510
—
65.8333
2.0510
4
—
117.2609
5.3043
—
117.2599
5.3042
5
104.0897
16.6667
1.5529
104.1119
16.6667
1.5522
6
181.5056
47.3225
0.4263
181.4711
47.3234
0.4265
7
118.4944
27.5000
0.5199
118.5289
27.5000
0.5197
8
—
67.7391
2.2611
—
67.7401
2.2612
9
—
15.0000
1.6084
—
15.0000
1.6084
10
167.0451
62.3225
2.2192
167.0853
62.3234
2.2181
11
12.9549
5.0000
0.9517
12.9147
5.0000
0.9587
12
123.8799
45.2391
1.4849
123.8808
45.2401
1.4849
13
26.1201
15.0000
0.8256
26.1192
15.0000
0.8256
14
45.4083
42.3225
4.2042
45.4092
42.3234
4.2042
15
—
63.3333
4.3361
—
63.3333
4.3361
16
104.5917
53.9275
5.2760
104.5908
53.9266
5.2759
Iteration number
101
6
Objective value (Z)
2188.2886
2188.2404Figure 2
The network topology in Example2.Figure 3
The convergence curves of LAA and NLAA in Example2.


## 5.1. First-Order and Second-Order Sensitivity Formulas

In this example,s
3 can be replaced by 20-s
1, and s
1 that is the only perturbation parameter (control variable) should be considered. Therefore, ρ is equal to 1. Together with (6) and (15), the first-order sensitivity with respect to s
1 can be rewritten as
(35)
[
D
s
f
D
s
μ
]
=
U
·
V
=
[
s
1
1
+
2
s
1
-
s
1
1
+
2
s
1
0
-
2
s
1
1
+
2
s
1
0
-
s
1
1
+
2
s
1
s
1
1
+
2
s
1
0
-
s
1
1
+
2
s
1
0
0
0
0
0
-
1
2
s
1
1
+
2
s
1
1
1
+
2
s
1
0
2
1
+
2
s
1
0
0
0
1
0
-
1
-
20
+
s
1
]
×
[
f
1
s
1
2
0
-
2
f
3
(
20
-
s
1
)
2
0
0
]
=
[
f
1
s
1
(
1
+
2
s
1
)
-
f
1
s
1
(
1
+
2
s
1
)
0
2
f
1
s
1
(
1
+
2
s
1
)
-
2
f
3
(
20
-
s
1
)
2
]
,
where
(36)
D
s
f
=
[
f
1
s
1
(
1
+
2
s
1
)
-
f
1
s
1
(
1
+
2
s
1
)
0
]
,
D
s
μ
=
[
2
f
1
s
1
(
1
+
2
s
1
)
-
2
f
3
(
20
-
s
1
)
2
]
.In (36), the sensitivity information of arc flow represents the change of arc flow on arc a, respectively, when the control variable s
1 increases one unit. Since f
1
≥
0 and s
1
>
0, the equilibrium flow on arc 1 will increase when s
1 increases one unit. In the meanwhile, the equilibrium flow on arc 2 will decrease. Because OD pair (3, 4) has only one path (arc 3), s
1 will not affect the equilibrium flow on arc 3.From Lemma7, the second-order sensitivity with respect to control variable is
(37)
[
H
s
f
H
s
μ
]
=
(
V
T
⊗
I
(
α
+
α
2
)
)
D
s
U
+
(
I
k
⊗
U
)
D
s
V
.
By Theorem 4, D
s
U can be derived by the chain rule for matrix functions as follows:
(38)
D
s
U
=
(
D
f
,
μ
U
)
[
D
s
f
D
s
μ
]
+
(
D
s
U
)
=
[
∂
vec
⁡
U
∂
vec
⁡
f
∂
vec
⁡
U
∂
vec
⁡
μ
]
[
D
s
f
D
s
μ
]
+
[
∂
vec
⁡
U
∂
vec
⁡
s
1
]
.In this example, the matrixU is only dependent on s
1. Hence, D
f
,
μ
U
=
0 and (38) can be rewritten as
(39)
D
s
U
=
[
∂
vec
⁡
U
∂
vec
⁡
s
1
]
=
[
∂
U
1
∂
s
1
∂
U
2
∂
s
1
∂
U
3
∂
s
1
∂
U
4
∂
s
1
∂
U
5
∂
s
1
]
,
where U
j represents the jth column of matrix U, and
(40)
∂
U
1
∂
s
1
=
[
1
(
1
+
2
s
1
)
2
-
1
(
1
+
2
s
1
)
2
0
2
(
1
+
2
s
1
)
2
0
]
,
∂
U
2
∂
s
1
=
[
-
1
(
1
+
2
s
1
)
2
1
(
1
+
2
s
1
)
2
0
-
2
(
1
+
2
s
1
)
2
0
]
,
∂
U
3
∂
s
1
=
[
0
0
0
0
0
]
,
∂
U
4
∂
s
1
=
[
-
2
(
1
+
2
s
1
)
2
2
(
1
+
2
s
1
)
2
0
-
4
(
1
+
2
s
1
)
2
0
]
,
∂
U
5
∂
s
1
=
[
0
0
0
0
2
(
-
20
+
s
1
)
2
]
.
Similarly, D
s
V can be derived as
(41)
D
s
V
=
(
D
f
,
μ
V
)
[
D
s
f
D
s
μ
]
+
(
D
s
V
)
=
[
∂
vec
⁡
V
∂
vec
⁡
f
∂
vec
⁡
V
∂
vec
⁡
μ
]
[
D
s
f
D
s
μ
]
+
[
∂
vec
⁡
V
∂
vec
⁡
s
1
]
=
[
1
s
1
2
0
0
0
0
0
0
0
0
0
0
0
-
2
(
20
-
s
1
)
2
0
0
0
0
0
0
0
0
0
0
0
0
]
[
f
1
s
1
(
1
+
2
s
1
)
-
f
1
s
1
(
1
+
2
s
1
)
0
2
f
1
s
1
(
1
+
2
s
1
)
-
2
f
3
(
20
-
s
1
)
2
]
+
[
-
2
f
1
s
1
3
0
-
4
f
3
(
20
-
s
1
)
3
0
0
]
=
[
f
1
s
1
3
(
1
+
2
s
1
)
-
2
f
1
s
1
3
0
-
4
f
3
(
20
-
s
1
)
3
0
0
]
.
According to Definition 1, (39), (40), and (38), (37) can be rewritten as
(42)
[
H
s
f
H
s
μ
]
=
(
V
T
⊗
I
5
)
D
s
U
+
(
I
1
⊗
U
)
D
s
V
=
[
f
1
s
1
2
·
I
5
0
·
I
5
-
2
f
3
(
20
-
s
1
)
2
·
I
5
0
·
I
5
0
·
I
5
]
T
[
∂
U
1
∂
s
1
∂
U
2
∂
s
1
∂
U
3
∂
s
1
∂
U
4
∂
s
1
∂
U
5
∂
s
1
]
+
(
1
·
U
)
[
f
1
s
1
3
(
1
+
2
s
1
)
-
2
f
1
s
1
3
0
-
4
f
3
(
20
-
s
1
)
3
0
0
]
=
[
-
4
f
1
s
1
(
1
+
2
s
1
)
2
4
f
1
s
1
(
1
+
2
s
1
)
2
0
-
8
f
1
s
1
(
1
+
2
s
1
)
2
4
f
3
(
-
20
+
s
1
)
3
]
.
Therefore,
(43)
H
s
f
=
[
-
4
f
1
s
1
(
1
+
2
s
1
)
2
4
f
1
s
1
(
1
+
2
s
1
)
2
0
]
,
H
s
μ
=
[
-
8
f
1
s
1
(
1
+
2
s
1
)
2
4
f
3
(
-
20
+
s
1
)
3
]
.


## 5.2. Computational Results of LAA and NLAA

Based on (36) and (43), the first differential and the second differential of equilibrium arc flow f
a can be obtained by (14). At iteration k,
(44)
B
s
k
+
1
=
d
f
(
s
0
;
s
)
=
D
s
f
|
f
=
f
k
,
s
1
=
s
1
k
·
(
s
1
k
+
1
-
s
1
k
)
=
[
f
1
k
s
1
k
(
1
+
2
s
1
k
)
-
f
1
k
s
1
k
(
1
+
2
s
1
k
)
0
]
·
(
s
1
k
+
1
-
s
1
k
)
=
[
f
1
k
(
s
1
k
+
1
-
s
1
k
)
s
1
k
(
1
+
2
s
1
k
)
-
f
1
k
(
s
1
k
+
1
-
s
1
k
)
s
1
k
(
1
+
2
s
1
k
)
0
]
,
C
(
s
k
+
1
)
2
=
1
2
d
2
f
(
s
0
;
s
)
=
1
2
(
(
s
1
k
+
1
-
s
1
k
)
T
⊗
I
3
)
·
H
s
f
|
f
=
f
k
,
s
1
=
s
1
k
·
(
s
1
k
+
1
-
s
1
k
)
=
1
2
(
(
s
1
k
+
1
-
s
1
k
)
⊗
[
1
0
0
0
1
0
0
0
1
]
)
·
[
-
4
f
1
k
s
1
k
(
1
+
2
s
1
k
)
2
4
f
1
k
s
1
k
(
1
+
2
s
1
k
)
2
0
]
·
(
s
1
k
+
1
-
s
1
k
)
=
[
-
4
f
1
k
(
s
1
k
+
1
-
s
1
k
)
2
2
s
1
k
(
1
+
2
s
1
k
)
2
4
f
1
k
(
s
1
k
+
1
-
s
1
k
)
2
2
s
1
k
(
1
+
2
s
1
k
)
2
0
]
.In this example, both LAA and NLAA are implemented in the MATLAB environment. Setδ
=
0.001 and the initial s
1
=
10; Table 2 lists the computational results of LAA and NLAA approaches, and it shows that NLAA is more efficient than LAA.Table 2
Computational results of LAA and NLAA in Example1.
Iteration
LAA
NLAA
f
1
s
1
Z
f
1
s
1
Z
1
8.44693
7.63647
47.23792
8.45125
7.70052
47.23576
2
8.45366
7.73667
47.23553
8.45326
7.73055
47.23552
3
8.45323
7.73019
47.23552
8.45326
7.73056
47.23552
4
8.45325
7.73040
47.23552Example 2.
This example is a simplified real network which represents the afternoon rush hour traffic between the working area Hsinchu Science-Based Industrial Park (HSIP) and the residential area Jhubei city. The network topology follows Figure2. In this period, there is a large amount of travel demand from HSIP (node 1) to Jhubei city (node 16). There are two parallel paths from HSIP to Jhubei city. One is a freeway (arc 2-arc 4-arc 16) and the other is a highway with 5 signal-controlled intersections (arc 1-arc 6-arc 8-arc 10-arc 12-arc 14). The objective of this problem is to find the optimal signal settings which minimize the system cost. The arc cost functions t
a
(
f
a
,
s
a
) and the system objective function Z
(
s
) are listed in Table 3. Table 4 lists the origin-destination demand. For the signal-controlled intersections, the arcs entering the same intersection share the same cycle time and the minimum green time for each approach is 10 sec.
In this example, we setδ
=
0.1 and the initial s
a
=
C
y
c
a
/
2 for each signalized arc. Table 5 lists the computational results of LAA and NLAA, respectively. Two parallel paths from node 1 to node 16 (2-4-16 and 1-6-8-10-12-14) have the same equilibrium travel time 13.4069 min. Table 5 shows that NLAA only takes 6% iterations, compared with LAA, to attain the same level of precision. Figure 3 shows the convergence curves of LAA and NLAA, respectively. The convergence rate of LAA is slower than NLAA due to the zigzag effect. Compared with Example 1, NLAA has more improvement in the speed of convergence than in Example 2. It may imply that NLAA is more efficient to deal with more nonlinear problems.Table 3
Arc cost functions and the system objective function in Example2.
Signalized arc cost function
t
a
(
f
a
,
s
a
)
=
t
0
a
(
1
+
α
a
(
f
a
C
a
(
s
a
/
Cy
c
a
)
)
β
a
)
Nonsignalized arc cost function
t
a
(
f
a
,
s
a
)
=
t
0
a
(
1
+
α
a
(
f
a
C
a
)
β
a
)
System objective function
Z
(
s
)
=
∑
a
(
t
a
(
f
a
,
s
a
)
·
f
a
)
Arc number
t
0
a (min)
α
a
β
a
C
a (veh/min)
Cyc
a (sec)
1
1.8545
0.9200
3.5800
56.6667
300
2
0.8667
0.9200
3.5800
40.0000
—
3
1.8000
1.2700
3.9600
115.0000
—
4
2.2364
1.2700
3.9600
115.0000
—
5
0.2945
1.2100
2.3900
28.3333
300
6
0.1964
1.4200
2.3200
85.0000
300
7
0.3818
0.8600
4.3400
85.0000
300
8
1.0154
1.2700
3.9600
68.3333
—
9
1.0000
1.2100
2.3900
20.0000
—
10
1.0154
1.2700
3.9600
68.3333
180
11
0.3273
0.9200
3.5800
56.6667
180
12
0.9818
1.4200
2.3200
85.0000
150
13
0.6545
0.8600
4.3400
113.3333
150
14
1.2000
1.5000
2.4400
113.3333
150
15
3.8727
1.2700
3.9600
115.0000
—
16
0.4909
0.9200
3.5800
40.0000
150Table 4
Origin-destination demand table in Example2 (unit: veh/hr).
Destination
4
6
8
11
13
14
16
Origin
1
50
275
475
400
1250
275
2250
2
0
0
0
0
2550
0
1400
5
0
150
250
200
0
150
250
7
0
0
500
400
0
300
450
9
0
0
0
325
0
225
350
12
0
0
0
0
0
125
175
15
0
0
0
0
0
0
900Table 5
Computational results of LAA and NLAA in Example2.
Arc number
LAA
NLAA
s
a (sec)
f
a (veh/min)
t
a (min)
s
a (sec)
f
a (veh/min)
t
a (min)
1
195.9103
31.4891
2.8118
195.8881
31.4901
2.8123
2
—
51.4275
2.8272
—
51.4266
2.8271
3
—
65.8333
2.0510
—
65.8333
2.0510
4
—
117.2609
5.3043
—
117.2599
5.3042
5
104.0897
16.6667
1.5529
104.1119
16.6667
1.5522
6
181.5056
47.3225
0.4263
181.4711
47.3234
0.4265
7
118.4944
27.5000
0.5199
118.5289
27.5000
0.5197
8
—
67.7391
2.2611
—
67.7401
2.2612
9
—
15.0000
1.6084
—
15.0000
1.6084
10
167.0451
62.3225
2.2192
167.0853
62.3234
2.2181
11
12.9549
5.0000
0.9517
12.9147
5.0000
0.9587
12
123.8799
45.2391
1.4849
123.8808
45.2401
1.4849
13
26.1201
15.0000
0.8256
26.1192
15.0000
0.8256
14
45.4083
42.3225
4.2042
45.4092
42.3234
4.2042
15
—
63.3333
4.3361
—
63.3333
4.3361
16
104.5917
53.9275
5.2760
104.5908
53.9266
5.2759
Iteration number
101
6
Objective value (Z)
2188.2886
2188.2404Figure 2
The network topology in Example2.Figure 3
The convergence curves of LAA and NLAA in Example2.


## 6. Conclusions

The key information to solve the equilibrium network signal control problem (ENSCP) is the reaction function of the lower-level problem. Because the reaction function cannot be obtained explicitly, the sensitivity information of equilibrium network flows is used to approximate it. Based on the first-order sensitivity formula and the matrix calculus, this paper first presents the general form of the second-order sensitivity formula for equilibrium network flows. With the second-order sensitivity formula, the reaction function can be approximated more accurately by a nonlinear function. From HSIP to Jhubei city, a simplified real network example demonstrates the speed of convergence between LAA and NLAA. The NLAA has significant improvement in solving the ENSCP with complicated arc cost functions; in this example, the NLAA only takes 6% iterations to attain the same level of precision.This study focuses on the NLAA and a simplified delay formula is adopted to reflect the influence of traffic congestion. Practically, a traffic propagation model, such as TRANSYT model, should be included when solving the ENSCP. Since the derivatives of TRANSYT model have been obtained explicitly [4, 42], it can be extended to second-order derivatives and applied to NLAA in the future research.Compared with LAA, the number of multiplications for matrix multiplication is greatly increasing in NLAA due to the Kronecker-product operation. NLAA has polynomial complexity with the network size and the number of perturbation parameters because of the property of the Kronecker product. There is still opportunity to improve the computing efficiency through adopting effective Kronecker-product algorithms.



---

*Source: 947190-2014-05-11.xml*