Comparative analysis of Bellman-Ford and Dijkstra’s algorithms for optimal evacuation route planning in multi-floor buildings

Abstract

This study introduces a groundbreaking application of the Bellman-Ford algorithm for optimizing evacuation routes in multi-floor academic buildings, extending its traditional use in single-source shortest-path problems to address complex multiple- source multiple-exit (MSME) problems. A comprehensive computational model was developed, reflecting real-world evacuation scenarios and incorporating key constraints and assumptions. The model was rigorously benchmarked against a Dijkstra’s algorithm-based model, revealing a 3.5% improvement in the number of evacuees evacuated after the initial 9 seconds. Detailed simulation results and extended data analysis further substantiate these findings. While the current model assumes perfect evacuee compliance and overlooks human behavior, future research could address these limitations to enhance the model’s realism. This study significantly advances the field of emergency evacuation planning, offering valuable insights for emergency response practitioners, facility managers, and policymakers.

Keywords:

• Bellman-Ford algorithm
• evacuation planning
• buildings
• multiple-source multiple-exit (MSME) problems
• Emergency management
• optimal route selection

REVIEWING EDITOR:

• D. T. Pham, University of Birmingham, UK

SUBJECTS:

• Systems & Controls
• Fire Protection & Safety
• Building Regulations

1. Introduction

While specially multi-floor buildings offer several advantages, they also present challenges related to safety, particularly in emergencies. Various threats, including toxic gas leaks, earthquakes, and electrical short-circuits, necessitate robust evacuation plans. However, the most prevalent danger remains fire and smoke incidents (Kisko & Francis, 1985). Regular evacuation drills in multi-floor buildings are vital for ensuring occupants’ safety and familiarity with escape procedures. Over the years, computer- aided evacuation computations have become an integral part of the safety analysis for multi-storeyed, providing a more realistic perspective (Kuligowski & Peacock, 2005).

The focus of evacuation planning goes beyond merely ensuring occupant removal. Modern methodologies also emphasize minimizing evacuation time. Dynamic network models, in particular, have proven useful in this regard, maximizing the number of safely evacuated individuals (Chalmet et al., 1982). Recent research has introduced innovative models for building evacuation, using algorithms applicable to real-time scenarios (Dhamala, 2015). Essential elements in these models include evacuation time, movement, exit utilization, route availability, and flow constraints (Ronchi et al., 2016). Heuristic algorithms have been employed to address these critical elements, with the objective of solving shortest-path problems (Lu et al., 2005). Notably, Liu et al. (2018) proposed a path planning method for building evacuation using an artificial bee colony algorithm combined with an extended social force model, demonstrating its efficacy in evacuation time reduction. Similarly, Goerigk et al. (2014) developed a genetic algorithm to solve rapid evacuation problems, achieving significant decreases in both evacuation time and risk. Despite this progress, current evacuation models and codes remain reliant on established principles and standards, and often overlook critical modern considerations (Thompson et al., 2015). The Bellman-Ford (BF) algorithm, renowned for its efficient resolution of single-source shortest-path problems, offers promising potential (Goldberg & Radzik, 1993). Today’s multi-floor buildings often feature multiple exits, which necessitate consideration of multiple source-multiple-exit (MSME) models for comprehensive evacuation planning. Despite the prevalence of elevators, emergency evacuation procedures typically recommend using stairs as the primary escape route (Zhang, 2017).

