3D 装箱

概述

最近使用 Clojure 实现了 Erhan Baltacıoğlu 文章The Distributer's Three-Dimensional Pallet-Packing Problem: A Human Intelligence-based Heuristic Approach中描述的三维装箱算法，代码仓库在：lotuc/bin-pack。

论文中的代码已经有人使用 c 语言实现:wknechtel/3d-bin-pack，本次也是将它作为参考实现，不过它只能在 windows 编译，为了方便，略作修改，移除了平台相关代码，推送在lotuc/3d-bin-pack:lotuc.

在这个参考实现中，有一份可视化代码，就没直接去修改，而直接使用 ClojureScript + three.js 重新实现了一个可视化工具，部署在https://lotuc.org/bin-pack. 它可以直接执行装箱算法并渲染输出结果（文本格式选成eb-afit input），另外，也可以选择eb-afit visualdot直接渲染参考实现的 c 代码输出的visualdot输出。这个工具在调试过程中起了不小的作用。

实现细节

整个算法的装箱过程和人工进行装箱时的过程比较类似，原文本身对于算法的解释已经比较详尽，这里对照本次实现列一下其装箱过程：

• 装箱总体过程是，一层一层向 y 轴方向行进，对于每层，x 轴作为“底边”，往 z 轴方向堆积；我们会遍历箱子/容器 (pallet) 每个摆放方式尝试 (exec-iterations) 取最好的那个结果。

• 向 y 轴装箱的步骤 (exec-iteration-on-pallet-variant) 如下

• 每一层开始前，需要选定一个层厚

• 我们会列举所有可能的层厚（根据所有箱子的所有尺寸得到）并计算这些层厚的权重值，按权重依次遍历每个层厚作为第一层进行装箱，最终取效果最好的方案 (list-candit-layers)

• 对于后续的层厚，同样使用剩余 y 方向余量及剩下未打包的盒子获取所有可能的层厚，计算权重后取权重值最小的（也即最合适）的层厚 (find-layer)

• 层厚选定之后，将开始进行该层的装箱操作 (pack-layer)，每层结束之后，会进入下一层

• 实际进入下一层前，会判断本层有没有触发 layer-in-layer 模式，简单来说就是这一层某一个盒子高出了最初选中的层厚，这种情况，会产生一个夹层，其高度是最高的盒子的摆放高度减去最初选中的层厚，而 z 轴长度取决于最开始触发条件那个盒子的位置

• 俯视二维平面中，可以认为 z 轴方向是“向上”的，每层的填装方式是依次找到最合适的箱子填充 z 坐标最低的那个凹槽。
  

• 俯视二维平面当前填充状态（拓扑）使用如图 2 中这些点即可表示，目前代码中是放在称为 scrap-pad 的 vector 中，如：

[{:cumx 8 :cumz 10} {:cumx 14 :cumz 5} {:cumx 18 :cumz 8}]

• “合适”的箱子需要满足能塞进凹槽，“最合适的”箱子需要考虑箱子与凹槽的匹配度 (find-box)

• 注意，合适的箱子有两类

• 一类是高度满足此层最初选定的层厚

• 一类是它高于最初选定的层厚，这种情况它装完后，会在 z 轴“下方”形成一个夹层，在继续往 z 轴方向装完次层，进入下一层前，我们需要将这个夹层当作一个容器进行一次装填

• 每个箱子填充后要更新两份信息 (apply-found-box-to-pack)

• 该箱子放置坐标

• 该箱子填充凹槽之后，当前层的拓扑（即更新 scrap-pad）

• 放置箱子时会让其贴近凹槽较高的一边，如图 2 中，新放置的箱子将贴近左边

• 另外，如果某个凹槽没找到“合适”的箱子，将直接忽略该凹槽 (apply-ignore-gap)

性能优化

下面是目前（2023-06-23）版本一次执行产生的火焰图

可以看到，目前calc-layer-weight仍然占据大部分近一半计算量，实际这部分在最初版本中占据了近 80-90% 的计算，最初的版本使用了 Clojure map 的 get-in 获取要计算的数据，另外，基本数据运算没有给定参数的类型，导致产生大量类型检查。

针对性，做了一些处理，开始使用 [clj-fast](https://github.com/bsless/clj-fast) 中的get-in替换了clojure.core版本，速度提升不少；不过，由于该函数是个性能瓶颈，最终将该函数计算所需数据使用 native array 存取，同时使用了 unchecked-* 运算符后，它的性能和 c 语言版本已经相差不大。

目前calc-layer-weight仍有部分优化空间，另外，find-box也可以考虑进行优化；不过总体来看，其性能已经满足期望（与 c 语言版本对比）。

文章转自https://zhuanlan.zhihu.com/p/639067617