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 (청록)
1개의 동일한 Item 이라고 하더라도 6개의 방향에 대한 경우의 수가 발행 할 수 있음을 확인할 수 있습니다.
논문에서 제안하는 알고리즘은 아래와 같습니다.
1.
입력 처리
물체의 크기와 컨테이너의 크기 정보를 입력으로 받음.
물체는 회전을 통해 최대 6개의 가능한 배치 방향(길이 × 너비 × 높이)이 계산됨.
2.
초기 정렬
물체를 크기 순서로 정렬.
3.
적합한 위치 탐색
각 물체에 대해 현재 컨테이너의 가능한 위치를 탐색.
각 물체는 가능한 6가지 회전 상태를 평가.
가장 적합한 회전 상태를 선택하여 배치.
4.
새로운 컨테이너 사용
현재 컨테이너에 배치할 수 없는 경우, 새로운 컨테이너를 열어 배치 시작.
5.
반복
모든 물체가 배치될 때까지 위 과정을 반복.
Keyword: Logistics Optimization, 물류 최적화, Linear Programming, Mixed Integer Programming, Google OR Tools
Reference:
