# Evacuation Network Optimization Model with Lane-Based Reversal and Routing

Authors: Xing Zhao; Zhao-yan Feng; Yan Li; Antoine Bernard
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

Sometimes, the evacuation measure may seem to be the best choice as an emergency response. To enable an efficiency evacuation, a network optimization model which integrates lane-based reversal design and routing with intersection crossing conflict elimination for evacuation is constructed. The proposed bilevel model minimizes the total evacuation time to leave the evacuation zone. A tabu search algorithm is applied to find an optimal lane reversal plan in the upper-level. The lower-level utilizes a simulated annealing algorithm to get two types of “a single arc for an intersection approach” and “multiple arcs for an intersection approach” lane-based route plans with intersection crossing conflict elimination. An experiment of a nine-intersection evacuation zone illustrates the validity of the model and the algorithm. A field case with network topology of Jianye District around the Nanjing Olympics Sports Center is studied to show the applicability of this algorithm.


---

## Body

## 1. Introduction

Sometimes, evacuation may seem to be the best choice as an emergency response [1]. In evacuation situations, people in danger zones need to escape to security zones, which will cause a rapid traffic increase in local region. Unfortunately, disasters often inflict severe damage on road network. Thus, it would consequently lead to traffic jams, especially if the traffic is already saturated for the everyday demand; the evacuation delay could be serious. Therefore, to achieve an efficient evacuation, the reallocation of traffic capacities and route planning on the evacuation network have major importance for transportation system planners [2].Evacuation modeling has been dealt with in literatures before. Problems such as shelter location [3, 4], evacuation management [5, 6], relief routing [7], and evacuee behavior [8, 9] are being given increased attention over the last decade. For advance-notice emergencies, hurricane, and flood, for instance, effective management strategies would improve the performance of urban evacuation. Liu [10] concluded a control framework including strategies of staged evacuation, lane reversal, signal time planning, and evacuation routing for traffic management under emergency evacuation. The techniques that are currently employed for management planning could be broadly categorized into optimization or simulation methods.Evacuation routing is a typical method to utilize limited capacity of network more rationally. Network flow models, for example, maximum dynamic flows, minimum cost flow, earliest arrival flows, quickest paths, and flows are commonly used to describe evacuation routing problems. Dunn and Newton [11] proposed a maximum flows approach with the objective of moving the most evacuation demands from danger zone to safety region within a network capacity; Yamada [12] performed traffic assignment according to the minimal cost flow problem, to generate the shortest evacuation plan in which the total distance from all evacuees to all shelters is minimized. Baumann and Skutella [13] presented an approximation method to send the maximum amount of flow to the sink for every time period in the considered time horizon [14]. To identify optimal evacuation routes, Campos et al. [15] presented a k-shortest path method to find an individual path with the greatest sum of the capacity/time ratios. By contrast, heuristic approaches were more developed especially for time-expanded network. The capacity constrained route planner (CCRP) [16, 17], a well-known heuristic approach, is useful for medium-sized networks; a scalable heuristic by reusing shortest routes based on bottleneck saturation shows a 95% reduction in computational time with small degradation of solution quality [18]; an evacuation scheduling algorithm (ESA) which is based on the shortest path algorithm for path generation and a greedy algorithm for flow generation could expedite the solution process [5].However, most of these network flow models did not take into account that vehicles have to move lane-based. Cova and Johnson [19] put forward a notion of lane-based evacuation routing and proposed an augmented network flow model that minimized the total travel distance. Their lane-based model was applied to build evacuation network in multiple researches [20–23]. Besides, traffic delays caused by conflicts at intersections were taken into consideration in research of Cova and Johnson [19], so they further established constraints of preventing intersection crossing conflicts and bounding the number of merging-conflicts. Therefore their lane-based minimal cost flow problem is extended by additional integer variables and constraints. More recently, Liu and Luo [24] formulated a model to determine which intersections should be signalized and which should have uninterrupted flow strategies, applied their model to a 26 node network, and achieved up to 39% improvement in total evacuation time over an existing plan. Jahangiri et al. [25] developed a bilevel model with the objective of minimizing evacuees’ total travel time to assess the effects of intersection crossing elimination during evacuations. In the aspect of algorithm, Cova and Johnson [19] used the network simplex method under the assumption that the travel time of each link was constant. Relaxation-based method is repeatedly demonstrated to be effective and efficient in evacuation planning with conflicts constraints [1, 20]; genetic algorithm and simulate annealing heuristic were used to solve such problem as well [24, 25].Lane reversal has been discussed as a widely used strategy for evacuation by increasing the outbound evacuation route capacity. Effectiveness of implementing lane reversal in enhancing evacuation efficiency has been certified in many studies. Lim and Wolshon [26] evaluated various kinds of design schemes of entrances and exits for reverse lanes by means of CORSIM. Kwon and Pitt [27] applied DYNASMART-P to test Minneapolis evacuation plan; Williams et al. [28] used CORSIM simulation models and numerical analysis to assess the adequacy of the lane reversal plan. Aiming at optimizing evacuation network with the strategy of lane reversal, Afandizadeh et al. [29] formulated evacuation network optimization models with lane reversal based on the user equilibrium or stochastic user equilibrium traffic assignment principle. Hua et al. [30] presented an integrated lane reversal strategy for uncertain evacuation demand to improve the efficiency of car-based and transit-based evacuation needs. In terms of algorithm, a lane reversal problem with single source and single sink is polynomially solvable. More analytical solutions and applications of lane reversal were investigated by Pyakurel and Dhamala [31]. However, a multiple source and sink problem becomes strongly NP-hard [32]. Thus, even simple cases of the problem are hard to solve and researchers have to resort to heuristic [33]. Afandizadeh et al. [29] presented a simulated annealing algorithm which is also a metaheuristic technique. Tabu-based heuristic approach and genetic algorithm are popular methods to solve the lane-based problem, especially for the lane-based capacity reversal problem [20, 21, 30].As Xie and Turnquist [20] pointed out, the integration of lane reversal and crossing conflict elimination has greater potential in optimizing evacuation network than the application of either of them solely; the two strategies were dealt with simultaneously in several evacuation network optimization models [1, 30, 34]. Their model and algorithm solved the integrative strategy effectively. However, lane-based route planning was not implemented at intersections in their model. It is difficult for emergency managers either to precisely predict the evacuating traffic distribution when drivers need to determine turning directions at intersections, or to ensure evacuees to take route choice in accordance with the optimal evacuation route plan adequately.Therefore, the main topic of this paper is reallocating the available capacities of each road section by lane-based reversal and implementing lane-based routing by formulating the unique turning direction of each lane on each intersection approach with crossing conflict elimination. In this premise, the vehicle route choice can be in accordance with the optimal system strictly. The proposed optimization model is a bilevel model to minimize the total evacuation time to leave the danger zone. The upper-level is to find an optimal lane-based reversal plan by a tabu search algorithm; the lower-level is to get two types of lane-based route plans with crossing conflict elimination utilizing a simulated annealing algorithm.The text is organized as follows. Section2 introduces the lane-based evacuation network formulation with crossing conflict elimination. Section 3 provides the evacuation network optimization model that generates lane-based capacity reversal and routing plan with crossing conflicts elimination. Section 4 presents a tabu-based search method and simulated annealing algorithm to solve the evacuation model heuristically. Section 5 demonstrates the application of the proposed models and algorithm to two cases with different network sizes. Finally, conclusions and future work are given in the last section.


