我面临一个 3 维装箱问题,目前正在对哪些算法/启发式目前产生最佳结果进行一些初步研究。由于问题是 NP 难题,我不希望在每种情况下都能找到最佳解决方案,但我想知道:
1)什么是最好的精确求解器?分支和绑定?我可以期望通过合理的计算资源解决哪些问题实例大小?
2)什么是最好的启发式求解器?
3) 有哪些现成的解决方案可以进行一些实验?
我面临一个 3 维装箱问题,目前正在对哪些算法/启发式目前产生最佳结果进行一些初步研究。由于问题是 NP 难题,我不希望在每种情况下都能找到最佳解决方案,但我想知道:
1)什么是最好的精确求解器?分支和绑定?我可以期望通过合理的计算资源解决哪些问题实例大小?
2)什么是最好的启发式求解器?
3) 有哪些现成的解决方案可以进行一些实验?
至于现成的解决方案,请查看用于装载卡车的MAXLOADPRO 。它可能能够配置为加载任何矩形体积,但我还没有尝试过。通常,3d 装箱问题具有额外的复杂性,即对象可以旋转到不同的位置,因此对于具有给定长度、宽度和高度的任何对象,您实际上必须创建三个变量来表示每个位置,但您只能在解决方案。
一般来说,独立的 MIP 公式(或分支定界)不能很好地解决 2d 或 3d 问题,但约束规划已经成功地为 2d 问题产生了精确的解决方案。看看这个摘要。在不看论文的情况下,我喜欢分解方法来解决您试图最小化相同大小的垃圾箱数量的问题。我还没有看到 3d 问题的很多结果,但是如果您发现任何可以实现的结果,请告诉我们。
祝你好运 !
我编写了一个程序来测试三种不同的算法。这也是一个很好的信息来源:包装箱的一千种方法 - 二维矩形箱包装的实用方法。它适用于二维矩形箱,但您始终可以将其转换为 3D。
您的问题类似于: 3d bin packing algorithm
虽然,因为你不允许旋转,你可以获得相当好的结果。我建议更多地寻找 FIRST-FIT-DECREASING 解决方案。
3dbinpacking是一种商业解决方案(不是算法),它通过漂亮的可视化公开 API 以供使用。它提供: