3차원 박스 적재 최적화를 위한 OptaPlanner 기반 구현기
1. 도입
물류센터, 창고관리(WMS), 배송 박싱 자동화 등의 문제에서 공통적으로 요구되는 기능 중 하나는 여러 물건(Item)을 제한된 공간(Bin)에 효과적으로 적재(Packing) 하는 것입니다.
이를 해결하기 위해서는 여러가지 알고리즘 밑 방법을 사용할 수 있는데 오늘은 Bin-Packing 알고리즘에 대해서 공부하고 이를 실제로 구현해보도록 하겠습니다.
이 글에서는 이러한 문제를 해결하기 위해 Java 기반의 제약 프로그래밍 프레임워크인 OptaPlanner와 JavaFX 기반 3D 시각화를 활용하여 3D Bin Packing 문제를 해결한 과정을 정리합니다.
2. 목표
다양한 크기와 모양(Shape)의 물건들을 제한된 박스 내부에 겹치지 않도록 배치
회전 가능한 물체의 방향(Rotation) 고려
실제 현실과 유사하게 물리 제약, 무게 제약, 부피 제약, 버퍼 영역 등을 반영
사용 박스 수를 최소화하는 방향으로 최적화
결과를 3D 화면으로 시각화하여 검증 가능하도록 구성
3. 시스템 구성
3.1 Item과 Bin 모델링
data class Item(val id: Int, val width: Long, val height: Long, val length: Long, val shape: Shape, ...)
data class Bin(val id: Int, val width: Long, val height: Long, val length: Long, val buffer: Double, ...)
Item은 물건 하나를 나타내며, 회전 가능성과 형태 정보도 포함합니다.
Bin은 적재 가능한 공간으로, 버퍼와 최대 무게 제한 등을 포함합니다.
3.2 PlanningEntity: ItemAssignment
@PlanningEntity
data class ItemAssignment(..., var bin: Bin?, var x: Long?, var y: Long?, var z: Long?, var rotation: Rotation?)
- 각 ItemAssignment는 특정 Item이 어떤 Bin의 어느 위치(x,y,z)에 어떤 방향(rotation)으로 배치될지를 나타냅니다.
4. 제약 조건 구성
4.1 주요 제약 조건
itemMustFitInBin: 물건이 박스를 넘지 않도록 보장
noOverlap: 두 아이템이 같은 공간을 차지하지 않도록 제한
binCapacityExceeded: 버퍼를 고려한 부피 초과 방지
binWeightLimitExceeded: 최대 무게 제한
minimizeBinUsage: 사용한 박스 수를 줄이기 위한 소프트 제약
4.2 ConstraintPurpose를 통한 점수 구조
enum class ConstraintPurpose(val level: Int, val isHard: Boolean, val description: String)
하드 제약: 충돌, 무게 초과 등 현실적 충족 필수 조건
소프트 제약: 사용 박스 수 최소화, 빈 공간 최소화, 무게 배분 등
5. 솔버 구성
SolverFactory.create<BinPackingSolution>(
SolverConfig()
.withSolutionClass(...)
.withEntityClasses(...)
.withConstraintProviderClass(...)
.withTerminationConfig(
TerminationConfig().apply {
unimprovedSecondsSpentLimit = 3L
}
)
SolverFactory를 통해 제약 조건 기반의 최적해를 탐색
종료 조건은 3초 동안 점수 개선이 없을 경우 자동 종료
6. 시각화
6.1 JavaFX 기반 3D Viewer
주요 특징:
각 Bin은 검정 테두리의 박스로 시각화
각 Item은 반투명하고 색상 지정된 3D Box로 시각화
각 아이템은 Golden Angle 기반 Hue 값을 통해 고유 색상을 유지
XYZ 축은 빨강, 초록, 파랑 선 및 라벨로 표현
카메라는 대각선 위에서 XY 평면을 내려다보는 구조로 배치
마우스 회전 및 확대 기능은 이후 단계에서 확장 가능
6.2 예시 화면
실행 시 결과 예시는 다음과 같습니다:
- 콘솔 화면
=== 결과 ===
Item 1 -> Bin 1 | Rotation: XYZ | X: 0, Y: 0, Z: 0
Item 2 -> Bin 1 | Rotation: YXZ | X: 1, Y: 0, Z: 0
...
Score: 0hard/0soft
Bin 1 [XY 평면 @ Z=0]
| 1 | 2 | |
| 3 | | |
| | | |
Bin 1 [XY 평면 @ Z=1]
| 4 | 5 | |
| | | |
| | | |
- JavaFX 화면
콘솔에는 XY 평면 기준으로 z=0부터 아이템이 어떻게 적재되었는지를 확인할 수 있습니다.
7. 학습 및 구현에서의 주요 고려 사항
단순히 부피만 고려하는 것이 아니라, 모양에 따른 buffer 영역까지 고려해야 현실적인 배치가 가능
아이템 회전과 도형별 부피 공식, 특히 원통, 원뿔, 파우치형 등은 단순 박스형보다 복잡
3D 시각화는 디버깅 및 결과 검증에 매우 효과적
8. 마무리
이번 프로젝트를 통해 물류 시스템에서 자주 접하게 되는 Packing 최적화 문제에 대해 제약 기반의 방식으로 접근할 수 있음을 경험할 수 있었습니다.
OptaPlanner는 수많은 상태를 가진 조합 문제를 빠르게 탐색할 수 있게 해주며, JavaFX 기반의 3D 출력은 단지 “작동한다” 이상의 검증 도구로 활용할 수 있었습니다.
다음 확장 방향으로는 다음을 고려하고 있습니다:
사용자 마우스 회전, 확대 조작 추가
다양한 박스 규격 자동 선택 로직
병렬 Bin 추천 기능 및 우선순위 부여 로직
웹기반 3D View 또는 Blender 렌더링 자동화