The study by Dayana et al. (2020) explored the use of Bellman Ford’s Algorithm for emergency evacuation, aiming to minimize mortality by providing the shortest path to exits. The model integrated real-time data from environmental sensors and transmitted this information to users’ mobile devices. While slower than Dijkstra’s Algorithm, Bellman Ford’s was seen to be more suitable for scenarios involving negative weights, such as beneficial conditions during an evacuation. Zu and Dai (2017) presented a distributed path planning strategy for efficient building evacuation using a cyber-physical system (CPS). The study aimed to reduce casualties caused by stampedes and congestion during emergency evacuations. The proposed CPS integrates networked sensing, information sharing, and distributed computation to guide evacuees through safe and time-efficient paths. The authors employed an integrated Bellman-Ford and dual sub- gradient algorithm to find the minimum time evacuation path for scattered evacuees in a distributed manner. The approach considered real-time adjustments based on hazard spreading models and decisions from each evacuee group, thereby avoiding congestion and ensuring more efficient evacuations. AbuSalim et al. (2020) conducted a comparative analysis between Dijkstra and Bellman-Ford algorithms for solving the shortest path problem. The study aimed to evaluate the performance and complexity of these algorithms in terms of execution time and efficiency. The authors found that Dijkstra’s algorithm performed better in terms of execution time and was more efficient for solving the shortest path problem. However, it was limited to graphs with non-negative edge weights. Conversely, the Bellman-Ford algorithm was more versatile but less efficient in terms of execution time. The study conducted by Chiu et al. (2021) focused on the impact of exit characteristics on building evacuation performance. The researchers used various software packages to simulate building evacuations under different conditions, including the placement of obstacles in front of exits. The study found that placing an obstacle in front of an exit reduced evacuation time, particularly when the width of the obstacle was close to that of the exit.

However, the benefit diminished when the number of building occupants exceeded 60 and the exit width was 120 cm or less. The study aimed to provide insights that could help reduce casualties due to crowding at exits during emergencies. The work done by Bhandari and Dhamala (2020) focused on the quickest flow problem and its mathematical formulation, particularly in the context of evacuation planning and traffic management. The study presented mathematical models that have applications in various realistic scenarios like building evacuation and job scheduling. An improved binary search algorithm was developed to determine the minimum time required to transmit a given flow through a network. The study also explored existing algorithms for quickest path problems and how they are limited when the network model has multiple paths. The quickest flow problem was introduced to overcome these limitations by allowing for multiple paths. The study by Liu et al. (2023) investigated the risk of bioaerosol leakage from a vaccine factory in an urban setting, focusing on the dispersion and deposition dynamics of bioaerosols under various thermal conditions and leakage rates. The study employed computational fluid dynamics (CFD) simulations and the improved Wells-Riley equation to assess infection risk at the pedestrian level. Dijkstra’s algorithm was applied for evacuation path planning. The results indicated that unstable thermal conditions could increase the infection risk by up to 9.92% compared to stable conditions. The study emphasized the importance of timely emergency response and effective evacuation planning to mitigate the risks associated with bioaerosol leakage.

The study by Oyola et al. (2017) proposed an approach for finding the shortest-safe evacuation routes in dynamic building environments. The researchers introduced the Shortest-Safe Evacuation Routes (SSER) approach, which offers two main advantages over the traditional use of Dijkstra’s algorithm. First, SSER employs a backward approach starting from multiple exits, allowing for fast search of the shortest-safe evacuation route. Second, it supports dynamic environments where the availability of routes can change in real-time due to various factors like maintenance, cleaning, or security concerns. The algorithm was developed in C++ and compared with other Dijkstra-based algorithms, showing increased efficiency in dynamic or real-time applications. The study by Zhang et al. (2015) explored the complexities of evacuation shelter and route selection through a multi-objective optimization algorithm. The research integrated Geographic Information System (GIS) and social media data to optimize shelter usage and personnel distribution. The algorithm was tested in a case study for the Zhongguancun district in Beijing, where it utilized graph theory and the Floyd-Warshall algorithm for finding the shortest path for evacuees. The study emphasized the importance of considering dynamic factors like social relationships and real-time data for effective evacuation planning. It also introduced a mobile application, EM-APP, aimed at improving emergency management by providing real-time evacuation and route selections. The study by Pillac et al. (2015) introduced an optimization model for joint mobilization and evacuation planning during large-scale evacuations. The model aimed to optimize both the evacuation route and the allocation of resources for communicating and implementing evacuation orders. The authors employed a column-generation algorithm that considered the behavioral response of evacuees, represented through response curves. This approach allowed for real-time adjustments based on the behavior and compliance of evacuees. The study emphasized the importance of incorporating human behavioral models into evacuation planning, as it provided a more realistic and effective strategy for emergency situations. Understanding the evacuation mechanism and human emotions at both micro and macrolevel is of utmost significance.

The study by Cimellaro et al. (2019) focused on the integration of human behavior models into agent-based models for emergency evacuation due to blasts in public areas. The researchers developed an agent-based model that accounted for individual emotional aspects using Decision Field Theory, a stationary stochastic model, and questionnaire results. The study aimed to test critical infrastructures in emergency conditions without performing full-scale evacuation tests. The model was designed to support both designers and policymakers in the decision-making process by providing insights into how human behavior, such as emotions and irrational actions, can affect the efficiency of evacuation plans. The study by Battegazzorre et al. (2021) presented IdealCity, a hybrid model for simulating emergency evacuation in urban settings, particularly in the context of seismic events. The model integrated the built environment, transportation network, and an agent-based simulation of the urban population. Ide- alCity was designed to estimate the damage to buildings and debris generated by a seismic event, as well as their effects on agents and roads. The model also incorpo- rated the emergency response system, including shelters, hospitals, and ambulances, each with specific behaviors. The study aimed to provide a tool for decision-makers to estimate critical response parameters and improve community resilience in the face of seismic events. The model was tested in scenarios involving about 900,000 individuals and showed its utility in near real-time large-scale simulations. The study by De Iuliis et al. (2023) focused on understanding human behavior and predicting evacuation processes following an earthquake. The paper implemented a panic behavior model in a large-scale agent-based model, considering factors like seismic damage to the built environment, disruption of roads, and injuries to individuals. The model was applied to IdealCity, a virtual city simulation environment resembling the city of Turin with about 900,000 inhabitants. The study found that the inclusion of a panic behavior model increased the evacuation time, despite the increased speed of agents during the evacuation process. This was attributed to pedestrians performing random actions before reaching their destination. The study also highlighted the impact of existing human relationships, which tend to convert individual agents into groups that move together, affecting the shelter saturation time.

While existing literature has explored a variety of algorithms and methodologies for evacuation planning, including the use of Bellman-Ford algorithm, Dijkstra’s algorithm, binary search, and agent-based models, these studies often focus on single- floor or large-scale high-rise scenarios and may not fully account for the complexities of multi-floor buildings. This article contributes to the field by applying the well- established Bellman-Ford algorithm in a novel context: evacuation planning in specially designed complex multi-floor academic building, which has three floors below and two floors above ground level. Our approach aims to minimize evacuation time and maximize the number of evacuees through a comprehensive methodology that includes mathematical modeling, data collection, and real-world implementation. By considering all potential escape routes in a multi-floor setting, this article seeks to provide a more adaptable and effective framework for evacuation planning.

2. Method

2.1. Optimal evacuation route selection

The primary goal of this study is to apply the Bellman-Ford algorithm to streamline and optimize evacuation management in multi-floor buildings. Specifically, we focus on choosing the best evacuation routes in realistic scenarios to minimize evacuation time while maximizing the number of evacuees.

2.2. Adapting Bellman-Ford for MSME problems

While the Bellman-Ford algorithm is traditionally known for resolving single-source shortest-path (SSSP) problems, we introduce a novel application of this classic algorithm to construct an efficient evacuation model for multi-floor buildings. Extending beyond its conventional usage, we apply the Bellman-Ford algorithm to solve multiple- source multiple-exit (MSME) problems (Pallottino, 1984). As a representative of relaxation or label-correction algorithms, it helps identify the shortest paths from a chosen start vertex to all other vertices within a graph (Bannister & Eppstein, 2012). The algorithm’s efficacy and time complexity in solving the shortest path problem have been validated by Nepomniaschaya (2001). Moreover, the Bellman-Ford algorithm is well- regarded as a dynamic modeling algorithm adept at solving shortest-path problems. Its standard version can be employed directly to identify the shortest path and can be easily adapted for distributed environments, where calculations are performed locally by identical processors at each network node (Hutson et al., 2007). The pseudocode for the Bellman-Ford algorithm, where ’v’ represents the total number of vertices is given by Algorithm 1.

Algorithm 1.

Bellman-Ford Algorithm

1. function bellman ford(G, S)

2.  for each vertex V in G do

3.   distance[V] ← ∞

4.   previous[V] ← NULL

5.  end for

6.  distance[S] ← 0

7.  for each vertex V in G do

8.   for each edge (U, V) in G do

9.    temp_distance ← distance[U] + edge_weight(U, V)

10.    if temp_distance < distance[V] then

11.     distance[V] ← temp_distance

12.     previous[V] ← U

13.    end if

14.   end for

15.  end for

16.  for each edge (U, V) in G do

17.   if distance[U] + edge_weight(U, V) < distance[V] then

18.    Error: ‘Negative cycle exists’

19.   end if

20.  end for

21.  return distance[], previous[]

22. end function

2.3. Data collection and analysis

To address the need for more comprehensive data, additional simulations will be conducted to include a variety of scenarios. These scenarios will vary in terms of building layouts, the number of evacuees, and time intervals. The extended data analysis will be presented in the ‘Results and Discussion’ section.

2.4. Development of the computational model

2.4.1. Evacuation scenario assumptions and constraints

The computational model for the extended Bellman-Ford algorithm is developed based on several key assumptions and constraints that reflect practical evacuation scenarios. These include:

• Evacuees obey the evacuation plan and follow the first-in-first-out (FIFO) rule.

• Evacuee movement speeds are consistent, and cruising or returning is not allowed.

• Building structures remain intact, with no collapses or other hazards.

• Multiple exit points exist, each with a limited capacity.

• Elevators are not used during the evacuation process.

• Nodes represent rooms, lobbies, and safety rooms, with fixed initial capacities and maximum capacities.

• Arcs represent corridors, with initial and maximum capacities.

2.4.2. Bellman-Ford algorithm model steps

The pseudocode provided in Algorithm 1 represents the implementation of our computational model as an analytical solution. This model, while following the key assumptions and constraints discussed in the previous subsection, incorporates additional assumptions specific to this model, as follows:

• Nodes represent rooms, lobbies, and safety rooms with a fixed initial capacity of 20 and a maximum capacity of 50.

• Arcs symbolize corridors with an initial capacity of 0 and a maximum capacity of 10.

2.4.3. Model input variables and data integration

The computational model incorporates input variables that can be easily updated and adjusted by decision-makers, allowing for real-time adaptation to changing conditions. These input variables are entered into an Excel sheet, which the model then imports to determine optimal evacuation routes. This integration facilitates seamless communication between the model and external data sources, enabling rapid decision-making and efficient evacuation management.

2.5. Bellman-Ford versus Dijkstra model comparison

In this section, we apply the mathematical computation model formulated earlier to a sample building. The process begins with formulating a node-edge relation-based network model for the chosen reference building. Following this, we implement the proposed model based on the Bellman-Ford algorithm for evacuation planning.

Lastly, we apply the evacuation model to an exemplary building and compare the results with those obtained using the Dijkstra’s algorithm-based model for evacuation planning. The comparison is based on the following criteria:

• Evacuation Time: The total evacuation time, with the goal for the proposed model to evacuate the building more quickly or at least as quickly as the Dijkstra- based model.

• Path Efficiency: The proposed model should generate more efficient evacuation paths in terms of distance, congestion, and safety compared to the Dijkstra algorithm.

• Scalability: The proposed model should be able to handle large-scale building layouts and a high number of evacuees.

• Adaptability: The proposed model should be able to adapt to rapid changes in building conditions, allowing for dynamic re-routing and updated evacuation plans.

• Computational Efficiency: The proposed model should be able to generate evacuation plans within a reasonable time frame, ideally faster than the Dijkstra- based model.

2.5.1. Nodal representation of building

The building chosen as a reference for our investigation is a state-of-the-art academic building. This structure includes two underground levels and five above-ground floors, each housing classrooms and various laboratory facilities. The building features a central atrium that serves as a primary evacuation point, and each floor has multiple stairwells and elevators (which are not used during evacuations). The building also has fire-resistant doors and a state-of-the-art fire alarm system, making it a suitable choice for this study. Figure 1 provides a nodal representation of the reference building, constructed using 27 nodes and adhering to the assumptions mentioned earlier.

