# Dynamic Path Optimization with Real-Time Information for Emergency Evacuation

Authors: Huajun Zhang; Qin Zhao; Zihui Cheng; Linfan Liu; Yixin Su
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

In order to find the optimal path for emergency evacuation, this paper proposes a dynamic path optimization algorithm based on real-time information to search the optimal path and it takes fire accident as an example to introduce the algorithm principle. Before the accidents, it uses the Dijkstra algorithm to get the prior evacuation network which includes evacuation paths from each node to the exit port. When the accidents occur, the evacuees are unable to pass through the passage where the accident point and the blocking point are located, then the proposed method uses the breadth-first search strategy to solve the path optimization problem based on the prior evacuation network, and it dynamically updates the evacuation path according to the real-time information. Because the prior evacuation network includes global optimal evacuation paths from each node to the exit port, the breadth-first search algorithm only searches local optimal paths to avoid the blockage node or dangerous area. Because the online optimization solves a local pathfinding problem and the entire topology optimization is an offline calculation, the proposed method can find the optimal path in a short time when the accident situation changes. The simulation tests the performances of the proposed algorithm with different situations based on the topology of a building, and the results show that the proposed algorithm is effective to get the optimal path in a short time when it faces changes caused by the factors such as evacuee size, people distribution, blockage location, and accident points.


---

## Body

## 1. Introduction

The most important thing for emergency evacuation is to guide people to move from dangerous areas to safe areas in the shortest time. Facing emergencies such as hurricanes, tsunamis, fires, and poisonous gas leakage [1], some methods were proposed to find the optimal path according to the prior information [2, 3], and the methods are not suitable for the emergency evacuation when the situations are significantly different from the prior information. Studies have shown that fire is the most frequent accident among the above emergencies [4–6], and it gets more attention from researchers since fire accidents frequently cause huge losses to mankind; then, this paper takes fire accident as an example to introduce the proposed algorithm principle. The evacuation environment includes route topology, exit location, evacuee size, and people distribution, and changes of each element bring different evacuation paths. Fire accidents often happen suddenly and unpredictably, and the static path planning algorithms have limited application in practice since the prior environment information is different from the real-time environment information during emergencies. According to the studies of some fire event cases [7–9], chaotic and untimely evacuation is the important reason for the high casualty rate. In crowded buildings such as shopping malls, supermarkets, and large cruise, people always move without any regular pattern, and it is necessary to search evacuation paths according to exit locations, real-time evacuee locations, and evacuee size [10, 11]. It is dangerous for evacuees to pass a passageway that is full of smoke, and the smoke spreading changes the route topology during the evacuation. The old path is not fit for the new situation when some passageways change, and it is a time-consuming process to find a new optimal path. In order to find the evacuation path in a short time, some methods [12] simplified the route topology to reduce the computation time, and the incomplete dynamic route topology made the new path different from the shortest one. With the development of stochastic optimization, some intelligent algorithms such as ant colony algorithm [13–15], particle swarm algorithm [16–18], bee colony algorithm [19–21], and genetic algorithm [22] or greedy algorithm [23] were used to find the dynamic path. When route topography and constraints changed, intelligent algorithms took the old path as a feasible solution for dynamic path searching. Although intelligent algorithms are able to search for optimal solutions globally, they converge slowly when facing dynamic evacuation problems.Recently, the dynamic evacuation problem has become a hot research topic, and many scholars try to get the shortest path according to dynamic situations. The authors in references [24–27] built the intelligent integrated fire rescue system which updated optimal paths by using the wireless sensor or vision camera to detect people locations. However, the wireless sensors and vision cameras are difficult to get accurate dynamic information about the people, and the online computation is also complex and time consuming. In order to get the shortest paths in a short time, basic and improved Dijkstra algorithms are the most popular methods used to search the optimal paths [28–30]. Beside the path length, safety is also important for people during the evacuation, and the authors references [31–33] took the safest and shortest paths as the cost function to search the optimal paths. Facing the dynamic situation, the authors in references [34–37] used dynamic planning to search for the optimal paths and informed everyone on the ship how to move toward the exit. Neural networks are good at learning the hidden knowledge from sample data, and the authors in [38–41] used neural networks to decide which paths are available for people to evacuate dynamically. Because the smog keeps spreading during the fire accident, feasible evacuation paths should consider the future changes of dangerous areas. The authors in [42–44] tried to predict the dangerous area and searched the optimal paths step by step, and the prediction performances influenced the effectiveness of the evacuation significantly.Effective emergency evacuation paths are important for the safety of personal in accidents, and the basic requirement is that the commander gets the optimal paths to fit the dynamic changes in a short time. This paper proposes a dynamic path optimization method which includes offline search and online search. The offline optimization gets the prior evacuation network which includes evacuation paths from each node to the exit port, and the online optimization searches the local optimal paths based on the prior evacuation network when the accidents happen. The changes from accident locations, dangerous areas, and blocking paths call the online optimization algorithm to search the dynamic optimal paths. Online optimization quickly plans the evacuation paths to adapt the real-time situations.This paper is organized as follows: Section2 introduces the method of establishing the network topology of the building. Section 3 details the proposed dynamic optimization algorithm that uses offline optimization and online optimization to search the optimal evacuation paths. The simulation results and analysis are in Section 4. Section 5 summaries the conclusions.


