랜덤형 2차원 할당문제의 최소 거리-최대 물동량 점진적 증대 매칭 알고리즘 (Algorithm for the Incremental Augmenting Matching of Min-Distance Max-Quantity in Random Type Quadratic Assignment Problem)

서지정보

· 발행기관 : 한국인터넷방송통신학회
· 수록지 정보 : 한국인터넷방송통신학회 논문지 / 22권 / 3호 / 177 ~ 183페이지
· 저자명 : 이상운

초록

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

영어초록

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.

참고자료

· 없음