2D Bin Packing 문제는 제한된 크기의 2차원 공간(빈)에 주어진 일련의 직사각형 물체들을 가능한 한 효율적으로 배치하는 문제입니다.
목표는 주어진 물체를 모두 빈에 담되, 최소한의 빈을 사용하는 것입니다.
즉, 가능한 한 많은 물체를 한 상자에 담거나, 필요한 상자의 개수를 최소화하는 것이 핵심입니다.
이 문제는 물체의 개수가 많아질수록 가능한 배치의 수가 기하급수적으로 증가하게 됩니다.
이로 인해 최적 해를 찾는 것은 매우 어려워질 수 있으며, 현실적으로는 문제의 복잡성을 고려해
휴리스틱(Heuristic) 알고리즘을 사용하여 합리적인 시간 내에 해결책을 찾는 것이 일반적입니다.
문제 정의
1. 물체는 빈의 경계를 넘을 수 없습니다.
2. 물체들끼리 서로 겹치지 않아야 합니다.
3. 빈의 크기는 고정되어 있으며, 물체의 크기는 사전에 정의됩니다.
Initialization
__init__ 함수는 상자의 너비(bin_width), 높이(bin_height), 그리고 물품들의 크기(items)를 입력으로 받아 모델을 초기화합니다. items는 각 물품의 (너비, 높이)로 구성된 리스트입니다.
Decision Variable
각 물품의 좌표를 나타내는 변수 x와 y를 생성합니다. 이는 각각 물품의 왼쪽 아래 모서리가 상자의 왼쪽 아래 모서리에서부터 얼마나 떨어져 있는지를 나타냅니다.
Constraints
물품들이 서로 겹치지 않도록 제약 조건을 설정합니다. 이를 위해 각 물품 쌍에 대해 네 가지 조건을 만듭니다:
1.
물품 i가 물품 j의 오른쪽에 있는 경우.
2.
물품 i가 물품 j의 왼쪽에 있는 경우.
3.
물품 i가 물품 j의 위쪽에 있는 경우.
4.
물품 i가 물품 j의 아래쪽에 있는 경우.
네 가지 조건 중 하나는 반드시 성립해야 하므로 AddBoolOr 함수를 사용해 물품들이 서로 겹치지 않도록 제약 설정 합니다.
전체소스
from ortools.sat.python import cp_model
class BinPacking2D:
def __init__(self, bin_width, bin_height, items):
self.bin_width = bin_width
self.bin_height = bin_height
self.items = items
self.num_items = len(items)
self.model = cp_model.CpModel()
def solve(self):
# Variables
x = [self.model.NewIntVar(0, self.bin_width - item[0], f'x_{i}') for i, item in enumerate(self.items)]
y = [self.model.NewIntVar(0, self.bin_height - item[1], f'y_{i}') for i, item in enumerate(self.items)]
bin_used = self.model.NewBoolVar('bin_used')
# Constraints for no overlap between items
for i in range(self.num_items):
for j in range(i + 1, self.num_items):
# Create boolean variables for each non-overlapping condition
no_overlap_right = self.model.NewBoolVar(f'no_overlap_right_{i}_{j}')
no_overlap_left = self.model.NewBoolVar(f'no_overlap_left_{i}_{j}')
no_overlap_above = self.model.NewBoolVar(f'no_overlap_above_{i}_{j}')
no_overlap_below = self.model.NewBoolVar(f'no_overlap_below_{i}_{j}')
# item i is to the right of item j
self.model.Add(x[i] + self.items[i][0] <= x[j]).OnlyEnforceIf(no_overlap_right)
# item i is to the left of item j
self.model.Add(x[j] + self.items[j][0] <= x[i]).OnlyEnforceIf(no_overlap_left)
# item i is above item j
self.model.Add(y[i] + self.items[i][1] <= y[j]).OnlyEnforceIf(no_overlap_above)
# item i is below item j
self.model.Add(y[j] + self.items[j][1] <= y[i]).OnlyEnforceIf(no_overlap_below)
# At least one of these conditions must hold (no overlap between i and j)
self.model.AddBoolOr([no_overlap_right, no_overlap_left, no_overlap_above, no_overlap_below])
# All items must fit within the bin dimensions
for i in range(self.num_items):
self.model.Add(x[i] + self.items[i][0] <= self.bin_width)
self.model.Add(y[i] + self.items[i][1] <= self.bin_height)
# Objective: Minimize the number of bins used (in a more complex version, but not required for this demo)
self.model.Minimize(bin_used)
# Solve the model
solver = cp_model.CpSolver()
status = solver.Solve(self.model)
if status == cp_model.OPTIMAL:
print('Optimal solution found!')
for i in range(self.num_items):
print(f'Item {i}: x={solver.Value(x[i])}, y={solver.Value(y[i])}')
else:
print('No solution found.')
# Example usage
bin_width = 10
bin_height = 10
items = [(3, 3), (5, 2), (4, 4), (1, 9), (2, 3), (2, 3), (3, 3), (3, 3), (3,3), (10, 1)] # List of items with their width and height
bin_packing = BinPacking2D(bin_width, bin_height, items)
bin_packing.solve()
Python
복사
결과를 시각화 하면 아래와 같습니다.
Item 0: x=7, y=0
Item 1: x=2, y=3
Item 2: x=1, y=5
Item 3: x=0, y=0
Item 4: x=5, y=0
Item 5: x=5, y=5
Item 6: x=7, y=3
Item 7: x=7, y=6
Item 8: x=1, y=0
Item 9: x=0, y=9
Plain Text
복사
Keyword: Logistics Optimization, 물류 최적화, Linear Programming, Mixed Integer Programming, Google OR Tools
Reference:
[1] The Bin Packing Problem by Google, https://developers.google.com/optimization/pack/bin_packing, Creative Commons Attribution 4.0 License
