3 维装箱算法
我面临着 3 维装箱问题，目前正在进行一些初步研究，了解哪些算法/启发式方法目前能产生最佳结果。由于问题是 NP 难问题，我不希望在每种情况下都能找到最佳解决方案，但我想知道：
1）什么是最好的精确求解器？分支定界？我可以使用合理的计算资源来解决哪些实例大小问题？
2) 最好的启发式求解器是什么？
3）有哪些现成的解决方案可以用来进行一些实验？
I'm faced with a 3 dimensional bin packing problem and am currently conducting some preliminary research as to which algorithms/heuristics are currently yielding the best results. Since the problem is NP hard I do not expect to find the optimal solution in every case, but I was wondering:
1) what are the best exact solvers? Branch and Bound? What problem instance sizes can I expect to solve with reasonable computing resources?
2) what are the best heuristic solvers?
3) What off-the-shelf solutions exist to conduct some experiments with?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
至于现成的解决方案，请查看用于装载卡车的MAXLOADPRO。它可能能够配置为加载任何矩形体积，但我还没有尝试过。一般来说，3D 装箱问题会增加复杂性，即对象可以旋转到不同的位置，因此对于具有给定长度、宽度和高度的任何对象，您实际上必须创建代表每个位置的三个变量，但只使用一个变量解决方案。
一般来说，独立的 MIP 公式（或分支定界）不适用于 2d 或 3d 问题，但约束规划已经取得了一些成功，为 2d 问题提供了精确的解决方案。查看此摘要。在不看论文的情况下，我喜欢解决问题的分解方法，即尝试最小化相同大小的垃圾箱的数量。我还没有看到那么多关于 3d 问题的结果，但如果您发现任何可以实现的结果，请告诉我们。
祝你好运 ！
As far as off the shelf solutions, check out MAXLOADPRO for loading trucks. It may be able to be configured to load any rectangular volume, but I haven't tried that yet. In general 3d bin-packing problems have the added complication that the objects can be rotated into different positions so for any object with a given length, width and height, you effectively have to create three variables representing each position, but you only use one in the solution.
In general, stand-alone MIP formulations (or branch and bound) don't work well for the 2d or 3d problem but constraint programming has met with some success producing exact solutions for the 2d problem. Check out this abstract. Without looking at the paper, I like the decomposition approach for the problem where you're trying to minimize the number of same-sized bins. I haven't seen as many results for the 3d problem, but let us know if you find any that are implementable.
Good luck !
我编写了一个程序来测试三种不同的算法。这也是一个很好的信息来源：一千种打包垃圾箱的方法 - 两种实用方法 -尺寸矩形箱包装。它适用于二维矩形箱，但您始终可以将其转换为 3D。
I've written a program which tests three various algorithms. Also this is a good source of information: A Thousand Ways to Pack the Bin - A Practical Approach to Two-Dimensional Rectangle Bin Packing. It is for two-dimensional rectangle bin, but you can always transform it to 3D.
来自 维基百科：
以下是他们为此提供的两个来源：
From wikipedia:
Here are the two sources they give for this:
最佳精确求解器：使用动态编程。
状态变量：
如果容器是平行六面体网格，并且项目“适合”网格的精确单元格，则可以使用 3 维数组来表示状态变量 2。否则，您将不得不使用更复杂的数据结构。
最佳启发式求解器
我不知道。也许是变量邻域搜索。您的问题和时间表构建问题（我正在研究）之间有一些相似之处，因此相同的启发式可能对两者都有好处。
进行实验的现成解决方案
抱歉，我什至不知道。
Best exact solver: Use dynamic programming.
State variables:
If the container is a parallelepiped grid, and the items "fit" in exact cells of the grid, you can use a 3-dimensional array to represent state variable 2. Otherwise, you will have to use more complex data structures.
Best heuristic solvers
I don't know. Perhaps Variable Neighborhood Search. There are some similarities between your problem and the timetable construction problem (which I'm working on), so the same heuristic might be good for both.
Off-the-shelf solutions to conduct experiments
I'm sorry, I don't even have a clue.
你的问题类似于：
3d装箱算法
尽管如此，因为您不允许旋转，您可以获得相当不错的结果。我建议更多地寻找“首次适应减少”的解决方案。
You question is similar to:
3d bin packing algorithm
Although, because you dis-allow rotation, you can get pretty good results. I suggest looking more towards a FIRST-FIT-DECREASING solution.
3dbinpacking 是一种商业解决方案（不是算法），它公开了一个 API，以便通过良好的可视化来使用。它提供：
3dbinpacking is a commercial solution (not an algorithm) exposing an API to consume with nice visualization. It offers: