The capacitated facility location problem(CFLP) is a well-known combinatorial optimization problem with applications in production and allocation planning. It consists of selecting facility locations from potential candidate locations while satisfying customers’ demands in such a way that minimizes the sum of facility set-up costs and transportation costs. A number of methods such as heuristics and exact algorithms have been proposed for this problem.
In this thesis, we propose a branch and price guided search(BPGS) to solve the CFLP. The performance of the BPGS is compared with CPLEX for some benchmark data. It is observed that BPGS outperforms the CPLEX when automatical cut generation for CPLEX is not used.
공급 제약이 있는 위치 선정 문제는 잘 알려진 조합 최적화 문제로써 제조, 배당 문제에 많이 사용되고 있다. 이 문제는 시설물 설치 가능 지역 중 어느 곳에 시설물을 설치하고 어떻게 물품을 제공해야 고객의 수요를 만족시키며 설치 비용과 운송 비용의 합을 최소화 시킬 수 있는 지에 관한 문제이다. 현재도 시설물 위치 선정 문제에 대한 많은 휴리스틱과 최적 해법이 연구, 개발되고 있다.
본 논문에서는 시설물 위치 선정 문제에 대해 분지평가법을 이용한 유도 탐색 해법을 제시한다. 또한 성능 평가를 위해 다른 논문에서 사용되었던 자료를 CPLEX 와 비교한다. 그 결과 자동적인 Cut 을 제외한 CPLEX 보다 더 우수한 성능을 나타내었으며 크기가 큰 문제에 대해서 휴리스틱을 제외한 CPLEX 보다 비교적 뛰어난 결과를 얻을 수 있었다.
