[논문]p-시설물 위치선정 모델

최명복; 이상운; 김봉경; 정승삼; 한태용

doi:10.7236/jiwit.2011.11.6.193

p-시설물 위치선정 모델
p-Facility Location Models 원문보기

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

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

초록
AI-Helper

본 논문은 $m$개의 후보 시설과 $n$개의 거주지역이 존재하는 경우, 비용 (주민수 ${\times}$ 최단거리) 측면에서 $p$개의 최적의 시설 위치를 선정하는 알고리즘을 제안하였다. 이 문제는 다항시간 알고리즘이 제안되지 않아 NP-난제로 분류되어 있다. 본 논문에서는 각 지역에서의 최소 비용을 선택한 $p=m$의 시설로부터 각 지역을 다음 최소 비용 시설로 이동시킬 경우 최소비용합으로 삭제할 수 있는 후보 시설을 $p=2$가 될 때까지 한 번에 하나씩 제거하는 방법으로 역-삭제 방법이다. 제안된 알고리즘은 다양한 문제들에 적용한 결과 $m{\times}n$이 $5{\times}5$, $7{\times}7$인 경우에는 초기 해로 최적해를 구하였다. Swain의 55-노드 망에 대해서는 $p=4$인 경우 해 개선 과정을 수행하여 최적해를 구하였으며, $p=5$인 경우에는 초기해로 최적해를 구하였다.

Abstract ▼ AI-Helper

This paper suggests $p$-facility locations in $m$ candidate locations and $n$ areas in optimal cost side(population${\times}$shortest distance). This problem has been classified by NP-complete because there is not a polynomial time algorithm. In this paper, we suggests reverse-delete method that deletes a candidate facility one by one from $p=m$ until $p=2$. As a result of the proposed algorithm for the $5{\times}5$ and $7{\times}7$, the initial solution is obtained. For the Swain's 55-node network, we obtain the optimal solution through a solution improvement process with $p=4$ and it by using the initial solution with $p=5$.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 논문은 공공시설, 주민편의시설 또는 대형마켓 등 다양한 시설을 설치할 최적의 위치를 선정하는 알고리즘을 제안하였다. 이 문제는 다항시간에 최적해를 구할 수 있는 알고리즘이 제안되지 않아 NP-난제로 알려져 있다.
본 논문은 시설의 최적 위치를 결정하는 p-중앙값 문제에 대해 휴리스틱한 근사해를 구하는 알고리즘을 제안한다. 제안된 방법은 p = n부터 p = 2까지 해당 노드 L_j를 가장 인접한 F_i로 이동시 최단거리 (또는 비용) 합이 최소가 되는 시설 1개를 삭제하는 역-삭제 (Reverse-delete) 방법으로 최적의 위치를 찾는다.

제안 방법

