Research for establishing a model of optimizing civilian withdrawal plan for the border area

A B S T R A C T KEYWORDS Purpose: This research proposes an optimization model for effective evacuation routing

and scheduling of civilians near the border area when full-scale war threats heighten.

Method: To reflect the reality, administrative unit network is created using Kruscal's Algorithm, Harmony Search, CCRP based on the geographical features, population, and traffic data of real cities, and then, optimal civilian evacuation routes are found.

Results: Optimal evacuation routes and schedules are computed by repetitive experiments, and it is found that the scenario that minimizes the average civilian evacuation time is effective for the civilian evacuation plan.

Conclusion: By using the civilian evacuation plan this research proposes, at the time of establishing the actual civilian evacuation plan, quantitative analysis is used for the effective plan making rather than only depending

War,

Civilian Withdraw Plan, Heuristic Method, Harmony Search, CCRP

연구목적 : 본 연구는 전면전 위기 고조 시 효율적인 접경지역 주민 철수경로 및 일정수립에 최적화된 모형 제안을 목적으로 한다 .

연구방법 : 현실 반영을 위해 실제 도시의 지형, 인구, 도로 데이터를 기반으로 Kruscal’s Algorithm, Harmony Search, CCRP를 활용하여 행정구역(읍·면·동) 단위 네트워크를 생성 한 후 , 최적의 주민철수로를 찾는 순서로 실험을 진행한다.

연구결과 : 반복실험을 통해 최적의 주민철수 경로 및 스케줄을 산출하였고, 주민 철수시간 평균을 최소화하는 시나리오가 주민철수 계획수립에 효율적이라는 것을 확인하였다 . 결론 : 본 연구에서 제안하는 주민철수 모형을 활용하면, 주민철수 계획 수립 시 기존의 정 성적인 분석에 정량적 분석을 보완하여 보다 효율적인 계획 수립이 가능할 것으로 사료된다 .

전면전 , 주민철수 계획 , 휴리스틱 기법 , 화음 탐색법 ,

용량 제한 라우팅계획

ⓒ 2018 Korea Society of Disaster Information All rights reserved

접경지역 최적 주민철수 계획수립을 위한 모형 연구

Research for establishing a model of optimizing civilian withdrawal plan for the border area

정재환

^a,1

^a,2

^a,3

^a,*

Jae Hwan Jung

^a,1

^a,2

^a,3

^a,*

a

Department of Industrial Engineering, University of Yonsei, Yensei-ro 50, 03722, Republic of Korea

* Corresponding author. Tel. +82-2-2123-4012. Fax. +82-2-364-7807 Email. [email protected]

1 Tel. +82-2-2123-8507 Email. [email protected] 2 Tel. +82-2-2123-8507 Email. [email protected] 3 Tel. +82-2-2123-8507 Email. [email protected]

ARTICLE HISTORY Received

Revised Accepted

Jun.

Jun.

Jun.

9, 11, 29,

2018

2018

2018

1976-2208 ⓒ 2018 Society of Disaster Information All rights reserved.

1. 서 론

전 세계적으로 기후변화에 따른 자연재해와 9·11테러 이후 지속해서 발생하고 있는 테러 등의 영향으로 재난 발생 시 대피 문제에 대한 연구가 활발히 진행되고 있다. 국내에서는 2011년 일본 도호쿠 대지진에 의해 발생한 원자력 발전소 방사 능 유출사고 이후, 재난 대피와 관련된 연구가 활성화되었고(안철현 등, 2011)[1], 2017년 포항 지진 발생 이후 그 중요성 이 더욱 강조되고 있다.

기존의 주민 생존성 보장을 위한 재난 대피 연구는 주로 태풍, 해일, 지진 등의 자연재해 및 원자력 발전소 사고, 화학 공장 사고 등 인적재난에 대한 연구에 집중되고 있어, 군사적 상황 발생에 따른 주민생존성 보장에 대한 연구는 부족했다.

한국전쟁 휴전 이후, 북한은 지속해서 군사적 공세주의의 본질적 성향을 유지하며 도발하고 있는 것을(Kim, 2017)[2] 고려 한다면 이에 대한 준비는 필수적이다. 군사적 상황은 크게 국지도발과 전면전으로 구분할 수 있는데, 전자의 경우 2010년 연평도 포격도발 이후, 주민 생존성 보장을 위한 대피소의 위치, 크기 및 용도 등과 관련된 연구가 활발히 진행되었다. 그러나 발생 가능성은 낮으나, 발생한다면 많은 인명피해가 예상되는 전면전 시 주민생존성 보장에 대한 연구는 전무한 상황이다.