## 2. Lane-Based Network Representation

In evacuation models, it is necessary to represent elements on the network with a mathematical graph structure. We assume that all sources and sinks, the expected travel demand of each source to sink, and the road network with available transportation infrastructures are inputs to the evacuation network optimization phase. Specifically, sources correspond to the midpoint of corresponding road sections between two intersections; locations of sinks are known and every sink has enough capacity to hold all evacuees that try to move it there; the expected travel demand of each source is defined and the OD distribution is based on the one-destination evacuation (ODE) feature of evacuation [35]; that is to say, all sinks are assumed to connect to a “supersink” with unlimited capacity as shown in Figure 1.Figure 1
A network with sources and sinks.Figure2(a) illustrates an example which contains an intersection and a road section connected with the intersection. The network contains nodes, m, t, l, j, s, k, q, n, o, i, p, directed arcs (
l
,
t
), (
t
,
m
), (
j
,
s
), (
s
,
k
) which reflect connectivity of both directions of the road section, and directed connectors (
m
,
p
), (
q
,
j
), (
o
,
n
), (
i
,
j
) which indicate the turning directions of arcs on each intersection approach.Figure 2
Illustrations of an intersection and a road section.
(a)
A single arc for each intersection approach
(b)
Multiple arcs for an intersection approachAmong all nodes,s, t are sources that the traffic is assumed to load at onto the evacuation network. Nodes on the intersection approach, m, q, o, i, are defined as intersection entrance nodes and nodes on the intersection departure, j, n, p, as intersection exit nodes. There must be one and only one connector for the intersection entrance nodes, while there can be none to several connectors for the intersection exit nodes. An arc pair is the sequential combination of two consecutive arcs demarcating by the certain source, and a road section can be composed of several arc pairs, such that the road section in Figure 2(a) is composed of the arc pairs [(
l
,
t
)
,
(
t
,
m
)] and [(
j
,
s
)
,
(
s
,
k
)]. The connector is a directed link from an entrance node to an exit node of one intersection. Therefore, the number of connectors of an intersection must be the same as the number of exit nodes of the intersection. What is more, a goal in our evacuation routing is to transform intersections into uninterrupted flow facilities, and, namely, that crossing is prohibited for the connectors of an intersection, for instance, the connectors (
m
,
n
) and (
i
,
j
) in Figure 2(a).In Figure2(a), the circles represent nodes, straight lines with arrows represent directed arcs, and dotted lines with arrows represent directed connectors.Moreover, the network is divided into two types of “a single arc for each intersection approach” (“a single arc” for short) and “multiple arcs for an intersection approach” (“multiple arcs” for short). “A single arc” means that all lanes on an approach form one arc; thus there must be only one entrance node on one approach, just as shown in Figure2(a). However “multiple arcs” refer to the fact that there could be (not must be) more than one arc on an approach with multiple lanes; thus there could be more than one entrance node on one approach, and one scheme of a lane-based routing of “multiple arcs” with crossing conflicts elimination is shown in Figure 2(b).


## 3. Evacuation Network Optimization Model Formulation

The evacuation network optimization model can be stated as a bilevel structure. In the upper-level part, the lane reversal operation with constraints for lane consistency needs to be optimized, while the lower-level part is set to be a lane-based routing model with constraints for crossing conflict elimination.


### 3.1. Notations

Sets
N
A: set of intersection entrance nodes,
N
P: set of intersection exit nodes,
L: set of arcs,
R: set of roadway sections between two adjacent intersections,
E: set of intersection connectors.Parameters
r
j
k
,
l
m: a roadway section composed of arc (j
,
k) and (l
,
m),
n
(
r
j
k
,
l
m
): the total number of lanes of roadway section r
j
k
,
l
m,
t
j
s
0: free-flow travel time on arc (j
,
s),
c
j
s: capacity of arc (j
,
s),
c
j
s
μ: capacity of lane u which is belonging to arc (j
,
s).Variables
t
j
s: travel time on arc (j
,
s),
x
j
s: traffic flow volume of arc (j
,
s),
z
j
k: access direction indicator of arc (j
,
k) (z
j
k
=
0 or 1),
n
j
s: number of lanes of arc (j
,
s),
y
i
j: connectivity indicator of intersection connector from node i to node j (y
i
j
=
0 or 1).


### 3.2. System Objectives

Objectives of the two layers of the model are both to minimize the total evacuation time:(1)
Z
=
M
i
n
i
m
i
z
e
∑
j
∑
s
x
j
s
t
j
s
,
∀
j
,
s
∈
L
.The travel time of arc (j
,
s) adopts Bureau of Public Roads Function which depends on the arc flow volume x
j
s and the capacity of arc (j
,
s)c
j
s, (2)
t
j
s
=
t
j
s
0
1
+
α
x
j
s
c
j
s
β
,
∀
j
,
s
∈
L
c
j
s
=
∑
μ
c
j
s
μ
,
∀
j
,
s
∈
L
,where α and β are constant, and the meanings of other parameters are shown in “Notations.”. Then(3)
Z
=
M
i
n
i
m
i
z
e
∑
j
∑
s
x
j
s
t
j
s
0
1
+
α
x
j
s
∑
μ
c
j
s
μ
β
.


### 3.3. Lane Consistency Constraints

Referring to the lane-based capacity reversibility (LCR) definition introduced by Tuydes and Ziliaskopoulos [36], constraints for the lane reversal operation are as follows: (4a) regulates that numbers of lanes should be the same for consecutive arcs; (4b) and (4c) represent the relationship between numbers of lanes of both directions in a road section. It is obvious that the number of lanes of each direction is a nonnegative integer variable which can take a value between 0 and the total number of lanes of the road section:(4a)
n
j
s
=
n
s
k
=
n
j
k
,
n
l
t
=
n
t
m
=
n
l
m
,
∀
j
,
s
,
s
,
k
,
l
,
t
,
t
,
m
∈
L
,
(4b)
n
j
k
+
n
l
m
=
n
r
j
k
,
l
m
,
∀
j
,
k
,
l
,
m
∈
L
,
∀
r
j
k
,
l
m
∈
R
,
(4c)
n
j
k
,
n
l
m
≥
0
and  integer
,
∀
j
,
k
,
l
,
m
∈
L
,
(4d)
z
j
s
=
0
or
1
,where z
j
k is a decision variable and z
j
k
=
1 indicates that the arc from node j to node k is connected, while z
j
k
=
0 means that the arc is disconnected. n
j
s and z
j
s follow the logical relationship: if n
j
s
>
0, then z
j
s
=
1; if n
j
s
=
0, then z
j
s
=
0.


### 3.4. Lane-Based Routing Constraints

Due to that there must exist one connector for an intersection entrance node, which is expressed as follows:(5a)
∑
n
∈
Γ
m
y
m
n
=
1
,
∀
m
∈
N
A
,
∀
n
∈
N
P
,
∀
m
,
n
∈
E
,
(5b)
x
t
m
=
x
m
n
,
∀
m
∈
N
A
,
∀
n
∈
N
P
,
∀
t
,
m
∈
L
,
∀
m
,
n
∈
E
,where y
i
j is 0-1 binary integer and y
i
j
=
1 indicates that the intersection connector from node i to node j is connected, while y
i
j
=
0 means that the connector is disconnected.


