# Topological Effects and Performance Optimization in Transportation Continuous Network Design

Authors: Jianjun Wu; Xin Guo; Huijun Sun; Bo Wang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Because of the limitation of budget, in the planning of road works, increased efforts should be made on links that are more critical to the whole traffic system. Therefore, it would be helpful to model and evaluate the vulnerability and reliability of the transportation network when the network design is processing. This paper proposes a bilevel transportation network design model, in which the upper level is to minimize the performance of the network under the given budgets, while the lower level is a typical user equilibrium assignment problem. A new solution approach based on particle swarm optimization (PSO) method is presented. The topological effects on the performance of transportation networks are studied with the consideration of three typical networks, regular lattice, random graph, and small-world network. Numerical examples and simulations are presented to demonstrate the proposed model.


---

## Body

## 1. Introduction

The network design problem (NDP) involves the optimal decision on the expansion of an urban street and highway system in response to a growing demand for travel. It has emerged as an important area for progress in handling effective transport planning, because the demand for travel on the roads is growing at a rate faster than our urban transport systems can ever hope to accommodate, while resources available for expanding the system capacity remain limited. The objective of NDP is to optimize a given system performance measure such as to minimize total system travel cost, while accounting for the route choice behavior of network users [1]. The decisions made by road planners influence the route choice behavior of network users, which is normally described by a network user equilibrium model. Mathematically, the bilevel programming is a good technique to describe this hierarchical property of the NDP with an equilibrium constraint. Generally the upper level problem is to minimize the total system cost and the lower level problem is to characterize the UE traffic flow pattern ([2, 3]).Studies have been overwhelmingly focused on the continuous network design problem (CNDP) and substantial achievements in algorithmic development have been made. Abdulaal and LeBlanc [4] formulated the CNDP under deterministic user equilibrium (DUE) as a bilevel programming model and the Hooke-Jeeves heuristic algorithm was also introduced. As an application, Friesz et al. [5] used a simulated annealing approach to solve the multiobjective equilibrium network design problem as a single level minimization problem. Marcotte [6] transferred the CNDP into a single level equivalent differentiable optimization problem. Meng et al. [7] reformulated the CNDP under the DUE constraints into an equivalent single level continuously differentiable problem by virtue of a marginal function tool. Gao and Song [3] combined the concept of reserve capacity with the continuous equilibrium network design problem and proposed a globally convergent algorithm to solve the CNDP.In the planning of road works, there should be awareness about the impacts of the increased capacity of a link on the whole network. Because the improvement of road capacity will attract the limitation of budget, the prioritization for road maintenance, repair, and contingency planning should be considered carefully in NDP. Therefore, increased efforts should be made on links that are more critical to the system. It would be thus helpful to model and evaluate the vulnerability and reliability of the transportation network when the network design is processing.In a series of papers, the measures to quantifiable efficiency/performance of a network have been developed. For example, Latora and Marchiori discussed the network performance issue by measuring the “global efficiency” in a weighted network as compared to that of the simple nonweighted small-world network [8–10]. In a weighted network, the network is characterized not only by the edges that connect different nodes, but also by the weights associated with different edges in order to capture the relationships between different nodes.The flow on a network is an additional important indicator of network performance as well as network vulnerability. Indeed, flows represent the usage of a network and which paths and links have positive flows and the magnitude of these flows are relevant in the case of network disruptions [11]. There are few papers to date that consider network flows in assessing network performance. The results in Zhu et al. [12] are notable since they demonstrate empirically through an application to the airline network of China how a measure with flows and costs outperforms existing measures in yielding more realistic results in terms of, for example, which cities are critical and their rankings in the network.Recently, Jenelius et al. [13] proposed several link importance indicators and applied them to the road transportation network in northern Sweden. Murray-Tuite and Mahmassani [14] also focused on identifying indices for the determination of vulnerable links in transportation networks. Qiang and Nagurney [11] proposed a unified network performance measure that can be applied to assess the importance of either links or nodes or both in the case of either fixed or elastic demands.Although previous work for the traffic network design has been focused on minimizing the total system cost or maximizing the total profits of the network, little attention has been given to the structure factors underlying vulnerabilities and the robustness. In the traffic network, if the Hub link is attacked, the whole network may be broken down soon. Therefore, the purpose of network designs is not only to decrease the travel cost of the system, but also to increase the robustness and reduce the vulnerabilities. Different with most previous works on CNDP, the performance measure is adopted to test the network design strategies in this paper. Our results give a better understanding of the network structure effects on its performance.This paper is organized as follows. A bilevel model of CNDP is given in Section2. Further solution algorithm is developed in Section 3. And Section 4 gives a numerical example to illustrate the model. Finally, conclusions and further considerations are presented in Section 5.


## 2. A Bilevel Programming Model for CNDP

The transportation CNDP can be represented as a leader-follower game where the transportation planning departments are leaders, and the users who can freely choose the path are the followers [15]. It is assumed that the transportation planning managers can influence, but cannot control, the users’ path-choosing behaviors. The users make their decision in a user optimal manner. Thus, this interactive game can be represented as a bilevel programming problem.The transportation planners, the upper level, decide the capacity of each road to maximize the system performance based on traffic flows. However, the lower level reflects the choice behaviors of drivers with user equilibrium assignment. In this model, the system performance and link flows are considered all together.Notations
A: the set of arcs (links);
R and S: the sets of vertices which represent origins and destinations, respectively;
x
a: the total flow on link a, a
∈
A, and A is the link set of the network;
ψ
a: the continuous capacity increase of link a;
K
r
s: the set of path between r and s;
r: the origin node, r
∈
R;
s: the destination node, s
∈
S;
t
a
(
·
): the link travel time (or cost) function which is continuously differentiable and convex for fixed ψ
a. Generally, we use the following form for t
a
(
·
):
(1)
t
a
(
x
a
,
ψ
a
)
=
t
0
a
[
1
+
η
a
(
x
a
k
a
+
ψ
a
)
]
4
,
where η
a are parameters and k
a is the capacity of link a [16]. t
0
a is the free-flow of link a;
q
r
s: the total traffic demand between origin r and destination s;
h
k
r
s: flows on path k connecting r and s;
δ
a
,
k
r
s: path/link incidence variables.


### 2.1. The Lower Level User Equilibrium Assignment

It is worth emphasizing that the network design problem must be solved with the network flow pattern constrained to be a user equilibrium problem. In general, improvement of road network characteristics will definitely induce changes in traffic flow over the network. More importantly, addition of a new road segment or capacity enhancement to a congested network, without considering the response of network users, may actually increase network-wide congestion. This well-known phenomenon has been demonstrated by the ostensible Braess paradox. Therefore, prediction of traffic patterns via a comprehensive behavior model is essential to the network design process.Traditionally, CNDP models hypothesize that the demand is given and fixed, and the users’ route choice is characterized by the user equilibrium assignment problem. LetA be the set of arcs (links); R and S are the sets of vertices which represent origins and destinations, respectively. The user equilibrium problem with fixed demand can be formulated as follows [16]:
(2)
(
L
)
min
⁡
T
(
x
,
ψ
)
=
∑
a
∈
A
∫
0
x
a
(
ψ
)
t
a
(
v
,
ψ
a
)
d
v
,
(3)
s
.
t
.
∑
k
h
k
r
s
=
q
r
s
,
∀
r
∈
R
,
s
∈
S
,
(4)
(
L
)
min
⁡
h
k
r
s
≥
0
,
∀
r
∈
R
,
s
∈
S
,
k
∈
K
r
s
,
(5)
(
L
)
min
⁡
x
a
=
∑
r
∑
s
∑
k
h
k
r
s
δ
a
,
k
r
s
,
∀
a
∈
A
.In this model, the users at the lower level are assumed to follow the user-equilibrium principle of Wardrop under the given network. Constraints (3), (4), and (5) are conservative, definitions, and nonnegativity of the flow constraints.


### 2.2. The Upper Level Model

#### 2.2.1. The Performance Measure of Network

Recently, the vulnerability of a network has attracted many interests in the urban traffic system. As an important performance index, it can be used to assess the efficiency of a network in the case of either fixed or elastic demands and capture flow information and behavior, allowing one to determine the criticality of various nodes (as well as links) through the identification of their importance and ranking [11]. Therefore, this measure can be used to assess the vulnerability of a network to disruptions and is a more general one since it not only considers the topology characteristics, but also captures the flows on the network through the disutility, costs, and the demands.The network performance/efficiency measureZ, for a given network topology G and the equilibrium (or fixed) demand vector q, is defined as follows [11]:
(6)
Z
=
∑
r
s
∈
W
(
q
r
s
/
c
r
s
)
n
r
s
,
where n
r
s is the number of OD pairs in the network and q
r
s and c
r
s denote the equilibrium (or fixed) demand and the equilibrium disutility or the shortest path for OD pair r
s, respectively. W is the set of OD pair.In this paper, it is an optimized objective in the upper level model. The network planners of the upper level are assumed to make the decisions about the improvement of link capacities and investments in order to maximize the performance of the whole system in the range of budgets formulated by the government. Therefore, the upper level of the bilevel model (U) can be presented as follows:
(7)
(
U
)
max
⁡
Z
=
∑
r
s
∈
W
(
q
r
s
/
c
r
s
)
n
r
s
,
(8)
s
.
t
.
∑
a
∈
A
G
a
(
ψ
a
)
≤
B
,
(9)
(
U
)
max
⁡
ψ
a
≥
0
;
∀
a
∈
A
,
(10)
(
U
)
max
⁡
c
k
r
s
=
∑
r
s
∈
W
,
k
∈
K
r
s
,
a
∈
A
δ
a
,
k
r
s
t
a
(
x
a
,
ψ
a
)
,
(
U
)
max
⁡
∀
r
s
∈
W
,
k
∈
K
r
s
,
(11)
(
U
)
max
⁡
c
r
s
=
min
⁡
{
c
k
r
s
}
,
∀
r
s
∈
W
,
k
∈
K
r
s
,
where ψ
a is the continuous capacity increase of link a; G
a
(
ψ
a
) is the investment function of link a
∈
A; B is the total investment budget; c
k
r
s is the cost of path k of OD pair r
s.The objective of upper level model is to maximize the performance. Constraint (8) ensures that the total investment cost will not exceed the total budget. Constraint (9) is the nonnegativity of the decision variables. Constraint (10) expresses the relationship between the  link and path cost. Constraint (11) is the shortest path cost between OD pair r
s.


## 2.1. The Lower Level User Equilibrium Assignment

It is worth emphasizing that the network design problem must be solved with the network flow pattern constrained to be a user equilibrium problem. In general, improvement of road network characteristics will definitely induce changes in traffic flow over the network. More importantly, addition of a new road segment or capacity enhancement to a congested network, without considering the response of network users, may actually increase network-wide congestion. This well-known phenomenon has been demonstrated by the ostensible Braess paradox. Therefore, prediction of traffic patterns via a comprehensive behavior model is essential to the network design process.Traditionally, CNDP models hypothesize that the demand is given and fixed, and the users’ route choice is characterized by the user equilibrium assignment problem. LetA be the set of arcs (links); R and S are the sets of vertices which represent origins and destinations, respectively. The user equilibrium problem with fixed demand can be formulated as follows [16]:
(2)
(
L
)
min
⁡
T
(
x
,
ψ
)
=
∑
a
∈
A
∫
0
x
a
(
ψ
)
t
a
(
v
,
ψ
a
)
d
v
,
(3)
s
.
t
.
∑
k
h
k
r
s
=
q
r
s
,
∀
r
∈
R
,
s
∈
S
,
(4)
(
L
)
min
⁡
h
k
r
s
≥
0
,
∀
r
∈
R
,
s
∈
S
,
k
∈
K
r
s
,
(5)
(
L
)
min
⁡
x
a
=
∑
r
∑
s
∑
k
h
k
r
s
δ
a
,
k
r
s
,
∀
a
∈
A
.In this model, the users at the lower level are assumed to follow the user-equilibrium principle of Wardrop under the given network. Constraints (3), (4), and (5) are conservative, definitions, and nonnegativity of the flow constraints.


## 2.2. The Upper Level Model