본 장에서는 먼저, Eiselt와 Sandblom^[1]에서 인용된 그림 5의 3개 데이터에 대해 제안된 알고리즘을 적용하여 보고, 다음으로 표 2의 Swain 55-노드 망 데이터에 적용하여 본다. C₂ 데이터는 p = 2에 대해 Lagrangean Relaxation으로, C₃데이터는 p = 3에 대해 욕심쟁이 알고리즘 (Greedy algorithm)으로, S₁ 데이터는 p = 3에 대해 p-중심 문제로 해를 구한 사례이다.
본 장에서는 새로운 개념의 시설위치 결정 알고리즘을 제안한다. 제안되는 알고리즘은 일반적으로 m개 지점 중 p개의 시설 후보지를 결정하는 경우 p = m으로 초기 집합으로 설정하고, 각 후보 시설 집합에 속한 노드들을 최소비용이 소요되는 다른 후보시설들이 커버 또는 지배하도록 이동시 비용합이 최소가 되는 후보시설 집합을 삭제하는 방법이다.
본 장에서는 새로운 개념의 시설위치 결정 알고리즘을 제안한다. 제안되는 알고리즘은 일반적으로 m개 지점 중 p개의 시설 후보지를 결정하는 경우 p = m으로 초기 집합으로 설정하고, 각 후보 시설 집합에 속한 노드들을 최소비용이 소요되는 다른 후보시설들이 커버 또는 지배하도록 이동시 비용합이 최소가 되는 후보시설 집합을 삭제하는 방법이다. 즉, 최소비용이 소요되는 후보 시설을 삭제하는 방법이다.
이와 같은 방법으로 최소비용 합 후보 시설을 삭제하는 방법을 적용하면 p = 2인 경우 p = {1,2}를 얻는다. 제안된 p-RD 알고리즘은 m -1회 수행되며, 각 시행시점에서 1개의 후보 시설이 삭제되고, 이 후보 시설에 가장 근접한 L_j들의 다음 근접한 후보 시설인 최소값을 선택하는 과정을 수행한다. 이는 최대 O(mn) 수행시간이 소요되므로, 제안된 알고리즘의 수행시간은 O(m²n) ≃O(n³)이 된다.
본 논문은 시설의 최적 위치를 결정하는 p-중앙값 문제에 대해 휴리스틱한 근사해를 구하는 알고리즘을 제안한다. 제안된 방법은 p = n부터 p = 2까지 해당 노드 L_j를 가장 인접한 F_i로 이동시 최단거리 (또는 비용) 합이 최소가 되는 시설 1개를 삭제하는 역-삭제 (Reverse-delete) 방법으로 최적의 위치를 찾는다. 2장에서는 p-중앙값 문제와 Caccetta와 Dzator^[4]가 제안한 휴리스틱 방법을 고찰한다.
하나의 후보 시설 집합 F_i가 삭제시 이 후보시설집합에 속한 노드들을 최소비용 후보시설들의 L_j로 이동시키고, 이동시틴 노드들과 삭제된 F_i롤 F_i로 하는 L_j 노드들에 대해서만 최소비용이 소요되는 다른 후보시설 F_i와 비용 c_ij를 갱신한다. 제안된 알고리즘은 p의 개수가 1개씩 감소시키는 형태로 p-RD (p-Reverse Delete) 알고리즘이라 칭하며, 그림 3과 같이 수행된다.
제안된 알고리즘은 목적함수를 일반적인 응급시설 위치 선정 문제와 같은 도달 가능 시간 T 이내이면 “1” 로 설정하는 0-1 정수계획법을 적용하지 않고, 단지 주민수와 거리의 곱인 비용으로 결정하였다.
제안된 알고리즘은 초기 집합으로 p = n = 5에 대해 c_ij = 0을 선택한 p = {1,2,3,4,5}를 구하였다. 다음으로, c_ij = 0을 삭제하고 L_j, (j = 1,2,⋯,5) 행에서 최소값을 선택하고, (F_i ,L_j)로 표기할 경우 _minc_ij인 (2,3) = 18을 얻는다.
제안된 알고리즘은 후보 응급시설 개수 m과 주민이 거주하는 지역 (노드) n이 존재할 경우, 초기치로 p = m으로 설정하고, 각 후보 응급시설을 삭제하고 다른 최소비용 응급시설로 병합할 경우 최소의 비용합인 후보 응급시설을 삭제하는 방법으로 한 번에 하나씩 삭제하는 방법을 적용하였다.

성능/효과

왜냐하면 p-개의 시설물은 외곽 경계에는 위치하지 않기 때문이다. 따라서 55개 노드 중에서 19개 노드에 대해 가장 인접한 비용 (최소비용)노드로 이동시키면 p = 36을 얻는다. 이 경우 p ={1,2,⋯,11,13,15,{16, 14,27}, {17,28,12}, {18,26}, 19, {20,21,49,51}, 22, {25,48}, {29,23}, 30,31,32,33, 34,{36,24,35}, {38,54}, 41,42,{43,46}, 44,45,47, {53,37,50,52}, {55,39,40}}을 얻는다.
제안된 p-RD 알고리즘으로 구한 초기해는 C₁, C₂, C₃, S₁과 Swain의 55-노드 망 p = 5에 대해서는 최적의 해를 구하였다. 다만, Swain의 55-노드 망 p = 4에 대해서만 해를 개선하는 과정을 수행하야 함을 알 수 있다.
제안된 알고리즘은 m×n이 5×5, 7×7인 C1, C2, C3, S1 데이터의 경우에는 초기 해로 최적해를 얻을 수 있음을 보였다.

질의응답

핵심어	질문	논문에서 추출한 답변
	시설에 대한 최적의 위치를 찾는 위치 이론은 어느 측면에서 많은 관심의 대상이 되고 있나요?	시설에 대한 최적의 위치를 찾는 위치 이론 (location theory)은 수학, 컴퓨터과학, OR (operational research), 경제, 지리학 등 많은 학문들에 근거를 둔 학제적 분야로 경제적 목적 또는 공공서비스 측면에서 많은 관심의 대상이 되고 있다.
	p-중앙값 문제의 해는 어떤 장점이 있나요?	Cooper는 1963년에 다중시설 위치-재배치 문제를 시작하기 위해 단일-시설 문제를 확장하였으며, Hakimi는 1964년에 p-중심과 p-중앙값 문제의 기초를 완성하였다. p-중심 문제의 해는 반드시 노드들에 위치하지 않는 반면에, p-중앙값 문제의 해는 항상 노드들에 위치하는 장점이 있다. 따라서 시설 위치 결정 문제는 p-중앙값 문제로 발전하였다.
	위치이론에서 p-중앙값 개념이란 무엇인가?	고객과 시설간의 평균거리 (average distance)가 감소하면 시설 접근성 (accessibility)은 증가하며, 평균 응답시간 (반응시간, response time)은 감소한다. 이 개념이 p-중앙값 (p-Median) 이다.

참고문헌 (7)

H. A. Eiselt and C-L, Sandblom, "Decision Analysis, Location Models, and Scheduling Problems, Part II: Location and Layout Decisions, Chapter 2. Location models on Networks", Springer-Verlag Berlin Heidelberg, pp. 169-210, 2004.
H. Jia, F. Ordonez, and M. Dessouky, "A Modeling Framework for Facility Location of Medical Services for Large-Scale Emergencies", IIE Transactions, Vol. 39, Issue. 1, pp. 41-55, 2007.

상세보기
H. K. Smith, G. Laporte, and P. R. Harper, "Locational Analysis: Highlights of Growth to Maturity", Journal of the Operational Research Society, Vol. 60, Supplement 1, pp. s140-s148, 2009.

상세보기
L. Caccetta and M. Dzator, "Heuristic Methods for Locating Emergency Facilities", Annual Conference of Economists ACE07, The Economic Society of Australia, 2007.
D. Serra, C. Revelle, and K. Rosing, "Surviving in a Competitive Spatial Market: The Threshold Capture Model", Journal of Regional Science, Vol. 39, Issue. 4, pp. 637-650, 1999.

상세보기
D. Serra, and C. Revelle, "Market Capture by Two Competitors: The Pre-Emptive Location Problem", Economics Working Paper 39, Dept. of Economics and Business, Universitat Pompeu Fabra, 1993.
D. Serra, and C. Revelle, "Competitive Location in Discrete Space", Economics Working Paper 96, Dept. of Economics and Business, Universitat Pompeu Fabra, 1994.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증

p-시설물 위치선정 모델
p-Facility Location Models 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

제안 방법

성능/효과

질의응답

참고문헌 (7)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

p-시설물 위치선정 모델 p-Facility Location Models 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

성능/효과

질의응답

참고문헌 (7)

이 논문을 인용한 문헌

저자의 다른 논문 :

최명복 (37) 이상운 (199) 한태용 (4)

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

p-시설물 위치선정 모델
p-Facility Location Models 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper