# Dynamic Sign Guidance Optimization for Crowd Evacuation considering Flow Equilibrium

Authors: Minghua Li; Chengyong Xu; Yan Xu; Li Ma; Yun Wei
Journal: Journal of Advanced Transportation
 (2022)

---

## Abstract

The dynamic exit sign has been verified as an effective means to guide the pedestrian during evacuation. The most critical mechanism with dynamic exit sign guidance is to balance the pedestrian flow on each exit route by optimizing the direction of signs. This paper formulates a bi-level programming model for the direction optimization problem of dynamic signs in buildings. In the bi-level program, the upper-level model is a system optimal model, aiming to minimize the total travel time by optimizing the dynamic sign direction. The lower-level model is a pedestrian assignment model satisfying the dynamic user optimal principle that describes the evacuee exit/route choice behaviour to achieve a balanced pedestrian distribution on the route. A method based on the fundamental diagram, the cell transmission model, and the point-queuing theory is developed to estimate evacuation travel time considering congestion and queuing. A heuristic algorithm is extended to solve the bi-level program. Finally, the proposed methodology is validated with numerical examples. Results reveal that the proposed model can produce the optimal dynamic sign direction, significantly improving the evacuation efficiency.


---

## Body

## 1. Introduction

Exit signs in buildings can help people find escape routes and emergency exits quickly, thus reducing evacuation time and the risk of casualties. Therefore, exit signs are widely used in buildings, especially in large public places with complex layouts such as transportation hubs, stadiums, and theatres. Most exit signs, which point to the nearest exit with a fixed arrow, operate in a Static Sign Guidance (SSG) mode. However, this SSG mode may have two negative impacts. First, the SSG will introduce evacuee into the dangerous zone if the waypoint in the direction of the sign has fire hazards. Second, without considering the crowd distribution, the SSG always guides people through the shortest route to the same exit. Consequently, this may lead to congestion at that exit and slow down the whole evacuation process, whereas other viable exits remain virtually unused.To overcome the inherent defects of SSG, researchers have developed Dynamic Sign Guidance (DSG) systems with direction-variable exit signs that can change their arrow direction [1–3]. The DSG system can guide people away from hazardous areas with the help of fire detectors, which can effectively eliminate the first negative impact of SSG [1]. Hence, we are more concerned with how to eliminate the second negative impact. Specifically, we focus on how to guide evacuees to appropriate routes considering the crowd distribution to reduce congestion. An approach is to reroute evacuees through DSG to ensure that all exits and routes are fully utilized during the evacuation process [4]. This full utilization is consistent with Francis’ fundamental “Uniformity Principle” which states that if the building is evacuated in minimum time, then the allocation of evacuees to routes is such that the route evacuation times are all the same [5]. In this case, the flow on the evacuation route is in a traffic equilibrium state. That is, we should guide evacuees through DSG with the aim of achieving a flow equilibrium state on the evacuated route to minimized evacuation time.In the DSG system, the guidance of the crowd flow on the evacuation route relies on the redirection of exit signs. Hence, the optimization of exit sign direction is very important to achieve the guidance of a flow equilibrium state. However, not much research has been done on the optimization of exit sign directions considering flow equilibrium. Some of the existing studies related to exit sign direction use only path distance as route metric for direction optimization and ignore the crowd distribution, much less the flow equilibrium state [4, 6–11]. Another part of the research considered a balanced assignment of evacuation flow using metric that reflects the travel cost of the route, including route flow [12, 13], density [2], flow to capacity ration of route [4], and travel time [14]. Then the exit sign direction is determined based on the optimal route in flow equilibrium state. However, this two-stage approach, which separates the equilibrium allocation of evacuated flows from the solution of exit sign direction, is not applicable to the dynamic sign-guided modes. The reason is that in a dynamic sign-guided approach, the adjustment of the exit sign direction implies a reconfiguration of evacuation network topology. This reconfiguration affects the route selection behaviour of evacuated individuals, which in turn leads to the redistribution of evacuee. The redistribution of evacuee crowd can destabilize the flow equilibrium state, which can make a mistake in solving the optimal route in the equilibrium state. That is, the adjustment of dynamic sign direction can break the flow equilibrium state and impact the route optimization. Therefore, we believe that the flow equilibrium assignment of the evacuation network and the optimization of the exit sign direction should be considered together, instead of being calculated separately in two stages. However, to the best of our knowledge, there are few studies that combine these two aspects.For closing this gap, we will study both exit sign direction optimization and flow equilibrium assignment of the evacuation network from the perspectives of both evacuation managers and evacuees. During evacuation, managers and evacuees have different optimization goals. The manager hopes to guide evacuees towards the uncrowded route by pointing exit signs to minimize the total evacuation cost. With the manager’s evacuation guidance, evacuees will choose the shortest route to evacuate, resulting in a different evacuee flow distribution than the manager expects. This difference may lead to an increase in the total evacuation cost. In this case, the sign should be redirected to reach the optimal goal of the system. Considered the above two perspectives, dynamic sign direction optimization and flow equilibrium assignment involve a game between managers and evacuees. To reflect the game, we committed to formulating a bi-level programming model for dynamic sign direction optimization of buildings in this study. This model also takes account the evacuee flow equilibrium assignment as well. Specifically, the upper-level model takes the exit sign direction as the decision variable from the manager’s perspective and the minimum total evacuated cost as the optimization objective. In the lower-level model, a dynamic pedestrian assignment (DPA) model consistent with the dynamic user optimum (DUO) principle is extended to describe individuals’ route choice behaviour to achieve an equilibrium distribution of evacuees on the route.The contributions of this paper are as follows:(1)
A new directed graph-based model: in this paper, the evacuation scene is divided into multiple grids, each of which is assumed to have an exit sign. Based on this, a directed graph-based model is conducted. The grid denotes the directed arc of the graph model and the neighbouring edges between the grids as the nodes of the graph model. The pointing of the exit sign in the grid equals to of the direction of the arc in the directed graph. Thus, the optimization of the exit sign direction can be transferred to the optimization of the arc direction in the directed graph-based model.(2)
A new approach of pointing exit signs based on the bi-level programming model: since few studies have focused on individual guidance to a balanced evacuation among multiple exits and routes through exit sign changes, the model in this paper can bridge this gap. A bi-level programming model is proposed, in which the upper-level model takes the exit sign direction as the decision variable and the lower-level model is a DPA model satisfying a DUO criterion. As a result, the exit sign direction can be solved explicitly for balanced evacuation guidance.(3)
A new method for calculating the travel time of evacuation routes: the travel time of an evacuation route is a basic measure of the number of evacuees allocated on that route. This metric ensures a balanced assignment of flows in the evacuation network. In this paper, we propose a method for calculating route travel time based on a cell transmission model. The method is able to calculate not only the delay time caused by congestion, which is considered by traditional methods, but also the queuing waiting time, which is not considered by traditional methods.The rest of this paper is organized as follows. Section2 surveys the works related to exit sign guidance optimization. Section 3 provides the model for dynamic sign direction optimization. A heuristic solution-combined genetic algorithm with a route-swapping algorithm was developed in Section 4. A set of numerical experiments are given in Section 5 to verify the effectiveness of the approach. Section 6 concludes the paper.


## 2. Related Work

A review of intelligent evacuation system can be found in literature [15]. According to the guidance approach, the intelligent evacuation system can be divided into dynamic signs, trained leaders, robots, and mobile devices [15]. However, the guidance approach with trained leaders, robots, and mobile devices still have some problems. In the case of leaders, it is difficult for leaders to maintain an accurate situation awareness of disasters and crowd distribution. But without these real-time dynamic information, leaders still struggle to fully address misdirection to dangerous or congestion area. Obviously, trained leaders can reduce the response time to evacuation warning and better guide the evacuation process [16]. However, trained leaders cannot be located everywhere throughout the building and they may not be able to reach the crowd quickly enough [17]. Temporary opinion leaders may be generated in the crowd. However, studies show that temporary opinion leaders do not always have sufficient influence on crowd, which reduces evacuation efficiency [18]. As far as robots are concerned, the application of robots in evacuation guidance is not yet mature. Issues such as high economic costs and restriction on application scenarios all limit the application of robots [15]. In addition, there may be problems with human trust in robot guidance, which can affect the effectiveness of evacuation guidance [19]. The effectiveness of mobile devices was verified in an experimental environment. During the experiments, most of the studies assume that each evacuee possesses a handheld communication device, like a smartphone or a wristband [13, 20]. The application on the smartphone is able to display the structure of evacuation scenarios and receive route information delivered from wireless sensor networks. However, we argue that the use of such device is impractical. For example, in public places such as stations and airports, prior installation of the application is not guaranteed for everyone.The exit sign is commonly used worldwide and is accustomed by users. It can be preinstalled and seen by each evacuated individual. These advantages have prompted researchers to pay attention to the dynamic exit sign [1–3]. Depending on the message conveyed, dynamic exit signs can be divided into two types: negative signs and positive signs. The negative sign shows a flashing red cross on the exit sign for displaying dissuasive message that a certain egress direction is not available [21]. Surveys [22, 23] and simulation [24–27] revealed that negative signs can significantly prevent evacuees from approaching hazardous areas compared to static sign. The positive signs display a recommendation message, that is, which exit route is better for the evacuee. Specifically, the positive signs designed with two arrows in opposite directions, which is different from traditional exit signs that have only one arrow. One of the two arrows is highlighted to indicate the recommended exit route direction. In particular, the highlighted arrow can be modified at any time according to the evacuation status. As a result, the dynamic exit sign can provide time-variable evacuation guidance to the crowd. A survey showed that the recommended information from positive signs is more useful than the prohibited information from negative signs [28]. Therefore, positive signs, as the main display terminal of Dynamic Sign Guidance (DSG) systems, are the subject of this paper.Exit sign direction optimization is a central issue for DSG systems. The available studies on the optimization of exit sign direction are mainly classified into the following three methods. The first method is based on static network shortest route optimization [6, 7, 10, 11], where researchers proposed several exit sign direction setting approaches with shortest route algorithms based on indoor navigation graph networks. The second method is based on dynamic network flow optimization [29–31]. Researchers calculated the optimal route from the evacuation origin to the exit in a time-space network using maximum flow models. The direction of each arc in that optimal route is used as the direction of the sign. The third method is based on evacuation simulation for exit choice. Several simulation models, such as cell automate [22], floor field [14, 32], and agent-based models [33, 34], were proposed for predicting the egress time of agents to multiple exits. Depending on the egress time, the sign at the agent’s location was set to point to the nearest exit. In general, the above methods took the direction of the edge in the optimal route as the exit sign direction based on the immutable network topology, and these methods are reasonable for static signs with fixed direction. However, in the DSG system, the network topology will change with the dynamic sign direction, which affects the optimal routes. As a result, to optimize dynamic sign direction, both the optimal evacuation route and the network topology change brought by sign direction adjustments should be considered.Fortunately, similar studies considering both network topology and route flow optimization have been conducted in regional evacuation guidance on road networks. These studies treat large-scale evacuation guidance as a network design problem [35, 36] or a one-way organization optimization problem [37] and proposed several bi-level programming models for these problems. In their bi-level programming models, the direction of each edge in the evacuation network was the decision variable for the upper-level model, and the route flow was the decision variable for the traffic assignment model that serves as the lower-level model. Consequently, the bi-level programming model could optimize both the traffic flow to the shortest route and the driving direction of roadway segments, which was precisely suitable for optimizing dynamic sign directions.However, there are still two flaws in our knowledge of applying these bi-level programming models for the dynamic sign direction optimization problem in buildings. The first one is that most lower-level models employ static user equilibrium models, which were usually conducted to describe the route choice behaviour of travellers in long-term planning problems such as road network planning. Hence, it was unsuitable for the dynamic process of evacuation due to the dynamic route choice behaviour of pedestrians. Thus, to better describe dynamic characteristics of pedestrians in evacuation, the dynamic user optimal (DUO) principle and the corresponding dynamic pedestrian assignment (DPA) model were proposed [38]. Just as dynamic traffic assignment models in road traffic flow, the DPA model could be divided into two categories, predictive and reactive, according to the different calculations of route evacuation time cost. The predictive model assumed that pedestrians could accurately predict evacuation times by considering future situation changes with their experience. The reactive model assumed that pedestrians would estimate the instantaneous egress time of the route based on the immediate collected information and choose a suitable route accordingly. Due to the dynamic feature of evacuation, it is difficult for pedestrians to predict the egress time accurately. Hence, the assumption of the reactive model is more consistent with the evacuation behaviour of pedestrians. Therefore, a reactive DPA model conforming to the DUO principle should be adopted in the lower-level model to describe the dynamic route selection behaviour of pedestrians.The second flaw concerns the route travel cost. As mentioned above, the route travel cost is the basis of the DPA model, which ensures a well-balanced distribution of pedestrian flow on each route. Existing studies on DSG have proposed various indicators of route travel costs, including distance [1, 7], travel time [2, 3, 6, 10], level of service [2, 11], hazard level [7], and individual congestion-awareness [39]. Among them, level of service, hazard level, and individual congestion-awareness rely on personal subjective judgments. Distance, on the other hand, although relatively objective, does not reflect the congestion impact of the route. Therefore, travel time has been widely used as a measure of route travel cost. However, most of the current travel time calculations adopt network-based flow methods, which can only reflect the time delay caused by congestion, but not the queuing time that would account for a large portion of the egress time [40]. While simulation-based methods can estimate the queuing time by simulating individual interactions, they suffer from computational costs. Guo et al. [33] established an iterative approach that can balance accuracy and computational efficiency based on a cell transmission model to calculate route travel time. However, this approach, which uses a spatial-potential field to define the virtual shortest route and calculate the travel cost, lacks an explicit queuing time expression. Nevertheless, the cell transmission model inspires us to bridge the gap between computational accuracy and efficiency.


## 3. Methodology

### 3.1. Problem Statement

Unlike the static sign with only a one-directional arrow, the dynamic sign considered in this paper has two arrows in opposite directions. Each arrow can be lit or off, thus indicating three states, namely, (1) one lit arrow guides to the left; (2) the other lit arrow guides to the right; and (3) both arrows are extinguished, that is, the sign does not guide pedestrians, as shown in Figure1, respectively. In the first two states, pedestrians should move according to the arrow pointing. In the third state, the sign has no direction, and pedestrians can move on their own according to the current speed direction.Figure 1
Dynamic sign with different guidance direction. Figure (a) denotes a guidance to the left with green arrow, Figure (b) denotes a guidance to the right with green arrow, and Figure (c) denotes no guidance.
(a)(b)(c)To better describe the decision behaviour of pedestrians in evacuation, we discretize the evacuation area into regular grids. Each grid can accommodate a certain number of pedestrians, and the pedestrians can move towards adjacent grids. The grids are used to construct a network representing the walkable areas and obstacles. Grids are used to calculate roadway travel times and thus determine the dynamic route choice of individuals. The size of the grid cannot be smaller than the distance travelled by pedestrians at free-walking speed in one-time step; otherwise, it cannot reflect the route choice behaviour provoked by the variability of pedestrian density in different grids. Too small a grid size also leads to a computational burden due to the large size of the evacuated network. The grid size should also not be too large in order to ensure the computational accuracy of the grid’s travel time. In order to balance the computational efﬁciency with accuracy requirements of travel time calculation, the length and width of each grid ranges from 1 m to 3 m.It is assumed that each grid has a dynamic sign to direct the movement of pedestrians. According to the adjacency relationship between the grids and the guided direction of signs, the walkable space with discrete grids can be converted into a directed network. Figure2 shows the indoor area with different sign directions and its corresponding directed network.Figure 2
The discretization of space with sign direction and its corresponding directed network. Figure (a) and (c) are the same discrete space with different sign directions, and Figure (b) and (d) are directed networks corresponding to Figure (a) and (c), respectively. In Figure (c), the sign direction in grid B and grid C points in the opposite direction compared with Figure (a). Accordingly, the corresponding directed network is reformed from Figure (b) to Figure (d) by changing the arc direction between node 13, node 14, and node 10.
(a)(b)(c)(d)As shown in Figure2(a), gray grids are obstacles, and blank white grids denote the walkable area. The neighbouring edge of two adjacent blank grids numbered in Figure 2(a) is regarded as a node in the directed network in Figure 2(b). The arrow in the blank grid, indicating the sign direction, is viewed as a directed arc between two nodes. As a result, the walkable space in Figure 2(a) can be transformed into the directed network in Figure 2(b). Besides, it should be noted that there is no arrow in grid A in Figure 2(a), which indicates that the sign of grid A is in the third state as described in Figure 2(c), and pedestrians in grid A can move towards the neighbouring edges 11 and 12. Therefore, the directed arc between nodes 11 and 12 in Figure 2(b) should be a bi-directional arc. If the sign direction in the grid is changed, the corresponding directed network will also be reformed. For example, the sign direction of grid B and grid C in Figure 2(a) is adjusted to the opposite direction, as shown by the red bold arrow of grid B and grid C in Figure 2(c). Then the directed arc between node 13, node 14, and node 10 in Figure 2(b) will also change, as shown by the red arrows in Figure 2(d). By this method, the optimization of the dynamic sign direction can be converted into the optimization of the network topology.For a better formulation, there are two assumptions as follows:(1)
Pedestrians are familiar with all sign directions and will comply with DSG.(2)
Pedestrians can estimate travel time on all available routes based on the pedestrian flow on each route.For the room with complex layouts and multiple exits, the walkable space is divided into several grids to form an evacuation networkH=HR, where R is the set of blank grids. Let D be the set of exit grids and Ri be the set of neighbour grids of grid i, then we have D⊂R and Ri⊂R. The evacuation period 0,T is divided into kmax time intervals by time duration Δt, so we have T=Δt×kmax and the set of time intervals is K=1,2,…,k…,kmax.For the convenience of readers, the primary notation is described in Table1.Table 1
: Temperature and wildlife count in the three areas covered by the study.
SymbolDefinitionnikThe number of people in gridi during time interval k.nijkThe number of people in gridi who choose to move to grid j during time interval k, where j∈Ri.nji,dkThe number of people in gridi who choose to exit d with passing through grid j during time interval k, where j∈Ri.cji,dkThe travel time for people in gridi to pass through grid j and eventually evacuate from exit d during time interval k, where j∈Ri (unit: s).cpi,dkThe travel time for people in gridi selecting route p to exit d during time interval k (unit: s).fpi,dkThe number of people in gridi selecting route p to exit d during time interval k.tijkThe estimated travel time for people in gridi moving into grid j during time interval k, where j∈Ri (unit: s).tij0The expected travel time for people in gridi moving into grid j with free flow velocity during time interval k, where j∈Ri (unit: s).ψji,dkThe minimum travel time for people in gridi moving from grid j to the queue tail at exit d during time interval k, where j∈Ri (unit: s).tji,dkThe minimum travel time for people in gridi moving to the queue tail at exit d by passing through grid j during time interval k, where j∈Ri.πpkThe minimum evacuation travel time of people selecting routep during time interval k.πikThe minimum evacuation time of people in gridi during time interval k.LijThe moving distance for people in gridi moving to grid j during time interval k, where j∈Ri.qdklThe queue length of exitd, which is predicted during time interval k, for the people arrives at exit d at the time interval l, where l≥k.ξj,ki,dlBinary variables and pedestrians in gridi choose exit d to evacuate by passing through grid j during time interval k; if the pedestrians can arrive exit d during time interval l, we have ξj,ki,dl=1, otherwise 0, where j∈Ri.ρikThe pedestrian density in gridi during time interval k (unit: persons per square meter).ρmaxAccording to the literature [41], the maximum pedestrian density is set at 5.4 persons per square meter for safety.EjkThe maximum number of people who allowed to moving into gridj during time interval k, that is, the acceptance capacity of grid j, where j∈Ri.YijkThe maximum number of people who can move from gridi to grid j during time interval k, that is, the output capacity of grid i to grid j, where j∈Ri.pijkThe ration of people moving into gridj who are from grid i during time interval k, where j∈Ri.QijThe through capacity between gridi and grid j; it set Qij=2.0734×llength−0.5901 according to the literature [38], where j∈Ri and llength denotes the length of neighbour edge between grid i and grid j.SijkThe transmission capacity for people who move from gridi to grid j during time interval k, where j∈Ri.MiThe area of gridi (unit: square meter).xijBinary variables, whether the dynamic sign guide in gridi points to grid j


### 3.2. The Upper-Level Optimization Model

The decision variable in the upper-level model is the dynamic sign direction in each grid, which is set as a binary variablexij (i∈R, j∈Ri), indicating whether the dynamic sign direction in grid i points to grid j:(1)xij=1,if the sign  of gridipoints  to  gridj,0,otherwise.The objective of the evacuation manager’s decision in the upper-level model is to minimize the total evacuation cost of the system to reduce network-wide congestion. According to the system-optimization program, withxij as the decision variable to minimize the total travel cost, the upper-level model is formulated as equations (1)–(5).(2)minZ=∑i∈R∑j∈Rtijxij,ρik,knijk,(3)s.t∑j∈Rixij≤1,∀i∈R,(4)xij+xji≤1,∀i∈R,j∈Ri,(5)xij∈0,1,∀i∈R,j∈Ri,where equation (2) is the objective of minimizing the total travel cost. In this paper, travel time is chosen as travel cost. In equation (2), tijxij,ρik,k is the link travel time for pedestrian from grid i to j, and it is a function of xij and ρik, where xij is determined by the upper-level model and ρik is obtained from the lower-level model. tijxij,ρik,k is abbreviated as tijk in following context and its specific calculation procedure is detailed in Section 3.4.Constraint (3) ensures that the sign cannot point in more than one neighbouring grid simultaneously. If∑j∈Rixij=1, it means that the sign in grid i will point to one of its neighbour grid j, and all pedestrians in grid i should move according to its guidance direction. In this case, grid i can be regarded as a one-way grid and defined as a directed grid in this paper. If ∑j∈Rixij=0, it means that there is no directional guidance in grid i, and all pedestrians in that grid can move according to their current routes, that is, their moving directions may not all be the same. In this case, grid i can be regarded as a nondirectional grid and defined as an undirected grid in this paper.Constraint (4) guarantees that two dynamic signs in two adjacent grids cannot point to each other simultaneously. Constraint (5) represents that the decision variable xij are binary variable.


### 3.3. The Lower-Level Dynamic User Optimization Model

According to the assumptions above, with sign directions obtained by the upper-level model, individuals desire to evacuate as quickly as possible along the route with the shortest travel time. However, it is challenging to predict the travel time of all routes exactly. Hence, the instantaneous travel time of each route estimated by pedestrians is taken to assess the shortest route in the lower-level model. Then the system will reach a reactive DUO equilibrium state when everyone chooses the route with the minimum travel time, and no one would be better by unilaterally changing his/her route. In this situation, the instantaneous travel time of all selected routes is equal and minimum. In contrast, that of all unselected routes is not less than the minimum instantaneous evacuation travel time. Namely, with the reactive DUO equilibrium state, if pedestrians in gridi choose evacuation route p toward exit d during time interval k, that is, fpi,dk>0, it means the evacuation route p has the minimum instantaneous evacuation travel time. Otherwise, fpi,dk=0 indicates that the evacuation travel time on route p is not less than the minimum evacuation travel time, and no one chooses that route. Therefore, we have the following expression.(6)cpi,dk=πpk,iffpi,dk>0,≥πpk,iffpi,dk=0.where cpi,dk is the time for pedestrians in grid i selecting route p to exit d and πpk is the minimum evacuation time of pedestrians on route p during the time interval k.Equation (6) can be equivalently expressed as a nonlinear complementarity problem (NCP) as follows [38].(7)fpi,dkcpi,dk−πpk=0,∀i∈R,d∈D∑d∑pfpi,dk=nik,∀i∈R,d∈D,cpi,dk−πpk≥0,∀i∈R,d∈D,fpi,dk≥0,∀i∈R,d∈D.Since equation (7) is a route-based model, all the routes from each grid to each exit should be enumerated, which is relatively inefficient to solve. Therefore, we reformulate equations (6) and (7) by transferring the route-based model to grid-based through the method developed in literature [38]. We assume that when a pedestrian in grid i chooses a certain shortest route p to exit d, it must first pass through its neighbour grid j, as shown in Figure 3. According to equation (6), if the travel time of route p is equal to the minimum travel time, we have fpi,dk>0 and nji,dk>0, where nji,dk is the number of pedestrians in grid i that choose to exit d with passing grid j. Otherwise, we have fpi,dk=0 and nji,dk=0 when the travel time of route p is not the minimum travel time. Hence, the travel time for pedestrians in grid i passing grid j to exit d is(8)cji,dk=πik,ifnji,d>0,≥πik,ifnji,d=0.Figure 3
The shortest route was chosen by a pedestrian [38].Similarly, the grid-based reactive DUO condition of equation (8) can also be rewritten as the following equivalent NCP formulation.(9)npi,dkcpi,dk−πpk=0,∀i∈R,j∈Ri,d∈D,∑j∈Ri∑d∈Dnpi,dk=nik,∀i∈R,cji,dk−πpk≥0,∀i∈R,j∈Ri,d∈D,npi,dk≥0,∀i∈R,j∈Ri,d∈D.To solve equation (9), we can equivalently restate it as a Variational Inequality (VI) problem. Let Ω=∑j∑dnji,dknik,nji,dk≥0,∀i∈R,j∈Ri,d∈D as the feasible grid flows of equation (9), n=nji,dk as the dynamic pedestrian flow vector, and cn=cji,dk as the vector of instantaneous evacuation travel time, which is a function of n. Then if there is a vector n∗∈Ω, equation (9) is equivalent to the VI problem as follows:(10)cn∗,n−n∗≥0,∀n∈Ω.The solution of the VI problem satisfies the instantaneous dynamic user optimal condition. The proof can be seen in literature [42].


### 3.4. Calculation of Instantaneous Route Travel Time

To solve the above model, we need to estimate the evacuation travel time of each route firstly. As we consider the impact of pedestrian congestion on the grid and queuing at bottlenecks on the travel time, the travel time is consisting of (1) the minimum travel time for pedestrians to move from the current grid i through grid j to exit d during time interval k, denoted as tji,dk, and (2) queuing time at exit d, denoted as wdk, equation listed as(11)cji,dk=tji,dk+wdk.As shown in Figure3, tji,dk is calculated as follows.(12)tji,dk=tijk+ψji,dk,where ψji,dk can be calculated using the shortest route algorithm based on the travel time tmnk between the adjacent grid m and n which are the parts of the shortest route corresponding to ψji,dk. tijk is related to the sign direction, the pedestrian flow speed, and the transmission capacity of grids i and j. We will develop it in the following section.


#### 3.4.1. Calculation of Travel Time between Two Adjacent Grids

We estimate the travel time between adjacent grids based on a velocity-density relationship. The velocity-density function of the grid is first stated. According to the fundamental diagram of pedestrian flow, the pedestrian flow speeduik is a function of ρik in grid i. As stated in Section 3.2, a one-way pedestrian flow is formed in the directed grid with ∑j∈Rixij=1, while the pedestrian flow in different directions is formed in the undirected grid with ∑j∈Rixij=1. In the latter case, the multidirectional pedestrian flows may produce friction and congestion effects, reducing the pedestrian flow speed in each direction. As a result, the pedestrian flow speed in undirected grids would be lower than in directed grids under the same pedestrian density. Therefore, in this paper, uik should be revised as a function of ρik and xij. We adopt the pedestrian flow velocity-density function uρ=umax1−expβρ−1−ρmax−1 proposed by Weidmann [41] to fit uik in the undirected grids and the directed grids, respectively, where umax and β are the parameters to be calibrated, ρmax=5.4persons/m2. As in equation (13), if ∑j∈Rixij=1, uik in directed grids can refer to literature [41] with umax=1.34 and β=1.913. If ∑j∈Rixij=0, uik in undirected grids is obtained with umax=1.26 and β=1.63 by fitting the data in literature [43] with the least-squares method.(13)uik=1.261−exp−1.631ρik−15.4,if∑j∈Rixij=0,1.341−exp−1.9131ρik−15.4,if∑j∈Rixij=1.Next, the travel time of the grid is estimated based onuik and the pedestrian flow moving distance Lij. Without consideration of the transmission capacity limitations caused by the edge length difference between adjacent grids, the travel time tij′k from grid i to grid j can be calculated by the following equation (14). In equation (14), if ∑j∈Rixij=1 and xij=0, it means that grid i is a directed grid, but the sign in grid i does not guide to grid j. This indicates that pedestrians in grid i are not allowed to move to grid j. Therefore, tij′k=+∞.(14)tij′k=Lij1.261−exp−1.631/ρik−1/5.4,if∑j∈Rixij=0,Lij1.341−exp−1.9131/ρik−1/5.4,ifxij=1,+∞,if∑j∈Rixij=1andxij=0.To take the influence of pedestrian congestion on the evacuation travel time into account, we perform a cell transmission model of traffic flow to obtain a more accurate travel time. When pedestrians travel through grids, the transmission capacitySijk between grid i and j, j∈Ri, have a significant impact on the travel time. Figure 4 shows the factors influencing Sijk. As shown in Figure 4, Sijk is influenced by the output capacity of grid i to grid j (denoted by Yijk), acceptance capacity of grid j (denoted by Ejk), and the acceptance ration of grid j (denoted by pijk).(1)
Yijk is influenced by the number of pedestrians in grid i who plan to travel to grid j and the through capacity Qij between grid i and j. By definition, Yijk can be calculated by(15)Yijk=minnijk,Qij.(2)
Ejk is determined by the remaining capacity of grid j and the capacity of grid j to its neighbour grids. To ensure evacuation safety, we set the maximum pedestrian density in each grid as ρmax=5.4persons/m2; then the remaining capacity of grid j is ρmaxMj−njk. Then, we have(16)Ejk=minρmaxMj−njk,∑i∈RjQij.(3)
To simplify, the following formula is used to define the allocation ratiopijk, which denotes the proportion of pedestrians moving into grid j who are from grid i during time interval k,(17)pijk=Yijk∑i∈RjYijk.Figure 4
The influencing factors ofSijk.As shown in Figure4, the through capacity Sijk from grid i to grid j during time interval k can be obtained by the following equation,(18)Sijk=minYijk,pijkEijk=minnijk,Qij,pijkEijk.Hence, considering transmission capacity limitation and sign direction of gridi, the travel time from grid i to grid j during time interval k is(19)tijk=maxtij0,tij′k,nijkSijkΔt.


#### 3.4.2. Calculation of Queuing Time of Exit

During the evacuation, reduced capacity at bottlenecks, such as exits, can lead to queues. Queuing time is part of the evacuation travel time and can also affect the route choice of pedestrians. The queuing time is related to the number of people queuing at the exit and the exit width. Therefore, a point queuing model [44] is used to estimate the number of people in line around exits.By definition, at current time intervalk, if pedestrians can arrive at exit d during time interval l with travel time tji,dk, that is, l≤tji,dk+k<l+1, we have ξj,ki,dl=1, otherwise ξj,ki,dl=0.(20)ξj,ki,dl=1,ifl≤tji,dk+k<l+1,0,otherwise.Hence, in time intervall, the number of pedestrians in line at exit d is(21)qkdl=maxqkdl−1+∑i∑jnji,dkξj,ki,dl−ΔtQdo,,ifl≥k,0,otherwise,where Qdo is the through capacity between exit d and the adjacent virtual outside grid o.Since the time for pedestrians to reach the exit is not necessarily an integer interval, for simplicity, the queue length of two adjacent integer intervals is considered when calculating the queue length, and the linearization method in literature [45] is used to calculate the number of pedestrians queuing at the exit at the time l+μΔt, μ∈0,1, that is,(22)qkdl+μ=μqkdl+1−μqkdl+1.Hence, the queuing time at exitd during time interval k is(23)wdk=qkdk+tji,dkQdoΔt.After in all, the evacuation travel timecji,dk can be estimated by equation (11)–(23).


## 3.1. Problem Statement

Unlike the static sign with only a one-directional arrow, the dynamic sign considered in this paper has two arrows in opposite directions. Each arrow can be lit or off, thus indicating three states, namely, (1) one lit arrow guides to the left; (2) the other lit arrow guides to the right; and (3) both arrows are extinguished, that is, the sign does not guide pedestrians, as shown in Figure1, respectively. In the first two states, pedestrians should move according to the arrow pointing. In the third state, the sign has no direction, and pedestrians can move on their own according to the current speed direction.Figure 1
Dynamic sign with different guidance direction. Figure (a) denotes a guidance to the left with green arrow, Figure (b) denotes a guidance to the right with green arrow, and Figure (c) denotes no guidance.
(a)(b)(c)To better describe the decision behaviour of pedestrians in evacuation, we discretize the evacuation area into regular grids. Each grid can accommodate a certain number of pedestrians, and the pedestrians can move towards adjacent grids. The grids are used to construct a network representing the walkable areas and obstacles. Grids are used to calculate roadway travel times and thus determine the dynamic route choice of individuals. The size of the grid cannot be smaller than the distance travelled by pedestrians at free-walking speed in one-time step; otherwise, it cannot reflect the route choice behaviour provoked by the variability of pedestrian density in different grids. Too small a grid size also leads to a computational burden due to the large size of the evacuated network. The grid size should also not be too large in order to ensure the computational accuracy of the grid’s travel time. In order to balance the computational efﬁciency with accuracy requirements of travel time calculation, the length and width of each grid ranges from 1 m to 3 m.It is assumed that each grid has a dynamic sign to direct the movement of pedestrians. According to the adjacency relationship between the grids and the guided direction of signs, the walkable space with discrete grids can be converted into a directed network. Figure2 shows the indoor area with different sign directions and its corresponding directed network.Figure 2
The discretization of space with sign direction and its corresponding directed network. Figure (a) and (c) are the same discrete space with different sign directions, and Figure (b) and (d) are directed networks corresponding to Figure (a) and (c), respectively. In Figure (c), the sign direction in grid B and grid C points in the opposite direction compared with Figure (a). Accordingly, the corresponding directed network is reformed from Figure (b) to Figure (d) by changing the arc direction between node 13, node 14, and node 10.
(a)(b)(c)(d)As shown in Figure2(a), gray grids are obstacles, and blank white grids denote the walkable area. The neighbouring edge of two adjacent blank grids numbered in Figure 2(a) is regarded as a node in the directed network in Figure 2(b). The arrow in the blank grid, indicating the sign direction, is viewed as a directed arc between two nodes. As a result, the walkable space in Figure 2(a) can be transformed into the directed network in Figure 2(b). Besides, it should be noted that there is no arrow in grid A in Figure 2(a), which indicates that the sign of grid A is in the third state as described in Figure 2(c), and pedestrians in grid A can move towards the neighbouring edges 11 and 12. Therefore, the directed arc between nodes 11 and 12 in Figure 2(b) should be a bi-directional arc. If the sign direction in the grid is changed, the corresponding directed network will also be reformed. For example, the sign direction of grid B and grid C in Figure 2(a) is adjusted to the opposite direction, as shown by the red bold arrow of grid B and grid C in Figure 2(c). Then the directed arc between node 13, node 14, and node 10 in Figure 2(b) will also change, as shown by the red arrows in Figure 2(d). By this method, the optimization of the dynamic sign direction can be converted into the optimization of the network topology.For a better formulation, there are two assumptions as follows:(1)
Pedestrians are familiar with all sign directions and will comply with DSG.(2)
Pedestrians can estimate travel time on all available routes based on the pedestrian flow on each route.For the room with complex layouts and multiple exits, the walkable space is divided into several grids to form an evacuation networkH=HR, where R is the set of blank grids. Let D be the set of exit grids and Ri be the set of neighbour grids of grid i, then we have D⊂R and Ri⊂R. The evacuation period 0,T is divided into kmax time intervals by time duration Δt, so we have T=Δt×kmax and the set of time intervals is K=1,2,…,k…,kmax.For the convenience of readers, the primary notation is described in Table1.Table 1
: Temperature and wildlife count in the three areas covered by the study.
SymbolDefinitionnikThe number of people in gridi during time interval k.nijkThe number of people in gridi who choose to move to grid j during time interval k, where j∈Ri.nji,dkThe number of people in gridi who choose to exit d with passing through grid j during time interval k, where j∈Ri.cji,dkThe travel time for people in gridi to pass through grid j and eventually evacuate from exit d during time interval k, where j∈Ri (unit: s).cpi,dkThe travel time for people in gridi selecting route p to exit d during time interval k (unit: s).fpi,dkThe number of people in gridi selecting route p to exit d during time interval k.tijkThe estimated travel time for people in gridi moving into grid j during time interval k, where j∈Ri (unit: s).tij0The expected travel time for people in gridi moving into grid j with free flow velocity during time interval k, where j∈Ri (unit: s).ψji,dkThe minimum travel time for people in gridi moving from grid j to the queue tail at exit d during time interval k, where j∈Ri (unit: s).tji,dkThe minimum travel time for people in gridi moving to the queue tail at exit d by passing through grid j during time interval k, where j∈Ri.πpkThe minimum evacuation travel time of people selecting routep during time interval k.πikThe minimum evacuation time of people in gridi during time interval k.LijThe moving distance for people in gridi moving to grid j during time interval k, where j∈Ri.qdklThe queue length of exitd, which is predicted during time interval k, for the people arrives at exit d at the time interval l, where l≥k.ξj,ki,dlBinary variables and pedestrians in gridi choose exit d to evacuate by passing through grid j during time interval k; if the pedestrians can arrive exit d during time interval l, we have ξj,ki,dl=1, otherwise 0, where j∈Ri.ρikThe pedestrian density in gridi during time interval k (unit: persons per square meter).ρmaxAccording to the literature [41], the maximum pedestrian density is set at 5.4 persons per square meter for safety.EjkThe maximum number of people who allowed to moving into gridj during time interval k, that is, the acceptance capacity of grid j, where j∈Ri.YijkThe maximum number of people who can move from gridi to grid j during time interval k, that is, the output capacity of grid i to grid j, where j∈Ri.pijkThe ration of people moving into gridj who are from grid i during time interval k, where j∈Ri.QijThe through capacity between gridi and grid j; it set Qij=2.0734×llength−0.5901 according to the literature [38], where j∈Ri and llength denotes the length of neighbour edge between grid i and grid j.SijkThe transmission capacity for people who move from gridi to grid j during time interval k, where j∈Ri.MiThe area of gridi (unit: square meter).xijBinary variables, whether the dynamic sign guide in gridi points to grid j


## 3.2. The Upper-Level Optimization Model

The decision variable in the upper-level model is the dynamic sign direction in each grid, which is set as a binary variablexij (i∈R, j∈Ri), indicating whether the dynamic sign direction in grid i points to grid j:(1)xij=1,if the sign  of gridipoints  to  gridj,0,otherwise.The objective of the evacuation manager’s decision in the upper-level model is to minimize the total evacuation cost of the system to reduce network-wide congestion. According to the system-optimization program, withxij as the decision variable to minimize the total travel cost, the upper-level model is formulated as equations (1)–(5).(2)minZ=∑i∈R∑j∈Rtijxij,ρik,knijk,(3)s.t∑j∈Rixij≤1,∀i∈R,(4)xij+xji≤1,∀i∈R,j∈Ri,(5)xij∈0,1,∀i∈R,j∈Ri,where equation (2) is the objective of minimizing the total travel cost. In this paper, travel time is chosen as travel cost. In equation (2), tijxij,ρik,k is the link travel time for pedestrian from grid i to j, and it is a function of xij and ρik, where xij is determined by the upper-level model and ρik is obtained from the lower-level model. tijxij,ρik,k is abbreviated as tijk in following context and its specific calculation procedure is detailed in Section 3.4.Constraint (3) ensures that the sign cannot point in more than one neighbouring grid simultaneously. If∑j∈Rixij=1, it means that the sign in grid i will point to one of its neighbour grid j, and all pedestrians in grid i should move according to its guidance direction. In this case, grid i can be regarded as a one-way grid and defined as a directed grid in this paper. If ∑j∈Rixij=0, it means that there is no directional guidance in grid i, and all pedestrians in that grid can move according to their current routes, that is, their moving directions may not all be the same. In this case, grid i can be regarded as a nondirectional grid and defined as an undirected grid in this paper.Constraint (4) guarantees that two dynamic signs in two adjacent grids cannot point to each other simultaneously. Constraint (5) represents that the decision variable xij are binary variable.


## 3.3. The Lower-Level Dynamic User Optimization Model

According to the assumptions above, with sign directions obtained by the upper-level model, individuals desire to evacuate as quickly as possible along the route with the shortest travel time. However, it is challenging to predict the travel time of all routes exactly. Hence, the instantaneous travel time of each route estimated by pedestrians is taken to assess the shortest route in the lower-level model. Then the system will reach a reactive DUO equilibrium state when everyone chooses the route with the minimum travel time, and no one would be better by unilaterally changing his/her route. In this situation, the instantaneous travel time of all selected routes is equal and minimum. In contrast, that of all unselected routes is not less than the minimum instantaneous evacuation travel time. Namely, with the reactive DUO equilibrium state, if pedestrians in gridi choose evacuation route p toward exit d during time interval k, that is, fpi,dk>0, it means the evacuation route p has the minimum instantaneous evacuation travel time. Otherwise, fpi,dk=0 indicates that the evacuation travel time on route p is not less than the minimum evacuation travel time, and no one chooses that route. Therefore, we have the following expression.(6)cpi,dk=πpk,iffpi,dk>0,≥πpk,iffpi,dk=0.where cpi,dk is the time for pedestrians in grid i selecting route p to exit d and πpk is the minimum evacuation time of pedestrians on route p during the time interval k.Equation (6) can be equivalently expressed as a nonlinear complementarity problem (NCP) as follows [38].(7)fpi,dkcpi,dk−πpk=0,∀i∈R,d∈D∑d∑pfpi,dk=nik,∀i∈R,d∈D,cpi,dk−πpk≥0,∀i∈R,d∈D,fpi,dk≥0,∀i∈R,d∈D.Since equation (7) is a route-based model, all the routes from each grid to each exit should be enumerated, which is relatively inefficient to solve. Therefore, we reformulate equations (6) and (7) by transferring the route-based model to grid-based through the method developed in literature [38]. We assume that when a pedestrian in grid i chooses a certain shortest route p to exit d, it must first pass through its neighbour grid j, as shown in Figure 3. According to equation (6), if the travel time of route p is equal to the minimum travel time, we have fpi,dk>0 and nji,dk>0, where nji,dk is the number of pedestrians in grid i that choose to exit d with passing grid j. Otherwise, we have fpi,dk=0 and nji,dk=0 when the travel time of route p is not the minimum travel time. Hence, the travel time for pedestrians in grid i passing grid j to exit d is(8)cji,dk=πik,ifnji,d>0,≥πik,ifnji,d=0.Figure 3
The shortest route was chosen by a pedestrian [38].Similarly, the grid-based reactive DUO condition of equation (8) can also be rewritten as the following equivalent NCP formulation.(9)npi,dkcpi,dk−πpk=0,∀i∈R,j∈Ri,d∈D,∑j∈Ri∑d∈Dnpi,dk=nik,∀i∈R,cji,dk−πpk≥0,∀i∈R,j∈Ri,d∈D,npi,dk≥0,∀i∈R,j∈Ri,d∈D.To solve equation (9), we can equivalently restate it as a Variational Inequality (VI) problem. Let Ω=∑j∑dnji,dknik,nji,dk≥0,∀i∈R,j∈Ri,d∈D as the feasible grid flows of equation (9), n=nji,dk as the dynamic pedestrian flow vector, and cn=cji,dk as the vector of instantaneous evacuation travel time, which is a function of n. Then if there is a vector n∗∈Ω, equation (9) is equivalent to the VI problem as follows:(10)cn∗,n−n∗≥0,∀n∈Ω.The solution of the VI problem satisfies the instantaneous dynamic user optimal condition. The proof can be seen in literature [42].


## 3.4. Calculation of Instantaneous Route Travel Time

To solve the above model, we need to estimate the evacuation travel time of each route firstly. As we consider the impact of pedestrian congestion on the grid and queuing at bottlenecks on the travel time, the travel time is consisting of (1) the minimum travel time for pedestrians to move from the current grid i through grid j to exit d during time interval k, denoted as tji,dk, and (2) queuing time at exit d, denoted as wdk, equation listed as(11)cji,dk=tji,dk+wdk.As shown in Figure3, tji,dk is calculated as follows.(12)tji,dk=tijk+ψji,dk,where ψji,dk can be calculated using the shortest route algorithm based on the travel time tmnk between the adjacent grid m and n which are the parts of the shortest route corresponding to ψji,dk. tijk is related to the sign direction, the pedestrian flow speed, and the transmission capacity of grids i and j. We will develop it in the following section.


### 3.4.1. Calculation of Travel Time between Two Adjacent Grids

We estimate the travel time between adjacent grids based on a velocity-density relationship. The velocity-density function of the grid is first stated. According to the fundamental diagram of pedestrian flow, the pedestrian flow speeduik is a function of ρik in grid i. As stated in Section 3.2, a one-way pedestrian flow is formed in the directed grid with ∑j∈Rixij=1, while the pedestrian flow in different directions is formed in the undirected grid with ∑j∈Rixij=1. In the latter case, the multidirectional pedestrian flows may produce friction and congestion effects, reducing the pedestrian flow speed in each direction. As a result, the pedestrian flow speed in undirected grids would be lower than in directed grids under the same pedestrian density. Therefore, in this paper, uik should be revised as a function of ρik and xij. We adopt the pedestrian flow velocity-density function uρ=umax1−expβρ−1−ρmax−1 proposed by Weidmann [41] to fit uik in the undirected grids and the directed grids, respectively, where umax and β are the parameters to be calibrated, ρmax=5.4persons/m2. As in equation (13), if ∑j∈Rixij=1, uik in directed grids can refer to literature [41] with umax=1.34 and β=1.913. If ∑j∈Rixij=0, uik in undirected grids is obtained with umax=1.26 and β=1.63 by fitting the data in literature [43] with the least-squares method.(13)uik=1.261−exp−1.631ρik−15.4,if∑j∈Rixij=0,1.341−exp−1.9131ρik−15.4,if∑j∈Rixij=1.Next, the travel time of the grid is estimated based onuik and the pedestrian flow moving distance Lij. Without consideration of the transmission capacity limitations caused by the edge length difference between adjacent grids, the travel time tij′k from grid i to grid j can be calculated by the following equation (14). In equation (14), if ∑j∈Rixij=1 and xij=0, it means that grid i is a directed grid, but the sign in grid i does not guide to grid j. This indicates that pedestrians in grid i are not allowed to move to grid j. Therefore, tij′k=+∞.(14)tij′k=Lij1.261−exp−1.631/ρik−1/5.4,if∑j∈Rixij=0,Lij1.341−exp−1.9131/ρik−1/5.4,ifxij=1,+∞,if∑j∈Rixij=1andxij=0.To take the influence of pedestrian congestion on the evacuation travel time into account, we perform a cell transmission model of traffic flow to obtain a more accurate travel time. When pedestrians travel through grids, the transmission capacitySijk between grid i and j, j∈Ri, have a significant impact on the travel time. Figure 4 shows the factors influencing Sijk. As shown in Figure 4, Sijk is influenced by the output capacity of grid i to grid j (denoted by Yijk), acceptance capacity of grid j (denoted by Ejk), and the acceptance ration of grid j (denoted by pijk).(1)
Yijk is influenced by the number of pedestrians in grid i who plan to travel to grid j and the through capacity Qij between grid i and j. By definition, Yijk can be calculated by(15)Yijk=minnijk,Qij.(2)
Ejk is determined by the remaining capacity of grid j and the capacity of grid j to its neighbour grids. To ensure evacuation safety, we set the maximum pedestrian density in each grid as ρmax=5.4persons/m2; then the remaining capacity of grid j is ρmaxMj−njk. Then, we have(16)Ejk=minρmaxMj−njk,∑i∈RjQij.(3)
To simplify, the following formula is used to define the allocation ratiopijk, which denotes the proportion of pedestrians moving into grid j who are from grid i during time interval k,(17)pijk=Yijk∑i∈RjYijk.Figure 4
The influencing factors ofSijk.As shown in Figure4, the through capacity Sijk from grid i to grid j during time interval k can be obtained by the following equation,(18)Sijk=minYijk,pijkEijk=minnijk,Qij,pijkEijk.Hence, considering transmission capacity limitation and sign direction of gridi, the travel time from grid i to grid j during time interval k is(19)tijk=maxtij0,tij′k,nijkSijkΔt.


### 3.4.2. Calculation of Queuing Time of Exit

During the evacuation, reduced capacity at bottlenecks, such as exits, can lead to queues. Queuing time is part of the evacuation travel time and can also affect the route choice of pedestrians. The queuing time is related to the number of people queuing at the exit and the exit width. Therefore, a point queuing model [44] is used to estimate the number of people in line around exits.By definition, at current time intervalk, if pedestrians can arrive at exit d during time interval l with travel time tji,dk, that is, l≤tji,dk+k<l+1, we have ξj,ki,dl=1, otherwise ξj,ki,dl=0.(20)ξj,ki,dl=1,ifl≤tji,dk+k<l+1,0,otherwise.Hence, in time intervall, the number of pedestrians in line at exit d is(21)qkdl=maxqkdl−1+∑i∑jnji,dkξj,ki,dl−ΔtQdo,,ifl≥k,0,otherwise,where Qdo is the through capacity between exit d and the adjacent virtual outside grid o.Since the time for pedestrians to reach the exit is not necessarily an integer interval, for simplicity, the queue length of two adjacent integer intervals is considered when calculating the queue length, and the linearization method in literature [45] is used to calculate the number of pedestrians queuing at the exit at the time l+μΔt, μ∈0,1, that is,(22)qkdl+μ=μqkdl+1−μqkdl+1.Hence, the queuing time at exitd during time interval k is(23)wdk=qkdk+tji,dkQdoΔt.After in all, the evacuation travel timecji,dk can be estimated by equation (11)–(23).


## 3.4.1. Calculation of Travel Time between Two Adjacent Grids

We estimate the travel time between adjacent grids based on a velocity-density relationship. The velocity-density function of the grid is first stated. According to the fundamental diagram of pedestrian flow, the pedestrian flow speeduik is a function of ρik in grid i. As stated in Section 3.2, a one-way pedestrian flow is formed in the directed grid with ∑j∈Rixij=1, while the pedestrian flow in different directions is formed in the undirected grid with ∑j∈Rixij=1. In the latter case, the multidirectional pedestrian flows may produce friction and congestion effects, reducing the pedestrian flow speed in each direction. As a result, the pedestrian flow speed in undirected grids would be lower than in directed grids under the same pedestrian density. Therefore, in this paper, uik should be revised as a function of ρik and xij. We adopt the pedestrian flow velocity-density function uρ=umax1−expβρ−1−ρmax−1 proposed by Weidmann [41] to fit uik in the undirected grids and the directed grids, respectively, where umax and β are the parameters to be calibrated, ρmax=5.4persons/m2. As in equation (13), if ∑j∈Rixij=1, uik in directed grids can refer to literature [41] with umax=1.34 and β=1.913. If ∑j∈Rixij=0, uik in undirected grids is obtained with umax=1.26 and β=1.63 by fitting the data in literature [43] with the least-squares method.(13)uik=1.261−exp−1.631ρik−15.4,if∑j∈Rixij=0,1.341−exp−1.9131ρik−15.4,if∑j∈Rixij=1.Next, the travel time of the grid is estimated based onuik and the pedestrian flow moving distance Lij. Without consideration of the transmission capacity limitations caused by the edge length difference between adjacent grids, the travel time tij′k from grid i to grid j can be calculated by the following equation (14). In equation (14), if ∑j∈Rixij=1 and xij=0, it means that grid i is a directed grid, but the sign in grid i does not guide to grid j. This indicates that pedestrians in grid i are not allowed to move to grid j. Therefore, tij′k=+∞.(14)tij′k=Lij1.261−exp−1.631/ρik−1/5.4,if∑j∈Rixij=0,Lij1.341−exp−1.9131/ρik−1/5.4,ifxij=1,+∞,if∑j∈Rixij=1andxij=0.To take the influence of pedestrian congestion on the evacuation travel time into account, we perform a cell transmission model of traffic flow to obtain a more accurate travel time. When pedestrians travel through grids, the transmission capacitySijk between grid i and j, j∈Ri, have a significant impact on the travel time. Figure 4 shows the factors influencing Sijk. As shown in Figure 4, Sijk is influenced by the output capacity of grid i to grid j (denoted by Yijk), acceptance capacity of grid j (denoted by Ejk), and the acceptance ration of grid j (denoted by pijk).(1)
Yijk is influenced by the number of pedestrians in grid i who plan to travel to grid j and the through capacity Qij between grid i and j. By definition, Yijk can be calculated by(15)Yijk=minnijk,Qij.(2)
Ejk is determined by the remaining capacity of grid j and the capacity of grid j to its neighbour grids. To ensure evacuation safety, we set the maximum pedestrian density in each grid as ρmax=5.4persons/m2; then the remaining capacity of grid j is ρmaxMj−njk. Then, we have(16)Ejk=minρmaxMj−njk,∑i∈RjQij.(3)
To simplify, the following formula is used to define the allocation ratiopijk, which denotes the proportion of pedestrians moving into grid j who are from grid i during time interval k,(17)pijk=Yijk∑i∈RjYijk.Figure 4
The influencing factors ofSijk.As shown in Figure4, the through capacity Sijk from grid i to grid j during time interval k can be obtained by the following equation,(18)Sijk=minYijk,pijkEijk=minnijk,Qij,pijkEijk.Hence, considering transmission capacity limitation and sign direction of gridi, the travel time from grid i to grid j during time interval k is(19)tijk=maxtij0,tij′k,nijkSijkΔt.


