1 Introduction

The fire situation in China has undergone remarkable changes with rapid economic growth in recent years [1]. Buildings with complex structure, such as stadiums and shopping malls, began to proliferate to meet the needs of consumers. Meanwhile, the frequent occurrence of building fire has caused serious mass disasters. For example, a fire occurred in Jilin Shopping Mall on November 5, 2010 with a death toll of 19 [2] and Anyang Trade Company fire happened in November 21, 2022 with a death toll of 38. Statistics from the Fire and Rescue Department Ministry of Emergency Management showed that 168 people have died in building fires in China in 2021. Asphyxiating and irritating gases generated in building fires threaten the safety of evacuees, and those who successfully escape but have been exposed to high temperatures and concentrations of hazardous gases also face the possibility of death even after the fire has ended [3]. Therefore, emergency evacuation should focus not only on improving evacuation efficiency and shortening evacuation time but also minimizing the risks that evacuees may suffer in the process of evacuation.

Evacuation of pedestrians is a process of path decision and moving to the emergency exit when threatened. Conventional static path indication signs guide pedestrians to escape in unfamiliar environments, but static signs fail to predict the risks that people may encounter in escape paths. Therefore, researchers have paid considerable attention to the field of evacuation path optimization in recent years. Many studies have focused on optimizing evacuation time or path length to ensure the safety of evacuees from the perspective of evacuation efficiency [4,5,6,7,8,9,10,11,12,13] but ignore the potential risks caused by the spread of fire to different paths. Some scholars have used fire risk as the optimization objective. Balboa et al. [14] proposed a pathway to prohibit excessive hazardous gases and avoid the risk of hazardous gases in fires. Wang et al. [15] put forward an optimization objective that minimizes the total amount of harmful gas inhalation. Faouzi Kamouna [16] considered the concentration of harmful gases, temperature, and crowding in the path. Wang et al. [17] took into account the influence of smoke temperature, visibility, and CO concentration on evacuation in drilling platforms. In addition to considering the risk of combustion product in fire, many studies have emphasized evacuation models that integrate fire risk with other influencing factors. Chu et al. [18] established a model for optimizing variable pedestrian evacuation guidance that considers congestion, hazard, and compliance behavior. Mirahadi and McCabe [19] used evacuation time, proximity of evacuation path to the fire location, crowding, and next expected isolation of the fire area (unpassable areas) as optimization objectives. Song et al. [20] proposed an evacuation route selection approach that considers hazards and time for indoor spaces and assessed fire hazard using the fractional effective dose of carbon monoxide, oxygen, and carbon dioxide and heat.

Although these studies have introduced path risk into the path planning model, the selection of path risk factors presents limitations. Faouzi Kamouna [16] and Song et al. [20] neglected visibility. Risk factors proposed by Wang et al. [17] failed to consider the harm caused by heat. On the basis of previous studies, this work optimized risk factors, including smoke toxicity, temperature, visibility, and crowding. However, the risk classification standard is unclear. Song et al. [20] assessed the fire risk through the fractional effective dose although this method is not applicable to the evaluation of crowding. Shi et al. [21] assessed risk in fire evacuations from several aspects but the calculation of risk levels lacks homogenization. A semiquantitative method is cited in this study to homogenize the risk characterization and classify the different degrees of potential harm to personnel.

Researchers have proposed various methods for solving the path planning problem and achieving the optimization objective. A* [22] is a widely used heuristic-based algorithm that has been successfully used to solve the shortest path problem and obtain the optimal path for various path planning problems. However, it does not apply to path planning of multiple exits. Evolutionary computing (EC) methods, such as genetic algorithm (GA) [23], particle swarm optimization (PSO) [24], ant colony optimization (ACO) [21], and artificial bee colony (ABC) [25], have been gradually introduced into path planning in recent years. Meanwhile, the modification of these methods and integration of different algorithms have rapidly developed [26] despite demonstrating some drawbacks. For instance, GA typically converges prematurely to the local optimal solution, and its ability to explore space is limited. PSO depends on users to adjust the control parameters and achieve the required solution. In addition, premature convergence also exists in the evolution process when PSO is used to deal with complex problems. Premature convergence is not ideal because the result is only locally optimal instead of being globally optimal. The typical occurrence of premature and stagnation phenomena in ant colony algorithms when the swarm scale is large imposes restrictions on further applications [25]. Dijkstra algorithm is a simple but powerful classical method that has been widely used in various fields for path selection and solving single-objective shortest path problems in static networks [27,28,29,30,31,32]. However, the Dijkstra algorithm is unsuitable for solving shortest path problems in dynamic networks as well as the multi-exit path planning problem. The modified Dijkstra algorithm utilized in solving the bi-objective model proposed in this study can be applied to the calculation in dynamic networks. This extended algorithm significantly optimizes the solution efficiency of the model in multi-exit building fires and solves the bi-objective model to find a comprehensive optimal solution with dynamic adjustability that traditional algorithms lack.

A bi-objective model that considers path risk and length is proposed in this study. The risks considered in the model are more comprehensive than those of previous studies because they take into account hazardous gases, temperature, visibility, and crowding. A semiquantitative risk classification standard is adopted to characterize the risk in a more homogeneous manner. The Dijkstra algorithm is optimized to differentiate it from the classical version in the following aspects: dynamic adjustability, path disabling, and efficiency. The model and algorithm in this study will contribute to solving the multi-exit fire evacuation problem by planning a safe and efficient evacuation path for escapees.

2 Path Planning Models

2.1 Building Emergency Evacuation Network

Path selection is a multi-objective optimization problem that must weigh many factors during evacuation. Intricate passages within the building form a connected network graph on the basis of graph theory. The passage is regarded as the arcs, the intersections of the passage are the nodes, and the arcs represent the connections between nodes of the network. A building with fifteen rooms and two exits will be taken as the objective of the study, and its emergency evacuation network is shown in Figure 1.

Figure 1
figure 1

Emergency evacuation network structure

Full size image

The emergency evacuation network is defined as an undirected graph \(G\text{(}V,E\text{)}\), as shown in Figure 1, where \(V\) is the set of nodes and \(E\) is the set of arcs, and \({v}_{1}\),\({v}_{2}\), …\({v}_{n}\) is set as the nodes in the network, that is,\(V\)= {\({v}_{1}\),\({v}_{2}\), …\({v}_{n}\)}. \({v}_{n}\) is the destination node, \({v}_{s}\) is the source node, and \({e}_{ij}\) is the physical length of (\({v}_{i},{v}_{j}\)).

The two optimization objectives herein are path risk level and length. The optimal evacuation path refers to the path that encompasses the risk level as low as possible and the length as short as possible. The bi-objective optimization model can be formulated as follows:

$${F}_{1}=min{f}_{1}$$
(1)
$${F}_{2}=min{f}_{2}$$
(2)

in which \({f}_{1}\) represents the risk level in the evacuation path, \({F}_{1}\) is the minimum risk level among all evacuation paths. \({f}_{2}\) is the physical length of the evacuation path, and \({F}_{2}\) is the minimum physical length in all evacuation paths.

2.2 Risk-Objective Model

2.2.1 Establishment of the Model

The principle of the risk-objective model is to prioritize the safety of evacuees, with the goal o1f mitigating potential harm to evacuees during the evacuation. The following additional notation is used.

  1. (1)

    \({R}_{ij}\): The risk level of arc \(\text{(}{v}_{i},{v}_{j}\text{)}\).

  2. (2)

    \({x}_{ij}\): The decision variable with \({x}_{ij}={1}\) if arc \(\text{(}{v}_{i},{v}_{j}\text{)}\) is included in the fixed path and 0 otherwise.

The formulation of the risk-objective model under the real-time development of fire is described as follows:

Model I:

$$ F_{1} = \min f_{1} = \mathop \sum \limits_{i = s}^{n} \mathop \sum \limits_{j = s}^{n} x_{ij} R_{ij} $$
(3)

S.t.

$$ \sum\limits_{\begin{subarray}{l} j = s \\ j \ne i \end{subarray} }^{n} {x_{{ij}} } - \sum\limits_{\begin{subarray}{l} j = s \\ j \ne i \end{subarray} }^{n} {x_{{ji}} } = \left\{ \begin{gathered} 1~~~~~~~~\,\,\,\,\,\,\,\,\,\,\,\,\,\,~i = s~~ \hfill \\ - 1~~~~~~~~\,\,\,\,\,\,\,\,\,\,i = n \hfill \\ 0~~~~~~~\,\,\,\,\,\,\,\,\,\,\,\,\,\,otherwise \hfill \\ \end{gathered} \right. $$
(4)
$$ \sum\limits_{\begin{subarray}{l} j = s \\ j \ne i \end{subarray} }^{n} {x_{{ij}} } = \left\{ \begin{gathered} \le 1~~~~~~~~\,\,\,\,\,\,\,\,\,\,\,\,\,\,~i \ne n~~ \hfill \\ = - 1~~~~~~~~\,\,\,\,\,\,\,\,\,\,\,i = n \hfill \\ \end{gathered} \right. $$
(5)
$$ x_{ij} = 0, 1, \,i = 1, 2, \ldots , n, j = 1, 2, \ldots , n $$
(6)

where Eq. (3) represents the objective of model, which minimizes the risk level along the path. Constraint (4) guarantees a feasible path from source node \({v}_{s}\) to destination node \({v}_{n}\) by restricting the value of \({x}_{ij}\). Considering the feasibility of the evacuation plan and the urgency of the evacuation time, Constraint (5) is used to ensure that there are no paths with loops [33]. Constraint (6) is the 0–1 integer constraint of the decision variable \({x}_{ij}\).

2.2.2 Characterization of \({R}_{ij}\)

Any fire risk that causes physical and psychological damage to evacuees increases the possibility of death. Asphyxiating gases, such as carbon monoxide (CO) and hydrogen cyanide (HCN), and high temperatures are the main causes of death during and after fires [3]. Smoke output from a fire can reduce visible distance and delay escape time as it spreads out in the path [34]. Overcrowding also increases the stay time of evacuees at the fire scene. Huo et al. [35] studied the effect of pedestrian density on evacuation results and showed that the greater the pedestrian density, the more the pedestrians fall to the ground and die. Therefore, we use risk factors, including CO concentration, HCN concentration, temperature, visibility, and crowding, in calculating the path risk level.

\({R}_{ij}\) is the weighted average and expressed as follows:

$$ R_{ij} = \alpha_{1} r_{ij}^{CO} + \alpha_{2} r_{ij}^{HCN} + \alpha_{3} r_{ij}^{T} + \alpha_{4} r_{ij}^{Vis} + \alpha_{5} r_{ij}^{D} $$
(7)

where the sum of weight coefficients \({\alpha }_{i}\in [\text{0,1}]\) is 1. These coefficients denote the weights of different risk factors. The risk index is defined as the value converted from real-time changes of risk factors in arc \(\text{(}{v}_{i},{v}_{j}\text{)}\). \({r}_{ij}^{X}\in [\text{0,1}]\) corresponds to the risk index associated with CO, HCN, temperature, visibility, and crowding.

A semiquantitative method is cited to homogenize the risk characterization and classify the different degrees of potential harm to personnel from risk factors [16]. Risk classification are listed in Table 1.

Table 1 Risk Classification and Risk Index
Full size table
  1. (1)

    \({r}_{ij}^{CO}\) and \({ r}_{ij}^{HCN }\)

Acute exposure guideline levels (AEGLs) represent threshold exposure limits (adverse health effects are likely to occur beyond this level) for the general public and are applicable to emergency exposures ranging from 10 min to 8 h [36]. Three levels, namely, AEGL-1, AEGL-2, and AEGL-3, were developed and differentiated for five exposure periods (10 min, 30 min, 1 h, 4 h, and 8 h) using various degrees of toxic effects. AEGLs refer to airborne concentrations of chemicals above which a person could experience evident discomfort or irritation (AEGL-1), serious and long-lasting health effects (AEGL-2), and life-threatening effects or death (AEGL-3). AEGLs with exposure times of 10 and 30 min were selected as the risk index of CO and HCN [36, 37]. According to Table 1, ranges for CO levels are converted into risk indexes [16] (Table 2).

Table 2 Classification of \({r}_{ij}^{CO}\)
Full size table

Similarly, ranges for HCN levels are converted into risk indexes on the basis of AEGLs at exposure times of 10 and 30 min of HCN (Table 3).

Table 3 Classification of \({r}_{ij}^{HCN}\)
Full size table
  1. (2)

    \({r}_{ij}^{T}\)

Human tolerance to high temperature is limited. The maximum tolerance time (τ(T)) as a function of temperature can be summarized as Eq. (8) [21]. The results are listed in Table 4.

Table 4 Maximum Human Tolerance Time at Different Temperatures
Full size table
$$\tau \left(T\right)={1812}{e}^{-\text{0.046}T}$$
(8)

High temperatures indicate a short tolerance time of humans. The tolerance time of a human is only 7 min at 120 °C. Hence, the maximum tolerance time of 7 min is defined as the highest risk classification.

Ranges for temperature levels are converted into the risk index \({r}_{ij}^{T}\) on the basis of the calculated maximum tolerance time at different temperatures (Table 5).

Table 5 Classification of \({r}_{ij}^{T}\)
Full size table
  1. (3)

    \({r}_{ij}^{Vis}\)

The risk classification criteria of visibility are based on the experimental data of British subjects [38]. \({r}_{ij}^{Vis}\) is determined according to the visible distance when evacuees choose to turn. The experimental results demonstrated that 100% of experimenters choose to change direction when the visible distance of the passage is less than 0.6 m; therefore, the visible distance of 0.6 m is defined as the highest risk classification. Only 9% of experimenters chose to change direction when the visible distance of the passage is greater than 3.7 m; hence, the visible distance of 3.7 m is set as the acceptable risk. Visible distance values converted into the risk index \({r}_{ij}^{Vis}\) are presented in Table 6.

Table 6 Classification of \({r}_{ij}^{Vis}\)
Full size table
  1. (4)

    \({r}_{ij}^{D}\)

Crowding exerts a significant effect on the evacuation time because it determines the walking speed of evacuees. Interpersonal walking contact and stagnation occur when the crowd density reaches 4 person/m2 [39]; therefore, the crowd density of 4 person/m2 is defined as the highest risk classification. Evacuees can walk freely without contact when the crowd density is below 1.8 person/m2; thus, 1.8 person/m2 is defined as the acceptable risk. Ranges for density levels converted to the risk index are listed in Table 7.

Table 7 Classification of \({r}_{ij}^{D}\)
Full size table

2.3 Length-Objective Model

In addition to risks in the emergency evacuation path, the length of the path is a key factor that must be considered. Although the chosen evacuation path is low risk in some cases, it requires a large number of detours. Related studies have shown that crowding typically happen at the intersections of two arcs in the emergency network [33]. Meanwhile, an excessively long evacuation path will also inevitably affect the evacuation time, thereby increasing the probability of suffering from risks. On the basis of the risk-objective model proposed in Sect. 2.1, a length-objective model is established with the aim of minimizing the length of evacuation paths.

The formulation of the length-objective model is as follows:

Model II:

$$ F_{2} = \min f_{2} = \mathop \sum \limits_{i = s}^{n} \mathop \sum \limits_{j = s}^{n} x_{ij} e_{ij} $$
(9)

S.t.

(4), (5) and (6)

2.3.1 Bi-objective Model

Models I and II can be planned for the evacuation path with the minimum risk level and the evacuation path with the minimum length, respectively. However, this section establishes a bi-objective path planning model on the basis of Models and II to obtain the integrated optimal evacuation path with respect to fire risk and path length as well as the Pareto optimal solution of the two objective functions.

A bi-objective optimization problem will involve multiple objective functions and constraints. The other objective may deteriorate when one objective reaches optimality. Obtaining the optimal solution for all objectives is difficult in the case of mutual constraints and interactions of objective functions. Different levels of attention should be given to each optimization objective, especially when the risk level in the path is excessively high, and the weight of the risk in the objective function should be increased. Moreover, the value of the optimized objective function corresponding to a specific Pareto optimal solution will likely fail to meet the actual needs of evacuees. Multiple Pareto solutions can be determined on the basis of the Dijkstra algorithm, and the results can be dynamically adjusted as the fire spreads. Linearly weighing the optimization objectives is a common method for solving the bi-objective optimal path [21]. Each weight represents the relative importance of each objective to some extent.

We use the linear weighted sum method to convert the risk and length-objective models into a bi-objective path selection model as shown below:

$$F={\gamma }_{1}\frac{{f}_{1}}{{f}_{1}^{*}}+{\gamma }_{2}\frac{{f}_{2}}{{f}_{2}^{*}}$$
(10)

S.t.

(3), (4), (5), (6) and (9)in which \({\gamma }_{1}\ge 0, {\gamma }_{2}\ge {0}\), and \({\gamma }_{1}+{\gamma }_{2}={1}\). \({f}_{1}^{*}\) denotes the ideal risk level in the evacuation path, representing the minimum risk level from \({v}_{s}\) to \({v}_{n}\); \({f}_{2}^{*}\) denotes the ideal path length in the evacuation path, representing the shortest length from \({v}_{s}\) to \({v}_{n}\). If the objective weight vectors \({\gamma }_{1}\) and \({\gamma }_{2}\) vary, monotonic decreases and increases occur in \({f}_{1}\) and \({f}_{2}\), respectively.

3 Modified Dijkstra Algorithm

3.1 Main Part and Calling Algorithm

The classical Dijkstra algorithm is modified to solve the dynamic bi-objective model. The main part of the newly modified algorithm is shown in Figure 2, and algorithm \(b\) is the calling algorithm of the main part. The problem is reduced to using \({\gamma }_{1}={0}\) or \({\gamma }_{2}={0}\) to ensure that Algorithm \(b\) can be applied directly when solving the single objective problem. However, if a bi-objective is to be solved, then the optimal path will be constructed at the end of algorithm \(b\) through the search space of the weight vector in Figure 2. The essential idea of the calling algorithm \(b\) is that each additional subsequent node will update the weights of the network on the basis of the path that was found when implementing the Dijkstra algorithm [40]. The following notations are used to express the main part of the algorithm (see Figure 2) and the calling algorithm (see Algorithm \(b\)).

Figure 2
figure 2

The main part of the modified algorithm

Full size image

Let \(p\text{(}{v}_{j}\text{)}\) be the minimum value of objective function \(F\) among the evacuation paths. \({B}_{j}\) represents the path with \(F\) equal \(p\text{(}{v}_{j}\text{)}\);\(S\) is the set of nodes for which the shortest path has been found; \(\updelta \) represents the optimal point; \({f}_{1}\text{(}\updelta \text{)}\) and \({f}_{2}\text{(}\updelta \text{)}\) represent the values of \({f}_{1}\) and \({f}_{2}\) in the path of \(F=p\text{(}{v}_{j}\text{)}\), respectively; \(K\) denotes the number of arcs in the selected path; \({r}^{*}\) denotes a set criterion that represents the upper limit of the ideal risk level, that is, humans will likely suffer from the threat of fire beyond this point; and \({r}^{*}\) is set to 0.7.

Algorithm b

3.2 Risk Threshold

The risk threshold is imposed on each arc. If a risk factor of the objective node reaches the risk threshold when the algorithm searches for the path with the minimum objective value \(F\), then the algorithm will ignore this node and search again for the path with the minimum objective value \(F\). The node with crowding reaches the risk threshold and the four other risk factors that fail to reach the risk threshold will be reconsidered when all paths that can be selected are unavailable. These risk thresholds can be determined on the basis of the results of the analysis in 2.1, where the value of a risk index reaching 1 is set as the risk threshold. Therefore, the risk threshold is 600 ppm for CO, 21 ppm for HCN, 120 °C for temperature, 0.6 m for visible distance, and 4 persons/m2 for crowded density.

3.3 Super-Destination Node

Several exits exist in the majority of modern buildings, and the evacuation problem can be solved in an emergency evacuation network with multiple destination nodes. The emergency evacuation network in Figure 1 shows the problem of multiple destination with source nodes. The classical Dijkstra algorithm requires two exits \(\text{(}{v}_{3} {\text{and}} {v}_{18}\text{)}\) as destination nodes and others as source nodes. The algorithm must be repeatedly and inefficiently called 16 times to solve the model. Note that demanding high efficiency in solving the algorithm is logical considering the urgency of evacuation.

The modified algorithm establishes a super-destination node [41], which connects all exits to change the original network structure and sets the weights of edges connecting each exit to the super-destination node to zero. Moreover, it transforms super destination node into a source node and transforms each source node into a destination node. Therefore, the optimal path from the super-destination node to other nodes can be solved by calling the Dijkstra algorithm only once and then converting the original problem into a single source node and single destination node problem. This method does not affect the final result and significantly improves the efficiency of the solution. The structure of the changed network is shown in Figure 3.

Figure 3
figure 3

The structure of the modified emergency network

Full size image

4 Case Study

A simulation experiment of a building fire is used in this section to demonstrate the reliability and feasibility of the bi-objective model and modified Dijkstra algorithm.

4.1 Introduction of Simulation Scenario and Risk Factor Weight

The simulation experiment is based on a building with fifteen rooms, two exits (Exits A and B), and a total area of 1640 m2. The emergency evacuation network is shown in Figure 1. A 3D model of the building is built using PyroSim software, and internal channels are evenly arranged with CO detectors, HCN detectors, visibility detectors, temperature detectors, and thermocouples. The initial temperature was set to 20 °C. The sofa rest area in the corner was selected as the fire point.

The worst-case scenario considered in the experiment assumes that the sprinkler system fails and the combustion surface is set to sustainable combustion. The HRR (heat release rate) is the product of the fire area and HRRPUA (heat release rate per unit area). HRRPUA is set to 2000 KW/m2 and the burning area of the fire source is set to 0.45 m2 in the PyroSim model; hence, HRR is equal to 900 KW. The completed 3D PyroSim model is shown in Figure 4.

Figure 4
figure 4

PyroSim 3D model

Full size image

The numerical simulation of fire was carried out after building the model. Data of 30-, 90-, and 200-s moments were used in the analysis. The fire development process can be seen through a 3D smoke dispersion simulation and CO, HCN, visibility, and temperature slices. The CO slice is taken as an example. Fire conditions at 30-, 90-, and 200-s moments were obtained through the 3D smoke dispersion simulation (Figure 5).

Figure 5
figure 5

3D smoke dispersion and CO slice

Full size image

Weight coefficients of five risk factors in this experiment are set according to the statistical data of fire death causes. Asphyxiating gases, especially CO, are the most lethal risk factor in case of fire. Although inhalation of HCN may lead to rapid incapacitation, its effects are smaller than those of CO in many cases. For instance, fires that produce cyanide give off CO and combustion conditions producing high yields of HCN also lead to high yields of CO [3]. CO is generally a more lethal risk factor in building fires compared with HCN; therefore, the weight of asphyxiating gases, especially CO is set higher in this case, with temperatures being second only to both. Visibility and crowding affect the speed of people but could not this cause crowd crash, which in turn causes death; thus, the weight of visibility and crowding is typically minimized. Weight coefficients of the five risk indexes in this case were finally set to \({\alpha }_{1}=\text{0.4,} {\alpha }_{2}=\text{0.3, }{\alpha }_{3}=\text{0.2,} {\alpha }_{4}=\text{0.05,} {\text{and}} {\alpha }_{5}=\text{0.05}\).

4.2 Simulation Results and Analysis

Data of visibility, CO concentration, HCN concentration, and temperature in each path can be obtained through the detectors in the channel. Crowd density is set randomly via MATLAB. Fire data and crowd density of each path at 30, 90, and 200 s are listed in Tables 8, 9, and 10, respectively.

Table 8 Fire Data and Crowd Density for Each Path at 30 s of fire
Full size table
Table 9 Fire Data and Crowd Density for Each Path at 90 s of Fire
Full size table
Table 10 Fire Data and Crowd Density for Each Path at 200 s of Fire
Full size table

The bi-objective path planning model and algorithm are programmed using MATLAB, and optimal evacuation paths of different nodes at various moments and their objective value \(F\) are generated by combining fire data within each segment of the path obtained from the PyroSim simulation and the set crowding data. Node 7 is used as an example to analyze the optimal evacuation paths of people in this position at 30, 90, and 200 s. The optimal evacuation path is marked in green and the path where the risk factor reaches the risk threshold is marked in orange. The results of the optimal evacuation path for node 7 are shown in Figure 6.

Figure 6
figure 6

Optimal evacuation paths for node 7

Full size image

The smoke does not spread widely when the fire lasts for 30 s. The optimal evacuation path at this time is determined via path crowding and length. Paths v5–v7 and v12–v15 will be ignored by the algorithm because they reach the risk threshold at 30 s. Finally, the optimal evacuation path of node 7 is determined as v7—v8—v6—v3. The optimal evacuation path is the evacuation path with the minimum path length of 34.7 m and objective value \(F\) of 0.035. The smoke spreads nearly throughout the building when the fire occurs for 90 s, but other paths, except for v1—v4, v4—v10, v9—v10, and v10—v17, fail to reach the risk threshold. The optimal evacuation path at this time is mainly determined on the basis of the risk level. The optimal evacuation path for node 7 at 90 s is determined as v7—v11—v12—v15—v14—v18, with an evacuation path length of 42.3 m and objective value \(F\) of 0.042. The majority of paths have reached the risk threshold when the fire occurs for 90 s due to the prolonged diffusion of smoke. The algorithm will resume the forbidden paths and retraverse them to obtain the path with the minimum objective value \(F\) because paths of the nodes are generally infeasible. The optimal evacuation path for node 7 at 200 s is still determined as v7—v11—v12—v15—v14—v18, with an evacuation path length of 42.3 m and objective value \(F\) of 1.302. The optimal evacuation path for node 7 is summarized in Table 11. Combined with the fire numerical simulation results of PyroSim and smoke dispersion simulation, the optimal evacuation path is obtained through the path planning model and algorithm by avoiding the area with high risk level and optimizing the evacuation path length. If the classical shortest path algorithm is used, then the path chosen will always be v7—v8—v6—v3 or v7—v5—v6—v3. However, this approach has failed to provide safe path for escapees as the fire progresses Figure 7.

Table 11 Optimal Evacuation Path for Node 7
Full size table
Figure 7
figure 7

Optimal evacuation paths for node 1

Full size image

Node 1 is at the center of the fire, and the path length objective function exerts a strong effect on the objective value \(F\) because of its far distance from Exit B. The optimal evacuation path planned for it by the bi-objective path planning model and algorithm is always v1—v4—v5—v6—v3 with a path length of 47.6 m. The shortest evacuation path v1—v4—v5—v6—v3 is determined to be the optimal evacuation path with an objective value \(F\) of 1.768 given that paths around Exit A are typically not disabled by the algorithm at 30 s of the fire. At 90 s of the fire, the risk level at node 1 is higher than that of other locations because this node is in the center of the fire. Paths around node 1 have generally reached the risk threshold, and people here face the situation of infeasible paths; hence, the algorithm restores forbidden paths and re-traverses them to obtain the path v1—v4—v5—v6—v3 with the minimum objective value \(F\), which is 2.688; The majority of locations in the building are filled with a high concentration of smoke and almost all paths have reached the risk threshold at 200 s of the fire. Therefore, the algorithm restores the forbidden paths, and the minimum path length v1—v4—v5—v6—v3 with an objective value \(F\) of 2.772 is still determined to be the optimal evacuation path. The optimal evacuation path for node 1 is summarized in Table 12.

Table 12 Optimal Evacuation Path for Node 1
Full size table

The optimal evacuation path for node 1 is different from the case of node 7, which is situated in the center of the building and far from the fire location. The optimal evacuation path of node 7 is determined via the crowding and path length when the smoke does not spread widely. The shortest evacuation path v7—v8—v6—v3 that avoids the congested path is optimal at 30 s. However, the fire risk objective function exerts a strong influence on the target value \(F\) as the fire progresses. The optimal evacuation path of node 7 at 90 and 200 s will no longer choose Exit A with a high risk level. Node 1 is located in the center of the fire and far from Exit B. Subject to the path length objective function, paths with extremely long lengths will be given high objective value and therefore will not be prioritized at three moments. The optimal evacuation path v1—v4—v5—v6—v3 is always the path with the minimum objective value \(F\).

4.3 Feasibility Analysis of Model Application

The application of the method in actual cases will be presented in this section. Detection data of the on-site path risk factor plays a decisive role in the accuracy of the calculation results of the model. CO concentration, HCN concentration, and visibility can be detected by fire smoke sensors; environment temperature in the path can be measured by temperature sensors; and crowd density in the path can be measured by IR camera when this model is applied to multi-exit buildings. The optimal evacuation path can be displayed in intelligent evacuation signs that can change the direction of indication in real time through the real-time calculation of path risk and length rather than being static similar to traditional evacuation signs that can direct escapees to a dangerous path.

5 Discussion

5.1 Meaning

The length of evacuation path (which may result in additional evacuation time) as well as the harmful effect of fire on human health (which may lead to casualties) are considered in the proposed evacuation path decision model. Risk factors considered in this model are more comprehensive than most current models with fire risk as the optimization objective. Distinguishing from the way risk has been quantified in previous studies, a more homogeneous semiquantitative approach is used to quantify the effects of CO, HCN, temperature, visibility, and crowding on escapees. The risk index is calculated with reference to numerous previous studies to enhance the scientificity of the results. For example, AEGLs are used as a basis for quantifying CO and HCN.

Moreover, the modified Dijkstra algorithm improves not only the calculation efficiency in the case of multiple exits but also adjusts the weights of path length and risk in the optimal path. Compared with the conventional method that only sets risk thresholds for hazardous gases or temperatures, the modified Dijkstra algorithm does not initially consider the paths where CO, HCN, temperature, visibility, and congestion reach the risk threshold to ensure the safety of evacuation paths further. The model and method presented in this study will be useful for intelligent evacuation [42] in building fires and management of building fire safety.

5.2 Limitations

In this study, some necessary assumptions are given directly, whose credibility cannot be proven at present, but may be verified in the future.

  1. (1)

    The grading standards are assumed directly in Table 1 (the risk index corresponding to each risk level is set to 0, 0.5, 0.7, and 1). Only four risk classifications exist, and the range of risk factor levels corresponding to each risk classification may be a wide range, such as a CO concentration of 150 and 400 ppm, both of which correspond to a risk index of 0.5. Future investigations may focus on working out a more detailed risk classification and narrowing the range of levels corresponding to each risk classification.

  2. (2)

    The risk level corresponding to CO and HCN may be different from the actual situation, and the threshold of concentration may be small because AEGLs are established on the basis of susceptible people who are more sensitive to harmful gases than the general population. Hence, the results may be conservative. Future investigations can focus on exploring the risk classification criteria for hazardous gases with high applicability to most populations.

  3. (3)

    We set the weights of the five risk factors in the path risk level in the case study depending on how different risk factors affect evacuation and the degree of hazard to humans. For example, asphyxiating gases in fire, especially CO, present the maximum lethal risk factor and cause more than 50% of deaths due to asphyxiation (Statistics from Fire and Rescue Department Ministry of Emergency Management in China [43]). We therefore assigned a high weight to CO and HCN. However, our assumptions lack experimental basis. This supposition will be the premise of our future work to determine the weights of risk factors on the basis of a more scientific and rigorous approach.

6 Conclusion

A new decision method is proposed for generating optimal evacuation paths in real time. The method involves evacuation models that consider path length and risk and an optimization algorithm with dynamic adjustment capabilities.

The optimal evacuation path based on path length and risk considers risks, including CO concentration, HCN concentration, temperature, visibility, and crowding. A Semiquantitative approach was used to characterize the risk level of paths to improve the homogeneity of data. The modified Dijkstra algorithm was applied for optimization and the adjustment of the Pareto optimal solution of the two objectives as the fire progresses. The bi-objective model and algorithm directs pedestrians toward a safe path. The rationality and feasibility of the optimal evacuation path are verified using simulation experiment. The case analysis results showed that the optimal evacuation path obtained from the model can be adjusted with fire progression through the fire objective function.

The proposed method can plan an optimal path for evacuees of a multi-exit building fire in terms of combined path risk and length while ensuring safety and efficiency. However, this study neglected the physiological factors of people in fire events, such as falls, trips and walking speed. Moreover, a future investigation can focus on the validity of risk classification criteria in this study and risk factor weights as well as refining the case study methodology.