특히 비무장지대 및 해상의 북방한계선과 맞닿아 있는 접경지역(접경지역 지원 특별법, 2018 개정)[3]은 전면전 발발 시 교전이 집중되는 지역으로 많은 인명피해가 발생할 수 있다. 또한 전쟁공포에 빠진 주민들의 무분별한 이탈에 의해 발생할 수 있는 도로기능 마비는 군의 전투준비에 부정적인 영향을 미칠 수 있어, 전면전 시 주민 생존성 보장과 군 작전여건 보장을 위해 주민철수 계획에 대한 연구가 필요하다.

주민철수 계획은 지방자치단체(이하 지자체) 주도로 접경지역 주민을 안전한 지역으로 이동시키는 계획으로 지자체별로 계획을 수립하고, 자체 및 군관 연계된 연습을 실시하고 있다. 하지만 계획수립 시 일반적인 재난 대피계획은 상황에 따라 기존의 연구 및 분석모형을 이용, 정량적 분석이 가능한 반면, 주민철수 계획의 특징에 부합되는 연구나 분석모형이 없어 계획수립관에 의한 도로, 인구 및 군 작전계획 등을 고려한 정성적인 분석에 그치고 있어, 효율적 주민철수 계획 수립에 한계 가 있다.

지금까지 주로 연구된 일반적인 재난 상황에서의 대피와 전면전시 주민철수는 지역 내 인원을 가능한 한 빠르게 대피시켜 야 한다는 공통점을 가지고 있다. 하지만 일반적인 재난상황에 대한 대부분의 연구는 가능한 모든 기동로를 사용하여 최단 시간(비용, 거리) 내에 주민을 대피시키는 것에 집중한다. 반면, 전면전 시 주민철수 문제가 갖는 특징인 ① 지역 내 군 작전 로 확보 ② 후방지역과 주민철수로 사용 협조, ③ 전쟁 수행 필수 인원(군인, 동원자원, 지정 공무원 등)의 지역이탈 방지,

④ 주민혼란 통제 때문에 모든 도로가 아닌 지정된 주민철수로를 따라 통제된 가운데 주민철수를 시행하는 차이점이 있어 기존 일반적인 재난 대피 연구를 주민철수 연구에 적용하기 제한된다.

본 연구는 연구 대상에 대한 현실적인 필요성 및 기존 연구의 한계점을 효율적인 주민철수 경로 및 일정을 수립할 수 있는 최적의 주민철수 모형을 제안하는 것을 목적으로 수행하였다. 연구진행으로 2장에서는 기존의 관련연구를 고찰하였고, 3장 에서는 연구모형에 대해 주민철수 계획 수립과 주민철수 네트워크 구성으로 구분하여 정의 및 가정사항을 정리하였다. 4장에 서는 실험 데이터 및 알고리즘을, 5장 및 6장에서는 실험결과를 분석하고 결론을 도출하였다.

2. 기존연구 고찰

재난 대피분야는 접근방법에 따라 거시적(Macro) 모형과 미시적(Micro)모형으로 구분된다. 본 연구는 거시적 모형 중 하나인 동적 네트워크 흐름 모형(Dynamic Network Flow Model)을 기반으로 하고 있어, 이 모형에 대한 기존 연구를 중심 으로 분석하였다.

Robinson et al.(2011, 2012)[4][5]은 재난 발생 시 단기간 내 특정 Node 또는 Arc에 수용가능 범위를 초과하는 이동량

이 집중될 때, 정체 감소를 위해 대피 경로 및 시간에 대한 정확한 계획 수립을 도출하는 ATIS(Advanced Traveler

Information Systems)에 대한 연구를 수행하였다. 대량 대피문제 해결을 위한 연구 중 이산시간 동적 네트워크 흐름 모형

(Discrete Time Dynamic Network Flow Model) 기반의 주요 연구로 Qingsong et al.(2004)[6]은 재난, 재해 및 테러

상황에서 인원을 대피시키기 위한 경로 및 일정을 수립하기 위해, 용량을 시계열로 모델링하고 용량 제한 휴리스틱 접근

