Optimal Path Search Algorithm for Emergency Cases

Introduction

Evacuation planning is an essential element of emergency planning for companies and organizations. In general terms, people should make their way to a safe place during the evacuation. Situations such as earthquakes, fires, gas leaks, or subsidence may be the reason for an evacuation (Künzer, 2016). The people who are affected must leave the buildings, business premises or educational institutions on their own as quickly as possible and in an orderly manner. In these situations that require evacuation, it is essential to determine which place should go to minimize the casualties.

In establishments particularly educational institutions, it is important that the people within be aware of reaching the nearest exit or must pay attention to evacuation process to minimize injuries. Students and personnel of the institution must be aware of the emergency strategies if anything might happen around the area. There should be a clear path going to the nearest exit of the buildings for an adequate evacuation plan and provide adequate instructions around the area to mobilize the evacuation in time of emergencies. Hitting to this situations, good evacuation planning must be carried out.

Proper evacuation planning for building or establishment should be considered. It can minimize or eliminate injuries during and after the occurrence. In this plan, the directions of the exit path should be emphasized to determine by the people for mobilizing evacuees effectively and efficiently.

There are many ways or method to create or develop an emergency evacuation plan, and one of those methods is the shortest path. In graph theory, the shortest path problem is the problem of finding a path between two vertices or nodes in a graph such that the sum of the weights of its constituent edges is minimized.

Dijkstra's Algorithm, introduced in 1959 provides one of the most efficient algorithms for solving the shortest-path problem. In a network, it is frequently desired to find the shortest path between two nodes. The weights attached to the edges can be used to represent quantities such as distances, costs or times. In general, if we wish to find the minimum distance from one given node of a network, called the source node or start node, to all the nodes of the network, Dijkstra's algorithm is one of the most efficient techniques to implement (“Dijkstra’s algorithm, n.d.”). In general, the distance along a path is the sum of the weights of that path (Biswas, 2005). The maximum capacity of the building that is accessible regarding the area of the path that people can occur can also consider in planning; this is to estimate the population may be involved in evacuating. Evacuation planning is usually done with the help of simulation tools that can give a realistic evaluation of particular evacuation scenarios such as Pathfinder simulation. It enables the update of the evacuation plan by people density information inside the enclosed areas and the interval of the entire process of evacuation.

Background of the Study

During the Earthquake Resilience Conference in Makati City on May 2015, there are five areas in Metro Manila which have been identified by as “highly vulnerable” in case of a 7.2-magnitude or stronger quake due to evacuation difficulties, being prone to fire and collapse of buildings and their big populations these vulnerable areas were Bagong Silang and Batasan Hills in Quezon City, Addition Hills in Mandaluyong, Lupang Arenda in Taytay, Rizal province, and Baseco compound in Manila. These places are not only those near the fault lines but also have a big population composed mostly of low-income families with limited access to basic services

Rizal Technological University main campus is located at Mandaluyong City Metro Manila. Mandaluyong City is one of the identified places that will be affected in case of the earthquake in the Valley Fault System. Currently, Rizal Technological University has a population of 30, 653 enrolled students as of the admission year 2014-2015, the University has been rapid regarding competitiveness in education and athletics among colleges and universities (“Rizal Technological University,” n.d.).

On July 2017, the University conducted a dry-run for the annual earthquake drill, held at Gonzales Academic Hall (GAH), Old Building (OB), Main Academic Building (MAB), and Dr. Josefina V. Estolas Building (DJVEB) former Administration Building (Industrial Technology Building) and Industrial Technology Complex (ITC). According to Prof. Nicanor Macabalug of Citizen Army Training-Disaster Risk Reduction Management (CAT-DRRM), all colleges took part in the mandated routine. GAH finished in 7 minutes, while OB and MAB within 7 minutes and 41 seconds and DJVEB ascertained in 7 minutes and 50 seconds. Despite the fact that it took longer than he expected, Prof. Macabalug marks a positive take on the drill and mentioned the importance of bringing a whistle and a flashlight (The Guardian Publication, 2017). Furthermore, in a study by Gloria Nenita V. Velasco (Epidemiological Assessment of Fires in the Philippines, 2010–2012), National Capital Region (NCR) had the highest proportion of fire-related casualties at 61.4% by Region. Mandaluyong is eighth (8th) among seventeen (17) cities in NCR with 2.9% fire-related casualties respectively. The determined fires and fire-related casualties are caused mostly by faulty electrical wiring.

The role of University is to ensure the safeness of individuals within its premises, by assuring the availability of exit paths which are very significant part of such educational institution. An exit path should consist of corridors, hallways, stairways and aisles leading to an exit gate, the path or way outside of the exit gate that leads away from the building with associated emergency lighting and signage, (Stanford University, 2014). Upon the absence of several requirements for exit path in the establishment, it can negatively affect the individuals to determine the optimal path corresponding to the emergency cases that is necessary to evacuate. It may cause a delay in evacuation and also may lead to casualties.

The researchers are interested in learning the emergency route plan of the Rizal Technological University Building specifically Administration Building (Industrial Technology Building) and Industrial Technology Complex (ITC) currently Dr. Josefina V. Estolas Building (DJVEB) to develop an effective proposed path for the people to evacuate the building in a short period. The researchers will use Dijkstra's algorithm to identify the shortest path, the maximum capacity to calculate the carrying capacity of each building and Pathfinder simulation to determine the total travel time of the evacuees. Pathfinder is an emergency egress simulator that includes an integrated user interface and animated 3D results. (Thunderhead Engineering Consultants Inc.) Pathfinder allows the researchers to evaluate evacuation models more quickly and produce more realistic graphics.

Conceptual Framework

Rizal Technological University’s premises:

• Administration Building (ITB) currently Profeta Building and Industrial Technology Complex (ITC) currently Dr. Josefina V. Estolas Building (DJVEB).
• Observing the current evacuation plan.
• Measuring the distances of the starting nodes leading to the exit.
• Defining the maximum capacity of each building.
• Determining the total travel time of the evacuees using Pathfinder simulation.
• Propose papers for the improvement of the emergency path.

Theoretical Framework

Dijkstra’s Algorithm

The Dijkstra’s algorithm will be used to find the shortest path in the emergency evacuation plan of the ITB and ITC building in RTU campus.

Maximum Capacity

The maximum capacity will be used to calculate the carrying capacity of each building that can occupy the space such as hallways/corridors during an emergency.

Pathfinder Simulation

Pathfinder simulation will be used to determine the total travel time of the evacuees from the starting node to the exit.

Statement of the problem

The main purpose of this study is to identify which is the shortest and efficient path that will serve as a guide heading to a safe place during an emergency, the maximum carrying capacity of each building and total travel time of the evacuees. This study seeks specifically answers to the following problems and sub-problems:

1. What is the campus Layout of RTU?
2. What is the current layout plan in:
   • Administration Building (Industrial Technology Building)
   • Industrial Technology Complex (ITC)
3. What is the minimum distance of doors of the following buildings going to quadrangle using Dijkstra’s Algorithm?
   • Administration Building (ITB)
   • Industrial Technology Complex (ITC)
4. What is the carrying capacity of the following buildings?
   • Administration Building (ITB)
   • Industrial Technology Complex (ITC)
5. Using the current path, what is the total travel time of the evacuees to evacuate in Administration Building (ITB) and Industrial Technology Complex (ITC)?
6. Using the proposed path, what is the total travel time of the evacuees to evacuate in Administration Building (ITB) and Industrial Technology Complex (ITC)?
7. Is there a significant difference between the total travel time of evacuees in the current path that was computed using the Dijkstra’s algorithm and the proposed path of the researchers?

Hypothesis

Null Hypothesis

There is no significant difference between the total travel time of evacuees in the current path that was computed using the Dijkstra’s algorithm and the proposed path of the researchers.

Alternative Hypothesis

There is a significant difference between the total travel time of evacuees in the current path that was computed using the Dijkstra’s algorithm and the proposed path of the researchers.

The Significance of the Study

This study will benefit the following:

To the Students and Employees, this study can help them to familiarize in the effective evacuation path in case of emergencies and increase their awareness in organizing evacuation by identifying the optimal emergency path.

To the Management, this study will encourage them to develop an effective route and provisions that will substantially improve the performance of disaster preparedness of the University.

To the University, this study will provide an updated evacuation route plan that will help to improve the performance of university structures and systems.

Scope and Delimitations of the Study

The researchers will conduct the study at Rizal Technological University-Boni Campus. The study delimits its coverage to the premises of the school specifically in the Administration Building (Industrial Technology Building) and Industrial Technology Complex (ITC). Also, the researchers only consider earthquake and fire incidents since it is nearly possible emergency can happen in the area.

Definition of Terms

To provide clarity, the researchers define the following terms on how they are used in the study.

Algorithm – a set of steps that are followed to solve a mathematical problem or to complete a computer process.

Behavior - the way in which one acts or conducts oneself, especially toward others. In this study, behavior refers to the act of the evacuees moving from the door to quadrangle strictly following the designated direction produced from the algorithm.

Exit path - is a continuous and unobstructed way of travel from any point in a building or structure to an exit leading outside of the building or structure.

Nodes – a place where lines in a network cross or meet. In this study, nodes refer to doors, stairs, exit paths of each building and quadrangle.

Simulation - the imitative representation of the functioning of one system or process using the functioning of another.

Review of Related Literature

Shortest Path

In the study of Sabri et al., the shortest path algorithm is used as a suitable exit route to evacuate the evacuees. It is more efficient to evacuate the evacuees from danger to a safe place especially to evacuees who are unfamiliar with the building. It will also guide the evacuees in easy and smooth to find the shortest path route in the safest way and in consequences to reduce injuries of evacuees during the evacuation. These objectives have been carried out to overcome the problem of difficulties faced by the evacuees to find the best routes including the shortest and safest path. The shortest path result is believed can help the evacuee to choose a suitable exit route to evacuate. For future improvements, one of the purposes is to find the shortest path by considering the existence of obstacle during the evacuation process. This might involve the shortest and safest route during the evacuation.

The optimality of a solution is difficult to measure, one theme which is common in all literature is that evacuation plans should minimize the evacuation time. In other words, minimizing the evacuation time is to minimize the total evacuation time for all people.

Dijkstra’s Algorithm

An article produced by Sabri et al. there are three steps involved to achieve the evacuation route. The first step is Building Layout Plan, followed by creating the Visibility Graph or Network and finally utilization of Dijkstra’s Algorithm to find the shortest path. Based on the experimental study, the result shows that Dijkstra’s Algorithm has produced a significant route to evacuate the building safely. Even though there are other factors need to be considered, this preliminary result has shown a promising outcome which can be extended to improve the capability of the algorithm. In conclusion, the obtained shortest path is believed can assist evacuee to choose a suitable exit route to evacuate safely.

The researchers have chosen Dijkstra's Algorithm as it can efficiently produce the shortest path for selection of the route. This scope of research is to find the shortest distance between a node and all other nodes and suit the Dijkstra’s Algorithm target. This technique also claims to be among the best approaches in solving simple shortest path problem and always provide shortest path from any evacuation node. Assadollah Karnema et al. suggested a method based on the Dijkstra's Algorithm. Dijkstra's Algorithm is used to find a route for emergency evacuation. Searches the routes rapidly and finds the shortest path between the damaged spot and the safe place finally the most suitable route for evacuation is selected.

Maximum Capacity

In the study of Prof. Dr. G. Keith, Crowd Safety and Risk Analysis wherein he illustrates a diagram of the standing density of people per square meter to assess the efficiency of the crowd movement. Three (3) is the average number of people per square meter; this number is said to be in between of stable and unstable crowd density of people during the evacuation.

Simulation

Jiang-wen Hu used the Pathfinder simulation to determine the optimal path in a new university library in which field measurement and surveys are conducted to obtain data. In the study, the readers are young college students in which they have a quick response and good physical fitness. After running scenes that may occur, the study arrived in strengthening the training for staffs, readjusting of seats in some area, etc.. Using simulation will determine the duration of the entire process of evacuation. The result of using the Pathfinder is observed by the researchers to be useful in determining the total travel time of the evacuees.

In a study conducted by Almeida et al., pathfinder is utilized by the emergency planners as evacuation planning tool on evaluating the egress time in different scenarios even without conducting real scale evacuation fire drills. Somehow, putting drill needs certain amount of time in conducting and might not be realistic for the worst case scenarios such as not treating drills seriously.