3D Bin Packing 문제는 2D Bin Packing 문제와 비슷하지만 물체와 Bin이 3차원이라는 점에서 차이가 있습니다.
물류에서는 3D Bin Packing 문제를 응용해서 컨테이너에 물건을 최대한 많이 적재하는 방법을 찾거나,
이커머스에서 박스상자의 최적의 크기를 산정하여 불필요한 지출을 방지는 목적으로 사용합니다.
3D Bin Packing 문제를 해결하는 다양한 방법이 있지만 본 글에서는 2D Bin Packing에서 작성한 OrTools 코드를 응용하는 방법을 살펴 보겠습니다.
문제 정의
1. 각 물체는 너비, 높이, 깊이의 3차원 크기를 가집니다.
2. 상자는 물체들을 담을 수 있는 한계 크기가 정해져 있습니다.
3. 최소한의 상자에 모든 물체를 넣는 것이 목표입니다.
데이터 모델
1. 빈의 가로, 세로, 높이를 각각 10으로 설정합니다.
2. 여러 개의 상자들에 대한 크기(가로, 세로, 높이)를 리스트로 저장합니다.
3. 사용할 수 있는 빈의 수를 2개로 설정합니다. 즉, 상자들은 최대 2개의 빈에 배치될 수 있습니다.
Decision Variable
각 상자에 대해 빈 안에서의 위치를 나타내는 변수들 x, y, z를 생성합니다. 이 변수들은 상자의 왼쪽 아래 모서리가 빈의 어느 좌표에 위치할지를 나타냅니다. bin_assignment 변수를 통해 각 상자가 어떤 빈에 배치될지를 정의합니다. 이 변수는 상자가 0번 빈에 배치될지, 1번 빈에 배치될지를 나타냅니다.
Constraints
각 상자는 빈의 크기 내에 완전히 들어가야 합니다. 예를 들어, 상자의 너비와 x 좌표의 합이 빈의 너비를 넘지 않아야 합니다. 두 상자가 같은 빈에 배치되면 서로 겹치지 않아야 합니다. 상자 i와 상자 j가 동일한 빈에 배치된 경우에만, 상자들이 서로 겹치지 않도록 하기 위해 6개의 불리언 변수(no_overlap)를 사용합니다. 이 변수들은 두 상자가 가로, 세로, 높이 방향에서 겹치지 않음을 나타냅니다.
Objective
이 문제의 목표는 가능한 적은 빈을 사용하여 모든 상자를 배치하는 것입니다. 이를 위해 각 상자의 bin_assignment 값을 더한 값을 최소화하는 목표를 설정합니다.
전체소스
from ortools.sat.python import cp_model
def create_data_model():
"""Creates the data for the example."""
data = {}
# Bin dimensions
data['bin_width'] = 10
data['bin_height'] = 10
data['bin_depth'] = 10
# Boxes dimensions: width, height, depth
data['boxes'] = [
[4, 4, 4],
[4, 4, 4],
[4, 4, 4],
[4, 4, 4],
[4, 4, 4],
[8, 4, 4],
[10, 2, 2],
]
return data
def main():
# Create the model.
model = cp_model.CpModel()
# Data
data = create_data_model()
bin_width = data['bin_width']
bin_height = data['bin_height']
bin_depth = data['bin_depth']
boxes = data['boxes']
num_boxes = len(boxes)
# Variables: x, y, z position of each box in the bin.
x = []
y = []
z = []
for i in range(num_boxes):
x.append(model.NewIntVar(0, bin_width, f'x_{i}'))
y.append(model.NewIntVar(0, bin_height, f'y_{i}'))
z.append(model.NewIntVar(0, bin_depth, f'z_{i}'))
# Constraints for keeping the boxes inside the bin.
for i in range(num_boxes):
box_width = boxes[i][0]
box_height = boxes[i][1]
box_depth = boxes[i][2]
# The box should be completely inside the bin dimensions.
model.Add(x[i] + box_width <= bin_width)
model.Add(y[i] + box_height <= bin_height)
model.Add(z[i] + box_depth <= bin_depth)
# Non-overlapping constraints: Ensure that no two boxes overlap.
for i in range(num_boxes):
for j in range(i + 1, num_boxes):
no_overlap_1 = model.NewBoolVar("1")
no_overlap_2 = model.NewBoolVar("2")
no_overlap_3 = model.NewBoolVar("3")
no_overlap_4 = model.NewBoolVar("4")
no_overlap_5 = model.NewBoolVar("5")
no_overlap_6 = model.NewBoolVar("6")
box_i_width = boxes[i][0]
box_i_height = boxes[i][1]
box_i_depth = boxes[i][2]
box_j_width = boxes[j][0]
box_j_height = boxes[j][1]
box_j_depth = boxes[j][2]
model.Add(x[i] + box_i_width <= x[j]).OnlyEnforceIf(no_overlap_1)
model.Add(x[j] + box_j_width <= x[i]).OnlyEnforceIf(no_overlap_2)
model.Add(y[i] + box_i_height <= y[j]).OnlyEnforceIf(no_overlap_3)
model.Add(y[j] + box_j_height <= y[i]).OnlyEnforceIf(no_overlap_4)
model.Add(z[i] + box_i_depth <= z[j]).OnlyEnforceIf(no_overlap_5)
model.Add(z[j] + box_j_depth <= z[i]).OnlyEnforceIf(no_overlap_6)
model.AddBoolOr([no_overlap_1, no_overlap_2, no_overlap_3, no_overlap_4, no_overlap_5, no_overlap_6])
# Objective: Minimize the total used volume of the bin (this is just an example of a goal).
model.Minimize(sum([x[i] for i in range(num_boxes)]) + sum([y[i] for i in range(num_boxes)]) + sum([z[i] for i in range(num_boxes)]))
# Solve the model.
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
print('Solution:')
for i in range(num_boxes):
print(f'Box {i}: {solver.Value(x[i])},{solver.Value(y[i])},{solver.Value(z[i])}')
else:
print('No solution found.')
if __name__ == '__main__':
main()
Python
복사
결과는 아래와 같습니다.
Solution:
Box 0: 0,0,0
Box 1: 0,0,4
Box 2: 0,4,4
Box 3: 4,0,0
Box 4: 4,0,4
Box 5: 0,6,0
Box 6: 0,4,0
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
