1 Introduction

Each year, many fires occur in buildings and many people lose their lives and property. The ability of the occupants of a building to evacuate in case of fire to a place of ultimate or total safety is a fundamental aspect of fire safety. A “means of escape” can be defined as the structural means whereby a safe route is provided for people to travel from any location in a building or structure to a place of safety without the need of outside assistance, https://app.croneri.co.uk.

Fire safety legislation places the onus on the “responsible person”—a person who has some level of control of premises, to assess, reduce, and manage fire risk. This includes ensuring that everyone who may be on the premises has a means of escape, https://www.marsden-fire-safety.co.uk. The safe egress and evacuation of disabled people require additional careful consideration and attention because not everyone with a disability will require help. There may be people with “hidden impairments,” a heart condition or epilepsy, which may require assistance in an emergency evacuation. Deaf people may not be able to hear the fire alarm, people with visual impairment may not be able to read fire exit signs clearly, and people with mental health issues may react in an unusual way (https://www.marsden-fire-safety.co.uk). Thus, it is not sufficient to try to evacuate people without considering a suitable plan adapted to the various emergency situations (Nasri and Bouziri 2014). Our main purpose is to produce a generic evacuation plan based on a set of variables. The evacuation time can thus be reduced if pedestrian behavior can be adapted to a building environment and controlled through education and training by identifying the risk factors and critical points (Khalid et al. 2018).

In this paper, a hybrid approach is utilized. The graph model is used as a tool for transforming building information into the data. The information is extracted directly from the building stored in a graph database. The evacuation time is calculated using a combination of M/G/C/C model and a metaheuristic algorithm.

The presented approach is applied to an office building using graph queries. While computing the length of indoor routes, the information about the existence of large open spaces (like halls, lobbies, and corridors), fireproof doors, and width of the doors is of vital importance. It is found that graph models can offer insight into the critical areas in an emergency evacuation and metaheuristic algorithms can provide useful estimates of the evacuation times for routing optimization.

One of the approaches to measure the performance of traffic rout in such a state-dependent network is using the M/G/C/C. Yuhaski and Smith (1989) presented a number of relationships between the walking speed of a pedestrian and the crowd density for circulation systems within a building. M/G/C/C measures the impact of various arrival rates by estimating the blocking probability. Chen et al. (2014) presented a vertical mixing evacuation model in high-rise buildings. They showed that the shortest evacuation time was obtained when a combination of elevators, staircases, and refuge floors was used. Khalid et al. (2018) indicated that the shortest route did not necessarily generate the optimal throughput and that the utilization of all available routes to pedestrian flow provided better performance. Desmet and Gelenbe (2013) showed that the analytical models based on queueing theory can provide fast estimates for the location of points of congestion. Nasri and Bouziri (2014) performed an experimental study on emergency evacuation from the Tunisian children’s hospital by TS algorithm. Strug and Ślusarczyk (2017) suggested intelligent knowledge-based navigation, which is based on the graph representation of the buildings in the design phase. Zhang et al. (2017) studied the fire evacuation and smoke spread in Atrium metro station. They also analyzed the escape environment, escape routes and reasonable evacuation time.

2 Problem Statement and Formulation

Two of the key concepts essential for finding the optimal routes in buildings are based on the topology of the spaces and information about the accessibility between the nodes of the topology. This information consists of the accessibility between spaces, height of the floors, and stairs and doors specifications. This information is used to search for the optimal routes.

In the first step of the search process, the topology of the building is stored in the graph model. In the second phase, the adjacency matrix is created and the distance matrix is calculated by Floyd–Warshall algorithm. After this step, the speed of people who use corridors and stairs in the evacuation event has to be estimated. The logic of the M/G/C/C approach can be utilized to analyze the performance of a queuing topological network (Han 2006). On the other hand, metaheuristic algorithms are an effective means to solve the problems that were resolved with probabilities in the past by taking less time and more restrictions.

2.1 Graph Representation of a Building

Theory of graphs has been efficiently applied to different problems in structures (Kaveh 2004, 2006). The graph model of a building concisely represents the connectivity of the building and enables the use of this branch of mathematics in its analysis and design. In this study, graphs enable the users to model the data exactly as they are represented in the real-world scenario, and this can significantly enhance the operations on data. Thus, graphs can keep all the information about an object in a single node and display the related information by relationships connected to it (Hor et al. 2018). When the structure of the building is stored in a graph, each space (room, corridor, etc.) is represented by a node, while edges represent connections and cost of passing between the spaces (Strug and Ślusarczyk 2017). Lift and stairs are connecting portals that connect different stores.

2.2 M/G/C/C State-Dependent Queuing Model

This model has been used in pedestrian and vehicular traffic flow. Experimental relationships between crowed density and walking speeds play an essential role in the development of the mathematical relations to determine the overall walking speed of the pedestrians as a function of the population density. It is reasonable that as the number of people along the corridor increases, the average speed of the pedestrians will tend to decrease.

These relationships are usually presented in graphical form (Fruin (1971) and Tregenza (1976)). Figure 1 is borrowed from Yuhaski and Smith (1989).

$$v_{n} = A\exp \left[ { - \left( {\frac{n - 1}{\beta }} \right)^{\gamma } } \right].$$
(1)
Fig. 1
figure 1

Variation of mean walking speed with crowd density a [HANK], b [OFLA], c [OLDE], d [TOGA], e [TOGA], f [FOOT]. Yuhaski and Smith (1989)

Full size image

A is the average walking speed of a lone occupant and is equal to 1.5 m s−1. A quantitative understanding of congestion can best be attained by considering unidirectional traffic along a corridor of length L and constant width w. β and γ are shape and scale parameters, respectively. These are found by fitting points to the curve by carefully approximating the positions of three representative points among the six curves in Tregenza (1976). In fact, Fig. 1 presents an approximation of empirical vehicular speed–density curves, based on various empirical studies Guerrouahane et al. (2017).

$$\gamma = \frac{{\ln \left[ {\frac{{\ln \left( {v_{a} /A} \right)}}{{\ln \left( {v_{b} /A} \right)}}} \right]}}{{\ln \left( {\frac{a - 1}{b - 1}} \right)}}$$
(2)
$$\beta = \frac{a - 1}{{\left[ {\ln \left( {\frac{A}{{v_{a} }}} \right)} \right]^{{\frac{1}{\gamma }}} }} = \frac{b - 1}{{\left[ {\ln \left( {\frac{A}{{v_{b} }}} \right)} \right]^{{\frac{1}{\gamma }}} }},$$
(3)

where

  • \(v_{n}\) = average walking speed for n pedestrians in a corridor,

  • \(v_{a}\) = average walking speed when crowd density is 2 peds/m2 = 0.64 m/s,

  • \(v_{b}\) = average walking speed when crowd density is 4 peds/m2 = 0.25 m/s,

  • n = number of pedestrians in a corridor,

  • a = 2 × l × w,

  • b = 4 × l × w.

2.3 Metaheuristic Algorithms

Nature has always been a major source of inspiration to engineers and natural philosophers, and many metaheuristic approaches are inspired by solutions that nature seems to have chosen for hard problems (Kaveh 2017a, b). Nature-inspired algorithms are very popular in solving real-life optimization problems (Balande and Shrimankar 2019). Metaheuristic algorithms provide good alternative solutions for problems that were resolved with probabilities in the past, by taking less time and more restrictions.

Time has a continuous nature, and our challenge here is to propose a metaheuristic solution for solving the evacuation problem. In this paper, the PSO, colliding bodies optimization (CBO) and an improved version of the colliding bodies optimization (enhanced colliding bodies optimization) are utilized.

PSO algorithm is based on the metaphor of social interaction and communication among different species in nature, such as bird flocking and fish schooling. The PSO was first introduced to optimize various continuous nonlinear functions by Eberhart and Kennedy and has been successfully applied to a wide range of applications.

In the PSO algorithm, each member is called a particle and each particle moves around in the multi-dimensional search space with a velocity constantly updated by the particle’s experience, the experience of the particle’s neighbors, and the experience of the whole swarm.

CBO and ECBO are two recently developed metaheuristic algorithms developed by Kaveh and Mahdavi (2014) and Kaveh and Ilchi Ghazaan (2014), respectively, and have found many applications, e.g., Kaveh and Talatahari (2011), Kaveh and Moradveisi (2016), Kaveh and Rezaei (2018), Kazemzadeh Azad et al. (2013), Kazemzadeh Azad (2016), and Hasançebi and Kazemzadeh Azad (2019).

CBO is a population-based stochastic optimization algorithm which is based on the simple physics law. The basic idea of the theory of colliding bodies optimization (CBO) is that the total momentum before the collision to be the same as the total momentum after the collision (Fig. 2), Kaveh and Mahdavi (2014). CBO has a simple concept and does not depend on any internal parameter. An efficient neighborhood structure and ease of coding are the core characteristics of this algorithm. In CBO, each CB is considered as an object with a specified mass and velocity.

Fig. 2
figure 2

Colliding body groups and the pairs of objects for collision

Full size image

In the initialization phase of the CBO, the positions of all individuals are randomly initialized [Eq. (4)]. In the second step, objective function is evaluated and masses are defined as Eq. (5):

$$x_{i}^{0} = x_{{{\rm{min}}}} + {\text{rand}}(x_{{{\rm{max}}}}^{{}} - x_{{{\rm{min}}}} ),\quad i = 1,2,{ \ldots },n$$
(4)
$$m_{k} = \frac{1}{{{\text{fit}}(k)}},\quad k = 1,2,{ \ldots },n.$$
(5)

At each iteration, a particle CBi adjusts its position xi and velocity vi according to the previous position and the velocity after the collision [Eqs. (4) and (6)]. The optimization process is repeated until the specified termination criterion, as the maximum number of iterations, is fulfilled.

$$v_{i}^{{\prime }} = \frac{{\left( {m_{i} - \varepsilon m_{{i - \frac{n}{2}}} } \right)v_{i} }}{{m_{i} + m_{{i - \frac{n}{2}}} }},\quad i = \frac{n}{2} + 1,{ \ldots },n$$
(6)
$$\varepsilon = 1 - \frac{\text{iter}}{{{\text{iter}}_{{{\rm{max}}}} }} .$$
(7)

The enhanced colliding bodies optimization is the improved version of CBO which was proposed for structural design by Kaveh and Ilchi Ghazaan (2014).

The steps of the ECBO are very similar to those of the CBO with two additional steps.

  • (i) Saving (this step is placed after defining mass in the CBO).

Consider a memory, which saves some best CB vectors and their related masses, and the objective function values. The solution vectors saved in CM are added to the population, and the same numbers of current worst CBs are deleted. Finally, CBs are sorted according to their masses in a decreasing order (Kaveh 2017a, b; Kaveh and Mahdavi 2014).

  • (ii) Escape from local optima (this step is placed after updating the new CBs). Metaheuristic algorithms should have the ability to escape from the trap when agents get close to a local optimum. In ECBO, a parameter denoted by Pro within (0, 1) is introduced, and it is specified whether a component of each CB must be changed or not. For each colliding body, Pro is compared with rand i (i = 1, 2,…, n), which is a random number uniformly distributed within (0, 1). If rand i < Pro, one dimension of the ith CB is selected randomly, and its value is regenerated (Kaveh and Ghobadi 2017).

2.4 Network Flow Model

The objective function is supposed to minimize the total time of the evacuation and establish a balance between exiting traffic to reduce the congestion in the evacuation route.

$$\hbox{min} \mathop \sum \limits_{i = 1}^{m} \left( {at_{i} x_{i} + bt_{i} y_{i} } \right),$$
(8)

  • m: the number of spaces in the building

  • n: the total number of occupants in the building

  • a and b: the numbers of people who are present at location i before the evacuation begins

$$\sum e + \sum f = n,$$
(9)

where

$$e \le f + 1,$$

e and f are the total traffic for each door exit. Equation (9) is used to make a balance between the traffic flows in exit doors.

$$\begin{aligned} x_{i} & = \left\{ {\begin{array}{*{20}l} {1\quad {\text{If}}\;{\text{people}}\;{\text{get}}\;{\text{out}}\;{\text{from}}\;{\text{entrance}}\;2} \hfill \\ {0\quad {\text{otherwise}}} \hfill \\ \end{array} } \right. \\ y_{i} & = \left\{ {\begin{array}{*{20}l} {1\quad {\text{If}}\;{\text{people}}\;{\text{get}}\;{\text{out}}\;{\text{from}}\;{\text{entrance}}\;1} \hfill \\ {0\quad {\text{otherwise}}} \hfill \\ \end{array} } \right. \\ \end{aligned}$$
$$t = {\raise0.7ex\hbox{$x$} \!\mathord{\left/ {\vphantom {x v}}\right.\kern-0pt} \!\lower0.7ex\hbox{$v$}} \left( {\text{s}} \right)$$
(10)
$$v_{ij} = \left\{ {\begin{array}{*{20}l} {{\text{in}}\;{\text{corridor}}\;{\text{is}}\;{\text{calculated}}\;{\text{according}}\;{\text{to}}\;{\text{the}}\;{\text{M/G/C/C}}\;{\text{analytical}}\;{\text{model}}} \hfill \\ {{\text{in}}\;{\text{staircase}}\;{\text{is}}\;14.6\;{\text{m/min}},\;{\text{namely}}\;0.24\;{\text{m/s}}.\;{\text{According}}\;{\text{to}}\;{\text{the}}\;{\text{United}}\;{\text{States}}\;{\text{NFPA130}}\;\left( {2014\;{\text{Edition}}} \right)} \hfill \\ \end{array} } \right.$$

3 Numerical Example

In this section, an example is presented, and the results for the multistage method are compared to those of three metaheuristic algorithms. The general structure of the example is taken from Strug and Slusarczyk (2017). The example is an office building with four floors. The building has two entrances: the main one with the stairs and a side one with a ramp allowing access for people with movement difficulties.

A fragment of a ground floor layout and 3D view for a building are shown in Figs. 3 and 4. The topology of the building is stored in the graph model shown in Fig. 5. Stairs, ramps, and elevators connect the graph of the stories to each other. The weights of all the edges are equal to (length × width) of the path, and the weight of all nodes is selected randomly between 1 and 5 persons in each space.

Fig. 3
figure 3

Layout of the building

Full size image
Fig. 4
figure 4

A 3D view of the floor layout from Fig. 2

Full size image
Fig. 5
figure 5

Graph model of the building in the ground floor

Full size image

By starting an alarm sound, evacuation from all locations takes place simultaneously. It should be mentioned that in an emergency case, if a building does not have a fire elevator like now, occupants are not permitted to use the elevators in the case of fire. Moreover, if a fire occurs near the staircase, the staircase door (fireproof doors) is also closed to prevent the spreading of smoke and to avoid the reduction in visibility during evacuation. In such situations, the cost of using an edge in the adjacency matrix increases considerably. With these two defaults, the evacuation time is investigated for various locations of fire in the building and the critical nodes have been identified. The results for various points of the fire are provided in Table 1.

Table 1 Minimum cost and CPU time for the considered numerical example
Full size table

Each algorithm is coded in MATLAB by considering 10 initial populations and 97 variables. In each implementation, the algorithm is capable to provide the best route for each location, report the evacuation time, and calculate the traffic of all the routes.

The comparisons of convergence histories for three algorithms in two conditions of first no fire in corridor and fire in two corridors (22 and 24) are provided in Figs. 6 and 7. Furthermore, Figs. 8 and 9 show the evacuation time for each location and the total number of persons who pass the corridors in the process of evacuation. As can be seen from Fig. 9, the traffic flow through the ground floor corridors is more than other corridors. Thus, more attention should be paid to these routes.

Fig. 6
figure 6

Convergence histories for the evacuation time (no fire in the corridor)

Full size image
Fig. 7
figure 7

Convergence histories of evacuation time (fire in corridor 24)

Full size image
Fig. 8
figure 8

Evacuation time for each location

Full size image
Fig. 9
figure 9

Total number of persons who pass the corridors in evacuation

Full size image

4 Conclusions

In this paper, a hybrid method is developed for efficient evacuation in fire. A weighted incidence graph is utilized to transform the connectivity of the components, and the method is improved by partitioning the occupants of a building by using metaheuristic algorithms in order to improve the planning of building evacuations. This approach is capable of supporting various incoming parameters and simulates different real-life evacuation scenarios.

Example of the previous section is studied by three metaheuristic algorithms, and their efficiencies are compared in Figs. 6 and 7. The analysis of Table 1 shows that if a fire occurs near the stairs, it increases the time of rescue and causes critical circumstance in the building. Therefore, this point is more important in monitoring the fire. Furthermore, it can be observed that the result for ECBO is quite adequate, compared to the PSO algorithm. The simple implementation, the ease of coding, and high convergence rate are the main characteristics of the ECBO.

The findings of this study have to be seen in light of some limitations. Simulation of human behavior is rather complicated. In a hazardous condition, decisions and behaviors of people are quite different and must be controlled by cyber-physical human systems (CPHS) to get closer to the calculated time in the example. Furthermore, the lack of quantitative studies in this area is an important issue; however, we were unable to make a proper comparison between the proposed methods and other studies.

Future research will aim at developing extensions of graph-based algorithms in building information modeling (BIM). The graph representation of information extracted from IFC files can also be used to search for accessible egress routes.