我怎样才能以编程方式确定如何将较小的盒子放入较大的包装中?

有没有人知道现有的软件或algorithm来计算运输多个项目的包装大小?

我在库存数据库中有一堆物品,长度,宽度和高度都是定义的。 鉴于这些尺寸,我需要计算有多less购买的项目将符合预定义的箱子大小。

这是一个Bin包装问题,而且是NP难题。 对于less量的对象和包,你可以简单地使用蛮力法来尝试每一种可能性。 除此之外,你需要使用某种启发式。 维基百科文章有一些细节,以及您可能想要查看的论文的参考。

当然,另一种select是从一个非常简单的algorithm开始(比如简单地“堆叠”物品),然后用这个algorithm计算一个合理的运输上限,那么如果你的人力包装商可以做得更好,你就可以获得一点利润。 或者假设你的包装不理想,可以稍微打折你的计算价格。

关于“3D Bin包装”的文献是广泛的。 通过跟踪David Pisinger教授的出版物,你可以得到一个很好的概述。 他还发布了源代码为3dbpp.c的bin包装的几个高质量实现之一

我自己的物stream工具箱pyShipping为仓储应用程序提供了3D Bin Packing实现。 它基本上实现了4D Bin Packing(3D尺寸和重量),并在第二次运行时为典型的订单尺寸(几十个包)获得了可接受的解决scheme。 它现在用于生产(即仓库)几个月,以确定要使用的运输箱的上限。 仓库工人通常能够更有效地装箱,但对我来说没问题。

你是否想要看看有多less单一types适合特定大小的包,或者你是否尝试混合types?

听起来像你正在试图解决背包问题 。 你可能会find一些适合你的具体要求的algorithm。 只要明白,很难find一个有效的algorithm,因为问题是NP完整的(尽pipe取决于您的具体要求,您可能能够find一个有效的近似值,或者您的input可能足够小,无所谓) 。

皮辛格是less数发布工作代码的学者之一。 在他的一篇论文中,他提到了“最小深度”问题。

这是一个实用和高效的三维矩形盒包装algorithm,用于调整封闭盒子的高度。

这里是一个在PHP中的实现。

如果这些盒子是手工打包的,那么你可以考虑写一个algorithm来做一个合理的人做的事情。 我build议这样做的原因是因为除非你想打印出每个订单的包装说明,否则无论谁在做包装,都必须制定如何适应订购物品的方法,订购。

这可能会导致你的人类包装工人来到这个问题上,如何编程地训练如何将n个物品打包成m个箱子。 :-P(他们也可能会要求这样做,要求你的指示等)。

只要你的algorithm做一个合理的人会做,我会亲自接受它的运输估计。

也许这件事我砍了最后几个小时可能会有所帮助: http : //github.com/yetzt/boxing

当有许多软件包和/或许多限制条件时,Metaheuristics可以很好地处理现实世界的bin包装问题。 一个开源的Java实现是Drools Planner 。

也许这听起来很明显,但可能值得记住这个问题,然后用手做一些。 对于NP-hard中的任意input和框,find一个最有效的解决scheme,但是通过限制问题空间,并接受一些低效率,NP的大小可能是合理的,通过记忆,你可能会把“常见的“时间大幅下降。

这也可能有助于考虑分层打包方面的事情。

经过很多search,我find了一个GitHub仓库,可以帮助别人。 函数PackingService.Pack()Container列表和要打包的Item列表作为参数,并返回包含大量信息的结果

“以百分比和包装和未包装物品清单包装的集装箱”

Interesting Posts