40

我面临一个 3 维装箱问题，目前正在对哪些算法/启发式目前产生最佳结果进行一些初步研究。由于问题是 NP 难题，我不希望在每种情况下都能找到最佳解决方案，但我想知道：

1）什么是最好的精确求解器？分支和绑定？我可以期望通过合理的计算资源解决哪些问题实例大小？
2）什么是最好的启发式求解器？
3) 有哪些现成的解决方案可以进行一些实验？

4

6 回答 6

7

至于现成的解决方案，请查看用于装载卡车的MAXLOADPRO 。它可能能够配置为加载任何矩形体积，但我还没有尝试过。通常，3d 装箱问题具有额外的复杂性，即对象可以旋转到不同的位置，因此对于具有给定长度、宽度和高度的任何对象，您实际上必须创建三个变量来表示每个位置，但您只能在解决方案。

一般来说，独立的 MIP 公式（或分支定界）不能很好地解决 2d 或 3d 问题，但约束规划已经成功地为 2d 问题产生了精确的解决方案。看看这个摘要。在不看论文的情况下，我喜欢分解方法来解决您试图最小化相同大小的垃圾箱数量的问题。我还没有看到 3d 问题的很多结果，但是如果您发现任何可以实现的结果，请告诉我们。

祝你好运 ！

于 2010-02-03T16:05:11.993 回答
4

我编写了一个程序来测试三种不同的算法。这也是一个很好的信息来源：包装箱的一千种方法 - 二维矩形箱包装的实用方法。它适用于二维矩形箱，但您始终可以将其转换为 3D。

于 2013-06-03T07:38:08.940 回答
2

来自维基百科：

尽管这些简单的策略通常足够好，但已经证明有效的近似算法可以在足够大的输入的最优解的任何固定百分比内解决装箱问题

以下是他们为此提供的两个来源：

于 2010-02-03T14:35:22.283 回答
1

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

状态变量：

  1. 您已打包并丢弃的物品。
  2. 装满容器的空间。

如果容器是平行六面体网格，并且项目“适合”网格的精确单元格，则可以使用 3 维数组来表示状态变量 2。否则，您将不得不使用更复杂的数据结构。

最佳启发式求解器

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

进行实验的现成解决方案

对不起，我什至没有头绪。

于 2010-04-19T15:17:56.643 回答
0

您的问题类似于： 3d bin packing algorithm

虽然，因为你不允许旋转，你可以获得相当好的结果。我建议更多地寻找 FIRST-FIT-DECREASING 解决方案。

于 2010-04-19T15:09:41.270 回答
0

3dbinpacking是一种商业解决方案（不是算法），它通过漂亮的可视化公开 API 以供使用。它提供：

  • 单箱包装
  • 多仓包装
  • 查找第三维
  • 查找 bin 尺寸
于 2015-05-08T11:24:18.500 回答