The objective of this study is to broaden the applicability of the uncapacitated facility location problem to real-world problems, by developing efficient solution methods for it and providing a way to use the model of this problem for a more realistic location problem. For this purpose, two approaches for obtaining strong lower bounds are developed, both of which have not been tested for the problem yet. In addition, we show that the model of the uncapacitated facility location problem can be used without modification for dealing with a more realistic stochastic problem.
First, we introduce a conceptually new method of generating strong cuts for the problem. Based on its special structure, we generate inequalities which even cut off part of the integer feasible region but still provide valid and sharp lower bounds of the problem when added to its linear programming relaxation. Also shown is the relation between such inequalities and the conventional valid inequalities of the problem.
Secondly, we present an algorithm of incorporating valid inequalities for solving the problem which can minimize the computational difficulties involved when implementing such inequalities. Heuristics of identifying the violated valid inequalities and solving the successive linear programming relaxation augmented with the inequalities will be developed. The efficiency of the proposed algorithm is analyzed through computing experiments with a number of sample problems.
Thirdly, an alternative way of obtaining strong lower bounds for the problem is developed by using the so-called 'penalty' concept developed in integer programming. Unlike the traditional way of calculating penalties, we present a method which can take advantage of structural properties of the problem. The proposed algorithm will also be tested by solving some test problems.
Finally, we present an alternative formulation of the deterministic location model which Tcha and Yoon have recently developed to approximate the stochastic uncapacitated facility location problem. The model, besides being more compact and easier to handle than their model, has the distinct advantage of having a tighter linear programming relaxation. Also suggested is how the new formulation can be implemented in Van Roy's Cross Decomposition method for solving a more general stochastic capacitated problem.
교통 및 통신시스템 등과 같은 대규모 시스템에서의 설비입지 선정문제는 그 현실적 요구에 의해 경영과학 분야의 가장 중요한 문제 중 하나로서 인식되어 왔다. 이러한 설비입지 선정문제 중에서도 특히 공급능력에 제한이 없는 설비입지 선정문제(Uncapacitated Facility Location Problem)는 현실문제에의 광범위한 응용 가능성과 0-1 혼합형 정수계획 문제로서의 이론적 중요성 때문에 그 동안 많은 연구가 이루어져 왔다.
본 연구의 목적은 공급능력에 제한이 없는 설비입지 선정문제의 응용 가능성을 더욱 넓히기 위하여 이 문제에 대한 효율적인 해법을 개발하고 더욱 현실적인 문제에의 응용 가능성을 도모하는데 있다. 우선 효율적인 해법 개발을 위한 노력으로 최근에 0-1 정수계획 문제에서의 새로운 접근방법인 대상문제의 실행가능영역(Feasible Region)의 표면구조(Facial Structure)를 이용하는 방법과 다른 0-1 정수문제에 많이 적용되어 왔던 penalty의 이용방법 등을 고려하였다. 그리고 대상문제의 모형이 간단한 변형을 통하여 더욱 현실적인 문제인 확률적인 수요하에서의 설비입지 선정문제를 다루는 데 사용될 수 있음을 보임으로써 이 문제의 응용 가능성을 더욱 넓힐 수 있도록 하였다.
본 연구에서 고려한 내용은 다음과 같이 요약할 수 있다.
첫째, 기존에 연구되어 온 대상문제의 표면구조를 이용하여 도출하던 유효부등식(Valid Inequality)의 개념을 더욱 확장하여 더 효율적인 부등식을 도출하는 방법을 제시하였다. 즉 대상문제의 특수구조를 이용하여 실행가능영역의 일부를 제거하면서도 원 문제에 계속 유효한 형태의 부등식을 도출하고 새로 도출된 부등식과 기존의 유효부등식의 관계를 설명하였다.
둘째, 기존에 이론적 연구에만 그쳤던 대상문제의 유효부등식을 실제 해법에 적용할 수 있는 방법을 제시하였다. 여타 0-1 정수 계획 문제에서의 성공사례에도 불구하고 본 연구의 대상문제에는 유효부등식이 적용되지 못하였는데, 본 연구에서는 원문제의 쌍대 구조를 이용한 휴리스틱을 개발함으로써 이를 가능케 하였다. 특히 이러한 접근방법이 성공적이었음이 개발된 해법의 효율성 test를 통해 입증되었다.
세째, 이제까지 많은 0-1 정수계획문제에 성공적으로 이용되어 왔으나 본 연구의 대상문제의 특수한 구조 때문에 적용할 수 없었던 또하나의 기법인 penalty를 이용하는 방법을 제시하였다. 이에 대하여서도 역시 기존 접근방법과는 달리 쌍대구조를 이용하여 penalty를 계산하는 효율적인 해법을 개발하였으며, 이의 효율성을 실제 test를 통하여 입증하였다.
마지막으로, 본 대상문제의 기본모형이 그 단순성에도 불구하고 더욱 현실적인 문제를 푸는데 이용될 수 있음을 보였다. 즉 최근에 확률적 수요하에서의 설비입지 선정문제를 확정적 모형으로 변형한 Tcha 와 Yoon의 모형이 본 연구의 대상문제로 다시 변형될 수 있음을 보이고, 새로이 변형된 모형이 그들의 모형보다 간단하면서도 선형계획으로 완화될 때 개선된 하한값을 제공하는 잇점이 있음을 제시하였다.
