:: The Journal of the Institute of Internet, Broadcasting and Communication ::, Vol.18 No.3 | (2018) pp.201~207
랜덤형 2차원 할당문제의 최소 거리-최대 물동량 배정 알고리즘
Abstract
2차원 할당 문제는 다항시간 알고리즘이 알려지지 않은 NP-완전 문제이다. 본 논문은 위치간 거리가 일정하지 않은 랜덤형 2차원 할당 문제의 최적 해를 O(n2) 수행 복잡도로 찾을 수 있는 알고리즘을 제안하였다. 제안된 알고리즘은 단순히 거리 합을 오름차순으로, 물동량 합을 내림차순으로 정렬하여 1:1 매치시킨 최소 거리 위치에 최대 물동량 시설을 배정하는 전략을 수행하고, 위치별 거리와 시설별 물동량 상관관계를 최적으로 반영하기 위해 시설들을 교환하는 전략을 적용하였다. 실험 데이터에 적용한 결과, 제안 알고리즘은 O(n2)의 다항시간 알고리즘임에도 불구하고 메타휴리스틱 방법의 일종인 유전 자 알고리즘의 해를 개선할 수 있었다.
There is no known polynomial time algorithm for random-type quadratic assignment problem(RQAP) that is a NP-complete problem. Therefore the heuristic or meta-heuristic approach are solve the approximated solution for the RQAP within polynomial time. This paper suggests polynomial time algorithm for random type quadratic assignment problem (QAP) with time complexity of O(n2). The proposed algorithm applies one-to-one matching strategy between ascending order of sum of distance for each location and descending order of sum of quantity for each facility. Then, swap the facilities for reflect the correlation of distances of locations and quantities of 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.
Linear assignment problem,Quadratic assignment problem,Random type,Max-flow/min-distance,Concentration
