基于最短取货时间的仓储机器人待命位策略研究

近年来,随着人工智能技术和机器人技术的飞速发展,智能机器人开始被研究并应用于仓储领域。2012年初亚马逊收购了一家创业公司的Kiva机器人系统,通过减少拣货人员在亚马逊巨大仓库中徒步行走浪费的时间,Kiva机器人显著提高了仓储系统整体的工作效率。此外包括Zappos、Walgreens、Gap在内的许多国际知名公司也采用了与Kiva系统类似的机器人仓储系统。这类新型仓储系统由成千上万的可移动式货架及一定数量的仓储机器人组成,工作人员只需在工作站等着,机器人即可把任何想要的货物所在的整个货架送到工作人员跟前[1] 。相较于国外,国内对这种新型仓储系统的应用起步较晚,新松机器人自动化股份有限公司是最早一批研究这类仓储机器人的企业之一。虽然还处在起步阶段,但这种新型仓储系统在国内具有广阔的应用前景。

待命位是指仓储机器人或堆垛机在空闲时在仓库中的停放位置,它是影响仓储系统响应时间的重要因素之一,国内外学者对仓储机器人待命位策略进行了系统的研究并取得了一系列成果。在国外的研究中,Bozer和White[2] 首次提出了在自动化立体仓库下的四种静态堆垛机待命位策略,并构建了单指令和双指令情况下自动化立体仓库系统(AS/RS)中堆垛机期望取货时间模型。Park[3] 构建了基于均匀分布货架、普通矩形的自动化立体仓库系统的待命位策略数学模型,并重点考虑了不同的堆垛机返回路径。Van den Berg[4] 将堆垛机待命位问题转换为设施选址问题,分别针对随机存储和分类存储策略构建了堆垛机到下一次操作指令位置的行走时间模型,为仓储系统运作和绩效评估提供了重要的意见。Jose[5] 等在单回路自动引导小车仓储系统中,建立了关于小车服务响应时间的模型,并且以最小化服务响应时间的最大值为目标函数,提出了相应的动态规划算法。Regattieri[6] 对随机存取的自动化立体仓库系统中堆垛机的期望服务时间和期望服务距离分别建立了相应的数学模型,并采用软件仿真方法对不同系统参数情况下堆垛机的待命位策略进行了分析比较。此外,也有少量学者针对非传统自动化立体仓库的待命位策略进行了研究,如:Vasili等[7] 研究了关于分离平台的自动化立体仓库(SP-AS/RS)的载货平台待命位问题,考虑垂直升降平台和水平移动平台的3种待命位策略,分别构建了行走时间模型,得出当系统形状因子为1时行走时间最短的结论。Hale、Pujari等[8,9] 研究了一种带旋转货架的自动化立体仓库系统(ASCS)的待命位问题,根据传送带的周长和高度分为两种情况讨论,得出了相应的闭合形式解并验证了模型的有效性。

在国内有关仓储系统拣货机器待命位问题的研究相对较少,主要是涉及到AGV物料搬运系统和立体仓库堆垛机待命位的定位研究,如:黄一钧[10] 将特定的物料准备区域作为AGV小车的待命区域,借助排队论模型,提出了AGV物料搬运系统中小车数量的配置与规划方法。宋伟刚等[11] 设定堆垛机的待命位置为入库台和成品出库台,开发了自动化立体仓库的出入库决策仿真系统。马永杰和蒋兆远[12] 综合考虑存储时间因素和存储位置的动态变化,采用了格拉斯曼空间映射和多质点重心法,提出一种立体仓库中堆垛机的理想待命位动态决策方法。

尽管国内外学者提出了多种方法用来解决仓储拣货机器的待命位问题,但绝大部分方案都是基于单元货物的自动化立体仓库的待命位研究,没有涉及到基于仓储机器人的新型仓储系统。在新型仓储系统中客户订单到达后,拣货机器人从待命位出发取货,最终回到待命位点,不同的待命位策略选择会导致不同的取货时间。本文将针对这种新型的仓储系统,将最短取货时间作为评价指标,对三种常见的机器人待命位策略进行比较研究。

