3D装箱算法

Question

3D装箱算法

4

有人知道任何3D装箱算法吗？我知道LAFF（Large Area Fits First）算法；然而，我需要一个约束条件是托盘具有固定的宽度和长度（高度为无限大）的算法。在LAFF实现中，它搜索盒子并找到长度和高度的最大值，然后将其作为固定托盘。

LAFF算法

- Kay

2个回答

1

您可以使用LAFF在有限的xy维度和无限的z维度中进行盒子适配。LAFF将2D级别的盒子逐层叠加以形成3D效果。

我创建了一个LAFF开源项目，您可以修改它，或者直接使用当前代码运行，只需将容器高度设置为Integer.MAX_VALUE即可。在计算机中，“无限”实际上并非无限；)

- ThomasRS

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Zim-Zam O'Pootertoot · Accepted Answer

吉尔廷切割启发式算法（例如参见这篇论文）虽然不精确但速度很快——当您向容器添加一个盒子时，容器会被分成三个不相交的子容器，例如，如果您有一个12x12x12的容器并添加了一个8x8x8的盒子，则会剩下一个12x12x4的容器，一个12x8x4的容器和一个8x8x4的容器。不精确之处在于，有一些合法的（根据物理定律）装箱方式被这种空间分割所禁止（例如，如果您有一个12x12x12的容器和四个12x8x4的盒子，则吉尔廷切割会将容器分割成只能放入三个12x8x4的盒子的状态）。

我在实现这个算法时使用了随机最佳适应减少算法——首先按体积从大到小排序，然后按周长从小到大排序（因此更像立方体的盒子会首先排序，例如8x8x8的盒子会排在4x8x16的盒子前面）。然后，我通过为每个盒子分配一个排序键等于Random.nextFloat(1.0 / (itemIndex + 1))来随机化此盒子队列，例如第一个盒子将具有介于0和1.0之间的排序键，第二个盒子将具有介于0和0.5之间的排序键，依此类推。同样，在插入盒子后分割容器时，我倾向于将容器分割成大小差不多的子容器（即周长最小的分割），但包括一个随机因素，以便偶尔生成一个大的子容器和两个小的子容器。

然后我并行运行了十几次，并选择了最佳结果。但请注意，我的任务只是提供一个估计值——算法的一致性和速度比准确性更重要。

我考虑过的一种更复杂但更精确的算法是极端点算法。我选择吉尔廷切割算法是因为它更快且更易于实现/维护。