Authors
Abstract
Introduction
Many researchers have worked on the issue of crisis management due to natural disasters such as earthquakes and hurricanes (Lindell & Prater 2002; Ardekani 1992). Accordance with the views Chiu & Zheng (2007), making decisions regarding emergency evacuation due to unexpected events, should include the following aspects:
• Destinations, the victims should be moved there, which can be temporary accommodation in tents, medical services or secure areas, and
• Consuming time to get the destinations by the victims that should be the shortest.
Temporary accommodation of earthquake victims includes the following steps: (Naghdi
et al., 2006; Saadatseresht et al., 2007)
• Phase 1: Searching for some safe areas based on some constraints, such as a minimum risk, adequate capacity, proper distribution, access to adequate drinking water etc.
• Phase 2: Determining the optimal path between each building block, located in the disaster area, and the safe areas based on several factors.
• Phase 3: Selecting the optimum safe area for each building block in an optimization process based on two criteria: traffic capacity and the minimum cost (the shortest) to get the safe area.
This paper presents a suitable algorithm for performing the 2nd phase of the process discussed above. This paper is developed a shortest path algorithm based on geographical information system (GIS) for quick discharge and transfer injury disaster victims to predetermined safe areas.
Methodology
Dijkstra's algorithm, introduced by Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs. For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex. This is asymptotically the fastest known single-source shortest-path algorithm for random directed graphs with unbounded nonnegative weights.
The general idea of the proposed algorithm for optimum route determination for emergency evacuation issue is based on the Dijkstra. Dijkstra is improved with defining some particular conditions regarding earthquake disaster management. Proposed algorithm can find shortest path (optimum path) among all building block (as place of victims) and all safe areas (as evacuation destinations). Since short path finding process for emergency evacuation should be repeated numerously along the network (equal to the product of the number of building blocks in the number of safe areas), most important features of the proposed algorithm is its high speed.
Results and Discussion
Capabilities and speed of the algorithm has been tested at both virtual and real urban network located in district 7 of Tehran. To evaluate the efficiency of the proposed method of this paper, the algorithm was examined in a real urban network. Test area within the northwest part of the seven regions of Tehran. Some data include building blocks, urban streets and green spaces (as safe areas for emergency evacuation), urban population was used. Selection of the safe areas has been done based on suggestions raised in Earthquake Studies in Tehran by JICA. After creating topology, a real network with 432 building-blocks’ nodes, 11 safe areas’ nodes and 1189 edges was established. The results show that determining optimal path in the real network of, only required about 90 seconds.
To be ensuring about the accuracy of the algorithm some tests have been done on both virtual and actual network. First, with a displacement of points of origin and destination, go and return path between two vertices of the network was searched independently by the algorithm and observed that the paths completely match. After repeating this test, accuracy of the algorithm was verified. In the second test, the overall performance to find global and local optimum path between two vertices was examined. In the third test, simultaneous performance of the proposed algorithm for searching optimal paths between a source (building blocks) and multiple destinations (safe areas) was investigated. All the tests were verified performance of the proposed algorithm.
Conclusion
In this paper after reviewing several methods, that have been used for finding the optimum path in a discrete network, a method based on modification of Dijkstra algorithm was presented. For increasing the speed of the proposed method, some constraints were added to Dijkstra. According the test has been done in both simulated and real network; we found the proposed method advantageous for optimum route determination problem. Multi-destination search capability to find shortest path to all safe areas from each building blocks by only one run of the algorithm, is other characteristics.
Decision making regarding the emergency evacuation when we consider that all affected people should be in a transport network with limited capacity is very difficult. Therefore, regardless of other issues involved in emergency evacuation problem, preparing a time schedule for evacuating people living in each block to avoid simultaneous presence of all injured at the site and creating traffic according to the limited capacity of urban streets, are the issues that require further study. Furthermore, the proposed algorithm can be used for other applications such as determining the optimum route for navigation activities.
Keywords
)