방법을 사용한 MRCCP (Multiple-Route Capacity Constrained Planner)를 제안했다. 실험을 통해 기존 선형접근법(LP : Linear Programming) 대비 근사 최적 솔루션 산출 및 계산량 감소 등의 효과를 확인하였다. Lim, et al(2012)[7]은 짧은 사전 재난경고 상황에서의 대피계획(SNEP : Short Notice Evacuation Planning)에서 대피인원을 최대화하기 위한 최적 대피 경로, 이동량 및 일정을 찾아내는 용량 제한 네트워크 흐름 모형(Capacity Constrained Network Flow Optimization Model) 을 제시하였다. 네트워크에 대한 해석시간 감소를 위해 대피일정 수립 모형(ESA : Evacuation Scheduling Algorithm)을 적용 했다. ESA는 시간 진행에 따라 달라지는 네트워크 내 이동량을 고려한 최적의 경로, 경로 Capacity의 최대 한계 및 대피 일정을 수립하기 위해 Dijkstra 및 Greedy 알고리즘을 사용하였다. 재난에 따른 인원의 대피계획과 이에 대응하려는 소방관 등의 진입계획은 모두 지역 내 도로를 기반으로 이루어지고, 통상 반대 방향으로 이동하기 때문에 서로의 계획에 큰 영향을 미친다.

기존 연구들은 재난 상황에서의 대피계획에만 집중한 것에 비해 Shin.(2017)[8]은 대피계획에 영향을 미치는 진입계획을 통합 적으로 고려한 동적 네트워크 흐름 모형 기반의 모형을 제시하였다. 그리고 해석의 어려움 및 긴 계산시간을 극복하기 위해 CCRP(Capacity Constrained Routing Planner)를 적용한 휴리스틱 알고리즘을 개발하였다.

본 연구는 동적 네트워크 흐름 모형에 대한 기존 연구를 바탕으로 주민철수 계획이 갖는 4가지 특징적 고려사항인 ① 지역 내 군 작전로 확보, ② 후방지역과 주민철수로 사용 협조, ③ 전쟁 수행 필수 인원(군인, 동원자원, 지정 공무원 등)들의 지역이탈 방지, ④ 주민혼란 통제를 반영하여 접경지역 주민철수 계획에 특화된 모형을 제시하고자 한다.

3. 문제정의

3.1. 주민철수 계획 수립

본 연구는 북한의 전면전 위기 고조 시 휴전선 접경지역 주민들의 최적 주민철수 모형 수립을 목적으로 한다. 주민철수는 다음과 같은 방법으로 진행된다. 첫째, 주민들은 거주지 인근의 대규모 인원이 집결 할 수 있는 학교, 공원 등 지정된 최초 집결지로 이동한다. 둘째, 행정동 단위로 이동을 통제하여 최초집결지(Node) 또는 거주지에서 지정된 도로를 따라 주민철수 로에 진입한다. 셋째, 주민철수로를 따라 후방의 목적지(중간 및 최종 집결지)로 이동한다.

주민철수 명령 발령 시 모든 주민은 세대 단위로 자가차량을 이용하여 주민철수로를 통해 목적지로 이동한다. 이때 철수하 는 주민이 같은 시간에 주민철수로에 집중된다면 차량 수용능력을 초과하여 많은 정체가 발생할 수 있고, 심각하게는 도로마 비가 발생하여 주민철수 소요시간이 증가하고 군의 전투준비 여건 보장이 제한될 수 있다. 따라서 주민철수로의 효율적 사용 및 철수시간 단축을 위해서는 주민들의 철수시작 시점 통제와 통행량을 고려한 적절한 차량분배가 필요하다. 본 연구에서는 이를 반영하기 위해 시간 변화에 따른 네트워크 용량 변화를 반영할 수 있는 이산시간 동적 네트워크 흐름 모형을 적용한다.

3.2. 주민철수 네트워크 구성

본 연구는 이산시간 동적 네트워크 흐름 모형을 기반으로 연구하였다. 이산시간 동적 네트워크 흐름 모형의 네트워크는 철수계획을 구현하기 위해 기본적으로 [G = ( N, A ), N = Set of Nodes, A = Set of Arcs]를 Fig. 1.과 같은 방법으로 적용했다. 이때 Node는 주민자들의 최초집결지를, Arc는 이동경로를 의미한다. 시간의 진행에 따른 Node와 Arc의 용량 변화를 반영하기 위해 Fig. 2.와 같은 방법으로 [GT = (NT, AT)], 시간 T로 확장하는 G를 정의하였다. 그래프 GT 에서는 시간(T)의 변화에 따라 이동하는 주민들의 수의 변경에 따라 조정되는 Node와 Arc의 용량이 적용된다.

본 연구에서 다루고자 하는 문제 중 네트워크의 구성은 중요한 이슈 중 하나이다. 이 모형은 그래프 [GT = (NT, AT)]가

