The two-dimensional bin-packing problem (2D-BPP) with rotations is an important optimization problem which has a large number of practical applications. It consists of the non-overlapping placement of a set of rectangular pieces in the lowest number of bins of a homogenous size, with the edges of these pieces always parallel to the sides of bins, and with free 90 degrees rotation. A large number of methods have been proposed to solve this problem, including heuristic and meta-heuristic approaches.
In this thesis, we presents a new heuristic algorithm to solve the 2D-BPP that incorporates ant colony algorithm specially designed for this problem. The performance of this algorithm is compared with other heuristics previously proposed by other authors in ten classes of frequently used benchmark problems. It is observed that, in some cases, the method here proposed is able to equal or even outperform to the results of the other two heuristics in most test problems.
2 차원 상자 채우기 문제 (The two-dimensional bin-pacing problem; 2D-BPP)는 사각형 아이템들과 동일한 면적의 사각형 상자들이 주어질 때, 상자들 안에 모든 아이템들이 서로 겹치지 않고 쌓일 수 있는 최소의 상자 개수를 찾는 문제이다. 또한 본 논문에서는 아이템의 회전을 고려하므로 상자에 아이템이 쌓일 때 90˚회전이 가능하다.
2D-BPP 는 목재 산업에서의 규격화된 크기로 자르는 작업, 철판과 유리 산업, 선반이나 트럭 그리고 창고에서 물건 쌓는 일, 그리고 신문 등에서 기사들을 배치하는 일 등의 재질을 자르거나 제품을 쌓는 산업에서 많이 응용되고 있으며, 이 문제를 해결하기 위해 많은 휴리스틱과 메타 휴리스틱 알고리즘들이 소개되어 왔다.
본 논문에서는 2D-BPP 를 해결하기 위한 새로운 휴리스틱 알고리즘을 제안했고, 이 휴리스틱의 성능 향상을 위하여 새롭게 변형시킨 개미 군집 알고리즘을 적용하였다. 새롭게 제안된 개미 군집 알고리즘의 성능을 객관적으로 측정하기 위해서 다른 논문들에서 제안된 알고리즘들에 빈번하게 사용되어 온 벤치마크 데이터에 개미 군집 알고리즘을 적용하였다. 본 논문에서 연구된 새로운 개미 군집 알고리즘의 성능 측정 결과는 이전의 다른 논문들과 비교하여 대부분 같은 값을 같거나 때로는 더 나은 결과를 갖는 부분도 존재하였다.
