# Multiobjective Optimization of Evacuation Routes in Stadium Using Superposed Potential Field Network Based ACO

Authors: Jialiang Kou; Shengwu Xiong; Zhixiang Fang; Xinlu Zong; Zhong Chen
Journal: Computational Intelligence and Neuroscience
 (2013)

---

## Abstract

Multiobjective evacuation routes optimization problem is defined to find out optimal evacuation routes for a group of evacuees under multiple evacuation objectives. For improving the evacuation efficiency, we abstracted the evacuation zone as a superposed potential field network (SPFN), and we presented SPFN-based ACO algorithm (SPFN-ACO) to solve this problem based on the proposed model. In Wuhan Sports Center case, we compared SPFN-ACO algorithm with HMERP-ACO algorithm and traditional ACO algorithm under three evacuation objectives, namely, total evacuation time, total evacuation route length, and cumulative congestion degree. The experimental results show that SPFN-ACO algorithm has a better performance while comparing with HMERP-ACO algorithm and traditional ACO algorithm for solving multi-objective evacuation routes optimization problem.


---

## Body

## 1. Introduction

The evacuation planning in large-scale public area usually possesses two difficult points:(1)
large scale: the large-scale public area has a complex flat structure. And it can hold thousands of people.(2)
multisource and multisink: in evacuation process, the evacuees often start at different places in public area and run away from different exits.In a word, the evacuation planning in large-scale public area is a challenging problem. For solving this problem, researchers have put forward some effective methods. Shi et al. [1] used agent-based model to simulate and analyze evacuation process in large public building under fire conditions. Chen and Miller-Hooks [2] employed Benders decomposition to determine a set of evacuation routes and the assignment of evacuees to these routes for large building. Tayfur and Taaffe [3] utilized linear programming relaxation to model and solve a resource requirements and scheduling problem during hospital evacuations with the objective of minimizing cost within a prespecified evacuation completion time. Fang et al. [4] modeled evacuation process in a teaching building with multiexits, simulated it by cellular automata, and analyzed the multiexits choice phenomenon to find out the optimal exits choice combination for all evacuees. Usually, multiple macroscopic objectives are required to be considered in actual evacuation planning, and a set of nondominated plans are needed for decision making. Thus, evacuation planning problem could be transformed into multi-objective optimization problem. However, just a few researches, such as the literature [5–7], focused on that. Among these pieces of literature, the literature [7] successfully solved the multi-objective evacuation routes optimization problem in stadium using HMERP-ACO algorithm. Fang et al. [7] abstracted evacuation zone as a hierarchical directed network according to the feature that the evacuees usually move far away from the center of evacuation zone in evacuation process. However, another feature, namely, each evacuee often moves toward and eventually reaches one of exits, was not considered in Fang’s paper. Then, how to take these two features into consideration? In physics, the potential of a point in the space generated by multiple point charges can be calculated by the superposition principle of electric potentials [8]. Inspired by this, we abstracted the center point of stadium as positive point charge and each exit as a negative point charge and used superposition principle of electric potentials to get the two features mentioned previous together. On the basis of superposed potential, we abstracted the Wuhan Sports Center stadium as a superposed potential field network (SPFN). And on the basis of SPFN, we proposed the SPFN-ACO algorithm to solve the multi-objective evacuation routes optimization problem. Compared with HMERP-ACO [7] and ACO [9], the SPFN-ACO shows much better optimization performance for solving multi-objective evacuation routes optimization problem.The remainder of this paper is organized as follows. Section2 introduces the state of the art evacuation planning using swarm intelligence. Section 3 defines multi-objective evacuation routes optimization problem. Section 4 introduces the SPFN. Section 5 states SPFN-ACO algorithm. Section 6 verifies optimization performance of SPFN-ACO by experiment and contains some analyses. Section 7 concludes this paper and looks into the future direction of this research.


## 2. Related Works

People in large-scale public areas are in danger because of a lot of manmade or natural accidents, such as fire, hurricane, and bomb [10]. For coping with these emergencies, many scientists and engineers have paid much attention to the researches about evacuation routes planning. In these researches, the application of swarm intelligence technologies to evacuation routes planning is a hot topic because evacuation process itself is a collective behavior. Swarm intelligence technology mainly includes particle swarm optimization (PSO) [11] technology and ant colony optimization (ACO) [9] technology. The swarm intelligence technology is mainly used in two aspects: the simulation of evacuation process and the optimization of evacuation routes [7, 12]. On one hand, swarm intelligence technologies have natural advantages to simulate collective behavior such as evacuation process [13]. On the other hand, the optimization mechanism of swarm intelligence algorithms can effectively optimize evacuation objectives by iterating the configuration of factors that affect evacuation efficiency [7, 14]. The factors that affect evacuation efficiency includes pheromone [7], location of shelters in evacuation zone [15], the direction of lanes [16], the placement of road barriers [17], and the scheduling of evacuation for each evacuee [18].Besides, evacuation routes optimization problem usually needs to consider multiple objectives, such as total clearance time [19] total number of survivals [20]. A few researches [5, 6] have involved the multi-objective evacuation routing optimization problem. Some of them applied swarm intelligence technologies to solve this kind of problem [7, 14].


