ABSTRACT

Based on the principle of “pre-disaster prevention outweighs rescue during disasters”, this study targets areas threatened by natural disasters, and develops an automatic algorithm based on the Prim algorithm to serve as an automatic identification system. In the face of natural disasters that disable key facilities in the region and prevent settlements from contacting the outside world or outsiders from sending rescuers to the settlements, the proposed system helps to identify whether these regions will become isolated areas and conduct disaster mitigation and relief resource allocation before any natural disaster in order to reduce potential disaster losses. An automatic identification system, based on the threshold of channel blocking due to broken roads and bridges, determines through the decision tree model and relevant patterns whether such regions will become isolated areas by identifying areas based on the results of model analysis. The proposed system’s identification results are verified by actual case histories and comparisons; the results can be used to correctly identify isolated areas. Finally, Microsoft Visual Studio C # and Google Map are employed to apply the results and to produce an information mode for the determination and decision support of isolated areas affected by natural disasters.

Keywords:

Prim Algorithm, Comb Route, Isolation Area, Hazard Decision Support System

1. Introduction

Due to the impact of climate variability, natural disasters have been occurring with increasing frequency, stronger power and greater damage in recent decades. The, types and threats of natural disasters tend to be complicated and diversified. “Disaster” refers to the loss of life and property caused by the interaction between human resource management and geophysical events. If a disaster occurs in a population, then any change in social patterns and the rapid development of the peripheral environment will have greater negative impacts on human and resource management systems. Once such a disaster expands in scale, especially when vehicles are unable to access the area, rescuers face increasing rescue difficulty and humanitarian-based pressure [1] [2] [3] .

Disaster management can be explored from the perspective of risk management. The most cost-effective approach is to implement disaster mitigation and prevention programs prior to disasters, thereby reducing the subsequent negative effects and the pressure on policymakers [4] [5] [6] [7] [8] . In terms of applying the concept of disaster management into a disaster prevention and rescue system, one needs to master the precise conditions before, during, and after disasters occur, pre-disaster prevention measures, storage of supplies including relevant medicine and food, maintenance of communication equipment, and an assessment as to whether those areas will easily become isolated in the event of a disaster. Doing so can help to develop and implement an evacuation plan when the impact of the damage caused by the disaster. In the event of a disaster, each response unit should be able to accurately grasp the situation of the disaster’s impact on various places, including the interruption of roads and bridges, the lack of food and medical supplies, and the damage to local communications and telecommunications equipment that result in an inability to connect to contingency units. In addition to the repair work on roads and bridges that connect an isolated area to the outside world, more importantly, post-disaster disposal covers the decision-making on the distribution of food supplies and medicine.

A large number of studies have promoted design science in recent years. For instance, Nunamaker et al. [9] proposed a set of research frameworks combining multiple methodologies, advocating the integration of system development into the research process. Researchers can use different research methods based on the relevant topics to help understand the development of the system. Walls et al. [10] and Markus [11] discussed the feasibility of producing a prototype approach through the establishment and testing of theories for addressing such problems. March and Smith [12] pointed out that design research should contribute to the applicability of information system research by promoting its application. Hevner [13] and Iivari [14] noted that more and more people have realized that design science research shares the same position as behavioral science research in the field of information systems. Owing to the lack of research-related processes and structures, it is hard to promote and successfully apply design science research.

This study focuses on an identification system of natural disasters in an isolated area. Through relevant patterns, such a system will automatically determine whether a certain place will become an isolated area in the event of a disaster. Thus, this study aims to design a pattern to help solve this issue. As this field belongs to design science, this study adopts the DSRM (Design Science Research Methodology) proposed by Peffers et al. [15] for information systems research. The program model of the design science research will be implemented in accordance with the following six steps: 1) Identify problems and motivations, 2) define goals for the solution, 3) design and develop solutions, 4) demonstrate solutions, 5) assess solutions, and 6) conduct relevant communication regarding the results.

First, identifying problems and motivations is important for targeting specific research questions and solutions. Due to global climate change in recent years and the impact of EI Nino, the occurrence frequency of natural disasters in various places has continued to rise. These disasters also exhibit ever greater variety, complexity and negatively impact human beings’ lives and property to a greater degree. Among them, the threats to isolated areas are the most profound. Once an isolated area is struck by a disaster whereby key facilities are damaged, the community will bear the impact of the islanding effect, that is, materials and medicines cannot be delivered timely, and with a damaged healthcare system, the lives of people will be threatened. If an effective set of isolated area identification patterns can be developed based on the evaluated risks to the damaged key facilities prior to a disaster, then disaster prevention decision makers will be able to accurately grasp the possible conditions of islanding in order to prepare appropriate plans in advance and take effective contingency measures.

Second, in order to define the objectives of a solution, goals and possible feasible methods should be inferred from the anticipated solution. Based on the Prim algorithm, this study develops an isolated area identification model with the aim of identifying areas that may become isolated before disasters (such as heavy rainfalls or typhoons) in order to execute pre-disaster preparedness, strengthen roads and bridges, and reduce disaster damage and formation of an isolated area. In case of a disaster, policymakers can also identify which areas are likely to be in an early warning state or have become isolated, in order to take effective emergency actions, such as evacuating residents in advance and repairing roads and bridges in a timely manner.

In the design and development of a solution, outputs should be generated, including their functions and framework. In demonstrating a solution, it is necessary to demonstrate how to use the outputs to solve one or more problems. Finally, in assessing the solution, it is important to observe and measure the extent to which the outputs support problem-solving.

2. Causes of Formation of Isolated Areas during Disasters

“Island” is defined as a small piece of land surrounded by water, and it is not necessarily inhabited; an isolated area means that it is isolated from the outside world and cannot readily get help if needed. Humans inhabit every corner of the earth. When settlements or communities are located in remote areas that lack convenient traffic, access, they are defined as “remote and isolated settlements.” Under normal conditions, these settlements rely on well-established external transport systems (such as railways, highways, waterways, and air travel), life sustaining systems (such as hydropower and fuel subsistence systems), emergency rescue hospitals, information and communications facilities, and hi-tech parks to provide safe and viable living functions and information connectivity for the inhabitants [16] [17] [18] [19] [20] . Once the key infrastructures in the habitat areas suffer significant damage due to a disaster event and are out of order, malfunction, are interrupted, or fail to provide services within 72 hours or longer, such areas become completely isolated from foreign aid and cannot be easily accessed. A more generalized meaning of “disaster isolated areas” is “a disaster area where some of the key infrastructure facilities have failed and some of the functions cannot operate” [21] .

By definition, a disaster-isolated area does not necessarily occur in a remote or isolated area. Two factors make the area a disaster-isolated area: one is the disaster, and the other is that the key facilities being out of order, malfunctioning, being interrupted, or failing to provide services. Disasters include natural or man-made disasters. Figure 1 shows the types and patterns of each disaster; they are the main causes of disaster-isolated areas and reach a certain strength in terms of scale so that the key facilities malfunction. Once the key facilities are destroyed, the communities in the area will suffer short-term or long-term “islanding”, such as isolation of traffic and communications, disruption of supplies, deteriorating medical conditions, and damage to the health system, which will inevitably threaten the lives of people [22] [23] [24] [25] [26] .

The formation of isolated areas during a disaster is mainly affected by the disaster. However, the disaster-resistant capability of key facilities is often of great importance. Investigations of various disasters have pointed out that the damage of roads and bridges is closely related to whether or not these areas become isolated areas; the factors that cause the interception of roads and bridges include earthquakes, landslides, and earth flows. Bridges and temporary corridors may be destroyed as a result of soaring water streams during a rainy season or as a result of a typhoon [27] [28] . In studying disasters, Chen and Yeh [29] noted that for villages with only one outbound road, the possibility of an isolated area forming is much higher than for areas with more than one outbound road.

Chen took the Wufeng Village at Hsinchu as an example. As this area only has one road or bridge, once it breaks, daily life supplies cannot be sent in, resulting in an isolated area [30] [31] . Pan [32] and Hung and Lin [33] conducted surveys on mountain townships, and found that owing to terrain constraints, these areas often become the focus of disaster prevention work. Disasters often cause damage to roads, telecommunications, and electricity; these prevent local residents from reaching the outside world. When the relevant authorities are unable to ascertain the conditions of local residents, it is difficult to conduct disaster prevention and rescue, causing “islanding”. The isolated area phenomenon has an impact on the social economy and industry. As the highway system is an important channel for transportation and people’s livelihood, any damage to it caused by disasters is likely to result in a major blockage preventing immediate contact, emergency relief, and material transportation.

The above studies have shown that roads and bridges in key facilities are the major factors that affect the formation of isolated areas. In particular, traffic systems in mountainous areas and remote areas are often limited by a single access road. These roads usually cross rivers and valleys, while the number of bridges is higher than those in flat areas, hence increasing the possibility of disasters. Once these roads and bridges are interrupted, an isolated area will result.

The distribution of roads in Taitung County, which is explored in this study, is shown in Figure 2. One major road connects the north and south of the whole area. The secondary roads extending from the main road serve as the major outbound roads of settlements, but the secondary roads do not connect with other roads due to terrain factors. The primary and secondary roads form a honeycomb-shaped channel, and the secondary roads become the only access to the settlements. Once these roads and bridges are affected, the settlements will become isolated areas.

3. Prim’s Algorithm

Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph [34] . Prim’s algorithm was developed in 1930 by Czech mathematician Vojtěch Jarník. At present, the technology and concept of Prim’s Algorithm have been widely used in various fields of research such as

network analysis, multiple objective decision making, optimization planning, etc. [35] - [40] .

The algorithm operates by building this tree one vertex at a time from an arbitrary starting node, in its connected but not yet selected node, by selecting a least weighted edge, and then adding a new node. This repeatedly joins the new node with the lowest weight until all the nodes have been selected. As a result, the minimum spanning tree is established. The village is connected by roads in a tree network. The set recorded by Prim’s Algorithm is an optimal connected subtree. The minimum spanning tree is solved to identify the isolate area. In practice implementation method is to establish a matrix with threshold value. The screening criteria are such that when the road preset risk value is greater than or equal to the road interruption threshold, the representation in the matrix will be “0”, which indicating nodes dislink. That means, isolated area is occured (Figure 3 & Table 1).

The process of calculating from a weight matrix is as follows:

1) Starting from node 0, we find the link with the smallest weight in the set of separated nodes 0 and other nodes. After the search result is (0, 1), the chain (0, 1) is added to the spanning tree.

2) Find the joint with the smallest weight in the set of separated node sets {0, 1} and other nodes. After the search result is (1, 2), join the chain (1, 2) to the spanning tree.

3) Find the joint with the smallest weight in the set of separated nodes {0, 1, 2} and other nodes. After the search result is (1, 4), the chain (1, 4) is added to the spanning tree.

4) Find the set of nodes with the minimum set of nodes {0, 1, 2, 4} and other nodes with the minimum number of links. After the search result is (4, 3), the chain (4, 3) is added to the spanning tree.

5) Find the joint with the minimum weight in the set of separated nodes {0, 1, 2, 3, 4} After the search result is (4, 5), the chain (4, 5) is added to the spanning tree.

(6) Since all the nodes have joined the spanning tree, the calculation is stopped and the minimum spanning tree is {(0, 1), (1, 2), (1, 4), (4, 3), (4, 5)}.

4. Design and Develop Solutions

4.1. Solutions

This study maps the risk values of communities, roads, and key facilities to the nodes, edges, and weights of graph theory and uses the Prim algorithm in graph theory to find the entire minimum spanning tree (MST) with values below the default risk threshold in the weighted connectivity graph. Each MST forms a separate area. If the area cannot communicate with the primary spanning tree within a valid time, then it is determined to be an isolated area. In other words, the tree formed by the subset of edges found by this algorithm not only includes all the vertices in the connected graph, but also the sum of the weights of all the edges.

In this step of designing and developing the solution, an output file should be created. The output may be a structure, pattern, method, or instance. To develop solutions, this study is based on the Prim algorithm and combines the concept of risk management to build an isolated area identification model. Figure 4 shows the identification pattern of this study. The social system and natural system comprise the basic data. The social system covers roads and bridges. The natural system covers the disaster potential and the rivers, and serves as the basis for Prim’s algorithm. The calculation process is shown in Figure 5. First, one node among all the nodes in all the combined roads is selected as a starting point.

1) Before the selection, the lowest risk value of road and bridge in the spanning tree enters the first judgment condition.

2) The first judgment condition: Whether all the outward connections and traffic generated by the spanning tree are interrupted.

a) If all the connections and traffics are interrupted, then the spanning tree

will be put into the set of used edges and the set of vertices to derive the current minimum spanning tree. The minimum spanning tree will then be entered into the fourth judgment condition to determine whether there are any unfound remaining nodes. If all the nodes have been found, then the minimum spanning tree is put into the subprogram to judge the isolated area. If not all of the nodes are found, then one node among all nodes that are not included in the spanning tree will be selected again as a starting point.

b) If there is no interruption to the external traffic in the first judgment condition, then the risk values of the roads and bridges selected from the current spanning tree and all the outbound roads and bridges are used as reference to enter the second judgment condition.

3) The second judgment condition: Whether the risk value of the roads and bridges of the spanning tree is less than the pre-set value

