This thesis considers a capacitated facility location problem where one wants to open or close facilities over a given time period to minimize the total cost while meeting demands of customers at various locations. This problem is called the dynamic capacitated facility location problem (DCFLP). In this paper, a hybrid ant colony algorithm (HAC) is developed to solve the DCFLP. HAC uses pheromone trail information to update current solutions.
Computational tests with randomly generated data are presented in order to evaluate the performance of the algorithm. We compare the performance of the HAC with a Tabu search approach and CPLEX. The results show that HAC can find near optimal solutions in a reasonable time.
이 논문은 주어진 다 기간 내에 용량제약이 있는 설비에 대하여 다 지역에 있는 고객들의 수요를 모두 만족하면서 총 비용은 최소화 할 수 있는 설치, 제거 운용계획을 설립하는 ‘용량제약이 있는 다기간 입지 선정문제’를 하이브리드 개미 군집 알고리즘을 적용하여 푸는 방법에 대한 연구이다. 하이브리드 개미 군집 알고리즘은 현재 해에 대한 정보를 저장하고 갱신하는 페르몬 경로 기억 행렬을 이용하는 방식으로, 본 연구에서는 이를 문제에 맞게 적절하게 수정하고 보강하여 적용하였다. 또한 기존 연구와 다르게 가장 좋은 해를 찾아가는 과정에서 비가능해가 나올 경우 이를 인접한 가능해로 전환시켜주는 기능과 현재 해를 기반으로 추가 개선 가능한 가능해를 검색하는 기능을 적용하였다. 실험을 기존 연구에서 데이터를 생성했던 규칙을 적용하여 만든 데이터와 본 연구에서 기존 규칙을 변형하여 새로 생성한 데이터를 이용하여 수행하였고 알고리즘의 성능은 기존에 타부탐색 방식, CPLEX를 이용한 최적해 방식과 비교 분석을 실시하였다. 그 결과 하이브리드 개미 군집 알고리즘이 본 문제에 대해서 기존 방식에 비해 더 빠른 시간 안에 더 최적해와 근사한 해를 구할 수 있다는 것을 확인하였다.