1 Department of International Program of Advanceed Information Sciences and Information Technology， Pukyong National University， South Korea

2 Interdisciplinary Program of Information Systems， Pukyong National University， South Korea

3 Department of IT Convergence and Application Engineering， Pukyong National University， South Korea

1. Introduction

Climate change is the major problem throughout the world wide. Flooding usually caused severe damage to the roads in disaster dangerous areas and cuts off the connection channel to the outside. Road system is considered as a country’s lifeline and plays an important role (Keiichi， 2007).When a segment of a route network is closed by flooding， the flooding road impacts can be observed on the characteristics of traffic flow. A segment of a road network must be closed when is disrupted by the flooding. To decrease the damage of the traffic system in inner cities by inundation， flooding dangerous roads should be issued to people in advance (Zameer， 2013).

Besides， it is desired to provide the detour routes from departure point to destination point together. However， it is the best way for drivers to evacuate to safe area around them practically rather than to provide the evacuation route to destination in case of flooding.

Therefore， the emergency department and citizen is desperate for the disaster information， which can help people to make relief decision and actions. In addition， the evacuation route system will analyze the optimal route which needs the shortest time to the destination.

Road is one of the most primary elements in the city transportation system. Therefore， we suggest the method for evacuation route algorithm in flooding by localized heavy rain. For this work， we define dangerous roads about flooding and those kinds of roads are blocked in case of flooding on roads(Kim， 2013). In addition， to find a good algorithm to find an evacuation path we compare and analyze between dijkstra and A* algorithms.

2. Analysis of Optimal Path Search Algorithm

We compared and analyzed two algorithms which are the most famous path search algorithm: Dijkstra algorithm and A* algorithm.

2.1. Dijkstra Algorithm

Dijkstra algorithm was used to solve the problem of finding the shortest path from the starting node to the destination node. It will set some distance values and will improve the distance values step by step（Ding， 2009）.

2.2. A* Algorithm

A* algorithm is most popular algorithm for finding the path to go from start node to goal node， based on efficiency of movement cost.

A* algorithm defines as: choosing next node which should be least cost that as a heuristic function from current node. If there has more than one least cost nodes， we can choose the nearest one as next node. Usually， a good heuristic function obtains optimal solution in a little time.

F(n)=G(n)+H(n) is one type of value functions. And， F(n) is assessment of every node which will be searched possibly. G(n) is the cost from start node to current node， we often use the depth of current node as its value;

H(n) is the assessment from current node to target node. As a heuristic algorithm， H(n) has relationship with whether the method is A* algorithm or not. Once following sufficient conditions are satisfied， the heuristic algorithm will be A* algorithm that has optimal solution. If H(n) is smaller than and approximates to H*(n)， which is considered as a good design (Li， 2005).

2.3. Comparison

Figure 1， 2， are shown the comparison result between Dijkstra and A* algorithm about two cases that there are blocking areas or not.

As a result， two algorithms have same distance from a departure to destination. However， A* algorithm has better result than Dijkstra algorithm about the time taken and the number of operation. Because the Dijkstra algorithm is used to solve the shortest path， but time complexity is O(n2) therefore this generally makes Dijkstra algorithm slower than A* algorithm.

A*Dijkstra

-- length: 22

-- time: 2.0 ms

-- operations: 95-- length: 22

-- time: 18.0 ms

-- operations: 1，574

Figure 1. #1 scenario information of simulated data when no blocking area

A* Dijkstra

-- length: 27.8

-- time: 2.0 ms

-- operations: 373-- length: 27.8

-- time: 16.0 ms

-- operations: 1，796

Figure 2. #2 scenario information of simulated data with blocking areas

As a result of comparison of two algorithm， we select the A* algorithm for simulation.

3. Define of Dangerous Roads for Flooding

For this study， we collected the data related to flooding in Busan， South Korea which is the research area.

3.1. Flooding History

Figure 3. Road links with flooding history

The flooded roads are extracted from the Inundation Trace Map made by Korea Cadastral Survey Corporation and the newspaper report.

The number of extracted flooded roads from the Inundation Trace Map is 2，398 out of 69，408 of total of road links in Busan. We collected the newspaper report from 2007 to 2012 and extracted the road links by matching them with the real map. The number of road links from this work is 609. Figure 5 is shown the road links which have flooding history.

3.2. Lowland

To find road links including in lowland， we use the Tool provided from ArcGIS Desktop System. This work is completed as comparison with the elevation of road link and average elevation of lowland area.

First， we extracted the elevation point of each road link using DEM and vector type data for road links and input the result to Database. Figure 4 is shown about this work.

Figure 4. The process for extraction of elevation from road links

Second， to find the lowland where rain converges we did the work as figure 5 by using ArcGIS System Tool.

Figure 5. The process for extraction of lowland

If road link is included in the lowland area extracted from the second work as above， elevation of that road link is compared with the average elevation of the lowland area where the road link is included. If the elevation of road link is smaller than the average elevation of the lowland area， that road link is considered the lowland road link.

4. Simulations

Figure 6. The road network in the research area

Figure 7. The result of basic routing path from a departure to a destination

Figure 8. The result of evacuation routing path

A prototype of evacuation route has been built. The research area is Haeundae-gu in Busan， South Korea and Figure 6 is shown the surroundings of the research area.

Figure 7 is shown the basic routing path from a departure to a destination if the heavy rain doesn’t occur.

If heavy rain is happen and its amount is the ten years frequency probability rainfall of a flood， 79mm/hr， roads with flooding history or lowland-roads are blocking. 79mm/hr is the standard rainfall to design a road in Busan. The evacuation routing path avoiding flooded roads is shown as Figure 8.

5. Conclusion

We developed the program to provide the safe evacuation routing path to drivers from a departure to a destination in case of flooding on roads.

For this development， we tried to find which path searching algorithm is good when there is a flood on roads. Then we compared and analyzed two algorithms and the result of the comparison is A* algorithm is better than Dijkstra algorithm when there is blocking points.

To find the dangerous roads for flooding， we used two ways. The first method is whether a road has flooding history or not. We extracted the road links with flooding history from the Inundation Trace Map and the newspaper reports. The number of extracted road links after this work is 3，007 out of 69，408 of total of road links in Busan.

We implemented the program to find the evacuation path in case of flooding as avoiding the road links which have flooding history or are included in lowland areas.

In the future， we will research about a flood risk level. That is to say， we try to classify road links according to the number of flooding history and research about correlation between roads with flooding history and in lowland areas.

Foundation item: The National Project of South Korea (No.: NEMA-NH-C-D-2012-0243). Authors are grateful to the Natural Hazard Mitigation Research Group， National Emergency Management Agency of Korea for financial support to carry out this work.

Corresponding Author:

Prof. Chang Soo Kim

Department of IT Convergence and Application Engineering

Daeyeon Campus， Pukyong National University

45 Yongso-Ro， Nam-Gu， Busan， Korea

E-mail: cskim@pknu.ac.kr

References

Keiichi， T.， Urban Flooding and Measures， Journal of Disaster Research 2007; 2(3):143-152.

Zameer， A.， Ram， M. R.， Ram， M. R.， Y， E. R.， Urban Flooding-Case Study of Hyderabad， Global Institute for Research Education 2013; 2(4):63-66.

Ding， J.， ji， G. L.， Liu， F. N.， Algorithm of the Optimal Route Based on Urban Emergency Response System， Journal of Xiamen University 2009; 48(5):662-667.

Li， Q.， Song， D. L.， Zhang， S. J.， Li， Z.， Liu， J. G.， Two improved optimum path planning algorithm， Journal of University of Science and Technology Beijing 2005; 27(3):367-370.

Kim， C. S.， Kim， E. M.， Rhee， K. H.， A study on the database construction using flooding danger information of road， The International Conference on Computer Applications and Information Processing Technology 2013; 72-5.