earticle

영어

There is no known polynomial time algorithm for QAP that is a NP-complete problem. This paper suggests O(n2) polynomial time algorithm for random type quadratic assignment problem (QAP). The proposed algorithm suggests incremental augmenting matching strategy that is to set the matching set M = {{li, fj)} from li with minimum sum of distance in location matrix L and fj with maximum sum of quantity in facility matrix F , and incremental augmenting of matching set M from M to li with minimum sum of distance and to fj with maximum sum of quantity. Finally, this algorithm performs swap strategy that is to reflect the complex correlations of distances in locations and quantities in facilities. For the experimental data, this algorithm, in spite of O(n2) polynomial time algorithm, can be improve the solution than genetic algorithm a kind of metaheuristic method.

한국어

2차원 할당 문제는 다항시간 알고리즘이 알려지지 않은 NP-완전 문제이다. 본 논문은 위치간 거리가 일정하지 않은 랜덤형 2차원 할당 문제의 최적 해를 O(n2) 수행 복잡도로 찾을 수 있는 알고리즘을 제안하였다. 제안된 알고리즘은 위치 행렬 L에서의 최소 거리 합 위치 li 와 시설 행렬 F에서의 최대 물동량 시설 fj를 M = {{li, fj)}으로 매치키시고, M을 기준으로 최소 거리 합 li 와 시설 행렬 F에서의 최대 물동량 시설 fj의 매칭 쌍 (li, fj) 을 점진적으로 증대시키는 전략을 수행하고, 위치별 거리와 시설별 물동량 상관관계를 최적으로 반영하기 위해 시설들을 교환하는 전략을 적용하였 다. 실험 데이터에 적용한 결과, 제안 알고리즘은 O(n2) 의 다항시간 알고리즘임에도 불구하고 메타휴리스틱 방법의 일 종인 유전자 알고리즘의 해를 개선할 수 있었다.