基于移动机器人的拣货系统RMFS的实践应用案例

2024-04-19  

订单拣选是将商品从其存储位置拣出以满足客户订单需求的过程,订单拣选是典型的劳动密集型作业,占仓库运作总成本的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的实践应用及学术研究提供参考。

01  RMFS简介

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

d5613146-5214-11ee-a25d-92fbcf53809c.png

图1 RMFS拣货区域布局图

wKgaomUBfOSAe3UFAAGsksTvw0M840.png

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

d5d11952-5214-11ee-a25d-92fbcf53809c.png

图3 RMFS拣货优化流程

d5fc2f20-5214-11ee-a25d-92fbcf53809c.png

图4 RMFS优化理论框架 02  RMFS研究现状

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

表1 RMFS研究文献汇总

d6195a3c-5214-11ee-a25d-92fbcf53809c.png

2.1 货位指派

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

d64aadd0-5214-11ee-a25d-92fbcf53809c.png

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

d66c4a1c-5214-11ee-a25d-92fbcf53809c.png

在模型1中,d68360c6-5214-11ee-a25d-92fbcf53809c.png表示将商品(或货架)d6960550-5214-11ee-a25d-92fbcf53809c.png存储在位置d6a4ee44-5214-11ee-a25d-92fbcf53809c.png,否则d6b02bb0-5214-11ee-a25d-92fbcf53809c.pngd6bd5f9c-5214-11ee-a25d-92fbcf53809c.png表示将商品(或货架)d6960550-5214-11ee-a25d-92fbcf53809c.png存储在货架或位置d6a4ee44-5214-11ee-a25d-92fbcf53809c.png的拣货代价(或收益);式(1)为目标函数,根据选取的d6bd5f9c-5214-11ee-a25d-92fbcf53809c.png不同,可分为求最小值或最大值(例如拣货时间或距离最小、拣货效率最大等);式(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订单分批优化过程中,需考虑每个订单d6e66946-5214-11ee-a25d-92fbcf53809c.png只能被指派到一个订单批次d6f44fca-5214-11ee-a25d-92fbcf53809c.png、每个批次d6f44fca-5214-11ee-a25d-92fbcf53809c.png包含的订单数不能超过规定的数量d7078a18-5214-11ee-a25d-92fbcf53809c.png以及该批次所有商品必须都被拣选等约束条件,一般将货架搬运次数、机器人行走距离以及同批次内订单关联度等指标作为优化目标。

d713bf90-5214-11ee-a25d-92fbcf53809c.png

图6 RMFS订单分批示意图 最基本的订单分批问题的数学模型为[72]:

d743eb3e-5214-11ee-a25d-92fbcf53809c.png

在模型2中,d754a9ec-5214-11ee-a25d-92fbcf53809c.png表示客户订单,d765e734-5214-11ee-a25d-92fbcf53809c.pngd779f904-5214-11ee-a25d-92fbcf53809c.png为订单集合,d7856a5a-5214-11ee-a25d-92fbcf53809c.pngd79976e4-5214-11ee-a25d-92fbcf53809c.png为每批次订单最大容量;d7a744f4-5214-11ee-a25d-92fbcf53809c.png表示拣取批次d7b4b72e-5214-11ee-a25d-92fbcf53809c.png所有商品的代价(例如时间、距离);d7c0fc00-5214-11ee-a25d-92fbcf53809c.png表示订单d7cdbcce-5214-11ee-a25d-92fbcf53809c.png被分配到批次d7da95fc-5214-11ee-a25d-92fbcf53809c.png,否则,d7e514d2-5214-11ee-a25d-92fbcf53809c.png;式(5)为目标函数,根据d7f21a24-5214-11ee-a25d-92fbcf53809c.png的不同可取最大值或最小值(例如货架搬运次数最小、系统吞吐量最大等);式(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订单分批问题的混合整数规划模型。

d7fedf16-5214-11ee-a25d-92fbcf53809c.png

在模型3中,d81f37e8-5214-11ee-a25d-92fbcf53809c.png为订单总数;d82f3580-5214-11ee-a25d-92fbcf53809c.png为货架总数;d8387492-5214-11ee-a25d-92fbcf53809c.png为商品种类总数;d847253c-5214-11ee-a25d-92fbcf53809c.png为订单批次总数;d8530438-5214-11ee-a25d-92fbcf53809c.png为每批次包含的最大订单数;d85c1ae6-5214-11ee-a25d-92fbcf53809c.png表示订单编号,d86a36da-5214-11ee-a25d-92fbcf53809c.pngd87c3f42-5214-11ee-a25d-92fbcf53809c.png表示货架编号,d8895d80-5214-11ee-a25d-92fbcf53809c.pngd896d3de-5214-11ee-a25d-92fbcf53809c.png表示商品种类,d8a19b70-5214-11ee-a25d-92fbcf53809c.pngd8b0aa7a-5214-11ee-a25d-92fbcf53809c.png为订单批次编号,d8bd1166-5214-11ee-a25d-92fbcf53809c.pngd8c95d90-5214-11ee-a25d-92fbcf53809c.png表示订单d8d6662a-5214-11ee-a25d-92fbcf53809c.png包括商品d8e97a94-5214-11ee-a25d-92fbcf53809c.png,否则,d8f2d562-5214-11ee-a25d-92fbcf53809c.pngd90152ea-5214-11ee-a25d-92fbcf53809c.png表示商品d90c9d80-5214-11ee-a25d-92fbcf53809c.png存储在货架d91a2a54-5214-11ee-a25d-92fbcf53809c.png,否则d92580a2-5214-11ee-a25d-92fbcf53809c.pngd931fe9a-5214-11ee-a25d-92fbcf53809c.png表示订单d8d6662a-5214-11ee-a25d-92fbcf53809c.png被分配给批次d948321e-5214-11ee-a25d-92fbcf53809c.png,否则d952682e-5214-11ee-a25d-92fbcf53809c.pngd95d21b0-5214-11ee-a25d-92fbcf53809c.png表示因拣选批次d8b0aa7a-5214-11ee-a25d-92fbcf53809c.png而搬运货架d87c3f42-5214-11ee-a25d-92fbcf53809c.png,否则,d98224a6-5214-11ee-a25d-92fbcf53809c.pngd98e7206-5214-11ee-a25d-92fbcf53809c.png表示批次d8b0aa7a-5214-11ee-a25d-92fbcf53809c.png包含商品d90c9d80-5214-11ee-a25d-92fbcf53809c.png,否则,d9aeaaa8-5214-11ee-a25d-92fbcf53809c.png;式(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是一个多机器人系统(MRS),其任务分配是一个典型的多机器人任务分配(MRTA)问题,具体包括两个方面,首先是将任务集分配给机器人群体,其次是协调机器人群体的行为,使其高效、可靠地完成任务[90]。 货架与机器人的任务分配示意图如图7所示,在构建货架与机器人之间的分配模型时,可将机器人的行走距离、订单拣选效率以及机器人电量消耗等指标作为优化目标,并将机器人的电量限制、同一时刻货架只能被一个机器人搬运(反之亦然)等作为约束条件。 MRTA问题可建模为最优分配、整数规划、调度、网络流等模型[91],也可将其视为多旅行商问题(Multiple traveling salesmen problem,MTSP)。MRTA问题本质上也是一种广义指派问题,其数学模型为[92]:

d9bfae8e-5214-11ee-a25d-92fbcf53809c.png

图 7  RMFS的货架与机器人分配示意图

d9dec94a-5214-11ee-a25d-92fbcf53809c.png

在模型4中,da005dbc-5214-11ee-a25d-92fbcf53809c.png表示将任务da0d6aca-5214-11ee-a25d-92fbcf53809c.png分配给da1a0352-5214-11ee-a25d-92fbcf53809c.png(Agent可为机器人或拣货/补货站台),否则da278cc0-5214-11ee-a25d-92fbcf53809c.pngda34289a-5214-11ee-a25d-92fbcf53809c.png表示将任务da0d6aca-5214-11ee-a25d-92fbcf53809c.png分配给da1a0352-5214-11ee-a25d-92fbcf53809c.png的工作代价或收益;da53d348-5214-11ee-a25d-92fbcf53809c.png表示da1a0352-5214-11ee-a25d-92fbcf53809c.png完成任务da0d6aca-5214-11ee-a25d-92fbcf53809c.png所需要的资源数量;da74e33a-5214-11ee-a25d-92fbcf53809c.pngda7ebb30-5214-11ee-a25d-92fbcf53809c.png分别表示da1a0352-5214-11ee-a25d-92fbcf53809c.png完成任务花费的最小和最大资源;式(15)为目标函数,根据选取的da34289a-5214-11ee-a25d-92fbcf53809c.png不同,可以取最小值或最大值;式(16) ~ (17)为约束条件,表示任务与da1a0352-5214-11ee-a25d-92fbcf53809c.png之间的分配关系;式(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% (大规模仓库)。

文章来源于:电子工程世界    原文链接
本站所有转载文章系出于传递更多信息之目的,且明确注明来源,不希望被转载的媒体或个人可与我们联系,我们将立即进行删除处理。