技术的真相 | 机器学习在仓库控制中的探索：以某场景的排序问题为例 - 极术社区

作为新一代托盘柔性物流解决方案，旷视智能托盘四向车系统具有高密度存储、场地适应性强、扩展灵活、交付周期短等优势，能为实体企业提供具备更优投资回报比（ROI）的自动化、智能化仓储解决方案。那么，在智能托盘仓库又是如何被设计出来的呢？这背后运用了怎样的分配策略？本期《技术的真相》，让我们一起走进智能托盘仓库场景中的装车排序设计。

01 仓库中的决策问题

基于物品在仓库中的流动可以被分为不同的生产过程：收货、存储、订单拣选、装车。在这些仓库生产过程中有着很多的决策问题。比如，在收货过程中，需要一个分配策略决定送货卡车对道口的分配；在存储过程中，需要储位分配策略决定物品放置的储位；如果存储系统有前置区和保留区之分，还需要有补货策略决定何时向前置区补多少量；在订单拣选过程中，可能需要组单策略来提升吞吐效率；如果是组单拣选的，又必须要有分拣过程，订单通过通道分配策略被分配给分拣机道口；在装车过程中，仍有装车卡车和订单对道口的分配策略。在所有需要将任务分配给人或机器的问题中，都需要分配策略来分配任务。

这些的决策问题，一般是 NP 难的。在传统的求解方法中，很难在短时间内得到精确解。本文以某场景的排序问题为例，探讨从传统方法到机器学习求解的过程。本文先介绍近几年机器学习解决决策问题的进展，然后介绍某场景的排序问题，以及这类排序问题以往研究，最后介绍使用的各种方法包括机器学习的方法求解这个问题，并展望使用机器学习解决复杂决策问题的未来。

02 机器学习与决策

决策问题大多数情况下都是涉及到决策顺序，即序列的决策问题，例如TSP问题、VRP 问题。复杂场景下的决策问题，一方面可能会太过昂贵，过于依赖专家决策或者计算代价太大；另一方面可能会太过简单，过于依赖启发式策略。由于现在深度学习(Deep Learning, DL)和强化学习(Reinforcement Learning, RL)技术的突飞猛进，我们可以借助 DL 和 RL 来直接求解决策问题。

机器学习的本质是学习或理解数据的结构或模式。所以，对于通过历史中决策生成的特征和目标数据，至少我们可以通过机器学习的方法做出近似于专家或已知模型的决策。另外，我们也因此希望能利用还未充分利用的知识，依靠强化学习框架，得到更好的决策模型（最大化回报）。

利用机器学习求解决策问题最直接的想法就是直接训练机器学习模型从而输出决策方案，即一个端到端的学习(End to End Learning, E2E)。端到端的学习可以理解为启发式的，同时它可以利用强化学习技术达到或接近最优化的效果。

深度神经网络通常将求解求解决策序列问题的模型称为Seq2Seq模型。其求解方法基本上都属于 Encoder-Decoder 方法。其中，Encoder 称作编码器，其作用是将现实问题转化为数学问题；Decoder 称作解码器，其作用是求解数学问题并转化为现实世界。

在这方面，已经有了一些研究。指针网络(Pointer network)被发明用于解决TSP这类序列决策问题。它利用 seq2seq 模型通过端到端的方式，同时在 encoder 和 decoder 之间，嵌入了 attention 结构。Bello 基于指针网络，使用了强化学习的训练方法，比监督的方式能找到质量更高的解。Kool 介绍了一种借助 Transformer 架构，使用 GNN 取代 RNN 来处理输入。其中，Transformer 网络结构完全由 Attention 机制组成 Encoder-Decoder结构。Attention 机制模仿了生物观察行为的内部过程。它作为一种机制，它的核心点在于更加关注重点，从而简化模型和优化算法。

03 Case study：某托盘仓库场景的装车排序问题

3.1 问题介绍

‍某托盘智能仓库有出库排序的需要。它具体指的是在装车阶段，各车装车完成后的各 SKU 箱子需要集中码放，即装车的箱子序列每 SKU 的箱子连续，不存在同一 SKU 的箱子在序列中隔有其他 SKU 的箱子。

