OR-Tools 中只有一个箱子的装箱

Question

我一直在尝试调整 OR-Tools 中常见的装箱问题来优化使用的空间，而不是优化箱数，但我似乎无法弄清楚如何做到这一点。

所以我想做的是：

给定一组不同尺寸的 2D 盒子，以及一个任意长、固定宽度的 2D 容器，我们可以将所有盒子包装得有多紧？

乍一看，这个问题的一个不错的解决方案似乎是定义如下变量：

x1 = [model.NewIntVar(0,L-l[i],f'x1{i}') for i in range(n)]
x2 = [model.NewIntVar(l[i],L,f'x2{i}') for i in range(n)]

其中 L 是最大容器长度，l[i] 是第 i 个盒子的长度，对于 n 个盒子。

然后对高度进行类似的操作，其中 H 为容器高度，h[i] 为盒子的高度。

然后我可以得到每个盒子的面积：

a = [model.NewConstant(h[i]*w[i]) for i in range(n)]

定义长度和宽度的一些间隔：

xinv = [model.NewIntervalVar(x1[i],w[i],x2[i],f'xinv{i}') for i in range(n)]
yinv = [model.NewIntervalVar(y1[i],h[i],y2[i],f'yinv{i}') for i in range(n)]

还有一个限制，即盒子不能重叠：

model.AddNoOverlap2D(xinv,yinv)

乍一看，我应该能够使用如下策略：

• 获取距离容器背面最远的盒子的 x 坐标
• 用它来定义一个包含到目前为止放置的所有盒子的正方形（正方形的其他边是容器的顶部、底部和背面）
• 将所有盒子的面积相加
• 从平方中减去它
• 结果是未被盒子填充的空白区域
• 设定一个目标以尽量减少空白空间

可以通过使用

model.AddMaxEquality

将变量设置为盒子到达的最大距离来定义正方形。但是，我陷入了“将所有放置的盒子的面积相加”部分。似乎没有办法回顾并获取先前放置的框的坐标，即使可以确定这些框的放置位置以强制执行

AddNoOverlap2D

约束。

如何计算容器中当前盒子的总面积？

Answer 1

1. 使用FixedSizeIntervalVar。
2. 你知道所有物品打包后，总面积是固定的。您只需最小化最大结束坐标即可。
3. 如果需要灵感，您可以查看https://github.com/google/or-tools/blob/stable/examples/python/knapsack_2d_sat.py

Answer 2

1. 使用FixedSizeIntervalVar。
2. 你知道所有物品打包后，总面积是固定的。您只需最小化最大结束坐标即可。
3. 想要灵感，你可以看看