본 논문은 여러 구역으로 분할된 도시에서 응급환자가 발생하였을 때 이에 대처하기 위한 최대 허용 도착시간 T를 충족시키면서, 응급시설 수 p를 한정시켰을 때 최대한의 주민수를 커버할 수 있는 응급시설의 최적 위치를 결정하는 알고리즘을 제안하였다. 이 문제는 일반적으로 두 구역 간 소요시간이 최대허용 도착시간이내이면 1로, 그렇지 않으면 0으로 하는 정수계획법으로 변환시키고, 선형계획법 도구를 활용하여 해를 구한다. 본 논문은 p=1인 경우 최대로 커버하는 노드로 결정하며, $p{\geq}2$인 경우 최대한으로 커버할 수 있는 노드 상위 5개를 $p_1$기준으로 포함-배제 원칙을 적용하여 $p_1$이 커버하는 영역을 삭제하였을 때 남은 노드들 중에서 최대로 커버하는 노드를 $p_2$로, $p_1,p_2$ 커버 영역을 삭제시 최대로 커버할 수 있는 노드를 $p_3$로 결정하였다. 이들 5개 기준 노드 집합 들 중에서 최대로 커버하는 노드 집합을 최적의 응급시설 위치로 결정하였다. 제안된 알고리즘을 12-노드 망, 21-노드 망과 Swain의 55-노드 망에 적용한 결과 최적해를 쉽고 빠르며, 정확하게 결정할 수 있었다.
본 논문은 여러 구역으로 분할된 도시에서 응급환자가 발생하였을 때 이에 대처하기 위한 최대 허용 도착시간 T를 충족시키면서, 응급시설 수 p를 한정시켰을 때 최대한의 주민수를 커버할 수 있는 응급시설의 최적 위치를 결정하는 알고리즘을 제안하였다. 이 문제는 일반적으로 두 구역 간 소요시간이 최대허용 도착시간이내이면 1로, 그렇지 않으면 0으로 하는 정수계획법으로 변환시키고, 선형계획법 도구를 활용하여 해를 구한다. 본 논문은 p=1인 경우 최대로 커버하는 노드로 결정하며, $p{\geq}2$인 경우 최대한으로 커버할 수 있는 노드 상위 5개를 $p_1$기준으로 포함-배제 원칙을 적용하여 $p_1$이 커버하는 영역을 삭제하였을 때 남은 노드들 중에서 최대로 커버하는 노드를 $p_2$로, $p_1,p_2$ 커버 영역을 삭제시 최대로 커버할 수 있는 노드를 $p_3$로 결정하였다. 이들 5개 기준 노드 집합 들 중에서 최대로 커버하는 노드 집합을 최적의 응급시설 위치로 결정하였다. 제안된 알고리즘을 12-노드 망, 21-노드 망과 Swain의 55-노드 망에 적용한 결과 최적해를 쉽고 빠르며, 정확하게 결정할 수 있었다.
This paper proposes an EMS algorithm designed to determine the optimal locations for Emergency Medical Service centers that both satisfy the maximum ambulance response time T in case of emergency and cover the largest possible number of residents given a limited number of emergency medical services ...
This paper proposes an EMS algorithm designed to determine the optimal locations for Emergency Medical Service centers that both satisfy the maximum ambulance response time T in case of emergency and cover the largest possible number of residents given a limited number of emergency medical services p in a city divided into different zones. This methodology generally applies integer programming whereby cases are categorized into 1 if the distance between two zones is within the response time and 0 if not and subsequently employs linear programming to obtain the optimal solution. In this paper, where p=1, the algorithm determines a node with maximum coverage. In cases where $p{\geq}2$, the algorithm selects top 5 nodes with maximum coverage. Based on inclusion-exclusion method, this selection entails repeatedly selecting a node with the maximum coverage when nodes with lower numbers are deleted. Among these 5 selected nodes, the algorithm selects a single node set with the greatest coverage and thereby as the optimal EMS location. The proposed algorithm has proven to accurately and expeditiously obtain the optimal solutions for 12-node network, 21-node network, and Swain's 55-node network.
This paper proposes an EMS algorithm designed to determine the optimal locations for Emergency Medical Service centers that both satisfy the maximum ambulance response time T in case of emergency and cover the largest possible number of residents given a limited number of emergency medical services p in a city divided into different zones. This methodology generally applies integer programming whereby cases are categorized into 1 if the distance between two zones is within the response time and 0 if not and subsequently employs linear programming to obtain the optimal solution. In this paper, where p=1, the algorithm determines a node with maximum coverage. In cases where $p{\geq}2$, the algorithm selects top 5 nodes with maximum coverage. Based on inclusion-exclusion method, this selection entails repeatedly selecting a node with the maximum coverage when nodes with lower numbers are deleted. Among these 5 selected nodes, the algorithm selects a single node set with the greatest coverage and thereby as the optimal EMS location. The proposed algorithm has proven to accurately and expeditiously obtain the optimal solutions for 12-node network, 21-node network, and Swain's 55-node network.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문은 예산상의 이유로 한정된 응급시설 개수가 결정되었을 때, T범위를 만족시키는 주민수를 최대한으로 할 수있는 응급시설 위치를 결정하는 알고리즘을 제안한다.
본 논문은 한 도시의 모든 주민들을 만족시킬 수 있는 응급시설의 개수를 결정하는 문제가 아닌, 예산 부족으로 인해 한정된 응급시설 개수만을 설치할 경우 최대로 주민들을 만족시킬 수 있는 위치를 결정하는 알고리즘을 제안하였다.
본 논문은 한정된 응급시설 개수를 최적으로 설치하는 알고리즘을 제안한다. 2장에서는 관련 연구와 문제점을 고찰한다.
한 도시에 n개의 구역 Ni, (i=1,2,⋯,n)이 존재하고, 두 구역 Ni와 Nj간 거리 dij를 알고 있다고 하자. 만약, 응급상황이 발생하였을 때 임의의 응급구조시설 Sj에서 응급환자 수송차량이 임의의 구역 Ni까지 도착하는데 허용되는 최대 소요시간 T는 준수하여야만 주민의 생명을 지킬 수 있다고 가정하자.
가설 설정
를 알고 있다고 하자. 만약, 응급상황이 발생하였을 때 임의의 응급구조시설 Sj에서 응급환자 수송차량이 임의의 구역 Ni까지 도착하는데 허용되는 최대 소요시간 T는 준수하여야만 주민의 생명을 지킬 수 있다고 가정하자. 이 경우, 이 도시 주민 모두를 만족시키도록 응급시설 p를 최소로 몇 곳에 설치하는 것이 가장 효율적인가를 판단해야만 한다[1].
제안 방법
12-노드와 21-노드 망에 대해서는 총 주민수를 커버하는 응급시설 개수는 기존의 최적 알고리즘과 동일한 개수를 구할 수 있었다. 55-node 망에 대해서는 5개 까지의 응급시설 개수로 최대로 커버하는 주민수를 구하였다.
12-노드, 21-노드와 55-노드 망에 대해 기존의 연구 결과와 제안된 알고리즘의 성능을 비교한 결과는 표 9에 요약하여 제시하였다. 기존의 알고리즘은 전체 주민수를 커버하기 위한 응급시설의 개수에 초점을 맞춘 반면에, 제안된 알고리즘은 주민수를 최대로 최대로 커버할 수 있는 제한된 응급시설의 개수를 찾고자 하였다. 12-노드와 21-노드 망에 대해서는 총 주민수를 커버하는 응급시설 개수는 기존의 최적 알고리즘과 동일한 개수를 구할 수 있었다.
이와 같이 p ≥ 2에 대해서는 포함-배제 원칙이 적용되기 때문에 Top 5의 5개 노드 각각의 교집합의 크기를 알 수 없어 Top 1 노드가 반드시 최적의 해라고 할 수 없다. 따라서 5개 노드에 대해 계산을 하여 그 중에서 최대로 커버하는 노드를 결정하는 방법을 적용한다. 만약, 최대 인원수 커버 노드를 선택하는 방법을 단순히 적용하면 다음과 같이 {4, 33, 36, 23, 21}의 5개 위치를 결정할 수 있으며, 이 경우 {12, 14, 27, 39, 40, 43, 46, 49, 50, 52, 53, 54, 55}의 13 노드 567명을 커버하지 못해 3,575명 중 3,008명만을 커버하여 좋은 결과를 얻지 못한다.
이 경우에 설치 가능한 p의 개수가 정책적으로 결정되었을 경우 가능한 최대한의 주민을 만족시키는 위치를 결정하는 것이 최선책이다. 본 장에서는 최대한의 도착 시간 (또는 거리) T의 조건을 만족하면서 p의 개수가 주어졌을 경우 p의 최적의 위치를 찾는 알고리즘을 다음과 같이 제안한다.
제안된 알고리즘은 포함-배제 원칙을 적용하여 최대로 커버하는 노드 상위 5개에 대해 해당 노드가 커버하는 영역을 삭제하였을 때 다음으로 최대로 커버하는 노드를 선택하는 방법을 적용하였다. 이들 상위 5개 노드 집합들 중에서 최대로 커버하는 노드 집합을 최적의 응급시설 위치로 결정하였다.
제안된 알고리즘은 포함-배제 원칙을 적용하여 최대로 커버하는 노드 상위 5개에 대해 해당 노드가 커버하는 영역을 삭제하였을 때 다음으로 최대로 커버하는 노드를 선택하는 방법을 적용하였다. 이들 상위 5개 노드 집합들 중에서 최대로 커버하는 노드 집합을 최적의 응급시설 위치로 결정하였다.
참고로, 표 1의 55-노드 망과 표 4의 21-노드 망에 대해 모든 주민수를 커버할 수 있는 응급시설의 개수를 구하였다. 55-노드 망에 대해서는 모든 주민 3,575를 T=10이내에 만족시킬 수 있는 응급시설의 개수는 p=9이며, 그림 2에 제시하였다.
대상 데이터
본 논문에서는 응급시설의 위치를 결정함에 있어 단순히 최대로 커버할 수 있는 주민수나 도달거리 T만을 고려하였다. 따라서, 추후 본 알고리즘을 실제 응급시설 설치분야에 적용하여 추가로 고려할 요인은 없는지 연구할 예정이다.
이론/모형
주어진 거리 행렬 데이터 D의 거리 (또는 시간)를 aij로 치환한 행렬 데이터 A에 대해 기존 알고리즘은 선형계획법(Linear programming, LP), 집합피복 (Set covering), 중앙값 방법 (Median method), 중심점 방법 (Center method)으로 해를 구하였다. 집합피복 문제의 정확한 해(exact solution)를 다항시간에 구하는 알고리즘은 아직 알려지지 않아 NP-완전 (Non-deterministic Polynomialcomplete)에 속하는 문제이다[4-7].
성능/효과
기존의 알고리즘은 전체 주민수를 커버하기 위한 응급시설의 개수에 초점을 맞춘 반면에, 제안된 알고리즘은 주민수를 최대로 최대로 커버할 수 있는 제한된 응급시설의 개수를 찾고자 하였다. 12-노드와 21-노드 망에 대해서는 총 주민수를 커버하는 응급시설 개수는 기존의 최적 알고리즘과 동일한 개수를 구할 수 있었다. 55-node 망에 대해서는 5개 까지의 응급시설 개수로 최대로 커버하는 주민수를 구하였다.
제안된 알고리즘은 이해하기 쉽고, 엑셀을 활용해도 쉽게 적용할 수 있기 때문에 일반적으로 활용할 수 있는 알고리즘임을 알 수 있다.
제안된 알고리즘을 12-노드 망, 21-노드 망과 55-노드 망에 적용한 결과 모든 망에 대해 최적의 위치를 찾을 수 있음을 보였다.
후속연구
본 논문에서는 응급시설의 위치를 결정함에 있어 단순히 최대로 커버할 수 있는 주민수나 도달거리 T만을 고려하였다. 따라서, 추후 본 알고리즘을 실제 응급시설 설치분야에 적용하여 추가로 고려할 요인은 없는지 연구할 예정이다.
질의응답
핵심어
질문
논문에서 추출한 답변
한 도시에 거주하는 모든 주민을 만족시키도록 응급시설을 몇 곳에 설치하는 것이 가장 효율적인가에 대한 해를 구하는 방법은 무엇이 있는가?
한 도시에 거주하는 모든 주민을 만족시키도록 응급시설을 몇 곳에 설치하는 것이 가장 효율적인가에 대한 해를 구하는 방법은 선형계획법 (Linear programming, LP), 집합피복(Set covering), 중앙값 방법 (p-Median method), 중심점 방법 (p-Center method)이 있다[3]. 중앙값과 중심점 방법은 모든 구역간의 최단거리의 최대값이 tij ≤ T가 되도록 응급시설의 위치를 이동시키는 방법이다.
Set covering 문제가 NP-완전에 속하는 문제인 이유는?
주어진 거리 행렬 데이터 D의 거리 (또는 시간)를 aij로 치환한 행렬 데이터 A에 대해 기존 알고리즘은 선형계획법(Linear programming, LP), 집합피복 (Set covering), 중앙값 방법 (Median method), 중심점 방법 (Center method)으로 해를 구하였다. 집합피복 문제의 정확한 해(exact solution)를 다항시간에 구하는 알고리즘은 아직 알려지지 않아 NP-완전 (Non-deterministic Polynomialcomplete)에 속하는 문제이다[4-7]. NP-완전 문제는 미국 클레이 수학재단에서 100만불의 상금을 제시한 21세기에 풀어야 할 7개 문제 중 첫 번째인 “P=NP?”이다[8].
중앙값과 중심점 방법은 무엇인가?
한 도시에 거주하는 모든 주민을 만족시키도록 응급시설을 몇 곳에 설치하는 것이 가장 효율적인가에 대한 해를 구하는 방법은 선형계획법 (Linear programming, LP), 집합피복(Set covering), 중앙값 방법 (p-Median method), 중심점 방법 (p-Center method)이 있다[3]. 중앙값과 중심점 방법은 모든 구역간의 최단거리의 최대값이 tij ≤ T가 되도록 응급시설의 위치를 이동시키는 방법이다. 반면에, 선형계획법과 집합피복은 식 (1)과 같이 정수계획법 (Integer programming, IP)을 적용하여 tij ≤ T이면 1로, tij > T이면 0으로 치환한다[1].
참고문헌 (12)
M. S. Daskin and E. H. Stern, "A Hierarchical Objective Set Covering Model for Emergency Medical Service Vehicle Deployment", Transportation Science, Vol. 15, No. 2, pp. 137-152, May. 1981.
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, Wikipedia Foundation Inc., 2013.
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.
L. Dawei, L. Yanjie, and W. Li, "Model and Algorithms for Emergency Service Facility Location Problem", International Conference on Services Science, Management and Engineering (IITA), pp. 15-19, IEEE Computer Science, Jul. 2009.
J. E. Storbeck and R. V. Vohra, "A Simple Trade-off Model for Maximal and Multiple Coverage", Geographical Analysis, Vol. 20, No. 3, pp. 220-230, Jul. 1988.
D. Serra and C. ReVelle, "Surviving in a Competitive Spatial Market: The Threshold Capture Model", Journal of Regional Science, Vol. 39, No. 4, pp. 637-650, Feb. 1999.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.