我该如何以程序方式确定如何将较小的盒子装入较大的包装箱中？

Question

我该如何以程序方式确定如何将较小的盒子装入较大的包装箱中？

algorithmbin-packing

51

有没有现成的软件或算法可以计算多个项目的运输包大小？

我们的库存数据库中有许多定义了长度、宽度和高度尺寸的物品。根据这些尺寸，我需要计算购买的物品可以适合预定义的盒子尺寸中的多少。

- polara

有趣的问题。起初我在考虑如何计算每个物品的面积与盒子可用空间的比例，但是当你有不是完美立方体的物品时，这种方法并不适用...你可能会在盒子里留下空间，但那并不是可用空间。嗯... - Kevin Fairchild

顺便感谢Rich B改进了这个问题的标题，特别是像最近的SO播客一样添加了“以编程方式”。 - polara

8个回答

19

"三维装箱"的文献非常广泛。您可以跟踪David Pisinger教授的出版物，以获取良好的概述。他还发布了一份高质量的装箱实现源代码：3dbpp.c 。

我的物流工具包pyShipping附带一个用于仓储应用的三维装箱实现。它基本上是实现了四维装箱（三维大小和重量）并在不到一秒的运行时间内为典型订单大小（数十个包裹）得到了可接受的解决方案。它已经在生产中（即仓库）使用数月，以确定要使用的运输箱的上限。仓库工人通常能够更有效地打包，但对我来说这也没问题。

- max

1

源代码链接已失效。 - Qwertie

嗨@Qwertie，我想我已经在这里找到源代码了：http://hjemmesider.diku.dk/~pisinger/3dbpp.c - R. McManaman

10

Pisinger是少数发布工作代码的学者之一。在他的一篇论文中，他提到了“最小深度”问题。

这里有一个实用且高效算法，可用于3D矩形盒子装箱，其调整了包围盒的高度。

这是php中的一个实现。

- TomEE

6

您是想知道特定尺寸的包装可以装下多少个同一类型物品，还是想混合不同类型物品？

听起来像是您正在尝试解决背包问题。您可能能够找到一些算法，可以根据您的具体要求进行调整。但请注意，很难找到一个高效的算法，因为这个问题是NP完全的（虽然根据您的具体要求，您可能能够找到一个高效的近似解，或者您的输入可能足够小，不会有关系）。

- Herms

您的描述和所引用的链接也是准确的。正如Arachnid提到的装箱问题一样，由于能够在盒子中侧放物品，可能会出现极其多样化的解决方案数量。 - polara

3

问题并不是背包问题的一个实例，这是原帖作者发布的内容。 - Michael Nett

4

如果要手动打包盒子，那么您可以考虑编写一个算法，使其执行与“合理”的人类相同的操作。我之所以建议这样做，是因为除非您想为每个订单打印包装说明，否则负责包装的人员将不得不确定他们将如何将订购的物品放入分配给订单的任意数量的盒子中。

这可能会导致您的人工包装人员来到 SO 并询问如何通过编程计算出如何将 n 个物品装入 m 个盒子中。:-P （他们也可能向您请求指示等）。

只要您的算法执行与合理的人类相同的操作，我个人会接受其运输估计。

- freespace

3

元启发式算法在处理实际的装箱问题时非常有效，特别是当存在许多包裹和/或许多约束条件时。一个开源的Java实现是Drools Planner。请参考Drools Planner。

- Geoffrey De Smet

2

也许这听起来很明显，但值得记忆的是，先将问题进行备忘，然后手工解决其中一些问题可能是值得的。对于任意输入和盒子找到最有效的解决方案是NP难的，但通过限制问题空间并接受一些低效率，NP大小可能会变得合理，并且通过备忘，您可能能够大大降低“常见情况”的时间。此外，以分层装箱的形式思考问题可能也有所帮助。

- Gregg Lind

谢谢。是的，Arachnid 也建议使用启发式算法。这个应用是为了计算运费，我可以想象一个完全自动化的解决方案会提出各种不切实际的安排。 - polara

0

在大量搜索之后，我找到了一个可能对某些人有帮助的GitHub存储库。函数PackingService.Pack()接受Container列表和要打包的Item（们）列表作为参数，并返回包含许多信息的结果，包括：

"以百分比表示的已打包容器和已打包和未打包项目的列表"

- Ammar

1

尽管这个链接或许可以回答问题，但最好在这里包含必要的答案部分并提供链接作为参考。仅有链接的回答如果链接页面发生变化可能会失效。 - Ruzihm

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

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

- Arachnid · Accepted Answer

这是一个装箱问题，它是NP难的。对于少量的物品和包裹，可能可以简单地使用试错法来尝试每种可能性。在此之后，您将需要使用某种启发式算法。维基百科的文章有一些细节，以及您可能想要查看的论文参考。

当然，另一种选择是从一个非常简单的算法（例如简单地“堆叠”项目）开始，并计算出使用该算法的合理上限运输费用，如果您的人工包装员能做得更好，那么您就会获得微小的利润。或者在假设您的包装不理想的情况下稍微降低计算出的价格。