求助一个装箱空间利用率最优解或者类似的开源项目或者算法或者思路

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 1787 天前的主题，其中的信息可能已经有所发展或是发生改变。

大概的需求是：

已经货物 A，B，C 的尺寸分别为 10 * 10 * 4，3 * 20 * 20，8 * 12 * 20，数量分别为 40，30，20 个

如果把它装在 60 * 50 * 40 的箱子中，怎么个堆叠方式最省空间。

感觉这个问题变量太多会比较复杂，或者也可以简化成：

只有一个货物 A，尺寸是 10 * 10 * 4，装在 60 * 50 * 40 的箱子中，怎么个方式可以放置尽量多的货物 A。

大概就是这样子。

我能想到的算法就是。。。。。。想不出来。。。

在网上找了个类似的

https://www.searates.com/cn/reference/stuffing/

但这个不能自定义集装箱大小。因为这个链接打开比较慢，我就截图贴在下面了

货物

箱子

算法

装箱

10 条回复 • 2020-01-04 20:58:31 +08:00

111qqz

2020-01-04 16:47:44 +08:00 via Android

在三个方向上分别做背包(？

tmsdy0404

2020-01-04 16:49:39 +08:00

@111qqz 啥意思？？没懂..

111qqz

2020-01-04 16:57:42 +08:00 via Android

@tmsdy0404 可以搜一下多重背包。不过只是一点直觉，没仔细想(

Mohanson

2020-01-04 16:58:58 +08:00

装箱问题一般用遗传算法来解决

Mohanson

2020-01-04 16:59:33 +08:00

是遗传算法的经典应用场景之一

Mohanson

2020-01-04 17:01:04 +08:00

另外好像也可以模拟退火算法

Kirscheis

2020-01-04 17:36:28 +08:00 via Android

这问题是 OR 的经典问题，如果不允许自由旋转的话，搜索 3-dimensional cuboid packing problem 有真相。这个问题目前并没有完全解决，但是有可行的结果还不错的算法，比如 Computers & Operations Research. 36.10 (2009): 2801-2815。

如果允许旋转，那就困难了，我暂时没有听说过什么具体的办法，可以试试力学随机模拟，结果应该不会太差

tmsdy0404

2020-01-04 20:35:59 +08:00 via iPhone

@Kirscheis 感谢指导，我研究研究

tmsdy0404

2020-01-04 20:47:21 +08:00 via iPhone

@Mohanson 第一次晓得这个模拟退火算法，搜了下，万脸懵逼。。。

tmsdy0404

2020-01-04 20:58:31 +08:00 via iPhone

http://www.ic.unicamp.br/~fkm/publication/rotation.pdf

以上链接是 Computers & Operations Research. 36.10 (2009): 2801-2815