移动机器人履行系统的订单处理研究

冯爱兰，杨 腾，孔继利

1.北京科技大学 机械工程学院，北京 100083

2.北京邮电大学 现代邮政学院，北京 100876

1 引言

移动机器人履行系统（Robotic Mobile Fulfillment Systems，RMFS）是一种“货到人”的拣选系统[1]，其通过智能仓储移动机器人搬运可移动货架，实现待拣选商品在存储位置和拣选台之间快速移动（如图1所示），从而提高订单履行效率，大幅度降低拣选人员的工作量，常见如Kiva系统[2-3]。RMFS当前多用于订单数量多、单笔订单规模小、品种多、配送区域分布广、配送时间要求高[4]的B2C电商企业，这类企业往往面临订单波动大而履行时间有限的问题。RMFS 具有高灵活性、高柔性、组装调整工期短等特点，有效满足了B2C电商企业的需要，在亚马逊、京东、天猫、唯品会等企业中得到普遍应用。

订单处理活动是拣选作业前的准备工作，是订单履行过程中的重要环节，订单处理的结果对订单履行效率具有重要影响。订单特点和订单拣选方式是决定订单处理方法的主要因素：品项多的订单通常采取按单拣选的方式；订单数量多、单个订单含有品项少的订单，直接拣选要消耗大量人力物力，并且效率极低，往往需要经过一定的处理工作再进行拣选作业——订单分批、订单合并、订单排序[5-7]都是常见的订单处理方式。传统的订单分批方法试图通过商品合并和路径整合实现行走距离最短，但在RMFS系统履行过程中不存在多种商品的路径整合，传统订单处理方式不能完全适用。RMFS的搬运活动以单个货架为单位，由于每个货架内商品的种类和数量是有限的，订单履行顺序和货架调度顺序将影响拣选作业的效率。Boysen 等[8]考虑动态拣选下的订单处理过程，将问题拆分成订单履行顺序和货架调度顺序两个子问题，并对系统机器人的配置数量问题进行分析。Xiang等[9]关注静态拣选方式下的订单处理问题，研究系统订单分批和货架调度过程，以货架调度次数最少为目标提出相应的求解算法。张彩霞等[10]从订单分批、拣选路径、任务分配三个方面探究“货到人”的订单拣选优化方法。李晓杰[11]同时考虑RMFS 的储位指派和订单分批问题，提出基于聚类方法的优化算法对两问题联合优化。更有学者[12-15]采用排队网络建模、仿真、算法优化等方法，从仓库布局、储位指派、拣选过程、履行绩效等不同方面对RMFS问题进行探究。

电子商务对时效的敏感决定了RMFS 订单处理活动的重要性，RMFS应用的灵活性也使订单履行流程更为复杂多样，而当前对RMFS 的研究相当有限。可以说，RMFS的订单处理问题仍有许多亟待探索和研究的空间。本文就RMFS的订单处理过程进行研究，在共享储位指派优化的基础上，提出OptGA-GR 混合算法，实现订单履行顺序和货架调度顺序的优化。

2 问题描述和模型建立

2.1 问题描述和假设

本研究中，将根据订单的信息确定“拣选台—订单”“订单—货架”“货架—拣选商品”的对应关系，为拣选活动提供订单拣选顺序和货架调度顺序的信息，辅助系统在最短时间完成所需要的拣选活动。由于订单拣选时间和货架调度次数直接相关，因此将问题目标由拣选时间最短转化成货架调度次数最少。研究基于动态拣选场景，拣选人员按照拣选台所能容纳的订单数量进行拣选，每有一个订单完成则立即补入新订单（如图2所示）。与静态拣选相比，动态拣选始终保持拣选订单数量一定，使每一次货架调度能够为更多订单服务。该拣选方法中，订单需要时时补充，货架调度要满足不断变化的SKU需求，订单之间包含的相同SKU数量、一次货架调度可以提供的SKU 种类都会对订单履行效率产生影响。因此，订单顺序和货架调度顺序成为影响RMFS动态订单拣选的重要因素，是订单处理活动所要解决的主要问题。Boysen 等[8]在其研究中证明了订单处理问题是NP-hard问题，其子问题订单排序问题和货架调度问题也都是NP-hard问题，求解难度大且耗时长，对问题规模十分敏感。

图2 RMFS动态订单拣选和静态订单拣选对比

本文基于如下假设条件：

（1）在RMFS中，采用共享储位的储位指派原则：一种商品可以存储在多个移动货架中，同时一个货架可以存储多种商品。

（2）货架上存放的商品能始终满足订单中商品数量的需要。该假设具有一定的合理性：一方面，B2C 订单表现出SKU 种类多但每类SKU 需求量小的特点，订单行数为1～2的订单占80%以上，而共享储位使补货能及时进行，大大降低了货架存放的商品无法满足订单需求的可能性。另一方面，在订单处理过程中考虑货架储存量和订单需求的关系将极大增加问题的复杂性，使问题的求解时间延长。并且，小概率的货架存量不足问题完全可以通过拣选过程中合理的应对措施及时处理。

（3）拣选台的订单容量是一定的，拣选台可处理的订单数量不受到订单规模、箱子体积的影响。

（4）货架的一次调度只能为一个拣选台服务。本文只考虑单一拣选台，该方法在多拣选台分区域拣选，货架服务唯一拣选台的场景中同样适用，具有一定的现实意义。

（5）忽略因货架位置不同导致的货架调度顺序和货架拣选顺序的不一致。

2.2 符号设置和模型建立

相关参数及变量的描述见表1和表2。

表1 参数描述

表2 决策变量描述

数学模型如下：

式（1）目标函数是求完成所有订单调度货架次数最少。约束（2）表示完成所有订单需调度货架次数的上限等于总订单行数；约束（3）表示一次最多只能调度一个货架；约束（4）表示每一次调度的货架都为一个以上的订单服务；约束（5）表示一个货架服务的订单数量不大于缓冲区待拣选订单数量；约束（6）表示订单中的每一个SKU都能被满足；约束（7）表示保证调度的货架能提供相应的商品；约束（8）为参数的基本约束。

2.3 共享储位优化

共享储位规则[16]对RMFS 具有十分重要的意义。这种模式不仅可以满足多拣选台请求同种商品的情况，实现及时响应，减少等待时间，也可以通过货架内存储商品的合理指派，增加一次货架调度满足多个订单中SKU的可能性，从而减少货架调度次数。

在具体的储位指派中，本文提出基于聚类的两步式启发式方法，增强货架中商品的相关性。考虑实际应用场景，限定一个SKU最多存储在M_max个货架中。具体步骤如下：

（1）通过历史订单计算商品之间的相关性。Ai表示包含商品i的订单集合，则商品相关系数可以用两商品共同存在的订单和两商品存在的总订单之比表示。利用公式（9）计算所有商品之间的相关系数，将相关系数按降序排列。

（2）为每个SKU指派一个货架存储位置。按Sij的降序对商品i、j进行指派。如果i、j均不在货架中，则寻找一个可行货架放入商品i、j；如果只有商品i存在某货架中，且该货架未满，则将商品j放入，否则随机选择未满货架放入商品j。

（3）实现商品多储位指派优化。按照SKU 出现频次对SKU 降序排列，得到(i1,i2,…,is)。按照商品i与其他商品相关系数降序指派商品i、j，直到货架位置全满，指派过程中保证每个SKU 存储货架数量不超过M_max。如果有只存储了商品i或j的未满货架，则将另一商品存入该货架，否则将商品i、j放入空货架中。如果不存在空货架，则寻找可行货架放入商品i、j。当对于所有的Sij，以上方法都不可行时，转入步骤4。

（4）将所有货架中的空位置随机指派SKU，停止。

3 RMFS订单处理过程

3.1 订单履行顺序问题和货架选择调度问题

订单顺序对订单履行效率有着重要影响，合理的订单顺序能够有效地减少货架的调度次数，从而提高整个系统的效率。假如有SKU 集合U={A,B,C,D} ，订单O1={A,B,C},O2={A,B,C,D},O3={A,C,D},O4={C,D} ，货架P1={A,C},P2={B,D},P3={C,D}，拣选台容量C=2,如图3所示。方案一显示，订单履行顺序[O1,O2,O3,O4]需要调度[P3,P1,P2,P1]四次货架满足。方案二中，按照[O3,O4,O2,O1] 顺序拣选订单，只需要调度[P3,P1,P2]三次货架，即订单履行顺序不同，需要调度货架的次数不同。当同一拣选台上的订单有较多相同SKU 时，一次货架调度能满足多个订单中的SKU 需要，对优化系统效率起到正向作用。

图3 RMFS订单顺序对订单履行效率的影响示例

当订单履行顺序确定后，待拣选订单的更新和待拣选商品的状态主要取决于货架的选择和调度。如图4所示，订单履行顺序同为[O1,O2,O3,O4]时，货架调度顺序不同，货架调度次数也不相同。

图4 RMFS货架调度对订单履行效率的影响示例

由此，可以将订单履行顺序和货架选择调度作为影响订单履行效率的关键因素，提出RMFS订单处理过程的优化算法。

3.2 OptGA-GR混合算法

RMFS 中订单排序问题和货架选择调度问题均为NP-hard问题，且整个订单拣选过程受两因素的影响，因此提出OptGA-GR混合算法，将改进遗传算法和改进贪婪算法相结合，并引入订单关联实现初始解的优化和算法的迅速收敛，达到短时间内得到满意订单处理结果的目的。

3.2.1 基于订单关联的贪婪算法产生初始种群

对于有N个待拣选订单和M个货架，拣选台容量为C的RMFS系统，订单拣选顺序及对应的货架调度方案用以下集合表示：δ={α,β}，α=[Oα(1),Oα(2),…,Oα(N)]，β=[Pβ(1),Pβ(2),…,Pβ(m)]。α表示需要拣选的订单集合及相应的订单顺序，β表示拣选台需要调度的货架及相应的货架调度顺序，m为完成该批次订单需要调度的货架数量，算法目标函数为min(m)。

在传统的遗传算法中往往通过随机方法产生随机解组成算法的初始种群，这种方法有收敛速度慢的弊端，使大规模问题求解耗时较长。本文在初始解的产生过程中引入订单的相似关系，用S(Oi,Oj)表示订单i和订单j的相似性，Oi表示订单i的SKU集合，订单的相似系数即两订单共有的SKU种类数和总SKU种类数之比，通过公式（10）计算两订单的相似性。

初始解的产生采用贪婪算法进行优化，首先随机选择订单Oi作为当前订单，然后在尚未指派的订单中选择与当前订单相关性S(Oi,Oj)最强的订单Oj作为下一个订单，更新当前订单Oj为Oi继续搜索直到所有订单都加入个体。最终得到的个体α包含所有需要拣选的订单，α中基因排列顺序代表订单的拣选顺序。

3.2.2 交叉和变异

OptGA-GR混合算法选择使用循环贪心交叉法，将订单的相关性作为交叉选择的指标，实现在交叉过程中提高后代质量的目的。循环贪心交叉法遵循以下四个步骤，示例如图5：

步骤1将父代的染色体看成首尾相连的闭环，即最后一个订单的后一个订单为第一个订单。随机选择一个订单作为两个子代的首个订单，计为A。

步骤2分别找出父代中与当前订单相邻的后（前）一个订单，记为E1、E2(W1、W2) ，比较当前订单和后（前）订单的相似性。

步骤3在E1、E2(W1、W2)中选择未指派且相似性更强的订单作为子代一（子代二）的下一个订单加入子代个体。如果两订单均已存在于子代个体中，则随机选择未被扩展的订单加入子代。

图5 循环贪婪交叉法

步骤4将子代中最后被加入的订单作为当前订单，重复步骤2和步骤3，直到子代染色体完整生成。

算法采用逆转变异的方法，在染色体中随机选择两个点，将这两个点之间的子串进行反序，并插入到该染色体的原位置。考虑到在实际运行中交叉概率和变异概率同样会对算法的结果产生重要影响，选择使用于莹莹等[17]在其研究中提出的自适应概率机制，考虑进化阶段、历史最优解和交叉、变异概率的关系，实现算法在不同阶段交叉概率和变异概率的动态调节。

算法通过交叉和变异改变个体α中的基因排列，探寻提高系统履行效率的订单拣选顺序。

3.2.3 基于改进贪婪算法得到适应度

算法取货架调度次数的倒数为个体的适应度值，把个体代表的订单顺序作为输入参数，采用加入跳出规则的贪婪算法寻找目标函数最大的个体。

当订单履行顺序确定时，订单拣选的一般状态表示成(U1,U2,…,UC,Podline,OC+1)，C表示拣选台容量，Uk表示拣选台k位置的订单中尚未被满足的SKU 集合，k=1,2,…,C,Ot表示下一个待拣选订单，Podline表示该状态下已调度的货架序列。

当下个货架j调度时，状态更新为(U1-Pj,U2-Pj,…,UC-Pj,[Podline,j],O′)。如果第k个订单拣选完成，那么Uk=Ot+1-Pj；如果本次货架调度有n个订单拣选完成，则O′=Ot+n。状态更新过程体现了货架调度过程中商品、订单和货架的关联：待拣选商品被货架j部分满足；货架的调度可能引起待拣选订单的更替。

拣选的初始状态可以表示为(U1,U2,…,UC,∅,OC+1)，最终状态为(∅,∅,…,∅,Podline,∅) ，该状态下拣选位上的待拣选商品集合(U1,U2,…,UC)为空，且不存在待拣选订单，Podline中货架能满足所有订单，则Podline为货架调度顺序β。

由于货架存储了所有SKU，任何状态下拣选台需要的商品都能被货架满足，且存在能提供最多SKU 的最优货架。因此，可以将每个状态下货架调度问题看成是货架调度的子问题，用贪婪算法逐步构造最优解（如表3）。在不同状态下，通过选择能提供更多SKU 的货架，寻求整体货架调度次数最少。但贪婪算法每一步只考虑当前状态，选取满足局部最优的子问题的解，具有一定的局限性。本算法为减少搜索次数且跳出局限，加入跳出机制：每次搜索前将货架搜索顺序乱序，当搜索到某货架可以提供一半以上需求SKU 时，认为该货架为最优货架，跳出本次搜索。

表3 货架选择调度问题的贪婪算法思想

3.2.4 算法结构

基于上述的分析，本文提出的OptGA-GR混合算法如图6所示，基本流程如下：

（1）基于订单关联的贪婪算法产生初始种群。

（2）在每一代的进化过程中，首先利用改进的贪婪算法获得货架调度次数，取其倒数作为适应度值。将求解适应度的问题视为订单履行顺序一定的货架调度次数最少问题，采用加入跳出机制的贪婪算法求解货架调度顺序。

（3）执行选择、交叉、变异过程。在父代个体和子代个体中选择最优的N个个体作为新种群执行交叉和变异的过程。交叉和变异过程分别采用循环贪心交叉法和逆转变异法实现，交叉、变异概率服从自适应概率机制。

（4）当算法达到终止条件时停止。

图6 OptGA-GR混合算法流程图

4 实例分析

为了便于分析比较，仓库布局、订单产生方法等数据参考文献[16]和文献[18]，实验参数设置如表4。设定移动货架在仓库中随机分布并在拣选完成之后随机回到任一空闲位置。共产生300 个数据样本，研究小、中、大三类仓库规模共30种不同的场景，每个场景运算10次。

本文将提出的OptGA-GR 算法与基于先到先服务的贪婪算法（FCFS-GR）、TSP 标准遗传算法[19]+贪婪算法（GA-GR）、SA-OS算法[8]相比较，其中，比较算法根据原论文内容编程实现。为保证公平比较，根据算法的收敛情况，限定算法运行时间为1 800 s。使用MATLAB R2018a 对问题进行设计实现，实验环境为Windows 10 i5-8250U，内存8.0 GBRAM。

表4 实验参数设置

实验结果中，用Obj表示该规模问题下算法运行十次的平均值，ARG表示算法和OptGA-GR混合算法的平均相对差距。从表5 中四种算法的目标值可以明显看出，OptGA-GR混合算法在大、中、小三种规模的问题中都表现出一定的优势，尤其是在中、小规模问题中优势明显。先到先服务的贪婪算法在几种算法中总体表现较差，其ARG 始终高于15%，在小规模问题中更是在40%左右，这意味着对相同的一批订单，先到先服务策略要多调度近一半的货架。但在实际应用中，先到先服务可以保证订单的即时履行，在一些重要客户、紧急订单履行的情景中具有现实意义。虽然TSP 标准遗传算法+贪婪算法（GA-GR）与OptGA-GR 混合算法相比，在不同规模问题的寻优能力始终稍差，但通过比较可以看出，随着问题规模增大，这种差距有所缩减。SA-SO 算法与OptGA-GR混合算法相比，在不同规模问题中ARG相对稳定，相比于OptGA-GR 混合算法，SA-SO 算法局部搜索能力较强但全局搜索能力较弱，所以在有限时间的求解过程中寻优能力表现较差。

表5 不同规模问题运算结果比较

图7 算法稳定性分析

表6 Wilcoxon检验统计量分析

同时，对算法的稳定性进行分析，计算不同算法不同场景的10 次运算结果的标准差值，结果如图7 所示。从整体趋势来看，随着问题规模的增大，各算法的稳定性均有所降低，其中SA-SO算法的波动最为明显。与其他算法相比，OptGA-GR 混合算法表现出更强的鲁棒性，在相同时间内求解结果更为稳定，尤其是在订单规模较小(N=50)的场景中。此外，Wilcoxon 配对的符号秩检验在95%置信水平下进行。表6的结果表明，算法差异性显著，p值＜0.05。很明显，统计检验进一步证实了OptGA-GR 混合算法在求解本文所研究的订单处理问题的稳定性能。

另外，就拣选台订单容量来看，随着容量C的增加，完成一批订单需要的货架调度次数逐渐减少（如图8所示）。这是由于当拣选台容量增加时，一个货架可为更多的订单提供SKU，从而减少了货架调度次数。合理地拣选台订单容量应该成为RMFS 仓库设计时的重要考察因素。但这种考虑忽略了多订单拣选过程中SKU数量的合并以及多个订单同时拣选活动中拣选时间的增加，不能直接地反应订单的履行效率。

图8 拣选台容量对货架调度次数的影响

5 结语

本文对RMFS 单拣选台动态拣选场景下的订单处理活动进行研究：首先通过对RMFS 系统特点的分析选择共享储位指派方式，提出优化共享存储的启发式方法。进而围绕订单拣选和货架调度两个子问题，建立问题模型和设计OptGA-GR 混合算法。通过引入订单相关性、循环贪心交叉、跳出机制等多种方法进行算法优化，在提高算法的收敛速度的同时防止算法陷入局部最优。通过与SA-SO、FCFS-GR 和GA-GR 算法的比较证明：OptGA-GR 混合算法能够在较短时间找到订单履行顺序和货架调度顺序的满意解，同时保持解的稳定性。

本文在货架调度顺序的决策中，仅考虑货架对SKU种类的满足与否，忽略了订单履行过程中的其他因素，如货架实际到达顺序对系统绩效的影响。另外，本文仅研究了单拣选台的订单处理活动，没有考虑多拣选台拣选时，订单任务分配和调度冲突等问题，这些问题可作为接下来的研究方向。