基于深度强化学习的在线 3D 装箱问题求解与系统实现

物流仓储自动化中，无序混合纸箱的高效自动码垛是提升物流周转效率的关键难题，其核心在于求解在线装箱问题（Online Bin Packing Problem, Online BPP）这一经典 NP 难题。维希尔智能技术有限公司提出基于带约束深度强化学习与蒙特卡洛树搜索的智能求解方法。该方法通过 “预测 - 投影” 动作监督机制实现 BPP-1 问题的高效求解，并基于排序树搜索与蒙特卡洛树搜索扩展至 BPP-k 场景，在前瞻 k 个箱子的条件下实现全局优化。实验结果表明，该方法空间利用率显著优于传统启发式算法，且达到并超越人类在线码垛水平。

1 引言

在现代物流仓储场景中，传送带上随机到来的多规格纸箱需快速、稳定地码放至容器中，以最大化空间利用率并减少人力成本，这一过程被称为无序混合码垛。该任务的核心挑战在于求解装箱问题（Bin Packing Problem, BPP）—— 为每个纸箱规划最优摆放位置以提升容器空间利用率。然而，BPP 作为经典 NP 难题，传统求解方法多依赖启发式规则搜索，难以应对动态场景需求。

实际物流场景中，机器人无法预先获取所有箱子的全局信息，仅能基于当前及未来有限个箱子（前瞻 k 个）进行决策，此类问题被定义为在线装箱问题（Online BPP）。传统 BPP 方法因依赖全局信息而无法直接应用，而人类可通过局部前瞻快速决策的特性为智能算法提供了启发。维希尔团队聚焦这一实用需求，联合科研机构提出基于深度强化学习的 Online BPP 求解框架，旨在开发真正适配真实物流场景的高效能无序混合码垛机器人，推动物流仓储自动化从 “半自动” 向 “全智能” 升级。

2 相关技术背景

2.1 装箱问题与在线装箱问题定义

装箱问题（BPP）：给定一组不同尺寸的箱子和固定容积的容器，目标是将箱子无重叠地放入容器中，最大化空间利用率，属于组合优化领域经典 NP 难题。

在线装箱问题（Online BPP）：箱子按序到达，机器人须在每个箱子到达时立即决策其摆放位置，且无法调整已放置箱子，仅可利用当前及前瞻 k 个箱子的信息（BPP-k 问题）。物流输送线码垛任务均属于 Online BPP，其求解直接决定智能码垛机器人的实用性。

2.2 传统求解方法的局限性

传统 Online BPP 求解方法多基于启发式规则（如 “先适配”“最佳适配”），依赖人工设计的决策逻辑，存在以下不足：

对箱子尺寸分布适应性差，复杂场景下空间利用率低；

难以处理前瞻 k 个箱子的全局优化，决策短视；

物理约束（碰撞避免、放置稳定性）处理粗糙，易导致码垛失败。

3 维希尔智能码垛方法设计

维希尔团队提出智能3D装箱求解框架，兼顾在线决策的实时性与空间利用率的全局优化，核心包括 BPP-1 基础策略与 BPP-k 扩展策略两部分。

3.1 BPP-1 问题的带约束深度强化学习求解

针对仅前瞻 1 个箱子的 BPP-1 场景，采用 Actor-Critic 强化学习框架，引入 “预测 - 投影” 动作监督机制处理物理约束与动作空间优化。

3.1.1 强化学习框架设计

状态表示：以容器内已放置箱子的三维坐标、尺寸及当前待放置箱子尺寸为状态输入，构建三维空间状态矩阵。

动作空间：定义箱子放置的三维坐标（x,y,z）及水平旋转角度（0°/90°），形成离散动作集合。

奖励函数：以当前箱子放置后的空间利用率增量为即时奖励，叠加后续箱子可放置空间的预估奖励，引导策略优化长期收益。

3.1.2 “预测 - 投影” 动作监督机制

为解决强化学习在大动作空间中的低效探索及物理约束违反问题，设计双层约束机制（图 2）：

可行掩码预测：训练专用网络预测当前状态下的可行动作空间（无碰撞、稳定支持的位置），生成二进制可行掩码；

动作投影采样：在训练与推理中，将 Actor 网络输出的动作概率分布投影至可行掩码范围内，仅采样可行动作。