## 3. Problem Formulation

In this paper, the evacuation zone is divided into many subzones. Each evacuation plan is composed of each evacuee’s route. So each evacuation planEPi can be represented as
(1)EPi=[er1er2⋯erj⋯erNE],i=1,2,…,NP,
where Np is the number of plans, erj is the route of the evacuee j, which can be described as
(2)erj=[sjStartsj1⋯sjk⋯sjEnd],j=1,2,…,NE,
where NE is the number of evacuees, sjStart and sjEnd are respectively, the start and the end subzone on the jth evacuee’s route. sjk is the kth interim subzone on the jth evacuee’s route. The end subzone is one of the exits in the evacuation zone.Thus, the multi-objective evacuation routes optimization problem in this paper could be formulated as in Algorithm1.Algorithm 1:Formulation of multi-objective evacuation routes optimization problem.
Finding the pareto optimal set [21] of evacuation
plans, make
f
1
=
min
(
TET
)
f
2
=
min
(
TERL
)
f
3
=
min
(
CCD
)
Subject to
N
E
i
(
t
)
≤
C
i,
where,NEi(t) is the number of evacuees in subzone i at tth
time step,Ci is the capacity of subzone i.The evacuation routes optimization problem involves three objectives that need to be achieved simultaneously, namely, minimization of total evacuation time, minimization of total evacuation route length, and minimization of cumulative congestion degree.Total evacuation time (TET) is given by(3)TET=∑i=1NEETi,
where ETi(i=1,2,…,NE) is the evacuation time of evacuee i.Total evacuation route length (TERL) is given by(4)TERL=∑i=1NEERLi,
where ERLi(i=1,2,…,NE) is the evacuation route length of evacuee i.Cumulative congestion degree (CCD) is given by(5)CCD=∑t=1NT∑i=1NSNEi(t)Ci,
where NEi(t) is the number of evacuees in subzone i at tth time step, Ci is the evacuees capacity of subzone i, NT is the number of time steps, and NS is the number of subzones.


## 4. Superposed Potential Field Network (SPFN)

