В инструментах Google ortools есть условие неперекрытия для 2D-прямоугольников, но не для 3D-кубоидов. Как я могу использовать Google ortools для реализации того же самого? Есть ли другие способы сделать то же самое?
Я работаю над проектом, в котором мне нужно выполнить упаковку трехмерного пространства. Я не уверен, какие ограничения следует добавить для неперекрывающихся трехмерных объектов. .Ниже приведен код:
from ortools.sat.python import cp_model
from io import StringIO
import pandas as pd
import numpy as np
#---------------------------------------------------
# data
#---------------------------------------------------
data = '''
itemid length width height weight value color
1 11 2 1 48 1 red
2 5 4 2 9 1 green
3 12 5 2 6 1 yellow
4 10 7 1 2 1 blue
5 2 4 2 33 1 pink
6 10 1 5 13 1 cyan
7 12 7 2 29 1 magenta
8 10 5 1 49 1 black
'''
df = pd.read_table(StringIO(data), sep='\s+')
print("Input data")
display(df)
L = 12
W = 8
H = 5
M = 400
print(f"Truck's Dimension Length:{L} Width:{W} Height:{H} Maximum Capacity:{M}")
#---------------------------------------------------
# derived data
# expand to individual items
#---------------------------------------------------
l0 = df["length"].to_numpy()
b0 = df['width'].to_numpy()
h0 = df['height'].to_numpy()
w0 = df['weight'].to_numpy()
v0 = df['value'].to_numpy()
indx0 = np.arange(np.size(l0))
n = len(l0)
print(f"Number of individual items: {n}")
#---------------------------------------------------
# create rotated items
# by duplicating
#---------------------------------------------------
# six possible rotation of a 3d object
l_rot = np.concatenate((l0, l0, b0, b0, h0, h0))
w_rot = np.concatenate((b0, h0, l0, h0, b0, l0))
h_rot = np.concatenate((h0, b0, h0, l0, l0, b0))
wr = np.tile(w0, 6)
vr = np.tile(v0, 6)
indxr = np.tile(indx0, 6)
nr = 6 * n
print(f"Number of individual items (after adding rotations): {nr}")
#---------------------------------------------------
# or-tools model
#---------------------------------------------------
model = cp_model.CpModel()
#
# variables
#
# u : item i is used
u = [model.NewBoolVar(f"u{i}") for i in range(nr)]
# x, y, z : location of item i
x = [model.NewIntVar(0, L, f"x{i}") for i in range(nr)]
y = [model.NewIntVar(0, W, f"y{i}") for i in range(nr)]
z = [model.NewIntVar(0, H, f"z{i}") for i in range(nr)]
# l, w, h : dimensions of item i
lx = [model.NewIntVar(0, L, f"lx{i}") for i in range(nr)]
ly = [model.NewIntVar(0, W, f"ly{i}") for i in range(nr)]
lz = [model.NewIntVar(0, H, f"lz{i}") for i in range(nr)]
# x2, y2, z2 : upper limit of interval variable
x2 = [model.NewIntVar(0, L, f"x2{i}") for i in range(nr)]
y2 = [model.NewIntVar(0, W, f"y2{i}") for i in range(nr)]
z2 = [model.NewIntVar(0, H, f"z2{i}") for i in range(nr)]
# interval variables
xival = [model.NewIntervalVar(x[i], lx[i], x2[i], f"xival{i}") for i in range(nr)]
yival = [model.NewIntervalVar(y[i], ly[i], y2[i], f"yival{i}") for i in range(nr)]
zival = [model.NewIntervalVar(z[i], lz[i], z2[i], f"zival{i}") for i in range(nr)]
#
# constraints
#
# The main idea here is: if an item is not selected, make its
# length, width, and height zero.
# u[i] = 0 ==> lx[i]=ly[i]=lz[i]=0
# u[i] = 1 ==> lx[i]=l_rot[i], ly[i]=w_rot[i], lz[i]=h_rot[i]
for i in range(nr):
model.Add(lx[i] == l_rot[i] * u[i])
model.Add(ly[i] == w_rot[i] * u[i])
model.Add(lz[i] == h_rot[i] * u[i])
# only one of the six possible rotations can be used
for i in range(n):
model.Add(sum(u[i + j * n] for j in range(6))
Подробнее здесь: https://stackoverflow.com/questions/786 ... e-or-tools