### 2.2.1. The Performance Measure of Network

Recently, the vulnerability of a network has attracted many interests in the urban traffic system. As an important performance index, it can be used to assess the efficiency of a network in the case of either fixed or elastic demands and capture flow information and behavior, allowing one to determine the criticality of various nodes (as well as links) through the identification of their importance and ranking [11]. Therefore, this measure can be used to assess the vulnerability of a network to disruptions and is a more general one since it not only considers the topology characteristics, but also captures the flows on the network through the disutility, costs, and the demands.The network performance/efficiency measureZ, for a given network topology G and the equilibrium (or fixed) demand vector q, is defined as follows [11]:
(6)
Z
=
∑
r
s
∈
W
(
q
r
s
/
c
r
s
)
n
r
s
,
where n
r
s is the number of OD pairs in the network and q
r
s and c
r
s denote the equilibrium (or fixed) demand and the equilibrium disutility or the shortest path for OD pair r
s, respectively. W is the set of OD pair.In this paper, it is an optimized objective in the upper level model. The network planners of the upper level are assumed to make the decisions about the improvement of link capacities and investments in order to maximize the performance of the whole system in the range of budgets formulated by the government. Therefore, the upper level of the bilevel model (U) can be presented as follows:
(7)
(
U
)
max
⁡
Z
=
∑
r
s
∈
W
(
q
r
s
/
c
r
s
)
n
r
s
,
(8)
s
.
t
.
∑
a
∈
A
G
a
(
ψ
a
)
≤
B
,
(9)
(
U
)
max
⁡
ψ
a
≥
0
;
∀
a
∈
A
,
(10)
(
U
)
max
⁡
c
k
r
s
=
∑
r
s
∈
W
,
k
∈
K
r
s
,
a
∈
A
δ
a
,
k
r
s
t
a
(
x
a
,
ψ
a
)
,
(
U
)
max
⁡
∀
r
s
∈
W
,
k
∈
K
r
s
,
(11)
(
U
)
max
⁡
c
r
s
=
min
⁡
{
c
k
r
s
}
,
∀
r
s
∈
W
,
k
∈
K
r
s
,
where ψ
a is the continuous capacity increase of link a; G
a
(
ψ
a
) is the investment function of link a
∈
A; B is the total investment budget; c
k
r
s is the cost of path k of OD pair r
s.The objective of upper level model is to maximize the performance. Constraint (8) ensures that the total investment cost will not exceed the total budget. Constraint (9) is the nonnegativity of the decision variables. Constraint (10) expresses the relationship between the  link and path cost. Constraint (11) is the shortest path cost between OD pair r
s.


## 2.2.1. The Performance Measure of Network

Recently, the vulnerability of a network has attracted many interests in the urban traffic system. As an important performance index, it can be used to assess the efficiency of a network in the case of either fixed or elastic demands and capture flow information and behavior, allowing one to determine the criticality of various nodes (as well as links) through the identification of their importance and ranking [11]. Therefore, this measure can be used to assess the vulnerability of a network to disruptions and is a more general one since it not only considers the topology characteristics, but also captures the flows on the network through the disutility, costs, and the demands.The network performance/efficiency measureZ, for a given network topology G and the equilibrium (or fixed) demand vector q, is defined as follows [11]:
(6)
Z
=
∑
r
s
∈
W
(
q
r
s
/
c
r
s
)
n
r
s
,
where n
r
s is the number of OD pairs in the network and q
r
s and c
r
s denote the equilibrium (or fixed) demand and the equilibrium disutility or the shortest path for OD pair r
s, respectively. W is the set of OD pair.In this paper, it is an optimized objective in the upper level model. The network planners of the upper level are assumed to make the decisions about the improvement of link capacities and investments in order to maximize the performance of the whole system in the range of budgets formulated by the government. Therefore, the upper level of the bilevel model (U) can be presented as follows:
(7)
(
U
)
max
⁡
Z
=
∑
r
s
∈
W
(
q
r
s
/
c
r
s
)
n
r
s
,
(8)
s
.
t
.
∑
a
∈
A
G
a
(
ψ
a
)
≤
B
,
(9)
(
U
)
max
⁡
ψ
a
≥
0
;
∀
a
∈
A
,
(10)
(
U
)
max
⁡
c
k
r
s
=
∑
r
s
∈
W
,
k
∈
K
r
s
,
a
∈
A
δ
a
,
k
r
s
t
a
(
x
a
,
ψ
a
)
,
(
U
)
max
⁡
∀
r
s
∈
W
,
k
∈
K
r
s
,
(11)
(
U
)
max
⁡
c
r
s
=
min
⁡
{
c
k
r
s
}
,
∀
r
s
∈
W
,
k
∈
K
r
s
,
where ψ
a is the continuous capacity increase of link a; G
a
(
ψ
a
) is the investment function of link a
∈
A; B is the total investment budget; c
k
r
s is the cost of path k of OD pair r
s.The objective of upper level model is to maximize the performance. Constraint (8) ensures that the total investment cost will not exceed the total budget. Constraint (9) is the nonnegativity of the decision variables. Constraint (10) expresses the relationship between the  link and path cost. Constraint (11) is the shortest path cost between OD pair r
s.


