[논문]적합성 함수를 이용한 2차원 저장소 적재 문제의 휴리스틱 알고리즘

연용호; 이선영; 이종연

doi:10.3745/kipstb.2009.16b.5.403

적합성 함수를 이용한 2차원 저장소 적재 문제의 휴리스틱 알고리즘
A Heuristic Algorithm for the Two-Dimensional Bin Packing Problem Using a Fitness Function 원문보기

정보처리학회논문지. The KIPS transactions. Part B. Part B, v.16B no.5, 2009년, pp.403 - 410

연용호 (목원대학교 공학교육혁신센터) , 이선영 (충북대학교 컴퓨터교육과) , 이종연 (충북대학교 컴퓨터교육과)

초록
AI-Helper

2차원 저장소 적재는 NP-hard 문제로서 그 문제의 정확한 해를 구하는 것이 어려운 것으로 알려져 있으며, 이의 더 좋은 해를 얻기 위해 유전자(genetic) 알고리즘, 시뮬레이티드 어닐링(simulated annealing), 타부서치(tabu search)등과 같은 근사적 접근법이 제안되어 왔다. 하지만 분지한계(branch-and-bound)나 타부서치 기법들을 이용한 기존의 대표적인 근사 알고리즘들은 휴리스틱 알고리즘의 해에 기반을 둠으로 효율성이 낮고 반복수행에 의한 계산시간이 길다. 따라서 본 논문에서는 이러한 근사 알고리즘의 복잡성을 간소화하고, 알고리즘의 효율성을 높이기 위해 적재가능성을 판단하는 적합성 함수(fitness function)를 정의하고 이를 이용하여 어떤 특정 개체의 적재영역을 판단하는데 영향을 주는 적재영역의 수를 계산한다. 또한, 이들을 이용한 새로운 휴리스틱 알고리즘을 제안하였다. 끝으로 기존의 휴리스틱 또는 메타휴리스틱 기법과의 비교실험을 통해 기존의 휴리스틱 알고리즘인 FFF와 FBS에 비해 97%의 결과가 같거나 우수하였으며, 타부서치 알고리즘에 비해 86%의 결과가 같거나 우수한 것으로 나타났다.

Abstract ▼ AI-Helper

The two-dimensional bin packing problem(2D-BPP) has been known to be NP-hard, and it is difficult to solve the problem exactly. Many approximation methods, such as genetic algorithm, simulated annealing and tabu search etc, have been also proposed to gain better solutions. However, the existing approximation algorithms, such as branch-and-bound and tabu search, have shown the low efficiency and the long execution time due to a large of iterations. To solve these problems, we first define the fitness function to simplify and increase the utility of algorithm. The function decides whether an item is packed into a given area, and as an important information for a packing strategy, the number of subarea that can accommodate a given item is obtained from the variant of the fitness function. Then we present a heuristic algorithm BF for 2D bin packing, constructed by the fitness function and subarea. Finally, the effectiveness of the proposed algorithm will be expressed by the comparison experiments with the heuristic and the metaheuristic of the literatures. As comparing with existing heuristic algorithms and metaheuristic algorithms, it has been found that the packing rate of algorithm BP is the same as 97% as existing heuristic algorithms, FFF and FBS, or better than them. Also, it has been shown the same as 86% as tabu search algorithm or better.

주제어

AI 본문요약
AI-Helper

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

문제 정의

2차원저장소 적재 문제(two- dimensional bin packing problem, 2D-BPP)에서 각각 w_j , h_j를 너비와 높이로 갖는 n개의 직사각 개체(item)와 너비와 높이가 W, H로 일정한 무한 수의 저장소(bin)가 주어진다. 이 문제의 목적은 모든 개체를 겹치지 않도록 저장소에 적재하되 저장소의 수가 최소가 되도록 적재하는 방법을 찾는 것이다.

가설 설정

너비가 W이고 높이가 H인 저장소와 n개의 개체로 구성된 집합 X = {1, 2,···, n} 가 주어져 있다고 가정하자.

제안 방법