## 2. Evacuation Environment Model

The emergency evacuation model mainly includes microscopic model and macroscopic model [45]. The microscopic model focuses on the study of individual behavior characteristics, and the path optimization algorithm simulates human individual behavior and mental activities to select evacuation paths. Typical microscopic models include the social force model, cellular automata model, and lattice gas model [46]. Because the microscopic model uses less overall information about the environment, it always gets local feasible paths and ignores the global optimal paths. The local feasible paths are able to guide people to move toward the exit, but it is different from the optimal solution that considers the evacuation time and personal safety during the evacuation process. In addition, the optimization algorithms based on the microscopic model converge slowly, and the online pathfinding requires fast convergence algorithms [47]. The macroscopic model pays attention to the people flow of each evacuation path at different moments based on global information. People move at different speeds when the density of people changes, and the move speeds are macroviews of individual behavior. The relationship between move speed and people density is summarized by the characteristics of individual movement and saved as a piecewise function. Since the optimization outputs based on the macroscopic model are global optimal solutions, the paths are more effective for emergency evacuation.In the macroscopic model, paths and intersections of the building are regarded as the edges and nodes of a graph. The macroscopic model is a weighted graph as follows:(1)G=V,E,W,where V is the set of nodes, V=vi|i∈1,n, in which n is the total number of the network nodes. E is the set of graph edges, V=eij|i,j∈V. W is the set of weights of each edge. Usually, corridors or stairways in a building are set as edges, and the endpoints of corridors are set as nodes, and the weight of each edge is the actual distance between the connected nodes. In the large-scale macroscopic model, optimization also requires complex computation due to a large number of nodes and edges.This paper uses macroscopic modeling principles to establish the model of an underground shopping mall and related passage spaces. This shopping mall is the middle floor of a three-floor structure, the bottom floor is the subway station, and the top floor has several urban traffic roads. The macroscopic model represents the fire evacuation environment of the surrounding area, and its graph is shown in Figure1. The model is a multioutlet network, where V is a set of ordinary nodes and V=N1,N2,…,N22 and O is a set of safe exit nodes and O=O1,O2,O3,O4. Each weight is the actual distance between adjacent nodes, and the weight values are shown in Table 1.Figure 1
Network model of the underground shopping mall.Table 1
The weight values between adjacent nodes.
Node numberWeight value (m)1w1,3=322w2,3=7, w2,6=113w3,1=32, w3,2=7, w3,4=21, w3,7=54w4,3=21, w4,5=13, w4,8=85w5,4=13,w5,9=14, w5,O1=66w6,2=11,w6,7=43, w6,13=647w7,3=5, w7,6=43, w7,8=17,w7,14=118w8,4=8,w8,7=17, w8,9=4,w8,15=119w9,5=14,w9,8=4, w9,10=44,w9,16=510w10,9=44,w10,11=8, w10,21=9211w11,10=812w12,13=813w13,6=64,w13,12=8, w13,14=51,w13,19=1314w14,7=11,w14,13=51, w14,O2=315w15,8=11,w15,16=13, w15,17=4116w16,9=5,w16,15=13, w16,18=3717w17,15=41,w17,18=26, w17,20=81,w17,O2=1418w18,16=37,w18,17=26, w18,O4=9919w19,13=13,w19,20=52, w19,22=1420w20,17=81,w20,19=52, w20,21=3421w21,10=92,w21,20=34, w21,O3=1222w22,19=14


