基于智能机器人的“货到人”系统订单排序优化

夏德龙，吴耀华，王艳艳，邹 霞

1) 山东大学控制科学与工程学院，山东济南250061；2)山东大学管理学院，山东济南250100； 3) 山东财经大学管理科学与工程学院，山东济南250014

订单分拣工作是配送中心最重要的过程之一[1]，分拣效率直接影响供应链下游的服务水平．传统的“人到货”人工拣选系统效率低下，从而出现利用机器人代替人工作业的智能机器人拣选系统．智能机器人“货到人”系统使用智能机器人将货架搬运到拣选站台，代替拣选人员在仓库内行走拣货的作业，极大提高了订单拣选的效率．在智能机器人“货到人”系统中，拣选人员拣选的效率大于货架出入库效率，从而货架出入库效率成为限制系统整体运作效率的瓶颈．

针对“货到人”系统订单分拣问题已有不少研究结果．卢少平等[2]研究自动分拣系统时，以烟草分拣为例，根据相似系数分配拣选区． DORNBERGER等[3]对自动化仓储系统(automated storage and retrieval system, AS/RS)中货物到出入口(input/output, I/O)的距离建模，且用改进的遗传算法优化订单拣选顺序，有效提高系统拣选效率．张喜妹[4]针对Kiva系统的行走距离最短作为目标函数建模，用以解决订单的分配问题，并采用A*算法求解模型．王艳艳等[5]对AS/RS和Carousel两类“货到人”系统依据不同订单类型进行系统优化．吴颖颖等[6]针对“货到人”系统中的多层穿梭车系统中批次内订单的排序问题，对同一拣选台相邻订单之间共同需求的货物进行建模，并采用改进的K-Means算法求解，但并未考虑拣选台之间订单的耦合． BOYSEN等[7]通过研究单拣选台同时拣选的订单数量来减少货架的出入库次数，从而提高整个Kiva系统的拣选效率，但是并未考虑多个拣选台的情况．刘德宝等[8]通过设计改进的小生境遗传算法，并用于不同类型拣货机的物品分配优化模型，最大限度地减少了总拣货时间． XIANG等[9]通过设计启发式算法求解Kiva系统的订单分批和储位分配问题．BOZER等[10]通过Kiva和Miniload系统对处理订单性能和预期吞吐量进行对比，从而得出Kiva系统的优点和局限性． LEE等[11]从人体工程学出发研究如何提高Kiva系统订单拣选效率，对比AS/RS系统，采用数字人体建模分析各种人体因素对拣选效率的影响．FOUMANI等[12]以最小拣选时间为目标函数，对AS/RS系统进行建模，通过探索最优拣选顺序，缩短系统拣选订单的时间，进而提升系统拣选订单的效率．BOYSEN等[13]对自动化拣选系统中的订单合并和订单分区分批策略进行建模，最大化合并订单的相似度．ARDJMAND等[14]提出多拣货机的订单分配、订单批处理和拣货机选路问题，并使用改进的精确算法求解所提出的数学模型，最终得出当订单数与拣选机数之比对拣选时间的影响．

鉴于鲜有研究涉及“货到人”智能机器人系统多拣选台相互影响的批次内订单排序问题，本研究考虑拣选台内相邻订单和拣选台之间订单的耦合，对“货到人”智能机器人系统进行订单排序优化，可以在不增加设备成本的情况下，提高整个系统的订单拣选效率，对整个拣选系统优化的成本控制，以及提高商家服务水平具有重要意义．

1 “货到人”智能机器人系统流程

1.1 “货到人”智能机器人系统

随着商对客电子商务模式(business-to-consumer, B2C)的发展，传统的“人到货”拣选方式已经不适应高增长的业务需求，而“货到人”智能机器人系统以其自动化程度高及运行成本低等优点备受电商用户青睐．其中，美国亚马逊公司的Kiva系统成为“货到人”智能机器人系统的典型．

“货到人”智能机器人系统主要由主控制台、智能机器人、可移动货架及拣选台等组成，如图1．系统重新定义了货物出库流程，智能机器人先移动到订单需要的货架下方，随后搬运货架至拣选工人面前，由拣选工人完成订单的拣选．

图1 “货到人”智能机器人系统Fig.1 (Color online) Parts-to-picker intelligent robot system

1.2 系统作业流程

系统作业如图1(a)，首先由主控制台分配若干订单组至各个拣选台，订单组为系统合单之后拣选台同时拣选的订单单位，每个订单组包含若干个订单；随后智能机器人(如图1(b))搬运所需的可移动货架至拣选台(如图1(c))，拣选工人根据订单需求从货架中拣选出订单组内订单所需货物，放入各个订单对应的订单箱中，完成订单拣选；最后由智能机器人搬运货架回库或送至需要该货架的拣选台．

随着订单量的增多，货架频繁出入库，出入库效率成为限制系统效率的瓶颈．通过有效的订单聚类分批，批次内订单组顺序排序优化，可有效减少货架的出入库搬运次数，提高整个系统的运作效率．

本模型对“货到人”智能机器人系统做以下假设：① 货架上货物量满足一个批次的订单需求，即在订单拣选过程中不存在缺货现象；② 各拣选台的任务量遵循均衡原则，两两拣选台之间订单组数量差≤1；③ 各拣选台上货架的缓存容量相同；④ 订单已按最优原则分成若干订单组，且每个订单组订单数相同；⑤ 多个拣选台共用一个货架时，优先选择排队较少或者无排队的拣选台．

1.3 两种优化情况

在基础条件下，每完成1个订单行的拣选作业，机器人会对相应货架执行2次搬运作业(1次入库和1次出库)，以下提出2种可以减少机器人搬运作业的情况．

情况1单拣选台的效率优化．设拣选台t的相邻两个订单组都包含货架m中的货物，则可通过使货架m不回库，减少两次机器人的搬运作业，从而减少货架出入库时间和频次，提高订单拣选效率．

图2 多拣选台之间共用货架Fig.2 (Color online) Shared racks in multiple picking stations

情况2多拣选台间的效率优化．设拣选台t1在拣选订单组O1时用到货架m中的货物，而拣选台t2,t3,…,tn拣选订单组O2,O3,…,On时也需要用到货架m中的货物，则拣选台t1拣选完成之后，机器人搬运货架m至拣选台t2,t3,…,tn， 如图2．当待拣选台tn的拣选完成后，货架m有两种情况：① 拣选台ti(1≤i≤n)下一个订单组会用到货架m中的货物，则拣选台tn拣选完成后，货架m回到拣选台ti缓存区，对应图2中⑤；② 拣选台ti(1≤i≤n)下一个订单组不会用到货架m中的货物，则货架m回库，对应图2中④．对于以上货架m的2种情况，均可减少搬运作业次数．

根据以上优化思路，本研究对“货到人”智能机器人系统货架出入库搬运次数进行建模，通过对拣选台的订单组拣选顺序优化，提升系统效率．

2 模型建立

2.1 货架出入库搬运作业次数

假设有N个订单组，共有S个拣选台，货架的个数为R，Qt为拣选台t分配的订单组个数，且

(1)

Otk表示第t个拣选台拣选顺序为k的订单组，在不考虑订单之间耦合的情况下，拣选订单组Otk所需要的货架搬运作业总次数为

(2)

由此可得在不考虑订单组之间耦合情况下，拣选所有订单组所需的货架搬运作业次数为

(3)

(4)

其中，d为拣选台中货架的缓存数量．

(5)

(6)

其中，dr表示拣选台剩余的货架缓存容量．

(7)

由于实际中拣选台的拣选速度并不完全一致，所以拣选台之间订单组的耦合所减少的搬运作业次数可能小于γ1， 引入ε表示不同拣选台拣选速度之间的影响因子， 0<ε≤1． 故拣选N个订单组货架总搬运作业次数为

γ=γ0-γ2-「εγ1⎤

(8)

2.2 系统出入库模型建立

从2.1节分析可知，无论是拣选台之间订单组的耦合，还是拣选台内部订单组之间的耦合，都可以有效减少货架的搬运次数，并且通过减少货架的搬运次数，能够有效提高整个系统的运作效率，增加拣选台的分拣效率．根据以上2种减少货架搬运作业次数的途径，以“货到人”智能机器人系统货架出入库搬运次数为目标函数建立如下模型．

(9)

(10)

(11)

φikt=0或1

(12)

其中，式(10)表示每个订单组仅被分配在一个拣选台中，且在该拣选台中顺序固定；式(11)表示固定拣选台和拣选顺序仅会被分配一个订单组；式(12)中φikt表示订单组i是否被分配至第t个拣选台中，且在第t个拣选台中拣选次序是否为k， 若是则φikt=1， 反之为0．

3 改进的带权值K-Means聚类算法

K-Means聚类算法输入聚类个数和数据源，可以得到方差最小的K个聚类，且同一聚类下的对象相似度高于不同聚类的对象．K-Means算法具有以下优点：① 算法简单，求解速度快；② 在求解大数据集时，算法收敛快；③ 时间复杂度接近线性，时间复杂度低．因此，该算法被广泛用于各种数据挖掘场景中．

如果把订单组之间的耦合因子看作距离，则可以把订单组之间的排序看作旅行商问题(travelling salesman problem, TCP)，本研究采用改进的K-Means算法求解模型．

订单组i可以表示为向量(xi1,xi2,…,xiR)， 其中，xim(1≤m≤R)表示订单组i是否包含货架m中的货物，若有，则xim=1； 反之，xim=0． 计算所有订单组两两之间的耦合因子，得到耦合矩阵为

(13)

对于模型的求解主要分为3个步骤：① 计算所有订单组的耦合矩阵；② 为所有拣选台分配初始订单组；③采用改进的带权值K-Means聚类算法分配剩余的订单组至各个拣选台．算法的伪代码请扫描论文末页右下角二维码．

4 仿真分析

通过仿真验证“货到人”智能机器人系统货架出入库模型的正确性，并且通过仿真数据检验算法的有效性．通过将优化模型同不考虑拣选台之间和拣选台内订单耦合的情况进行比较(优化前模型正常拣选1个订单行，进行2次搬运作业)，找出降低货架出入库次数的各种影响因素．引入批次订单相似系数来反映该批次订单组的相似度，订单相似系数通过计算平均订单耦合因子来估计批次内订单的耦合程度，且

(14)

由计算机随机模拟出3组不同订单相似系数的订单，每组订单的订单组数量均为40个，且根据3组不同订单的仿真结果，可以预估该模型对不同批次订单减少货架搬运次数的情况．

仿真中货架数量R默认为50个，拣选台个数S默认为4个，拣选台货架缓存个数d默认为4个，拣选台间影响因子ε默认设定为0.5．

表1为3组不同相似系数订单仿真数据．可见，订单组顺序优化后，3组订单货架搬运次数分别减少了32.04%、35.75%及39.11%，平均减少35.63%．造成减少货架搬运次数百分比不同的主要原因是批次订单相似系数的差异．优化减少的货架搬运次数百分比随着订单相似系数的增大而增大，这是由于订单相似系数增大的同时，订单组之间共用的货架数量增大，从而订单组排序优化后，减少的货架搬运次数百分比增大，优化效果更显著．

表1 不同批次订单优化情况

订单组个数变化时，优化减少的货架搬运次数百分比变化如图3．可见，3组订单随订单组个数的增加，优化减少的搬运次数百分比同样增大．3条曲线的斜率随订单组个数的增大而减小，反映出优化减少的搬运次数百分比增大的幅度随订单组个数的增大而减少．

图3 订单组个数对货架搬运次数的影响Fig.3 The influence of order numbers on rack visits

拣选台货架缓存数量从1增大到6时，优化减少的搬运次数百分比变化如图4．d从1变化到4时，3条曲线优化减少的搬运次数百分比逐渐增大，d从4变化到6时，订单批次2和3的曲线纵坐标变化较小，批次订单1曲线纵坐标不变．这是由于订单组优化后耦合因子主要集中在4左右，d从1变化到4时，拣选台货架缓存容量小于大部分订单组间耦合因子，所以，随着d的增大，曲线的纵坐标迅速增加；但是d从4变化到6时，d不再成为减少货架搬运次数的主要限制因素，故曲线变化幅度不大．

图4 拣选台货架缓存数量对货架搬运次数的影响Fig.4 The influence of picking station’s rock capacity on rock visits

3组订单中订单组个数变化和拣选台货架缓存容量变化时，对出入库次数百分比影响的敏感度分析结果如表2．其中，订单组个数选择基准为20个，拣选台货架缓存容量选择基准为4个，表2中相对变化率为出入库次数变化与订单组个数变化，或拣选台货架缓存容量变化的比值．由表2可见，相对变化率随订单组个数的增大逐渐变小，出入库次数对订单组个数的敏感度逐渐降低，对比3组订单，订单批次3对订单组个数变化的敏感度最高，说明订单相似系数越高，拣选时对订单组个数变化的依赖越高；同理，出入库次数对拣选台缓存容量变化的敏感度随缓存容量的增大而逐渐降低，当缓存增加50%时，敏感度降至最低，订单相似系数越高，出入库频次对拣选台缓存容量的敏感度越高．

表2 不同批次订单敏感度分析

结 语

采用“货到人”智能机器人系统模型和改进的K-Means算法可有效减少系统的货架搬运次数，减少的货架搬运次数百分比随批次订单相似系数的增加而增加；一个批次内订单组的数量对减少货架搬运次数百分比具有重要影响．订单数量大于一定数值之后，优化减少的货架搬运次数百分比不再增加；在系统货架及智能机器人等设备不变的情况下，适当增加拣选台的货架缓存容量可有效减少货架的搬运次数；出入库频次对订单个数和拣选台容量的敏感度随订单相似系数的增大而增大，通过优化算法提高订单相似度有助于提高拣选效率．