## 3. Solution Algorithm of the Bilevel Model

### 3.1. Particle Swarm Optimization (PSO)

Since the bilevel programming is a NP-hard problem, in general, it is difficult to solve with optimization algorithms. Although many solution algorithms such as the sensitivity analysis based on an algorithm (SAB) [1, 3] have been developed, the SAB method has to calculate the inverse of the matrix and only can be used under many assumptions (e.g., assume that the lower level functions are second order continuous differentiable and the lower level has a unique solution for fixed upper level variables), which limits the application in engineering. Recently, the intelligent algorithms are designed to solve the bilevel programming including the Gene algorithm, Ant algorithm, and particle swarm optimization (PSO) [17]. Compared with other algorithms, PSO has some advantages: (1) the algorithm is easy to implement and there are few parameters to adjust; (2) all of the particles have a strong ability to find the optimized solution; (3) it need not any special conditions about functions and can be used to solve all kinds of bilevel models. Currently, PSO has been widely used in function optimization, neural networks, fuzzy systems control, and other applications. In recent years, the research and practice show that PSO has fast convergence at high solution quality, robustness, and other advantages in terms of optimization objectives. Therefore, PSO algorithm based on solution procedure is used in this paper.Bird flocking optimizes a certain objective function. Each particle knows its personal best position (p
best) so far and the global best position (g
best) of the swarm among all the p
bests. Each particle tries to modify its position using the current velocity and the distance from p
best and g
best [18].In this paper, a particle position is denoted by a feasible link capacity enhancementψ
i
=
(
…
,
ψ
(
i
)
a
,
…
). The velocity V
i
=
(
…
,
v
(
i
)
a
,
…
,
) of the ith particle corresponds to the search direction. Therefore, the position of ith particle is used to represent the feasible decision scheme. By comparing the fitness value, which denotes the value of upper objective function, the optimal positions p
best
i
n and g
best
n of ith particle and the whole swarm particle at time n are obtained, respectively. Then the velocity and the position of ith particle are updated at time n
+
1 as follows:
(12)
V
i
n
+
1
=
ω
V
i
n
+
c
1
R
i
1
n
(
p
best
i
n
-
ψ
i
n
)
+
c
2
R
i
2
n
(
g
best
n
-
ψ
i
n
)
,
(13)
ψ
i
n
+
1
=
ψ
i
n
+
χ
V
i
n
,
where i
=
1,2
,
…
,
M; M is the swarm’s size; χ is a constriction factor used to control and constrict velocities; ω is the inertia weight; c
1 and c
2 are two positive constants, called the cognitive and social parameter, respectively; R
i
1
n and R
i
2
n are random numbers uniformly distributed within the interval [
0
,
1
]. The parameters c
1
R
i
1
n and c
2
R
i
2
n provide randomness that renders the technique less predictable but more flexible [17]. In general, the performance of each particle is measured according to fitness function.Fourie and Groenwold [19] proposed a dynamic inertia and maximum velocity reduction method. That is, if no more improved solutions are obtained after several iterations, set the inertia weight ω
n
+
1
=
α
ω
n and maximum allowed velocity V
max
⁡
n
+
1
=
β
V
max
⁡
n (0
<
α, β
<
1) to fine-tune local search.