## 3. Dynamic Path Optimization

The proposed dynamic path optimization includes offline optimization and online optimization. With prior information of the evacuation model shown in Figure1, the offline optimization is used to search for the optimal paths that contain evacuation routes from each node to exit nodes. The online optimization dynamically searches the optimal paths when real-time information is different from the prior information. The online optimization searches the local areas and converges fast, and it gets new optimal paths that fit the real-time requirement in a short time.


### 3.1. Offline Prior Evacuation Path Network

Before the fire accident, it is necessary to get the shortest evacuation path from each node to each exit for the building. This search is an offline process that uses the Dijkstra algorithm to get the prior evacuation path network that stores the node number of each evacuation path. The Dijkstra algorithm is a typical algorithm for searching the shortest path between nodes in a graph, and it has been widely used to search for the shortest evacuation paths in fire incidents. The flow of the standard Dijkstra algorithm is shown as Algorithm1. The operation u ← vertex in Q with min dist [u] means the algorithm searches for the vertex u in the vertex set Q that has the least distance. Operation lengthu,v returns the length of the edge connecting two adjacent nodes u and v.Algorithm 1: Offline evacuation path optimization.
create vertex setQfor each vertex v in Graph:dist [v]  ⟵  Infinitypath [v]  ⟵  Undefinedaddv to Qdist [source]  ⟵  0whileQ is not empty:u  ⟵  vertex in Q with min dist [u]removeu from Qfor each neighbor v of u:expand  ⟵  dist [u] + length (u, v)if expand < dist [v]:dist [v]  ⟵  expandpath [v]  ⟵  ureturn dist [], path []The variableexpand is the length of the path from the source node to the node v via u. The principle used to determine whether the node v satisfies the slack condition is as follows:(2)du,v>du,q+dq,v,where du,v is the distance between node u and node v. Equation (2) shows that the distance from node u to node v via node q is shorter than the old distance between node u and node v, and then the path pu,v is updated as follows:(3)pu,v=u,q,v.According to the Dijkstra algorithm, we get the evacuation path network of the building shown in Figure1. The network includes the shortest path from each node to each exit. Since the network is too large to display, Table 2 describes the nodes from node 3 to the four exits and the paths are shown in different colors in Figure 2. If people are at node N3, they will use the information shown in Table 2 to quickly escape to the safety exit, so this network is the prior information for the people to escape. When the fire environment is the same as the offline optimized hypothetical environment, people can move according to the prior evacuation network.Table 2
Evacuation paths from node 3 to the exits.
Start node and exit nodeShortest pathDistance (m)N3-O1N3,N4,N5,O140N3-O2N3,N7,N14,O219N3-O3N3,N7,N14,O2,N17,N20,N21,O3160N3-O4N3,N7,N14,O2,N17,N18,O4158Figure 2
The paths from node 3 and node 8 to different exits in the prior evacuation network.


### 3.2. Online Local Path Optimization

