3D Bin Packing 문제를 효과적으로 해결하는 방법 중 하나로 휴리스틱 접근법이 좋은 결과를 보이고 있습니다.
GitHub에서 "3D Bin Packing" 키워드로 검색하면 유용한 프로젝트들을 여러 개 찾아볼 수 있습니다.
이 프로젝트는 로직이 간단하며, 참고한 논문도 함께 제공되어 있어 3D Bin Packing 문제를 이해하는 데 큰 도움이 되었습니다.
본 논문에서 풀고자 하는 3D Bin Packing 문제는 주어진 다양한 크기의 직육면체 아이템들을 최소한의 3차원 상자에 적재하는 문제로,
아이템의 회전이 허용되며, 각 아이템은 6가지의 회전 형태를 가질 수 있습니다.
논문을 이해하기 위해서는 아래와 같이 6개의 방향에 대해서 먼저 이해하는게 필요합니다.
대신 Python등의 도구를 이용해서 6개 방향을 그려보면 대략 아래와 같은 6개의 경우의 수를 생각할 수 있습니다.
1. L × W × H (빨강)
2. L × H × W (초록)
3. W × L × H (파랑)
4. W × H × L (주황)
5. H × L × W (보라)
6. H × W × L (청록)
6개의 경우의 수를 Python 그려보면 아래와 같습니다.
논문에서는 기존의 2가지 휴리스틱 방법을 설명하고 개선하는 방법을 제시합니다.
1.
First Fit Decreasing: 아이템을 크기 순으로 정렬한 후, 첫 번째로 맞는 상자에 배치하는 방법입니다.
2.
Best Fit: 아이템을 가장 적합한 상자에 배치하여 남은 공간을 최소화하는 방법입니다.
논문에서 제안하는 알고리즘은 아래와 같습니다. (3D Best Fit, with pivoting)
1.
입력 처리
물체의 크기와 컨테이너의 크기 정보를 입력으로 받음.
물체는 회전을 통해 최대 6개의 가능한 배치 방향(길이 × 너비 × 높이)이 계산됨.
2.
초기 정렬
물체를 크기 순서로 정렬.
3.
적합한 위치 탐색
각 물체에 대해 현재 컨테이너의 가능한 위치를 탐색.
각 물체는 가능한 6가지 회전 상태를 평가.
가장 적합한 회전 상태를 선택하여 배치.
4.
새로운 컨테이너 사용
현재 컨테이너에 배치할 수 없는 경우, 새로운 컨테이너를 열어 배치 시작.
5.
반복
모든 물체가 배치될 때까지 위 과정을 반복.
Keyword: Logistics Optimization, 물류 최적화, Linear Programming, Mixed Integer Programming, Google OR Tools
Reference:
