Dynamic Mean Value Cross Decomposition Algorithm for Capacitated Facility Location Problems

Abstract

In this thesis, we propose practical algorithms for capacitated facility location problems (CFLP). Many algorithms employ the branch-and-bound technique in order to solve the CFLP.There are also some different approaches which can obtain primal solutions while exploiting the primal and dual structure simultaneously. One of them is the mean value cross decomposition (MVCD) method that ensures convergence without solving master problems. Though MVCD is an attractive method in that it can effectively provide the various information of solutions and the same bounds as those of the Lagrangian relaxation, it has not been widely applied to other problems except UFLP, due to the fact that the performance is highly dependent on the structure of the problem.We propose two approaches in order to apply MVCD for CFLP practically. One is a heuristic method to search better feasible solutions based on the MVCD framework, keeping the Lagrangian relaxation with the integrality property. It is named as the adaptive mean value cross decomposition algorithm (AMVCD) and focuses on the efficiency of the algorithm. The other is the dynamic mean value cross decomposition algorithm (DMVCD), which produces the tighter bound than Lagrangian relaxation by using the cutting plane methods in spite of having no integrality property. It is designed to guarantee the tighter bound than that of existing MVCD.Finally, computational results of various instances are also reported to verify effectiveness and efficiency of the AMVCD and DMVCD.설비입지결정문제(Facility Location Problem)는 여러 공급지에서 여러 수요지로 제품을 공급할 때 제품생산을 위한 설비에 투자하는 고정비와 제품의 수송비용을 최소로 할 수 있는 설비의 입지를 결정하는 최적화 문제이다.설비입지결정문제는 유통 및 물류, 통신 등에 응용되며 글로벌 시대의 도래와 함께 기업의 활동 범위가 세계로 확장됨에 따라기업의 중요한 의사결정문제로 대두되고 있다. 이러한 설비입지결정문제는 제한용량이 없는 설비입지결정문제(UFLP : Uncapacitated Facility Location Problem)와 제한용량이 있는 설비입지결정문제(CFLP : Capacitated Facility Location Problem)로 분류할 수 있으며 일반적인 해법으로는 풀기 어려운 NP-hard 문제 유형의 조합최적화문제로 알려져있다. 또한 이 중 제한용량이 있는 설비입지결정문제가 보다 현실을 잘 반영하는 문제로 최근까지도 그 해법에 대한 연구가 활발히 진행되고 있다.제한용량이 있는 설비입지결정문제를 푸는 대부분의 해법들은 라그랑쥐 이완(Lagrangian relaxation) 및 분할 기법 decomposition technique)을 기반으로한 분지한계법(branch-and-bound)과 발견적해법(Heuristics)을 이용하고 있으며 이러한 해법들은 한계값(bound)을 향상시키고 이러한 한계값으로부터 최적해에 가까운 가능해를 구하는데 초점을 맞추고 있다. 이와 유사한 맥락으로 절단평면법(cutting plane methods)은 최적해를 얻기위해 유효부등식(valid inequality)을연속적으로 추가하여 한계값을 향상시킨다. 또한 이러한 유효부등식을 생성하기 위한 제한용량이 있는 설비입지결정문제의 다면체구조(polyhedral structure)에 대한 연구를 바탕으로제한용량이 있는 설비입지결정문제에 대한 분지절단법(branch-and-cut) 기반의 알고리즘이 개발되었다. 이러한 연구들 대부분 원시문제나 쌍대문제의 단일 구조만을 이용하고 있는데 반해 원시문제와 쌍대문제를 동시에 이용하는 접근법으로 교차분할법(cross decomposition)과 평균치교차분할법(mean value cross decomposition)이 있다.이러한 접근법은 Benders 분할법과 라그랑쥐 이완법을 하나의 체계(framework)로 통합하여 하한값(lower bound)과 상한값(upper bound)를 동시에 제공하고 가능해를 회복할 수 있는 다양한 정보까지도 생성한다. 하지만 교차분할법은 수렴성에 따라 복잡한 마스터문제를 계속적으로 풀어주어 하며이에 비해 단순한 계산절차로 이루어진 평균치교차분할법도 성능이 문제의 구조에 따라 제한되기 때문에 기존에 제한용량이 없는 설비입지결정문제에만 적용되었고 적용범위가 더이상 확장되지 못하고 있다.본 연구에서는 제한용량이 있는 설비입지결정문제를 실질적으로 풀기 위해 평균치교차분할법의 장점을 최대한 유지하면서 한계점을 극복할 수 있는 평균치교차분할법 기반의 두가지 알고리즘을 제안한다. 하나는 평균치교차분할법 기반에서 좋은 가능해를 효율적으로 찾을 수 있는 발견적 해법인 적응형평균치교차분할법(adaptive mean value cross decomposition)이며 또 다른 하나는 절단평면법과 결합하여 라그랑쥐 이완법이나 평균치교차분할법보다 좋은 하한값을 제공하여 쌍대차이(duality gap)를 줄일 수 있도록 고안된 동적평균치교차분할법(dynamic mean value cross decomposition)이다.이를 위해 풀기 쉬운 구조를 생성할 수 있는 라그랑쥐 이완 기법과 평균치교차분할법보다 좋은 하한값을 보장하기 위해 유효부등식을 선택하고 추가하는 전략을 제안하며 수렴속도를 향상시키기 위해 초기해를 제거시키는 방법을 소개한다. 마지막으로 제한용량이 있는 설비입지결정문제의 유형 및 규모에 따라 생성된 다양한 문제에 대한 실험결과를 제시함으로써 제안 알고리즘의 효과성과 효율성을 입증한다.