[논문]응급시설 위치 문제

최명복; 김봉경; 한태용

doi:10.7236/jiwit.2011.11.6.183

응급시설 위치 문제
Emergency Medical Service Location Problem 원문보기

한국인터넷방송통신학회 논문지 = The journal of the Institute of Internet Broadcasting and Communication, v.11 no.6, 2011년, pp.183 - 191

최명복 (강릉원주대학교 멀티미디어공학과) , 김봉경 (남서울대학교, 스포츠경영학과) , 한태용 (강릉원주대학교, 여성인력개발학과)

초록
AI-Helper

본 논문은 하나의 도시가 여러 구역으로 분할되고, 응급환자가 발생하였을 때, 모든 구역에 대해 최대 허용 도착시간 T를 충족시키도록 응급시설을 배치하는 문제에 대한 알고리즘을 제안하였다. 이 문제는 일반적으로 다항시간으로 해를 구하는 알고리즘이 존재하지 않아 두 구역 간 소요시간이 최대허용 도착시간이내이면 1로, 그렇지 않으면 0으로 하는 정수계획법으로 변환시키고, 선형계획법 도구를 활용하여 해를 구한다. 본 논문은 최소차수 노드의 이웃 노드들 중 최대 차수 노드를 응급시설의 위치로 결정하는 집합피복 알고리즘을 적용하였다. 제안된 알고리즘을 텍사스 오스틴 시의 33개 구역에 대한 사례에 대해 $3{\leq}T{\leq}20$ (분)을 적용하고, Swain의 55개 노드 망에 대해 T=15에 대해 응급시설의 위치를 결정할 수 있는지 여부를 검증하였다. 선형계획법을 활용한 전통적인 집합피복 알고리즘은 몇 개의 T에 대해 해를 구하지 못한 반면에, 제안된 알고리즘은 18개의 모든 T에 대해 해를 구하였다.

Abstract ▼ AI-Helper

This paper suggests emergency medical service vehicle (ambulance) algorithm when the emergency patient occurs in order to be sufficient the maximum permission time T of arrival about all sectors in one city that is divided in the various areas. This problem cannot be solved in polynomial times. One can obtains the solution using the integer programming. In this paper we suggest vertex set (or dominating set) algorithm and easily decide the location of ambulances. The core of the algorithm decides the location of ambulance is to the maximum degree vertex among the neighborhood of minimum degree vertex. For the 33 sectors Ostin city in Texas, we apply $3{\leq}T{\leq}20$ minutes. The traditional set cover algorithm with integer programming cannot obtains the solution in several T in 18 cases. But, this algorithm obtains solution for all of the 18 cases.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문은 최소 응급시설 대수를 구하기 위해 최소 집합피복의 근사 해 (Approximate solution)를 찾는 욕심쟁이 알고리즘 (Greedy algorithm)을 제안한다. 2장에서는 관련 연구를 고찰한다.
어떤 한 도시 (광역, 또는 지방)에 설치되는 경찰서, 소방서와 응급의료시설과 같은 응급구조 시설은 사회적, 경제적과 정책적 목적을 만족시켜야만 한다. 특히, 한 도시에 n개의 구역 N_i, (i = 1,2,⋯,n)이 존재하고, 두 구역 N_i와 N_j간 거리 d_ij를 알고 있다고 하자. 만약, 응급상황이 발생하였을 때 임의의 응급구조시설 S_j에서 응급환자수송차량 (응급시설, ambulance)가 임의의 구역 N_i까지 허용되는 최대 도착시간 T 는 준수하여야 주민의 생명을 지킬 수 있다고 가정하자.

가설 설정

특히, 한 도시에 n개의 구역 N_i, (i = 1,2,⋯,n)이 존재하고, 두 구역 N_i와 N_j간 거리 d_ij를 알고 있다고 하자. 만약, 응급상황이 발생하였을 때 임의의 응급구조시설 S_j에서 응급환자수송차량 (응급시설, ambulance)가 임의의 구역 N_i까지 허용되는 최대 도착시간 T 는 준수하여야 주민의 생명을 지킬 수 있다고 가정하자. 이 경우, 이 도시에 응급시설을 최소로 몇 대 배치하는 것이 가장 효율적인가를 판단해야만 한다.

제안 방법