### 3.2. The Algorithm for Solving the Bilevel Model of CNDP

The major steps of the PSO method for solving the CNDP are summarized as follows.Step 1 (initialization).
Initialize parametersω
0, V
max
⁡, α, β (0
<
α, β
<
1), the dynamic delay period h, and the swarm size M which corresponds to feasible solutions and evaluate the initial velocity of every particle. The initial position ψ
i
0 and velocity V
i
0 are given. Let time step n
=
0.Step 2 (calculating fitness).
For each particle, we translate it into a feasible solution. Then, we solve the corresponding lower level problem by Frank-Wolfe method [16] and evaluate the upper level objective in (7), calculating the particle’s fitness.Step 3 (updating).
For each particle, update itsp
best with the position relevant to the smallest fitness which it so far experienced. For the swarm, update the g
best with the position relevant to the smallest fitness among all the p
best. If no improvement in the g
best occurs after h iterations, set ω
n
+
1
=
α
ω
n, V
max
⁡
n
+
1
=
β
V
max
⁡
n. Then, update the velocities using (12) and truncate them to the nearest integers.Step 4 (generating new position).
Generate the new position with (13).Step 5 (checking feasibility).
All the new positions are tentative particles. Discard the new positioni (i
=
1,2
,
…
,
M) if it does not satisfy constraints (8) and (9). Leave it at the previous position and go to Step 6.Step 6 (termination).
If the iteration number reaches the maximum iteration number or other termination criteria, then stop. Get the lastg
best as the optimal solution. Otherwise, n
++, go to Step 2.


## 3.1. Particle Swarm Optimization (PSO)

Since the bilevel programming is a NP-hard problem, in general, it is difficult to solve with optimization algorithms. Although many solution algorithms such as the sensitivity analysis based on an algorithm (SAB) [1, 3] have been developed, the SAB method has to calculate the inverse of the matrix and only can be used under many assumptions (e.g., assume that the lower level functions are second order continuous differentiable and the lower level has a unique solution for fixed upper level variables), which limits the application in engineering. Recently, the intelligent algorithms are designed to solve the bilevel programming including the Gene algorithm, Ant algorithm, and particle swarm optimization (PSO) [17]. Compared with other algorithms, PSO has some advantages: (1) the algorithm is easy to implement and there are few parameters to adjust; (2) all of the particles have a strong ability to find the optimized solution; (3) it need not any special conditions about functions and can be used to solve all kinds of bilevel models. Currently, PSO has been widely used in function optimization, neural networks, fuzzy systems control, and other applications. In recent years, the research and practice show that PSO has fast convergence at high solution quality, robustness, and other advantages in terms of optimization objectives. Therefore, PSO algorithm based on solution procedure is used in this paper.Bird flocking optimizes a certain objective function. Each particle knows its personal best position (p
best) so far and the global best position (g
best) of the swarm among all the p
bests. Each particle tries to modify its position using the current velocity and the distance from p
best and g
best [18].In this paper, a particle position is denoted by a feasible link capacity enhancementψ
i
=
(
…
,
ψ
(
i
)
a
,
…
). The velocity V
i
=
(
…
,
v
(
i
)
a
,
…
,
) of the ith particle corresponds to the search direction. Therefore, the position of ith particle is used to represent the feasible decision scheme. By comparing the fitness value, which denotes the value of upper objective function, the optimal positions p
best
i
n and g
best
n of ith particle and the whole swarm particle at time n are obtained, respectively. Then the velocity and the position of ith particle are updated at time n
+
1 as follows:
(12)
V
i
n
+
1
=
ω
V
i
n
+
c
1
R
i
1
n
(
p
best
i
n
-
ψ
i
n
)
+
c
2
R
i
2
n
(
g
best
n
-
ψ
i
n
)
,
(13)
ψ
i
n
+
1
=
ψ
i
n
+
χ
V
i
n
,
where i
=
1,2
,
…
,
M; M is the swarm’s size; χ is a constriction factor used to control and constrict velocities; ω is the inertia weight; c
1 and c
2 are two positive constants, called the cognitive and social parameter, respectively; R
i
1
n and R
i
2
n are random numbers uniformly distributed within the interval [
0
,
1
]. The parameters c
1
R
i
1
n and c
2
R
i
2
n provide randomness that renders the technique less predictable but more flexible [17]. In general, the performance of each particle is measured according to fitness function.Fourie and Groenwold [19] proposed a dynamic inertia and maximum velocity reduction method. That is, if no more improved solutions are obtained after several iterations, set the inertia weight ω
n
+
1
=
α
ω
n and maximum allowed velocity V
max
⁡
n
+
1
=
β
V
max
⁡
n (0
<
α, β
<
1) to fine-tune local search.


