공급 제약이 있는 시설물 위치 선정 문제의 분지평가법을 이용한 유도 탐색 해법

Abstract

공급 제약이 있는 위치 선정 문제는 잘 알려진 조합 최적화 문제로써 제조, 배당 문제에 많이 사용되고 있다. 이 문제는 시설물 설치 가능 지역 중 어느 곳에 시설물을 설치하고 어떻게 물품을 제공해야 고객의 수요를 만족시키며 설치 비용과 운송 비용의 합을 최소화 시킬 수 있는 지에 관한 문제이다. 현재도 시설물 위치 선정 문제에 대한 많은 휴리스틱과 최적 해법이 연구, 개발되고 있다. 본 논문에서는 시설물 위치 선정 문제에 대해 분지평가법을 이용한 유도 탐색 해법을 제시한다. 또한 성능 평가를 위해 다른 논문에서 사용되었던 자료를 CPLEX 와 비교한다. 그 결과 자동적인 Cut 을 제외한 CPLEX 보다 더 우수한 성능을 나타내었으며 크기가 큰 문제에 대해서 휴리스틱을 제외한 CPLEX 보다 비교적 뛰어난 결과를 얻을 수 있었다.