### 3.5. Crossing Conflict Elimination Constraints

According to the relative position of nodes at an intersection with “a single arc” setting, crossing conflict elimination constraints can be expressed in two inequalities as (6) and the first inequality reveals the noncoexistence of straight forward connectors of two adjacent approaches which is depicted in Figure 3(a), while the second inequality indicates the pairwise noncoexistence of left-turn links of two adjacent approaches and straight ahead link of the clockwise approach as shown in Figure 3(b):(6)
y
m
r
+
y
q
p
≤
1
,
y
i
j
+
y
m
r
+
y
o
p
≤
1
,
∀
m
,
r
,
q
,
p
,
i
,
j
,
o
,
p
∈
E
.Figure 3
Potential crossing conflicts for intersection.
(a)
An example of a crossing conflict of type I
(b)
An example of a crossing conflict of type II
(c)
An example of crossing conflicts for multiple arcsWhen there is more than one arc for an intersection approach, in addition to constraints (6), it should also satisfy constraint (7) which shows that any other potential crossing conflicts in Figure 3(c), for example, between connectors (
i
,
m
) and (
p
,
j
), between connectors (
r
,
n
) and (
o
,
j
), or between connectors (
p
,
j
) and (
q
,
m
), are not allowed in an evacuation plan:(7)
y
a
g
+
y
c
h
≤
1
,
y
a
g
+
y
b
f
≤
1
,
y
a
h
+
y
b
g
≤
1
,
∀
a
1
,
g
1
,
c
1
,
h
1
,
b
1
,
f
1
,
a
1
,
h
1
,
b
1
,
g
1
∈
E
.


### 3.6. Traffic Assignment

Lane-based routing takes each lane as an object; as a result, each lane has a unique turning direction without traffic diversion, which enables the proposed model to omit the traffic assignment step.


## 3.1. Notations

Sets
N
A: set of intersection entrance nodes,
N
P: set of intersection exit nodes,
L: set of arcs,
R: set of roadway sections between two adjacent intersections,
E: set of intersection connectors.Parameters
r
j
k
,
l
m: a roadway section composed of arc (j
,
k) and (l
,
m),
n
(
r
j
k
,
l
m
): the total number of lanes of roadway section r
j
k
,
l
m,
t
j
s
0: free-flow travel time on arc (j
,
s),
c
j
s: capacity of arc (j
,
s),
c
j
s
μ: capacity of lane u which is belonging to arc (j
,
s).Variables
t
j
s: travel time on arc (j
,
s),
x
j
s: traffic flow volume of arc (j
,
s),
z
j
k: access direction indicator of arc (j
,
k) (z
j
k
=
0 or 1),
n
j
s: number of lanes of arc (j
,
s),
y
i
j: connectivity indicator of intersection connector from node i to node j (y
i
j
=
0 or 1).


## 3.2. System Objectives

Objectives of the two layers of the model are both to minimize the total evacuation time:(1)
Z
=
M
i
n
i
m
i
z
e
∑
j
∑
s
x
j
s
t
j
s
,
∀
j
,
s
∈
L
.The travel time of arc (j
,
s) adopts Bureau of Public Roads Function which depends on the arc flow volume x
j
s and the capacity of arc (j
,
s)c
j
s, (2)
t
j
s
=
t
j
s
0
1
+
α
x
j
s
c
j
s
β
,
∀
j
,
s
∈
L
c
j
s
=
∑
μ
c
j
s
μ
,
∀
j
,
s
∈
L
,where α and β are constant, and the meanings of other parameters are shown in “Notations.”. Then(3)
Z
=
M
i
n
i
m
i
z
e
∑
j
∑
s
x
j
s
t
j
s
0
1
+
α
x
j
s
∑
μ
c
j
s
μ
β
.


## 3.3. Lane Consistency Constraints

Referring to the lane-based capacity reversibility (LCR) definition introduced by Tuydes and Ziliaskopoulos [36], constraints for the lane reversal operation are as follows: (4a) regulates that numbers of lanes should be the same for consecutive arcs; (4b) and (4c) represent the relationship between numbers of lanes of both directions in a road section. It is obvious that the number of lanes of each direction is a nonnegative integer variable which can take a value between 0 and the total number of lanes of the road section:(4a)
n
j
s
=
n
s
k
=
n
j
k
,
n
l
t
=
n
t
m
=
n
l
m
,
∀
j
,
s
,
s
,
k
,
l
,
t
,
t
,
m
∈
L
,
(4b)
n
j
k
+
n
l
m
=
n
r
j
k
,
l
m
,
∀
j
,
k
,
l
,
m
∈
L
,
∀
r
j
k
,
l
m
∈
R
,
(4c)
n
j
k
,
n
l
m
≥
0
and  integer
,
∀
j
,
k
,
l
,
m
∈
L
,
(4d)
z
j
s
=
0
or
1
,where z
j
k is a decision variable and z
j
k
=
1 indicates that the arc from node j to node k is connected, while z
j
k
=
0 means that the arc is disconnected. n
j
s and z
j
s follow the logical relationship: if n
j
s
>
0, then z
j
s
=
1; if n
j
s
=
0, then z
j
s
=
0.


## 3.4. Lane-Based Routing Constraints

Due to that there must exist one connector for an intersection entrance node, which is expressed as follows:(5a)
∑
n
∈
Γ
m
y
m
n
=
1
,
∀
m
∈
N
A
,
∀
n
∈
N
P
,
∀
m
,
n
∈
E
,
(5b)
x
t
m
=
x
m
n
,
∀
m
∈
N
A
,
∀
n
∈
N
P
,
∀
t
,
m
∈
L
,
∀
m
,
n
∈
E
,where y
i
j is 0-1 binary integer and y
i
j
=
1 indicates that the intersection connector from node i to node j is connected, while y
i
j
=
0 means that the connector is disconnected.


## 3.5. Crossing Conflict Elimination Constraints

According to the relative position of nodes at an intersection with “a single arc” setting, crossing conflict elimination constraints can be expressed in two inequalities as (6) and the first inequality reveals the noncoexistence of straight forward connectors of two adjacent approaches which is depicted in Figure 3(a), while the second inequality indicates the pairwise noncoexistence of left-turn links of two adjacent approaches and straight ahead link of the clockwise approach as shown in Figure 3(b):(6)
y
m
r
+
y
q
p
≤
1
,
y
i
j
+
y
m
r
+
y
o
p
≤
1
,
∀
m
,
r
,
q
,
p
,
i
,
j
,
o
,
p
∈
E
.Figure 3
Potential crossing conflicts for intersection.
(a)
An example of a crossing conflict of type I
(b)
An example of a crossing conflict of type II
(c)
An example of crossing conflicts for multiple arcsWhen there is more than one arc for an intersection approach, in addition to constraints (6), it should also satisfy constraint (7) which shows that any other potential crossing conflicts in Figure 3(c), for example, between connectors (
i
,
m
) and (
p
,
j
), between connectors (
r
,
n
) and (
o
,
j
), or between connectors (
p
,
j
) and (
q
,
m
), are not allowed in an evacuation plan:(7)
y
a
g
+
y
c
h
≤
1
,
y
a
g
+
y
b
f
≤
1
,
y
a
h
+
y
b
g
≤
1
,
∀
a
1
,
g
1
,
c
1
,
h
1
,
b
1
,
f
1
,
a
1
,
h
1
,
b
1
,
g
1
∈
E
.