Daskin과 Stern은 최대 허용 응답시간 T 를 3분에서 20분까지 1분 단위로 변화시키면서 응급시설 수와 위치를 선형계획법과 유사한 집합피복 (또는 지배집합) 방법으로 구하였다. 이때 지배된 집합을 포함하는 CSC (Conventional Set Covering)와 지배된 집합을 배제시키는 HOSC (Hierarchical Objective Set Covering)방법으로 하여 해를 구하였다.
T = 15의 경우 정확히 5개의 응급시설 위치인 53,21, 43,22,36을 얻었다. Swain 55-노드 망에 대해서는 편의상 각 노드들에서의 최단거리를 계산하지 않고 시각적으로 결정하는 방법을 적용하였다.
첫 번째로, 33개의 구역으로 구성된 텍사스 오스틴 시에 대해 최대 허용 도착시간 T를 3 ≤ T ≤ 20(분)을 1분 간격으로 가정하였을 경우 모든 T에 대해 응급시설의 위치를 쉽게 결정할 수 있었다. 두 번째로, Swain의 55-노드 망에 대해 T = 15에 대해 해를 구하였다.
29로 T =15를 초과한다. 또한, ② 노드는 37, 52, 55, 22 노드로 부터도 T = 15를 초과하여 어느 노드에서도 커버될 수 없어 6개의 응급시설 위치를 결정하여야 하나 5개의 위치만 결정하였다.
본 논문은 NP-완전 문제로 선형계획법, 집합피복 또는 지배집합으로도 해를 구하기가 어려운 응급시설 위치를 결정하는 문제에 대해 O(n²)의 다항시간으로 집합피복 (또는 지배집합)으로 해를 구하는 알고리즘을 제안하였다.
본 장에서는 먼저, Daskin과 Stern^[1]이 표 1에 대해 CSC와 HOSC로 해를 얻지 못한 최대 도착 허용시간 T = 9, 10, 14 (분)를 포함한 모든 T = [3,20]에 대한 해를 구하여 본다.
만약, 임의의 노드 v_i를 선택하면 v_i는 인접한 노드들을 피복 (covering) 또는 지배 (dominate)한다고 한다. 이러한 그래프 개념을 도입하여 제안된 알고리즘은 두 번째로, 0-1 정수계획법 행렬 A의 각 행에 대해 1의 개수 (차수)의 합을 구한다. 최소차수 노드 δ(G) = v의 이웃 N_G(v) = u들 중에서 최대차수 _maxd_G(u)인 노드 u를 선택하여 응급시설의 위치로 결정한다.

대상 데이터

표 1에서, 각 행의 최대 값의 최소값은 15이며, 이에 해당되는 노드는 7과 11이다. 7과 11 노드 중 모든 노드까지의 총 소요시간이 최소인 11 노드를 최적 위치로 선정하였다. 즉, 15 ≤ T ≤ 20에 대한 응급시설의 위치는 11 노드로 16 ≤ T≤ 20은 구하지 않아도 됨을 알 수 있다.
제안된 알고리즘을 Daskin과 Stern^[1]로부터 인용된 그림 4의 2개 데이터에 적용하여 보자. 먼저 6개 노드가 존재할 경우 ③과 ②를 선택하여 응급시설 위치로 쉽게 결정할 수 있었으며, 11개 노드가 존재할 경우 ③과 ⑤를 선택할 수 있었다.

이론/모형

Daskin과 Stern은 최대 허용 응답시간 T 를 3분에서 20분까지 1분 단위로 변화시키면서 응급시설 수와 위치를 선형계획법과 유사한 집합피복 (또는 지배집합) 방법으로 구하였다. 이때 지배된 집합을 포함하는 CSC (Conventional Set Covering)와 지배된 집합을 배제시키는 HOSC (Hierarchical Objective Set Covering)방법으로 하여 해를 구하였다. 이 방법을 적용하기 위해서는 응급시설 수를 최소화시키는 목적함수값 W을 적절히 설정하는 문제도 제기된다.
주어진 거리 행렬 데이터 D의 거리 (또는 시간)를 a_ij로 치환한 행렬 데이터 A에 대해 기존 알고리즘은 선형 계획법 (Linear programming, LP), 집합피복 (Set covering), 중앙값 방법 (Median method), 중심점 방법 (Center method)으로 해를 구하였다. 집합피복 문제의 정확한 해 (exact solution)를 다항시간에 구하는 알고리즘은 아직 알려지지 않아 NP-완전 (Non-deterministic Polynomial complete)에 속하는 문제이다.

성능/효과