其中：

每个载货托盘只有 1 个 SKU 的箱子。
仓库有多个楼层，每个楼层有非常多的储位存放托盘。
提升机连接各个楼层。
出库站点分为整托出库站点和拆零出库站点。整托出库指的是将整个托盘在存储区出库后通过托盘线直接运送至整托出库站进行拣选后装车。拆零出库指的是在托盘在存储区出库后将托盘运送至拆零出库站进行拣选，再通过分拣系统分拨给各车装车。整托出库比拆零出库的拣箱效率明显要高。
整托托盘不会有返库行为。
每个卡车的装箱顺序来自整托出库站点的拣选箱线和拆零出库分拣后的通道箱线的合并。

我们假设：

提升机不是出库的性能瓶颈
拣选能力是一定的
各设备运行带有一定的随机性
出库订单是提前知道的
这里不考虑设备异常情况。

图1: 某托盘智能仓库。其中，紫色框（右边）为储位；中心为红十字的白框（中间）是提升机，由上到下一共 8 个，第 2～5 个通过托盘线连接拆零机械臂，第 6～8 个通过托盘线连接整托机械臂；粉色长框（左边）为卡车，整托机械臂拣选后的箱子和拆零机械臂拣选后通过缓存箱线的箱子会送至卡车内。

3.2 分拣与排序简介

如果批次拣选或者分区拣选存在的话，通常我们还需要去切分批次和按照客户订单合并物品。这个过程叫做 Order Accumulation/Sorting(OA/S)。按照Bozer 的定义，OA/S 系统一般分为两类：大量的小订单(OA/S-1)与小量的大订单(OA/S-2)。其中，OA/S-1 和 OA/S-2 可能同时存在在一个仓库。如下图，OA/S-1 在 split-case 拣选后用于来区分打包，OA/S-2 在码垛后用于区分发车。通常，我们的研究都指的是 OA/S-1。

图2: OA/S-1 和 OA/S-2 在同一仓库中的例子

OA/S-1 系统一般由累积输送线、再循环输送线、通道和分拣器组成。要装载到（一定数量的）通道的一组订单形成一个波次，从拣选区中拣选。为了高的订单拣选效率，同一个订单的物品可能来自不同的拣选者（人或机器）。在拣选后，物品会被放在分拣系统。由于拣选者的差异，物品到达分拣系统的时间点带有一定的随机性。物品或者被分配给某个通道（通道已被指派给某个订单），或者进入再循环输送线。当通道上的订单被完全满足时，通道会被释放以用于下次的分拣。

在 OA/S-1 中，通道数量会小于最小粒度订单总数。这里的最小粒度订单总数指的是同总订单 id（即同用户id）和同最小分拣粒度 id（sku、item、部门、所有）的共同总数。当有通道可用时，一个最小粒度订单可以被分配给一个通道。当这个最小粒度订单完成后，这个通道被释放。如果到达物品没有可用通道，就会进入再循环输送线。当然，再循环输送线也可用于积累订单物品。

在 OA/S-1 中，为了同步拣选和平衡拣选负载，当前拣选波次（或时间窗）内只拣选制定的最小粒度订单集合。

如果在分拣中还要求在最小粒度订单中物品的排放顺序按照当前粒度更小的粒度，这就是排序的需求，我认为它本质上和分拣是一回事情。但是，它比分拣要困难很多，因为它要在更小粒度上连续，但又不能以这个更小粒度释放通道，增加了拥堵程度。实际上，排序需求对波次的产生提出了更高的要求。

回过来我们在看我们之前给出的场景，它实际上更加复杂。因为它不仅分别要求了整托出库的排序和拆零出库的排序，而且更要求整托出库和拆零出库一起是排序出库的。

图3:OA/S-1 的一般表示

3.3 历史文献

关于 OA/S 系统的研究还是相对有限的。Bozer 和 Sharp 研究了再循环和非再循环的分拣系统中的不同的设计因素和控制策略。他们在通道满足所有订单分拣的情况下，通过仿真分析了通道容量、通道个数、聚集现象与分拣效率的关系。

Bozer 通过仿真分析了波次属性、通道数量、订单-通道分配策略、波次释放策略对再循环的分拣系统中分拣效率的影响。其中，在波次容量相同的情况下，每波次订单越小分拣效率越高；通道数越大（不超过订单数），分拣效率越高；“Incidental assignment”（动态分配）的订单-通道分配策略被作者推荐。

Johnson 开发了再循环分拣系统的拣选时间的分析模型。他比较了两类通用的分拣策略（订单-通道分配策略）：FPS 和 NAR。FPS(fixed priority schemes)指通过某种量度预先排序订单；NAR(next available rule)指不使用预先序二使用当前系统信息。显然前面所说“Incidental assignment”属于此类。这个分析模型和仿真结果都显示后一种策略明显优于前一种。

Meller 开发一个算法来优化再循环分拣系统中通道分配问题。他把订单分配策略作出整数规划的定义，通过约束通道容量等要素，求解所有再循环物品最大时间的最小化。

综上，分拣系统的吞吐能力不仅依赖于设备能力，而且也依赖于操作策略，更依赖于波次属性。更确切地说，分拣时间不是一个关键指标，而恰当地将订单切分出波次，从而在减小再循环等待时间和增加拣选效率之间平衡才是最有意义的事情。同时，在排序需求的基础上，我们的可用通道数量在动态上有可能远小于实际通道数量。这就要求我们的波次考虑的更加全面。

04 Case study：我们的解决方法

4.1 初始动机

装车箱子序列来源于两个方向：整托拣选和拆零拣选。如果要求同一 SKU 箱子序列连续，应保证当前 SKU 的整托拣选和拆零拣选两方向的到达时间相近，使得相互等待的时间最小。

同时，对于拆零拣选，为了四向穿梭车子仓的效率，应尽量提总后出库。这是因为提总后才能最大的减少四向穿梭车的出库吞吐。但这也就意味着，如果不同车都需要同一 SKU 的箱子，应使得不同车对此 SKU 的箱子的到达时间相近。

综上，我们可以通过控制一个仓库整体出库 SKU 的序列，来达到排序的目的。

但是，为了出库效率最优，我们不可能将出库 SKU 的序列完全串行化作业，这样会造成资源的浪费。其中，资源包括整托出库站、拆零出库站、四向穿梭车。所以，我们需要当前时刻存在一个 SKU 子序列，使得资源应尽量被利用。同时，SKU 子序列内部的 SKU 排序可以通过出库车辆延迟决策、托盘线缓存、箱线缓存、运力分配、提升机任务分配等“微操”来完成。这样，问题转变成尽量使得资源被占用的前提下，输出一个 SKU 子序列的序列，使得“微操”难度最小，来达到排序的目的。

还有，为了四向穿梭车子仓的效率，我们本应考虑运力空驶代价。但因为业务上设计整托托盘不会有返库行为，这也意味着整托托盘楼层的运力空驶代价本质上不因排序而变化。而散托托盘业务上往往只有 1 托，因此我们在此问题上不考虑空驶代价。

“微操”的一些原则在历史文献中有些讨论。以下，我们只讨论 SKU 序列的生成问题。同时，四向穿梭车仓库中，SKU 对应托盘之间可能存在出库顺序的依赖关系，从而 SKU 之间可能会存在依赖关系。我们讨论的 SKU 序列只会将不被依赖的 SKU 或 SKU 组（组内相互依赖）中的 SKU 当作候选 SKU，并从中挑选。

4.2 求解方法一：基于资源利用效率的贪婪决策

每次决策当前时刻的一个 SKU 子序列，是没有后效性的。因此，整个决策过程实际上是一个马尔可夫决策过程。但是，由于当前不能充分采样以及对问题的简化，我们的决策先只考虑当前最优状况且对波次衔接进行简化处理。

在决策过程中，我们按照资源的优先级先考虑整托出库站，再考虑零拣出库站，最后考虑四向穿梭车。

1. 子问题一：在考虑整托出库站时，我们应在覆盖掉所有整托出库站的前提下，尽量使得 SKU 子序列的个数最少，或者尽量使得逆序托盘数最少。其中，逆序托盘指的是 SKU 子序列的如果排序后面的箱子先到而需要先进行缓存的托盘。

那么，问题就转化为二部图模型。其数学定义如下：

设 G 为二部图<X, E, Y>，其中 X 表示整托出库站集合，Xi 表示整托出库站i；Y 表示出库命中 SKU 集合，Yj 表示 SKU j；E 表示整托出库站与 SKU 的关系，Eij 表示 SKU j 需要出库至整托出库站i，当 E 为有权边时，其权值为 SKU j 需要出库至整托出库站 i 的托盘数。

此问题不同构于最小点覆盖问题。本问题实际上是选择尽量少的右边点，覆盖掉左边点。其中覆盖是指当右边点被选择时，与它相连的左边点认为被覆盖。此问题是 NP 难问题。最直觉的求解方法是贪心方法。即尽量选择右边点集中剩余度数最高的右边点。

子问题二：在考虑拆零出库站时，我们应在覆盖掉所有拆零出库站的前提下，尽量使得总逆序代价最少。其中，总逆序代价包括整托出库的逆序托盘代价和拆零出库的逆序箱子代价之和。

设 SKU j 的拆零托盘数为 cost[j]，总逆序代价为 weight[j]，s[j]表示是否选择 SKU j，其问题与典型 0-1 背包问题同构，使用动态规划求解。

4.3 求解方法二：类网络流模型

方法一在仿真中取得了比较好的效果。但是，它有其天然的缺陷，那就是它总是偏好整托相比拆零更多的 SKU，导致作业前后并不均衡。所以，我们有了将整托和拆零整体考虑的初衷。

我们可以抽象成一个网络流模型 G={V, E}。其中，V 除了源点 S 和汇点 T 外还包括：表示各 SKU 的点、表示各整托机械臂的点、单独表示零拆机械臂的点。E 中边包括：由 S 向各 SKU 的点的边，表示是否选中当前 SKU，其代价为固定代价 sum#j{cost[j][i]}；由各 SKU 的点到各整托机械臂的点的边，表示选中当前 SKU 可以覆盖当前整托机械臂，其容量为 1，其代价若机械臂空闲为-cost[j][i]，否则为 0；由各SKU的点到拆零机械臂点的边，表示选中当前 SKU 可以覆盖多少拆零机械臂容量，其容量为 p#j，其代价为 0；由各整托机械臂的点到 T 的边，表示整托机械臂需求，其容量为 1，代价为 0（进一步可以为当前站点工作情况）；由拆零机械臂点到T的边，表示拆零机械臂需求，其容量为拆零机械臂托盘需求 P，代价为 0（进一步可以为拆零机械臂工作情况）。

图4: 类网络流模型的图形化表示

我们追求最大流动，此时满足覆盖各空闲整托机械臂和空闲拆零机械臂。同时，在此基础上，我们追求最小代价，即在满足需求的前提下，使得子仓排序微操难度最小。

但是，因为由 S 向各 SKU 的点的边的代价为固定代价。它不能用经典的 MCMF 的相关算法求解。实际上，它是 NP 难问题。即使这个网络实际上是个二部图。它被 Garey 和 Johnson 列为 NP-hard 问题列表的 ND32。在 S.O. Krumke 的论文中有讨论近似解法，即最大容量不变，代价为固定代价除以最大容量，然后按 MCMF 问题求解。但是，经过测试，这样产生的近似解并不好。

所以，我们转化为整数规划问题，通过求解器求解。其形式化定义如下：

图5: 类网络流模型的形式化定义。其中，y 表示 s 到 SKU 侧（共 m 个）的各边，x 表示 SKU 侧到站点侧（共 n+1 个，对应 n 个整托机械臂和拆零机械臂整体）

4.4 求解方法三：深度强化学习

我们前面的方法因为做了问题简化，仍有两个缺陷：

只考虑当前最优，没有考虑决策对很长一段时间之后的作业情况的影响
对波次的衔接考虑得非常生硬，不能精确地预测一段时间后的作业情况

我们可以使用 DL+RL 的方法来设计完全端到端的神经网络，在自动地学习到隐含的启发式信息，尽可能地达到与类网络流模型相近的效果。然后，再通过同构仿真得到的真实数据去 fine-tune，利用还未了解的不确定性因素和未知因素，得到更优决策。也就是说，我们可以通过两阶段学习，达到既计算代价小又优于专家决策的目的。其中，第一阶段为模仿学习，第二阶段为微调优化。

我们对方法二中整数规划的形式化定义，可以转化为找到当前总代价最小的对应SKU 子序列的问题。其中，总代价为优化代价和惩罚项，其中惩罚项为不满足约束条件的惩罚。

同时，我们可以通过图(Graph)来描述这个问题的上下文信息。SKU 作为图中的结点(Node)，连接结点之间的边(Edge)描述 SKU 之间隐性关系。其中每个顶点都有自己的特征来描述种种属性，包括对各站点的分配关系等等。在Transformer网络中，Encoder部分实际上就是对问题的编码(Embedding)。

4.4.1 模型结构

该问题的解决方案是一个 SKU 子序列。在当前时刻，它可以看作是一个连续决策问题，即决策选择下一个 SKU 追加到整仓序，直到资源不再无效空闲。我们将这个问题定义为一个有 n 个点的全连接图，其中点 i 由特征 xi 表示。其中 xi 包括：

SKU 对各个目标货车的分配关系，包括整托托盘数和整箱数
SKU 对拆零机械臂的分配托盘数
SKU 对每楼层的分配托盘数，节点之间的关系由GAT隐形表达

同时，该问题的输入是 SKU 集合、SKU 辅助信息和其他信息，输出是 SKU 序列，所以我们可以使用 Encoder-Decoder 架构来求解。它先用 Encoder 根据输入信息 SKU 与各站点、各机械臂、各楼层的关系，经过 GAT 得到 SKU 的特征 x，经过一系列处理，再用 Decoder 迭代地选择某个点也是某个 SKU，来构造解 y(y1,y2,…)。其中，在构造解的过程中，Decoder 是按照某种策略 p(y|x)在带掩码掩住前面已选点的前提下预测剩余每个点被选择的概率分布。实际上，针对本问题，其预测的上下文信息还应包括当前整体作业的作业情况。因此，当假设为策略 p 的参数，我们最终得出以下公式：某一个解决方案 y(y1,y2,…)的条件概率的对数等于所有得出 yi 的条件概率的对数之和。而我们知道其对数概率与对应的奖励相结合就是 policy-based RL 中的策略梯度，RL 的目标就是最大化期望奖励。

我们再总结下该模型的输入参数：

sku对各个目标货车的分配关系，包括整托托盘数PalletAssign<sku,dst,qty>和整箱数 BoxAssign<sku,dst,qty>
sku 对拆零机械臂的分配托盘数：PalletAssignPart<sku,qty>
sku 对每楼层的分配托盘数: PalletAssignFloor<sku,floor,qty>
当前各个货车的作业情况，即各个整托机械臂已分配但未完成的托盘数<dst,qty>、拆零机械臂已分配但未完成的托盘数<qty>、各个楼层已分配但未完成的托盘数<floor,qty>。

4.4.2 求解过程

解码是按顺序执行的，每步输出一个点（即 SKU）直至状态认为是结束。解码根据整个图的嵌入信息和当前的状态上下文来输出选择各个点（即 SKU）的概率。其中，当前状态上下文是指上述输入参数 4）中初始状态下各个资源已分配但未完成的信息，结合在这之前的每一步解码选择而得到的各个资源已分配但未完成的信息。选择各个点（即 SKU）的概率，是上述上下文信息与 encoder 节点信息进行注意力匹配计算得到的，同时还要结合掩码不允许选择已选择的点（即 SKU）。

图6:解码器的解码过程。解码是按顺序进行的，在第 t 步时，解码器根据编码器的图嵌入以及 t’(t’< t)时刻产生的输出信息从而输出选择各个节点的概率。

当前状态上下文：等于图的嵌入信息加上每一步后的资源使用线性映射后的嵌入信息。其中，每一步后的资源使用信息由每步解码计算后更新相关信息得到的。其更新流程为：

维护当前每货车空闲整托机械臂信息、当前空闲拆零机械臂信息、当前每楼层空闲小车信息
对当前步选择的点（即 sku）生成 onehot
根据 onehot 计算这一步选择的每货车新追加的托盘数和箱数
更新当前每货车空闲整托机械臂信息
根据 onehot 计算这一步选择的拆零机械臂新追加的托盘数
更新当前空闲拆零机械臂信息
根据 onehot 计算这一步选择的每楼层新追加的托盘数
更新当前每楼层空闲小车信息

奖励：等价于代价的相反数。代价的计算公式为以下，其中，代价分为两部分，一部分为类网络流模型的形式化定义中的优化目标，另一部分为惩罚项，其对应类网络流模型的形式化定义中约束条件。

4.4.3 训练算法

在模仿学习阶段，我们训练的目标是最小化代价。模型将解码的每一步选择视为马尔可夫决策过程，不断地最小化策略梯度。

4.4.4 微调优化：从在线策略到离线策略

在微调优化阶段，我们的通过模拟仿真或者观察真实运营的记录每次的上下文信息、决策信息和最终奖励。其中，我们使用当前时刻后的一段时间的吞吐效率作为当前决策的最终奖励。整个训练过程也基本不变，只是在选择 sku 时不再按照输出概率贪心选择，而是直接使用记录的当前决策，然后再做策略梯度计算。

由于在模仿学习阶段，由于数据可以实时生成，所以在做策略梯度时可以随时搜集数据随时更新策略。在这个阶段我们并不担心训练数据获取成本的问题。但是，在微调优化阶段，我们的数据是通过模拟仿真或者真实运营数据而得来的，它们的成本很高。如果数据在搜集之后只使用一次后就丢弃，将会带来极高的成本。因此，我们还要考虑离线训练策略梯度模型。这里我们通过重要性权重的技术来修正采集数据和当前训练数据的两个数据分布差异。

05 展望

我们通过一个例子描述了一个在排序场景下的波次决策问题。我们发现此类分拣排序的复杂场景下，历史文献只是给出了通用性的指标和策略描述，并没有详细的研究。这里我们先由动机出发，再从基于资源利用效率的贪婪决策升级到类网络流模型，最终通过深度强化学习模型的描述来解决这个问题。

我们在物流仓库中遇到的问题大多数是复杂的序列决策问题，其也基本上是 NP 难的。我们往往也使用启发式的算法求解。这个解的质量实际上非常依赖于专家决策。同时，我们对问题简化后往往丢弃了些隐含信息，而这也会影响我们解的质量。

而随着深度学习的发展，特别 Attention 机制的发现，很多简单的决策序列问题比如 TSP 问题、VRP 问题都有被研究而且解决地更好。那么，对于我们面对的复杂决策序列问题中，我们其实至少是可以使用 DL+RL 的方法通过预训练达到专家决策水平，再通过仿真数据+微调的方式逐步调优。而同时，在物流仓库中，很多问题都可以通过图的方式来进行表示，而深度学习恰恰能够学习到图中各个节点的隐藏信息。这些发展都可以被我们应用到物流领域。

总之，我们提供了一个使用 DL+RL 解决物流仓库中序列决策问题的一套方法。同时，本文也不失是对排序分拣问题的一个回顾。

来源：旷视研究院
作者：旷视研究院

专栏文章推荐

欢迎关注旷视研究院极术社区专栏，定期更新最新旷视研究院成果。欢迎添加极术小姐姐微信（id:aijishu20)加入技术交流群，请备注研究方向。
加入旷视：career@megvii.com

技术的真相 | 机器学习在仓库控制中的探索：以某场景的排序问题为例