earticle

영어

This paper suggests -facility locations in candidate locations and 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 until . As a result of the proposed algorithm for the and , the initial solution is obtained. For the Swain's 55-node network, we obtain the optimal solution through a solution improvement process with and it by using the initial solution with .

한국어

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