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

李腾, 张茹兰, 丁佩佩

(哈尔滨商业大学管理学院, 哈尔滨 150028)

移动机器人履约系统(robotic mobile fulfillment system,RMFS)是一种新型的“货到人”拣选系统,与传统的人工和自动化立体仓库系统AS/RS(automated storage and retrieval system)拣选相比,其在拣选效率、仓库空间利用率等方面都存在着明显的优势[1]。货架储位再指派问题是RMFS所特有的,其是指通过规划货架完成拣选任务后储存的位置,缩短移动机器人行驶距离,降低成本,提高仓库拣选效率的优化问题。Krenzler等[2]是较早研究此类问题的学者,其建立了考虑货架在拣选台队列位置和移动机器人数量,不考虑客户订单商品储位情况和补货问题的简化模型,采用了二进制、最近位置、固定位置、随机位置、迭代二进制遗传以及俄罗斯方块算法求解,得出在大型算例应用中俄罗斯方块算法更为有效。Yuan等[3]基于随机、类、周转率原则构建排队模型,得出基于两类或三类的储位分配策略可以实现大多数潜在益处且益处会随货架周转率的变化而变化。Weidinger等[4]进一步研究将货架储位再指派问题转化成特殊的区间调度问题,提出自适应货架储位再指派策略。Ji等[5]将货架储位再指派问题分成了一次对一个货架指派和一次对多个货架进行指派两类问题,建立了考虑货架未来搬运距离的优化模型。Rimélé等[6]提出了一种高效但计算成本较高的蒙特卡洛树法。

随着研究的深入,越来越多的学者在进行相关问题研究时将货架储位再指派作为考虑的因素。徐翔斌等[7]提出了一种考虑货架与储位匹配程度的货架再指派策略。Roy等[8]在多存储区域移动机器人分配策略问题的研究中,对随机货架储位再指派策略下的移动机器人多存储区域分配策略性能进行了研究。Li等[9]对高密度移动货架系统中任务分配、路径规划及冲突、阻塞解决问题进行了研究。

Merschformann 等[10]在研究任务分配、货架选择、货架储位再指派问题对系统运行指标影响时,指出任务分配策略对系统吞吐量指标影响最大。因此,货架储位再指派策略也常常在任务分配问题研究中被考虑。Zhang[11]、Yuan等[12]和孙君阳等[13]研究了货架返回原位置策略下的多移动机器人调度问题。Gharehgozli等[14]提出考虑订单优先级的任务分配问题并对存在多货架返回位置可选情况下的货架位置选择问题进行了讨论。Yoshitake 等[15]建立了考虑货架和移动机器人状态的实时调度方法,给出货架返回距离移动机器人最近储存位置的策略。Rimélé等[16]提出了一种实时决策形式化的随机数学建模框架,研究了在随机输入订单情况下,RMFS中包括订单排序、储位指派、货架储位再指派等大多数操作决策问题。Bao等[17]提出一种同时考虑任务分配和货架储位再指派的策略,即货架返回到指派位置与下一任务点距离之和最小位置的策略。

在已有相关文献中针对货架储位再指派问题的研究多为对货架储位再指派单一问题或如在任务分配、多机器人调度、储位规划中考虑货架储位再指派策略的研究,而针对货架储位再指派问题和RMFS其他规划问题的联合优化研究文献较少。移动机器人完成拣选任务过程中货架返回位置是影响移动机器人行驶距离和运行时间的重要因素,不同运行状态下能耗的差别也是影响移动机器人完成任务成本的重要因素。因此在已有研究文献基础上,现研究考虑下一任务位置的任务分配与货架储位再指派联合优化问题,将移动机器人运行成本作为主要目标,细化单位时间移动机器人重载与空载成本差异。探讨RMFS实现移动机器人完成任务成本更优,拣选效率更高的策略,丰富相关理论,并为企业提供参考。

1 RMFS描述

RMFS主要由拣选台、可移动货架、通道以及移动机器人组成,其布局如图1所示。在“货到人”拣选模式下,当仓库管理系统接收到订单后,按照订单波次,系统使用一定的调度规则对任务进行一次性分配。在进行任务分配前,移动机器人的状态是不明确的,任务可以分配给任意移动机器人完成。如果任务所分配的移动机器人处于忙碌状态,则需要等待该机器人完成任务后,再对分配任务进行搬运。移动机器人开始执行任务(如图1中空载标记位置)后,将按照任务序列对任务货架进行依次搬运。在移动机器人任务执行过程中,移动机器人首先会从初始位置移动到被分配任务所需要的货架位置(如图1中实线指向标号为1的货架),再将货架搬运至任务指定拣选台(如图1中实线指向拣选台5),由拣选人员根据任务订单商品信息对货架上的商品进行拣选、完成扫描和打包。当系统中指定拣选台被占用时,移动机器人会在指定的拣选台进行排队等待,直到被拣选完毕。移动机器人将货架搬回存储区,在存储区中选择某一位置放回货架(如图1中星形标记位置),遵循不同货架储位再指派策略,移动机器人会将货架放在不同空位上并在货架下等待执行下一任务的命令。

图1 RMFS布局图

2 RMFS任务分配与货架储位再指派联合优化的数学模型

2.1 联合优化问题描述

移动机器人运行时,根据移动机器人状态不同可以分为重载(如图1中重载标记)和空载(如图1中空载标记)两种状态。不难发现,移动机器人在完成拣选任务的过程中,重载与空载状态是交替进行的,其中移动机器人行驶的重载距离包括移动机器人搬运货架到拣选台和从拣选台返回到储存区的两段距离,空载距离为移动机器人接收到任务后,从所在地点前往所需搬运任务货架地点之间的距离。移动机器人重载状态需要托载沉重的货架,因此重载与空载行驶能耗不同,为进一步减小移动机器人完成任务总成本,应细化移动机器人重载和空载成本差距。

在空载运行中,移动机器人行驶距离由移动机器人初始位置和任务位置决定;在重载运行中,移动机器人行驶距离由任务位置、拣选台位置和返回存储区位置决定。其中任务位置和拣选台位置与订单相关由管理信息系统指定,相对固定。而移动机器人初始位置与返回存储区位置,由于在移动机器人即将完成当前任务列表时,新的任务列表会提前发放给移动机器人等待执行,即除第一轮任务执行开始外,移动机器人执行不同轮次任务中的初始位置等于该移动机器人上一任务货架返回位置,因此移动机器人初始位置和返回存储区位置主要由货架储位再指派策略决定。

实际中常用的货架储位再指派策略主要有两种,返回原位置策略和返回距离拣选台最近位置策略,其中返回原位置策略(如图1中蓝色虚线所示,下文统一策略1表示),其是指将拣选完成后的货架由移动机器人搬运至存储货架的原位置。返回距离拣选台最近策略(如图1中橙色虚线所示,下文统一用策略2表示),它是指将拣选完成的货架由移动机器人搬运至距离拣选台最近的空储位上。本文研究提出了一种考虑任务分配的货架储位再指派策略(如图1中红色虚线所示,下文统一用策略3表示),当货架完成拣选后,移动机器人根据其执行的任务列表,将货架放置在返回储存区指派位置与到达任务列表中下一任务位置联合距离最小的空储位上。

对3种策略下移动机器人搬运货架行驶距离进行算例讨论,如图1所示,对地图进行栅格化处理后,将每一单位小格设置为1 个单位距离。移动机器人从初始位置搬运任务1到达拣选台需要移动距离为21 个单位距离(如图1中黑色实线行走距离),使用策略1下移动机器人从拣选台到任务1返回位置再到达任务2需要移动33 个单位距离(如图1中蓝色虚线行走距离);使用策略2下移动机器人需要移动47 个单位距离(如图1中橙色虚线行走距离),而使用策略3,机器人移动31 个单位距离(如图1中红色虚线行走距离),相较于前两种策略,策略3有效地缩小了移动机器人的行驶距离,算例结果表明策略3对完成任务移动机器人行驶距离优化效果最好。为验证算例的通用性,建立以移动机器人完成任务总成本最小为目标,考虑移动机器人重载与空载成本差异,同时对任务分配及货架储位再分配位置进行决策的数学模型,对比3种策略的实验结果。

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为货架储位总数。

考虑机器人重空载差异的任务分配与货架储位再指派联合优化问题,机器人完成任务成本由两部分组成:移动机器人空载成本和重载成本,因此,目标函数为

(dZjPk+dPkSl)c2}xijl

(4)

(5)

(6)

(7)

(8)

(9)

式中:C为移动机器人完成任务的总成本;c1为移动机器人行驶单位距离空载成本;c2为移动机器人行驶单位距离重载成本;xijl为决策变量,表示是否由移动机器人i完成任务j并搬运任务货架返回第l个货架储位。

式(4)表示移动机器人完成所有任务花费的总成本最小;式(5)表示每个任务只能由一个移动机器人执行;式(6)表示仓库内货架储位数量大于可移动货架数量;式(7)表示每个移动机器人一次只能执行一个任务;式(8)表示每个货架只能被指派到一个储位上;式(9)为决策变量取值约束。

通过求解上述规划模型,不仅可以得到移动机器人任务分配结果,而且可以得到移动机器人返回储位区的货架再指派位置。

3 算法设计

任务分配与货架储位再指派联合优化问题是一个非确定性多项式完全问题(non-deterministic polynomial complete problem,NPC),并且涉及的数据量较大,很难在短时间内通过直接求解方式得到问题的最优解,本文研究根据此联合优化问题的特点,借助遗传算法效率高、通用性和稳定性好等优点,设计求解算法。算法的具体求解过程如下。

步骤1采用实数编码产生染色体如图2所示,其中染色体上的基因位表示任务编号,长度为任务总数;基因表示移动机器人编号。同时设定初始种群数量、交叉概率、变异概率和最大迭代次数,确定使用移动机器人数量、完成任务数量。

图2 染色体编码

步骤2移动机器人完成任务总成本及货架再指派位置计算。分别计算移动机器人行驶空载、重载距离、货架再指派位置。重载距离中移动机器人搬运任务货架到拣选台的距离,利用任务坐标与拣选台坐标可计算两者之间的曼哈顿距离,而另一段重载距离即搬运货架返回存储区距离、空载距离和货架再指派位置主要由不同货架储位再指派策略决定。

情况1策略1货架完成拣选后由移动机器人将货架搬运至原位置。从拣选台返回存储区距离和空载距离由上一任务位置坐标、本次执行任务坐标以及拣选台位置坐标计算得出。策略1中货架再指派位置为原位置。

情况2策略2货架完成任务后将返回至计算所有可选空储位距离拣选台最近的空储位;策略3返回至计算所有可选空储位中移动机器人搬运货架返回选中空储位与从该空储位前往移动机器人任务列表中下一任务位置距离和最小的空储位。在执行任务和对应拣选台由管理信息系统指定的情况下,移动机器人搬运货架回储存区距离和空载距离的大小均主要取决于选择放回的货架最优储位。两段距离均由上一任务选中空位坐标、拣选台位置坐标、本次执行任务坐标、本次执行任务选中空位坐标计算得出。

在情况2中,货架最优储位的选择是尤为重要的,移动机器人可选择的货架空储位范围需受移动机器人从拣选台搬运货架返回储存区顺序影响。因此移动机器人从拣选台返回存储区的顺序即移动机器人在拣选台等待拣选的队列顺序对移动机器人返回储存区行驶距离有重要作用。移动机器人返回顺序计算规则设计如下。

忽略拣选人员拣选时间且使用移动机器人到达拣选台行驶总距离升序作为移动机器人从拣选台搬运货架回储存区的顺序,所以可能出现距离相等、排序相同的情况。此时若所有移动机器人为第一次到达拣选台(移动机器人到达拣选台的距离设置为移动机器人从初始位置到任务位置再到拣选台距离的总和),同样距离的移动机器人可以随机选择进入拣选台队列顺序,但当移动机器人第二次到达时(移动机器人到达拣选台的距离设置为移动机器人上一次离开拣选台到再次到达拣选台之间的距离),若移动机器人到达拣选台距离相同,移动机器人进入队列的顺序应受第一次从拣选台返回顺序的影响,此时同样距离下,应该先执行上一任务放回队列中顺序在前的移动机器人。因此为保证货架空储位选择的有序进行,设置参数a,a∈[1,2,…,n],将移动机器人计算第二次达到拣选台顺序的未排序前行驶距离依次加上参数a,如图3所示。(当移动机器人位于第一次到达拣选台返回队列首位,第一个计算再次到达拣选台距离时,a=1;返回队列中第二位移动机器人,a=2,依次类推),此时计算的移动机器人行驶距离将仅作为货架放回存储区顺序使用;当计算移动机器人行驶总成本时使用未加和参数a的值进行计算。移动机器人按照上述计算所得顺序有序进行空位选择。

图3 拣选台排序计算规则示意图

空储位选择规则如下:假设存在n台移动机器人共同执行任务,任务执行最初,空位集合应为n台移动机器人执行任务空位加上开放储位。根据上文得到的任务执行过程中货架在拣选台的队列,当位于拣选台队列首位移动机器人从拣选台返回储位区时,根据策略2、策略3的货架返回空储位的要求对空位进行选择并存入选中空储位集合。已知拣选台位置、空位位置、移动机器人任务列表,能计算出拣选台队列中移动机器人搬运货架存放的新空储位。当移动机器人得到货架储位再指派策略下任务货架应存放位置后,将在空位集合中扣除计算所得位置。新任务被搬运时,将添加新任务位置至空位集合。因此不难发现两种货架储位再指派策略下的任务货架新储位集合顺序与移动机器人的拣选台队列顺序相对应。具体任务货架新储位、染色体、拣选台队列间的对应关系如图4所示。

图4 货架返回位置与染色体关系示意图

染色体的适应度值为移动机器人完成所有任务行驶总成本的倒数,即步骤3遗传操作。采用精英保留策略选择一定数量适应度值高的优良个体作为父代。为保证种群的多样性,按照交叉概率进行交叉操作,选择两个父代个体,使两条染色体上随机一段基因进行交叉从而生成新的个体。按照变异概率对选择个体进行变异操作;随机选择染色体上任意一位替换为所采用移动机器人任意序号。生成新种群,为了保证仓库中移动机器人均参与任务执行,将对选择、交叉、变异后产生的群体进行筛选,将其中因变异产生的移动机器人缺失的极少数情况去除。设置最大迭代次数,若程序执行已达到最大迭代数则停止迭代,输出最终结果,形成染色体与任务返回位置对应关系。若未达到迭代次数则返回步骤2继续执行。

(10)

4 算例分析

4.1 算例描述

为了验证本文模型的有效性,设典型仓库拣选区域面积为50 m×50 m,将区域地图进行栅格化处理并建立直角坐标系,取单位距离为1 m,标记左下角第一个位置坐标设置为(0,0),其中第一个数值为其所在列,第二个数值为其所在行。拣选台坐标设定为(24,5)。栅格化拣选区域布局如图1所示。

通过调研方式得到6 组目前应用较广泛的移动机器人数据如表1所示。

表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所示。

表2 实验参数设定

根据历史订单采用二八原则抽取任务,即任务所需货架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)}。

表3 任务坐标

4.2 算例结果

在MATLAB R2017a环境下实现本文提出的启发式算法的仿真程序,在WIN1064Bit操作系统下进行实验,设置初始种群个数600 个,交叉概率与变异概率分别为0.9和0.8。设置最大迭代次数800 次。运行10 次选取最优实验结果如图5所示。其实验结果迭代图如图6 (c)所示。

货架内的编号表示任务编号;红色编号表示任务执行后指派位置为原位置;黑色编号表示任务执行后新的指派位置

图6 3种策略下的移动机器人完成任务成本迭代图

基于实际数据进行3种策略下移动机器人完成任务成本对比实验。3种策略下均进行10 次运行,取其实验结果中最小值作为最终结果。实验结果迭代图和移动机器人调度结果如图6和图7所示。为进一步对比结果,以4 号移动机器人为例描绘3种策略下移动机器人行驶路径和货架储位再指派结果,如图8所示。从图7和图8中可以看出采用不同的货架再指派策略将会得到不同的任务分配结果和货架返回位置。

图7 三种策略下移动机器人调度结果

图8 4号移动机器人三种策略下执行任务行驶路线及货架再指派结果

策略3下移动机器人完成任务成本为1.679 3 元,策略2下移动机器人完成任务成本为1.794 4 元,而策略1下移动机器人完成任务成本为1.792 3 元(图6)。策略3优于另两种策略。为进一步验证本文所提联合优化策略的优越性,再次生成10 批60 个任务,分别得到3种策略下移动机器人运行成本,对结果进行降序排序,得出如图9所示的运行成本对比图。从图9中看出,本文所提策略3总成本最低,结果最优。

图9 3种策略移动机器人完成任务成本对比图

4.3 结果分析

4.3.1 不同优化目标下的实验结果对比分析

在移动机器人调度与货架储位再指派问题研究中,数学模型多为以移动机器人完成任务行驶距离最小为目标和以移动机器人完成任务成本最小为目标两种,其中以成本最小为目标计算多使用距离乘统一的单位行驶距离成本得到,但实际在移动机器人完成任务过程中,移动机器人有两种运行状态:空载和重载,其两者间能耗存在差距,移动机器人完成任务成本的计算应该考虑移动机器人能耗差距带来的单位成本变化。因此,本文构建考虑移动机器人重空载成本差距因素的以移动机器人完成任务成本最小为目标的数学模型,同时设计实验与以移动机器人完成任务行驶距离最小为目标下移动机器人完成任务成本情况进行对比,实验设计了考虑货架储位再指派策略和额外空储位因素的如下5种情况,情况1:有额外空储位采用策略3;情况2:策略1;情况3:有额外空储位采用策略2;情况4:无额外空储位采用策略3;情况5:无额外空储位采用策略2。

应用表3任务数据进行10 次实验,选择实验结果中最小值。实验结果显示,5种情况下,情况5移动机器人完成任务成本最大,为1.884 5 元。基于此其余4种情况成本降低百分比和成本值对比图,如图10所示。

图10 不同优化目标下成本值及基于情况5成本下降百分比对比图

图10中两种优化目标下,存在额外空储位因素下以移动机器人完成任务总成本最低为目标成本优化效果最好。3种策略移动机器人完成任务成本优化效果排序为策略3优于策略1优于策略2。

4.3.2 极端任务分析

实际仓库运作过程中,拣选订单因销售策略、市场客户需求的多变性而具有不确定性,可能出现订单任务所在货架位置相对集中的情况。因此设计任务货架集中分布情况下,几种货架储位再指派策略对比实验。

根据仓库实际运行情况,货架可能出现的集中情况归纳为两类:仓库布局适宜当前市场需求变化时任务货架集中靠近拣选台一侧,和仓库布局与当前市场需求变化情况存在偏差,仓库即将根据季节、需求变动进行仓库重新布局时,任务货架集中远离拣选台一侧两类。

在极端任务情况下,同时考虑不同移动机器人运行极端参数,根据实际调研的移动机器人运行参数,归纳为3 种:重空载成本差距极大L、重空载成本差距一般M和重空载成本差距极小S,具体参数如表4所示。

表4 移动机器人运行参数

对移动机器人不同重空载单位成本、极端任务分布和应用的货架储位再指派策略组合设计实验,产生了12 组对比情况,如图11所示。

图11 极端任务实验分组图

对图11中12 组情况设置10 组任务进行实验,将结果降序排列后,结果如图12所示。由图12得到本文提出的联合优化策略,在3种重空载成本差距情况下,任务货架集中远离拣选台分布与任务货架集中靠近拣选台分布,优化效果均优于另两种策略。对比图12中另外两种策略,在M、S成本差距情况下,无关任务货架分布情况,返回原位置策略优于返回距离拣选台最近位置策略,移动机器人完成任务成本更低。但当成本差距情况为L时,任务货架集中远离拣选台分布时,返回距离拣选台最近策略与返回原位置策略移动机器人使用成本相差较小。

图12 极端任务实验成本对比图

5 结论

研究了RMFS下考虑移动机器人重空载成本差距的任务分配与货架储位再指派的联合优化问题,建立了以移动机器人完成任务总成本最小为目标的数学模型,设计了求解模型的启发式算法,并与传统的返回原位置和返回距离拣选台最近位置策略进行了实验对比,得到以下结论。

(1)本文提出的任务分配与货架储位再指派联合优化策略移动机器人完成任务成本更低,效率更高。

(2)货架储存区存在开放储位时,移动机器人完成任务成本更小。

(3)无关任务分布和移动机器人重空载成本差距大小情况,联合优化策略均具有完成任务总成本最低特征。

在大部分情况下,返回原位置策略移动机器人完成任务总成本均低于返回距离拣选台最近策略。该结果对不同货架布局和移动机器人规格下的货架储位再指派策略选择具有一定的指导作用。

由于RMFS优化问题影响因素的复杂性,后续将考虑货架周转率变化对货架位置的影响,周转率高的货架存放在距离拣选台较远的位置将会造成移动机器人行驶距离增大,进而增加移动机器人运行总成本。结合实际,在联合优化问题中考虑货架周转率,进一步提高拣选效率。