三维装箱算法

Question

我面临一个三维装箱问题，目前正在进行一些初步的研究，以确定哪些算法/启发式方法目前产生了最佳结果。由于该问题是NP难的，我并不期望在每种情况下找到最优解，但我想知道：

1）最好的精确求解器是什么？分支定界算法？使用合理的计算资源可以解决什么样的问题实例大小？
2）最好的启发式求解器是什么？
3）有哪些现成的解决方案可用于进行一些实验？

- BuschnicK

---

你正在将盒子装入盒状容器吗？你能旋转盒子使它们适合吗？ - Jason Orendorff

Karpreduction，跳过未解决的步骤（“perfect”）同构肯定棘手，但我们可以。 - Niklas Rosencrantz

https://dev59.com/fnI_5IYBdhLWcg3wBuNs - Brad Gilbert

不旋转。是的，我正在将盒子装入盒形垃圾箱中。谢谢Brad，我知道那个问题，但没有找到令人满意的答案或问题。 - BuschnicK

BK，我刚刚查看了我们的MaxLoadPro版本。您可以定义自己的“车辆”或“容器”，并且不受任何预定义尺寸的限制。当然，该软件使用启发式算法，但它确实允许您在推荐解决方案后移动物品。 - Grembo

Answer 1

就现成的解决方案而言，请查看MAXLOADPRO以装载卡车。它可以配置为加载任何矩形体积，但我还没有尝试过。一般来说，三维装箱问题的复杂性在于物体可以旋转到不同的位置，因此对于具有给定长度、宽度和高度的任何物体，您需要创建三个变量表示每个位置，但在解决方案中只使用一个。

一般来说，独立的MIP公式（或分支和限界）不适用于2D或3D问题，但约束编程已经在2D问题的确切解决方案方面取得了一些成功。请查看这个abstract。没有查看论文，我喜欢问题的分解方法，其中您正在试图最小化相同大小的垃圾箱数量。我还没有看到关于3D问题的太多结果，但如果您发现可实施的结果，请告诉我们。

祝你好运！

- Grembo

Answer 2

我已经编写了一个程序，测试了三种不同的算法。同时，这里还有一份很好的信息来源：在限制为二维矩形的情况下如何将物品装箱 - 实用的方法。虽然这是针对二维矩形装箱的，但你总可以将其转化为三维。

- Kris

Answer 3

来自 维基百科:

虽然这些简单策略通常已经足够好，但已经证明了高效的近似算法，可以在输入量足够大时以任何固定比例解决填充问题的最优解。

以下是它们提供的两个来源：

• 近似算法
• 线性时间内可解决填充问题

- BlueRaja - Danny Pflughoeft

---

请注意，“1 + ε”论文至少是指一维装箱问题，而问题是关于三维装箱（我假设是箱子）。简单的策略可以轻松地推广到三个维度；我不确定更复杂的策略。 - Jason Orendorff

（我猜是木盒子）-接近但不完全正确。我处理的是将木梁压合成更大的梁和形状的木桁架。由于压合过程是生产中最耗时、最昂贵的部分，所以问题是如何在机器上最优化地加载。 - BuschnicK

Answer 4

最佳精确求解器：使用动态规划。

状态变量：

1. 你已经打包和丢弃的物品。
2. 容器中填充的空间。

如果容器是一个长方体网格，而物品“适合”于网格的确切单元格中，则可以使用三维数组表示状态变量2。否则，您将不得不使用更复杂的数据结构。

最佳启发式求解器

我不知道。也许可变邻域搜索。你的问题与时间表构建问题之间存在一些相似之处（我正在研究这个问题），因此相同的启发式方法可能对两者都有好处。

现成的解决方案来进行实验

很抱歉，我甚至没有头绪。

- isekaijin

---

更复杂的数据结构有哪些例子？ - Kasparov92

Answer 5

你的问题与以下类似： 3D装箱算法

尽管如此，由于你不允许旋转，你可以得到相当不错的结果。我建议更加倾向于使用首次适应减少算法。

- user320450

Answer 6

3d物品装箱是一种商业解决方案（不是算法），提供了一个很好的可视化API。它提供以下功能：

• 单个箱子装箱
• 多个箱子装箱
• 查找第三维度
• 查找箱子尺寸

- hdoghmen