The purpose of this is to develop efficient computational approaches for solving the facility location problems which encompass the implications of salient aspects of distribution systems - two-level facility location, multicommodity and multiperiod.
First, a branch and bound algorithm is developed to solve a two-level facility location problem which may be also viewed as a generalized formulation of a multicommodity facility location problem. The algorithm is made efficient by employing a series of devices which exploit the supermodularity of the objective function. The efficiency of the algorithm is analyzed through computational experiments with some test problems.
Secondly, a new dual-based solution procedure for the static facility location problem is proposed. Based upon the existing dual-based approach, the procedure is devised with the emphasis on the solution quality at the marginal increase of computational load. Its wide applicability to other location problems is briefly discussed.
Finally, this dual-based approach is generalized to a dynamic context to solve a dynamic facility location problem. This generalization is based upon the fact that the dynamic facility location problem can be viewed as a special case of the static problem. Computational experience with static as well as dynamic test problems shows that the proposed dual-based procedure appears to be an attractive heuristic, given its empirical performance and its reasonable computational requirements.
경제현상의 질적, 양적 팽창에 따라 기업의 제품수송체계 또한 규모의 확장 및 다양화가 이루어져 왔다. 이에 따라 보다 효율적인 수송체계 운영이 절실히 요망되어 과거 20여년간 이에 대한 연구가 꾸준히 진행되어 왔다. 그러나 이들 대부분의 연구들이 실제 수송체계를 너무 간략화한 모형을 중심으로 이루어져 왔기 때문에 이의 실제적용에는 많은 어려움이 있었다. 이에 본 연구는 실제 수송체계의 중요한 요인들을 반영한 모형들을 정립하고 이의 효율적인 algorithm을 개발함으로서 보다 효율적인 수송체계 설계 및 운영을 위한 분석도구를 제시하고자 한다.
기존의 대다수 연구들이 소홀히 한 수송체계 요인중 실제 수송체 계의 분석에서 생략되어서는 안될 요인은 다음과 같다.
1) 이단계 설비입지
2) 동적 양태
본 연구에서는 이들 두 요인을 고려한 설비입지 선정문제들을 다루기로 한다. 이 두가지 외에 다제품 요인 또한 중요한 것이나 다제품 설비입지 선정모형은 이단계 설비입지 선정모형의 한 특수한 형태로 볼 수 있기 때문에 본 연구에서는 별도로 고려하지 않았다.
본 연구에서는
첫째, 실제 제품수송체계는 이단계로 즉 공장에서 창고, 창고에서 수요자로, 이루어지므로 이를 반영하기 위해 공장 및 창고의 입지 선정이 동시에 고려되는 모형을 정립하였다. 특히 이 경우 공장 및 창고의 상호 종속적인 관계가 내포되어 있는 경우가 많으므로 이를 표현하기 위한 부가제약조건을 모형에 포함시켰다. 이러한 부가제약조건은 또한 다제품 설비입지 선정모형이 본 모형의 한 특수한 형태가 되도록 하는 중요한 역할을 하였다. 본 연구에서는 이 문제의 해법으로서, 모형의 목적함수의 성질, supermodularity, 를 이용하여 개발한 여러가지 기법을 포괄한 branch and bound algorithm을 개발하였다. 이 algorithm의 효율성은 다수의 예제를 통하여 충분히 입증되었다.
둘째, 기존의 dual-based approach를 근간으로 하여, 계산절차는 약간 더 복잡하나 보다 좋은 해를 구할 수 있는 새로운 dualbased solution procedure를 개발하였다. 이 procedure는 두개의 subprocedure들로 구성되어 있다. 첫째는 dual ascent procedure로서 대상문제의 relaxed LP의 dual solution을 효과적으로 구하는 절차이고 둘째는 primal procedure로서 앞에서 구한 dualsolution으로부터 하나의 primal feasible solution을 구하는 절차이다. 이 새로운 approach는 기존의 approach들이 적용가능한 모든 문제에 역시 적용가능하나 우선 가장 간단한 UncapacitatedFacility Location Problem에 대하여 전개하고 이를 다음에 다룰동적 모형에서 일반화시키기로 한다.
다음으로 다룰 문제는 수송체계가 시간이 경과함에 따라 제품수요 및 생산비용이 급격히 변하는 경우에 꼭 고려해야 할 동적요인을 포함시킨 동적 설비입지 선정문제이다. 그런데 이 모형은 정적모형의 한 특수한 형태로 볼 수 있기 때문에, 이 모형의 해법으로서 앞에서 전개한 dual-based procedure에 약간의 수정을 가하여 개발할 수 있었다. 개발된 해법의 효율성을 동적 문제의 예제뿐만 아니라 정적문제의 예제들을 통하여 평가하여 보았다. 특히 Roodman-Schwarz의 greedy heuristic과 기존의 dualbased approach의 계산결과와 비교하여 본 결과 본 해법이 매우 효율적이라는 사실이 입증되었다.
결과적으로 본 연구에서 제시한 모형은 실제 수송체계의 중요한 요인들을 적절히 반영시켰을 뿐만 아니라 각 모형에 대한 효율적 algorithm은 이러한 모형들에 대한 다각적 분석을 용이하게 한다고 볼 수 있다.