The electric potential field of the point charge is shown in Figure1. If zero of potential at infinity is chosen, the potential u [8] at a distance r from a point charge Q is
(6)u=kQr,
for positive point charge (Figure 1(a)) or
(7)u=-kQr,
for negative point charge (Figure 1(b)).Potential field of point charge.
(a)
Positive point charge
(b)
Negative point chargeThe center point of the stadium could be seen as a positive point charge, and each exit could be seen as a negative point charge. The Wuhan Sports Center (Figure2) could be seen in a superposed potential field. According to the superposition principle of electric potentials, the superposed potential of a point in stadium uS could be derived by
(8)uS=uc+∑j=1NExitsuj=CCrC-∑j=1NExitsCjrj,
where NExits is the number of exits, uj is the potential of exit j,uj=-Cj/rj. Cj is the capacity of the exit j,rj is the distance to the exit j, uC is the potential of center point. rC is the distance to the center point, and CC is the capacity of the center point.Figure 2
Wuhan Sports Center (http://www.wuhansport.com/).Based on the superposed potential, we proposed the superposed potential field network (SPFN) to abstract the stadium. This model is partly based on the point model used in [5]. The SPFN could be formulated as
(9)G=(H,Z,U,C),
where H is the set of nodes, Z is the set of links, U is the set of potential of each node, and C is the set of capacity of each node.The stadium is divided into 157 subzones. Each subzone is abstracted as a node in SPFN. Each link between two nodes represents a connection relationship between two subzones. The potential of each node is the potential of the center point of the corresponding subzone. The capacity of each node is the capacity of the corresponding subzone. The coordinate of each node is the coordinate of the center point of the corresponding subzone. If an evacuee or a group of evacuees is seen as a positive test charge, it would always move from high potential node to low potential node. There are 216 links and 157 nodes in the SPFN of the Wuhan Sports Center stadium, including 10 exits nodes and 42 bleachers nodes. Figure3 shows the potential distribution of SPFN of the Wuhan Sports Center stadium.Figure 3
Potential distribution of SPFN of Wuhan Sports Center stadium.


## 5. SPFN-ACO

For solving the multi-objective evacuation routes optimization problem mentioned in Section3, on the basis of SPFN, we propose SPFN-ACO algorithm.


### 5.1. The Main Procedure of SPFN-ACO Algorithm

The main procedure of SPFN-ACO algorithm is listed in Algorithm2. We use pheromone vector to represent pheromones configuration on each link in the network. The pheromone vector (PV) is given by
(10)PV=[τ1τ2τ3⋯τNlinks],
where τk is the pheromone on kth link connecting node i and node j and  Nlinks is the total number of links between nodes in network.Algorithm 2:Procedure of SPFN-ACO.
S1.Initializes initial PVs population P0 as all-zero vectors. The population size of P0 is 2*Np. The number of ants is NA. m=1.
S2.For each PV, do:
S2.1. Each ants simultaneously finds its evacuation route under current PV by Simulation of Evacuation Process;
S2.2.All ants’ routes construct the corresponding evacuation plan under current PV and the objectives’ values
of this plan are calculated.
S3.Non-dominated sort 2*NpPVs according to corresponding route plan’s objectives. And, select the top NpPVs.
S4.Update top NpPVs. The updated top NpPVs construct PVs population Pm
S5.
m
=
m
+
1.
S6.For each PV in Pm-1, do:
S6.1. Each ants simultaneously finds its evacuation route under current PV by Simulation of Evacuation Process;
S6.2.All ants’ routes construct the corresponding evacuation plan under current PV and the objectives’ values of this plan are
calculated.
S7.Update Np pheromone vectors in Pm-1. The updated top Np pheromone vectors construct pheromone vectors population Qm.
ThePm-1 and Qm construct Rm, namely Rm=Pm-1∪Qm. The population size of Rm is 2*Np.
S8.Non-dominated sort Rm according to corresponding route plan’s objectives. And, select the top Np pheromone vectors to
construct new populationPm.
S9.If m⩽m_Max, go to S5.Or else, terminate the algorithm and output final Pareto optimal set of evacuation plans.
Note:
m is the number of generations; m_Max is the maximum number of generations.


### 5.2. Superposed Potential Field Based Roulette Wheel Method for Node Selection

The main procedure of Superposed Potential Field Based Wheel Method is listed in Algorithm3. There are NSC allowed visit neighbor nodes. SC is the set of allowed visit neighbor nodes. sk is the kth candidate node in SC,k=1,2,…,NSC. sj is the node which the ant i is in currently. SC can be given by
(11)SC={k∣NEk≤Ck,uk<uj}.
The neighbor nodes in SC must fit two conditions: the capacity constraint and the potential constraint.Algorithm 3:Simulation of evacuation process.
For each PV, there is a corresponding evacuation plan generated as follows:
S1.  t=0;
S2. Set the pheromone amounts on all connections by current PV.
S3. Randomly initialize each ant’s position and velocity, and select interim destination node for each ant by Superposed Potential
Field based Roulette Wheel Method;
S4.  t=t+1;
S5. For each ant, do:
S5.1. move one step towards the center point of its destination subzone;
S5.2. If this ant reaches its interim destination node, select new interim destination node by Superposed Potential Field based
Roulette Wheel Method;
S5.3. If this ant reaches one of exits, this ant stop move;
S6. If all ants have reached exits, quit and output each ant’s evacuation route; or else, go to S4.The capacity constraint is given by(12)NEk≤Ck.N
E
k is the number of evacuees in node sk, which is given by
(13)NEk=NAk*μ.NAk is the number of ants in node sk. Each ant represents μ evacuees.C
k is the capacity of node sk, which is calculated through
(14)Ck=AreakAreaE.Areak is the area of subzonek. AreaE is the average area which an evacuee usually occupies. By the literature [22], each evacuee occupies 0.3 m2.The potential constraint is given by(15)uk<uj,
where uj is the potential of the current visit node and uk is the potential of the next visit node. The potential constraint indicates that the ant should move from high-potential node to low-potential node, namely, the potential uk of next visit node sk should be less than the potential uj of current visit node sj.The procedure of superposed potential field based roulette wheel method is shown in Algorithm4.  Its principle could be explained by an example in Figure 4. In Figure 4, the digit on each node is the value of potential. The red node is the node which evacuee i is in. By potential, he could just choose the nodes of which the potential value is lower than the node which he is in as the candidates. So, he could choose three neighbor nodes as allowed visit nodes. The potential of allowed visit nodes is, respectively, 4, 4, and 2. And then, he has to choose one of them as the next visit node by calculating the transition probability and cumulative transition probability of each candidate as shown in Algorithm 4.Algorithm 4:Superposed potential field based Roulette Wheel Method.
S1.
Calculate the distance to neighbor nodes.
The distanceDjk between the current node sj and allowed visit neighbor node sk is given by:
D
j
k
=
(
x
j
-
x
k
)
2
+
(
y
j
-
y
k
)
2
,
s
k
∈
S
C,
where,(xk,yk) is the coordinate of the neighbor node sk; (xj,yj) is the coordinate of the current node sj; Djk is the length of link
j
k.
S2.
Calculate the congestion degrees of neighbor nodes.
The allowed visit neighbor nodesk’s congestion degree CDk(t) at the tth time step is given by:
CD
k
(
t
)
=
N
E
k
(
t
)
c
k
,
s
k
∈
S
C,
where,NEk(t) is the number of evacuees in neighbor node sk at the tth time step. ck is the capacity of node sk.
S3.
Calculate transition probability from node
s
j
to
s
k
The transition probabilityPjki(m,n,t) from node sj to sk at the tth time step is given by:
P
j
k
i
(
m
,
n
,
t
)
=
{
τ
j
k
α
(
m
,
n
)
η
j
k
β
(
m
,
n
,
t
)
∑
s
w
∈
S
C
τ
j
w
α
(
m
,
n
)
η
j
w
β
(
m
,
n
,
t
)
,
s
k
∈
S
C
0
,
otherwise
,
where,sj is the subzone which the ant i is in currently. τijα(m,n) is the pheromone amount on connection ij at mth generation
undernth pheromone vector; ηijβ(m,n,t) is the heuristic information related with link ij at tth time step, under nth pheromone
vector, atmth generation; SC is the set of candidate nodes; α and β are the parameters to control the relative importance between
the pheromone and the heuristic information.
The heuristic informationηij(m,n,t) on link ij at tth time step is given by:
η
i
j
(
m
,
n
,
t
)
=
1
D
i
j
*
(
(
N
E
j
(
m
,
n
,
t
)
+
1
)
/
(
C
j
+
1
)
),
where,Dij is the length of link ij; NEj(m,n,t) is the number of evacuees in node j at the tth time step; Cj is the capacity of node j.
S4.
Select one of candidate nodes according to cumulative transition probability
According to roulette wheel selection, the nodesk would be selected only and if only when
P
P
j
(
k
-
1
)
(
m
,
n
,
t
)
<
rand
≤
P
P
j
k
(
m
,
n
,
t
), rand is a random real number between 0 and 1. PPjk(m,n,t) is the cumulative transition
probability, which is given by:
P
P
j
k
(
m
,
n
,
t
)
=
∑
w
=
0
k
P
j
w
(
m
,
n
,
t
)
,
s
k
∈
S
C
Besides, we rule thatPPj0(m,n,t)=0.Figure 4
An example to show the superposed potential field based roulette wheel method.


### 5.3. Velocity, Position, and Moving Strategy

When the interim destination node is selected, the anti begins moving along link between current node sj and interim destination node sk. The moving speed [7] vi(t) of ant i is given by
(16)vi(t)=vmax*e-NEj(t)/Cj,
where NEi(t) is the number of evacuees in node sj at the tth time ste, Cj is the capacity of node sj, and  vmax is the maximum speed of ant i.We define a concept called remaining distance to interim destination node to measure whether the anti has already arrived interim destination node. The iterative formula of remaining distance is given by
(17)RDi(t+1)=RDi(t)-vi(t)*Δt,
where RDi(t+1) and RDi(t) are the remaining distance at (t+1) th and tth time step. Δt is the interval of time step, such as ten or twenty seconds. When an ant arrives at interim destination node, the remaining distance is set as the length of link between the interim destination node and the next interim destination node.


### 5.4. Pheromone Updating

The pheromone on each link between nodes is updated by(18)τjk(m+1,n)=(1-ρ)τjk(m,n)+ρΔτjk(m,n),
where τjk(m+1,n) and τjk(m,n) are pheromone amount on link jk between nodes sj and sk at (m+1)th and mth generation under nth pheromone vector. Δτjk is the variation amount of pheromone on link jk. The variation amount of pheromone Δτjk(m,n) is given by
(19)Δτjk(m,n)=1Djk*∑t=0NT(m,n)(NEk(m,n,t)/Ck),
where Djk is the length of link jk, NEk(m,n,t) is the number of evacuees in node sk at the tth time step, and Ck is the capacity of node sk.


## 5.1. The Main Procedure of SPFN-ACO Algorithm

The main procedure of SPFN-ACO algorithm is listed in Algorithm2. We use pheromone vector to represent pheromones configuration on each link in the network. The pheromone vector (PV) is given by
(10)PV=[τ1τ2τ3⋯τNlinks],
where τk is the pheromone on kth link connecting node i and node j and  Nlinks is the total number of links between nodes in network.Algorithm 2:Procedure of SPFN-ACO.
S1.Initializes initial PVs population P0 as all-zero vectors. The population size of P0 is 2*Np. The number of ants is NA. m=1.
S2.For each PV, do:
S2.1. Each ants simultaneously finds its evacuation route under current PV by Simulation of Evacuation Process;
S2.2.All ants’ routes construct the corresponding evacuation plan under current PV and the objectives’ values
of this plan are calculated.
S3.Non-dominated sort 2*NpPVs according to corresponding route plan’s objectives. And, select the top NpPVs.
S4.Update top NpPVs. The updated top NpPVs construct PVs population Pm
S5.
m
=
m
+
1.
S6.For each PV in Pm-1, do:
S6.1. Each ants simultaneously finds its evacuation route under current PV by Simulation of Evacuation Process;
S6.2.All ants’ routes construct the corresponding evacuation plan under current PV and the objectives’ values of this plan are
calculated.
S7.Update Np pheromone vectors in Pm-1. The updated top Np pheromone vectors construct pheromone vectors population Qm.
ThePm-1 and Qm construct Rm, namely Rm=Pm-1∪Qm. The population size of Rm is 2*Np.
S8.Non-dominated sort Rm according to corresponding route plan’s objectives. And, select the top Np pheromone vectors to
construct new populationPm.
S9.If m⩽m_Max, go to S5.Or else, terminate the algorithm and output final Pareto optimal set of evacuation plans.
Note:
m is the number of generations; m_Max is the maximum number of generations.


## 5.2. Superposed Potential Field Based Roulette Wheel Method for Node Selection

The main procedure of Superposed Potential Field Based Wheel Method is listed in Algorithm3. There are NSC allowed visit neighbor nodes. SC is the set of allowed visit neighbor nodes. sk is the kth candidate node in SC,k=1,2,…,NSC. sj is the node which the ant i is in currently. SC can be given by
(11)SC={k∣NEk≤Ck,uk<uj}.
The neighbor nodes in SC must fit two conditions: the capacity constraint and the potential constraint.Algorithm 3:Simulation of evacuation process.
For each PV, there is a corresponding evacuation plan generated as follows:
S1.  t=0;
S2. Set the pheromone amounts on all connections by current PV.
S3. Randomly initialize each ant’s position and velocity, and select interim destination node for each ant by Superposed Potential
Field based Roulette Wheel Method;
S4.  t=t+1;
S5. For each ant, do:
S5.1. move one step towards the center point of its destination subzone;
S5.2. If this ant reaches its interim destination node, select new interim destination node by Superposed Potential Field based
Roulette Wheel Method;
S5.3. If this ant reaches one of exits, this ant stop move;
S6. If all ants have reached exits, quit and output each ant’s evacuation route; or else, go to S4.The capacity constraint is given by(12)NEk≤Ck.N
E
k is the number of evacuees in node sk, which is given by
(13)NEk=NAk*μ.NAk is the number of ants in node sk. Each ant represents μ evacuees.C
k is the capacity of node sk, which is calculated through
(14)Ck=AreakAreaE.Areak is the area of subzonek. AreaE is the average area which an evacuee usually occupies. By the literature [22], each evacuee occupies 0.3 m2.The potential constraint is given by(15)uk<uj,
where uj is the potential of the current visit node and uk is the potential of the next visit node. The potential constraint indicates that the ant should move from high-potential node to low-potential node, namely, the potential uk of next visit node sk should be less than the potential uj of current visit node sj.The procedure of superposed potential field based roulette wheel method is shown in Algorithm4.  Its principle could be explained by an example in Figure 4. In Figure 4, the digit on each node is the value of potential. The red node is the node which evacuee i is in. By potential, he could just choose the nodes of which the potential value is lower than the node which he is in as the candidates. So, he could choose three neighbor nodes as allowed visit nodes. The potential of allowed visit nodes is, respectively, 4, 4, and 2. And then, he has to choose one of them as the next visit node by calculating the transition probability and cumulative transition probability of each candidate as shown in Algorithm 4.Algorithm 4:Superposed potential field based Roulette Wheel Method.
S1.
Calculate the distance to neighbor nodes.
The distanceDjk between the current node sj and allowed visit neighbor node sk is given by:
D
j
k
=
(
x
j
-
x
k
)
2
+
(
y
j
-
y
k
)
2
,
s
k
∈
S
C,
where,(xk,yk) is the coordinate of the neighbor node sk; (xj,yj) is the coordinate of the current node sj; Djk is the length of link
j
k.
S2.
Calculate the congestion degrees of neighbor nodes.
The allowed visit neighbor nodesk’s congestion degree CDk(t) at the tth time step is given by:
CD
k
(
t
)
=
N
E
k
(
t
)
c
k
,
s
k
∈
S
C,
where,NEk(t) is the number of evacuees in neighbor node sk at the tth time step. ck is the capacity of node sk.
S3.
Calculate transition probability from node
s
j
to
s
k
The transition probabilityPjki(m,n,t) from node sj to sk at the tth time step is given by:
P
j
k
i
(
m
,
n
,
t
)
=
{
τ
j
k
α
(
m
,
n
)
η
j
k
β
(
m
,
n
,
t
)
∑
s
w
∈
S
C
τ
j
w
α
(
m
,
n
)
η
j
w
β
(
m
,
n
,
t
)
,
s
k
∈
S
C
0
,
otherwise
,
where,sj is the subzone which the ant i is in currently. τijα(m,n) is the pheromone amount on connection ij at mth generation
undernth pheromone vector; ηijβ(m,n,t) is the heuristic information related with link ij at tth time step, under nth pheromone
vector, atmth generation; SC is the set of candidate nodes; α and β are the parameters to control the relative importance between
the pheromone and the heuristic information.
The heuristic informationηij(m,n,t) on link ij at tth time step is given by:
η
i
j
(
m
,
n
,
t
)
=
1
D
i
j
*
(
(
N
E
j
(
m
,
n
,
t
)
+
1
)
/
(
C
j
+
1
)
),
where,Dij is the length of link ij; NEj(m,n,t) is the number of evacuees in node j at the tth time step; Cj is the capacity of node j.
S4.
Select one of candidate nodes according to cumulative transition probability
According to roulette wheel selection, the nodesk would be selected only and if only when
P
P
j
(
k
-
1
)
(
m
,
n
,
t
)
<
rand
≤
P
P
j
k
(
m
,
n
,
t
), rand is a random real number between 0 and 1. PPjk(m,n,t) is the cumulative transition
probability, which is given by:
P
P
j
k
(
m
,
n
,
t
)
=
∑
w
=
0
k
P
j
w
(
m
,
n
,
t
)
,
s
k
∈
S
C
Besides, we rule thatPPj0(m,n,t)=0.Figure 4
An example to show the superposed potential field based roulette wheel method.


## 5.3. Velocity, Position, and Moving Strategy

When the interim destination node is selected, the anti begins moving along link between current node sj and interim destination node sk. The moving speed [7] vi(t) of ant i is given by
(16)vi(t)=vmax*e-NEj(t)/Cj,
where NEi(t) is the number of evacuees in node sj at the tth time ste, Cj is the capacity of node sj, and  vmax is the maximum speed of ant i.We define a concept called remaining distance to interim destination node to measure whether the anti has already arrived interim destination node. The iterative formula of remaining distance is given by
(17)RDi(t+1)=RDi(t)-vi(t)*Δt,
where RDi(t+1) and RDi(t) are the remaining distance at (t+1) th and tth time step. Δt is the interval of time step, such as ten or twenty seconds. When an ant arrives at interim destination node, the remaining distance is set as the length of link between the interim destination node and the next interim destination node.


## 5.4. Pheromone Updating

The pheromone on each link between nodes is updated by(18)τjk(m+1,n)=(1-ρ)τjk(m,n)+ρΔτjk(m,n),
where τjk(m+1,n) and τjk(m,n) are pheromone amount on link jk between nodes sj and sk at (m+1)th and mth generation under nth pheromone vector. Δτjk is the variation amount of pheromone on link jk. The variation amount of pheromone Δτjk(m,n) is given by
(19)Δτjk(m,n)=1Djk*∑t=0NT(m,n)(NEk(m,n,t)/Ck),
where Djk is the length of link jk, NEk(m,n,t) is the number of evacuees in node sk at the tth time step, and Ck is the capacity of node sk.


## 6. Experiment and Analysis

### 6.1. The Experiment Design

In this paper, we took a 20000 evacuees’ drill in Wuhan Sports Center Stadium as an example to do simulation experiment. This stadium has 42 bleachers subzones and 10 exits subzones. Ants are randomly allocated to 42 bleachers subzones, and each ant represents 100 evacuees. The maximum speed of each ant is 2 m/s [23] and varies from 0 to 2 m/s along with the congestion degree. The optimization performance of SPFN-ACO was compared with HMERP-ACO and traditional ACO which is used in Fang’s paper [7]. By experience, the parameters of the three algorithms are set as Table 1. m_Max is the total number of generations. Np is the population size of evacuation plans in each generation. vmax is the maximum speed of each ant. Δt is the length of each time step. NA is the total number of ants. Each ant represents μ evacuees. α and β are the parameters to control the relative importance between the pheromone and the heuristic information. ρ is the evaporation rate [24], ρ∈(0,1].Table 1
Parameter values in SPFN-ACO, HMERP-ACO, and ACO.
m
_
Max
N
p
v
max
Δ
t
α
β
ρ
N
A
μ
200
10
2 m/s
25 s
1
3
0.5
200
100


### 6.2. The Experimental Result Analysis

Figure5 shows the f1,f2, and f3 values of non-dominated plans derived from the three algorithms. The “blue cross,” “red pentagram,” and “black solid circle,” respectively, represent the f1,f2, and f3 values of non-dominated plans derived from the SPFN-ACO, the HMERP-ACO, and the ACO algorithm. The f1,f2, and f3 values of non-dominated plans derived from the SPFN-ACO algorithm are smaller than those generated by the other two algorithms. According to Bierlaire’s viewpoint [25], the evacuation process could be seen as a series of node selections made by evacuees, and then f1,f2, and f3 values of non-dominated plans would depend on the node selection strategy. For the three algorithms mentioned in this paper, the efficiency of node selection strategy resorts to the transition probabilities. The transition probability is mainly determined by two aspects: the selection of candidate neighbor nodes and the relative importance pheromone versus heuristic information. The latter aspect is determined by the setting of relative importance parameters α and β. The former aspect is determined by the conditions of candidate neighbor nodes selection. Among the conditions, the capacity constraint is same for all the three algorithms. Thus, the difference is another condition: the ACO algorithm adopts the tabu list; the HMERP-ACO adopts the hierarchy defined in Fang’s paper [7]; the SPFN-ACO adopts the potential introduced in this paper. The tabu list takes the visited nodes on each ant’s route as forbidden visit nodes for this ant. It did not consider any domain knowledge that can raise evacuation efficiency. The hierarchical directed network uses the feature that each evacuee moves far away from the center point of the stadium but without considering another feature that each evacuee moves towards one of the exits. The superposed potential field network takes the two features into account, obviously further raises the evacuation efficiency, and improves optimization objectives. This is the reason why the f1,f2, and f3 values of non-dominated plans derived from the SPFN-ACO are better than those derived from HMERP-ACO and ACO.f
1
,
f
2
, and f3 values of nondominated plans derived from three algorithms.
(a)
(b)
(c)
(d)Figure6 shows the evacuation curves [26] of the three algorithms. By SPFN-ACO, 95% of evacuees have left the stadium at 450 seconds, and 100% of evacuees have been evacuated out of the stadium at 725 seconds. By HMERP-ACO, it, respectively, needs 575 and 875 seconds; by ACO, it even needs 1675 and 3525 seconds. The results indicate that the candidate nodes selection condition using domain knowledge can shorten the evacuation time and raise evacuation efficiency. And if two factors that can facilitate evacuation are taken into account, the evacuation time is less than that just considering one factor. The SPFN-ACO shows a much better evacuation time performance than that of the other two algorithms.Figure 6
Evacuation curves of the three algorithms.Figure7 shows the time-varying congestion degrees of the nodes in the three algorithms. At the first X seconds, all the three algorithms show a relatively high congestion in nodes 1 to 100. With the rise of time, the plans generated by the ACO and HMERP-ACO algorithms show a slowly decreased heavy congestion in nodes. But the congestion in nodes decreases sharply for the plan generated by SPFN-ACO. This indicates that, compared with the other two algorithms, the SPFN-ACO can evacuate most of evacuees out of the middle zone of stadium and therefore reduce the congestion degree in the middle zone rapidly. However, in all the three algorithms, it takes a relatively long time to make the congestion degrees in all nodes decrease to zero, although the SPFN-ACO expands the least time. The “long-tail pheromone” indicates that all the three algorithms need a relatively long time (compared with the network clearance time) to take all evacuees out of the stadium. Besides, the SPFN-ACO possesses the smallest cumulative congestion degree in the three algorithms. Therefore, totally speaking, the congestion situation of SPFN-ACO generated plans is better than that of the other two algorithms, but the congestion situation of SPFN-ACO still needs to be improved.Time-varying congestion degrees in three algorithms.
(a)
SPFN-ACO
(b)
HMERP-ACO
(c)
ACOFigure8 shows the natural logarithm of hypervolume for three algorithms. Horizontal ordinate is the generations of evolution; vertical ordinate is the natural logarithm of the hyper volume (HV). The hyper volume is a metric of convergence [27]. The larger the natural logarithm of hyper volume, the better the convergence of the algorithm. Thus, from Figure 8, we can conclude that the SPFN-ACO acquires the best convergence performance, the HMERP-ACO comes second, and the ACO has the worst. And, with the rise of generations, the convergence of all three algorithms is improved. It indicates that, with the iteration of pheromones on each link, the evacuation plans generated by all the three algorithms could be gradually slightly improved. However, the relative merits between three algorithms are not changed. This indicates that the relative merits between three algorithms are determined by the selection of candidate nodes and the relative importance pheromone versus heuristic information but not the concrete pheromone value on each link.The natural logarithm of hypervolume for three algorithms.
(a)
(b)
SPFN-ACO
(c)
HMERP-ACO
(d)
ACOFigure9 shows the proportion of non-dominated plans in all plans derived from three algorithms. As shown in Figure 8, before the 40th generation, for all three algorithms, the proportion of non-dominated plans fluctuates; from the 40th to 197th generation, the proportion increases in stage. But at the 198th generation, for HMERP-ACO, the proportion sharply drops down to 20%. Finally, by the evolution of 200 generations, the proportion of non-dominated plans for SPFN-ACO reaches 50%, higher than that for HMERP-ACO (20%) and ACO (40%).Figure 9
The proportion of non-dominated plans derived from three algorithms.


## 6.1. The Experiment Design

In this paper, we took a 20000 evacuees’ drill in Wuhan Sports Center Stadium as an example to do simulation experiment. This stadium has 42 bleachers subzones and 10 exits subzones. Ants are randomly allocated to 42 bleachers subzones, and each ant represents 100 evacuees. The maximum speed of each ant is 2 m/s [23] and varies from 0 to 2 m/s along with the congestion degree. The optimization performance of SPFN-ACO was compared with HMERP-ACO and traditional ACO which is used in Fang’s paper [7]. By experience, the parameters of the three algorithms are set as Table 1. m_Max is the total number of generations. Np is the population size of evacuation plans in each generation. vmax is the maximum speed of each ant. Δt is the length of each time step. NA is the total number of ants. Each ant represents μ evacuees. α and β are the parameters to control the relative importance between the pheromone and the heuristic information. ρ is the evaporation rate [24], ρ∈(0,1].Table 1
Parameter values in SPFN-ACO, HMERP-ACO, and ACO.
m
_
Max
N
p
v
max
Δ
t
α
β
ρ
N
A
μ
200
10
2 m/s
25 s
1
3
0.5
200
100


## 6.2. The Experimental Result Analysis

Figure5 shows the f1,f2, and f3 values of non-dominated plans derived from the three algorithms. The “blue cross,” “red pentagram,” and “black solid circle,” respectively, represent the f1,f2, and f3 values of non-dominated plans derived from the SPFN-ACO, the HMERP-ACO, and the ACO algorithm. The f1,f2, and f3 values of non-dominated plans derived from the SPFN-ACO algorithm are smaller than those generated by the other two algorithms. According to Bierlaire’s viewpoint [25], the evacuation process could be seen as a series of node selections made by evacuees, and then f1,f2, and f3 values of non-dominated plans would depend on the node selection strategy. For the three algorithms mentioned in this paper, the efficiency of node selection strategy resorts to the transition probabilities. The transition probability is mainly determined by two aspects: the selection of candidate neighbor nodes and the relative importance pheromone versus heuristic information. The latter aspect is determined by the setting of relative importance parameters α and β. The former aspect is determined by the conditions of candidate neighbor nodes selection. Among the conditions, the capacity constraint is same for all the three algorithms. Thus, the difference is another condition: the ACO algorithm adopts the tabu list; the HMERP-ACO adopts the hierarchy defined in Fang’s paper [7]; the SPFN-ACO adopts the potential introduced in this paper. The tabu list takes the visited nodes on each ant’s route as forbidden visit nodes for this ant. It did not consider any domain knowledge that can raise evacuation efficiency. The hierarchical directed network uses the feature that each evacuee moves far away from the center point of the stadium but without considering another feature that each evacuee moves towards one of the exits. The superposed potential field network takes the two features into account, obviously further raises the evacuation efficiency, and improves optimization objectives. This is the reason why the f1,f2, and f3 values of non-dominated plans derived from the SPFN-ACO are better than those derived from HMERP-ACO and ACO.f
1
,
f
2
, and f3 values of nondominated plans derived from three algorithms.
(a)
(b)
(c)
(d)Figure6 shows the evacuation curves [26] of the three algorithms. By SPFN-ACO, 95% of evacuees have left the stadium at 450 seconds, and 100% of evacuees have been evacuated out of the stadium at 725 seconds. By HMERP-ACO, it, respectively, needs 575 and 875 seconds; by ACO, it even needs 1675 and 3525 seconds. The results indicate that the candidate nodes selection condition using domain knowledge can shorten the evacuation time and raise evacuation efficiency. And if two factors that can facilitate evacuation are taken into account, the evacuation time is less than that just considering one factor. The SPFN-ACO shows a much better evacuation time performance than that of the other two algorithms.Figure 6
Evacuation curves of the three algorithms.Figure7 shows the time-varying congestion degrees of the nodes in the three algorithms. At the first X seconds, all the three algorithms show a relatively high congestion in nodes 1 to 100. With the rise of time, the plans generated by the ACO and HMERP-ACO algorithms show a slowly decreased heavy congestion in nodes. But the congestion in nodes decreases sharply for the plan generated by SPFN-ACO. This indicates that, compared with the other two algorithms, the SPFN-ACO can evacuate most of evacuees out of the middle zone of stadium and therefore reduce the congestion degree in the middle zone rapidly. However, in all the three algorithms, it takes a relatively long time to make the congestion degrees in all nodes decrease to zero, although the SPFN-ACO expands the least time. The “long-tail pheromone” indicates that all the three algorithms need a relatively long time (compared with the network clearance time) to take all evacuees out of the stadium. Besides, the SPFN-ACO possesses the smallest cumulative congestion degree in the three algorithms. Therefore, totally speaking, the congestion situation of SPFN-ACO generated plans is better than that of the other two algorithms, but the congestion situation of SPFN-ACO still needs to be improved.Time-varying congestion degrees in three algorithms.
(a)
SPFN-ACO
(b)
HMERP-ACO
(c)
ACOFigure8 shows the natural logarithm of hypervolume for three algorithms. Horizontal ordinate is the generations of evolution; vertical ordinate is the natural logarithm of the hyper volume (HV). The hyper volume is a metric of convergence [27]. The larger the natural logarithm of hyper volume, the better the convergence of the algorithm. Thus, from Figure 8, we can conclude that the SPFN-ACO acquires the best convergence performance, the HMERP-ACO comes second, and the ACO has the worst. And, with the rise of generations, the convergence of all three algorithms is improved. It indicates that, with the iteration of pheromones on each link, the evacuation plans generated by all the three algorithms could be gradually slightly improved. However, the relative merits between three algorithms are not changed. This indicates that the relative merits between three algorithms are determined by the selection of candidate nodes and the relative importance pheromone versus heuristic information but not the concrete pheromone value on each link.The natural logarithm of hypervolume for three algorithms.
(a)
(b)
SPFN-ACO
(c)
HMERP-ACO
(d)
ACOFigure9 shows the proportion of non-dominated plans in all plans derived from three algorithms. As shown in Figure 8, before the 40th generation, for all three algorithms, the proportion of non-dominated plans fluctuates; from the 40th to 197th generation, the proportion increases in stage. But at the 198th generation, for HMERP-ACO, the proportion sharply drops down to 20%. Finally, by the evolution of 200 generations, the proportion of non-dominated plans for SPFN-ACO reaches 50%, higher than that for HMERP-ACO (20%) and ACO (40%).Figure 9
The proportion of non-dominated plans derived from three algorithms.


## 7. Conclusions and Future Works

We proposed a multi-objective optimization algorithm of the evacuation routes SPFN-ACO, which is based on the organization of the evacuees’ space-time paths within a superposed potential field network (SPFN). The ACO algorithm organizes evacuees’ space-time paths without any domain knowledge that can help improve evacuation efficiency; the HMERP-ACO algorithm merely employs one promotive factor for improving evacuation efficiency; the SPFN efficiently combines two factors together, which can facilitate the raise of evacuation efficiency by reasonably organizing the evacuees’ space-time paths. By validation of simulation experiment, compared with HMERP-ACO and ACO algorithms, the SPFN-ACO algorithm is more suitable to solve the multi-objective optimization problem of the evacuation routes.It is planned to do further researches on the basis of SPFN-ACO, such as defining more realistic evacuation scenarios, studying the effects of grouping size of evacuees and the total number of evacuees on evacuation efficiency, and discussing the influences of the population size of pheromone vectors and the number of evolution generations on algorithm performance.



---

*Source: 369016-2013-06-19.xml*