p-시설물 위치선정 모델 (p-Facility Location Models)

서지정보

· 발행기관 : 한국인터넷방송통신학회
· 수록지 정보 : 한국인터넷방송통신학회 논문지 / 11권 / 6호 / 193 ~ 205페이지
· 저자명 : 최명복, 이상운, 김봉경, 정승삼, 한태용

초록

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

영어초록

This paper suggests p-facility locations in m candidate locations and n areas in optimal cost side(population×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×5 and 7×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 .

참고자료

· 없음