3D Bin Packing (eb-afit)

最近使用 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 输出。这个工具在调试过程中起了不小的作用。

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

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

   

   Figure 1: 坐标轴方向与尺寸

2. 向 y 轴装箱的步骤 (exec-iteration-on-pallet-variant) 如下
   1. 每一层开始前，需要选定一个层厚
      • 我们会列举所有可能的层厚（根据所有箱子的所有尺寸得到）并计算这些层厚的权重值，按权重依次遍历每个层厚作为第一层进行装箱，最终取效果最好的方案 (list-candit-layers)
      • 对于后续的层厚，同样使用剩余 y 方向余量及剩下未打包的盒子获取所有可能的层厚，计算权重后取权重值最小的（也即最合适）的层厚 (find-layer)
   2. 层厚选定之后，将开始进行该层的装箱操作 (pack-layer)，每层结束之后，会进入下一层
      • 实际进入下一层前，会判断本层有没有触发 layer-in-layer 模式，简单来说就是这一层某一个盒子高出了最初选中的层厚，这种情况，会产生一个夹层，其高度是最高的盒子的摆放高度减去最初选中的层厚，而 z 轴长度取决于最开始触发条件那个盒子的位置

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

   

   Figure 2: 单层装箱拓扑

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

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

   2. “合适”的箱子需要满足能塞进凹槽，“最合适的”箱子需要考虑箱子与凹槽的匹配度 (find-box)
   3. 注意，合适的箱子有两类
      • 一类是高度满足此层最初选定的层厚
      • 一类是它高于最初选定的层厚，这种情况它装完后，会在 z 轴“下方”形成一个夹层，在继续往 z 轴方向装完次层，进入下一层前，我们需要将这个夹层当作一个容器进行一次装填
   4. 每个箱子填充后要更新两份信息 (apply-found-box-to-pack)
      1. 该箱子放置坐标
      2. 该箱子填充凹槽之后，当前层的拓扑（即更新 scrap-pad）
   5. 放置箱子时会让其贴近凹槽较高的一边，如图 2 中，新放置的箱子将贴近左边
   6. 另外，如果某个凹槽没找到“合适”的箱子，将直接忽略该凹槽 (apply-ignore-gap)

下面是 2023-06-23 版本的一次执行产生的火焰图：

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

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

同时，也可以注意到 find-box 中 Map 的 assoc 和 get 操作占据了大部分计算，这个提交对其进行了优化，最终对于 mpp05.txt 这份数据，执行时间从 28s 降到 11s 左右，下面是优化之后的火焰图：

在项目根目录执行 clj -X:test :dirs '["envs/test/"]' 可以得到部分数据的执行结果及其执行时间。

另外，浏览器中（https://lotuc.org/bin-pack）执行时间比本地还是慢上一些。