## 3.2. The Algorithm for Solving the Bilevel Model of CNDP

The major steps of the PSO method for solving the CNDP are summarized as follows.Step 1 (initialization).
Initialize parametersω
0, V
max
⁡, α, β (0
<
α, β
<
1), the dynamic delay period h, and the swarm size M which corresponds to feasible solutions and evaluate the initial velocity of every particle. The initial position ψ
i
0 and velocity V
i
0 are given. Let time step n
=
0.Step 2 (calculating fitness).
For each particle, we translate it into a feasible solution. Then, we solve the corresponding lower level problem by Frank-Wolfe method [16] and evaluate the upper level objective in (7), calculating the particle’s fitness.Step 3 (updating).
For each particle, update itsp
best with the position relevant to the smallest fitness which it so far experienced. For the swarm, update the g
best with the position relevant to the smallest fitness among all the p
best. If no improvement in the g
best occurs after h iterations, set ω
n
+
1
=
α
ω
n, V
max
⁡
n
+
1
=
β
V
max
⁡
n. Then, update the velocities using (12) and truncate them to the nearest integers.Step 4 (generating new position).
Generate the new position with (13).Step 5 (checking feasibility).
All the new positions are tentative particles. Discard the new positioni (i
=
1,2
,
…
,
M) if it does not satisfy constraints (8) and (9). Leave it at the previous position and go to Step 6.Step 6 (termination).
If the iteration number reaches the maximum iteration number or other termination criteria, then stop. Get the lastg
best as the optimal solution. Otherwise, n
++, go to Step 2.


## 4. Numerical Examples