따라서 본 논문은 휴리스틱 알고리즘과 타부서치 등과 같은 근사 알고리즘의 복잡함을 간소화하고, 효율성을 높이기 위해 적재가능성을 판단할 수 있는 적합성 함수(fitness function)를 정의하고 이를 이용하여 개체를 적재하는 새로운 휴리스틱 알고리즘 BP (Bin Packing)를 제안한다. 알고리즘 BP는 1단계 알고리즘이고 회전가능하지 않은 개체에 적용되며 실험을 통하여 기존의 휴리스틱 알고리즘인 FFF와 FBS ([4])에 비해 97%의 결과가 같거나 우수하였으며, 타부서치 알고리즘 [16]에 비해 86%의 결과가 같거나 우수함을 입증하였다.
알고리즘 BP는 1단계 알고리즘으로 크기가 W× H인 저장소에 개체를 직접 적재하는 알고리즘이다. 부분영역의 집 합을 S = {(0,0;H)}로 초기화하고, 한 부분영역 s 에 개체가 적재될 때, 가장 작은 #값을 갖는 개체 j가 선택되도록 설계하였다. 또한 최소의 #값을 갖는 개체가 많을 경우에 면적이 가장 큰 개체를 선택하여 적재한다.
에 대한 최악인 경우의 실행율(worst-case performance ratio) 을 결정하였고, [7]과 [20]에서 제안한 1차원 적재 문제의 하한을 일반화하여 2차원 문제의 하한 L₁과 이를 개선한 하한으로 L₂, L₃, L₄을 유도하였다. 회전 가능한 개체에 대한 하한은 Dell’ Amico, Martello와 Vigo([8])에 의해 소개되었다.
정확한 (exact) 알고리즘에 대한 연구가 Martello, Vigo와 Dell’Amico ([8], [19], [21])에 의해 이루어졌으며 회전되지 않는 개체에 대한 정확한 알고리즘은 [19]과 [21]에서 제안되었다. 이 알고리즘들은 분지한계 기법을 사용하였고, 주어진 모든 개체의 개체 저장을 위해 필요한 저장소의 하한(lower bound)을 분석하였다. Martello와 Vigo([21])는 연속하한(continuous lower bound)

대상 데이터

본 논문에서 소개한 BP 알고리즘은 java6.0으로 프로그래밍 되었고, PC pentium 4 2.4GHz Memory RAM 1 GB에서 실험되었다.
실험결과의 비교 대상은 휴리스틱 알고리즘 FFF , FBS ([4])와 이웃검색(neighborhood search)기법을 사용한 타부서치 TS ([16]), 그리고 floor-ceiling기법의 휴리스틱 알고리즘 FCOG, FCOF([17])와 1차원 배낭문제(knapsack problem)의 해법을 적용한 알고리즘 KPOG([17]), Lodi, Martello와 Vigo([17])에 의해 새롭게 제안된 양방향(alternate directions) 알고리즘 ADOF, 그리고 알고리즘 KPOG, ADOF해를 초기해로 이용한 타부서치 알고리즘이다.

성능/효과

마지막 열은 본 논문의 알고리즘 BP 에 의한 결과로 각 클래스의 평균값을 비 교할 때, 모든 예에서 FFF , FBS 와 평행절단 문제의 알고리즘인 FCOG, KPOG와 같거나 우수한 결과를 얻었으며, 평행절단을 적용하지 않은 알고리즘인 FCOF, ASOF와 97%가 같거나 우수한 것으로 나타나 전반적으로 기존의 휴리스틱 알고리즘에 비해 우수한 성능을 보였다.
본 논문에서 제안한 휴리스틱 알고리즘 BP는 타부서치 알고리즘에 비해 그 알고리즘이 간결하며 기존의 휴리스틱 알고리즘에 비해 좋은 성능을 보이고 있어 이 알고리즘의 해를 초기해로 적용하는 타부서치 기법은 기존의 근사 알고리즘에 비해 좋은 결과를 얻을 것으로 예상된다. 또한 회전 가능 개체에 대한 2차원 적재문제와 2차원 적재기법을 이용한 3차원 적재 문제에 이 함수를 확장하여 적용하면 원재료의 절단 문제나 컨테이너 또는 팔레트 적재 문제 등 산업현장에 실제로 적용되는 예에서 좋은 결과를 얻을 수 있을 것으로 기대된다.
이러한 관점에서 적재와 절단 문제의 발전은 그 중요성이 증대되고 있는 반면 그 문제의 난해함으로 인하여 획기적이 발전이 어렵다. 본 논문에서는 적재 패턴을 판단하는 적합성 함수 제안으로 알고리즘을 간소화하였고 계산을 용이하게 처리할 수 있었으며, 기존의 연구결과와 비교하여 좋은 결과를 얻을 수 있었다.
따라서 본 논문은 휴리스틱 알고리즘과 타부서치 등과 같은 근사 알고리즘의 복잡함을 간소화하고, 효율성을 높이기 위해 적재가능성을 판단할 수 있는 적합성 함수(fitness function)를 정의하고 이를 이용하여 개체를 적재하는 새로운 휴리스틱 알고리즘 BP (Bin Packing)를 제안한다. 알고리즘 BP는 1단계 알고리즘이고 회전가능하지 않은 개체에 적용되며 실험을 통하여 기존의 휴리스틱 알고리즘인 FFF와 FBS ([4])에 비해 97%의 결과가 같거나 우수하였으며, 타부서치 알고리즘 [16]에 비해 86%의 결과가 같거나 우수함을 입증하였다.
마지막 열의 * 표시는 알고리즘 BP와 TS의 비교에서 BP ≤ TS인 경우이다. 표1의 실험결과로 휴리스틱 알고리즘인 FFF와 FBS에 비해 97%의 결과가 같거나 우수하였으며, 타부서치 알고리즘 TS에 비해 86%의 결과가 같거나 우수한 것으로 나타났다.

후속연구

본 논문에서 제안한 휴리스틱 알고리즘 BP는 타부서치 알고리즘에 비해 그 알고리즘이 간결하며 기존의 휴리스틱 알고리즘에 비해 좋은 성능을 보이고 있어 이 알고리즘의 해를 초기해로 적용하는 타부서치 기법은 기존의 근사 알고리즘에 비해 좋은 결과를 얻을 것으로 예상된다. 또한 회전 가능 개체에 대한 2차원 적재문제와 2차원 적재기법을 이용한 3차원 적재 문제에 이 함수를 확장하여 적용하면 원재료의 절단 문제나 컨테이너 또는 팔레트 적재 문제 등 산업현장에 실제로 적용되는 예에서 좋은 결과를 얻을 수 있을 것으로 기대된다.

질의응답

핵심어	질문	논문에서 추출한 답변
	2차원 저장소 적재는 어떤 문제로서 정확한 해를 구하는 것이 어려운가?	2차원 저장소 적재는 NP-hard 문제로서 그 문제의 정확한 해를 구하는 것이 어려운 것으로 알려져 있으며, 이의 더 좋은 해를 얻기 위해 유전자(genetic) 알고리즘, 시뮬레이티드 어닐링(simulated annealing), 타부서치(tabu search)등과 같은 근사적 접근법이 제안되어 왔다. 하지만 분지한계(branch-and-bound)나 타부서치 기법들을 이용한 기존의 대표적인 근사 알고리즘들은 휴리스틱 알고리즘의 해에 기반을 둠으로 효율성이 낮고 반복수행에 의한 계산시간이 길다.
	2차원 저장소 적재문제보더 더 좋은 해를 얻기 위해 무엇들이 제안되었는가?	2차원 저장소 적재문제는 강한 NP-hard 문제로 이 문 제들의 정확한 해를 구하는 것은 어렵다. 따라서 기존의 많은 연구들은 더 좋은 해를 얻기 위해 휴리스틱(heuristic) 또는 메타휴리스틱(meta-heuristic)등과 같은 근사 알고리즘들 [4, 6, 11, 15-17]을 제안한 바 있다. 하지만 분지한계나 타부 서치 기법들을 이용한 기존의 대표적인 근사 알고리즘들은 휴리스틱 알고리즘의 해에 기반을 둠으로 효율성이 낮고 복수행에 의한 계산시간이 길다.
	기존의 대표적인 근사 알고리즘들은 어떤 문제가 있는가?	2차원 저장소 적재는 NP-hard 문제로서 그 문제의 정확한 해를 구하는 것이 어려운 것으로 알려져 있으며, 이의 더 좋은 해를 얻기 위해 유전자(genetic) 알고리즘, 시뮬레이티드 어닐링(simulated annealing), 타부서치(tabu search)등과 같은 근사적 접근법이 제안되어 왔다. 하지만 분지한계(branch-and-bound)나 타부서치 기법들을 이용한 기존의 대표적인 근사 알고리즘들은 휴리스틱 알고리즘의 해에 기반을 둠으로 효율성이 낮고 반복수행에 의한 계산시간이 길다. 따라서 본 논문에서는 이러한 근사 알고리즘의 복잡성을 간소화하고, 알고리즘의 효율성을 높이기 위해 적재가능성을 판단하는 적합성 함수(fitness function)를 정의하고 이를 이용하여 어떤 특정 개체의 적재영역을 판단하는데 영향을 주는 적재영역의 수를 계산한다.

참고문헌 (21)

B. E. Bengtsson, Packing rectangular pieces-a heuristic approach, The Computer Journal Vol.25, No.3, pp.353-357, 1982

상세보기
J. E. Beasley, Algorithms for unconstrained two-dimensional guillotine cutting, Journal of Operational Research Society, Vol.36, pp.297-306.

상세보기
J. E. Beasley, An exact two-dimensional non-guillotine cutting tree search procedure, Operations Research, Vol.33, pp.49-64, 1985.

상세보기
J. O. Berkey and P. Y. Wang, Two dimensional finite bin packing algorithms Journal of the Operational Research Society 38, pp.423-429, 1987.

상세보기
N. Christofides and C. Whitlock, An algorithm for twodimensional cutting problrems, Operations Research, Vol.25, pp.30-44, 1977.

상세보기
F. K. R. Chung, M. R. Garey and D. S. Johnson, On Packing two-dimensional bins, SIAM Journal of Algebraic and Discrete Methods, Vol.3, No.1, pp.66-76, 1982.

상세보기
M. Dell'Amico and S. Martello, Optimal scheduling of tasks on identical parallel processors, ORSA Journal on Computing, Vol.7, No.2, pp.191-200, 1995.

상세보기
M. Dell'Amico, S. Martello and D. Vigo, A lower bound for the non-oriented two-dimensional bin packing problem, Discrete Applied Mathematics, Vol.118, pp.13-24, 2002.

상세보기
H. Dyckhoff, A typology of cutting and packing problems, European Journal of Operational Research, Vol.44, No.2, pp. 145-159, 1990.

상세보기
H. Dyckhoff and G. Finke, Cutting and packing in production and distribution, Physica Verlag, Heidelberg, 1992.
A. El-Bouri, N. Popplewell, S. Balakrishnan and A. Alfa, A search based heuristic for the two-dimensional bin-packing problem, INFOR, Vol.32, No.4, pp.265-274, 1994.
P. C. Gilmore and R. E. Gomory, Multistage cutting problems of two and more dimensions, Operations Research, Vol.13, No.1, pp.94-120, 1965

상세보기
E. Hadjiconstantinou and N. Christofides, An Exact algorithm for general, orthogonal, two-dimensional knapsack problem, European Journal of Operational Research, Vol.83, pp.39-56, 1995.

상세보기
A. Lodi, S. Martello and M. Monaci, Two-dimensional packing problems: a survey, European Journal of Operational Research, Vol.141, pp.241-252, 2002.

상세보기
A. Lodi, S. Martello, and D. Vigo, Neighborhood search algorithm for the guillotine non-oriented two-dimensional bin packing problem, in: S. Martello, I. H. Osman, C. Roucairol (Eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic Publishers, Boston, pp.125-139, 1998.
A. Lodi, S. Martello and D. Vigo, Approximation algorithms for the oriented two-dimensional bin packing problem, European Journal of Operational Research, Vol.112, 158-166, 1999.

상세보기
A. Lodi, S. Martello and D. Vigo, Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems, INFORMS Journal of Computing, Vol.11, No.4, pp. 345-357, 1999.

상세보기
A. Lodi, S. Martello, D. Vigo, Ricent advances on twodimensional bin packing problems, Discrete Applied Mathematics 123, pp.373-390, 2002.

상세보기
S. Martello, M. Monaci and D. Vigo, An exact approach to the strip packing problem, Informs Journal on Computing, Vol.15, 310-319, 2003.

상세보기
S. Martello and P. Toth, Lower bounds and reduction procedures for the bin packing problem, Discrete Applied Mathematics, Vol.28, pp.59-70, 1990.

상세보기
S. Martello and D. Vigo, Exact solution of the two dimensional finite bin packing problem, Management Science, Vol.44, pp. 388-399, 1998.

상세보기

저자의 다른 논문 :

표제어: 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

연합인증