基于移动机器人的拣货系统研究进展

订单拣选是将商品从其存储位置拣出以满足客户订单需求的过程,订单拣选是典型的劳动密集型作业,占仓库运作总成本的60%～ 70%[1].随着客户需求从大批量少批次向小批量个性化转变,客户对订单的配送时限和服务质量要求越来越高,提升订单拣选效率已成为当今学术界和工业界共同关心的难题.基于移动机器人的拣货系统(Robotic mobile fulfillment systems,RMFS)的订单拣选效率是传统拣货系统的2～ 3 倍[2–3],彻底颠覆了传统仓库的拣货作业模式,为仓库的广泛应用和研究开辟了新途径.

RMFS 系统2003 年由Kiva 公司最先开发,2012 年亚马逊收购Kiva 后在其北美各大配送中心开始部署[4–5],国内已有菜鸟、京东和快仓等公司成功应用RMFS.RMFS 的核心思想是利用移动机器人将存储商品的移动式货架搬运到拣货站台,拣货人员拣取商品后再由机器人将货架送回存储区存储.相比传统拣货系统,RMFS 提高了拣货效率、准确性以及仓库空间利用率,缩短了仓库部署和调试时间,并可根据客户需求的变化实时、动态调整仓库布局结构,特别适合需求波动性大、时效性强的电商企业的订单拣选[2–3,6].

与传统拣货系统类似,RMFS 也面临货位指派、订单分批、任务分配以及路径规划等方面的问题,但在实际运作过程中,RMFS 与传统拣货系统相比存在诸多不同,面临一些新的亟需解决的问题.鉴于此,本文对RMFS 订单拣选过程的几个关键问题进行综述研究,并给出未来的研究方向,为RMFS的实践应用及学术研究提供参考.

1 RMFS 简介

RMFS 的仓库布局可分为存储区、拣选区和运输区(如图1(a)所示),订单拣选作业主要在拣选区进行(如图1(b)～ (d)所示).仓库一般采用栅格化布局,利用条码、RFID 等技术实现信息识别,并利用室内GPS 和传感器技术进行导航、定位和避障[6−8].RMFS 的货架为移动式货架,有运输货架和存货货架两种,运输货架是存放订单容器的货架,存货货架又可分为托盘货架和单品货架,托盘货架的作用是存放和拣选整箱商品,单品货架则存放零拣商品[4,6].补货站台位于存储区和拣选区之间,拣选站台位于拣选区和运输区之间,拣货和补货人员分别位于拣选站台和补货站台,他们只需要站在原地等待移动机器人搬运货架到来,并根据系统指示进行订单拣选或仓库补货作业.RMFS 的作业流程为:系统先按照一定策略将商品分配到各存储货架(货位指派问题),在收到客户订单后,基于特定的订单分配分批和任务分配策略将订单分批,再分配给相应的拣选站台(订单分批和分配问题),同时向运输机器人发布运输任务(多机器人任务分配问题),机器人将目标货架从其存储位置搬运到指定的拣选站台(多机器人路径规划问题),拣选人员按照系统指示依次进行拣选、扫描确认、存放等作业,完成商品拣选后,运输机器人再将货架送回存储区存储(多机器人路径规划问题),需要说明的是,货架返回后的存储位置不一定是其原来的存储位置(货架储位动态分配问题)[2].RMFS 的整个作业流程如图2所示,有关图2 的具体说明可参考文献[2].

图1 RMFS 拣货区域布局图
Fig.1 RMFS picking area layout

图 2 RMFS 订单拣选作业流程
Fig.2 RMFS order picking process

从图2 的作业流程可以发现RMFS 的几个关键的优化和研究方向:首先,RMFS 的正常运作依靠自动识别技术、传感器及通信等技术的支撑,可以对这些使能技术进行研究[9].其次,与传统拣货系统类似,货位指派[4]、订单分批[10]、任务分配[11]、路径规划[12]等问题的优化研究也是提升RMFS 效率的关键途径.再次,RMFS 本质上是一个自组织模式运营的分布式多机器人系统,可基于分布式、去中心化的思路进行系统优化,这与传统拣货系统有很大的不同[13].总的来说,RMFS 的优化可从使能技术、仓库布局设计、货位指派、订单分批、路径规划、分区拣选以及多机器人任务分配及协作等方面开展研究[1,14] (如图3 所示).RMFS 的优化研究可分为系统实现、系统作业以及研究方法三个层面,其优化理论框架如图4 所示.

图3 RMFS 拣货优化流程
Fig.3 RMFS picking optimization process

图4 RMFS 优化理论框架
Fig.4 RMFS optimization theory framework

2 RMFS 研究现状

RMFS 的相关研究主要涉及货位指派、订单分批、任务分配与调度、路径规划以及系统设计与评估等问题,相关问题的研究文献总结如表1 所示.

表1 RMFS 研究文献汇总
Table 1 Summary of literature on RMFS

2.1 货位指派

传统意义上的货位指派是指将商品分配到仓库中的合适储位,使订单分拣过程行走的距离最短[1].RMFS 的货位指派可分为商品储位指派和货架储位动态指派,商品储位指派是指在考虑商品销售关联性的情况下,将关联商品指派到同一货架存储,最终实现货架存储商品的关联度最大,降低订单拣选搬运的货架总次数,图5(a)为商品储位指派的示意图;在构建商品储位指派数学模型时,需考虑所有商品必须被指派到货架存储、同一类商品可以存储于多个货架以及货架的存储容量等约束条件.货架储位动态指派是在订单拣选的过程中,为搬运货架重新分配储位,例如将存储畅销商品的货架指派到靠近拣货站台的储位,同时将存储滞销商品的货架指派到远离拣货站台的储位,实现订单拣选过程的机器人行走距离最短,图5(b)为货架储位动态指派的示意图;在构建货架储位动态指派数学模型时,需考虑所有货架必须被指派到储位,储位的状态(占用储位或开放储位)以及仓库布局的连续动态变化关系等约束条件.

图5 RMFS 货位指派示意图
Fig.5 RMFS location assignment diagram

货位指派是典型广义指派问题(Generalized assignment problem,GAP)[50],最基本的货位指派的数学模型为:

模型 1.

在模型1 中,xij=1 表示将商品(或货架) i 存储在位置 j,否则 xij=0 ;cij 表示将商品(或货架)i存储在货架或位置 j 的拣货代价(或收益);式(1)为目标函数,根据选取的 cij 不同,可分为求最小值或最大值(例如拣货时间或距离最小、拣货效率最大等);式(2)和(3)为约束条件,表示商品(或货架)与储位之间的存储关系;式(4)为变量及取值范围.

科学的货位指派方法可以缩短行走距离、降低搜寻时间、减少工作量以及提高仓库拣货效率[51–52].Hausman 等[53]最早提出定位存储、随机存储和分类存储三种基本的货位指派策略,随后的文献分别从需求相关性[54–55]、出货量[56]、COI[57]、周转率[58]以及需求和结构相关性[59–60]等方面对货位指派问题进行了研究,根据问题类型、指派策略以及优化目标的不同,大量文献基于模型1 进行了深入广泛的研究.

RMFS 与传统拣货系统的货位指派问题不同在于:1)传统拣货系统的货位指派与路径策略密切相关[61],RMFS 的货位指派则与路径策略没有必然联系.2)指派目的地不同:传统货位指派只需将商品指派到某一分区或巷道,RMFS 既要将商品指派到具体的货架,还需考虑将关联商品指派到同一货架来降低拣货成本.3)优化目标不同:传统拣货系统将拣货行走的时间或距离作为货位指派问题的优化目标,RMFS 则可将货架搬运次数、机器人利用率等作为优化目标[23].4)指派复杂度不同:传统拣货系统的货位指派只需对商品进行储位指派,RMFS则还需考虑货架的储位指派(即货架在仓库中的位置),这是一个更加复杂的动态指派问题.5)静态与动态指派的不同:传统货位指派基于“一次指派、分批出库”的思路,RMFS 的货位指派过程是一种“动态优化、逐步求精”的过程.

RMFS 的货位指派可从以下几个方面借鉴传统货位指派问题的研究理论和方法:1)考虑商品需求关联性和频率:传统拣货系统考虑商品需求关联性、频率等因素进行货位指派研究[54–55],RMFS 也需考虑此类因素对商品和货架储位指派优化的影响.2)考虑逐步求精的动态货位调整:动态货位调整比一次性长远规划的货位指派更为简单有效[62],可基于逐步求精、渐进式优化的思路研究RMFS 的商品和货架的动态调整问题.3)考虑人因及设备等因素:传统拣货系统中人的因素对订单拣选效率影响巨大[63],货位指派需考虑人员的工作负荷[64]、技能[65]以及拥堵[66]等因素,RMFS 货位指派优化过程中也应考虑机器人拥堵、空闲率、电量以及作业人员技能、效率等因素.4)借鉴已有研究方法:譬如可用动态规划[67]、启发式[68]、数据挖掘[69]和聚类分析[70]等方法来研究RMFS 货位指派问题.

RMFS 的货位指派研究可分为商品储位指派研究和货架储位指派研究,现有文献主要利用排队论、整数规划、仿真、启发式规则以及智能优化等方法进行建模和求解.研究文献根据问题和方法分类综述如下:

1)商品储位指派研究

a)利用排队论方法

Lamballais 等[3]构建了RMFS 系统效能评估的排队网络模型,分别以最大订单吞吐量、平均订单拣选周期以及机器人利用率等指标评价了不同存储策略的系统绩效,结果表明采用基于货架周转率的商品分区存储策略可使系统的最大吞吐量提高50%左右,不足之处是文中假设每个货架只存储一种商品.在此基础上,onal 等[15]提出了一种爆炸存储的商品储位指派策略,构建了商品储位指派的排队论模型,结果表明随着爆炸水平的提高,订单拣选时间最多可降低16%.

b)利用混合整数规划方法

Xiang 等[20]在考虑爆炸存储策略和商品关联性的情况下,构建了RMFS 商品储位指派与路径规划协同优化的混合整数规划模型,设计的变邻域搜索算法在解的质量和求解时间方面比遗传算法分别好6.0%和3.3%,但未考虑缺货和补货的情况.蔺一帅等[21]也利用改进的协同优化遗传算法对RMFS 的商品储位指派和路径规划问题进行了协同优化,构建了商品储位指派与路径规划协同优化的混合整数规划模型.

2)货架储位指派研究

a)利用排队论方法

Nigam 等[4]利用排队论模型研究了RMFS 随机空位存储与最近空位存储策略的效率问题,结果表明随机空位存储的RMFS 系统空间利用率较高,而最近空位存储的RMFS 系统吞吐量较高.Yuan 等[17]进一步研究了随机存储、基于速度和基于类的货架储位指派策略,构建了不同存储策略绩效评估的排队模型,结果发现基于类的策略鲁棒性较强,可以适应不同仓库配置、布局的RMFS.

b)利用(混合)整数规划方法

在基于策略的货位指派研究中,文献[24,71]提出一种可显著提高RMFS 拣货效率的共享存储策略,文献[19]发现分区存储策略也能显著的提高RMFS 的拣货效率,在此基础上,Weidinger 等[18]对RMFS 的货架储位动态指派问题进行了研究,构建了混合整数规划模型,并利用自适应规划方法求解模型,将机器人的拣货总行程和编队数量分别降低了3.49%和2.17%,提高了RMFS 的拣货效率,但未构建反映货架储位动态变化关系的理论模型,文献[22]进一步构建了反映货架储位动态变化关系的混合整数规划模型,该动态优化模型可缩短30%左右的拣货距离.

此外也有文献利用仿真来研究RMFS 问题,仿真技术具有可视化效果好、人机交互灵活等优点,特别适合用于模型和优化效果的验证,例如Zou 等[28]利用仿真方法验证了半开放排队网络模型的正确性,Merschformann 等[29]则在规划模型基础上,利用仿真平台RAWSim-O 对RMFS 的随机、固定、最近空位以及基于类这几种典型的货架储位指派策略进行了对比研究,结果表明基于类的指派策略的效果更加显著.

综上所述,有关RMFS 货位指派的研究成果显著,但主要集中在对商品和货架储位指派的系统绩效评估方面,较少涉及商品储位指派和货架储位指派的协同优化,并且一般采用仿真验证指派策略的有效性.由于RMFS 与传统拣货系统在货位指派方面存在诸多不同,建议重点关注:1)考虑集成多种指派策略、并寻找最优策略的货位指派方法.2)由于RMFS 需要分别对商品和货架存储进行双重指派,应重点关注商品关联性对商品、货架储位指派的影响,重点研究商品和货架储位的双重指派这二者之间的内在联系和相关影响.3)特别关注动态货位指派问题,可基于逐步求精、渐进式优化的思想研究RMFS 的商品与货架的动态储位指派问题.4)在模型1 的基础上,根据RMFS 货位指派问题的特性,分别对商品和货架的(动态)货位指派模型进行研究,构建RMFS 货位指派问题的理论模型.

2.2 订单分批

订单分批是指为了提高订单拣选效率而把多个订单合并拣选的过程,其目的是为了降低订单拣选时货架的搬运次数、机器人的行走距离或时间[1].RMFS 的订单分批示意图如图6 所示,在RMFS订单分批优化过程中,需考虑每个订单 j 只能被指派到一个订单批次 i、每个批次 i 包含的订单数不能超过规定的数量 C 以及该批次所有商品必须都被拣选等约束条件,一般将货架搬运次数、机器人行走距离以及同批次内订单关联度等指标作为优化目标.

图6 RMFS 订单分批示意图
Fig.6 RMFS order batching diagram

最基本的订单分批问题的数学模型为[72]:

模型 2.

在模型2 中,J 表示客户订单,J={1,2,···,n} ;I为订单集合,I={1,2,···,m} ;C 为每批次订单最大容量;di 表示拣取批次 i 所有商品的代价(例如时间、距离);aij=1 表示订单 j (j ∈J) 被分配到批次 i(i ∈I),否则,aij=0 ;式(5)为目标函数,根据di的不同可取最大值或最小值(例如货架搬运次数最小、系统吞吐量最大等);式(6)为订单批次合理性约束;式(7)表示每个订单都必须被指派到一个批次;式(8)为变量和参数取值.

订单分批问题最早由Ackerman[73]提出,相比货位指派,订单分批优化对拣货效率的提升更加明显[74].根据订单信息是否已知,订单分批可分为在线订单分批和离线订单分批,其中在线订单分批更加符合实际情况.订单分批问题为NP 难题[75],一般利用(元)启发式算法[76–77]、数据挖掘[78]以及聚类和仿真[79]等方法研究离线订单分批问题,而在线订单分批问题则利用时间窗、启发式等方法研究[10],对离线订单分批问题的研究方法进行改进也可用于在线订单分批问题的研究[80],国内的马士华等[81]、李诗珍等[79]也对这方面的问题进行了深入研究.

RMFS 订单分批的目的是使货架搬运次数、订单拣选时间或延迟率等指标最小,该问题可分为两种情况:一是先对订单分批处理,然后将订单批次分配至拣货站台;二是先将订单分配至拣货站台,再进行订单分批处理.RMFS 与传统拣货系统的订单分批问题的不同表现在:1)分批对象不同:RMFS既可直接对订单分批,还可根据待拣商品的存储位置对机器人进行分批.2)考虑因素不同:传统拣货系统的订单分批问题一般只考虑拣货车容量、拣货员的工作负荷、拥堵以及路径策略等因素[77,82−83],RMFS 则还需要考虑机器人死锁、电量、故障以及利用率等问题.3)优化目标不同:RMFS一般将商品货架搬运次数、机器人利用率等指标作为优化目标[23].4)复杂度不同:RMFS 的订单分批需要考虑两种不同的订单分批情况,问题的复杂度更高.

RMFS 的订单分批可从以下几个方面借鉴传统订单分批问题的研究成果:1) RMFS 订单分批问题为NP 难题,可利用(元)启发式、数据挖掘、聚类等方法对RMFS 的订单分批进行研究.2)考虑拣货人员的影响:传统拣货系统认为拣货员的技能可提高批次拣货的效率[65],RMFS 的订单分批问题研究也需要考虑拣货员的技能、效率以及工作负荷等因素的影响.3)考虑订单交货期限:订单交期对订单拣选至关重要,与传统拣货系统类似[84],研究RMFS的订单分批问题也应考虑订单交期问题.4)考虑系统综合优化:为得到全局最优的订单分批方案,传统拣货系统将订单分批与路径规划、任务分配等问题进行协同优化研究[85],综合考虑RMFS 多个子问题的协同优化研究将是必然趋势.5)继续释放约束条件:与传统拣货系统类似,考虑拣货过程中出现的突发情况和随机因素(如插单、取消订单等) 对RMFS 订单分批问题的影响,使RMFS 订单分批的研究更加贴合实际情况.

现有文献以批次订单关联性最大、货架搬运次数最小等指标为优化目标,主要利用排队论、(混合)整数规划、聚类等方法研究RMFS 订单分批问题,对RMFS 订单分批的文献按照研究方法综述如下:

1)利用排队论方法

Yu 等[86]在人工拣货作业背景下,构建了订单分批与拣货分区协同优化的近似排队网络模型,该近似排队网络模型与仿真结果相比相对误差小于10%.考虑到订单分批策略对RMFS 效率的影响与AS/RS 类似,Hur 等[87]设计了评估AS/RS 系统绩效的排队网络模型,仿真结果表明其设计的模型的误差在0.1%到8.6%之间,这些研究为基于排队论方法研究RMFS 的订单分批问题提供了理论基础.

2)利用(混合)整数规划方法

Xiang 等[20]最先研究了RMFS 的订单分批问题,在模型2 的基础上构建了RMFS 订单分批问题的混合整数规划模型.

模型 3.

在模型3 中,N 为订单总数;M 为货架总数;P 为商品种类总数;K 为订单批次总数;E 为每批次包含的最大订单数;n 表示订单编号,n=1,2,···,N;m 表示货架编号,m=1,2,···,M; i,j表示商品种类,i,j=1,2,···,P;k 为订单批次编号,k=1,2,···,K;ain=1 表示订单 n 包括商品i,否则,ain=0; =1 表示商品 i 存储在货架m,否则=0;znk=1表示订单 n被分配给批次k,否则 znk=0;wkm=1表示因拣选批次k 而搬运货架 m, 否则,wkm=0;uik=1 表示批次 k 包含商品i,否则,uik=0;式(9)为目标函数,表示批次拣货过程货架搬运次数最小;式(10)表示每个订单都必须被指派到一个订单批次;式(11)表示分配到批次的订单总数不能超过规定的最大数量;式(12)表示商品的批次归属;式(13)表示被搬运的货架必须存储该批次所有的商品;式(14) 表示变量取值.此外Xiang 等[20]还设计了可变邻域搜索算法进行求解,结果表明货位指派与订单分批的协同优化显著降低了货架的搬运次数.Boysen 等[24]则将该问题扩展为订单分批、订单排序以及货架在拣货站台排序三个子问题,结果表明较优的订单调度与货架排序可使机器人运行时间最少可降低21%.AS/RS 与RMFS 同为“物至人”拣货系统,在订单分批方面存在诸多相同之处,王艳艳等[88]对AS/RS 和Carousel 拣货系统的订单分批问题进行研究,吴颖颖等[23]在此基础上研究了物至人拣货系统的订单排序问题,将货架出入库频率作为优化目标,优化后的系统拣货效率提高了15.9%.为了提高电商仓库的拣货效率,王旭坪等[74]和Zhang 等[10]在考虑订单交货期限的前提下对订单分批与排序协同优化问题进行了研究,构建了协同优化的整数规划模型,实现了80.365%的订单配送率.

3)利用聚类的方法

订单分批本质上是一个聚类过程,因而聚类策略是订单分批问题研究的重点,Chen 等[78]利用基于关联规则的聚类方法研究了人工拣货系统的订单分批问题,构建了订单分批的0-1 整数规划模型,利用关联规则算法进行模型求解,优化效果显著.与文献[78]不同,Al-Araidah 等[89]则设计了订单聚类的启发式规则,最多可减少44%的拣货时间.这些研究表明利用聚类、关联规则等数据挖掘方法进行RMFS 的订单分批研究将是一种有效途径.

综上,上述文献对RMFS 的订单分批问题做了初步研究,并取得了一定的优化效果,特别是AS/RS 的订单分批研究对RMFS 具有重要的借鉴意义.但RMFS 与传统拣货系统的订单分批问题存在诸多不同,应重点关注:1) 研究不同分批策略对RMFS 订单分批效果的影响,并比较各分批策略的优劣.2)RMFS 的订单分批应将商品关联性、需求频率以及货架搬运次数作为重要优化指标,并考虑机器人特性、状态(如电量、路径等)等因素对订单分批的影响.3)考虑订单取消以及插单等突发情况下的RMFS 订单分批问题.

2.3 任务分配及调度

传统拣货系统的任务分配是将拣货任务按一定方式分配给拣货员或堆垛机,让拣货员或堆垛机将待拣商品从存储位置拣出,目的是使拣货的总代价最小[1].与传统拣货系统不同,RMFS 是一个多机器人系统(Multi-robot systems,MRS),其任务分配是一个典型的多机器人任务分配(Multi-robot task allocation,MRTA)问题,具体包括两个方面,首先是将任务集分配给机器人群体,其次是协调机器人群体的行为,使其高效、可靠地完成任务[90].货架与机器人的任务分配示意图如图7 所示,在构建货架与机器人之间的分配模型时,可将机器人的行走距离、订单拣选效率以及机器人电量消耗等指标作为优化目标,并将机器人的电量限制、同一时刻货架只能被一个机器人搬运(反之亦然)等作为约束条件.MRTA 问题可建模为最优分配、整数规划、调度、网络流等模型[91],也可将其视为多旅行商问题(Multiple traveling salesmen problem,MTSP).MRTA 问题本质上也是一种广义指派问题,其数学模型为[92]:

图7 RMFS 的货架与机器人分配示意图
Fig.7 RMFS shelf and robot distribution diagram

模型 4.

在模型4 中,xij=1 表示将任务j 分配给Agent i (Agent 可为机器人或拣货/补货站台),否则 xij=0 ;cij 表示将任务 j 分配给Agent i 的工作代价或收益;rij 表示Agent i 完成任务 j 所需要的资源数量;ai 和 bi 分别表示Agent i 完成任务花费的最小和最大资源;式(15)为目标函数,根据选取的 cij 不同,可以取最小值或最大值;式(16)～ (17)为约束条件,表示任务与Agent 之间的分配关系;式(18)为变量和参数取值.

多数文献将机器人完成任务的代价最小、利用率或产出率最大等作为优化目标,并利用基于行为[93]、情感[94–95]、市场[96–97] 和最优化[11,98] 等方法求解MRTA 问题.其中基于市场和最优化的方法应用最为广泛,基于市场的方法是利用拍卖的思想进行任务分配,又可分为单物品拍卖和组合拍卖[90]两种,相比其他拍卖形式,组合拍卖能够提高拍卖效率,降低竞标人风险.由于组合拍卖的胜者决定问题已被证明是NP 难题,大多文献都利用启发式或元启发式算法[11,99]求解MRTA 问题,也有文献利用聚类[100]和仿真[101]的方法,值得一提的是陈培友等[102]将混沌理论引入了组合拍卖的任务分配过程.

RMFS 的任务分配问题与传统MRTA 问题存在诸多不同,主要有:1)任务分配复杂度不同:相比传统MRTA 问题,RMFS 是多任务多目标的任务分配,涉及订单与拣货站台、货架与机器人以及拣货(补货)站台与机器人三个方面[28–29],任务分配的复杂度更高.2)决策方式不同:RMFS 的任务分配采用去中心化的分布式智能体决策方式,相比传统MRTA 的集中决策控制系统鲁棒性更强、效果更好[9,42].3)约束条件不同:RMFS 的任务分配需要考虑订单交货时间、服务水平等特殊条件约束.4)任务分配环境不同:RMFS 的任务分配是在动态环境中进行,比静态环境中的MRTA 问题更加复杂.

RMFS 的任务分配问题可以按照广义指派问题进行模型构建,现有文献主要利用排队论、启发式规则、智能优化算法以及仿真等方法研究MRTA问题,相关研究文献按照研究方法分类综述如下:

1)利用排队论方法

Zou 等[28]以在线零售为背景,构建了排队网络模型来研究RMFS 的任务分配规则问题,并设计邻域搜索方法寻找最优分配规则,结果表明基于订单处理速度的分配规则要比随机分配规则更优,并且邻域搜索方法可以找到接近最优的分配规则,但文中未对机器人的分配规则进行研究.在此基础上,Roy 等[33]研究了多分区存储模式的RMFS 的机器人分配策略,构建了两阶段排队网络随机模型,结果表明,单个存储区应采用按批次分配机器人的方式,最短队列的分配方式则在多分区存储中系统吞吐量更大,最多可降低60%的订单拣选时间,但缺乏对随机模型参数更加广泛的评估研究.Yuan 等[27]则利用排队网络和共享协议研究了RMFS 搬运机器人的任务共享与分配问题.

2)利用启发式规则与仿真方法

Zhou 等[11]对RMFS 中的MRTA 问题进行研究,提出了同时考虑基于拍卖和聚类策略的平衡启发式机制,以机器人行走距离最小为目标,仿真发现平衡启发式机制能缩短机器人行走距离,提高了机器人利用率,并且在解的质量相近的情况下,平衡启发式机制的求解时间降低了5%～ 15%.但文献[11]在机器人完全自利、环境已知等条件假设的前提下研究了RMFS 的MRTA 问题,与实际RMFS 的MRTA 问题有一定的差距.Merschformann 等[29]则从拣货和补货两方面利用RAWSim-O 仿真平台研究了RMFS 任务分配,指出工程人员应该更加注重待拣订单的分配决策问题.Ghassemi 等[30]则进一步利用仿真的方法对RMFS 的任务分配问题进行研究,比较了分散和集中分配两种任务分配模式,结果表明,分散分配在保证解的质量的情况下,求解速度比集中算法快1～ 3 个数量级.RMFS 拣货过程的微观问题同样对拣货效率具有重要影响,Gue 等[42]利用仿真的方法研究了机器人系统的控制方法,设计了多机器人分散控制算法,结果表明分散控制相比集中控制方法更能避免机器人死锁的发生.值得一提的是,Yoshitake 等[34]利用实时全息调度方法研究了RMFS 的机器人实时调度问题,将RMFS 的生产率平均分别提高了6.7% (标准仓库)和12.5% (大规模仓库).

3)利用智能优化算法

文献[25]在文献[11]的基础上研究了RMFS的任务调度问题,分别利用强化学习和遗传算法进行问题求解.沈博闻等[8]则利用智能调度算法研究了RMFS 的任务分配调度问题,但对订单的分配处理过于理想化.袁瑞萍等[32]进一步研究了RMFS的任务调度问题,设计了改进的共同进化遗传算法进行问题求解,结果表明改进的算法缩短了求解时间(同步拣选模式下算法的求解时间是异步模式下求解时间的50%).随后的Zhang 等[35]也利用改进的遗传算法研究了RMFS 的机器人分配问题,与传统的基于规则的调度方法相比,改进的遗传算法更加有效.

综上,RMFS 的任务分配及调度研究成果丰硕,主要针对RMFS 的MRTA 问题的绩效指标评价、策略比较、拣货调度以及任务分配问题进行研究,但对MRTA 与RMFS 系统其他问题的协同优化研究不多.RMFS 任务分配及调度研究可借鉴传统MRTA 问题的研究理论和方法:1)利用组合拍卖的方法:RMFS 中订单、拣选站台、机器人以及货架之间存在复杂的交互关系,组合拍卖的方法更适合RMFS 的任务分配问题[103].2)考虑机器人能力:机器人数量、电量、速度以及停泊点等会影响RMFS的作业效率,在任务分配及调度研究过程中应予以重点关注,尤其应考虑机器人电量的影响[26–27,31,43].3)基于机器学习的方法:强化学习、深度学习等机器学习方法被广泛的用于解决MRTA 问题[104],可将其用于求解RMFS 的任务分配及调度问题.

RMFS 的任务分配及调度研究应重点关注以下几个方面的问题:1)综合研究订单与拣货站台、货架与机器人以及机器人与拣货站台之间的分配,作为多个双向组合拍卖,相比传统的拍卖方法更加复杂.2)考虑订单紧急程度及交货期限,确定合理的RMFS 订单分配及调度规则.3)考虑特殊情况下RMFS 任务分配问题,如出现订单取消、插单以及紧急订单时的任务动态分配及调度研究,还应考虑机器人的电量、拥堵等对任务分配及调度的影响.4)在模型4 的基础上构建RMFS 任务分配及调度的数学模型,为RMFS 多机器人任务分配及调度研究提供理论基础.

2.4 路径规划

路径规划是为拣货人员规划拣货时的行走路径,使最终的拣货距离最短.拣货员的路径规划问题一般视为旅行商问题(Travelling salesman problem,TSP),人工拣货系统常用穿越、回转、中点、最大间隙等策略规划拣货员的行走路径[1].与传统拣货系统不同,RMFS 的路径规划是一个多机器人路径规划(Multi-robot path planning,MRPP)问题,其目的是确保机器人在不发生碰撞、拥堵、死锁以及满足时间约束要求的前提下,同时对多个机器人进行路径规划,最终使机器人拣货行走的总距离最短,从而提高订单拣选的效率[12].如图8 所示为RMFS的路径规划示意图,图中以拣货过程(补货过程路径规划类似) 为例给出了一条机器人的行走路径,机器人需要将 i 位置的货架搬运到拣货站台,然后再将货架送到存储区的 j 位置存储,再将 i′ 位置的货架搬运至拣货站台拣货,随后再送至 j′ 位置存储,最终回到停泊区等待;RMFS 的MRPP 问题类似于TSP 问题,需要机器人遍历系统预先分配好的各个位置,使得机器人行走的路径最短,此外RMFS的MRPP 问题还应考虑机器人避障、电量限制等约束条件.

图8 RMFS 的路径规划示意图
Fig.8 RMFS path planning diagram

传统的MRPP 是一种多旅行商问题(Multi-Travelling salesman problem,MTSP)[105],其数学模型为:

模型 5.

MTSP 一般被定义为图 G=(V,A),V 表示节点集合;A 表示边的集合.在模型5 中,cij 表示旅行所需花费的代价;xij=1 表示机器人从点 i 到点j,否则,xij=0 ;式(19) 为目标函数,式(20) 和(21)表示这 m 个机器人必须回到同一个起始地点;式(22)、(23)和(25)为分配约束条件;式(24)为消除子回路的约束条件.MTSP 及其各类建模方法可具体参考文献[105].

MRPP 问题的求解方法有精确方法、启发式以及人工智能等[106],静态路径规划一般利用可视图、Voronoi 图、栅格图、人工势场等路径规划方法,并通过深度优先、广度优先、Dijkstra 以及A*和D*等算法求解[107],动态路径规划一般利用启发式或元启发式[108]、强化学习[109]等智能优化方法求解,也有学者利用双层模糊逻辑[110]、仿真技术[111]对多机器人路径规划问题进行研究.

RMFS 的路径规划与传统的MRPP 问题存在诸多不同,主要有:1)复杂程度不同:传统的MRPP是在开放空间内的路径规划,较少考虑预设行走路径,RMFS 的路径规划分为载货机器人路径规划(在巷道内的路径规划)和空载机器人路径规划(在无限制情况下进行路径规划,因为空载机器人可在巷道和货架下自由行驶)[3].2)约束条件不同:RMFS的路径规划需考虑订单交货时间或优先级等因素.3)存在任务切换代价:RMFS 的路径规划需考虑任务切换的代价,即机器人存储货架后再搬运下一货架所需行走的时间或距离[3].4)优化目标不同:相比传统的MRPP 问题,可将订单延迟率、任务切换代价等作为优化目标.

RMFS 的MRPP 问题可建模为MTSP 问题,已有文献主要利用图论、智能优化、强化学习、精确算法以及启发式方法研究RMFS 的路径规划问题,涉及RMFS 的MRPP 问题的文献按照研究方法分类综述如下:

1)利用图论的方法

传统拣货系统的路径规划问题通常可利用图论的方法建模[112],一般是先对RMFS 拣货区域进行栅格化的处理,然后将RMFS 的MRPP 问题视为栅格地图上的路径规划问题,例如张丹露等[38]针对RMFS 的MRPP 问题提出了一种基于动态加权地图的方法,与预约表下改进的A*算法相比,该方法能够将机器人行走时间降低17.4%.

2)利用智能优化算法和强化学习

由于MRPP 问题是NP 难题,一般无法求得最优解,更多利用智能优化算法求解,夏清松等[39]利用蚁群算法研究RMFS 的路径规划与避障的协同优化问题,并设计了MRPP 的避障规则,但文中有关机器人转向次数较少的假设不符合实际情况,且未考虑动态MRPP 问题.Lee 等[44]对RMFS 系统进行了扩展,用拣取机器人替代拣货员拣取商品,并将RMFS 的拣货过程看作特殊的车辆路径问题(Pick,place,and transport vehicle routing problem,PPTVRP)进行了研究,并利用智能优化算法求解.值得关注的是Dou 等[25]利用强化学习方法研究了RMFS 的MRPP 问题,实验结果显示其优化效果与遗传算法相近,但未进行更广泛的实例测试.

3)利用精确算法和启发式规则

沈博闻等[8]和Merschformann 等[12]利用A*及其改进算法研究了RMFS 的MRPP 问题,主要关注生成的路径有无堵塞和死锁,但未考虑机器人电量对路径规划的影响.Kumar 等[36]、Zhang 等[37]、Lee 等[40]以及于赫年等[41]针对无冲突的MRPP 问题进行了研究,主要利用Dijkstra、A*、启发式规则等算法实现了多机器人无冲突的路径规划.

综上,上述文献对RMFS 的MRPP 问题进行了初步研究,取得了一定的研究成果,但MRPP 与RMFS 其他问题的协同优化研究不多,也很少有文献研究动态情况下RMFS 的MRPP 问题,并且当前RMFS 的MRPP 问题研究一般采用仿真的方法,没有在理论上给出相应的数学模型.

RMFS 的路径规划研究可借鉴传统MRPP 问题的研究理论和方法:1)利用机器学习方法:强化学习、神经网络等机器学习方法可将路径规划、避碰、避障、死锁以及协作等问题统一解决,无须建立路径规划的环境模型和地图[113],相比传统方法具有更多优势.2)释放约束条件:考虑不确定环境及动态情况下的MRPP 问题,即考虑机器人故障、电量、障碍物等因素对MRPP 的影响.3)多类问题协同优化:将MRPP 问题与RMFS 的订单分批、任务分配等问题进行协同优化.4)限定范围的连续路径规划研究:与传统MRPP 问题类似,RMFS 的路径规划为一定范围(如图8 所示区域)内的连续路径规划问题,例如Zhang 等[37]、夏清松等[39]利用栅格图法研究了RMFS 在拣货区域内的连续路径规划.

RMFS 路径规划问题在借鉴传统MRPP 问题研究的基础上,应重点关注:1)设计载货机器人和空载机器人的不同路径规划规则,尤其考虑空载机器人可在货架下行驶的情况.2)考虑订单交期、退单、插单、退货以及紧急订单等情况对RMFS 的MRPP 问题的影响.3)将强化学习、深度学习等方法用于RMFS 的MRPP 问题的研究.4)在模型5的基础上对RMFS 的MRPP 问题进行研究,提出符合RMFS 实际情况的MRPP 理论模型.

2.5 研究方法

RMFS 系统建模和优化方法主要涉及排队论、图论、机器学习、数据挖掘以及Agent 建模等方法,本节对这些建模和优化方法进行综述,为RMFS 系统的后续研究指明方向.

1)排队论方法

排队论是研究系统随机聚散现象和随机服务系统工作过程的数学理论和方法,RMFS 的货位指派、订单分批、任务分配及调度等问题可利用排队论进行研究.例如Lamballais 等[3]、onal 等[15]、Nigam 等[4]以及Yuan 等[17]分别利用排队论对商品和货架的储位指派策略进行了研究;Yu 等[86]和Hur 等[87]均构建了传统拣货系统订单分批问题的排队网络评估模型,为利用排队论研究RMFS 的订单分批问题提供了参考;Zou 等[28]和Roy 等[33]也都利用排队网络模型研究RMFS 的任务分配和机器人分配问题.在利用排队论方法对RMFS 的优化研究中,主要是针对研究的问题特性构建系统绩效评估的排队网络模型,并通过仿真对优化策略和排队模型进行有效性验证,如图9 所示为RMFS 系统绩效评估的半开放排队网络模型.

图9 RMFS 绩效评估的半开放排队网络模型
Fig.9 Semi-open queueing network for performance estimation of RMFS

2)图论方法

图可直观的表示出事物之间的关系,传统拣货系统的路径规划问题可利用图论的方式进行表示和研究[1],RMFS 的路径规划作为一种多机器人的路径规划问题,也可利用图论的方法进行研究.例如张丹露等[38]针对RMFS 的多机器人路径规划问题提出了一种基于动态加权地图的研究方法,Zhang 等[37]和夏清松等[39]也利用图的表示方式对多机器人的路径规划问题进行了研究,如图10 为RMFS 的路径规划及其图表示.

图10 RMFS 路径规划及其图表示
Fig.10 RMFS path planning and its graph representation

3)机器学习方法

机器学习作为一种基于经验的学习方法,已经成功地应用于图像识别和自然语言处理等领域,Dou 等[25]最先利用强化学习方法研究了RMFS 的路径规划问题,证明了将机器学习方法用于RMFS优化研究的可行性和有效性,Zhang 等[47]则进一步将强化学习与进化计算组合对RMFS 快递分拣仓库布局的自动化设计进行了研究,此外神经网络[114]、深度学习[115]等机器学习方法也被广泛地用于求解多机器人任务分配、路径规划以及障碍物识别等问题,例如,Li 等[116]和Zhu 等[117]分别利用神经网络研究了多机器人的动态路径规划和任务分配问题;Heo 等[118]利用深度学习研究工业协作机器人的障碍物识别问题.基于强化学习的RMFS优化框架如图11 所示,可以看出,RMFS 系统中的机器人、货架、商品、订单、拣货/补货站台以及拣货员等要素可视为Agent,这里的环境为RMFS 系统,Agent执行的动作 at 可以是货位指派、订单分批、任务分配以及路径规划的策略或规则,Agent 通过动作at影响环境,更新环境状态 st,并从环境获得反馈 rt [119].

图11 基于强化学习的RMFS 优化框架
Fig.11 RMFS optimization framework based on Reinforcement Learning

4)数据挖掘方法

RMFS 的商品和货架储位指派需考虑商品销售的关联关系和畅销程度,订单分批也需知道商品之间的关联强度,任务分配和路径规划则需预测任务及资源的可用性,这些问题均可用聚类、预测等数据挖掘方法进行研究.例如Chen 等[78] 和Al-Araidah 等[89]分别利用聚类的方法对订单分批问题进行了研究,Pang 等[69]则进一步利用关联规则方法挖掘商品之间的需求关系,最终实现了商品储位指派优化.

5) Agent 建模方法

基于Agent 的建模方法(Agent-based modeling,ABM)是一种分布式的建模方法,可对主体的微观行为进行刻画,并可以观察宏观层面涌现的系统特征,更适合对复杂系统的建模[120].RMFS 作为分布式多Agent 系统,可利用ABM 方法进行建模研究,将整个拣货系统中的移动货架、机器人、拣选(补货)站台等看作自主决策的Agent,每个Agent都具有特定的行为规则、特征和属性,以一定规则在拣货系统中独立决策、自主运行,并与系统中其它Agent 和环境进行交互.ABM 的目标是对这些规则和交互关系进行调整和优化,实现整个拣货系统的状态最优.基于Agent 的RMFS 多机器人运作结构如图12 所示,ABM 可对RMFS 的Agent个体与拣货系统整体进行协调优化[121].众多文献从建模分析[122]、死锁、路径规划[123]等角度通过ABM方法研究多机器人系统,利用ABM 方法对RMFS进行建模还需考虑机器人之间的协同合作、避障、时间约束等问题.Alphabet Soup[124]、RAWSim-O[125] 等开源RMFS 仿真平台均基于ABM 方法,Bozer 等[45]也利用ABM 方法验证了RMFS 相比传统拣货系统具有更高的拣货效率和柔性.此外,Swarm、Repast、Netlogo 等ABM 的建模与仿真平台也为RMFS 的优化研究提供了可靠的技术支撑.

