This thesis considers the parametric uncapacitated facility location problem. Though there has been a great deal of research on the uncapacitated facility location problem, the parametric analysis for that problem has not been studied as yet, despite the significance of the parametric analysis. For this reason, three major issues relevant to the parametric facility location problem are considered.
First, we show that the parametric right-hand side problem is transformed into a specialized version of the parametric cost problem by using the special structure of the uncapacitated facility location problem. In addition, we extract the important attributes from the special structure and demonstrate that they are well utilized for developing an efficient method for parametric analysis. The efficiency of the developed method is shown through the computational experiments with a number of sample problems including large sized ones.
Secondly, as a specialization of the parametric analysis, we observe how sensitively the optimal solution changes with respect to the changes in demand requirements and fixed costs. We also develop an efficient technique of reoptimization for the changes in the model structure.
Finally, we show that the method suggested for the parametric analysis on the parametric facility location problem can be exploited in solving the public facility location problem in which two conflicting goals exist: the preference at each demand site for maximizing the amount supplied and the authority's aspiration of expenditure minimization. By investigating how the total cost changes as the demand parameter varies continuously, we find out the best compromising tradeoff between these two conflicting goals.
설비 입지 선정 문제는 대규모의 통신 시스템과 같이 복잡하지만 현실적으로 중요한 시스템의 설계, 분석 및 최적화를 위해 많이 연구되어 왔다. 여러 가지 형태의 설비 입지 선정 문제들 가운데 특히 공급 능력에 제한이 없는 설비 입지 선정 문제 (UFLP : Uncapacitated Facility Location Problem)는 그 모형의 단순함에도 불구하고, 보다 복잡하고 현실적인 입지 선정 문제를 다루는 데 있어 기초를 제공한다는 점에서 가장 많은 관심과 연구의 대상이 되어 왔고, 앞으로도 그 문제에 대한 연구는 계속되리라 생각된다. 그러나 이와같은 많은 연구에도 불구하고, UFLP에 대한 모수 변화 분석(parametric analysis)은 거의 다루어지지 않았다. 일반적인 수리계획법 분야에서와 마찬가지로 설비 입지 선정 문제에 대한 모수 변화 분석은 대규모의 현실 시스템에 필연적으로 수반되는 불확실성에 대처하기 위해서 반드시 수행되어져야 한다.
따라서 본 연구의 목적은 UFLP에 대한 모수 변화 분석의 효율적인 방법을 개발함으로써 설비 입지 선정 문제의 현실 응용 가능성을 더욱 높이고, 그러한 문제와 관련된 시스템의 설계와 분석에 필요한 의사결정에 많은 도움을 주고자 하는 것이다. 본 연구에서 다루어지는 내용은 다음과 같다.
첫째, 각 수요지에서의 수요량이 매개 변수의 함수로서 선형으로 증가할때, 전체 비용이 어떻게 변화하는지를 알아보는 문제를 다룬다. 이 문제는 혼합 정수계획법의 우변상수벡터에 대한 모수 변화 분석문제의 일종이다. 일반적으로 혼합 정수계획법의 우변상수에 대한 모수 변화 분석은 비용함수가 불연속하여 취급하기가 상당히 까다로운 것으로 알려져 있다. 그러나 UFLP가 갖는 특수한 구조로부터 아주 흥미로운 특성들을 발견함으로써, 이러한 특성들을 이용하여 모수 변화 분석의 효율적인 방법을 개발하였다. 일반적인 정수계획법 이나 혼합 정수계획법의 모수 변화 분석 방법에는 Additive algorithm, Branch and bound method, Cutting plane method의 3가지가 있는 데, 본 연구에서는 Marsten 과 Morin이 제시한 것과 같이 매개변수 전 구간을 대상으로 하한함수(lower bound function)와 상한함수(upper bound function)를 사용하는 Branch and bound 방법을 이용하였다. 본 연구에서는 좋은(tight) 하한함수를 쉽게 찾아내고 또한 bounding test를 간편하게 함으로써 그 효율성을 높일 수 있었고, 많은 예제에 대한 test를 통해 그 효율성을 입증하였다.
둘째, 앞서 다룬 문제의 특수한 형태로서 설비 입지 선정 문제에 대한 민감도 분석(sensitivity analysis)을 수행하였다. 현재의 최적해가 바뀌지 않고 유지되는 수요량의 변화 범위와 설비 입지의 고정비용의 변화 범위를 쉽게 찾아 내었다. 또한 새로운 수요지나 설비 입지 후보지가 시스템에 새로이 추가될 경우에 새로운 최적해를 효율적으로 찾는 방법을 제시하고, 아울러 기존의 수요지나 설비가 시스템에서 제외되는 경우도 역시 고려해 보았다.
마지막으로 공공 서비스 시스템과 관련된 공공 설비 입지 선정 문제 (Public Facility Location Problem)를 푸는 데 모수 변화 분석 방법이 잘 이용될 수 있음을 보였다. 이 문제에는 각 수요지는 가능한 한 공공 서비스를 많이 받고자 하고, 시스템 관련 당국은 예산상의 제약때문에 시스템 전체에 소요되는 예산을 가능한 한 줄이려고 하는 두 가지 상충되는 목표가 내재되어 있다. 이러한 상황은 확정적(deterministic) modelling을 불가능하게 만들어 최적 의사결정을 내리는 데 어려움을 준다. 따라서 본 연구에서는 퍼지집합이론(Fuzzy Set Theory)을 이용하여 두 가지 상충되는 목표를 수식적 model에 반영하고, 모수 변화 분석 방법을 이용하여 두 가지 목표를 공히 가능한 한 높이 달성시키는 최선의 의사 결정 대안을 찾아 낼 수 있었다.