CSC 방법은 T = 9,10,14의 3가지 경우에 대해 응급시설의 위치를 구하지 못한 반면에, HOSC는 T = 10의 1가지 경우에서 응급시설의 위치를 구하지 못하였다. 두 방법 모두 T = 10에서 응급시설 배치 장소 수는 정수값 대신 실수값 3.75대를 구하여 현실성이 없음을 알 수 있다.
제안된 방법은 그림 3에 제시되어 있다. 즉, 제안된 알고리즘은 선형계획법과 같이 목적함수를 결정하지도 않아도 쉽게 적용할 수 있는 장점을 갖고 있다.
첫 번째로, 33개의 구역으로 구성된 텍사스 오스틴 시에 대해 최대 허용 도착시간 T를 3 ≤ T ≤ 20(분)을 1분 간격으로 가정하였을 경우 모든 T에 대해 응급시설의 위치를 쉽게 결정할 수 있었다.

후속연구

제안된 알고리즘은 응급수송차량 배치 문제 뿐 아니라, 통신분야의 무선중계기, 각종 공공시설의 위치 결정등 다양한 분야에 응용될 수 있을 것이다.
제안된 알고리즘은 각 구역의 주민 수와 한 대의 응급 시설이 출동 시 또 다른 응급환자가 발생하였을 경우 이에 대처할 수 있는 응급시설의 대수는 고려하지 않았다. 추후 이러한 현실적인 제약사항들을 고려한 알고리즘을 연구할 예정이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	어떤 한 도시 (광역, 또는 지방)에 설치되는 응급구조 시설은 어떠한 요구를 필요로 하는가?	어떤 한 도시 (광역, 또는 지방)에 설치되는 경찰서, 소방서와 응급의료시설과 같은 응급구조 시설은 사회적, 경제적과 정책적 목적을 만족시켜야만 한다. 특히, 한 도시에 n개의 구역 Ni , (i = 1,2,⋯,n)이 존재하고, 두 구역 Ni와 Nj간 거리 dij를 알고 있다고 하자.
	한 도시에 응급시설을 몇 대 배치하는 것이 가장 효율적인가에 대한 연구의 답을 찾기위해선 어떠한 방법을 사용할 수 있는가?	본 논문은 한 도시에 응급시설을 몇 대 배치하는 것이 가장 효율적인가에 대한 연구에 한정한다. 이 문제의 해를 구하는 방법은 선형계획법 (Linear programming, LP), 집합피복 (Set covering), 중앙값 방법 (Median method), 중심점 방법 (Center method)이 있다.[2] 중앙값과 중심점 방법은 모든 구역간의 최단거리의 최대값이 tij ≤ T가 되도록 응급시설의 위치를 이동시키는 방법이다.
	선형계획법과 집합피복은 어떠한 계획법을 적용하는가?	[2] 중앙값과 중심점 방법은 모든 구역간의 최단거리의 최대값이 tij ≤ T가 되도록 응급시설의 위치를 이동시키는 방법이다. 반면에, 선형계획법과 집합피복은 식 (1)과 같이 정수계획법 (Integer programming, IP)을 적용하여 tij ≤ T이면 1로, tji > T이면 0으로 치환한다.[1]

참고문헌 (10)

M. S. Daskin, "A Hierarchical Objective Set Covering Model for Emergency Medical Service Deployment", Transportation Science, Vol. 15, No. 2, pp. 137-152, 1981.

상세보기
R. Z. Farahani and M. Hekmatfar, "Facility Location: Concepts, Models, Algorithms and Case Studies", Springer-Verlag Berlin Heidelberg, 2009.
L Carsten and Y. Mihalis, "On the Hardness of Approximating Minimization Problems", Journal of the ACM, Vol. 41, No. 5, pp. 960-981, 1994.

상세보기
V. Chvatal, "A Greedy Heuristic for the Set-Covering Problem", Mathematics of Operations Research, Vol. 4, No. 3, pp. 233-235, 1979.

상세보기
R. M. Karp, Reducibility Among Combinatorial Problems", Complexity of Computer Computations, New York: Plenum, pp. 85-103, 1972.
Wikipedia, "List of NP-complete Problems", http://en.wikipedia.org/wiki/List_of_NP-complete_ problems, 2011.
K. J. Devlin, "The Millennium Problems: The Seven Greatest Unsolved Mathematical Puzzles of Our Time", Basic Books. 2002.
R. J. Vanderbei, "Linear Programming: Foundations and Extensions", 3rd ed., International Series in Operations Research & Management Science, Vol. 114, Springer Verlag, 2008.
R. Church and C. ReVelle, "The Maximal Covering Location Problem", Journal of Regional Science, Vol. 32, pp. 101-118, 1974.

상세보기
D. Serra and C. ReVelle, "Surviving in a Competitive Spatial Market: The Threshold Capture Model", Journal of Regional Science, Vol. 39, Issue. 4, pp. 637-650, 1999.

상세보기

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증