The location and time of the fire are unpredictable; the distribution of people inside the building is also changing. The prior evacuation network needs to be modified when some edges are blocked or in a dangerous area. This modification only adjusts the nodes of the paths that are affected by the fire, and it is a local path optimization based on the prior evacuation network. Because the fire is changing during the evacuation, then the online local path optimization keeps searching for the new solutions. In the network graph modelG=V,E,W, the evacuation path pi,j from the start node i to the end node j is as follows:(4)pi,j=Ni,Nr,…,Ns,Nj,where Ni, Nr, Ns, and Nj are the node number. The total distance distpi,j of the evacuation path pi,j is(5)distpi,j=∑t=ijwt,t+1,where wt,t+1 is the actual distance between node t and node t+1. The cost function of the dynamic optimization is to search for the paths that do not include the impassable nodes. Suppose the real-time impassable nodes set is IV, then the online optimization problem is as follows:(6)min∑t=ijwt,t+1,t∈V,t∉IV.Equation (6) is a constraint optimization problem; the optimization result pi,j only includes the safe and passable nodes. Suppose PNet is the prior evacuation path network, NBNode is the neighbor nodes of the impassable nodes in IV. The online optimization starts to search for the optimal paths when the PNet is not fit for the real-time situation, and the online optimization algorithm flow is shown as Algorithm 2.Algorithm 2: Online dynamic path optimization.
forp in PNetford inIVifpath p contains node dSNode ⟵ the first node of path pforNiinNBNodepNi,Ohis updated by the breadth-first search algorithmforNkinSNodeupdate the path ofDPNodeaspNk,Oh=pNk,Ni+pNi,Ohforp inDPNodeforNrin path pp ⟵ check the nodes aroundNrwhether p is the shortestreturnDPNodeThis paper uses the online dynamic optimization algorithm to search for the real-time optimal paths for the graph in Figure1. Suppose N7 is in the fire area and the impassable node set IV=N7. According to the dynamic optimization algorithm in Algorithm 2, the SNode stores the starting nodes of the prior paths that contains N7, and the nodes of SNode are as follows:(7)SNode1=N12,N13,N14,N17,N19,N20,N22,SNode2=N1,N2,N3,N4,N5,N6,N8,N9,N10,N11,N15,N16,SNode3=N1,N2,N3,N4,N5,N8,N9,N10,N11,SNode4=N1,N2,N3,N6,where SNodei contains the starting nodes of the prior paths that are from each node to Oi via N7. Because the paths from the nodes in SNode to exits are impassable, then these paths are adjusted dynamically. N3, N6, N8, and N14 are neighbor nodes of N7; then, the nodes of NBNode are as follows:(8)NBNode1=N14,NBNode2=N3,N6,N8,NBNode3=N3,N8,NBNode4=N6,where NBNodei contains the neighbor nodes of N7 in SNodei. Because the nodes of NBNode are around node N7, the paths from these nodes to the exits help the people to avoid the impassable node N7. We use the breadth-first search (BFS) algorithm to search for the optimal paths from the nodes of SNode to the exits. Since the paths from each node to the exits are stored in the prior evacuation network, the BFS gets the shortest path from a node when it visits the node. This prior evacuation path network reduces the search time significantly, and it only needs a little lookup time to get the path information when it visits a node. The BFS visits nodes of NBNode and checks whether the shortest paths contain impassable node. If path from node Nk to exit Oh does not contain the impassable node, then the new path from node Ni to exit Oh is updated as follows:(9)pNi,Oh=pNi,Nk+pNk,Oh,where node Ni∈SNode, Nk∈NBNode, and Oh is the exit node. The paths from nodes of SNode to the exit nodes are updated according to equation (9) step by step. Although the new paths avoid impassable node, some paths are not the shortest, and it is necessary to fine-tune the suboptimal paths. Suppose DPNode is the set of the new dynamic paths, and one of the new paths is(10)pNi,Oh=Ni,Nr,…,Nk,Nt,…,Nn,Oh,where Ni, Nr, …, Nn∉IV. Nodes around the node of pNi,Oh are used to check whether there is a much shorter path; if a node Nα around Nk satisfies the inequality as follows:(11)wNk,Nα+distNα,Oh<wNk,Nt+distNt,Oh,then the new shorter path is as follows:(12)p′Ni,Oh=pNi,Nα+pNα,Oh.The real-time information triggers the online dynamic optimization to search for the new shortest paths according to the above algorithm principle. In Figure1, suppose node N7 is in the fire area, there are 35 paths that contain N7. Different paths are shown in Figure 3. Path1 is the prior shortest evacuation path from node N6 to exit O2, Path2 is a feasible path that avoids node N7, and Path3 is the final shortest path obtained by global search. It takes 11 ms to update the shortest paths from nodes in SNode to the exits.Figure 3
The paths from nodeN6 to exit O2 updated by the proposed dynamic algorithm.