Example 1 (a simple network form).
To illustrate the effectiveness of the proposed approach, consider the 5-node and 6-link graph given in Figure1 [11]. There are two OD pairs from origin 1 to destinations 4 and 5, respectively. Table 1 presents the functional forms of the travel and investment costs, as well as the parameter values for each link, used in this numerical test.Table 1
Data for the test network.
Link
t
0
a
η
a
d
a
k
a
1→2
1.0
0.15
0.5
40
1→3
2.0
0.15
0.5
40
2→4
1.0
0.15
0.5
40
2→5
1.5
0.15
0.5
40
3→4
1.0
0.15
0.5
40
3→5
1.5
0.15
0.5
40
t
a
(
x
a
,
ψ
a
)
=
t
0
a
[
1
+
η
a
(
x
a
/
(
k
a
+
ψ
a
)
)
]
4Figure 1
Test network.The investment function is given asG
a
(
ψ
a
)
=
1.5
d
a
(
ψ
a
)
2, where d
a is a parameter of the function. In this example, assume that the largest iteration number n
=
1000. Other parameters are shown in Table 2. Table 3 presents the comparisons of different budgets with OD demand 100-80 (the two numbers denote the demand of OD pairs 1-4 and 1-5).Table 2
Parameters used in Example1.
Parameters
M
α, β
h
V
min
⁡
V
max
⁡
ω
0
c
1
c
2
χ
Values
10.0
0.98
15.0
0.05
0.2
0.8
2.1
0.9
1.0Table 3
Comparison results of different budgets.
Budget
Capacity
Link
1→2
1→3
2→4
2→5
3→4
3→5
150
4.60
2.46
3.12
2.41
1.72
1.26
250
5.73
2.97
4.42
3.28
2.96
0.63
350
6.18
4.45
4.85
0.11
4.03
1.58Tables4 and 5 give the variation of total system cost (TSC) and performance (PER) with different budgets and OD demands. As we know, with the increase of budgets, TSC and PER could be improved by using the bilevel decision methods, which can avoid paradox effectively. This has been clearly reflected in Tables 4 and 5. The result indicates that the larger budget can alleviate traffic congestion and improve the performance efficiently. In addition, a positive fact is that the large OD demand will deteriorate the traffic.Table 4
TSC of the network with different OD demands and budgets.
Budget
TSC
OD
100-20
100-40
100-60
100-80
100-100
150
432.44
584.10
865.89
1213.67
1853.30
250
431.25
579.45
793.35
1159.37
1636.84
350
410.91
560.11
743.75
1112.40
1509.32Table 5
PER of the network with different OD demands and budgets.
Budget
Performance
OD
100-20
100-40
100-60
100-80
100-100
150
0.3992
0.2799
0.1795
0.1272
0.0798
250
0.4188
0.2837
0.1969
0.1356
0.0954
350
0.4447
0.3289
0.2265
0.1446
0.1057To illustrate the efficiency of the solution algorithm further, a convergence test is given in the numerical example. Figure2 shows the convergence of PSO in the case of budget 350 and OD demand 100-20. The result indicates that the algorithm can converge to a steady state after 30 steps.Figure 2
Illustration of the convergences for the algorithm.Example 2 (an extended example considering network topologies).
The structure properties on traffic networks have attracted a tremendous amount of recent interest which shows different network structures have important effects on their performance. It has been known well that there are three typical structures in traffic networks: random graph (RG), small-world network (SW), and regular lattice (RL). We start by constructing networks according to regular ER [20] and WS [21] algorithms. It has been demonstrated that SW networks have both a small value of average shortest path, like RG, and a high clustering coefficient, like RL. Such a definition corresponds to networks having a high value of global efficiency and a high value of local efficiency, that is, to networks extremely efficient in exchanging information both at a global and at a local scale [22].
In this example, to investigate the effects of topologies on NDP, the network design decisions for different network structures with the same nodes and edges are given. Three typical network topologies are showed in Figure3. These networks are generated according to the procedure in [21], where self-links and repeated links are forbidden. Particularly, the SW network is formed by a RL rewired with probability 0.1. All topologies are set to have the same average degree 〈
k
′
〉
≈
4 and 20 nodes. Other parameters are equal to that in Example 1.Figure 3
Three different network topologies.The number of the brackets represents the initial performance before the network design. Table6 provides the optimization results for three typical networks. From the table, we can see that PER of SW network is the largest, but RL is the smallest one. The result can be explained easily. The SW network has the small average shortest path which decreases the distance between two arbitrary nodes. Therefore it will be an efficient network to improve the performance of traffic network. But for the RL network, the larger average shortest path increases the distance between two arbitrary nodes, which reduces the network performance. Therefore, the result is in accordance with the prediction of “structure-determinative-function.”Table 6
The optimization results for different network topologies.
Budget
Topology
SW
ER
RL
200
0.5483
0.5228
0.4604
250
0.5486
0.5231
0.4650
300
0.5486
0.5234
0.4659
350
0.5487
0.5238
0.4666
400
0.5488
0.5241
0.4667


## 5. Conclusion

The transportation network performance is an important indicator to evaluate its reliability. In order to improve the network vulnerability, the performance should be considered in network design decisions. This paper studies a new form of transportation network design problem by optimizing the network performance, and a bilevel programming model is proposed to describe this problem. In the model, the upper level is to optimize the system performance within limited budgets, while the lower level is user equilibrium assignment problem. Finally, numerical examples show that, by redesigning the network, the performance (the total system cost) will increase (reduce) greatly. In addition, the network structure has profound effects on its performance. Compared with the other two topologies, the form of small-world network is the best one.In this paper, it is assumed that the OD matrix is fixed. In reality, OD demand would fluctuate every day, even every hour. Therefore it would be interesting to examine the dynamic OD demand in network design problem further.



---

*Source: 490483-2014-01-21.xml*