堆叠算法 - 在最小的区域内堆叠3D物体

Question

3

我正在尝试解决将物品堆叠成最方便的邮寄大小的问题。物品的大小和形状各不相同，所有物品的长度、宽度和高度都是已知的。

例如，客户可能会订购一个（长×宽×高）为200x100x10厘米的宽平板物品以及2个50x50x50厘米的立方体物品。如果我要打包，我会把宽平物品放在底部，两个立方体并排放在顶部。

是否有人有或知道一个相当有效的算法解决这个问题？甚至是一种解决这个问题的方法？我已经编码了整整一周，现在很晚了，我的大脑已经崩溃。我还没有绝望，但我只是想明天休息一天。

我设想的方式是创建一个表示3D空间的数组，每个数组元素代表该空间中1平方厘米的正方形。3D空间的长度和宽度将基于最长的物品和最宽的物品。然后，您只需从最大的物品到最小的物品进行操作，找到足够的“空洞”并填满它们。

虽然我确定会有一个数学公式更有效地完成这项工作。

有什么想法吗？

- user147791

首先，你需要定义你的限制条件：

- mbeckish

2

http://en.wikipedia.org/wiki/Bin_packing_problem - Tom Haigh

我正在尝试限制整体的音量。最终我会尝试创建一个立方体。 - user147791

你是否在制作自定义的盒子？如果没有，你能否使用一组定义好的盒子来放置物品？例如，物品a、b和c的面积为x，因此它们将适合于j号盒子。 - Justin Giboney

不，这些“盒子”实际上是随机形状的物品，我的想法是利用每个物品的长度、宽度和高度来形成一个类似盒子的对象，以便进行算法装箱。 - user147791

最近已经解决了球体的包装问题，这涉及到非常复杂的前沿符号计算...所有这些都是为了得出自然六边形堆积是最优的结论！ - Alexandre C.

4个回答

2

这不是一个简单的问题，我猜它甚至是 NP-hard。你似乎有一些好的想法！我建议阅读关于背包问题的理论和新思路，请点击背包问题了解更多信息。

- Jonas Elfström

2

我不认为这是琐碎的事情。我相信这个问题的适当名称是装箱问题，谷歌搜索结果显示有很多学术论文，但没有简单的算法（特别是在三维情况下，这正是你想要的）。

你实际上需要处理多少个物体？如果数量相对较少（即不是将数百个物体放入TEU集装箱中，而是将几个物体放入一个纸板盒子中进行Fedex运输），那么也许采用一种简单的暴力方法来寻找局部最优解可能是最好的方法。

- Brian Agnew

他的例子看起来很简单（三个盒子），但我不确定这是否是典型的，还是他只是使用一个简单的例子来演示概念。 - Kip

我需要向邮寄公司提供有关尺寸的规格说明，以便获取加入总费用的定价。 - user147791

1

我不是专家，但我认为目前不可能找到最优结果而不使用暴力方法，但我可以提供一些建议：

1）如果您从容器的第一个开始放置具有最大体积的物品，第二个最大物品放在第二个容器上，第三个最大物品再放在第一个容器上，以此类推，那么结果最多比最优结果差14％（或者是34％？我记不清了！）我曾在Paul Hoffman的书《唯独爱数字的人》中读过。

2）遗传算法应该会提供相对较好的结果，但需要牺牲一些性能。

此外，还有一些公司像Logen Solutions和MaxLoad正在做这种生意，所以如果你愿意付出代价你也可以使用他们的网络服务。

- Alix Axel

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

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

- High Performance Mark · Accepted Answer

第一条建议--离开键盘，停止编码，开始思考！

第二条建议--你提出的方法（先放最大的，然后放次大的）是一个被广泛使用且备受尊重的启发式算法。除非你需要打包大量物品或进行大量打包操作，否则不要过于关注执行效率，开发效率可能应该是你的首要任务。

第三条建议--Google搜索bin-packing，但请注意，这方面有大量的文献。

最后，不要那么肯定这里有一个数学公式 :-)