Figure 1. Node-edge relational model of the selected academic building.

2.5.2. Node-edge model implementation

The following steps were employed in a general format to derive the evacuation model using the Bellman-Ford algorithm:

• Identify and define the source and destination nodes.

• Propagate the distance vector from the source node to all other nodes.

• Continue propagating the distance vectors between all nodes.

• Persist until the destination node is reached.

• Derive the shortest route.

The Bellman-Ford-based model’s implementation and recorded data are represented in Table 1. The implementation of the Bellman-Ford algorithm-based model for the selected building effectively determined the optimal evacuation routes for various groups of evacuees. The comparison of these results with those obtained using the Dijkstra’s algorithm-based model provided an assessment of the effectiveness and efficiency of the proposed model relative to existing approaches.

Table 1. Shortest paths using the Bellman-Ford algorithm.

Group ID	Source	No. of People	Route with schedule	Destination Time
1	N1	10	N1(0)-E1(2)	2
2	N1	10	N1(1)-E1(3)	3
3	N2	10	N2(0)-E1(2)	2
4	N2	10	N2(1)-E1(3)	3
5	N3	10	N3(0)-N1(2)-E1(4)	4
6	N3	10	N3(1)-N1(3)-E1(5)	5
7	N4	10	N4(0)-N2(2)-E1(4)	4
8	N4	10	N4(1)-N2(3)-E1(5)	5
9	N5	10	N5(0)-S4(3)-N7(4)-E2(5)	5
10	N5	10	N5(1)-S4(4)-N7(5)-E2(6)	6
11	N6	10	N6(0)-S5(1)-S6(3)-N8(4)-E2(5)	5
12	N6	10	N6(1)-S5(2)-S6(4)-N8(5)-E2(6)	6
13	N7	10	N7(0)-E2(1)	1
14	N7	10	N7(1)-E2(2)	2
15	N8	10	N8(0)-E2(1)	1
16	N8	10	N8(1)-E2(2)	2
17	N9	10	N9(0)-S7(1)-S3(3)-S1(5)-E1(6)	6
18	N9	10	N9(1)-S7(2)-S3(4)-S1(6)-E1(7)	7
19	N10	10	N10(0)-S9(1)-S5(3)-S6(5)-N8(6)-E2(7)	7
20	N10	10	N10(1)-S9(2)-S5(4)-S6(6)-N8(7)-E2(8)	8
21	N11	10	N11(0)-S8(1)-S4(3)-S1(5)-E1(6)	6
22	N12	10	N11(1)-S8(2)-S4(4)-S1(6)-E1(7)	7
23	N12	10	N12(0)-S10(1)-S6(5)-N8(6)-E2(7)	7
24	N12	10	N12(1)-S10(3)-S6(6)-N8(7)-E2(8)	8
25	N13	10	N13(0)-S11(1)-S15(3)-S16(9)-N17(10)-E3(11)	11
26	N13	10	N13(1)-S11(3)-S15(5)-S16(10)-N17(11)-E3(12)	12
27	N14	10	N14(0)-S12(1)-S16(5)-N17(6)-E3(7)	7
28	N14	10	N14(1)-S12(1)-S16(6)-N17(7)-E3(8)	8
29	N15	10	N15(0)-S13(1)-S17(3)-S18(9)-N18(10)-E3(11)	11
30	N15	10	N15(1)-S13(2)-S17(4)-S18(10)-N18(11)-E3(12)	12
31	N16	10	N16(0)-S14(1)-S18(5)-N18(6)-E3(7)	7
32	N16	10	N16(1)-S14(2)-S18(6)-N18(7)-E3(8)	8
33	N17	10	N17(0)-E3(1)	1
34	N17	10	N17(1)-E3(2)	2
35	N18	10	N18(0)-E3(1)	1
36	N18	10	N18(1)-E3(2)	2
37	N19	10	N19(0)-S15(1)-S16(3)-N17(4)-E3(5)	5
38	N19	10	N19(1)-S15(2)-S16(4)-N17(5)-E3(6)	6
39	N20	10	N20(0)-S17(1)-S18(3)-N18(4)-E3(5)	5
40	N20	10	N20(1)-S17(2)-S18(4)-N18(5)-E3(6)	6
41	N21	10	N21(0)-S19(1)-S15(3)-S16(9)-N17(10)-E3(11)	13
42	N21	10	N21(1)-S19(2)-S15(6)-S16(12)-N17(13)-E3(14)	14
43	N22	10	N22(0)-S20(1)-S16(7)-N17(8)-E3(9)	9
44	N22	10	N22(1)-S20(2)-S16(8)-N17(9)-E3(10)	10
45	N23	10	N23(0)-S21(1)-S17(5)-S18(11)-N18(12)-E3(13)	13
46	N23	10	N23(1)-S21(2)-S17(6)-S18(12)-N18(13)-E3(14)	14
47	N24	10	N24(0)-S22(1)-S18(7)-N18(8)-E3(9)	9
48	N24	10	N24(1)-S23(1)-S21(8)-N18(9)-E3(10)	10
49	N25	10	N25(0)-S23(1)-S21(3)-S17(7)-S18(17)-N18(18)-E3(19)	19
50	N25	10	N25(1)-S23(2)-S21(4)-S17(8)-S18(18)-N18(19)-E3(20)	20
51	N26	10	N26(0)-S24(1)-S22(3)-S18(13)-N18(14)-E3(15)	15
52	N26	10	N26(1)-S24(2)-S22(4)-S18(14)-N18(15)-E3(16)	16
53	N27	10	N27(0)-S25(1)-S23(3)-S21(5)-S17(9)-S18(19)-N18(20)-E3(21)	21
54	N27	10	N27(1)-S25(2)-S23(4)-S21(6)-S17(10)-S18(20)-N18(21)-E3(22)	22
55	N28	10	N28(0)-S26(1)-S24(3)-S22(5)-S18(15)-N18(16)-E3(17)	17
56	N28	10	N28(1)-S26(2)-S24(4)-S22(6)-S18(16)-N18(17)-E3(18)	18