사전에 구성됨을 전제로 하는데, 주민철수로를 지정하고 이를 중심으로 네트워크가 구성된 기존 연구가 없어, 주민철수로

중심의 주민철수 네트워크를 휴리스틱 기법을 적용하여 구성하였다. 도시 내에 주민들은 행정동 단위로 각지로 흩어져 있고,

수많은 도로가 얽혀있는 상황에서, 지역별 거주 인구 및 도로의 용량을 고려한 주민철수로 선정은 주민철수 계획의 효율성에

큰 영향을 미칠 수 있다. 실제 지자체에서도 주민철수계획의 특징 반영과 지역 내 군부대와 협조를 통해 주민철수로를 선정하

고 있지만, 계획수립관에 의한 정성적인 판단에 그치고 있다. 본 연구에서는 주민철수로를 실험에 의해 정량적으로 선정하고,

더불어 Node(최초집결지)에서 주민철수로에 이르는 효율적 접근로까지 선정하고자 한다.

Fig. 1. G = Evacuation Network[9] Fig. 2. GT = Time-expanded Evacuation Network[9]

3.3. 세부연구 및 가정사항

본 연구에서 다루는 문제는 ① 주민철수 네트워크 구성, ② 주민철수 계획 수립(이산시간 동적 네트워크 흐름 모형)으로 구성된다.

먼저 주민철수 네트워크 구성 세부절차는 ① Node 간 거리를 기준으로 행정동 내 네트워크를 스패닝 트리 구조로 생성하 여 행정동 내 Node 간 효율적인 이동로를 선정한다. ② 행정동 내 Node 중 주민철수로와 연결되는 Node를 선정한다. ③ 각 행정동에서 선정된 주민철수로와 연결되는 Node를 스패닝 트리 구조로 연결하여 행정동과 연결된 주민철수로를 선정한 다.

이전 과정을 통해 주민철수 네트워크를 구성한 후, CCRP를 적용하여 마지막 주민의 철수 완료시간과 전체 주민의 평균 철수 완료시간의 최소화를 목표로, 해당 네트워크에 대한 최적 주민철수 계획을 수립한다. 세부 절차는 ① 각 최초 집결지 (Node)에서 목적지까지의 최단 경로를 계산하기 위해 A* 알고리즘(A* Search Algorithm) 사용한다. ② Node별 주민들의 철수 시점 및 세대 수를 시간에 따른 도로의 용량 변화를 고려, 효율적으로 분배하여 주민철수 계획을 산출한다. ③ 화음 탐색법(Harmony Search Algorithm)을 적용하여 행정동 간 네트워크(주민철수로)와 관련된 Node를 변경 후 ①~② 과정 을 반복 실험하여 근사 최적해를 도출, 최적의 주민철수 네트워크 및 주민철수 계획을 산출한다.

모형 수립 시 현실적인 요소 반영 및 연구목적 달성을 위해 다음과 같이 가정 사항을 설정하였다. ① 모든 주민은 세대

단위 자가 차량으로 철수하고(모형 내 주민 1은 1세대를 의미), 자가차량 미보유자 및 이동불가자는 고려하지 않는다. ②

모든 주민은 Node에서 Node로 이동 시 이동방향을 변경하지 않는다. ③ 도로(Arc)의 용량이 한계점에 도달하면 주민은

용량이 허용될 때까지 대기한다. ④ 전면전 발발 이전 주민철수를 방해하는 요소(북한 특수부대 및 화력에 의한 공격 등)는

없다. ⑤ 교차로에서 발생 할 수 있는 차량 정체는 고려하지 않는다. ⑥ 모든 주민은 통제소 및 통제요원의 지시에 따라 이동

한다. ⑦ 주민철수에 필요한 가용시간은 충분하다. ⑧ 군부대 투입 및 작전운용 여건 조성을 위해 주민철수 시 각 도로의

한 방향의 차선들만 사용한다.

4. 실험설계

4.1. Data Set

주민철수 계획수립 모형 검증을 위해 국내 특정 도시 데이터를 기반으로 총 91개의 Node(최초집결지 : 90개, 목적지 : 1개)에 대한 위치, 인구, 도로 등에 대한 데이터를 수집하였다. Node의 위치는 각 행정동 단위에서 Node로 사용할 수 있는 학교로 선정하여 위도, 경도 데이터를 반영하였고, 인구 및 세대 데이터는 지역별 인구통계를 참고하였다. Node와 Node간의 거리는 직선거리가 아닌 T-Map API를 활용하여 차량 이동거리를 산출/활용하였다. 도로는 단방향만 고려하는 것을 가정하여, 1 ~ 4차선의 폭을 가지고, 도로의 용량은 실제 주민철수 시 통제소에서 이루어지는 확인절차 및 교차로에서 의 차량정체 등을 고려 1시간, 1km 당 1개 차선에 300대로 가정하였다. CCRP에서 적용한 T의 기준은 1km를 이동할 수 있는 시간으로 가정하였고, 1km 범위 내에 있는 Node 간의 T는 1로 가정하였다.