## 3.4.2. Calculation of Queuing Time of Exit

During the evacuation, reduced capacity at bottlenecks, such as exits, can lead to queues. Queuing time is part of the evacuation travel time and can also affect the route choice of pedestrians. The queuing time is related to the number of people queuing at the exit and the exit width. Therefore, a point queuing model [44] is used to estimate the number of people in line around exits.By definition, at current time intervalk, if pedestrians can arrive at exit d during time interval l with travel time tji,dk, that is, l≤tji,dk+k<l+1, we have ξj,ki,dl=1, otherwise ξj,ki,dl=0.(20)ξj,ki,dl=1,ifl≤tji,dk+k<l+1,0,otherwise.Hence, in time intervall, the number of pedestrians in line at exit d is(21)qkdl=maxqkdl−1+∑i∑jnji,dkξj,ki,dl−ΔtQdo,,ifl≥k,0,otherwise,where Qdo is the through capacity between exit d and the adjacent virtual outside grid o.Since the time for pedestrians to reach the exit is not necessarily an integer interval, for simplicity, the queue length of two adjacent integer intervals is considered when calculating the queue length, and the linearization method in literature [45] is used to calculate the number of pedestrians queuing at the exit at the time l+μΔt, μ∈0,1, that is,(22)qkdl+μ=μqkdl+1−μqkdl+1.Hence, the queuing time at exitd during time interval k is(23)wdk=qkdk+tji,dkQdoΔt.After in all, the evacuation travel timecji,dk can be estimated by equation (11)–(23).


## 4. Algorithm

### 4.1. The Algorithm for Upper-Level Model

Since the discrete bi-level programming model in this paper is an NP-hard problem, it is difficult to get the optimal global solution in polynomial time. Existing heuristic algorithms for solving discrete bi-level programming problems mainly use the branch-and-bound method [46]. However, this method is inefficient in dealing with a massive number of variables xij. Therefore, in this paper, a genetic algorithm is designed for the bi-level programming model as follows.In the genetic algorithm, the genes in the chromosome are to be coded according to the constraints of the variables. To satisfy the constraints (4), we encode every two adjacent genes in pairs of 0 and 1 to denote the decision variablexij and xji. Therefore, the chromosome can be described as X=…,xij,xji,…, where 1≤i<cardR, j∈Ri, and j>i. The pseudocode of the genetic algorithm is given as Algorithm 1. The genetic algorithm also includes algorithms for crossover, mutation, and reproduction, which correspond to the pseudocodes as Algorithms 2–4, respectively.Algorithm 1: Genetic algorithm for upper-level model.
(1)
Input: number of pedestrians in gridsnijk, the travel time tijk(2)
Output: the chromosomeX with maximum FX(3)
Procedure GENETICALGORITHM(nijk, tijk)(4)
Initialize population sizeP, crossover probability Pc, mutation probability Pm, contemporary population Yg, maximum evolution algebra G. Let g=1.(5)
whileg<G, do(6)
CROSSOVER(P, Pc, Yg, cardR)(7)
MUTATION(P, Pm, Yg, cardR)(8)
REPRODUCTION(P, Yg, Y′g, nijk, tijk)(9)
g=g+1(10)
End while(11)
For each chromosome inYg, do(12)
Calculate the fitness valueFX of the chromosome X(13)
obtain the chromosomeX with the maximum FX from Yg(14)
End for(15)
ReturnX(16)
End procedureAlgorithm 2: Crossover algorithm in genetic algorithm.
(1)
Input:P, Pc, Yg, the cardinality of the set RcardR(2)
Output: the offspring populationY′g(3)
Procedure CROSSOVER(P, Pc, Yg, cardR)(4)
Set temporary population chromosome setT=∅(5)
Fori=1 to P, do(6)
generate random numberr∈0,1(7)
Ifr<Pc(8)
Then add thei th chromosome in Yg to T(9)
End if(10)
End for(11)
For them th chromosome Xm in T (m=1 to cardT), do(12)
For then th chromosome Xn in T (n=m+1 to cardT), do(13)
generate random positive integerr∈0,cardR(14)
Forβ=r to cardR, do(15)
Swap the gene pairsxβj,xjβ and yβj,yjβ in Xm and Xn corresponding to the neighbour edges of the β th grid. That is xβj↔yβj and xjβ↔yjβ, where xβj,xjβ∈Xm, yβj,yjβ∈Xn,j∈Rβ.(16)
End for(17)
Two new chromosomesXm′ and Xn′ are obtained and added to the offspring population Y′g.(18)
End for(19)
End for(20)
ReturnY′g(21)
End procedureAlgorithm 3: Mutation algorithm in genetic algorithm.
(1)
Input:P, Pm, Yg, cardR(2)
Output: the offspring populationY′g(3)
Procedure MUTATION(P, Pm, Yg, cardR)(4)
Set temporary population chromosome setT=∅(5)
Fori=1 to P, do(6)
generate random numberr∈0,1(7)
Ifr<Pm(8)
Then add thei th chromosome in Yg to T(9)
End if(10)
End for(11)
For them th chromosome Xm in T (m=1 to m=1), do(12)
generate random positive integerβ∈0,cardR(13)
Selection of gene pairxβj,xjβ in Xm to mutate to xβ′j,xj′β. Let xβ′j=1−xβj and xj′β=0 if xβj=0, otherwise, x′jβ=xjβ.(14)
the new chromosomesXm′ are obtained and added to the offspring population Y′g.(15)
End for(16)
ReturnY′g(17)
End procedureAlgorithm 4: Reproduction algorithm in Genetic algorithm.
(1)
Input:P, Yg, Y′g(2)
Output: the next-generation populationYg+1(3)
Procedure REPRODUCTION(P, Yg, Y′g, nijk, tijk)(4)
SetY″g=Yg∪Y′g, make sure no identical chromosomes are in Y″g.(5)
For each chromosome inY″g, do(6)
Calculate the fitness valueFX of the chromosome X obtain the chromosome X with maximum fitness value FX from Y″g(7)
End for(8)
LetY″g=Y″g−X， Yg+1=Yg+1+X.(9)
whilecardY″g<P, do(10)
Randomly select chromosomeXm and Xn from Y″g(11)
IfFX1≥FX2(12)
Then setX=X1(13)
Else setX=X2(14)
End if(15)
LetY″g=Y″g−X， Yg+1=Yg+1+X.(16)
End while(17)
ReturnYg+1(18)
End procedureIn line 12 of Algorithm1, and in line 6 of Algorithm 4, the chromosome fitness values FX=Z0/ZX,ρik are calculated according to equation (2), where Z0 is the total travel time with xij=xji=0, i,j∈R.According to Algorithms1–4, the complexity of the genetic algorithm is mainly affected by Algorithm 2, and the time complexity of the genetic algorithm is OMP2, where M is the number of variables xij and P is population size.


### 4.2. The Algorithm for Lower-Level Model

In this paper, we develop an iterative heuristic algorithm based on the concept of adjusting pedestrians from long routes to shorter ones in literature [38]. The algorithm pseudocode is as follows.Algorithm 5: Algorithm for lower-level model.
(1)
Input: the current simulation time intervalk, sign direction variable xij, pedestrian number in grids nji,dk,(2)
Output: the exit/route choice result for individuals in each grid(3)
Procedure ROUTECHOICE(k, xij, nji,dk)(4)
initialize the convergence accuracyε(5)
while do not satisfy the convergence condition, do(6)
For all each gridi∈R, do(7)
calculateuik according to equation (13) based on nji,dk.(8)
For all each gridj∈Ri, do(9)
calculate thetijk according to xij (j∈Ri) and equations (15)–(20).(10)
End for(11)
End for(12)
Find shortest path and calculate the shortest travel timeψij,dk(13)
For all each gridi∈R, do(14)
Calculate the travel timetji,dk and ξj,ki,dl (l>k) according to equations (12) and (19), respectively(15)
Calculate the queue lengthqkdl and estimate the evacuation travel time cji,dk according to equations (20) and (11), respectively.(16)
End for(17)
For all OD pairsi,d, do(18)
For allj∈Ri, do(19)
calculate the minimum evacuation timeπik=mincji,dk and its corresponding grids set R^i=j,d|cji,dk=πik according to equation (24), where j∈Ri,d∈D(20)
End for(21)
Calculateϑ=∑j∈Ri∑d∈Dαnji,dkcji,dk−πik, where α denotes pedestrian sensitivities to the evacuation travel time differences(22)
For allj∈Ri, do(23)
Ifj,d∉R^i(24)
Then setnji,dk=nji,dk−αnji,dkElse set nji,dk=nji,dk+ϑ/R^i(25)
End if(26)
End for(27)
End for(28)
End while(29)
End procedureThe convergence condition in line 5 of Algorithm5 needs to satisfy the following equation; then the iteration algorithm terminates.(24)∑i∈R∑j∈Ri∑d∈Dnji,dkcji,dk−πik∑i∈R∑j∈Ri∑d∈Dnji,dkπik<ε.The time complexity of Algorithm5 is mainly affected by the multilayer iterations in line 17 to 27, and the algorithm complexity is On2, where n=cardR. The multilayer iterations transfer pedestrians in the route with a long evacuation travel time to the shortest route. The total transfer amount cannot exceed the full flow in each route to ensure feasibility.


### 4.3. Simulation Algorithm for Evacuation

For numerical analysis, we try to embed the bi-level model into a microscopic simulation model and put forward an algorithm framework integrating the macroscopic evacuation guidance optimization and microscopic simulation, as seen in Algorithm6. In Algorithm 6, the best route selected by pedestrians from the macro optimization model determines their moving direction in the microscopic simulation model. Then, the pedestrian density of grids is updated after pedestrians move in the microscopic simulation. The new pedestrian density of grids can then be input into the macroscopic model.The social force model in literature [47] is adopted in the microscopic simulation model with a simulation step length Δt′. Due to the computational time consuming of upper-level model, we assume that the optimization for dynamic sign direction is conducted in every δ time, where δ=w×Δt′ and w is a positive integer to improve the computation efficiency. The simulation algorithm pseudocode is as follows.Algorithm 6: Simulation algorithm for evacuation.
(1)
Procedure SIMULATION( )(2)
Generate the grid division and evacuate network. InitializeN pedestrians with velocity and location of each pedestrian p, set simulation time τ=0. Set xij=0, initialize the social force model parameters.(3)
whileN>0do(4)
Ifτmodδ=0, then(5)
GENETICALGORITHM(nijk, tijk)(6)
ROUTECHOICE(k, xij, nji,dk)(7)
End if(8)
For the pth pedestrian (p=1 to N), do(9)
According the exit /route choice result update thepth pedestrian’s desire velocity direction(10)
Calculate thepth pedestrian’s velocity and acceleration using social force model(11)
End for(12)
For the pth pedestrian (p=1 to N), do(13)
Update thepth pedestrian’s velocity and location(14)
Ifp has evacuated out, then(15)
N=N−1(16)
End if(17)
End for(18)
τ=τ+Δt′(19)
End while(20)
End procedure


## 4.1. The Algorithm for Upper-Level Model

Since the discrete bi-level programming model in this paper is an NP-hard problem, it is difficult to get the optimal global solution in polynomial time. Existing heuristic algorithms for solving discrete bi-level programming problems mainly use the branch-and-bound method [46]. However, this method is inefficient in dealing with a massive number of variables xij. Therefore, in this paper, a genetic algorithm is designed for the bi-level programming model as follows.In the genetic algorithm, the genes in the chromosome are to be coded according to the constraints of the variables. To satisfy the constraints (4), we encode every two adjacent genes in pairs of 0 and 1 to denote the decision variablexij and xji. Therefore, the chromosome can be described as X=…,xij,xji,…, where 1≤i<cardR, j∈Ri, and j>i. The pseudocode of the genetic algorithm is given as Algorithm 1. The genetic algorithm also includes algorithms for crossover, mutation, and reproduction, which correspond to the pseudocodes as Algorithms 2–4, respectively.Algorithm 1: Genetic algorithm for upper-level model.
(1)
Input: number of pedestrians in gridsnijk, the travel time tijk(2)
Output: the chromosomeX with maximum FX(3)
Procedure GENETICALGORITHM(nijk, tijk)(4)
Initialize population sizeP, crossover probability Pc, mutation probability Pm, contemporary population Yg, maximum evolution algebra G. Let g=1.(5)
whileg<G, do(6)
CROSSOVER(P, Pc, Yg, cardR)(7)
MUTATION(P, Pm, Yg, cardR)(8)
REPRODUCTION(P, Yg, Y′g, nijk, tijk)(9)
g=g+1(10)
End while(11)
For each chromosome inYg, do(12)
Calculate the fitness valueFX of the chromosome X(13)
obtain the chromosomeX with the maximum FX from Yg(14)
End for(15)
ReturnX(16)
End procedureAlgorithm 2: Crossover algorithm in genetic algorithm.
(1)
Input:P, Pc, Yg, the cardinality of the set RcardR(2)
Output: the offspring populationY′g(3)
Procedure CROSSOVER(P, Pc, Yg, cardR)(4)
Set temporary population chromosome setT=∅(5)
Fori=1 to P, do(6)
generate random numberr∈0,1(7)
Ifr<Pc(8)
Then add thei th chromosome in Yg to T(9)
End if(10)
End for(11)
For them th chromosome Xm in T (m=1 to cardT), do(12)
For then th chromosome Xn in T (n=m+1 to cardT), do(13)
generate random positive integerr∈0,cardR(14)
Forβ=r to cardR, do(15)
Swap the gene pairsxβj,xjβ and yβj,yjβ in Xm and Xn corresponding to the neighbour edges of the β th grid. That is xβj↔yβj and xjβ↔yjβ, where xβj,xjβ∈Xm, yβj,yjβ∈Xn,j∈Rβ.(16)
End for(17)
Two new chromosomesXm′ and Xn′ are obtained and added to the offspring population Y′g.(18)
End for(19)
End for(20)
ReturnY′g(21)
End procedureAlgorithm 3: Mutation algorithm in genetic algorithm.
(1)
Input:P, Pm, Yg, cardR(2)
Output: the offspring populationY′g(3)
Procedure MUTATION(P, Pm, Yg, cardR)(4)
Set temporary population chromosome setT=∅(5)
Fori=1 to P, do(6)
generate random numberr∈0,1(7)
Ifr<Pm(8)
Then add thei th chromosome in Yg to T(9)
End if(10)
End for(11)
For them th chromosome Xm in T (m=1 to m=1), do(12)
generate random positive integerβ∈0,cardR(13)
Selection of gene pairxβj,xjβ in Xm to mutate to xβ′j,xj′β. Let xβ′j=1−xβj and xj′β=0 if xβj=0, otherwise, x′jβ=xjβ.(14)
the new chromosomesXm′ are obtained and added to the offspring population Y′g.(15)
End for(16)
ReturnY′g(17)
End procedureAlgorithm 4: Reproduction algorithm in Genetic algorithm.
(1)
Input:P, Yg, Y′g(2)
Output: the next-generation populationYg+1(3)
Procedure REPRODUCTION(P, Yg, Y′g, nijk, tijk)(4)
SetY″g=Yg∪Y′g, make sure no identical chromosomes are in Y″g.(5)
For each chromosome inY″g, do(6)
Calculate the fitness valueFX of the chromosome X obtain the chromosome X with maximum fitness value FX from Y″g(7)
End for(8)
LetY″g=Y″g−X， Yg+1=Yg+1+X.(9)
whilecardY″g<P, do(10)
Randomly select chromosomeXm and Xn from Y″g(11)
IfFX1≥FX2(12)
Then setX=X1(13)
Else setX=X2(14)
End if(15)
LetY″g=Y″g−X， Yg+1=Yg+1+X.(16)
End while(17)
ReturnYg+1(18)
End procedureIn line 12 of Algorithm1, and in line 6 of Algorithm 4, the chromosome fitness values FX=Z0/ZX,ρik are calculated according to equation (2), where Z0 is the total travel time with xij=xji=0, i,j∈R.According to Algorithms1–4, the complexity of the genetic algorithm is mainly affected by Algorithm 2, and the time complexity of the genetic algorithm is OMP2, where M is the number of variables xij and P is population size.


## 4.2. The Algorithm for Lower-Level Model

In this paper, we develop an iterative heuristic algorithm based on the concept of adjusting pedestrians from long routes to shorter ones in literature [38]. The algorithm pseudocode is as follows.Algorithm 5: Algorithm for lower-level model.
(1)
Input: the current simulation time intervalk, sign direction variable xij, pedestrian number in grids nji,dk,(2)
Output: the exit/route choice result for individuals in each grid(3)
Procedure ROUTECHOICE(k, xij, nji,dk)(4)
initialize the convergence accuracyε(5)
while do not satisfy the convergence condition, do(6)
For all each gridi∈R, do(7)
calculateuik according to equation (13) based on nji,dk.(8)
For all each gridj∈Ri, do(9)
calculate thetijk according to xij (j∈Ri) and equations (15)–(20).(10)
End for(11)
End for(12)
Find shortest path and calculate the shortest travel timeψij,dk(13)
For all each gridi∈R, do(14)
Calculate the travel timetji,dk and ξj,ki,dl (l>k) according to equations (12) and (19), respectively(15)
Calculate the queue lengthqkdl and estimate the evacuation travel time cji,dk according to equations (20) and (11), respectively.(16)
End for(17)
For all OD pairsi,d, do(18)
For allj∈Ri, do(19)
calculate the minimum evacuation timeπik=mincji,dk and its corresponding grids set R^i=j,d|cji,dk=πik according to equation (24), where j∈Ri,d∈D(20)
End for(21)
Calculateϑ=∑j∈Ri∑d∈Dαnji,dkcji,dk−πik, where α denotes pedestrian sensitivities to the evacuation travel time differences(22)
For allj∈Ri, do(23)
Ifj,d∉R^i(24)
Then setnji,dk=nji,dk−αnji,dkElse set nji,dk=nji,dk+ϑ/R^i(25)
End if(26)
End for(27)
End for(28)
End while(29)
End procedureThe convergence condition in line 5 of Algorithm5 needs to satisfy the following equation; then the iteration algorithm terminates.(24)∑i∈R∑j∈Ri∑d∈Dnji,dkcji,dk−πik∑i∈R∑j∈Ri∑d∈Dnji,dkπik<ε.The time complexity of Algorithm5 is mainly affected by the multilayer iterations in line 17 to 27, and the algorithm complexity is On2, where n=cardR. The multilayer iterations transfer pedestrians in the route with a long evacuation travel time to the shortest route. The total transfer amount cannot exceed the full flow in each route to ensure feasibility.


## 4.3. Simulation Algorithm for Evacuation

For numerical analysis, we try to embed the bi-level model into a microscopic simulation model and put forward an algorithm framework integrating the macroscopic evacuation guidance optimization and microscopic simulation, as seen in Algorithm6. In Algorithm 6, the best route selected by pedestrians from the macro optimization model determines their moving direction in the microscopic simulation model. Then, the pedestrian density of grids is updated after pedestrians move in the microscopic simulation. The new pedestrian density of grids can then be input into the macroscopic model.The social force model in literature [47] is adopted in the microscopic simulation model with a simulation step length Δt′. Due to the computational time consuming of upper-level model, we assume that the optimization for dynamic sign direction is conducted in every δ time, where δ=w×Δt′ and w is a positive integer to improve the computation efficiency. The simulation algorithm pseudocode is as follows.Algorithm 6: Simulation algorithm for evacuation.
(1)
Procedure SIMULATION( )(2)
Generate the grid division and evacuate network. InitializeN pedestrians with velocity and location of each pedestrian p, set simulation time τ=0. Set xij=0, initialize the social force model parameters.(3)
whileN>0do(4)
Ifτmodδ=0, then(5)
GENETICALGORITHM(nijk, tijk)(6)
ROUTECHOICE(k, xij, nji,dk)(7)
End if(8)
For the pth pedestrian (p=1 to N), do(9)
According the exit /route choice result update thepth pedestrian’s desire velocity direction(10)
Calculate thepth pedestrian’s velocity and acceleration using social force model(11)
End for(12)
For the pth pedestrian (p=1 to N), do(13)
Update thepth pedestrian’s velocity and location(14)
Ifp has evacuated out, then(15)
N=N−1(16)
End if(17)
End for(18)
τ=τ+Δt′(19)
End while(20)
End procedure


## 5. Numeral Experiments

### 5.1. Case Description and Parameters Setting

For comparative analysis, an evacuation scene in literature [38] was selected as the simulation scenario. The evacuation scene is a 23m×18m room with two exits, namely, exit A and exit B, with a width of 2 m and 1.5 m, respectively. According to the positions of walls, obstacles, and exits, the scene is divided into 86 grids. The length of grids ranges from 1 meter to 3 meters. Figure 5 shows the simulation scene diagram, where the gray grids are obstacles, green grids are exits, and blank grids with index are the walkable area.Figure 5
The layout and grid division of the simulation scene.The parameters in the social force model are set asτ=0.5s, A=2000, B=0.08, k1=1.2×105, k2=2.4×105, Δt′=0.01s, and δ=10Δt′=0.1s. Let pedestrian quality m=70kg, and pedestrian radius r is a uniform value between 0.25m,0.35m and desired speed vmax=1.34m/s. The parameters in the genetic algorithm are set as P=50, Pc=0.6, Pm=0.01，and G=200. With Microsoft Visual Studio 2017 based on dot net Framework 4.6, the simulation experiment with 200 pedestrians is operated on the platform of Windows 10, CPU is intel i7-7700HQ 2.8 GHz, and 16G memory. It takes 132 seconds for the simulation case to finish running. Figure 6 shows the pedestrian evacuation simulation process at different time intervals. In Figure 6, red arrows represent the dynamic sign direction, purple circles denote those who selected exit B to evacuate, and green circles correspond to those who chosen exit A.Figure 6
Snapshots of simulation at different simulation time intervals: (a)t = 0 s; (b) t = 26.31 s; (c) t = 47.66 s; (d) t = 56.42 s.
(a)(b)(c)(d)As shown in Figure6, at the moment t=0s, pedestrians are randomly uniform distributed in the scene, and the sign directions were generated according to the upper-level model. Each individual chooses the exit according to the dynamic sign direction. As the simulation evolves, the direction of some signs is adjusted. For example, the red arrows labelled with blue circles in Figures 6(b)–6(d) change their pointing in comparison with Figures 6(a)–6(c), respectively. Accordingly, some pedestrians also adjust their target exits and routes.


### 5.2. Effectiveness Analysis of DSG

We conduct some comparative simulations with DSG and SSG on the same inputs in this section. In the DSG simulation, pedestrians move according to our model. In the SSG simulation, pedestrians choose the nearest exit and the shortest route to evacuate. Three statistical indexes are calculated to illustrate the effectiveness of our model on evacuation time as follows:(1)
The maximum evacuation timeTmax is the time of the last person left from the simulation scene, that is, Tmax=maxhTh, where Th is the evacuation time for pedestrian h.(2)
The average evacuation timeTave is the average evacuation time of all pedestrians, that is, Tave=∑hNTh/N, where N is the number of pedestrians in simulation.(3)
The average delay timeTdel is the average delay time compared with the evacuation time required on the shortest route under free flow, that is, Tdel=∑hNTh−Th0/N, where Th0 is the evacuation time for pedestrian h moving in the desired velocity vmax along the shortest route.Random distributions of pedestrian locations during the initialization lead to different results. To eliminate the differences in results, we simulate the same number of individuals at random locations 50 times. The statistical index is the average of 50 simulations listed in Table2. In Table 2, Err is the relative gap of the statistical index between DSG and SSG, which is calculated by Gap=the statistical indexinSSG−corresponding index in DSG×100%/the statisticalindex in SSG.Table 2
: Comparative results with different number of pedestrian.
NTmaxTaveTdelDSG (s)SSG (s)Gap (%)DSG (s)SSG (s)Gap (%)DSG (s)SSG (s)Gap (%)1017.0917.090.009.839.830.000.000.000.001517.0417.040.009.769.760.000.000.000.002017.0817.080.009.779.770.000.000.000.002517.0717.070.009.729.720.000.000.000.003017.1817.180.0010.6510.650.000.860.860.003517.1617.160.0011.3311.330.001.541.540.004017.1217.120.0012.2112.210.002.182.180.004518.3619.113.9213.0113.271.962.993.072.615020.3422.7210.4815.2616.336.555.446.5516.9510026.4329.5510.5618.5921.3312.858.8511.4922.9815032.7538.6915.3522.927.1615.6813.0717.4224.9720044.5158.2123.5431.2840.4222.6121.4430.5829.8925062.8492.7032.2148.5768.3428.9338.7858.5133.7230082.14136.0539.6362.4599.2837.1052.6989.4441.09350104.68182.2142.5579.37139.4243.0769.52129.6446.37400130.21228.643.0496.36178.4946.0186.52168.7648.73As shown in Table2, as the number of evacuees increases, the difference in statistical indexes between the DSG model and the SSG model can be divided into three groups. The evacuation process can be divided into three situations accordingly.(1)
The first situation: In this situation, the number of pedestrians is relatively small (N<30), and the above three statistical indexes for DSG and SSG are equal. In particular, Tdel is zero for DSG and SSG. It follows that when the number of people is small, the sign direction in the DSG model is the same as that in the SSG model, both pointing to the nearest exit along the shortest route. It makes the same pedestrians in DSG and SSG move in the same trajectory. As a result, Tmax and Tave are the same in both models. Furthermore, everyone can also move with vmax without congestion during the evacuation process; hence, the delay time is zero in both models. During the simulation, we find that the initial position of pedestrians has a negligible impact on Tmax and Tave.(2)
The second situation: In this situation, the number of pedestrians is30≤N≤40, and the above three statistical indexes for DSG and SSG are equal. Unlike the first situation, Tdel is greater than zero. The equality of statistical indexes shows that the sign direction under DSG is the same as that under SSG. However, with the number of pedestrians increasing, it causes congestion on some evacuation routes. Hence, the delay time is greater than zero. Meanwhile, the increase in the number of pedestrians will increase the congestion and its duration, making a positive correlation between Tave and N. Nonetheless, not all pedestrians would be affected by the congestion. As a result, Tmax is still randomly distributed.(3)
The third situation: In this situation, the number of pedestrians isN>40, and statistical indexes of DSG are all smaller than that of SSG. It means that the sign direction under DSG will be adjusted according to the congestion and waiting time at the exit. This adjustment can guide pedestrians to detour or even change the exits. In this way, pedestrians are distributed in balance on evacuation routes and exits, with minimum total travel time cost. Overall, all the three statistical indexes of DSG and SSG increase with the number of pedestrians.Generally, as listed in Table2, there is no significant difference between the SSG and DSG in the first and second situations due to the relatively low density of pedestrians and the absence of congestion during evacuation. However, as the number of pedestrians increases (N>40), the relative gaps of all three statistical indexes almost increase. For instance, the relative gap of Tave is 12.85% when the number of pedestrians is 100 and 37.1% when the number of pedestrians is 300. Through the above analysis, we can conclude that the more the pedestrians in evacuation, the better the improvement of DSG over SSG on evacuation time and delay time.


### 5.3. Effectiveness of DSG at a Different Location

This subsection mainly focuses on analysing the effect of DSG at different locations on the evacuation process. We counted the number of sign direction changes for each gird during the simulation, as shown in Figure7. According to the number of changes, the grids where these signs are located can be divided into two types, described as follows.(1)
For the first type of grids, the change times of sign direction are less than 5, and most of them are 1, namely, the sign directions in these grids change from the undirected state shown in Figure1(c) to a specific direction shown in Figures 1(a) and 1(b) at the beginning of the simulation, and will be maintained until the end of the simulation, like the grids numbered in 1–9 in Figure 5. It indicates that the direction states of the signs in this type of grids are stable, and the optimal route and exit guided by these signs do not change with the fluctuation of pedestrian flow in the grids. This type of grids accounts for a significant proportion of the whole evacuation area, as shown in Figure 7.(2)
For the second type of grids, the change times of sign direction are more than 5, and most of them are even greater than 10, such as the grids numbered 47, 48, 49, 50, 58, and 68 in Figure5. Namely, the sign direction changes in this type of grids are more frequent than those in the first type of grids. As shown in Figure 7, the scene, in this case, can be divided into two regions with and without square filling. The pedestrians in these two regions choose exit B and exit A, respectively. And the second type of grids is mainly located on both sides of the boundary line (red dot line in Figure 7) of these two regions. It may be because that the travel time from the boundary grid to the two exits is relatively close, so even slight changes in the pedestrian flow can cause the two evacuation times through exit A and exit B to take turns to be the larger one. As a result, exit A and exit B will alternate between being the nearest exit of the boundary grid. This alternation further leads to frequent guidance adjustment of dynamic signs in these boundary grids. These boundary grids are different from the first type of grids where the travel time to one of the exits is much greater than that to the other one, and fluctuations in pedestrian flow have little effect on the alternation of shortest routes and exits. Therefore, we believe that the second type of grids is more sensitive to pedestrian flow than the first type of grids. And DSG in the second type of grids may have a more significant impact on evacuation time.Figure 7
The change times of dynamic sign direction in the grids.To evaluate the influence of dynamic guidance in the above two types of grids, we perform seven sets of comparative simulation experiments for each of the two types of grids with different signs, as shown in Table3. In Table 3, the grid with no signs means it is an undirected grid, while the grid with static grids means the signs in that grid always direct to the nearest exit. Set the number of pedestrians as N=300. The above experiments are simulated 50 times, respectively, and the initial locations of these pedestrians are the same in each simulation.Table 3
: Experimental scheme for different evacuation sign guidance.
Experiment no.The signs set in the gridsTave (s)The first type of gridsThe second type of grids1Dynamic signsDynamic signs62.412No signsDynamic signs62.653Static signsDynamic signs62.474Dynamic signsNo signs71.85No signsNo signs71.866Dynamic signsStatic signs97.597Static signsStatic signs99.36As shown in Table3, Tave of the seven groups of experiments can be divided into three grades. Among them, Tave of experiment 1, 2, and 3 in the first grade is less than 63 s; Tave of experiment 4 and 5 in the second grade is 71.8 s and 71.86 s, respectively; and Tave of experiment 6 and 7 in the third grade is greater than 97 s. Within the same grade, Tave of all experiments with the same evacuation signs in the second type of grids and different signs in the first type of grids are close. It can be seen that whether set as dynamic signs, static signs, or no signs in the first type of grids, the impact on evacuation time is not significant. Therefore, in practice, static signs can be set in the first type of grids, and their guidance directions can be optimized in advance to save computational costs.Comparing the experiments of different grades, we can be seen thatTave of each experiment differs greatly when the evacuation signs are the same in the first type of grids and different in the second type of grids. For example, when the first type of grids are set to dynamic signs, Tave is reduced by 35.18s and 9.39 s if the second type of grids is set to dynamic signs, compared to static signs and no signs, respectively. It can be concluded that there are some critical grids similar to the second type of grids in the evacuation area. These critical grids play an important role in balancing congestion and improving evacuation efficiency. Combining with experiment 2 and experiment 3, we can know that focusing on optimizing DSG in these critical grids can improve calculation efficiency while realizing good evacuation effectiveness.


### 5.4. Effectiveness of Dynamic Guidance at Different Periods

In the previous experiments, we assumed thatδ=0.1s, indicating that the sign direction may change every 0.1 s. However, this is unreasonable because frequent adjustments of sign directions in a short period leave pedestrians without enough reaction time, which may bring chaos to evacuation. Therefore, to relieve the confusion, we set the time interval between two sign direction adjustments to an acceptable value. This setting means that the dynamic guidance of signs is limited. Based on experiment 3 in Table 3, the effect of DSG on Tave with limitation is discussed in this subsection.According to experiment 3 in Table3, we know that Tmax is no less than 73.4 s in the above simulation scene with 300 individuals. Therefore, we set the sign direction to change no more than seven times so that δ is greater than 10s. Let the number of sign direction adjustment h=1,2,…,7, and δ=Tmax/h, where Tmax≥82s. With this setting, Tave for the same initial pedestrian distribution under different h is counted, as shown in Figure 8.Figure 8
The average evacuation time with different number of sign direction optimization.From Figure8, it is easy to see that the average evacuation time increases with the number of dynamic sign direction optimization from 0 to 1, while it decreases gradually when h>1. It implied that when h=1, the dynamic sign direction no more changes after optimization, which will cause a maximum evacuation time similar to the static signs. And when h>1, the dynamic sign direction in the second type of grids will be optimized several times according to the pedestrian distribution, effectively reducing evacuation time.To analyse the effectiveness of DSG onTave in the different periods, we design five simulation experiments based on experiment 3 in Table 3. In each experiment, four times of dynamic sign direction optimization are employed with an interval of 10s in the second type of grids, that is, h=4 and δ=10s. In the five experiments, the only difference is that the start time of dynamic sign direction optimization is different, which are at 0s, 10s, 20s, 30s, and 40s, respectively. The average evacuation times corresponding to the five simulations are 74.07 s, 73.16 s, 72.62 s, 72.2 s, and 71.88 s, respectively, as shown in Figure 9.Figure 9
The average evacuation time with DSG in different periods.The comparative results show that the performance of dynamic guidance in the later period is better than that in the early period under the same situation. The following reasons may cause this performance. Firstly, the pedestrian distribution in the early period is more uniform than that in the later period. And the pedestrian flow in the second type of grids is uncrowded. As a result, the dynamic sign direction optimized according to the initial pedestrian distribution may not be consistent with the pedestrian distribution in the later stage, resulting in prolonging evacuation time. Secondly, in the later period, pedestrians in the critical grids are more than that in the early period. Thus, the optimization of DSG employed in the later period may be more practical, and the optimization results would affect more pedestrians to reduce evacuation time.


### 5.5. Limitations

The goal of the work is to achieve dynamic evacuation guidance. The optimization of DSG is the core model in an evacuation guidance system. A complete evacuation guidance system framework includes three modules: detecting devices, back-end computing, and evacuation guidance display. This paper deals with the development of the latter two modules but not yet with the detecting devices. The detecting devices mainly collect pedestrian locations and input the pedestrian density of grids to the DSG model. In this paper, the density of pedestrians in grids is obtained using a simulation method. However, in practice, pedestrian density needs to be obtained with sensors for pedestrian detection. For example, the whole evacuation scene can be monitored by installing a large number of videos. Each video monitoring area can be considered as a grid. The grid density of the DSG model can be obtained by identifying the number of pedestrians within the video. Thus, a DSG-based evacuation guidance system can be implemented.


## 5.1. Case Description and Parameters Setting

For comparative analysis, an evacuation scene in literature [38] was selected as the simulation scenario. The evacuation scene is a 23m×18m room with two exits, namely, exit A and exit B, with a width of 2 m and 1.5 m, respectively. According to the positions of walls, obstacles, and exits, the scene is divided into 86 grids. The length of grids ranges from 1 meter to 3 meters. Figure 5 shows the simulation scene diagram, where the gray grids are obstacles, green grids are exits, and blank grids with index are the walkable area.Figure 5
The layout and grid division of the simulation scene.The parameters in the social force model are set asτ=0.5s, A=2000, B=0.08, k1=1.2×105, k2=2.4×105, Δt′=0.01s, and δ=10Δt′=0.1s. Let pedestrian quality m=70kg, and pedestrian radius r is a uniform value between 0.25m,0.35m and desired speed vmax=1.34m/s. The parameters in the genetic algorithm are set as P=50, Pc=0.6, Pm=0.01，and G=200. With Microsoft Visual Studio 2017 based on dot net Framework 4.6, the simulation experiment with 200 pedestrians is operated on the platform of Windows 10, CPU is intel i7-7700HQ 2.8 GHz, and 16G memory. It takes 132 seconds for the simulation case to finish running. Figure 6 shows the pedestrian evacuation simulation process at different time intervals. In Figure 6, red arrows represent the dynamic sign direction, purple circles denote those who selected exit B to evacuate, and green circles correspond to those who chosen exit A.Figure 6
Snapshots of simulation at different simulation time intervals: (a)t = 0 s; (b) t = 26.31 s; (c) t = 47.66 s; (d) t = 56.42 s.
(a)(b)(c)(d)As shown in Figure6, at the moment t=0s, pedestrians are randomly uniform distributed in the scene, and the sign directions were generated according to the upper-level model. Each individual chooses the exit according to the dynamic sign direction. As the simulation evolves, the direction of some signs is adjusted. For example, the red arrows labelled with blue circles in Figures 6(b)–6(d) change their pointing in comparison with Figures 6(a)–6(c), respectively. Accordingly, some pedestrians also adjust their target exits and routes.


## 5.2. Effectiveness Analysis of DSG

We conduct some comparative simulations with DSG and SSG on the same inputs in this section. In the DSG simulation, pedestrians move according to our model. In the SSG simulation, pedestrians choose the nearest exit and the shortest route to evacuate. Three statistical indexes are calculated to illustrate the effectiveness of our model on evacuation time as follows:(1)
The maximum evacuation timeTmax is the time of the last person left from the simulation scene, that is, Tmax=maxhTh, where Th is the evacuation time for pedestrian h.(2)
The average evacuation timeTave is the average evacuation time of all pedestrians, that is, Tave=∑hNTh/N, where N is the number of pedestrians in simulation.(3)
The average delay timeTdel is the average delay time compared with the evacuation time required on the shortest route under free flow, that is, Tdel=∑hNTh−Th0/N, where Th0 is the evacuation time for pedestrian h moving in the desired velocity vmax along the shortest route.Random distributions of pedestrian locations during the initialization lead to different results. To eliminate the differences in results, we simulate the same number of individuals at random locations 50 times. The statistical index is the average of 50 simulations listed in Table2. In Table 2, Err is the relative gap of the statistical index between DSG and SSG, which is calculated by Gap=the statistical indexinSSG−corresponding index in DSG×100%/the statisticalindex in SSG.Table 2
: Comparative results with different number of pedestrian.
NTmaxTaveTdelDSG (s)SSG (s)Gap (%)DSG (s)SSG (s)Gap (%)DSG (s)SSG (s)Gap (%)1017.0917.090.009.839.830.000.000.000.001517.0417.040.009.769.760.000.000.000.002017.0817.080.009.779.770.000.000.000.002517.0717.070.009.729.720.000.000.000.003017.1817.180.0010.6510.650.000.860.860.003517.1617.160.0011.3311.330.001.541.540.004017.1217.120.0012.2112.210.002.182.180.004518.3619.113.9213.0113.271.962.993.072.615020.3422.7210.4815.2616.336.555.446.5516.9510026.4329.5510.5618.5921.3312.858.8511.4922.9815032.7538.6915.3522.927.1615.6813.0717.4224.9720044.5158.2123.5431.2840.4222.6121.4430.5829.8925062.8492.7032.2148.5768.3428.9338.7858.5133.7230082.14136.0539.6362.4599.2837.1052.6989.4441.09350104.68182.2142.5579.37139.4243.0769.52129.6446.37400130.21228.643.0496.36178.4946.0186.52168.7648.73As shown in Table2, as the number of evacuees increases, the difference in statistical indexes between the DSG model and the SSG model can be divided into three groups. The evacuation process can be divided into three situations accordingly.(1)
The first situation: In this situation, the number of pedestrians is relatively small (N<30), and the above three statistical indexes for DSG and SSG are equal. In particular, Tdel is zero for DSG and SSG. It follows that when the number of people is small, the sign direction in the DSG model is the same as that in the SSG model, both pointing to the nearest exit along the shortest route. It makes the same pedestrians in DSG and SSG move in the same trajectory. As a result, Tmax and Tave are the same in both models. Furthermore, everyone can also move with vmax without congestion during the evacuation process; hence, the delay time is zero in both models. During the simulation, we find that the initial position of pedestrians has a negligible impact on Tmax and Tave.(2)
The second situation: In this situation, the number of pedestrians is30≤N≤40, and the above three statistical indexes for DSG and SSG are equal. Unlike the first situation, Tdel is greater than zero. The equality of statistical indexes shows that the sign direction under DSG is the same as that under SSG. However, with the number of pedestrians increasing, it causes congestion on some evacuation routes. Hence, the delay time is greater than zero. Meanwhile, the increase in the number of pedestrians will increase the congestion and its duration, making a positive correlation between Tave and N. Nonetheless, not all pedestrians would be affected by the congestion. As a result, Tmax is still randomly distributed.(3)
The third situation: In this situation, the number of pedestrians isN>40, and statistical indexes of DSG are all smaller than that of SSG. It means that the sign direction under DSG will be adjusted according to the congestion and waiting time at the exit. This adjustment can guide pedestrians to detour or even change the exits. In this way, pedestrians are distributed in balance on evacuation routes and exits, with minimum total travel time cost. Overall, all the three statistical indexes of DSG and SSG increase with the number of pedestrians.Generally, as listed in Table2, there is no significant difference between the SSG and DSG in the first and second situations due to the relatively low density of pedestrians and the absence of congestion during evacuation. However, as the number of pedestrians increases (N>40), the relative gaps of all three statistical indexes almost increase. For instance, the relative gap of Tave is 12.85% when the number of pedestrians is 100 and 37.1% when the number of pedestrians is 300. Through the above analysis, we can conclude that the more the pedestrians in evacuation, the better the improvement of DSG over SSG on evacuation time and delay time.


## 5.3. Effectiveness of DSG at a Different Location

This subsection mainly focuses on analysing the effect of DSG at different locations on the evacuation process. We counted the number of sign direction changes for each gird during the simulation, as shown in Figure7. According to the number of changes, the grids where these signs are located can be divided into two types, described as follows.(1)
For the first type of grids, the change times of sign direction are less than 5, and most of them are 1, namely, the sign directions in these grids change from the undirected state shown in Figure1(c) to a specific direction shown in Figures 1(a) and 1(b) at the beginning of the simulation, and will be maintained until the end of the simulation, like the grids numbered in 1–9 in Figure 5. It indicates that the direction states of the signs in this type of grids are stable, and the optimal route and exit guided by these signs do not change with the fluctuation of pedestrian flow in the grids. This type of grids accounts for a significant proportion of the whole evacuation area, as shown in Figure 7.(2)
For the second type of grids, the change times of sign direction are more than 5, and most of them are even greater than 10, such as the grids numbered 47, 48, 49, 50, 58, and 68 in Figure5. Namely, the sign direction changes in this type of grids are more frequent than those in the first type of grids. As shown in Figure 7, the scene, in this case, can be divided into two regions with and without square filling. The pedestrians in these two regions choose exit B and exit A, respectively. And the second type of grids is mainly located on both sides of the boundary line (red dot line in Figure 7) of these two regions. It may be because that the travel time from the boundary grid to the two exits is relatively close, so even slight changes in the pedestrian flow can cause the two evacuation times through exit A and exit B to take turns to be the larger one. As a result, exit A and exit B will alternate between being the nearest exit of the boundary grid. This alternation further leads to frequent guidance adjustment of dynamic signs in these boundary grids. These boundary grids are different from the first type of grids where the travel time to one of the exits is much greater than that to the other one, and fluctuations in pedestrian flow have little effect on the alternation of shortest routes and exits. Therefore, we believe that the second type of grids is more sensitive to pedestrian flow than the first type of grids. And DSG in the second type of grids may have a more significant impact on evacuation time.Figure 7
The change times of dynamic sign direction in the grids.To evaluate the influence of dynamic guidance in the above two types of grids, we perform seven sets of comparative simulation experiments for each of the two types of grids with different signs, as shown in Table3. In Table 3, the grid with no signs means it is an undirected grid, while the grid with static grids means the signs in that grid always direct to the nearest exit. Set the number of pedestrians as N=300. The above experiments are simulated 50 times, respectively, and the initial locations of these pedestrians are the same in each simulation.Table 3
: Experimental scheme for different evacuation sign guidance.
Experiment no.The signs set in the gridsTave (s)The first type of gridsThe second type of grids1Dynamic signsDynamic signs62.412No signsDynamic signs62.653Static signsDynamic signs62.474Dynamic signsNo signs71.85No signsNo signs71.866Dynamic signsStatic signs97.597Static signsStatic signs99.36As shown in Table3, Tave of the seven groups of experiments can be divided into three grades. Among them, Tave of experiment 1, 2, and 3 in the first grade is less than 63 s; Tave of experiment 4 and 5 in the second grade is 71.8 s and 71.86 s, respectively; and Tave of experiment 6 and 7 in the third grade is greater than 97 s. Within the same grade, Tave of all experiments with the same evacuation signs in the second type of grids and different signs in the first type of grids are close. It can be seen that whether set as dynamic signs, static signs, or no signs in the first type of grids, the impact on evacuation time is not significant. Therefore, in practice, static signs can be set in the first type of grids, and their guidance directions can be optimized in advance to save computational costs.Comparing the experiments of different grades, we can be seen thatTave of each experiment differs greatly when the evacuation signs are the same in the first type of grids and different in the second type of grids. For example, when the first type of grids are set to dynamic signs, Tave is reduced by 35.18s and 9.39 s if the second type of grids is set to dynamic signs, compared to static signs and no signs, respectively. It can be concluded that there are some critical grids similar to the second type of grids in the evacuation area. These critical grids play an important role in balancing congestion and improving evacuation efficiency. Combining with experiment 2 and experiment 3, we can know that focusing on optimizing DSG in these critical grids can improve calculation efficiency while realizing good evacuation effectiveness.


## 5.4. Effectiveness of Dynamic Guidance at Different Periods

In the previous experiments, we assumed thatδ=0.1s, indicating that the sign direction may change every 0.1 s. However, this is unreasonable because frequent adjustments of sign directions in a short period leave pedestrians without enough reaction time, which may bring chaos to evacuation. Therefore, to relieve the confusion, we set the time interval between two sign direction adjustments to an acceptable value. This setting means that the dynamic guidance of signs is limited. Based on experiment 3 in Table 3, the effect of DSG on Tave with limitation is discussed in this subsection.According to experiment 3 in Table3, we know that Tmax is no less than 73.4 s in the above simulation scene with 300 individuals. Therefore, we set the sign direction to change no more than seven times so that δ is greater than 10s. Let the number of sign direction adjustment h=1,2,…,7, and δ=Tmax/h, where Tmax≥82s. With this setting, Tave for the same initial pedestrian distribution under different h is counted, as shown in Figure 8.Figure 8
The average evacuation time with different number of sign direction optimization.From Figure8, it is easy to see that the average evacuation time increases with the number of dynamic sign direction optimization from 0 to 1, while it decreases gradually when h>1. It implied that when h=1, the dynamic sign direction no more changes after optimization, which will cause a maximum evacuation time similar to the static signs. And when h>1, the dynamic sign direction in the second type of grids will be optimized several times according to the pedestrian distribution, effectively reducing evacuation time.To analyse the effectiveness of DSG onTave in the different periods, we design five simulation experiments based on experiment 3 in Table 3. In each experiment, four times of dynamic sign direction optimization are employed with an interval of 10s in the second type of grids, that is, h=4 and δ=10s. In the five experiments, the only difference is that the start time of dynamic sign direction optimization is different, which are at 0s, 10s, 20s, 30s, and 40s, respectively. The average evacuation times corresponding to the five simulations are 74.07 s, 73.16 s, 72.62 s, 72.2 s, and 71.88 s, respectively, as shown in Figure 9.Figure 9
The average evacuation time with DSG in different periods.The comparative results show that the performance of dynamic guidance in the later period is better than that in the early period under the same situation. The following reasons may cause this performance. Firstly, the pedestrian distribution in the early period is more uniform than that in the later period. And the pedestrian flow in the second type of grids is uncrowded. As a result, the dynamic sign direction optimized according to the initial pedestrian distribution may not be consistent with the pedestrian distribution in the later stage, resulting in prolonging evacuation time. Secondly, in the later period, pedestrians in the critical grids are more than that in the early period. Thus, the optimization of DSG employed in the later period may be more practical, and the optimization results would affect more pedestrians to reduce evacuation time.


## 5.5. Limitations

The goal of the work is to achieve dynamic evacuation guidance. The optimization of DSG is the core model in an evacuation guidance system. A complete evacuation guidance system framework includes three modules: detecting devices, back-end computing, and evacuation guidance display. This paper deals with the development of the latter two modules but not yet with the detecting devices. The detecting devices mainly collect pedestrian locations and input the pedestrian density of grids to the DSG model. In this paper, the density of pedestrians in grids is obtained using a simulation method. However, in practice, pedestrian density needs to be obtained with sensors for pedestrian detection. For example, the whole evacuation scene can be monitored by installing a large number of videos. Each video monitoring area can be considered as a grid. The grid density of the DSG model can be obtained by identifying the number of pedestrians within the video. Thus, a DSG-based evacuation guidance system can be implemented.


## 6. Conclusion

This paper proposes a bi-level programming model for the direction optimization problem of dynamic signs in buildings. (1) The upper-layer model takes the dynamic sign direction as the decision variables and minimum evacuation time as the optimization objective from the managers’ perspective. (2) In the lower-level model, a DPA model consistent with the DUO principle is extended to describe individuals’ route choice behaviour to achieve a balanced pedestrian distribution on the route. While to estimate the evacuation time according to the congestion, a formula is given to calculate the queuing time according to the point queuing model based on the cell transmission model in the lower-level model. A heuristic algorithm is developed to solve the bi-level programming problem.Several numerical experiments are performed to verify the effectiveness of the proposed approach. The results indicate that (1) the more pedestrians in evacuation, the better DSG performs than SSG on evacuation time. (2) DSG at different locations in the evacuation scene has various features. The direction of DSG in the boundary grids changes frequently, and the change times of which are more than 5, and most of them are even greater than 10. On the contrary, the change times in the no-boundary grids are less than 5, and most of them are 1. It indicates that DSG in the boundary grids is more sensitive than that in no-boundary grids. Thus, focusing on the optimization of DSG in these critical grids can improve calculation efficiency. (3) The different periods of DSG have various achievements. The optimization of DSG employed in the later period may be more practical, and the optimization results would affect more pedestrians to improve the evacuation efficiency.In this work, all pedestrians are assumed to obey DSG perfectly. However, it is not similar to the actual situation. In reality, pedestrians may not fully comply with DSG due to herd behaviour and panic during evacuation. Therefore, various random factors need to be considered in the model to describe the probability of pedestrian obedience to DSG. Besides, the time interval for dynamic sign direction adjustment was set to10s due to the size of the numerical experiments. However, in practice, this time interval is still short for pedestrians. Therefore, the numerical example of a large-scale evacuation scenario can be performed in the future. In addition, we optimized the guidance direction of signs based on the crowd distribution but did not consider the evolution of hazardous events. Hazardous events may lead to path interruption, which are very different from path congestion due to unbalanced crowd distribution. Therefore, DSG considering the evolution of hazard events should be conducted in future work.



---

*Source: 2555350-2022-01-21.xml*