3차원 박스 적재 최적화를 위한 OptaPlanner 기반 구현기

조현준조현준
3 min read

1. 도입

물류센터, 창고관리(WMS), 배송 박싱 자동화 등의 문제에서 공통적으로 요구되는 기능 중 하나는 여러 물건(Item)을 제한된 공간(Bin)에 효과적으로 적재(Packing) 하는 것입니다.

이를 해결하기 위해서는 여러가지 알고리즘 밑 방법을 사용할 수 있는데 오늘은 Bin-Packing 알고리즘에 대해서 공부하고 이를 실제로 구현해보도록 하겠습니다.

이 글에서는 이러한 문제를 해결하기 위해 Java 기반의 제약 프로그래밍 프레임워크인 OptaPlannerJavaFX 기반 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 렌더링 자동화

9. 참고 자료

1
Subscribe to my newsletter

Read articles from 조현준 directly inside your inbox. Subscribe to the newsletter, and don't miss out.

Written by

조현준
조현준