This thesis considers a problem of locating both distribution centers and retailers in a zone-dependent two-level distribution network where either a distribution center or a retailer should be located in each zone. Customer demands of each zone should be satisfied directly from either its own distribution center or its own retailer being supplied from a distribution center of another zone. The objective of the proposed problem is to minimize total cost being composed of distribution center/retailer setup costs and transportation costs. In the analysis, the problem is proved to be NP-hard, so that a branch-and-bound algorithm is derived for the problem. Numerical experiments show that the proposed branch-and-bound algorithm provides the optimal solution efficiently for some small problems.
본 논문에서는 구역 제약하의 두단계 설비 배치 문제를 다루었다. 고객의 위치와 수요의 양이 미리 정해져 있는 상황에 주어진 후보지 중 적합한 유통센터와 소매상을 선택하는 문제이다. 이 때 총 비용, 즉 유통센터와 소매상의 총 설치 고정비용과 유통센터와 소매상 사이의 총 운송비용의 합을 최소화 하는 해를 찾는 것이 이 논문의 목적이다. 기존의 다른 두단계 설비 배치 문제와의 차이점은 기존의 문제에 구역 제약을 추가하여 각 구역 안에 유통센터와 소매상이 적어도 하나는 설치되도록 하는 것을 기본 가정으로 한 것이다. 이 논문은 서비스 센터의 네트워크 구성, 외국과의 무역 네트워크 구성 등의 실제 사례에 적용할 수 있다.
이 문제는 NP-hard하므로 비교적 짧은 시간 안에 최적의 해를 구할 수 있는 분지한계법(Branch-and-bound Algorithm)이 제안되었고, 알고리즘의 효율을 높이기 위한 Branching Rule과 Bounding Rule을 고려하였다. 그리고 알고리즘의 성능을 평가하기 위해 실험을 수행하였고, 그 결과 제안된 분지한계법이 빠른시간 안에 최적의 해를 제공하는 것을 확인할 수 있었다.
