상자채우기 문제 (Bin Packing Problem)
한 줄 정의: 크기가 서로 다른 여러 품목을 용량이 동일한 상자(빈)에 담을 때, 각 상자의 용량을 초과하지 않으면서 사용하는 상자의 수를 최소화하는 조합최적화 문제입니다.
쉽게 풀면
무게 제한이 있는 택배 상자에 크기가 제각각인 물건들을 담아 상자 수를 가장 적게 쓰려면 어떻게 넣어야 할까 하는 문제입니다. 직관적으로는 쉬워 보이지만, 물건이 많아지면 가능한 조합이 폭발적으로 늘어 정확한 최적해를 구하기 매우 어렵습니다.
왜 중요한가
적재·포장, 컨테이너 배정, 작업 할당, 서버 가상머신 배치 등 '용량이 있는 자원에 작업을 묶는' 거의 모든 문제가 상자채우기의 변형입니다. NP-난해 문제의 대표 사례로, 근사 알고리즘의 성능 보장(근사비율) 이론이 발전한 무대이기도 합니다.
논문에서는 이렇게 쓰입니다
"배송 품목의 차량 적재 계획을 상자채우기 문제(bin packing problem)로 모형화하고, 최초적합감소(FFD) 휴리스틱으로 필요 차량 수를 산정하였다."
물건을 차량에 나눠 싣는 문제를 상자채우기로 보고 간단한 규칙으로 차량 수를 구했다는 뜻입니다.
"열생성법 기반 하한과 FFD 상한의 차이가 1 이하로 나타나 거의 모든 인스턴스에서 최적해가 확인되었다."
이론적 최소값과 휴리스틱 답이 거의 같아 휴리스틱이 사실상 최적임을 확인했다는 의미입니다.
조금 더 깊게 보면
고전적 휴리스틱인 최초적합(FF), 최적적합(BF)과 품목을 크기 내림차순으로 정렬한 FFD는 각각 근사비율 17/10, 11/9의 성능 보장을 갖습니다. 정확해법으로는 Gilmore-Gomory의 패턴 기반 정식화에 열생성법과 분지가격법을 결합한 방법이 표준입니다. 2차원·3차원 상자채우기, 온라인 버전(품목이 순차 도착), 가변 크기 상자, 품목 간 충돌 제약 등 다양한 변형이 연구됩니다.
주의할 점
1차원 모형은 무게나 부피 합만 고려하므로 실제 적재에서의 형상·적재 순서·안정성은 반영되지 않습니다. 또한 품목 수가 적고 크기가 상자 용량에 비해 클 때는 간단한 휴리스틱이 최적에서 상당히 벗어날 수 있어 하한과의 비교가 필요합니다.