基于深度强化学习的四向协同三维装箱方法
基于深度强化学习的四向协同三维装箱方法
随着互联网的普及和人们消费能力的提高，网络购物进入高速发展时期。网络购物带来的物流需求激增，为物流行业带来新的挑战，如何提高物流效率成为研究者关注的重点。三维装箱问题（Three-dimensional bin packing problem, 3D-BPP）作为物流的基本组成部分之一，是运筹学和计算机科学领域的一类组合优化问题，主要探讨在特定的约束下，将一系列给定尺寸的长方体箱子装入一个或多个给定尺寸的长方体容器中，以最大程度地提高容器的空间利用率。
图 1 3D-BPP在物流中的应用场景
作为一种多维组合优化问题，3D-BPP因其强意义上的NP-hard性质难以在数学上采用精确算法在规定时间内求取最优解，尤其是对于大尺寸容器或多箱子种类数的离散装箱问题。因此采用精确算法求解3D-BPP的相关研究较少，主要集中在分支定界、动态规划、整数规划等方法上。
在过去的较长一段时间内，启发式三维装箱（Heuristic-3DBP）方法成为3D-BPP领域的研究热点。Heuristic-3DBP方法通常寻找装箱问题的近似最优解，在可接受的时间内求取可行解的概率远高于精确算法。早期有First-fit、Extreme point、Deepest bottom left、Largest area first-fit、Empty maximal spaces等方法被提出，近几年也出现了一些如两阶段层构建等新的Heuristic-3DBP方法。张德富等提出通过找点法和水平垂直参考线规则来控制装箱过程。何琨和黄文奇结合捆绑策略和Empty maximal spaces思想，提出一种基于动作空间的改进型穴度算法。以上方法能够在给定时间内有效处理各自场景下的装箱问题。
不过，Heuristic-3DBP方法通常依赖专家预先设计的手工规则，不具备普适性，而且Heuristic-3DBP方法是基于经验和直觉的，可能受到人类主观意识和认知偏差的影响，在解决复杂装箱问题时可能无法提供全局最优解。
进一步，研究者提出使用元启发式算法或其他搜索算法来处理装箱问题，以提高算法求取全局最优解的能力。在元启发式算法方面，遗传算法、蚁群算法、模拟退火、禁忌搜索等算法均被广泛用于装箱问题的求解。在其他搜索算法方面，刘胜等在水平层构建启发式算法的基础上，采用树搜索法来搜索最优集装箱装载方案。Ren等、Zhu等和Araya等结合块构建启发式算法和树搜索法来解决实际约束下的集装箱装载问题。上述算法探索和评估了装箱问题解的搜索空间，提高了启发式算法求取全局最优解的能力。不过，在大尺寸容器和多箱子种类数的复杂装箱问题中，由于过于庞大的搜索空间以及可能发生的“组合爆炸”现象，这些算法有着较高的时间复杂度。
为提高算法的普适性和时间效率，研究者开始尝试使用深度强化学习（Deep reinforcement learning, DRL）。最早，Vinyals等提出一种基于学习的序列模型PtrNet（Pointer net）。Bello等以REINFORCE强化学习算法训练PtrNet以解决旅行商问题。此后，DRL被广泛应用于求解平面旅行商、最大切割、最小顶点覆盖、最大独立集和三维装箱等组合优化问题。在3D-BPP方面，最早的基于DRL的三维装箱方法（Three-dimensional bin packing method based on DRL, DRL-3DBP）由Hu等提出，该方法以PtrNet充当策略网络来生成装箱顺序，使用REINFORCE算法进行学习，在三维灵活装箱问题（Three-dimensional flexible bin packing problem, 3D-FBPP）上取得了平均容器表面积比Heuristic-3DBP低约5%的结果。但是，该方法依靠启发式算法决定装箱方向和位置，智能体无法观测全面的信息，难以学习到最优策略。
在Hu等工作的基础上，Duan等提出一种多任务选择学习（Multi-task selected learning, MTSL）框架，以近端策略优化（Proximal policy optimization, PPO）算法学习装箱顺序，以监督的方式学习装箱方向，相较于文献[31]进一步减少了平均容器表面积。然而，MTSL仍然由启发式算法指导装箱位置，无法实现完全端对端的学习，因此灵活性和全局优化能力仍然较弱。也有研究者提出使用DRL求解一些特殊的3D-BPP。例如，Verma等将DRL引入箱子信息不可完全观测的在线3D-BPP，使用深度Q网络（Deep Q-network, DQN）框架来学习实际机器人约束下的在线装箱策略。Liu等针对不规则物体的3D-BPP，提出一种基于DQN框架的智能装箱算法，根据不规则物体的三维点云数据优化装箱方案。
近几年来，研究者开始将注意力转向了端对端的DRL-3DBP。设计端对端的DRL-3DBP的难点在于3D-BPP固有的大规模动作空间，该挑战源于装箱顺序、方向以及位置的三种可能性相互乘积导致的巨大数量的可能解。为处理大规模动作空间问题，研究者设计了各式各样的方案。Li等首次提出一种端对端的DRL-3DBP：CQL（Conditional query learing），将每一步的装箱动作分解为索引选取、方向选取和位置选取三部分。策略网络按顺序分别生成三个子动作的策略，从而将每个子动作空间限制在较小范围。但这种三阶段的策略网络结构使得子网络之间必须传递信息并学习特征，增加了训练和推理的计算复杂性，加之CQL没有处理位置选取子动作的大规模动作空间，导致其在大尺寸容器装箱问题上的表现欠佳。
Jiang等在CQL的基础上引入了容器顶视图来增强状态表示，并使用动作表示学习来处理大尺寸容器带来的位置选取子动作的大规模动作空间，显著地提升了空间利用率。然而，动作表示学习涉及额外的监督更新规则，增大了计算开销。Zhang等设计一种单向装箱方法，通过REINFORCEE算法学习策略网络，只需生成箱子在一轴的位置便可实现其在容器中的定位。该方法显著减小了位置选取的动作空间，但它同时也牺牲了对大量合理位置的探索，限制了智能体行为的多样性，因此容易陷入局部最优解。Que等提出一种基于平面特征容器状态表示的DRL-3DBP，通过保留最大平面面积放置点对平面特征下采样，以此来压缩位置选取子动作的动作空间。该方法在大尺寸容器3D-BPP上达成的空间利用率高于现有其他算法，但所采用的平面特征下采样同样会使得合适的装箱位置被忽略，限制了智能体对部分合理位置的探索，从而影响方法性能。
针对现有端对端DRL-3DBP在处理大尺寸容器问题时存在的不足，本文提出一种基于DRL的四向协同装箱（Four directional cooperative packing, FDCP）方法。首先，策略网络接收剩余箱状态和4个旋转方向的容器状态，生成4个装箱策略；然后，根据4个装箱策略采样得到的动作分别转移至4个新状态，价值网络估计4个新状态的价值；最后，选取价值最大的新状态对应的动作为装箱动作。本文的主要贡献总结如下：
- 提出一种基于DRL的FDCP方法，通过旋转容器状态来鼓励智能体对4个方向装箱策略的探索，显著减小了位置选取动作空间，改善了现有压缩动作空间方法造成的计算开销大、探索能力低的问题。
- 设计一种用于FDCP的两阶段策略网络结构，即索引方向-位置选取策略。与三阶段策略网络相比减少了子网络间的信息传递和学习，从而降低了计算复杂性，进一步提升了装箱方案的空间利用率。
- 使用A2C（Advantage actor-critic）算法在多种箱子数量和容器尺寸的算例上训练模型，结果表明本文方法在20、30、50箱子数量的算例上的空间利用率比同类最优DRL-3DBP提升了2.9%、2.4%和1.2%。
图 2 笛卡尔坐标系与箱子属性
图 3 容器状态表示
本文提出一种基于深度强化学习的四向协同装箱方法，并对应设计了一种两阶段策略网络结构，以求解大尺寸容器和多箱子种类数的离散三维装箱问题。面对大尺寸容器带来的大规模离散动作空间，FDCP在压缩位置选取动作空间的同时，鼓励智能体对4个方向合理装箱策略的探索。实验验证表明，FDCP在大型容器和随机生成箱子信息的装箱问题中取得了先进的结果。未来的工作将专注于稳定性等实际约束下的三维装箱问题求解，高效且能够用于实际的离线或在线装箱算法将是后续研究的重点。