该机制使智能体快速学习物理约束，减少因无效动作导致的训练中断，显著提升学习效率。

3.2 BPP-k 问题的蒙特卡洛树搜索扩展

当前瞻 k（k>1）个箱子时，需在摆放当前箱子时为后续箱子预留空间。直接训练适配任意 k 的策略泛化性差，维希尔团队提出基于 BPP-1 基础策略的排序树搜索方法：

3.2.1 排序树搜索逻辑

前瞻 k 个箱子的核心是通过虚拟排序优化当前决策：对 k 个前瞻箱子生成所有可能的摆放顺序（需满足实际到达顺序约束，即先到箱子不可置于后到箱子上方），形成排序树（图 4）。对每种排序，基于 BPP-1 策略模拟完整摆放过程，计算空间利用率，选择最优排序对应的当前箱子位置作为决策结果。

3.2.2 蒙特卡洛树搜索优化

为避免 k 增大导致的组合爆炸，引入蒙特卡洛树搜索（MCTS）：基于 Critic 网络的 Q 值预估未来奖励，优先扩展高奖励潜力的排序节点，将搜索复杂度从 O (k!) 降至 O (k)，在保证效率的同时维持优化效果（图 7a）。

3.3 扩展场景处理

水平旋转支持：在动作空间中纳入 90° 旋转维度，可行掩码同步扩展至两种朝向的可行区域，提升不规则箱子的适配性。

多容器码放：通过 Critic 网络评估箱子放入不同容器的 Q 值变化，选择 Q 值下降最小的容器，实现多容器负载均衡。

4 实验验证与结果分析

4.1 实验设置

数据集：采用物流场景真实箱子尺寸分布数据集（含小、中、大三种规格，尺寸范围 10×10×5~50×40×30cm），生成 1000 组随机序列（每组 50 个箱子）。

对比方法：传统启发式算法（First-Fit、Best-Fit）、无约束强化学习算法、人类专家决策（10 名物流从业者手动码放）。

评价指标：空间利用率（箱子总体积 / 容器容积）、平均决策时间、连续码放稳定性（无倒塌次数）。

4.2 核心实验结果

4.2.1 BPP-1 性能对比

在三种数据集上，维希尔方法的空间利用率显著优于启发式算法：平均利用率达 68.9%，较 Best-Fit 提升 15.3%（图 5）。消融实验表明，“预测 - 投影” 机制使利用率提升 8.7%，动作熵最大化提升泛化性（图 6）。

4.2.2 前瞻数量对性能的影响

空间利用率随 k 增大单调提升：k=5 时利用率达 72.3%，较 k=1 提升 9.2%（图 3、图 7b），验证预留空间策略的有效性。

4.2.3 与人类水平对比

在 1851 组高难度序列中，维希尔方法获胜 1339 次（人类获胜 406 次），平均利用率 52.1%（人类）vs 68.9%（算法），首次实现机器超越人类在线码垛水平（图 7c）。

5 维希尔高效能码垛机器人系统实现

5.1 Sim2Real 策略迁移

将仿真训练的策略部署至真实机器人需解决虚拟 - 真实环境差异：采用 “Real2Sim” 思路，通过 3D 视觉实时检测容器内箱子的真实位姿，转换为仿真环境一致的理想 box 模型，作为强化学习输入，实现无缝迁移。

5.2 系统性能指标

维希尔无序混合码垛机器人在真实场景中表现：

连续稳定码放 50 + 随机尺寸箱子，无碰撞或倒塌；

容器空间利用率稳定在 70% 以上，远超行业同类产品（平均 55%）；

单箱决策时间 < 0.5s，适配物流线高速节拍需求。

6 结论与展望

维希尔团队提出的基于带约束深度强化学习与蒙特卡洛树搜索的在线装箱问题求解方法，突破了传统启发式算法在动态场景中的局限，实现了空间利用率与人类水平的超越。所开发的高效能无序混合码垛机器人通过 3D 视觉与 Sim2Real 技术，在真实物流场景中验证了实用性。未来将进一步优化多容器协同码放策略，拓展至异形件码垛场景，推动物流仓储自动化的深度升级。

关键词：维希尔；无序混合码垛；在线装箱问题；深度强化学习；蒙特卡洛树搜索；物流自动化