a) If the risk value is greater than, or equal to, the pre-set value, then put the current spanning tree into the isolated area set to be determined. The spanning tree will then be put into the set of edge sets and vertices to obtain the current minimum spanning tree; it enters the fourth judgment condition to determine whether there are any remaining nodes that have not yet been found. If all the nodes have been found, then the minimum spanning tree is put into the subprogram to judge the isolated area. If not all of the nodes have been found, then one node among all nodes that are not included in the spanning tree will be selected again as a starting point.

b) If the risk value is less than the default value and if there is at least one minimum risk value, then select the road and the bridge with the shortest distance. The selected road and bridge are then put into the set of edge, and the selected vertex is put into the vertex set; these are later entered into the third judgment condition.

4) The third judgment condition: Whether there is any external traffic in the spanning tree at present

a) If the current spanning tree has other external traffic that can be connected, return to step 3.2 and select the risk values of roads and bridges and all outbound roads and bridges from the current spanning tree as a reference to enter the second judgment condition.

b) If the current spanning tree has no other external traffic that can be connected, use the set of edges and vertices to derive the current minimum spanning tree and enter the fourth judgment condition.

5) The fourth judgment condition: Whether there is any remaining node that has not been searched

a) If there is any remaining node that has not been searched, return to the next one and select one node that is not included in the spanning tree node as a starting point to re-search.

b) If all the nodes have been searched, put the current minimum spanning tree into the islanding subprogram, and then put the edges and vertices selected by the current minimum spanning tree into the set.

After the above steps have been completed, the output of the result will be presented to the relevant decision makers or users through a graphic interface. The graphic interface provides a better understanding of the current overall situation than the text interface does.

4.2. System Implementation

The development tools used in this study are Microsoft Visual Studio C # and Google Maps. The reason for choosing Microsoft Visual Studio C # is that there is a Help Documentation in the C # platform for Microsoft development that is not available in other open programs written in C #; for example, the development environment of Sharp Develop provides help documentation. In addition, when using Microsoft Visual Studio C #, one may use the functions of Web Forms Designer in conjunction with the Google Maps display map. The main function of C # is that when the user gives a risk value, the program will automatically determine which road is feasible and which road is not feasible. Finally, a text interface of villages and towns becoming isolated areas will be presented. If the user wishes to present the result with a map, then Google Maps can help judge which towns and villages in C # will become isolated areas. In addition to the use of red flags for marking, latitude, longitude, and other related information are presented to the user for reference. Figure 6 shows the system activity diagram from the system user’s perspective, in order to perform the development.

First, the user must enter the risk value obtained after an assessment of the interruption risk of relevant roads into the box of the road interruption threshold value. The value range should be between 0.1 and 0.9. Second, the user only needs to press the start button after the input is completed. The system

starts with the Prim algorithm to search for the isolated areas and the accessible villages and towns, and presents all the related and complete information in the Textbox box, including connections of villages and towns that are not isolated areas, villages and towns that are isolated areas, and villages and towns that are accessible (Figure 7(a)). Third, after viewing the information generated by the complete text interface, the user can decide whether to click the map mode to view the villages and towns in the isolated areas marked by red flags. If the user does not view the map mode, the user may choose to turn off the window and stop the program. To view the related information and data in the map mode, the user clicks the map mode to view the detailed information on the villages and towns in the related area. The details of the records and presentations include latitude and longitude, the area of land (km²), the number of villages, the

number of neighborhoods, the number of households, the population, and the population density of the isolated area in the villages and towns (Figure 7(b)).

5. Conclusion

Although disaster prevention technology continues to enjoy innovation and improvement in order to reduce the scope of disasters, it is still difficult to achieve comprehensive warning and effective control of disasters due to the complexity and uncertainty of disasters. This study is based on the Prim algorithm; it is employed to find and identify areas that may form isolated areas before natural disasters occur. Text interface based on the Prim algorithm is used to identify isolated areas and the access to non-isolated areas in a successful and correct manner. The areas that are identified as isolated areas can be displayed in a visual map mode, together with the social and economic information related to disaster relief, such as population data and land area. In terms of disaster prevention, the research results can be used for disaster mitigation and risk analysis, disaster resource planning and disposition, and disaster prevention and mitigation projects based on the concept of risk management, in seeking to avoid casualties and economic losses caused by islanding.

Acknowledgements

The authors are thankful for the assistants Y.C. Wang, and J.J Zeng for their help on this study. This study is supported by the Ministry of Science and Technology of Taiwan under Grants MOST 107-2119-M-143-002.

Cite this paper

Wang, W.-C., Hsieh, M.-C. and Huang, C.-H. (2018) Applying Prim’s Algorithm to Identify Isolated Areas for Natural Disaster Prevention and Protection. Engineering, 10, 417-431. https://doi.org/10.4236/eng.2018.107029

References