## 3.6. Traffic Assignment

Lane-based routing takes each lane as an object; as a result, each lane has a unique turning direction without traffic diversion, which enables the proposed model to omit the traffic assignment step.


## 4. Solution Algorithms

For the complexity of the proposed problem, a tabu search and simulated annealing based heuristic algorithm is used to achieve a nearly optimal solution in an appropriate amount of time.


### 4.1. Upper-Level Algorithm

Step 1 (initial solution).
Confirm numbers of lanes of each arc on the initial network. Define tabu tenure and maximum iteration number. Set the number of iterationst
=
0. Create empty lists: search list, tabu list.
Utilize the simulated annealing algorithm of lower-level, determine the connectivity of each connector in the base case, and acquire the total travel timeZ
(
0
) on the initial network.Step 2 (neighborhood search).
Set the number of iterationst
=
t
+
1 and determine the search list. If there exist available capacities for both directions in a road section, calculate the congestion values of both directions g
j
k
=
(
x
j
s
/
c
j
s
)
β
+
1
+
(
x
s
k
/
c
s
k
)
β
+
1 and g
l
m
=
(
x
l
t
/
c
l
t
)
β
+
1
+
(
x
t
m
/
c
t
m
)
β
+
1; if g
j
k
<
g
l
m, add the arc pair (
j
,
k
) into the search list.Step 3 (move).
If the arc pair(
j
,
k
) belongs to the search list but does not belong to the tabu list, one lane is reversed from the arc pair (
j
,
k
) and added to the arc pair (
l
,
m
). Based on the suggested lane reversal schemes, the capacity reallocation of all arcs on the network can be acquired. For evacuation network optimization of “a single arc,” the intersection configuration may have three cases along with lane reversal operation: after lane reversal, if the number of lanes of the arc pair [(
j
,
s
)
,
(
s
,
k
)] n
(
j
,
k
)
=
0, the configurations of the intersections connected to the road section change with decreases of number of arcs; if the number of lanes of the arc pair [(
l
,
t
)
,
(
t
,
m
)], n
(
l
,
m
)
=
1, that is, n
(
l
,
m
)
=
0 before lane reversal, the configurations of the intersections connected to the road section change with increases of the number of arcs; and if n
(
j
,
k
)
≥
1 and n
(
l
,
m
)
>
1, the configurations of the intersections connected to the arc pair do not change.Step 4 (the decision criteria of move).
After the move, compute the optimal lane-based route plan based on the lower-level algorithm under certain lane reversal plan in the iterationt. Record the objective function value as Z
(
t
). If Z
(
t
)
<
Z
(
t
-
1
), the move is accepted, and record the evacuation network w
t; if the objective does not improve while the search list is not empty, conduct the diversification action that the reversing scheme would be modified to be a new one to further evaluate.Step 5 (tabu list).
Put the arc pair(
l
,
m
) that gains a lane into the tabu list to prohibit from reversing the lane on the arc until the number of iterations reaches the predefined tabu tenure.Step 6 (end of program).
If it satisfies stopping rules, the search can be terminated, and the final solution of “a single arc” is recorded asw, while the solution of “multiple arcs” is recorded as W; if the algorithm is not over yet, set t
=
t
+
l, and S
(
t
)
=
V
a
r
i
S
(
t
), return to Step 2, and continue to calculate.Stopping Rules. The tabu search has several termination measures such as tolerable objective function value and maximum computing time limit. In this paper, when the search list is empty and improved searches options such as intensification have been tested to be ineffective in improving the objective function, or iteration number reaches the preset threshold value, the search can be terminated.Diversification Searches. If the search list is not empty, while an aggregate reversing scheme does not improve the objective function, Z
(
t
)
>
Z
(
t
-
1
), the proposed reversing scheme would be modified to be a new one that only contains lane reversals in the search list to improve the objective function; thus the subset of arcs that have negative impact on the objective function is excluded from the new reversing scheme [36].


### 4.2. Lower-Level Algorithm

Step 1.
Determine the initial temperatureT
i
n
i
t
i
a
l, final temperature T
f
i
n
a
l, number of feasible solutions at each iteration M, and cooling schedule.Step 2.
Set the number of iterationst
=
0; define an initial feasible solution X
(
0
) satisfying the lane-based routing constraints and intersection crossing conflict elimination constraints. In the solution, all potential connectors on network are coded with “0” and “1.” Take the intersection as shown in Figure 2(a) as an example, the connectors (
m
,
p
), (
i
,
j
), (
o
,
n
), and (
q
,
j
) are all encoded as 1, while other connectors such as (
o
,
p
) and (
o
,
j
) are encoded as 0. The codes of all connectors form a solution of the lower-level model. Significantly, during coding, all lanes on an approach are regarded as an arc in schemes of “a single arc for each intersection approach” while for “multiple arcs for an intersection approach,” each lane is considered as an arc at the very beginning of each iteration, and then lanes on an approach converging to flow into the same arc are deemed as an arc in the following calculation. Calculate the objective function value Z
(
0
) of X
(
0
), and record X
(
0
) and Z
(
0
) as the current optimal solution X
c and its objective function value Z
c separately.Step 3.
Set the number of iterationst; generate M new feasible solutions X
1
(
t
)
,
X
2
(
t
)
,
…
,
X
M
(
t
) based on movement strategy. The strategy could be described as follows: choose one intersection on the network randomly; sort out any two connectors of the intersection and implement movement. It could be divided into three conditions: Firstly, when codes of two connectors are “1,” change their connecting exit nodes. For instance, if connectors (
m
,
p
) and (
o
,
n
) were selected, codes for (
m
,
p
) and (
o
,
n
) would become “0,” while (
m
,
n
) and (
o
,
p
) would go into “1” in the new solution after movement. Secondly, when one code of two connectors is “1” and the other is “0,” if two connectors origin from the same entrance node, interchange the two codes; otherwise, reselect two connectors randomly. Thirdly, when codes of two connectors are “0,” reselect two connectors randomly. Besides, check whether the intersection after performing movement still meets the crossing conflict elimination constraints; if satisfied, accept the solution as a new feasible solution; or else, give up the solution. Calculate the objective function value of each feasible solution X
1
(
t
)
,
X
2
(
t
)
,
…
,
X
M
(
t
). Take the solution with the smallest value as the new solution of tth iteration; record it as X
(
t
) and its objective function value as Z
(
t
).Step 4.
CalculateΔ, the difference between the new and current optimal objective function values. If Δ
≤
0, the new solution is accepted; otherwise, the new solution can be accepted with the probability of P
c
=
exp
⁡
(
Z
c
-
Z
t
)
/
T
e
m
p
e
r
a
t
u
r
e; specifically, generate a random number ξ in [
0,1
]; if ξ
≤
P
c, accept the new solution Z
(
t
).Step 5.
If the algorithm is not over yet, sett
=
t
+
l, decrease the temperature according to the cooling schedule, return to Step 3, and continue to calculate.Stopping Rules. (
1
) If the improvement in the objective function was negligible and the acceptance of worse solutions was less than 5 percent in defined consecutive iterations or (
2
)
T
e
m
p
e
r
a
t
u
r
e
=
T
f
i
n
a
l the search can be terminated.


