[논문]랜덤형 2차원 할당문제의 최소 거리-최대 물동량 배정 알고리즘

이상운

doi:10.7236/jiibc.2018.18.3.201

랜덤형 2차원 할당문제의 최소 거리-최대 물동량 배정 알고리즘
The Min-Distance Max-Quantity Assignment Algorithm for Random Type Quadratic Assignment Problem 원문보기

The journal of the institute of internet, broadcasting and communication : JIIBC, v.18 no.3, 2018년, pp.201 - 207

초록
AI-Helper

2차원 할당 문제는 다항시간 알고리즘이 알려지지 않은 NP-완전 문제이다. 본 논문은 위치간 거리가 일정하지 않은 랜덤형 2차원 할당 문제의 최적 해를 $O(n^2)$ 수행 복잡도로 찾을 수 있는 알고리즘을 제안하였다. 제안된 알고리즘은 단순히 거리 합을 오름차순으로, 물동량 합을 내림차순으로 정렬하여 1:1 매치시킨 최소 거리 위치에 최대 물동량 시설을 배정하는 전략을 수행하고, 위치별 거리와 시설별 물동량 상관관계를 최적으로 반영하기 위해 시설들을 교환하는 전략을 적용하였다. 실험 데이터에 적용한 결과, 제안 알고리즘은 $O(n^2)$의 다항시간 알고리즘임에도 불구하고 메타휴리스틱 방법의 일종인 유전자 알고리즘의 해를 개선할 수 있었다.

Abstract ▼ AI-Helper

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(n^2)$. 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(n^2)$ polynomial time algorithm, can be improve the solution than genetic algorithm a kind of metaheuristic method.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

단지, 우리는 주어진 위치 행렬 L의 각 위치별 타 위치들과의 거리 합과 시설 행렬 F의 각 시설별 타 시설들과의 물동량 합은 알 수 있다. 따라서 본 장에서는 이러한 거리 합과 물동량 합의 사전 정보를 활용하는 전략을 제안한다.
본 논문은 랜덤형 QAP(RQAP)에 한정된 알고리즘을 제안한다. 2장에서는 QAP의 형태를 고찰하고, Lee^[10]의 RQAP에 대한 최대흐름-최소거리 정렬 역-점수화 매칭 방법을 고찰한다.
본 논문은 지금까지 다항시간으로 해를 구하는 알고리즘이 알려져 있지 않은 RQAP에 대해 O(n²)의 다항시간 알고리즘을 제안하였다.

가설 설정

Lee[10]의 RSMA는 주어진 QAP의 거리행렬을 거리 오름차순으로, 흐름량 행렬의 용량을 내림차순으로 정렬한다. 두 번째로, 거리행렬의 {l_i,l_j}와 흐름량 행렬의 {f_k,f_l}가 일치하면 (l_i,f_k), (l_j,f_l)로 배정한다. 만약, 다르면 최적의 위치로 배정한다.

제안 방법

)인 다항시간 알고리즘임에도 불구하고, FL-QAP(1)과 FL- QAP(3)에 대해서는 메타휴리스틱 방법의 일종인 유전자 알고리즘의 해를 개선하는 효과를 얻었다. 또한 RSMA와 동일한 결과를 얻었지만 RSMA의 최적의 매칭 어려움을 해결할 수 있는 단일화된 규칙을 제시하였다.
이러한 문제점을 해결하기 위해 본 논문에서는 RSMA와 동일하게 최소 거리(거리 오름차순 정렬)-최대 물동량(물동량 내림차순 정렬) 순서에 대해 초기 실현 가능 해로 1:1로 매칭시키는 과정을 동일하게 수행하였다. 본 논문에서 제안된 알고리즘과 RSMA의 차별성은 본 논문에서는 초기 실현 가능해에 대해 비용을 감소시킬 수 있는 시설을 상호 교환하는 규칙을 적용하여 항상 동일한 최적 해의 결과를 얻을 수 있는 방법을 제안하였다는 점이다.
본 장에서는 그림 9의 n=9 FL-QAP(3) 시설 배정 문제와 n=19 FL-QAP(4) 병원 배정 문제에 대해 제안된 CA의 적용성을 평가해 본다.
)의 다항시간으로 해를 구하는 Lee[10]의 RSMA는 거리와 물동량을 1:1로 매칭시키는 유일한 규칙을 갖고 있지 않아 최적의 매칭을 시키지 못할 수도 있는 단점을 갖고 있었다. 이러한 문제점을 해결하기 위해 본 논문에서는 RSMA와 동일하게 최소 거리(거리 오름차순 정렬)-최대 물동량(물동량 내림차순 정렬) 순서에 대해 초기 실현 가능 해로 1:1로 매칭시키는 과정을 동일하게 수행하였다. 본 논문에서 제안된 알고리즘과 RSMA의 차별성은 본 논문에서는 초기 실현 가능해에 대해 비용을 감소시킬 수 있는 시설을 상호 교환하는 규칙을 적용하여 항상 동일한 최적 해의 결과를 얻을 수 있는 방법을 제안하였다는 점이다.
제안 알고리즘은 위치 행렬 L의 각 위치의 거리 합을 오름차순으로 정렬하고, 시설 행렬 F의 각 시설별 물동량 합을 내림차순으로 정렬하여 1:1로 매치시켜 초기 해를 구한다.

성능/효과

결국, 본 논문은 NP-완전인 RQAP에 대해 RSMA에 비해 보다 다항시간 알고리즘 존재 가능성을 높일 수 있는 알고리즘이 존재함을 보였다.
본 논문에서 거론된 4개 데이터에 대해 기존에 알려진 최적해와 CA를 비교한 결과는 표 1에 제시되어 있다. 제안된 CA는 단지 2와 3-opt만을 수행하는 O(n²)의 수행복잡도를 갖는 다항시간 알고리즘임에도 불구하고, 4개의 실험 데이터 모두에서 메타휴리스틱 방법의 일종인 유전자 알고리즘에 비해 최적 해를 찾았음을 알 수 있다.
제안된 알고리즘은 수행 복잡도가 O(n²)인 다항시간 알고리즘임에도 불구하고, FL-QAP(1)과 FL- QAP(3)에 대해서는 메타휴리스틱 방법의 일종인 유전자 알고리즘의 해를 개선하는 효과를 얻었다. 또한 RSMA와 동일한 결과를 얻었지만 RSMA의 최적의 매칭 어려움을 해결할 수 있는 단일화된 규칙을 제시하였다.

질의응답

핵심어	질문	논문에서 추출한 답변
	2차원 할당문제(quadratic assignment problem, QAP)란 무엇인가?	2차원 할당문제(quadratic assignment problem, QAP)는 n개 위치(locations, li, i=1, 2, ⋯, n)에 n개 시설(facilities, fj, j=1, 2, ⋯, n)을 배치하는 문제로, 위치 간 n×n 거리 행렬 L과 시설 간 n×n 물동량 행렬 F에 대해 운송비용을 최소화하도록 fj를 li에 1:1로 배정하는문제이다[1].
	할당 문제(AP)는 어떻게 분류할 수 있나?	할당 문제(AP)는 그림 1과 같이 1차원과 2차원으로 분류된다. 1차원 할당 문제는 Kn,n의 완전 이분 그래프로 형태로 작업이 기계에서 소요되는 단방향 시간에 대해 작업과 기계 측면의 양측-최적화를 수행하는 형태로 볼수 있다.
	할당 문제(AP) 중 2차원 할당 문제는 어떤 문제로 분류되나?	일반적인 할당문제(assignment problem, AP)는 1차원 할당 문제로 i행과 j열의 1차원의 양측-최적화만을 수행해야 하지만, QAP는 2개의 행렬에 대해 4차원의 4측-최적화를 수행해야 하는 극도로 어려운 문제로 현재까지 다항시간으로 풀 수 있는 알고리즘이 알려져 있지않아 NP-완전(NP-complete) 문제로 분류되고 있다[1]. 일반적으로, QAP는 n!개의 가능한 할당 경우수가 존재한다.

참고문헌 (18)

E. M. Loiola, N. M. M. Abreu, P. O. Boaventura-Netto, P. Hahn, and T. Querido, "A Survey for the Quadratic Assignment Problem," European Journal of Operational Research, Vol. 176, No. 2, pp. 657-690, Jan. 2007. doi:10. 1016/j.ejor.2005.09.032

상세보기
P. Ji, Y. Wu, and H. Liu, "A Solution Method for the Quadratic Assignment Problem (QAP)," The 6th International Symposium on Operations Research and Its Applications (ISORA), Xinjiang, China, pp. 106-117, 2006.
M. Solimanpur and A. Jafari, "Optimal Solution for the Two-dimensional Facility Layout Problem using a Branch-and-bound Algorithm," Journal of Computers and Industrial Engineering, Vol. 55, No. 3, pp. 606-619, Oct. 2008. doi:10.1016/j.cie. 008.01.018

상세보기
I. Mihajlovic, Z. Zivkovic, N. Strbac, D. Zivkovic, and A. Jovanovic, "Using Genetic Algorithms to Resolve Facility Layout Problem," Serbian Journal of Management, Vol. 2, No. 1, pp. 35-46, Jan. 2007.
S. U. Lee, "A Reverse-Delete Algorithm for Assignment Problems," Journal of KIIT, Vol. 10, No. 8, pp. 117-126, Aug. 2012. uci:G704-001947.2012.10.8.007
S. U. Lee, "Assignment Problem Algorithm Using Dual-path Competition Method," Journal of KIIT, Vol. 13, No. 12, pp. 75-83, Dec. 2015. doi:10. 4801/jkiit.2015.13.12.75
L. Steinberg, "The Backboard Wiring Problem: A Placement Algorithm," SIAM Review, Vol. 3, pp. 37-50, Jan. 1961. doi:10.1137/1003003

상세보기
A. N. Elshafei, "Hospital Layout as a Quadratic Assignment Problem," Operations Research Quarterly, Vol. 28, No. 1, pp. 167-179, Mar. 1977.

상세보기
S. U. Lee, "The Grid Type Quadratic Assignment Problem Algorithm," Journal of KSCI, Vol. 19, No. 4, pp. 91-99, Apr. 2014. doi:/10.9708/jksci.2014.19.4.091
S. U. Lee, "The Random Type Quadratic Assignment Problem Algorithm," Journal of KSCI, Vol. 21, No. 4, pp. 81-88, Apr. 2016. doi:10. 9708/jksci.2016.21.4.081
R. E. Burkard, S. E. Karisch, and F. Rendl, "QAPLIB-A Quadratic Assignment Problem Library," Journal of Global Optimization, Vol. 10, No. 4, pp. 391-403, Jun. 1997. doi:10.1023/A:1008293323270
S. Tsutsui and N. Fujimoto, "Solving Quadratic Assignment Problems by Genetic Algorithms with GPU Computation: a Case Study," Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference, pp. 2523-2530, Jul. 2009. doi:10.1145/1570256.1570355
P. A. Jensen and J. F. Bard, "Operations Research Models and Methods, Section 7.4 Facility Location Problem," John Wiley and Sons. 2003. ISBN:0-471-38004-0
K. C. Chan and H. Tansri, "A Study of Genetic Crossover Operations on the Facilities Layout Problem," Computers and Industrial Engineering, Vol. 26, No. 3, pp. 537-550, Jul. 1994. doi: 10.1016/0360-8352(94)90049-3

상세보기
K. L. Mak, Y. S. Wong, and F. T. S. Chan, "A Genetic Algorithm for Facility Layout Problems," Computer Integrated Manufacturing Systems, Vol. 11, No. 1-2, pp. 113-127, Sep. 1998. doi:10. 1016/S0951-5240(98)00018-4

상세보기
M. A. El-Baz, "A Genetic Algorithm for Facility Layout Problems of Different Manufacturing Environments," Computers & Industrial Engineering, Vol. 47, No. 2-3, pp. 233-246, Nov. 2004. doi:10.1016/j.cie.2004.07.001

상세보기
S. Jannat, A. A. Khaled, and S. K. Paul, "Optimal Solution for Multi-Objective Facility Layout Problem Using Genetic Algorithm," International Conference on Industrial Engineering and Operations Management, Dhaka, Bangladesh, Jan. 2010.
M. G. Misola and B. B. Navarro, "Optimal Facility Layout Problem Solution Using Genetic Algorithm," World Academy of Science, Engineering and Technology, Vol. 7, No. 8, pp. 545-550, Aug. 2013. doi:scholar.waset.org/1307-6892/16153

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증