图12 基于Agent 的RMFS 多机器人运作结构
Fig.12 Agent-based multi-robot operation structure of RMFS

6)其他方法

值得特别关注的是,Petković等[48]给出了研究RMFS 的全新方法,文章利用隐马尔科夫模型和心理理论对RMFS 拣货过程中人的意图进行评价,并通过虚拟现实技术验证了模型的有效性,这涉及到机器学习、心理学等学科,表明了多学科交叉也是RMFS 未来重要的研究方法,例如Keung 等[126]利用基于云的网络物理系统研究了RMFS 的避障问题,进一步说明了学科交叉研究的可行性和必要性.

3 进一步研究方向

有关RMFS 的研究起步较晚,现有文献研究主要集中在系统分析、设计优化以及运作规划与控制方面,Azadeh 等[127]给出了系统分析、设计优化、运作策略以及系统比较4 个主要的研究方向,本文则提出以下更为具体的研究方向.

3.1 RMFS 仓库布局及配置研究

从提升RMFS 系统拣货效率的角度出发,针对RMFS 的仓库布局及配置设计和各种设计方案的系统绩效评估,提出的进一步的研究方向有:1)仓库存储区形状对拣货效率的影响研究.RMFS存储区普遍为矩形布置方式(例如图1(b)所示),在拣货和补货站台位置固定的情况下,仓库存储区的长宽比一方面可能会影响拣货过程机器人的路径规划和拥堵情况,导致拣货效率下降;另一方面当拣货站台一侧对应的存储区宽度较窄时,将造成较多存储畅销商品的货架只能存储在距离拣货站台较远的储位,最终导致拣货过程机器人搬运货架的距离加长、拣货效率降低.因此,对仓库存储区布局的优化是提升RMFS 拣货效率的重要研究方向.2)拣货站台与补货站台的比例对拣货效率的影响研究.拣货站台与补货站台的数量比对订单拣选效率、拣货与补货的平衡关系以及拣货/补货员的作业负荷都具有重要影响,例如拣货站台较少,则可能出现拣货员作业负荷过大、订单拣选时间长以及部分补货站台空闲的情况;若补货站台较少,则会出现补货员作业负荷过大、库存商品短缺、订单拣选时间长以及部分拣货站空闲的情况;因此,拣货站台和补货站台比例优化对提升RMFS 的拣货效率具有重要意义.3)机器人数量、速度、利用率、待命停泊点以及充电策略等因素对拣货效率的影响研究.在拣货过程中,机器人的数量和速度决定了一次性最多能搬运的货架数量和机器人的行走时间;机器人停泊点则对连续作业机器人的行走距离具有重要影响;机器人充电策略则决定了机器人充电过程的调度方式,对机器人的可用率和货架搬运效率都具有重要影响.因此,在考虑拣货成本、资源限制及利用率等因素的情况下,如何合理配置机器人数量、速度以及规划机器人的充电策略将是未来的重要研究方向.4)机器人结构设计与操作效能的提升研究.RMFS机器人的结构设计可分为硬件结构设计和控制系统结构设计,其中硬件结构设计决定了机器人搬运货架的方式、可承载的最大重量、行驶速度以及充电方式,控制系统结构设计则涉及机器人控制方式(集中控制或分散控制)、避障规则、充电策略以及通信切换等问题.操作效能的提升涉及货架的一体化设计、拣货/补货人员的技能熟练程度等人因问题研究.这方面涉及运筹优化、机械设计以及人因工程的交叉学科研究,对提升RMFS 拣货效率具有重要意义.

3.2 考虑随机因素及动态情况的RMFS 优化研究

从减少理想化假设条件、考虑随机因素影响和动态情况出发,提出的主要研究方向有:1)考虑动态情况下的货位指派、订单分批、任务分配、路径规划研究.相比静态问题的研究,动态货位指派比一次性货位优化更具优势,更能反映拣货过程随时间的变化规律;动态货位指派也更加符合实际情况,例如在线订单分批能根据客户的动态需求进行更加合理的订单分批.因此,针对RMFS 的商品和货架储位动态指派、在线订单分批、动态任务分配以及动态路径规划等问题的研究将是重要的优化方向.2)考虑机器人死锁、损坏等突发情况的研究.在拣货过程中,机器人出现故障是难免的,为了保证拣货过程顺利进行并提高机器人的利用率,对拣货过程机器人死锁、损坏等突发情况的研究十分必要.3)考虑订单取消、插单、退货等情况的研究.在电商环境下,客户可能因多种原因出现取消订单、催单(订单加急)以及退货等情况,虽然已有文献对RMFS的静态订单分批问题进行了初步研究,但未考虑订单取消、插单等情况,建议在RMFS 拣货优化过程中考虑订单取消、插单、退货等情况,此外订单取消、插单对系统绩效的影响评估也可作为一个重点研究方向.4)考虑拣货和补货人员工作负荷、人因以及技能熟练程度对拣货效率的影响研究.拣货和补货人员的工作负荷、人因以及技能熟练程度对拣货效率具有重要影响,例如较少的工作负荷容易造成拣货和补货人员空闲,较多则会引发疲劳、压力过大等情况的出现;长时间固定姿势的劳作容易造成人体机能和器官的损伤(例如拣货和补货人员经常弯腰);拣货人员和补货人员的技能熟练程度决定了拣货站台和补货站台的服务速率,对站台区域的拥堵情况和拣货效率具有重要影响.虽然人因、技能熟练程度等指标难以量化,但这方面的研究却十分必要.

3.3 RMFS 的资源调度研究

RMFS 的调度问题涉及货架、机器人、订单、商品、拣货站台以及补货站台等多种资源,针对RMFS系统的资源调度问题,提出的主要研究方向有:1)考虑需求关联性的商品及货架储位调度研究.将需求关联性强的商品指派到相同货架存储,可减少货架搬运次数;将存储畅销商品的货架指派到靠近拣货站台的位置存储,可降低货架搬运距离,因此考虑需求关联性的商品及货架的储位调度研究是提高拣货效率的重要优化方向,这方面研究重点关注商品需求关联性计算,货架储位动态调度等.2)订单的分批策略及规则研究.是采用在线订单分批还是离线订单分批、或者同时考虑这二者的混合策略,是将订单分配给拣货站台后再分批还是先分批再分配给拣货站台,是根据订单的相似程度分批还是根据搬运的货架分批,都是目前RMFS 订单分批优化中亟需解决的问题;并且在线订单分批需考虑订单的动态变化关系,相比离线订单分批更加复杂.3)机器人与货架、拣货/补货站台以及充电设施的协同调度策略及规则研究.机器人是RMFS 的主要搬运工具,在拣货过程中,机器人与货架、拣货/补货站台以及充电设施之间存在复杂的协同调度关系,包括机器人任务分配和充电设施分配调度等一系列问题,因此,机器人与货架、拣货/补货站台以及充电设施的协同调度策略及规则研究是RMFS 系统优化必须面对的问题.

3.4 多问题协同优化研究

RMFS 作为复杂决策系统,货位指派、订单分批、任务分配以及路径规划等问题之间存在紧密的内在联系,例如任务分配之前必须完成货位指派和订单分批,路径规划必须考虑商品及货架的存储位置.因此,多个问题的协同优化更加符合RMFS 的运作过程,是实现系统全局最优的关键,将成为RMFS 优化研究的重要趋势,但多个问题的协同优化研究在问题描述、模型构建、算法设计以及问题求解等方面都更加复杂,后续可重点对多目标(问题)协同优化模型构建、算法设计及问题求解进行深入研究.

3.5 优化方法研究

针对RMFS 的优化方法研究提出两点主要的研究方向:1)在现有的RMFS 仿真软件的基础上应开发新的算法和优化模块.RMFS 的系统效能评估、各因素对拣货效率的影响等问题可能无法构建精确的优化模型,只能通过离散仿真的方法进行研究.因此,类似Alphabet Soup、RAWSim-O 等仿真软件的开发和应用是必不可少的.2) 设计针对RMFS 的求解大规模问题的智能优化算法.RMFS的应用背景通常是大型电商企业(例如亚马逊、京东),系统所包含的货架、机器人、订单等资源的数量庞大,尤其在面临类似“双十一”等促销活动时,对RMFS 的运作效率和服务质量都是极大的挑战,因此,研究求解大规模问题的智能优化算法尤为重要.

3.6 RMFS 与新一代人工智能的交叉研究

随着通信和信息技术的发展,人工智能发展进入了新阶段,2017 年7 月国务院发布的《新一代人工智能发展规划》将人工智能定位为国家战略,明确指出“人工智能技术应用成为改善民生的新途径”、“人工智能成为带动我国产业升级和经济转型的主要动力”.2014 年10 月国务院发布的《物流业发展中长期规划(2014—2020 年)》中将物流业定义为支撑国民经济发展的基础性、战略性产业,而RMFS 作为一种新型的智能物流仓储系统,是智能物流的一个重要研究方向,也是我国物流业降本增效、产业升级的主要动力,其研究和应用离不开机器学习、多智能体、大数据、计算机视觉及自然语言处理等新一代人工智能技术的支撑.RMFS 与新一代人工智能交叉的研究方向有:1)基于深度强化学习(Deep reinforcement learning,DRL)的优化研究.强化学习能够解决无模型序列决策问题,但在处理高维变量问题时常常会面临巨大挑战,而深度学习则具备从高维变量中自动学习表征的能力,DRL 则将这两者结合起来,为RMFS 这类复杂高维问题的决策和优化提供了端到端的解决方案,让RMFS 在需求多变的复杂环境中高效完成任务;此外RMFS 是一个典型的多Agent 系统,这些Agent之间相互合作或竞争,单一Agent 系统无法满足RMFS 系统决策的需要,因此可进一步基于多主体的深度强化学习(Multi-agent deep reinforcement learning,MARL)研究RMFS,对RMFS 系统中Agent 之间的感知发现、知识获取、竞争合作以及演化进行深入研究,这将成为RMFS 智能优化的研究热点[128].2) RMFS 机器人操作技能学习研究.RMFS机器人在完成拣货和上架任务时,需要执行移动、避障、抓取、放置、拆垛与码垛等一系列复杂的动作,RMFS 机器人的操作技能、执行动作的精确度和效率是RMFS 高效运行的关键,目前机器人技能大多通过人工预定义的规则实现,无法应对动态复杂的物流场景,让RMFS 机器人通过与环境交互得到经验数据,从经验数据中自主学习,一方面可以让RMFS 机器人具有自我优化的能力,同时让RMFS的任务部署更加灵活和用户友好.RMFS机器人操作技能自主学习涉及构建机器人操作技能模型、设计学习策略等关键问题,已有文献从动力学与学习算法相结合、DRL 等方面开展研究[129],后续研究可关注RMFS 机器人高效学习和模型的可解释,在此基础上构建RMFS 机器人操作技能学习框架.3) RMFS 系统自主学习能力研究.RMFS 机器人在高度动态、复杂多变的环境(商品装卸、货架搬运以及各机器人动态移动)下工作,经常会出现碰撞、失效、电量不足等突发情况,如何使RMFS机器人在长期运行中与复杂多变的环境相适应是RMFS的一个研究热点,这方面涉及到RMFS 机器人的环境地图构建与动态维护、重定位及动态场景感知与理解等基础任务能力的研究.在RMFS 的环境表征的研究方面,可基于数据融合与信息增强,通过多层次传感器数据融合得到的环境信息来提升RMFS 环境表征能力,为RMFS 机器人提供更可靠的决策信息,在此基础上利用DRL 的方法在RMFS 机器人与环境的交互的基础上进行学习,提升RMFS 机器人自主环境适应能力,这需要解决机器人基于在线获取的弱标注数据进行学习这一问题,它是使RMFS 机器人具有长期自主环境适应能力的关键;在场景感知与理解方面建议基于深层次语义信息挖掘来获取RMFS 场景中物体间的属性关联,来提升RMFS 移动机器人场景认知能力[130].4)基于计算机视觉技术和自然语言处理的优化研究.近年来,机器视觉和自然语言处理研究均取得了重大的理论突破,并分别成功地运用于自动驾驶和机器翻译等领域,计算机视觉技术可提升RMFS机器人识别商品的准确度;基于语音识别的人机交互技术可提升拣货效率,例如RMFS 机器人通过语音与拣货员(补货员) 交互降低拣货(补货) 差错.5)基于大数据的优化研究.大数据是实现智能决策的重要支撑,大数据分析可实现客户画像构建、商品销售分析以及RMFS 系统存储决策优化,因而是RMFS 优化研究的重要方向,例如可利用数据挖掘的聚类和关联规则等算法得到商品销售频率和需求关系性,来优化RMFS 的订单分批和货位指派.

4 结论

RMFS 作为一种新型的“物至人”拣货系统,相比传统拣货系统具有拣货效率高、柔性强等诸多优势,随着电子商务的迅猛发展,RMFS 已在物流行业取得成功的应用,同时针对RMFS 的优化研究已成为热点研究领域.本文主要针对RMFS 的货位指派、订单分批、任务分配、路径规划以及建模方法等问题进行了文献总结和述评,并给出了未来的研究方向.以上工作抛砖引玉,以期促进RMFS 拣货效率的进一步提升,使其更好地为电子商务的订单拣选服务.