本文研究了一种全自动化的新型仓储系统,系统中的仓储机器人取代了传统拣货员,专门设计的可移动式货架代替了传统固定货架。系统的一个完整取货周期如下:客户订单到达后,通过计算机终端控制技术找到可用的机器人,接收指令的机器人从待命位出发到达目标货架并移动到货架下面,把载有货品的货架举起,送到指定的出货口,由拣选员取下货品,随后机器人将货架返还回原来的位置,最后回到指定的待命位点。分别考虑两种常见的仓库布局情况,如图1和图2所示,每条垂直巷道的两边各有一列货架,第一种仓库布局设置了前后两条横向巷道,第二种仓库额外设置了一条中间横向巷道。

由于系统每一次完整的取货周期都是从机器人离开待命位开始,到最终回到待命位结束,所以不同的待命位策略与系统对订单的反应时间有着紧密联系。在现实中,仓储机器人常见的待命位策略包括:①返还货架后回到仓库下方中点处;②返还货架后回到仓库右下角位置;③返还货架后直接停留在作业结束位置。本文拟考虑上述两种仓库布局情况,针对这三种机器人待命位策略进行分析比较。

本文的模型基于以下假设:①机器人沿着巷道行走,根据数据终端的计算选择最快捷的路线,行走速度恒定,不考虑加减速的影响;②采用随机存储策略,即任一货架被选择作为拣选点的概率都相同;③一个货架上存储一种货物品类;④由于机器人托举和放下货架所用的时间相对固定,与待命位策略无关,所以在建模的时候可以忽略不计;⑤忽略机器人在出货口的等待时间和人工取货时间;⑥不考虑机器人行走途中的拥堵情况;⑦假设系统中存在足够多的机器人,不考虑订单等待时间。

符号说明如表1所示。

在如图1所示的传统布局的仓储系统中,考虑第一种待命位策略,机器人返还货架后回到仓库下方中点处,即待命位点为O1,假设系统的出货口也在O1处,机器人的取货周期时间包括从待命位O1到目标货架X,然后将货架从X运到出货口O1,随后从O1将货架返还至X位置,最后再从X位置回到待命位O1处。

用ET[O1,X]表示机器人从O1点到任一货架的期望行走时间,由于系统采用随机存储策略,则在这种策略下的系统期望行走时间为4ET[O1,X]。建立如图1所示的直角坐标系,将待命位O1的坐标表示为(Xd,0),其中 ,分别用ETh[O1,X]、ETz[O1,X]表示O1点到目标取货位置X的期望横向行走时间和纵向行走时时间,则:

用X(Xi,j,Yi,j)表示目标拣货点X的坐标,其中i表示处于第i列货架,j表示处于第j排货架,不妨设n为偶数,由对称性,只需考虑Xd≥Xi,j的情况(即i=1,2,3,…,n),O1点到目标拣货位置X的期望横向行走时间如下:

由于从O1点到每一行货架的纵向行走时间都是相同的,机器人到目标拣货位置X的期望纵向行走时间如下:

最后,将式(2)和式(3)带入式(1)中,则可计算出在第一种待命位策略下的机器人期望取货时间为

其中,

保持机器人的待命位点位于O1的策略不变,若在仓库中设置了一条中间的横向巷道,将仓库分为上下两个区域,每个区域有 排货架(为了便于对两种系统的比较,不妨设c为偶数),如图2所示。显然O1点到目标货架X的期望横向行走时间不会发生变化,即ETCh[O1,X]=ETh[O1,X]。O1点到目标货架X处的期望纵向行走时间如下:

在带中间巷道的仓储系统中,第一种待命位策略下的机器人期望取货时间为

其中,

在第二种策略下,即机器人的待命位点为图1中的O2处,假设系统的出货口也在O2处,机器人一次的取货周期时间为从待命位O2到目标货架X,然后将货架从X运到出货口O2,随后从O2将货架返还至X位置,最后再从X位置回到待命位点O2。用ET[O2,X]表示从待命位点出发到目标货架的期望行走时间,则机器人期望取货时间计算公式为

第二种待命位策略与第一种策略比较,从待命位点到货架的纵向期望行走时间是相同的,将公式(2)中的n用2n代替,即为从待命位O2到货架的横向期望行走时间,如下:

将式(10)和式(11)带入式(9)中,则可计算出在第二种待命位策略下的机器人期望取货时间为

当仓储系统中存在中间横向巷道时,保持机器人的待命位点位于O2的策略不变,O2点到目标货架X的期望横向行走时间不变,ETCh[O2,X]=ETh[O2,X]。纵向行走时间与第一种策略下、带中间横向巷道的仓储系统下的行走时间相同,ETCz[O2,X]=ETCz[O1,X],则在带中间横向巷道的系统中,第二种待命位策略下的机器人期望取货时间如下:

在第三种策略下,机器人的待命位点为返还货架后直接停留在作业结束位置,假设系统的出货口在图1中O1处,在随机存储的假设条件下,用ET[A,B]表示机器人随机地从系统中的A点到B点的期望行走时间,机器人经历一次完整的取货周期花费的期望行走时间计算公式为

其中,ET[O1,X]的结果在3.1中已经求出。首先计算ETh[A,B],用iA表示A点处于第iA列,并令

当iA=1,即机器人停留在处于第一列的货架A下等待命令时:

当iA=2时,即机器人停留在处于第二列的货架A下等待命令时:

令 ,根据系统布局不难发现如下规律:

当iA=1时,EThA[,B]=f1(n)+f2(1);

当iA=2时,EThA[,B]=f1(1)+f2(n);

当iA=3时,EThA[,B]=f1n(-1)+f2(2);

当iA=4时,EThA[,B]=f1(2)+f2n(-1);

以此类推,直到当iA=2n时,EThA[,B]=f1(n)+f2(1)。

综上,机器人从货架A到货架B的期望横向行走时间如下:

接下来计算ETz[A,B],用jA表示A点处于第j行货架,有必要分两种情况考虑。

①A、B两点位于同一条纵向巷道两旁的任意位置(概率为: );

当jA=1,即机器人停留在处于第一行的货架A下等待命令时:

令 ,则 ,可以发现如下规律:

当jA=2时,ETzA[,B]=g(2)+g (c-1);

当jA=3时,ETzA[,B]=g(3)+g (c-2);

以此类推,当jA=c时,ETz[A,B]=g(c)+g(1)。

则在A、B两点位于同一条纵向巷道两旁的任意位置的情况下,结果为

②A、B两点不在同一条纵向巷道两旁的任意位置(概率为: )。

由对称性,我们只需计算当A处在仓库下半边区域,即当jA=1,2,3,…,m时机器人随机地从系统中的A点到B点的期望纵向行走时间。通过与上述类似的计算过程,可以得到如下结果:

综合①和②两种情况的计算结果,机器人从货架A到货架B的期望纵向行走时间如下:

将式(5)、式(15)和式(18)代入式(14)中,即可得到在无中间巷道的仓储系统下采取第三种待命位策略机器人的期望取货时间,如下:

当仓储系统中存在中间横向巷道时,采用第三种待命位策略,机器人经历一次完整的取货周期花费的期望行走时间仍然可以表示为

其中,ETC[O1,X]的结果在3.1中已经求出,由于中间巷道的设置不改变机器人横向行走的时间,故ETCh[A,B]=ETh[A,B]。

下面分析纵向行走时间ETCz[A,B],由于在系统中中间巷道将仓库分为上下两个拣货区,需要分别考虑两种情况。第一种是A、B两点位于同一个拣货区域,这种情况出现的概率为0.5,与无中间巷道的情况类比,此时只需将公式(18)中ETz[A,B]表达式中的c用 取代,m用m′代替即可(为了方便对两种系统的比较,不妨设m为偶数),结果如下:

第二种情况是A、B两点位于不同的拣货区域,仍然用jA表示A点处于第j行货架,由于对称性,我们假设A点在下拣货区,B点在上拣货区,我们只需考虑jA=1,2,…,m的情况下的ETCz[A,B]。

当jA=1,即机器人停留在处于第一行的货架A下等待命令(这种情况出现的概率为 )时:

令 ,不难发现如下规律:

则在A、B两点位于不同的拣货区域时:

综合两种情况的计算结果,在设置中间巷道的仓储系统下机器人随机地从货架A到货架B的期望纵向行走时间如下:

最后,将式(8)、式(15)和式(23)带入式(20)中,即可得到在带中间巷道的系统中采取第三种待命位策略机器人的期望取货时间,如下:

为了验证模型的有效性,下面我们设定在具体的仓储系统中,即给定几组变量值,将模型计算的结果和计算机软件Matlab仿真结果对比。假定系统中机器人行走的速度为3米每秒,货架长和宽都为1.2米,横向巷道宽2米,纵向巷道宽1.8米,改变纵向巷道的数量n和每一列设置的货架个数c形成不同的模拟场景,在计算机仿真模拟中每种策略下取货操作进行10000次,取其均值作为机器人在相应策略下的期望取货时间,对每个场景模拟100次。选取其中五个场景下的模型结果和仿真结果的相对误差和标准差,形成下表2。从表中可以看出模型结果和仿真结果的相对误差几乎都小于1%,最大相对误差也小于2%,表明上文构建的取货时间模型有很好的有效性。

在无中间巷道的仓储系统下,从ET1和ET2的表达式中可以明显看到:ET1-ET2<0,表明第一种策略下机器人期望取货时间比第二种策略下的期望取货时间更短。同理,在带中间巷道的仓储系统下,第一种策略下机器人期望取货时间比第二种策略下的期望取货时间更短。

在无中间巷道的仓储系统下,针对第三种机器人待命位策略,同样假定系统中机器人行走的速度为3米每秒,货架长和宽都为1.2米,横向巷道宽2米,纵向巷道宽1.8米,分别固定参数c的值为20、参数n的值为10,得到ET1、ET2和ET3的函数图像,如图3和图4所示。结果表明在无中间巷道的仓储系统下,随着纵向巷道的数量或每一列设置的货架总个数的变化,第三种待命位策略下机器人期望取货时间总是比第一种和第二种策略下的期望取货时间短。

在带中间巷道的仓储系统下,ETC1、ETC2和ETC3的函数值随n或c的变化分别如图5、图6所示,同样也可看出出ETC3<ETC1<ETC2,即:随着纵向巷道的数量或每一列设置的货架总个数的改变,第三种机器人待命位策略都是最优的,第一种待命位策略次之,第二种待命位策略表现最差。

在两种仓储系统下,先对第一种和第二种机器人待命位策略进行比较,从ET1、ETC1、ET2、ETC2的表达式(4)、式(7)、式(12)和式(13)中可以明显看到:ET1<ETC1、ET2<ETC2,表明与带中间巷道的仓储系统相比较,第一种和第二种待命位策略在无中间巷道的仓储系统中更有优势,上一节表1中模型或仿真结果也可说明这个结论。

针对第三种待命位策略,同样假定系统中机器人行走的速度为3米每秒,货架长和宽都为1.2米,横向巷道宽2米,纵向巷道宽1.8米,首先固定参数c的值为20,得到ET3和ETC3关于变量n的函数图像,如图7所示。可以看到:在无中间巷道的仓储系统下,随着纵向巷道的数量改变,与无中间巷道的仓储系统相比较,第三种待命位策略在带中间巷道的仓储系统中更有优势。同理,固定参数n的值为10,得到ET3和ETC3关于变量c的函数图像,如图8所示。结果表明在无中间巷道的仓储系统中,当每一列设置的货架数量较少时,第三种待命位策略在带中间巷道的仓储系统中表现更差;随着每一列设置的货架数量的增加,第三种待命位策略在带中间巷道的仓储系统中更有优势。在实际应用中,当每一列设置的货架数量较少时,额外设置的中间巷道会带来不必要的行走时间,无法体现出第三种待命位策略的优势;当每一列设置的货架数变大时,带中间横向巷道的系统可以避免拣货时需要跨越几个纵向巷道的折返距离,从而节省了大量行走时间,第三种待命位策略在带中间横向巷道的仓储系统中的优势才会体现出来。

本文借助统计建模的方法研究了在一种新型的仓储系统中拣货机器人的待命位策略问题。分别考察了两种不同的仓储布局系统,将最短取货周期时间作为评价指标,对三种机器人待命位策略进行了比较。结果表明无论仓储系统中是否设置中间横向巷道,在仓库设计的其他参数不变的情况下,随着纵向巷道的数量或每一列设置的货架数量的改变,第三种机器人待命位策略都是最优的,第一种待命位策略次之,第二种待命位策略表现最差。同时,在两种布局中,第一种和第二种待命位策略在无中间横向巷道的仓储系统中更有优势,当每一列的货位数较多时,第三种待命位策略在带中间横向巷道的仓储系统中才具有明显优势。上述结论可以在新型仓储系统的设计和运作策略选择决策中提供科学的分析依据,有助于提高仓储系统的取货效率,改善系统的整体服务水平。