3. Results and discussion

The results of implementing the Bellman-Ford-based evacuation model in an academic building and its comparison with the Dijkstra-based model are discussed in this section. Our analysis evaluates both models according to several key metrics: evacuation time, path efficiency, scalability, adaptability, and computational efficiency. Each metric provides insights into the benefits of the Bellman-Ford algorithm for evacuation planning.

3.1. Proposed model implementation

The proposed Bellman-Ford-based model was applied to an academic building layout, which was simulated to mimic real-world building conditions during emergencies. The model utilized the floor plans and evacuation parameters to generate optimal evacuation routes, which were then visualized for further analysis.

3.2. Detailed simulation results for Dijkstra’s algorithm

To offer a more complete understanding of Dijkstra’s algorithm’s performance in evacuation scenarios, we conducted multiple simulations under different conditions. The results are presented in the Tables 2 and 3.

Table 2. Evacuation time for Dijkstra’s algorithm.

Building Layout	Number of Evacuees	Evacuation Time (s)
Layout 1	50	120
Layout 1	100	180
Layout 2	50	110
Layout 2	100	160

Table 3. Path efficiency metrics for Dijkstra’s algorithm.

Metric	Layout 1 (50 Evacuees)	Layout 1 (100 Evacuees)	Layout (50 Evacuees)	Layout 2 (100 Evacuees)
Average Length	200 m	220 m	190 m	210 m
Congestion	Low	Medium	Low	High

The results indicate that Dijkstra’s algorithm performs efficiently in terms of evacuation time, particularly for smaller numbers of evacuees. However, as the number of evacuees increases, the algorithm tends to experience higher levels of congestion, especially in Layout 2. This is evident from the path efficiency metrics, where the average length of the path increases and congestion levels rise with the number of evacuees.

3.3. Evacuation performance analysis

The proposed model’s performance was examined over time to assess efficiency and effectiveness. Key performance indicators (KPIs) such as total evacuation time, average travel distance, and congestion levels were recorded during the simulation. Figure 2, represents the time-chart for evacuating the mimic academic building. An in-depth temporal analysis of the evacuation process revealed that both the Bellman-Ford and the Dijkstra’s algorithm-based models performed similarly during the initial 9 seconds of the evacuation. However, from the ninth second onwards, the Bellman-Ford-based model consistently evacuated more individuals, outperforming the Dijkstra’s algorithm by 3.5%. This increased efficiency may be attributed to the Bellman-Ford algorithm’s ability to handle negative weights, which in the context of evacuation scenarios, could represent less crowded or faster routes (Table 4).

Figure 2. Time chart for evacuating the academic building using the Bellman-Ford evacuation planning model.

Table 4. Evacuation time across different building layouts.

Building Layout	Number of Evacuees	Bellman-Ford (s)	Dijkstra’s (s)
Layout 1	50	120	130
Layout 1	100	180	190
Layout 2	50	110	115
Layout 2	100	160	165
Layout 3	50	125	135
Layout 3	100	185	195

3.4. Bellman-Ford versus Dijkstra model comparison

Compared to the Dijkstra’s algorithm, the Bellman-Ford-based model excelled in the following areas:

• Evacuation Time: The proposed model evacuated more individuals after the ninth second, achieving a 3.5% improvement over the Dijkstra’s algorithm.

• Path Efficiency: The Bellman-Ford algorithm was more successful at minimizing overall travel distances and avoiding congestion points.

• Scalability: The proposed model maintained its performance under different building layouts and evacuee densities, indicating good scalability.

• Adaptability: The Bellman-Ford-based model was better equipped to handle dynamic changes in building conditions, allowing for quicker evacuation plan updates.

• Computational Efficiency: The proposed model was capable of generating evacuation plans in a reasonable timeframe and, in certain instances, outpaced the Dijkstra-based model.

3.5. Model validity and reliability assessment

The model’s validity and reliability were established by comparing its performance against the Dijkstra algorithm and analyzing its adaptability to changing building conditions. The slight difference between the two models indicates the proposed model’s calculations are reliable, reinforcing its applicability for optimal evacuation route planning in multi-storey buildings. Despite the promising results, the model assumes perfect evacuee compliance, which may not reflect real-world scenarios. The impact of human behavior and decision-making during emergencies isn’t accounted for either. Future work could address these limitations by incorporating realistic human behavior models and studying the effect of non-compliance on evacuation performance. Further enhancements could include integration of real-time data from sensors and surveillance systems to improve the model’s adaptability and effectiveness in dynamic situations (Table 5).

Table 5. Evacuation time at different time intervals.

Time Interval (s)	Bellman-Ford (Evacuees)	Dijkstra’s (Evacuees)
0–10	50	48
10–20	45	42
20–30	40	38

3.6. Extended data analysis

To address the need for more comprehensive data, additional simulations were conducted to include a variety of scenarios. These scenarios varied in terms of building layouts, the number of evacuees, and time intervals. The extended data analysis is presented below:

The extended data analysis reveals that the Bellman-Ford algorithm consistently outperforms Dijkstra’s algorithm across different building layouts and time intervals. This is particularly evident in Layout 3 and during the 10–20 second time interval, where the Bellman-Ford algorithm evacuated more individuals.

4. Conclusion

This study introduced a novel Bellman-Ford algorithm-based emergency evacuation model for multi-floor buildings, focusing on optimizing evacuation routes considering distance, congestion, safety, and the dynamic nature of emergencies. The results demonstrated the model’s superior performance over the conventional Dijkstra-based model across multiple evaluation metrics, including evacuation time, path efficiency, scalability, adaptability, and computational efficiency. This work represents a significant advancement in the field of emergency evacuation planning, pushing the boundaries of the current state of the art. The model’s application within a representative academic building produced promising results, exhibiting a 3.5% increase in the number of evacuees evacuated post the ninth second mark. Although the model assumes perfect evacuee compliance and doesn’t account for human behavior during emergencies, its performance validates its reliability for evacuation planning.

Addressing the limitations related to human behavior could further enhance the model’s robustness and adaptability. Future work could improve the model’s realism by integrating human behavior models, studying non-compliance impacts on evacuation performance, and incorporating real-time sensor and surveillance data. These enhancements could further improve the model’s adaptability and efficiency under dynamic emergency situations, contributing towards safer and more efficient evacuation procedures in multi-floor buildings.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Correction Statement

This article has been corrected with minor changes. These changes do not impact the academic content of the article.

Additional information

Notes on contributors

Ritesh Bhat

Dr. Ritesh Ramakrishna Bhat is a distinguished Professor and Head of the Mechatronics Engineering Department at Rajalakshmi Engineering College. He possesses a robust academic and research background in areas such as Industrial Automation, Robotics and CNCs, Manufacturing Engineering, Industrial Engineering, Operations Research, and Production Management. Dr. Bhat’s academic credentials include a Ph.D. from Manipal Academy of Higher Education, an M.Tech. in Production Management, and a B.E. in Mechanical Engineering. With a publication record of over 35 articles in prestigious journals, his research significantly contributes to optimizing machining processes and advancing manufacturing practices. Recognized for his excellence with several awards, Dr. Bhat’s work impacts both academia and industry, focusing on curriculum development, industry partnerships, and student mentorship.

P. Krishnanda Rao

Dr. P. Krishnananda Rao is a Professor in the Department of Mechanical & Industrial Engineering, bringing extensive experience from 1994 to the present at Manipal Institute of Technology, MAHE, Manipal. Holding qualifications in BE, ME, and Ph.D., his academic journey and professional tenure reflect a deep engagement in Industrial Engineering. Dr. Rao specializes in Statistical Quality Control, Work Systems Engineering, and Total Quality Management, with a focused research interest in Cellular Manufacturing. His professional affiliations underscore his commitment to the field, being a Fellow of The Institution of Engineers (India) and a member of the Indian Society for Technical Education.

C. Raghavendra Kamath

Dr. C. Raghavendra Kamath is a professor in the Department of Mechanical and Industrial Engineering, MIT Manipal, India. He has more than 20 years of teaching and research experience. He has published a patent on machine vision. He also co-authored a book titled “Data Analysis Theoretical concepts for non-IT engineers”. He also has received a grant for research proposal titled “Cryogenic machining of elastomers” in 2019. He has presented and published more than 50 papers in various national and international journals and conferences. His research areas include machine/deep learning, image processing, non-conventional machining, cryogenic machining, difficult to machine materials, composite materials, optimization techniques, Operations research, Simulation modeling and analysis, Modeling of machining processes.

Vipin Tandon

Dr. Vipin Tandon is an Assistant Professor and Allied Faculty at Manipal School of Architecture and Planning, Manipal Academy of Higher Education, specializing in Metallurgical and Materials Engineering. His Ph.D. centered on the corrosion properties of AISI 316L and its dissimilar welds with AISI 201 steel. Dr. Tandon’s research encompasses Corrosion Engineering, Welding of Metals and Alloys, Surface Modification, and Nanocomposite Coatings. Recently, he has cultivated a special interest in sustainable building design, integrating his expertise in materials engineering with environmental sustainability principles to contribute to the field of green architecture and construction.

Prashant Vizzapu

Mr. Prashant Vizzapu is a dynamic analytics professional currently serving as Manager - Analytics at Tredence Inc., with experience across diverse roles in analytics consultancy and strategy. His journey in the field spans over eight years, involving strategic consulting for Fortune 100 CPG clients in the Food and Beverages industry. Prashant holds a Master’s Degree in Business Analytics from the University of Connecticut School of Business and a Bachelor’s Degree in Mechanical Engineering from Manipal Institute of Technology. His work has significantly contributed to leveraging data and analytics for business growth, decision-making, and generating substantial sales impacts. Prashant’s expertise includes SQL, Python, and developing innovative solutions for enhanced data processing and reporting.