## 3.1. Offline Prior Evacuation Path Network

Before the fire accident, it is necessary to get the shortest evacuation path from each node to each exit for the building. This search is an offline process that uses the Dijkstra algorithm to get the prior evacuation path network that stores the node number of each evacuation path. The Dijkstra algorithm is a typical algorithm for searching the shortest path between nodes in a graph, and it has been widely used to search for the shortest evacuation paths in fire incidents. The flow of the standard Dijkstra algorithm is shown as Algorithm1. The operation u ← vertex in Q with min dist [u] means the algorithm searches for the vertex u in the vertex set Q that has the least distance. Operation lengthu,v returns the length of the edge connecting two adjacent nodes u and v.Algorithm 1: Offline evacuation path optimization.
create vertex setQfor each vertex v in Graph:dist [v]  ⟵  Infinitypath [v]  ⟵  Undefinedaddv to Qdist [source]  ⟵  0whileQ is not empty:u  ⟵  vertex in Q with min dist [u]removeu from Qfor each neighbor v of u:expand  ⟵  dist [u] + length (u, v)if expand < dist [v]:dist [v]  ⟵  expandpath [v]  ⟵  ureturn dist [], path []The variableexpand is the length of the path from the source node to the node v via u. The principle used to determine whether the node v satisfies the slack condition is as follows:(2)du,v>du,q+dq,v,where du,v is the distance between node u and node v. Equation (2) shows that the distance from node u to node v via node q is shorter than the old distance between node u and node v, and then the path pu,v is updated as follows:(3)pu,v=u,q,v.According to the Dijkstra algorithm, we get the evacuation path network of the building shown in Figure1. The network includes the shortest path from each node to each exit. Since the network is too large to display, Table 2 describes the nodes from node 3 to the four exits and the paths are shown in different colors in Figure 2. If people are at node N3, they will use the information shown in Table 2 to quickly escape to the safety exit, so this network is the prior information for the people to escape. When the fire environment is the same as the offline optimized hypothetical environment, people can move according to the prior evacuation network.Table 2
Evacuation paths from node 3 to the exits.
Start node and exit nodeShortest pathDistance (m)N3-O1N3,N4,N5,O140N3-O2N3,N7,N14,O219N3-O3N3,N7,N14,O2,N17,N20,N21,O3160N3-O4N3,N7,N14,O2,N17,N18,O4158Figure 2
The paths from node 3 and node 8 to different exits in the prior evacuation network.


## 3.2. Online Local Path Optimization

The location and time of the fire are unpredictable; the distribution of people inside the building is also changing. The prior evacuation network needs to be modified when some edges are blocked or in a dangerous area. This modification only adjusts the nodes of the paths that are affected by the fire, and it is a local path optimization based on the prior evacuation network. Because the fire is changing during the evacuation, then the online local path optimization keeps searching for the new solutions. In the network graph modelG=V,E,W, the evacuation path pi,j from the start node i to the end node j is as follows:(4)pi,j=Ni,Nr,…,Ns,Nj,where Ni, Nr, Ns, and Nj are the node number. The total distance distpi,j of the evacuation path pi,j is(5)distpi,j=∑t=ijwt,t+1,where wt,t+1 is the actual distance between node t and node t+1. The cost function of the dynamic optimization is to search for the paths that do not include the impassable nodes. Suppose the real-time impassable nodes set is IV, then the online optimization problem is as follows:(6)min∑t=ijwt,t+1,t∈V,t∉IV.Equation (6) is a constraint optimization problem; the optimization result pi,j only includes the safe and passable nodes. Suppose PNet is the prior evacuation path network, NBNode is the neighbor nodes of the impassable nodes in IV. The online optimization starts to search for the optimal paths when the PNet is not fit for the real-time situation, and the online optimization algorithm flow is shown as Algorithm 2.Algorithm 2: Online dynamic path optimization.
forp in PNetford inIVifpath p contains node dSNode ⟵ the first node of path pforNiinNBNodepNi,Ohis updated by the breadth-first search algorithmforNkinSNodeupdate the path ofDPNodeaspNk,Oh=pNk,Ni+pNi,Ohforp inDPNodeforNrin path pp ⟵ check the nodes aroundNrwhether p is the shortestreturnDPNodeThis paper uses the online dynamic optimization algorithm to search for the real-time optimal paths for the graph in Figure1. Suppose N7 is in the fire area and the impassable node set IV=N7. According to the dynamic optimization algorithm in Algorithm 2, the SNode stores the starting nodes of the prior paths that contains N7, and the nodes of SNode are as follows:(7)SNode1=N12,N13,N14,N17,N19,N20,N22,SNode2=N1,N2,N3,N4,N5,N6,N8,N9,N10,N11,N15,N16,SNode3=N1,N2,N3,N4,N5,N8,N9,N10,N11,SNode4=N1,N2,N3,N6,where SNodei contains the starting nodes of the prior paths that are from each node to Oi via N7. Because the paths from the nodes in SNode to exits are impassable, then these paths are adjusted dynamically. N3, N6, N8, and N14 are neighbor nodes of N7; then, the nodes of NBNode are as follows:(8)NBNode1=N14,NBNode2=N3,N6,N8,NBNode3=N3,N8,NBNode4=N6,where NBNodei contains the neighbor nodes of N7 in SNodei. Because the nodes of NBNode are around node N7, the paths from these nodes to the exits help the people to avoid the impassable node N7. We use the breadth-first search (BFS) algorithm to search for the optimal paths from the nodes of SNode to the exits. Since the paths from each node to the exits are stored in the prior evacuation network, the BFS gets the shortest path from a node when it visits the node. This prior evacuation path network reduces the search time significantly, and it only needs a little lookup time to get the path information when it visits a node. The BFS visits nodes of NBNode and checks whether the shortest paths contain impassable node. If path from node Nk to exit Oh does not contain the impassable node, then the new path from node Ni to exit Oh is updated as follows:(9)pNi,Oh=pNi,Nk+pNk,Oh,where node Ni∈SNode, Nk∈NBNode, and Oh is the exit node. The paths from nodes of SNode to the exit nodes are updated according to equation (9) step by step. Although the new paths avoid impassable node, some paths are not the shortest, and it is necessary to fine-tune the suboptimal paths. Suppose DPNode is the set of the new dynamic paths, and one of the new paths is(10)pNi,Oh=Ni,Nr,…,Nk,Nt,…,Nn,Oh,where Ni, Nr, …, Nn∉IV. Nodes around the node of pNi,Oh are used to check whether there is a much shorter path; if a node Nα around Nk satisfies the inequality as follows:(11)wNk,Nα+distNα,Oh<wNk,Nt+distNt,Oh,then the new shorter path is as follows:(12)p′Ni,Oh=pNi,Nα+pNα,Oh.The real-time information triggers the online dynamic optimization to search for the new shortest paths according to the above algorithm principle. In Figure1, suppose node N7 is in the fire area, there are 35 paths that contain N7. Different paths are shown in Figure 3. Path1 is the prior shortest evacuation path from node N6 to exit O2, Path2 is a feasible path that avoids node N7, and Path3 is the final shortest path obtained by global search. It takes 11 ms to update the shortest paths from nodes in SNode to the exits.Figure 3
The paths from nodeN6 to exit O2 updated by the proposed dynamic algorithm.


## 4. Simulation Results and Analysis

The more nodes in the network model, the more time it takes to search for evacuation paths in real-time. This paper establishes a network model with 2000 nodes to compare the performances of the proposed dynamic optimization and the traditional Dijkstra algorithm. Suppose the set of safe exit nodes isO=N7,N77,N777 and each node has two edges connecting to other nodes, the weight of each edge is randomly assigned a positive value between 0 and 100.Let nodeN18 be in the fire area; both the proposed dynamic algorithm and the Dijkstra algorithm are used to search for the shortest paths from node N1225 to exit N7 and N777. The path optimization results are shown in Table 3. The M1 is the method that uses the Dijkstra algorithm to search for the shortest path offline. M2 and M3 are the methods that use the proposed dynamic algorithm and the Dijkstra algorithm to search for the shortest path according to the real-time information as node N18 is in the fire area. M2 and M3 are online searching that avoid passing through node N18. The results show that the evacuation paths of the online searching algorithms are longer than those of the offline algorithm; this difference is due to the fact that the online search algorithms need to avoid node N18. M2 gets the same path as M3 in online path searching, and it shows that the proposed dynamic algorithm has the ability to get the shortest path.Table 3
Evacuation paths of different algorithms.
Start-endMethodEvacuation pathDistanceN1225–N7M1{N1225,N564,N18,N1587,N113,N1210,N653,N1030, N334,N1503,N51,N1289,N1201,N7}291M2N1225,N1631,N801,N979,N1668,N1580,N432,N1218,N7N1218,N7324M3N1225,N1631,N801,N979,N1668,N1580,N432,N1218,N7N1218,N7324N1225–N777M1N1225,N564,N18,N474,N761,N558,N777234M2N1225,N564,N1372,N607,N895,N1938,N197,N777279M3N1225,N564,N1372,N607,N895,N1938,N197,N777279The node fromN1 to N200 is set as a fire point step by step, and the curve of the number of nodes in SNode is shown in Figure 4. Different nodes cause different sizes of SNode, and the online searching time is also shown in Figure 4. The curves in Figure 4 show that the online searching time is positively correlated with the size of SNode.Figure 4
The performance of the proposed dynamic algorithm: (a) relationship between the size of SNode and node number; (b) relationship between the searching time and the node number.
(a)(b)With the same nodes inSNode, this paper compares the online searching time of the proposed dynamic algorithm with that of the Dijkstra algorithm, and the results are shown in Figure 5. The comparison result shows that the proposed dynamic algorithm searches much faster than the Dijkstra algorithm all the time. The Dijkstra algorithm executes a global optimization when facing a new order to search for a path from the node in SNode to the exit; it takes a long time to find out the shortest path. The proposed dynamic algorithm takes advantage of the prior evacuation path and only visits the nodes around the fire area to get the local shortest paths. Because the proposed dynamic algorithm does not search each node of the model, it is more effective than the Dijkstra algorithm. Let tp denote the online searching time of the proposed dynamic algorithm and td denote the online searching time of the Dijkstra algorithm; the ration of tp to td is also shown in Figure 5. The maximum ratio is 0.92, and the minimum ratio is 0.02, and there are some ratios that have a value of 0 since they have no node pass through the fire area. At node N51, there are 256 paths that need to be modified and the ratio is 0.1. At node N35, there are 178 paths that need to be modified and the ratio is 0.05. It is efficacious to use the proposed dynamic algorithm as there are many nodes in the SNode.Figure 5
The performance comparison between the proposed dynamic algorithm and the Dijkstra algorithm: (a) comparison of the searching time; (b) ratio oftp to td.
(a)(b)


## 5. Conclusions

The prior evacuation paths are inefficient when the situations are different from the prospective environments. It takes a long time to search for the shortest paths from each node to the exits, and it is unsuitable for online searching. The proposed dynamic algorithm adjusts the prior paths that pass through the fire areas according to the situations. Because the proposed method takes advantages of the prior evacuation path network, it visits the nodes around the fire area to get the path information instead of searching each node of the model. It modifies the paths that pass through the fire areas in a short time, and each path is the shortest one from itself to the exit. The proposed dynamic algorithm is suitable for the online evacuation path optimization because of its fast convergence and global searching.



---

*Source: 3017607-2021-08-03.xml*