접경지역 주민철수는 해당 지역 지방자치단체가 주관하여 행정단위(동, 읍, 리 등) 별로 주민 통제가 이루어지기 때문에 각 Node는 동 단위로 클러스터링 하였고, Fig. 3.은 Node의 위도, 경도 기반의 위치 정보와 행정단위 별로 클러스터링한 모습을 나타낸다. 가장 하단의 중앙 쪽에 위치한 Node는 최종 목적지를 뜻한다.

≫

Fig. 3. Node information of experimental data and clustering information based on administrative unit 4.2. 행정동 내 네트워크 구성

≫

Fig. 4. Network configuration of nodes in the administrative unit

≫

행정동 내 네트워크를 구성하기 위해 Kruskal’s 알고리즘을 사용하였다. 이 알고리즘은 1956년 Joseph Kruskal에 의해 제안된 것으로 무향 연결 그래프에서 각 Node를 가능한 가장 작은 가중치로 연결하기 위한 Arc를 찾는 최소 스패닝 트리 알고리즘(MST : Minimum Spanning Tree Algorithm)이다. 스패닝 트리는 해당 그래프의 모든 정점을 포함하는 트리형태 의 서브그래프를 뜻하고, 한 그래프 내에 여러 개가 존재할 수 있는데, Kruskal’s 알고리즘은 여러 개의 스패닝 트리 중 Arc의 가중치의 합이 가장 작은 최소 스패닝 트리를 찾는 알고리즘이다.(Kruskal, 1956)[10]

주민철수 시 주민들은 거주지별 지방자치단체의 통제에 따라 이동하기 때문에 우선 행정동을 기준으로 이동을 위한 네트워 크를 구성하였다. 행정동 내 각 Node(최초 집결지) 간 거리를 기준으로 Kruskal’s 알고리즘을 사용, 최소 스패닝 트리를 만들어 각 Node간 가장 가까운 거리로 연결된 네트워크를 생성하였다. Fig. 4.은 Kruskal’s 알고리즘을 적용하여 행정동 내에 있는 Node들의 네트워크를 구성한 예시이다.

4.3. 주민철수로 네트워크 구성 및 주민 철수계획 수립

행정동과 행정동 간의 네트워크 구성을 위해서 행정동 내 네트워크 구성 시와 동일하게 Kruskal’s 알고리즘을 사용하였 다. Node에서 목적지에 이르는 도로 중 주민철수로를 선정하기 위하여 각 행정동에서 임의로 한 개의 Node를 선정하고, Node를 대상으로 Kruskal’s 알고리즘을 적용하여 최소 스패닝 트리를 생성, 주민철수로 네트워크를 구성하였다. Fig. 5.는 행정동과 행정동을 연결하는 네트워크를 구성한 예시이다.

Fig. 5. Example of network configuration between the administrative units

지금까지의 과정을 통해 지역 내 전체 도로 중 주민철수를 위한 도로들이 선정되었고, 이것을 활용하여 모든 Node가 연결 된 네트워크가 구성되었다. 앞서 기술한 바와 같이 주민철수는 선정된 도로를 이용하여 목표지점으로 이동하는데, 철수하는 차량 수 대비 도로의 용량이 제한적이기 때문에 효율적 주민철수를 위해서는 최초 집결지에서의 출발시간을 통제할 수 있는 스케줄이 필요하다. 본 연구에서는 주민철수 스케줄을 CCRP를 사용하여 구성하였다.

CCRP는 2005년 Qingsong Lu 등에 제안된 알고리즘으로 CCRP를 사용하면 전역 최적해 대비 10%내의 우수한 결과를

보장하면서 기존의 LP(Linear Programming)의 제한사항인 Node 수가 증가 할 때 계산시간의 급격한 증가와 Node별 정확

한 이동경로를 확인이 어려운 것을 극복할 수 있다. CCRP는 시계열로 모델링 된 네트워크 내에서 각 Node에서 목표지역까

지의 최단경로를 찾는다. 최단경로룰 이용할 때 시간변화에 따른 도로의 용량제약을 지역 내 모든 Node의 주민이 철수할

때까지 반복 계산하여 하는 Node별 스케줄을 산출할 수 있다.(Qingsong. et al, 2005)[9]

4.4. 메타휴리스틱을 활용한 최적의 네트워크 구성

최적의 주민철수 계획을 수립하기 위해 행정동 별 대표 Node를 결정하는 문제는 메타휴리스틱 기법 중 화음 탐색법을 활용하였다. 화음 탐색법은 2001년 Geem et al.에 의해 제안된 최적화 알고리즘의 하나로 즉흥연주를 하는 연주자들이 지금까지의 경험 및 연습과 감각을 바탕으로 최적의 화음을 찾아가는 과정을 모방해서 고안하였고, 다양한 분야의 NP-Hard 문제를 풀이하는데 많은 성과를 보이고 있다. 화음 탐색법은 기억 의존법(Memory Considering), 음 조정법(Pitch Adjustment), 임의 결정법(Randomization)으로 총 3가지 기법을 확률적으로 활용하여, 새로운 해를 생성해낸다. 유전 알고리즘(GA : Genetic lgorithm)을 비교했을 때, 유전 알고리즘은 2개의 후보해를 고려하여 새로운 해를 생성하나, 화음 탐색법은 모든 후보해를 고려하여 새로운 해를 생성하기 때문에 유전 알고리즘보다 유연한 후보해를 생성할 수 있다.(Geem et al., 2004)[11] 화음 탐색법의 의사코드는 Table. 1.에 나타내었다.

Harmony Search 1: Begin

2: Define Objective Function f(X), X = (x1, x2, …, xn) 3: Define HMCR, PAR, BW and other parameters 4: Generate harmony memory with random harmonies 5: While i < number of iterations

6: While j < number of variables

7: IF(Rand < HMCR) choose a value from HM for the variable j 8: IF(Rand < PAR) adjust the value by adding a certain amount

9: End IF

10: Else IF choose random value

11: End IF

12: End While

13: Accept the new harmony if better 14: End While

15: Find the current best solution 16: End

Table 1. Pseudo Code of Harmony Search

정리하자면, 4.2.와 4.3.의 과정을 통해 주민철수 계획을 수립하였는데, 이 과정은 최적의 네트워크를 구성하기 위한 초기 네트워크 및 초기해를 구하기 위한 과정이었다. 4.3.에서 행정동 간의 네트워크를 결정하는 문제는 행정동 간에 어떤 Node가 연결되는지에 따라 결과값이 다르게 도출되기 때문에 Node를 변경하면서 반복 실험을 통해 최적의 결과를 찾아야 한다.

그래서 행정동 별 대표 Node를 결정하는 문제는 화음탐색법으로 도출하고, 결정된 Node를 Kruscal’s 알고리즘을 적용하

여 행정동 간의 후보 네트워크를 결정하였으며, CCRP 적용을 통해 주민 철수 계획을 도출하는 과정을 반복 시행하여 최적의

주민철수로 및 철수계획(스케줄)을 선정하였다. CCRP는 Node 별로 어떤 경로로 언제, 얼마나 보낼지를 결정하는데, 경로를

결정할 때 A* 탐색 알고리즘을 활용하였다.(Zeng, 2007)[12]

5. 실험방법 및 결과

5.1. 실험 조건

Item Description

Settings

Objective Function MinMax(Dest. Arrival Time), MinAvg(Dest. Arrival Time) Parameter HM = 30, HMCR = 0.9, PAR = 0.7, BandWidth = {-2, 2}

Iteration 10,000

Repetition 30

Environment

OS Windows 10, 64bit

CPU Intel Core i7 (2.67GHz)

Memory 16GB RAM

IDE Visual Studio 2017

Programming Language C# 6.0

Table 2. Experiment environment

화음 탐색법 기반의 주민철수 계획 수립 모형의 목적함수는 마지막 주민의 철수 완료시간 최소화(MinMax)과 주민의 평균 철수 완료시간 최소화(MinAvg)로 설정하였다. 화음 탐색법의 파라미터는 원 개발자의 권장값으로 설정하였으며, 총 30회의 반복실험을 진행하였다. 실험을 진행하기 위해 설정한 파라미터의 값과 실험 환경은 Table. 2.와 같다.

5.2. 실험결과 및 분석

위의 Table. 2.와 같이 주민철수 완료시간의 MinMax과 MinAvg를 목적함수로 설정하여 실험한 결과, CCRP의 연산결과 인 주민철수 계획은 Table. 3.과 같이 스케줄 형태로 도출된다. 본 연구가 설정한 규모의 최종 주민 철수 스케줄은 행의 개수만 400~500개가 되기 때문에 본 논문에는 별도로 기재하지 않았으며, 반복 실험에 따른 결과값의 평균, 표준편차 값과 Best Scenario의 MinMax, MinAvg를 Table. 4에 기재하였다.

ID Source Route with Schedules Dest. Arrival Time No. of Evacuees

1 N70 N70( t

) → N8( t

) → Destination 5 420

2 N26 N26( t

) → N28( t

) → Destination 6 380

3 N73 N73( t

) → N79( t

) → N28( t

) → Destination 9 600

··· ··· ··· ··· ···

484 N4 N4(t

) → N61(t

) → … → N8(t

) → Destination 52 300

485 N4 N4(t

) → N2(t

) → … → N28(t

) → Destination 55 126

Table 3. Example Evacuation Plan

ID Objective Function Results of Repeated Experiments Results of Best Scenario Average of

Objective Value Standard

Deviation Final

Evacuation Time Average Evacuation Time

1 MinMax (Dest. Arrival Time) 125.767 32.577 85 26.651

2 MinAvg(Dest. Arrival Time) 30.969 6.196 96 25.985

Table 4. Experiment Result

모든 Node의 사람들이 철수할 때까지 걸리는 시간의 최대값을 최소화하는 조건의 실험 결과는 Table. 4.의 ID 1과 같았다.

총 30회 반복 실험한 결과 평균은 118.967, 표준편차는 23.102였고 가장 좋은 시나리오의 값은 마지막 주민까지 철수완료가 85,

철수 평균시간은 26.651이었다. 모든 Node의 사람들이 철수할 때까지 걸리는 평균 시간의 값을 최소화하는 조건의 실험 결과는

평균 30.909, 표준편차는 4.993였고, 가장 좋은 시나리오의 값은 마지막 주민까지 철수완료가 96, 철수 평균시간은 25.985이었다.

Fig. 6. Graph of arrival time distribution by destination and node distance(Objective Function:MinAvg)

Fig. 7. Graph of arrival time distribution by destination and node distance(Objective Function:MinMax)

Fig. 6.과 Fig. 7.은 Node와 주민철수 완료시간의 관계를 나타내는 그래프이다. X축은 좌측에서 우측으로 갈수록 목적지와 거리가 먼 Node를 의미하고, Y축은 Node별로 목적지까지 도달한 시간을 의미한다. 도로(Arc)의 용량을 고려하여 Node에 있는 주민을 분산하여 철수시키기 때문에 1개의 Node가 분산된 정도에 따라 여러 Y축의 값을 나타내기도 한다.

두 그래프에서 볼 수 있듯이 CCRP를 적용했을 때 목적지에 가까운 Node부터 목적지로 이동시키는 경향이 있음을 알

수 있다. 그래서 목적지에서 먼 Node일수록 휴전선과 인접에 따른 위험이 클 수 있어 주민철수 계획 수립 시 이에 대한

추가적인 고려가 필요하다.

Fig. 8. Graph of difference in cumulative number of Civilians by time of two scenarios

Fig. 8.은 목적함수(MinMax, MinAvg)별 시나리오의 결과 데이터 중 시간(T)의 변화에 따른 누적 철수주민수의 차이 (ID2-ID1)를 표현한 그래프인데, T=1 ~ T=64 까지 대부분 기간 동안 철수시간의 평균을 최소화하는 시나리오에서 더 많은 주민이 철수하는 것을 알 수 있다. 접경지역 주민의 생존성을 최대한 보존하고, 군 작전 여건 보장을 위해서는 주민철수 가 가능한 빠르게 이루어 져야하고, 현실적으로 100%의 주민을 철수시키기 어렵다는 점을 고려할 때, 주민 철수시간의 평균 을 최소화하는 시나리오가 전면전 주민철수 계획 수립에 보다 적합할 것으로 판단된다.

6. 결론 및 향후연구

본 연구는 효율적인 주민 철수경로 및 일정을 수립하는 것을 목적으로 기존의 재난 대피 관련 선행연구들 중 이산시간 동적 네트워크 흐름 모형에 대한 연구를 기반으로 전면전 시 최적 주민철수 계획수립 모형을 수립하였다. 이 모형은 기존 일반적인 대피 문제의 고려사항에 전면전 시 주민철수 계획이 갖는 4가지 특징을 반영하고, Kruskal’s 알고리즘과 Harmony Search를 사용하여 가용한 모든 경로를 사용 할 수 있는 네트워크가 아닌, 지정된 주민철수로를 이용하는 최적의 네트워크를 구성하였다. 또한 CCRP를 이용하여 Node별 최적의 주민철수 경로 및 스케줄을 산출하였다.

주민철수 계획은 주민의 분포 및 인구, 복잡한 교통망, 군 작전요소, 통제요소 등 고려요소가 많은 복잡한 계획이기 때문에, 계획수립관의 경험과 직관에 의한 정성적 판단으로는 최적의 주민철수 계획을 수립하기 어렵다. 본 연구에서는 정량적 분석 이 가능한 데이터를 기반으로 주민철수 계획수립을 위한 모형을 제안한다.

주민 철수 소요시간을 판단할 때, 철수소요(주민수), 도로의 용량으로 크게 판단할 수 있는데, 이 두 요소에 따라 지자체별 소요시간이 달라질 수 있다. 따라서 시나리오 실험결과를 토대로 가용시간이 충분하다면 마지막 철수시간의 최소화를 목적함 수를 사용하고, 가용시간이 부족하다면 평균 철수시간을 최소화하는 목적함수를 사용하는 것이 적절하다고 판단된다.

주민철수가 이루어지는 시점에 접경지역에서 일어나는 또 다른 중요한 과정은 군의 전투준비이다. 이 과정은 도로를 이용

해 많은 병력과 물자들이 전방지역으로 이동하는 소요를 포함하고, 작전상황 변화에 따른 우발상황에 대비하기 위한 군 작전

로 확보 또한 필요로 한다. 또한 지역 내 주민과 군이라는 두가지 요소가 동시 도로사용에 따른 혼란과 정체가 주민철수에

많은 영향을 미칠 것으로 예상된다. 향후 연구방향은 앞서 설명한 주민철수 계획에 군 전투준비 요소를 반영하여 보다 현실적

인 주민철수 계획을 수립하고자 한다.

감사의 글

이 논문은 2017년도 정부(교육부)의 재원으로 한국연구재단의 지원을 받아 수행된 기초연구사업임.

(No. RF-2015R1D1A1A01058059)

References

[1] 안철현 등. (2011). “대규모 복합재난대비 체계적인 훈련방안 연구“, 행정안전부, MOPAS-재난안전R&D-2011-007) [2] TaeHyun Kim. (2017). “North Korea`s Aggressive Military Strategy: Continuity and Change”, The Quarterly Journal

of Defense Policy Studies, Vol.33(1) pp 163-165

[3] 접경지역 지원 특별법 법률 제12248호(2014. 1. 14. 타법개정)

[4] Robinson, R.M. and Khattak, A. (2011). “Selection of Source and Use of Traffic Information in Emergency Situations”, Transportation Research Record, Vol.2234, pp.71-78.

[5] Robinson, R.M. and Khattak, A. (2012). “Evacuee Route Choice Decisions in a Dynamic Hurricane Evacuation Context”

Transportation Research Record. Vol.2312, pp.141-149.

[6] Qingsong Lu., Yan Huang., Shashi Shekhar. (2003). “Evacuation Planning: A Capacity Constrained Routing Approach“, Forst NFS/NIJ Symposium, Tucson, AZ, USA, (2003), pp.111-125

[7] Lim, G. J., Zangeneh S., (2012). Baharnemati M. Reza and Assavapokee. (2012). “A Capacitated Network Flow Optimization Approach for Short Notice Evacuation Planning”, European Journal of Operational Research, Vol.223(1), pp.234-245.

[8] Shin. Youngchul. (2017). “Mathematical Model and Heuristic Algorithm for Simultaneous Evacuation and Entrance Planning, Master's degree, Seoul National University

[9] Qingsong Lu. Betsy George, and Shashi Shekhar. (2005). “Capacity Constrained Routing Algorithms for Evacuation Planning: A Summary of Results”, 9th International Symposium, SSTD. (2005) pp.291-307

[10] Joseph Kruskal. (1956). “Greedy algorithm for the minimum spanning tree problem”, American Mathematical Society.

[11] Z.W. Geem., J.H. Kim. (2004) “A new heuristic optimization Algorithm: harmony search, Computers and Structures, Vol. 82. pp. 781-798

[12] W. Zeng., R.L. Church.(2007). “Finding shortest paths on real road networks:the case for A*”, International Journal

of Geographical Information Science, Vol.23(4), pp.531-543