Consider a capacitated facility location problem in which each customer is assumed to have a uniform demand, and each facility capacity has to be chosen from the given set of admissible levels. Under the restriction that each customer's uniform demand be met by exactly one facility, the objective is to select a set of facilities to open, along with their capacities, and to assign customer's demand to them so as to minimize the total cost which includes fixed costs of opening facilities as well as variable assignment costs. The problem is modelled as a pure zero-one program which extends the scope of applicability significantly over that by conventional location models. The purpose of this study is to develop efficient computational procedures for solving the pure zero-one facility location problems with the fixed uniform facility capacity, the fixed facility capacity, and the multiple facility capacity. Due to the special structure of our zero-one location problem with a uniform demand, it can be converted to a location problem with unimodular property.
First, a Lagrangean relaxation algorithm is developed to solve the pure zero-one location problem with the fixed uniform facility capacity. The problem may be viewed as a variant of well-known capacitated facility location problems. The algorithm is made efficient by employing a device which exploits the special structure of a surrogate constraint. The efficiency of the algorithm is analyzed through computational experiments with some test problems.
Secondly, we give a solution method for the zero-one location problem with the fixed facility capacity based on Cross Decomposition developed by Van Roy. Solution methods to derived sub and master problems in a branch and bound scheme are discussed, and their computational results are given for a number of test problems. We also compare the efficiency of the method with other methods suggested for the fixed uniform capacity case.
Finally, we present an implementation of the Cross Decomposition procedure to solve the pure zero-one facility location problem wherein facility capacities can be chosen from a set of predetermined levels. Exploiting the special primal and dual structure of the problem, we have proposed a branch and bound procedure. Computational experiments with a randomly generated set of test problems have been conducted. The results were fairly satisfactory considering the complexity of the problem.
산업의 발전, 국제화 및 다양화에 따라 제품, 용역 및 정보 등의 분배체계에 대한 연구가 최근 활발히 전개되어 왔다. 즉 분배체계의 중요설비인 공장, 창고, 레이더 기타, 컴퓨터 센터 등의 입지 및 규모의 개정을 어떻게 하면 가장 경제적으로 결정할 것인가에 대한 수리적인 기법이 다양하게 제시된 것이다. 그러나 기존 연구들이 분배체계의 행태중에서 중요한 실제적인 사항을 간과한 것이 대부분이었으므로 본연구에서는 실제의 분배체계의 행태를 고려한 모형을 정립하고 이의효율적인 해법을 계발함으로서 보다 현실적이며 효과적인 분배체계 설계의 기본도구를 제공하고자 하는 것이 그 목적이다.
기존의 설비입지선정 모형을 분석한 바에 의하면 대부분 다음의 두가지의 중요한 현실적인 면을 무시하였거나 고려하였더라도 효율적인 해법을 제시하지 못하였다.
1) 복수설비용량 (Multiple Facility Capacities)
일반적으로 설비는 다종의 형태 및 용량을 가질 수 있으며 이는보다 실제의 분배시스템을 잘 표현하고 있는 것이다. 이같이 현실적으로 중요성이 있음에도 불구하고 이를 고려하면 문제의 구조상 풀기 어려운 형태가 되므로 기존의 연구에서는 소홀히 취급되어 왔으며 취급하였더라도 모형의 소개 및 발견적 (Heuristic) 해법의 제시에 그치고 있다.
2) 단일배정 구조 (The Single Assignment Structure)
단일배정 구조를 갖는 설비입지선정이란 어떤 한 사용자의 수요는 반드시 하나의 설비에 의해서만 충족되어야 한다는 것으로서 과업을 기계 또는 부서에 해당하는 경우, 컴퓨터 터미널을 Concentrator에 연결시키는 경우 및 특정 상품을 하나의 공장에서 공급 받는 경우 등이있다. 이는 실제의 설비구조를 고려한 것으로서 그 가치가 인정되는 반면에 이와같이 단일배정구조로 정식화 할 경우 0-1 정산계획모형이되어 복수배정 (Multiple Assignment) 이 허용되는 모형보다 수리적으로 그의 해법계발이 어려워지는 난점이 있다. 즉 설치해야할 설비의 장소와 그 수가 정해 있다 하더라도 사용자를 설비에 배정시키는 문제자체가 일반화된 해당문제 (Generalized Assignment Problem) 의 특수한 경우로 풀기 어려운 문제의 하나가 되는 것이다.
상기의 실제적인 면을 고려한 일반적인 모형은 그 구조상 매우난해하므로 본 연구에서는 균일수요를 갖는 단일배정 제약하에 설비입지선정 모형을 정립하고 단일배정 구조를 이용하여 모형을 변환하여 다루었다.
첫째로, 단일배정 제약하의 균일용량 설비입지선정 모형에 대하여 Lagrangean Relaxation (LR) 기법을 이용한 해법을 제시하였으며 특히 본해법에서는 Surrogate Constraint를 도입함으로써 큰 효과를 나타내고 있다. 또한 개발된 해법의 효율성을 분석평가하기 위하여 다수의 예제를 통하여 검증한 바 기존의 타 연구보다 평균적으로 좋은 결과를 보이고 있다.
둘째로, 단일배정 제약하의 단일용량 설비입지 선정 모형에 대하여 Cross Decomposition(CD) 과 Branch and Bound (B\&B) 기법을 사용하여 최적해를 구하는 해법을 제시하였으며 예문을 통하여 분석한 바 기존의 타 연구 및 앞에서 제시한 LR해법보다 더 효율적인 것으로 평가되었다.
세째로, 단일배정 제약하의 복수용량 설비입지 선정모형을 새로이 정식화하고 CD와 B\&B 기법을 활용하여 그 해법을 제시하였다. 이복수용량 문제는 기존의 연구결과 없으므로 객관적인 비교는 할수 없으나 문제의 난해성 (Complexity)에 비추어 볼 때 매우 만족할만한 결과로 평가된다.
결론적으로 본 연구는 실제적인 분배체계를 잘 반영한 복수용량모형의 정립과 이의 효율적인 해법의 제시에 큰 의의가 있는 것으로 사료된다.