## 4.1. Upper-Level Algorithm

Step 1 (initial solution).
Confirm numbers of lanes of each arc on the initial network. Define tabu tenure and maximum iteration number. Set the number of iterationst
=
0. Create empty lists: search list, tabu list.
Utilize the simulated annealing algorithm of lower-level, determine the connectivity of each connector in the base case, and acquire the total travel timeZ
(
0
) on the initial network.Step 2 (neighborhood search).
Set the number of iterationst
=
t
+
1 and determine the search list. If there exist available capacities for both directions in a road section, calculate the congestion values of both directions g
j
k
=
(
x
j
s
/
c
j
s
)
β
+
1
+
(
x
s
k
/
c
s
k
)
β
+
1 and g
l
m
=
(
x
l
t
/
c
l
t
)
β
+
1
+
(
x
t
m
/
c
t
m
)
β
+
1; if g
j
k
<
g
l
m, add the arc pair (
j
,
k
) into the search list.Step 3 (move).
If the arc pair(
j
,
k
) belongs to the search list but does not belong to the tabu list, one lane is reversed from the arc pair (
j
,
k
) and added to the arc pair (
l
,
m
). Based on the suggested lane reversal schemes, the capacity reallocation of all arcs on the network can be acquired. For evacuation network optimization of “a single arc,” the intersection configuration may have three cases along with lane reversal operation: after lane reversal, if the number of lanes of the arc pair [(
j
,
s
)
,
(
s
,
k
)] n
(
j
,
k
)
=
0, the configurations of the intersections connected to the road section change with decreases of number of arcs; if the number of lanes of the arc pair [(
l
,
t
)
,
(
t
,
m
)], n
(
l
,
m
)
=
1, that is, n
(
l
,
m
)
=
0 before lane reversal, the configurations of the intersections connected to the road section change with increases of the number of arcs; and if n
(
j
,
k
)
≥
1 and n
(
l
,
m
)
>
1, the configurations of the intersections connected to the arc pair do not change.Step 4 (the decision criteria of move).
After the move, compute the optimal lane-based route plan based on the lower-level algorithm under certain lane reversal plan in the iterationt. Record the objective function value as Z
(
t
). If Z
(
t
)
<
Z
(
t
-
1
), the move is accepted, and record the evacuation network w
t; if the objective does not improve while the search list is not empty, conduct the diversification action that the reversing scheme would be modified to be a new one to further evaluate.Step 5 (tabu list).
Put the arc pair(
l
,
m
) that gains a lane into the tabu list to prohibit from reversing the lane on the arc until the number of iterations reaches the predefined tabu tenure.Step 6 (end of program).
If it satisfies stopping rules, the search can be terminated, and the final solution of “a single arc” is recorded asw, while the solution of “multiple arcs” is recorded as W; if the algorithm is not over yet, set t
=
t
+
l, and S
(
t
)
=
V
a
r
i
S
(
t
), return to Step 2, and continue to calculate.Stopping Rules. The tabu search has several termination measures such as tolerable objective function value and maximum computing time limit. In this paper, when the search list is empty and improved searches options such as intensification have been tested to be ineffective in improving the objective function, or iteration number reaches the preset threshold value, the search can be terminated.Diversification Searches. If the search list is not empty, while an aggregate reversing scheme does not improve the objective function, Z
(
t
)
>
Z
(
t
-
1
), the proposed reversing scheme would be modified to be a new one that only contains lane reversals in the search list to improve the objective function; thus the subset of arcs that have negative impact on the objective function is excluded from the new reversing scheme [36].


## 4.2. Lower-Level Algorithm

Step 1.
Determine the initial temperatureT
i
n
i
t
i
a
l, final temperature T
f
i
n
a
l, number of feasible solutions at each iteration M, and cooling schedule.Step 2.
Set the number of iterationst
=
0; define an initial feasible solution X
(
0
) satisfying the lane-based routing constraints and intersection crossing conflict elimination constraints. In the solution, all potential connectors on network are coded with “0” and “1.” Take the intersection as shown in Figure 2(a) as an example, the connectors (
m
,
p
), (
i
,
j
), (
o
,
n
), and (
q
,
j
) are all encoded as 1, while other connectors such as (
o
,
p
) and (
o
,
j
) are encoded as 0. The codes of all connectors form a solution of the lower-level model. Significantly, during coding, all lanes on an approach are regarded as an arc in schemes of “a single arc for each intersection approach” while for “multiple arcs for an intersection approach,” each lane is considered as an arc at the very beginning of each iteration, and then lanes on an approach converging to flow into the same arc are deemed as an arc in the following calculation. Calculate the objective function value Z
(
0
) of X
(
0
), and record X
(
0
) and Z
(
0
) as the current optimal solution X
c and its objective function value Z
c separately.Step 3.
Set the number of iterationst; generate M new feasible solutions X
1
(
t
)
,
X
2
(
t
)
,
…
,
X
M
(
t
) based on movement strategy. The strategy could be described as follows: choose one intersection on the network randomly; sort out any two connectors of the intersection and implement movement. It could be divided into three conditions: Firstly, when codes of two connectors are “1,” change their connecting exit nodes. For instance, if connectors (
m
,
p
) and (
o
,
n
) were selected, codes for (
m
,
p
) and (
o
,
n
) would become “0,” while (
m
,
n
) and (
o
,
p
) would go into “1” in the new solution after movement. Secondly, when one code of two connectors is “1” and the other is “0,” if two connectors origin from the same entrance node, interchange the two codes; otherwise, reselect two connectors randomly. Thirdly, when codes of two connectors are “0,” reselect two connectors randomly. Besides, check whether the intersection after performing movement still meets the crossing conflict elimination constraints; if satisfied, accept the solution as a new feasible solution; or else, give up the solution. Calculate the objective function value of each feasible solution X
1
(
t
)
,
X
2
(
t
)
,
…
,
X
M
(
t
). Take the solution with the smallest value as the new solution of tth iteration; record it as X
(
t
) and its objective function value as Z
(
t
).Step 4.
CalculateΔ, the difference between the new and current optimal objective function values. If Δ
≤
0, the new solution is accepted; otherwise, the new solution can be accepted with the probability of P
c
=
exp
⁡
(
Z
c
-
Z
t
)
/
T
e
m
p
e
r
a
t
u
r
e; specifically, generate a random number ξ in [
0,1
]; if ξ
≤
P
c, accept the new solution Z
(
t
).Step 5.
If the algorithm is not over yet, sett
=
t
+
l, decrease the temperature according to the cooling schedule, return to Step 3, and continue to calculate.Stopping Rules. (
1
) If the improvement in the objective function was negligible and the acceptance of worse solutions was less than 5 percent in defined consecutive iterations or (
2
)
T
e
m
p
e
r
a
t
u
r
e
=
T
f
i
n
a
l the search can be terminated.


## 5. Case Study

To verify the effectiveness and applicability of the proposed model and algorithm, two cases are illustrated in this section.


### 5.1. Test 1

An experiment of nine-intersection evacuation zone is carried out based on the known distribution of parking lots, initial road network, and traffic data.In this test, an emergency event occurs and vehicles need to evacuate from the danger zone as shown in Figure4. During the evacuation process, it allows traffic to flow out only in this area. All streets on the network have two lanes, each lane has a unit travel distance (
t
j
s
0
=
1
), and capacity of each lane is equal to 600 veh/lane according to the recommended urban road traffic capacity of China (c
j
s = 600 veh/lane). There are four parking lots with 1200 parking spaces each in the area. Figure 4 depicts the initial network with circles and lines; the straight lines with arrow represent directed arcs; the small, medium, and big circles represent sources (nodes 1–36), sinks (nodes 37–42), and intersections (nodes 43–51), respectively; and the black rectangles represent parking lots. The initial network has 108 nodes including 36 sources and 6 sinks, 72 arcs, 74 connectors, and 76 conflicts. The nodes in each intersection are not drawn up in the figure.Figure 4
The initial network.As mentioned, except the sources 1, 17, 18, and 26, the flow volume loading at each source is the existing traffic on the arc, which is also called background traffic. In this paper, three assumptions on background traffic are made, containing ① 0, ② 300, ③ 600 for each source. Therefore, except the sources 1, 17, 18, and 26, the evacuation traffic demands of the rest sources are all equal to ① 0, ② 300, ③ 600 under the corresponding three assumptions, respectively; for sources 1, 17, 18, and 26, the source flow is the sum of the background traffic on the arc and the vehicles in corresponding parking lot that are all equal to ① 1200, ② 1500, ③ 1800 under the corresponding three assumptions, respectively, and it is assumed that these evacuation demands load onto their sources simultaneously.The algorithm presented above is implemented in Matlab and run on a desktop personal computer with CPU of Intel Core™ 2 2.2 GHz and RAM of 2 GB. To implement the algorithm for this specific problem, the parameters were determined as follows. The tabu tenure and the maximum iteration number are confirmed based on network size; the annealing schedule trial and error were used to determine the initial temperature which lead to improvements in the objective function, the final temperature that was small enough to avoid accepting worse solutions and the number of feasible solutions at each iteration. In addition, referring to existing researches, the typical geometric temperature reduction method was adopted to reduce the temperature, and the coefficient of reduction was 0.9 [25]. Consequently, for this case, algorithmic parameters in the upper-level include tabu tenure = 3 and the maximum iteration number = 30, while parameters in the lower-level include the initial temperature T
i
n
i
t
i
a
l
=
10, final temperature T
f
i
n
a
l
=
1, number of iterations at each temperature M
=
3, and cooling schedule T
k
=
0.9
·
T
s.The final solutions of “multiple arcs” and objective function values under assumptions of ① and ② are as shown in Figures5(a) and 5(b). The optimal evacuation plans of “a single arc” and “multiple arcs” under assumption of ③ are presented in Figures 5(c) and 5(d). The computational time required to find the corresponding optimal solutions are about 66, 129, 94, and 135 seconds, respectively.Figure 5
Schemes of evacuation network optimization of test 1.
(a)
SolutionW under ① (Z
=
34.3657)
(b)
SolutionW under ② (Z
=
199.784)
(c)
Solutionw under ③ (Z
=
2471.28)
(d)
SolutionW under ③ (Z
=
2260.26)In general, the optimal lane-based reversal and routing plans with crossing conflict elimination are achieved in the above four solutions.By comparing Figures5(a), 5(b), and 5(d), it can be found that when the background traffic of each arc is zero, several lanes are reversed in the optimal solution of the proposed model; when the background traffic of each arc is 300 or 600, most lanes are reversed and form one arc for an intersection approach in the optimal solution. Along with the increase of background traffic, the objective function value of the optimal solution gets larger and larger.Aiming at the performance of the two optimal solutions of “a single arc” and “multiple arcs” under assumption of ③, the latter one costs more computing time (30.37%) but gets a better result with the total evacuation time reduced by 9.34%. It means that an evacuation network with better evacuation efficiency may be acquired by solution of “multiple arcs” than “a single arc”; however, the plan of “multiple arcs” costs more computing time than “a single arc,” and thus, the emergency managers must decide which is appropriate with consideration of both evacuation efficiency and solving time in current situation.


### 5.2. Test 2

For the large-scale experiment, instance developed from the Jianye district of Nanjing city which has a total area of 80 square kilometers is used [37]. Nanjing Olympic Sports Center in this district, which can hold 87,000 people, often undertakes large-scale activities, such as the opening and closing ceremonies of the 10th National Games of China and the second Youth Olympic Games and New Year’s concert. Assume that a terrorist incident is forecasted in this stadium during an attractive activity with a full attendance, and short notice time is available. Three shelters from west to east called Baochuanchang Relic Site, Yueguang Square, and South Lake, separately, are selected. All audiences are required to evacuate.An evacuation network which is composed of major arterials in Jianye district is extracted from the whole road network. The candidate roads, sources, and sinks are shown in Figure6. The emergency incident location (Nanjing Olympic Sports Center) is denoted by a red star; sources (exits for vehicles of the Nanjing Olympic Sports Center) and shelters are represented by gray triangles and green circles, respectively. The evacuation network contains 26 evacuation origins, 3 evacuation destinations, 62 intersections, and 99 road sections. The evacuation demand is set as the number of private cars in parking lots of the stadium, and since that there is a period of time from learning evacuation notice to beginning evacuating for audiences, the vehicles traveling on roads could be induced to leave the area and do not contribute to traffic demand. The total demand is 16200 vehicles for this network. Other properties related to roadway section length and numbers of lanes are already obtained by survey.Figure 6
Candidate evacuation network with sources and sinks of Jianye district.Specific information of each roadways is listed in Table1.Table 1
Basic information of roadways.
Roadway
Length (m)
Number of lanes
Aoti
3100
6
Mengdu
3550
8
Xinglong
3670
4
Yingtian
3800
8
Jiqingmen
4000
6
Hudong
1000
4
Shuiximen
410
8
Hanzhongmen
1820
4
Qingliangmen
1400
4
Xiangjiang
980
4
Longyuannan
790
4
Caochangmen
1700
6
Yangzijiang
6050
8
Leshan
2000
4
Yanshan
4020
6
Jiangdong
6600
8
Lushan
3830
6
Huangshan
3900
6
Taishan
4000
4
Qingjiang
1900
6
Lijiang
930
4
Zhanjiang
2220
4
Longyuanzhong
800
2
Longyuandong
750
2In this part, two groups of experiments of “a single arc” and “multiple arcs” are performed and compared. Due to the large network size, original objective function values reach seven to eight orders of magnitudes, which causes difficulty to the calculation of cooling process. Consequently, average evacuation time per vehicleZ
′
=
∑
j
∑
s
x
j
s
t
j
s
0
1
+
α
x
j
s
/
∑
μ
c
j
s
μ
β
/
∑
s
f
s is proposed to substitute the original objective function in this case. Based on the same method in case 1, we set the values of the above-mentioned parameters as tabu tenure = 7 and the maximum iteration number = 1000, while parameters in the lower-level include the initial temperature T
i
n
i
t
i
a
l = 50, final temperature T
f
i
n
a
l
=
0.3, number of iterations at each temperature M
=
5, and cooling schedule T
k
=
0.9
·
T
s. The CPU computation times for obtaining the optimal solutions of this case are 0.96 and 1.33 hours, respectively.The lane-based reversal and routing plans that were obtained under settings of “a single arc” and “multiple arcs” could be shown in Figures7(a) and 7(b). Black circles with numbers and dotted lines represent intersections with turning prohibitions, while bold arrowed solid lines represent directed arcs for evacuation. When some roadway sections contain two arcs, the number besides the arc in the figure represents number of lanes of the arc. For instance, the roadway section (2, 8) in Figure 7(a) contains two arcs, of which one arc has three lanes and the other has one lane. For roadway sections with more than two arcs such as (9, 10) in Figure 7(b), the middle arc is not labeled and its number of lanes can be obtained combining Table 1. For example, the road section (9, 10) contains three arcs with four lanes, one lane, and three lanes, separately. In particular, the road section (8, 9) contains four arcs with two lanes each.Figure 7
Schemes of evacuation network optimization in the Jianye district.
(a)
Solution of “a single arc”
(b)
Solution of “multiple arcs”The total travel times of the evacuation flows in Figures7(a) and 7(b) are 10829099 veh∗s and 10156590 veh∗s, respectively; accordingly, the average travel times of the evacuation demand are 668.5 s/veh and 626.95 s/veh. In addition, there are 52, 70 road sections (52.53% and 70.71% of all road sections on the network), and 42, 53 intersections (67.74% and 85.48% of all intersections) are selected to be reorganized and controlled for evacuation, separately.Contrasting Figures7(a) and 7(b), it can be found that between the schemes of evacuation network optimization of “a single arc” and “multiple arcs,” the latter one costs more computing time (27.51%) but gets a better result with the total evacuation time reduced by 6.62%. Besides, more road sections and intersections (25.71% and 20.75%) are reorganized and controlled in the plan of “multiple arcs.” In solution of “a single arc,” most selected road sections are reversed to be one-way and all lanes for an intersection approach form one arc, while in solution of “multiple arcs,” almost all selected road sections except (2, 3) are one-way and 18 road sections (25.71% of selected road sections) have more than one arc on one approach. In general, setting of “multiple arcs” would increase the complexities of solving and traffic organizing but improve the efficiency of evacuation.


## 5.1. Test 1

An experiment of nine-intersection evacuation zone is carried out based on the known distribution of parking lots, initial road network, and traffic data.In this test, an emergency event occurs and vehicles need to evacuate from the danger zone as shown in Figure4. During the evacuation process, it allows traffic to flow out only in this area. All streets on the network have two lanes, each lane has a unit travel distance (
t
j
s
0
=
1
), and capacity of each lane is equal to 600 veh/lane according to the recommended urban road traffic capacity of China (c
j
s = 600 veh/lane). There are four parking lots with 1200 parking spaces each in the area. Figure 4 depicts the initial network with circles and lines; the straight lines with arrow represent directed arcs; the small, medium, and big circles represent sources (nodes 1–36), sinks (nodes 37–42), and intersections (nodes 43–51), respectively; and the black rectangles represent parking lots. The initial network has 108 nodes including 36 sources and 6 sinks, 72 arcs, 74 connectors, and 76 conflicts. The nodes in each intersection are not drawn up in the figure.Figure 4
The initial network.As mentioned, except the sources 1, 17, 18, and 26, the flow volume loading at each source is the existing traffic on the arc, which is also called background traffic. In this paper, three assumptions on background traffic are made, containing ① 0, ② 300, ③ 600 for each source. Therefore, except the sources 1, 17, 18, and 26, the evacuation traffic demands of the rest sources are all equal to ① 0, ② 300, ③ 600 under the corresponding three assumptions, respectively; for sources 1, 17, 18, and 26, the source flow is the sum of the background traffic on the arc and the vehicles in corresponding parking lot that are all equal to ① 1200, ② 1500, ③ 1800 under the corresponding three assumptions, respectively, and it is assumed that these evacuation demands load onto their sources simultaneously.The algorithm presented above is implemented in Matlab and run on a desktop personal computer with CPU of Intel Core™ 2 2.2 GHz and RAM of 2 GB. To implement the algorithm for this specific problem, the parameters were determined as follows. The tabu tenure and the maximum iteration number are confirmed based on network size; the annealing schedule trial and error were used to determine the initial temperature which lead to improvements in the objective function, the final temperature that was small enough to avoid accepting worse solutions and the number of feasible solutions at each iteration. In addition, referring to existing researches, the typical geometric temperature reduction method was adopted to reduce the temperature, and the coefficient of reduction was 0.9 [25]. Consequently, for this case, algorithmic parameters in the upper-level include tabu tenure = 3 and the maximum iteration number = 30, while parameters in the lower-level include the initial temperature T
i
n
i
t
i
a
l
=
10, final temperature T
f
i
n
a
l
=
1, number of iterations at each temperature M
=
3, and cooling schedule T
k
=
0.9
·
T
s.The final solutions of “multiple arcs” and objective function values under assumptions of ① and ② are as shown in Figures5(a) and 5(b). The optimal evacuation plans of “a single arc” and “multiple arcs” under assumption of ③ are presented in Figures 5(c) and 5(d). The computational time required to find the corresponding optimal solutions are about 66, 129, 94, and 135 seconds, respectively.Figure 5
Schemes of evacuation network optimization of test 1.
(a)
SolutionW under ① (Z
=
34.3657)
(b)
SolutionW under ② (Z
=
199.784)
(c)
Solutionw under ③ (Z
=
2471.28)
(d)
SolutionW under ③ (Z
=
2260.26)In general, the optimal lane-based reversal and routing plans with crossing conflict elimination are achieved in the above four solutions.By comparing Figures5(a), 5(b), and 5(d), it can be found that when the background traffic of each arc is zero, several lanes are reversed in the optimal solution of the proposed model; when the background traffic of each arc is 300 or 600, most lanes are reversed and form one arc for an intersection approach in the optimal solution. Along with the increase of background traffic, the objective function value of the optimal solution gets larger and larger.Aiming at the performance of the two optimal solutions of “a single arc” and “multiple arcs” under assumption of ③, the latter one costs more computing time (30.37%) but gets a better result with the total evacuation time reduced by 9.34%. It means that an evacuation network with better evacuation efficiency may be acquired by solution of “multiple arcs” than “a single arc”; however, the plan of “multiple arcs” costs more computing time than “a single arc,” and thus, the emergency managers must decide which is appropriate with consideration of both evacuation efficiency and solving time in current situation.


## 5.2. Test 2

For the large-scale experiment, instance developed from the Jianye district of Nanjing city which has a total area of 80 square kilometers is used [37]. Nanjing Olympic Sports Center in this district, which can hold 87,000 people, often undertakes large-scale activities, such as the opening and closing ceremonies of the 10th National Games of China and the second Youth Olympic Games and New Year’s concert. Assume that a terrorist incident is forecasted in this stadium during an attractive activity with a full attendance, and short notice time is available. Three shelters from west to east called Baochuanchang Relic Site, Yueguang Square, and South Lake, separately, are selected. All audiences are required to evacuate.An evacuation network which is composed of major arterials in Jianye district is extracted from the whole road network. The candidate roads, sources, and sinks are shown in Figure6. The emergency incident location (Nanjing Olympic Sports Center) is denoted by a red star; sources (exits for vehicles of the Nanjing Olympic Sports Center) and shelters are represented by gray triangles and green circles, respectively. The evacuation network contains 26 evacuation origins, 3 evacuation destinations, 62 intersections, and 99 road sections. The evacuation demand is set as the number of private cars in parking lots of the stadium, and since that there is a period of time from learning evacuation notice to beginning evacuating for audiences, the vehicles traveling on roads could be induced to leave the area and do not contribute to traffic demand. The total demand is 16200 vehicles for this network. Other properties related to roadway section length and numbers of lanes are already obtained by survey.Figure 6
Candidate evacuation network with sources and sinks of Jianye district.Specific information of each roadways is listed in Table1.Table 1
Basic information of roadways.
Roadway
Length (m)
Number of lanes
Aoti
3100
6
Mengdu
3550
8
Xinglong
3670
4
Yingtian
3800
8
Jiqingmen
4000
6
Hudong
1000
4
Shuiximen
410
8
Hanzhongmen
1820
4
Qingliangmen
1400
4
Xiangjiang
980
4
Longyuannan
790
4
Caochangmen
1700
6
Yangzijiang
6050
8
Leshan
2000
4
Yanshan
4020
6
Jiangdong
6600
8
Lushan
3830
6
Huangshan
3900
6
Taishan
4000
4
Qingjiang
1900
6
Lijiang
930
4
Zhanjiang
2220
4
Longyuanzhong
800
2
Longyuandong
750
2In this part, two groups of experiments of “a single arc” and “multiple arcs” are performed and compared. Due to the large network size, original objective function values reach seven to eight orders of magnitudes, which causes difficulty to the calculation of cooling process. Consequently, average evacuation time per vehicleZ
′
=
∑
j
∑
s
x
j
s
t
j
s
0
1
+
α
x
j
s
/
∑
μ
c
j
s
μ
β
/
∑
s
f
s is proposed to substitute the original objective function in this case. Based on the same method in case 1, we set the values of the above-mentioned parameters as tabu tenure = 7 and the maximum iteration number = 1000, while parameters in the lower-level include the initial temperature T
i
n
i
t
i
a
l = 50, final temperature T
f
i
n
a
l
=
0.3, number of iterations at each temperature M
=
5, and cooling schedule T
k
=
0.9
·
T
s. The CPU computation times for obtaining the optimal solutions of this case are 0.96 and 1.33 hours, respectively.The lane-based reversal and routing plans that were obtained under settings of “a single arc” and “multiple arcs” could be shown in Figures7(a) and 7(b). Black circles with numbers and dotted lines represent intersections with turning prohibitions, while bold arrowed solid lines represent directed arcs for evacuation. When some roadway sections contain two arcs, the number besides the arc in the figure represents number of lanes of the arc. For instance, the roadway section (2, 8) in Figure 7(a) contains two arcs, of which one arc has three lanes and the other has one lane. For roadway sections with more than two arcs such as (9, 10) in Figure 7(b), the middle arc is not labeled and its number of lanes can be obtained combining Table 1. For example, the road section (9, 10) contains three arcs with four lanes, one lane, and three lanes, separately. In particular, the road section (8, 9) contains four arcs with two lanes each.Figure 7
Schemes of evacuation network optimization in the Jianye district.
(a)
Solution of “a single arc”
(b)
Solution of “multiple arcs”The total travel times of the evacuation flows in Figures7(a) and 7(b) are 10829099 veh∗s and 10156590 veh∗s, respectively; accordingly, the average travel times of the evacuation demand are 668.5 s/veh and 626.95 s/veh. In addition, there are 52, 70 road sections (52.53% and 70.71% of all road sections on the network), and 42, 53 intersections (67.74% and 85.48% of all intersections) are selected to be reorganized and controlled for evacuation, separately.Contrasting Figures7(a) and 7(b), it can be found that between the schemes of evacuation network optimization of “a single arc” and “multiple arcs,” the latter one costs more computing time (27.51%) but gets a better result with the total evacuation time reduced by 6.62%. Besides, more road sections and intersections (25.71% and 20.75%) are reorganized and controlled in the plan of “multiple arcs.” In solution of “a single arc,” most selected road sections are reversed to be one-way and all lanes for an intersection approach form one arc, while in solution of “multiple arcs,” almost all selected road sections except (2, 3) are one-way and 18 road sections (25.71% of selected road sections) have more than one arc on one approach. In general, setting of “multiple arcs” would increase the complexities of solving and traffic organizing but improve the efficiency of evacuation.


## 6. Conclusions

To enable an efficiency evacuation, an optimization model for lane-based reversal design and routing with intersection crossing conflict elimination for evacuation is constructed in this study. The proposed model is a bilevel model to minimize the total evacuation time to leave the evacuation zone. The upper-level is to find an optimal lane-based reversal plan by a tabu search algorithm; the lower-level is to implement lane-based routing of “a single arc for an intersection approach” and “multiple arcs for an intersection approach” under certain lane reversal plan, by formulating the optimal unique turning directions of each lane on each intersection approach with eliminating crossing conflict. In the lower-level model, it utilizes a simulated annealing algorithm to solve the problem.The proposed model and algorithm is tested by two cases. One case is an experiment in a nine-intersection evacuation zone based on the known distribution of parking lots, initial road network, and traffic data. The solutions show that when the background traffic reaches a certain extent, most arcs are reversed and become a single arc for an intersection approach. Along with the increase of background traffic, the objective function value of the optimal solution gets larger and larger. The other case is developed from the Jianye district of Nanjing city based on relevant survey data. In this case, two groups of experiments of “a single arc” and “multiple arcs” are performed. By comparing the schemes of evacuation network optimization of “a single arc” and “multiple arcs,” it can be found that the latter one costs more computing time but gets a better result with the total evacuation time. Besides, more road sections and intersections are reorganized and controlled in the plan of “multiple arcs,” and a quarter of road sections contain more than one arc on one approach in the plan of “multiple arcs.” In general, setting of “multiple arcs” would increase the complexities of solving and traffic organizing but improve the efficiency of evacuation.There are some directions for further research in this paper. Firstly, in contrast to the assumption that impedance of road sections is constant [19], the proposed model costs much more computing time. Therefore, further researches on the applicable scopes for either constant or BPR impedance function is needed. Secondly, the proposed model is static; it is assumed that all traffic loads at an arc simultaneously; however, in fact, there must be time differences among them, thus, the static impedance values must be greater than the actual impedance, and this model cannot solve the situations with staged evacuation. Therefore, combined with the existing research of the authors [38], the models would be developed based on Cell Transmission Model or other dynamic traffic models with the staged evacuation strategy in future.



---

*Source: 1273508-2016-08-17.xml*