机器人履约系统任务分配与货架储位再指派联合优化.pdf

投稿网址:2023 年 第23 卷 第26 期2023,23(26):11271-11科 学 技 术 与 工 程Science Technology and EngineeringISSN 16711815CN 114688/T收稿日期:2022-09-21修订日期:2023-06-13基金项目:国家科技支撑项目(2018YFB1402500);黑龙江省自然科学基金(LH2023G009);黑龙江省博士后科研启动金项目(LBH-Q21102)第一作者:李腾(1982),女,汉族,河北徐水人,博士,副教授。研究方向:智慧物流。E-mail:。引用格式:李腾,张茹兰,丁佩佩.机器人履约系统任务分配与货架储位再指派联合优化J.科学技术与工程,2023,23(26):11271-11281.Li Teng,Zhang Rulan,Ding Peipei.Joint optimization for automated guided vehicle task assignment and pod repositioning in robotic mobilefulfillment systemJ.Science Technology and Engineering,2023,23(26):11271-11281.机器人履约系统任务分配与货架储位再指派联合优化李腾1,张茹兰2,丁佩佩3(哈尔滨商业大学管理学院,哈尔滨 150028)摘 要 为优化移动机器人履约系统(robotic mobile fulfillment system,RMFS)中移动机器人运行成本,提出一种考虑移动机器人任务分配和货架储位再指派的联合优化策略。以移动机器人完成任务成本最小为优化目标,构建考虑移动机器人重载和空载成本差异的数学模型,并用遗传算法对模型进行求解。经与返回原位置及返回距离拣选台最近位置两种策略进行仿真实验对比,结果表明联合优化策略可以有效降低移动机器人完成任务成本,提高拣选效率。关键词 移动机器人履约系统;任务分配;货架储位再指派;联合优化中图法分类号 TP242.2;文献标志码 AJoint Optimization for Automated Guided Vehicle TaskAssignment and Pod Repositioning in Robotic Mobile Fulfillment SystemLI Teng1,ZHANG Ru-lan2,DING Pei-pei3(Management School,Harbin University of Commerce,Harbin 150028,China)Abstract To optimize the operating cost of mobile robots in the robot mobile fulfillment system(RMFS),a joint optimization strat-egy was proposed that considers mobile robot task assignment and pod repositioning.A mathematical model was constructed,conside-ring the difference between the heavy load and the no-load cost of the mobile robot,with the goal of minimizing the cost of completingthe task by the mobile robot.The model was solved using the genetic algorithm.Compared with the two strategies of returning to theoriginal position and returning to the closest position to the picking station,the results show that the joint optimization strategy can ef-fectively reduce the cost of completing tasks by mobile robots and improve picking efficiency.Keywords robotic mobile fulfillment system;task assignment;pod repositioning;joint optimization 移动机器人履约系统(robotic mobile fulfillmentsystem,RMFS)是一种新型的“货到人”拣选系统,与传统的人工和自动化立体仓库系统 AS/RS(automa-ted storage and retrieval system)拣选相比,其在拣选效率、仓库空间利用率等方面都存在着明显的优势1。货架储位再指派问题是 RMFS 所特有的,其是指通过规划货架完成拣选任务后储存的位置,缩短移动机器人行驶距离,降低成本,提高仓库拣选效率的优化问题。Krenzler 等2是较早研究此类问题的学者,其建立了考虑货架在拣选台队列位置和移动机器人数量,不考虑客户订单商品储位情况和补货问题的简化模型,采用了二进制、最近位置、固定位置、随机位置、迭代二进制遗传以及俄罗斯方块算法求解,得出在大型算例应用中俄罗斯方块算法更为有效。Yuan 等3基于随机、类、周转率原则构建排队模型,得出基于两类或三类的储位分配策略可以实现大多数潜在益处且益处会随货架周转率的变化而变化。Weidinger 等4进一步研究将货架储位再指派问题转化成特殊的区间调度问题,提出自适应货架储位再指派策略。Ji 等5将货架储位再指派问题分成了一次对一个货架指派和一次对多个货架进行指派两类问题,建立了考虑货架未来搬运距离的优化模型。Riml 等6提出了一种高效但计算成本较高的蒙特卡洛树法。随着研究的深入,越来越多的学者在进行相关问题研究时将货架储位再指派作为考虑的因素。徐翔斌等7提出了一种考虑货架与储位匹配程度的货架再指派策略。Roy 等8在多存储区域移动机器人分配策略问题的研究中,对随机货架储位再指派策略下的移动机器人多存储区域分配策略性能投稿网址:进行了研究。Li 等9对高密度移动货架系统中任务分配、路径规划及冲突、阻塞解决问题进行了研究。Merschformann 等10在研究任务分配、货架选择、货架储位再指派问题对系统运行指标影响时,指出任务分配策略对系统吞吐量指标影响最大。因此,货架储位再指派策略也常常在任务分配问题研究中被考虑。Zhang11、Yuan 等12和孙君阳等13研究了货架返回原位置策略下的多移动机器人调度问题。Gharehgozli 等14提出考虑订单优先级的任务分配问题并对存在多货架返回位置可选情况下的货架位置选择问题进行了讨论。Yoshitake等15建立了考虑货架和移动机器人状态的实时调度方法,给出货架返回距离移动机器人最近储存位置的策略。Riml 等16提出了一种实时决策形式化的随机数学建模框架,研究了在随机输入订单情况下,RMFS 中包括订单排序、储位指派、货架储位再指派等大多数操作决策问题。Bao 等17提出一种同时考虑任务分配和货架储位再指派的策略,即货架返回到指派位置与下一任务点距离之和最小位置的策略。在已有相关文献中针对货架储位再指派问题的研究多为对货架储位再指派单一问题或如在任务分配、多机器人调度、储位规划中考虑货架储位再指派策略的研究,而针对货架储位再指派问题和RMFS 其他规划问题的联合优化研究文献较少。移动机器人完成拣选任务过程中货架返回位置是影响移动机器人行驶距离和运行时间的重要因素,不同运行状态下能耗的差别也是影响移动机器人完成任务成本的重要因素。因此在已有研究文献基础上,现研究考虑下一任务位置的任务分配与货架储位再指派联合优化问题,将移动机器人运行成本作为主要目标,细化单位时间移动机器人重载与空载成本差异。探讨 RMFS 实现移动机器人完成任务成本更优,拣选效率更高的策略,丰富相关理论,并为企业提供参考。1 RMFS 描述RMFS 主要由拣选台、可移动货架、通道以及移动机器人组成,其布局如图 1 所示。在“货到人”拣选模式下,当仓库管理系统接收到订单后,按照订单波次,系统使用一定的调度规则对任务进行一次性分配。在进行任务分配前,移动机器人的状态是不明确的,任务可以分配给任意移动机器人完成。如果任务所分配的移动机器人处于忙碌状态,则需要等待该机器人完成任务后,再对分配任务进行搬运。移动机器人开始执行任务(如图 1 中空载标记位置)后,将按照任务序列对任务货架进行依次搬运。在移动机器人任务执行过程中,移动机器人首先会从初始位置移动到被分配任务所需要的货架位置(如图 1 中实线指向标号为 1 的货架),再将货架搬运至任务指定拣选台(如图 1 中实线指向拣选台 5),由拣选人员根据任务订单商品信息对货架上的商品进行拣选、完成扫描和打包。当系统中指定拣选台被占用时,移动机器人会在指定的拣选台进行排队等待,直到被拣选完毕。移动机器人将货架搬回存储区,在存储区中选择某一位置放回货架(如图 1 中星形标记位置),遵循不同货架储位再指派策略,移动机器人会将货架放在不同空位上并在货架下等待执行下一任务的命令。2RMFS 任务分配与货架储位再指派联合优化的数学模型2.1 联合优化问题描述移动机器人运行时,根据移动机器人状态不同可以分为重载(如图 1 中重载标记)和空载(如图 1中空载标记)两种状态。不难发现,移动机器人在完成拣选任务的过程中,重载与空载状态是交替进行的,其中移动机器人行驶的重载距离包括移动机器人搬运货架到拣选台和从拣选台返回到储存区的两段距离,空载距离为移动机器人接收到任务后,从所在地点前往所需搬运任务货架地点之间的距离。移动机器人重载状态需要托载沉重的货架,因此重载与空载行驶能耗不同,为进一步减小移动机器人完成任务总成本,应细化移动机器人重载和空载成本差距。在空载运行中,移动机器人行驶距离由移动机器人初始位置和任务位置决定;在重载运行中,移动机器人行驶距离由任务位置、拣选台位置和返回存储区位置决定。其中任务位置和拣选台位置与订单相关由管理信息系统指定,相对固定。而移动机器人初始位置与返回存储区位置,由于在移动机器人即将完成当前任务列表时,新的任务列表会提前发放给移动机器人等待执行,即除第一轮任务执行开始外,移动机器人执行不同轮次任务中的初始位置等于该移动机器人上一任务货架返回位置,因此移动机器人初始位置和返回存储区位置主要由货架储位再指派策略决定。实际中常用的货架储位再指派策略主要有两种,返回原位置策略和返回距离拣选台最近位置策略,其中返回原位置策略(如图 1 中蓝色虚线所示,下文统一策略 1 表示),其是指将拣选完成后的货架27211科 学 技 术 与 工 程Science Technology and Engineering2023,23(26)投稿网址:图 1 RMFS 布局图Fig.1 Layout of RMFS由移动机器人搬运至存储货架的原位置。返回距离拣选台最近策略(如图 1 中橙色虚线所示,下文统一用策略 2 表示),它是指将拣选完成的货架由移动机器人搬运至距离拣选台最近的空储位上。本文研究提出了一种考虑任务分配的货架储位再指派策略(如图 1 中红色虚线所示,下文统一用策略 3 表示),当货架完成拣选后,移动机器人根据其执行的任务列表,将货架放置在返回储存区指派位置与到达任务列表中下一任务位置联合距离最小的空储位上。对 3 种策略下移动机器人搬运货架行驶距离进行算例讨论,如图 1 所示,对地图进行栅格化处理后,将每一单位小格设置为 1 个单位距离。移动机器人从初始位置搬运任务 1 到达拣选台需要移动距离为 21 个单位距离(如图 1 中黑色实线行走距离),使用策略1 下移动机器人从拣选台到任务1 返回位置再到达任务 2 需要移动 33 个单位距离(如图 1中蓝色虚线行走距离);使用策略 2 下移动机器人需要移动47 个单位距离(如图1 中橙色虚线行走距离),而使用策略 3,机器人移动 31 个单位距离(如图 1 中红色虚线行走距离),相较于前两种策略,策略 3 有效地缩小了移动机器人的行驶距离,算例结果表明策略 3 对完成任务移动机器人行驶距离优化效果最好。为验证算例的通用性,建立以移动机器人完成任务总成本最小为目标,考虑移动机器人重载与空载成本差异,同时对任务分配及货架储位再分配位置进行决策的数学模型,对比 3 种策略的实验结果。372112023,23(26)李腾,等:机器人履约系统任务分配与货架储位再指派联合优化投稿网址:2.2 模型假设为便于模型的建立,做如下假设。(1)第一次拣选任务下发之前移动机器人均处于空闲状态,并且随机分布在系统中。(2)任务下发后,所有移动机器人均在运行状态,不考虑移动机器人空闲成本。(3)移动机器人在执行搬运任务过程中电量始终保持充足。(4)存储区货架储位数多于货架数,即存在空余储位。(5)仓库中的货架规格相同。(6)拣选台有足够的移动机器人等待空间。(7)移动机器人的速度是恒定的,忽略移动机器人加速/减速。(8)不考虑移动机器人起升货架成本与转弯成本。(9)拣选台服务遵循先到先服务原则。(10)货架商品数量满足订单拣选需求,不考虑缺货情况。(11)忽略移动机器人因避障等问题出现的距离增加情况。2.3 数学模型建立栅格化地图后,距离计算适用于使用曼哈顿距离为dRiZj=xRi-xZj+yRi-yZj(1)式(1)中:dRiZj为 Ri移动机器人从初始位置到 Zj任务货架存储点的距离;(xRi,yRi)为系统中 Ri移动机器人的起始位置坐标;(xZj,yZj)为系统中 Zj任务的位置坐标;R 为移动机器人集;n 为拣选系统移动机器人数量;Ri为拣选系统中第 i 个移动机器人,i=1,2,n;Z 为任务集;m 为拣选系统中任务的数量;Zj任务中的第 j 个任务,j=1,2,m。dZjPk=xZj-xPk+yZj-yPk(2)式(2)中:dZjPk为从 Zj任务货架存储点到 Pk拣选台的距离;(xPk,yPk)为系统中 Pk拣选工作台的位置坐标;P 为拣选台集;p 为拣选台的数量;Pk为拣选系统中的第 k 个拣选台,k=1,2,p。dPkSl=xPk-xZjSl+yPk-yZjSl(3)式(3)中:dPkSl为从拣选台 Pk到货架指派位置 Sl的距离(任务 Zj所在的位置变化为指派的 Sl位置);(xZjSl,yZjSl)为移动机器人搬运的任务 Zj的货架搬回货位 Sl位置坐标;Sl为存储区第 l 个货架储位,l=1,2,s;S 为货架储位集合;s 为货架储位总数。考虑机器人重空载差异的任务分配与货架储位再指派联合优化问题,机器人完成任务成本由两部分组成:移动机器人空载成本和重载成本,因此,目标函数为C=minpk=1mj=1ni=1sl=1dRiZjc1+(dZjPk+dPkSl)c2xijl(4)ni=1xijl=1,j=1,2,m,l=1,2,s(5)ni=1mj=1sl=1xijl s(6)mj=1xijl=1,i=1,2,n,l=1,2,s(7)sl=1xijl=1,i=1,2,n,j=1,2,m(8)xijl=0 或 1,i=1,2,n,j=1,2,m,l=1,2,s(9)式中:C 为移动机器人完成任务的总成本;c1为移动机器人行驶单位距离空载成本;c2为移动机器人行驶单位距离重载成本;xijl为决策变量,表示是否由移动机器人 i 完成任务 j 并搬运任务货架返回第 l个货架储位。式(4)表示移动机器人完成所有任务花费的总成本最小;式(5)表示每个任务只能由一个移动机器人执行;式(6)表示仓库内货架储位数量大于可移动货架数量;式(7)表示每个移动机器人一次只能执行一个任务;式(8)表示每个货架只能被指派到一个储位上;式(9)为决策变量取值约束。通过求解上述规划模型,不仅可以得到移动机器人任务分配结果,而且可以得到移动机器人返回储位区的货架再指派位置。3 算法设计任务分配与货架储位再指派联合优化问题是一个非确定性多项式完全问题(non-deterministicpolynomial complete problem,NPC),并且涉及的数据量较大,很难在短时间内通过直接求解方式得到问题的最优解,本文研究根据此联合优化问题的特点,借助遗传算法效率高、通用性和稳定性好等优点,设计求解算法。算法的具体求解过程如下。步骤 1采用实数编码产生染色体如图 2 所示,其中染色体上的基因位表示任务编号,长度为任务总数;基因表示移动机器人编号。同时设定初始种群数量、交叉概率、变异概率和最大迭代次数,确定47211科 学 技 术 与 工 程Science Technology and Engineering2023,23(26)投稿网址:图 2 染色体编码Fig.2 Chormosome coding使用移动机器人数量、完成任务数量。步骤 2 移动机器人完成任务总成本及货架再指派位置计算。分别计算移动机器人行驶空载、重载距离、货架再指派位置。重载距离中移动机器人搬运任务货架到拣选台的距离,利用任务坐标与拣选台坐标可计算两者之间的曼哈顿距离,而另一段重载距离即搬运货架返回存储区距离、空载距离和货架再指派位置主要由不同货架储位再指派策略决定。情况 1 策略 1 货架完成拣选后由移动机器人将货架搬运至原位置。从拣选台返回存储区距离和空载距离由上一任务位置坐标、本次执行任务坐标以及拣选台位置坐标计算得出。策略 1 中货架再指派位置为原位置。情况 2 策略 2 货架完成任务后将返回至计算所有可选空储位距离拣选台最近的空储位;策略 3返回至计算所有可选空储位中移动机器人搬运货架返回选中空储位与从该空储位前往移动机器人任务列表中下一任务位置距离和最小的空储位。在执行任务和对应拣选台由管理信息系统指定的情况下,移动机器人搬运货架回储存区距离和空载距离的大小均主要取决于选择放回的货架最优储位。两段距离均由上一任务选中空位坐标、拣选台位置坐标、本次执行任务坐标、本次执行任务选中空位坐标计算得出。在情况 2 中,货架最优储位的选择是尤为重要的,移动机器人可选择的货架空储位范围需受移动机器人从拣选台搬运货架返回储存区顺序影响。因此移动机器人从拣选台返回存储区的顺序即移动机器人在拣选台等待拣选的队列顺序对移动机器人返回储存区行驶距离有重要作用。移动机器人返回顺序计算规则设计如下。忽略拣选人员拣选时间且使用移动机器人到达拣选台行驶总距离升序作为移动机器人从拣选台搬运货架回储存区的顺序,所以可能出现距离相等、排序相同的情况。此时若所有移动机器人为第一次到达拣选台(移动机器人到达拣选台的距离设置为移动机器人从初始位置到任务位置再到拣选台距离的总和),同样距离的移动机器人可以随机选择进入拣选台队列顺序,但当移动机器人第二次到达时(移动机器人到达拣选台的距离设置为移动机器人上一次离开拣选台到再次到达拣选台之间的距离),若移动机器人到达拣选台距离相同,移动机器人进入队列的顺序应受第一次从拣选台返回顺序的影响,此时同样距离下,应该先执行上一任务放回队列中顺序在前的移动机器人。因此为保证货架空储位选择的有序进行,设置参数 a,a1,2,n,将移动机器人计算第二次达到拣选台顺序的未排序前行驶距离依次加上参数 a,如图 3 所示。(当移动机器人位于第一次到达拣选台返回队列首位,第一个计算再次到达拣选台距离时,a=1;返回队列中第二位移动机器人,a=2,依次类推),此时计算的移动机器人行驶距离将仅作为货架放回存储区顺序使用;当计算移动机器人行驶总成本时使用未加和参数 a 的值进行计算。移动机器人按照上述计算所得顺序有序进行空位选择。空储位选择规则如下:假设存在 n 台移动机器人共同执行任务,任务执行最初,空位集合应为 n台移动机器人执行任务空位加上开放储位。根据上文得到的任务执行过程中货架在拣选台的队列,当位于拣选台队列首位移动机器人从拣选台返回储位区时,根据策略 2、策略 3 的货架返回空储位的要求对空位进行选择并存入选中空储位集合。已知拣选台位置、空位位置、移动机器人任务列表,能计算出拣选台队列中移动机器人搬运货架存放的新空储位。当移动机器人得到货架储位再指派策略下任务货架应存放位置后,将在空位集合中扣除计算所得位置。新任务被搬运时,将添加新任务位置至空位集合。因此不难发现两种货架储位再指派策略下的任务货架新储位集合顺序与移动机器人的拣选台队列顺序相对应。具体任务货架新储位、染色体、拣选台队列间的对应关系如图 4 所示。染色体的适应度值为移动机器人完成所有任务行驶总成本的倒数,即图 3 拣选台排序计算规则示意图Fig.3 Schematic diagram of sorting calculationrules of picking stations572112023,23(26)李腾,等:机器人履约系统任务分配与货架储位再指派联合优化投稿网址:图 4 货架返回位置与染色体关系示意图Fig.4 Schematic diagram of the relationship between the return position of the pod and chromosomef(x)=1minpk=1mj=1ni=1sl=1(dRiZjc1+(dZjPk+dPkSl)c2)xijl(10)步骤 3 遗传操作。采用精英保留策略选择一定数量适应度值高的优良个体作为父代。为保证种群的多样性,按照交叉概率进行交叉操作,选择两个父代个体,使两条染色体上随机一段基因进行交叉从而生成新的个体。按照变异概率对选择个体进行变异操作;随机选择染色体上任意一位替换为所采用移动机器人任意序号。生成新种群,为了保证仓库中移动机器人均参与任务执行,将对选择、交叉、变异后产生的群体进行筛选,将其中因变异产生的移动机器人缺失的极少数情况去除。设置最大迭代次数,若程序执行已达到最大迭代数则停止迭代,输出最终结果,形成染色体与任务返回位置对应关系。若未达到迭代次数则返回步骤2 继续执行。4 算例分析4.1 算例描述为了验证本文模型的有效性,设典型仓库拣选区域面积为 50 m 50 m,将区域地图进行栅格化处理并建立直角坐标系,取单位距离为 1 m,标记左下角第一个位置坐标设置为(0,0),其中第一个数值为其所在列,第二个数值为其所在行。拣选台坐标设定为(24,5)。栅格化拣选区域布局如图 1 所示。通过调研方式得到6 组目前应用较广泛的移动机器人数据如表 1 所示。参考表 2 中行业数据,选取典型移动机器人参数:固定成本98 000 元,功率 1 000 w,移动机器人充电时间3 h,空载续航12 h,重载续航8 h,空载使用年限12 a,重载使用年限 10 a。电费为每千瓦时 0.86元计算,由移动机器人充电时间、功率、重空载续航时间、可知系统中每台移动机器人每秒空载耗电为0.000 06 元,每秒重载耗电为0.000 09 元。从移动机器人固定成本与重空载使用年限可知系统中每台移动机器人空载年折损为8 167 元,重载年折损为9 800元,每秒空载折损为 0.000 26 元,每秒重载折损为0.000 31 元,移动机器人行驶速度为 1 m/s,由此可得,移动机器人空载单位总成本 c1为 0.000 32 元,重载单位总成本 c2为 0.000 40 元,如表 2 所示。表 1 移动机器人调查参数Table 1 Mobile robot survey parameters型号序号123纯重载续航/h688纯空载续航/h8129负载/kg600600300充电时长/h332 3价格/元98 00079 80053 000功率/w8001 200200重载使用年限/a8103 4空载使用年限/a12127平均使用年限/a10105型号序号456纯重载续航/h868纯空载续航/h10 12812负载/kg300600600充电时长/h21.52.5 4价格/元80 000100 00060 000功率/w重载使用年限/a8107 8空载使用年限/a121210平均使用年限/a10108表 2 实验参数设定Table 2 Setting of experimental parameters参数名称参数值拣选区面积/m22 500电费/(kW h)0.86货架数量/个600拣选台坐标(24,5)机器人功率/w1 000机器人充电时间/h3机器人固定成本/元98 000机器人行驶速度/(m s-1)1机器人空载年折损/元8 167机器人重载年折损/元9 800机器人重载续航时间/h8机器人空载续航时间/h12机器人重载使用年限/a10机器人空载使用年限/a12机器人重载单位年折损/(元 h-1)1.116机器人空载单位年折损/(元 h-1)0.936机器人重载单位耗电费用/(元 h-1)0.324机器人空载单位耗电费用/(元 h-1)0.216机器人重载单位距离总费用/(元 h-1)1.440机器人空载单位距离总费用/(元 h-1)1.15267211科 学 技 术 与 工 程Science Technology and Engineering2023,23(26)投稿网址: 根据历史订单采用二八原则抽取任务,即任务所需货架 80%为中高热度货架,20%为低热度货架。60 个任务坐标如表 3 所示。随机产生 10 台移动机 器 人 初 始 坐 标 1(10,13)、2(26,13)、3(39,27)、4(3,34)、5(2,28)、6(3,45)、7(23,41)、8(14,24)、9(6,20)、10(26,27)。设定仓库存在10 个额外空储位,空储位坐标为(31,23)、(39,29)、(22,31)、(11,34)、(19,41)、(15,13)、(39,15)、(43,22)、(11,21)、(31,34)。4.2 算例结果在 MATLAB R2017a 环境下实现本文提出的启发式算法的仿真程序,在 WIN1064Bit 操作系统下进行实验,设置初始种群个数600 个,交叉概率与变异概率分别为 0.9 和 0.8。设置最大迭代次数 800次。运行 10 次选取最优实验结果如图 5 所示。其实验结果迭代图如图 6(c)所示。表 3 任务坐标Table 3 Position of tasks编号12345678910坐标(6,14)(6,22)(26,15)(22,22)(34,17)(19,13)(14,16)(30,13)(30,30)(35,37)编号11121314151617181920坐标(15,41)(23,37)(22,30)(34,27)(10,30)(15,27)(42,41)(6,34)(6,27)(14,20)编号21222324252627282930坐标(34,24)(30,44)(15,35)(39,21)(43,30)(43,35)(26,21)(35,42)(18,22)(47,31)编号31323334353637383940坐标(47,23)(6,43)(19,36)(11,37)(6,36)(22,28)(18,28)(27,38)(18,38)(18,21)编号41424344454647484950坐标(2,38)(47,45)(27,28)(35,30)(31,20)(23,15)(35,20)(11,24)(14,28)(27,24)编号51525354555657585960坐标(38,30)(3,30)(42,24)(42,17)(11,17)(19,31)(30,36)(38,22)(7,30)(31,17)货架内的编号表示任务编号;红色编号表示任务执行后指派位置为原位置;黑色编号表示任务执行后新的指派位置图 5 任务分配与货架储位再指派联合优化策略实验结果Fig.5 Experimental results of joint optimization strategy of task allocation and pod storage repositioning772112023,23(26)李腾,等:机器人履约系统任务分配与货架储位再指派联合优化投稿网址:图 6 3 种策略下的移动机器人完成任务成本迭代图Fig.6 Iterative graph of mobile robot taskcompletion cost under three strategies基于实际数据进行 3 种策略下移动机器人完成任务成本对比实验。3 种策略下均进行 10 次运行,取其实验结果中最小值作为最终结果。实验结果迭代图和移动机器人调度结果如图 6 和图 7 所示。为进一步对比结果,以 4 号移动机器人为例描绘 3种策略下移动机器人行驶路径和货架储位再指派结果,如图 8 所示。从图 7 和图 8 中可以看出采用不同的货架再指派策略将会得到不同的任务分配结图 7 三种策略下移动机器人调度结果Fig.7 Scheduling results under three strategies果和货架返回位置。策略 3 下移动机器人完成任务成本为 1.679 3元,策略 2 下移动机器人完成任务成本为 1.794 4元,而策略 1 下移动机器人完成任务成本为 1.792 3元(图 6)。策略 3 优于另两种策略。为进一步验证本文所提联合优化策略的优越性,再次生成 10 批60 个任务,分别得到 3 种策略下移动机器人运行成本,对结果进行降序排序,得出如图 9 所示的运行成本对比图。从图 9 中看出,本文所提策略 3 总成本最低,结果最优。4.3 结果分析4.3.1 不同优化目标下的实验结果对比分析在移动机器人调度与货架储位再指派问题研究中,数学模型多为以移动机器人完成任务行驶距离最小为目标和以移动机器人完成任务成本最小为目标两种,其中以成本最小为目标计算多使用距离乘统一的单位行驶距离成本得到,但实际在移动机器人完成任务过程中,移动机器人有两种运行状态:空载和重载,其两者间能耗存在差距,移动机器人完成任务成本的计算应该考虑移动机器人能耗差距带来的单位成本变化。因此,本文构建考虑移动机器人重空载成本差距因素的以移动机器人完成任务成本最小为目标的数学模型,同时设计实验与以移动机器人完成任务行驶距离最小为目标下移动机器人完成任务成本情况进行对比,实验设计了考虑货架储位再指派策略和额外空储位因素的如下 5 种情况,情况 1:有额外空储位采用策略 3;情况 2:策略 1;情况 3:有额外空储位采用策略 2;情况4:无额外空储位采用策略 3;情况 5:无额外空储位采用策略 2。应用表3 任务数据进行10 次实验,选择实验结果中最小值。实验结果显示,5 种情况下,情况 5 移87211科 学 技 术 与 工 程Science Technology and Engineering2023,23(26)投稿网址:图 8 4 号移动机器人三种策略下执行任务行驶路线及货架再指派结果Fig.8 Task driving route and pod repositioning results of mobile robot No.4 under three strategies图 9 3 种策略移动机器人完成任务成本对比图Fig.9 Comparison of the cost of completing tasks formobile robots with three strategies动机器人完成任务成本最大,为 1.884 5 元。基于此其余 4 种情况成本降低百分比和成本值对比图,如图 10 所示。图 10 中两种优化目标下,存在额外空储位因素下以移动机器人完成任务总成本最低为目标成本优化效果最好。3 种策略移动机器人完成任务成本优化效果排序为策略 3 优于策略 1 优于策略 2。4.3.2 极端任务分析实际仓库运作过程中,拣选订单因销售策略、市场客户需求的多变性而具有不确定性,可能出现订单任务所在货架位置相对集中的情况。因此设计任务货架集中分布情况下,几种货架储位再指派策略对比实验。根据仓库实际运行情况,货架可能出现的集中情况归纳为两类:仓库布局适宜当前市场需求变化972112023,23(26)李腾,等:机器人履约系统任务分配与货架储位再指派联合优化投稿网址:时任务货架集中靠近拣选台一侧,和仓库布局与当前市场需求变化情况存在偏差,仓库即将根据季节、需求变动进行仓库重新布局时,任务货架集中远离拣选台一侧两类。在极端任务情况下,同时考虑不同移动机器人运行极端参数,根据实际调研的移动机器人运行参数,归纳为 3 种:重空载成本差距极大 L、重空载成本差距一般 M 和重空载成本差距极小 S,具体参数如表 4 所示。图 10 不同优化目标下成本值及基于情况5 成本下降百分比对比图Fig.10 Comparison chart of cost value and cost reductionpercentage based on case 5 under different optimization objectives表 4 移动机器人运行参数Table 4 Mobile robot operating parameters参数情况LMS机器人纯重载续航/h888机器人纯空载续航/h121212功率/w1 2001 000800充电时间/h333单价/元98 00098 00098 000重载使用年限/a810报废年限:10 a空载使用年限/a1212报废年限:10 a重载运行单位总成本/(元 h-1)1.785 61.441.375 2空载运行单位总成本/(元 h-1)1.1881.1521.288 8重空载成本差距/(元 h-1)0.597 60.2880.086 4 对移动机器人不同重空载单位成本、极端任务分布和应用的货架储位再指派策略组合设计实验,产生了 12 组对比情况,如图 11 所示。对图11 中12 组情况设置10 组任务进行实验,将结果降序排列后,结果如图 12 所示。由图 12 得到本文提出的联合优化策略,在 3 种重空载成本差距情况下,任务货架集中远离拣选台分布与任务货架集中靠近拣选台分布,优化效果均优于另两种策略。对比图 12 中另外两种策略,在 M、S 成本差距情况下,无关任务货架分布情况,返回原位置策略优于返回距离拣选台最近位置策略,移动机器人完成任务成本更低。但当成本差距情况为 L 时,任务货架集中远离拣选台分布时,返回距离拣选台最近策略与返回原位置策略移动机器人使用成本相差较小。图 11 极端任务实验分组图Fig.11 Group diagram of extreme task experiment08211科 学 技 术 与 工 程Science Technology and Engineering2023,23(26)投稿网址:图 12 极端任务实验成本对比图Fig.12 Cost comparison chart of extreme task experiment5 结论研究了 RMFS 下考虑移动机器人重空载成本差距的任务分配与货架储位再指派的联合优化问题,建立了以移动机器人完成任务总成本最小为目标的数学模型,设计了求解模型的启发式算法,并与传统的返回原位置和返回距离拣选台最近位置策略进行了实验对比,得到以下结论。(1)本文提出的任务分配与货架储位再指派联合优化策略移动机器人完成任务成本更低,效率更高。(2)货架储存区存在开放储位时,移动机器人完成任务成本更小。(3)无关任务分布和移动机器人重空载成本差距大小情况,联合优化策略均具有完成任务总成本最低特征。在大部分情况下,返回原位置策略移动机器人完成任务总成本均低于返回距离拣选台最