考虑双端口布局的紧致化仓储系统堆垛机路径优化

自动化仓储系统(Automated Storage/Retrieval Systems, AS/RS),又称自动化立体仓库,作为一种集存储、输送、拣选和管理等功能于一体的集成系统,在现代仓储中发挥着重要作用[1].然而随着电商快速发展和工厂向智能化转型,系统的工作效率及强度要求也在不断被推向新的高度,传统的仓储技术已经越来越难以应对日益增长的生产需求.加之城市化持续扩张导致土地供应不断下降,增加了土地和劳动力成本.所有这些因素都促使企业寻求更紧凑、更有效的仓储系统[2].紧致化仓储系统的出现有效解决了这些难题,该系统仍主要由一台传统的自动化堆垛机完成货物存/取任务,用以实现货物的水平和垂直运动,但在货架的深度方向,会有一台动力输送装置帮助实现货物的深度位移,有别于传统AS/RS只能实现单深位或双深位存储,也即紧致化仓储系统能够实现货物的多深位存储[3].本文研究一种考虑了双端口布局的紧致化立体仓库,相同空间条件下,该系统除了拥有更多的储位单元,更节省成本以外,还将拥有更高的柔性和吞吐量,因此得到了更为广泛的关注与应用.

目前,鉴于系统新颖性与复杂性,国内外众多学者针对紧致化仓储系统所开展的研究还主要集中在模型分析[2,4,5]和货架设计[6,7,8],调度优化相关的研究尚处于起步阶段.堆垛机作为系统出/入库作业最主要的搬运工具,对其进行路径优化以提高作业效率,同样具有较高的实用价值和研究意义.以下可以通过综述传统AS/RS堆垛机调度相关的文献资料来为紧致化仓储系统寻求研究视角.

现有文献中,针对传统AS/RS堆垛机的路径优化问题,国内外有大量学者进行了研究.Kim等[9]对系统出/入库作业任务进行分析,以堆垛机行程距离最短为目标,采用一种改进启发式算法进行求解.Hsu等[10]在货物存储规模和订单数量不同的情况下建立堆垛机行程距离最短优化模型,提出采用基于订单批次处理的遗传算法进行求解.田国会等[11]以堆垛机拣选所有货位所耗时间最小为目标,提出一种结合Hopfield网络模型的遗传算法,求解得到了堆垛机拣选作业的全局优化路径.杨玮等[12]针对单巷道固定货架堆垛机拣选路径优化问题,建立以存/取时间最短为目标的数学模型,提出采用结合模拟退火算法的混合粒子群算法进行求解,提高了优化效率.以上关于堆垛机路径优化问题的研究主要针对堆垛机的单一作业方式,堆垛机的行程距离和行程时间是最常考虑到的两个优化指标.Kung等[13]以多堆垛机共享分拣巷道为主要研究问题,建立了堆垛机行程距离最短的动态规划模型,并采用一种快速排序调度方法进行求解,提高了系统分拣效率.Gharehgozli等[14]研究AS/RS中的出/入库作业排序问题,采用多项式时间算法,实现堆垛机总行程时间最小.包珊珊等[15]建立了考虑半托盘出库情况的堆垛机复合作业拣选路径优化模型,以堆垛机拣选时间最小为目标,采用离散烟花算法求解,实现算法的全局搜索和局部搜索.杨小明等[16]通过构建能耗成本、作业时间以及出货惩罚值最小为目标的堆垛机复合拣选作业优化模型,提出采用改进NSGA-Ⅱ算法进行求解.以上研究主要针对堆垛机的复合作业方式,但由于系统对象并未涉及出/入库端口的布局和分配,所以并不需要考虑堆垛机在交替执行出/入库任务时的起始点变化问题.

本文与以上针对紧致化系统研究及堆垛机调度研究的区别在于:① 目前研究同类系统的文献聚焦于模型分析和货架设计,本文则首次提出了双端口紧致化系统的堆垛机路径优化问题.优化过程不仅考虑了出/入库任务的操作排序及端口选择问题,同时也兼顾考虑了输送装置作深度位移对出/入库任务产生的影响.② 针对批次任务订单中出库任务与入库任务数量往往不对等的情形,提出了堆垛机执行单一作业和复合作业并存的混合作业模式,使堆垛机的路径寻优过程更加符合系统实际,也更具有现实指导意义.

紧致化仓储系统作为传统AS/RS的一种扩展和创新,在动力输送装置的协助下实现了货物的多深位存储,因此与传统AS/RS又可概括为多深系统与单深系统的区别.但考虑到动力输送装置作深度位移只可能影响堆垛机的作业时间,不会影响行程距离,所以在研究该类系统堆垛机路径调度问题时,将堆垛机的行程时间作为调度指标进行描述要更为准确.因此本文从出/入库端口分配、出/入库作业排序和出/入库作业路径的集成角度,以双端口紧致化立体仓库为研究对象,再考虑堆垛机采用混合作业模式时的运行特性,建立了出/入库任务时间调度模型,然后提出一种遗传-集束搜索混合优化算法(Genetic Algorithm-Beam Search, GA-BS)进行求解.利用遗传算法(Genetic Algorithm, GA)得到的最优个体作为集束搜索(Beam Search, BS)的初始路径选择,再按照正常BS算法流程寻求堆垛机的最优出/入库作业路径.

图1为某双端口布局的紧致化仓储系统实例,该系统由货物出/入库子系统、堆垛机子系统和紧致货架子系统组成:① 货物出/入库子系统,由货物拣选台、出/入库输送装置及出/入库端口构成,实现出库或入库外围对接的功能;② 堆垛机子系统,由堆垛机和直行导轨构成,实现货物在货架上的存/取功能;③ 紧致货架子系统,由紧致化货架和货格内的动力输送装置(见图2)构成,主要实现货物存储以及货物在货架深度方向上的运动功能.

系统中,每相邻的两排货架产生1条巷道,巷道两端各设有1个出/入库端口.货架采用紧致化货格单元设计,每个货格单元内都包含一个动力输送装置,能够实现货物的多深位存储以及深度位移.相比传统AS/RS,双端口紧致化立体仓库具有以下优势:

(1) 作业效率高,双端口布局有效减少了堆垛机在巷道中的行走时间,提高了系统作业效率;

(2) 仓储密度大,紧致化货架以及动力输送装置的设计实现了多深位仓储,扩展了系统仓储密度;

(3) 投入成本低,紧致化货架在有效提升系统仓储密度的同时,也减少了堆垛机的投入数量以及可利用土地资源的使用成本.

堆垛机执行出/入库作业任务时通常有单一指令(Single Command, SC)和复合指令(Dual Command, DC)两种作业方式[17].一个作业周期内,堆垛机完成一次入库或一次出库的单一操作为SC作业;完成一次入库和一次出库的复合操作为DC作业,两种作业方式如图3所示.图中:x为货架的水平方向;y为货架的垂直方向;O为入库端口;R为出库端口;P为货位点;P1为入库货位点;P2为出库货位点.在批次出/入库任务订单中,出库任务和入库任务的数量往往不对等,尽管DC作业的效率更高,但堆垛机难免还是要执行部分SC作业.因此,为进一步提升作业效率,就要考虑如何规划出更加合理的DC/SC任务队列,使堆垛机完成出/入库任务的时间最小.本文即针对考虑双端口布局的紧致化立体仓库,提出了更加符合实际生产的DC/SC混合作业方式,并以此建立堆垛机的出/入库作业调度模型,进而对系统出/入库端口分配、出/入库作业序列和出/入库作业路径展开优化研究.

为方便构建模型,通过分析相关设备的实际运行方式,对系统各项运行参数作如下设定:

(1) 紧致化货架共有I*J个货格单元,其中I表示货架列数,J表示货架层数;每个货格单元可以存放k件货物(图4中k=5);货格单元的列宽为l,层高为h,深度为z.设第i列、j层货格单元内所有货位的坐标为(i,j),则左端口的坐标为(0,1),右端口的坐标为(I+1,1).

(2) 设堆垛机为单载运行,水平运行速度为vx,垂直运行速度为vy,两个方向均为恒速运行,忽略堆垛机的启动时间和制动时间.

(3) 设动力输送装置在深度方向上的运行速度为vz,亦为恒速.堆垛机执行任务先到达指定货格单元,输送装置再启动将货物运送至货格单元的前端,此时堆垛机会产生等待时间,但由于目标货物始终处于货格单元最前端或仅仅落后一个货位的位置,如图4所示,也即堆垛机的等待时间不会太长,将该时间统一假设为一定值.

由以上假设,可以得到堆垛机由某一货格单元位置P1(x1, y1)运行至位置P2(x2, y2)所需要的时间为

TP1P2=max{|x1−x2|lvx,|y1−y2|hvy}ΤΡ1Ρ2=max{|x1-x2|lvx,|y1-y2|hvy} (1)

堆垛机到达指定货格单元后的等待时间(定值)为

TW=zkvzΤW=zkvz (2)

考虑双端口紧致化仓储系统的实际作业流程,所建立的堆垛机调度模型需要优化两个目标:① 对出/入库任务的操作序列进行合理排序;② 对堆垛机作业的出/入库端口进行合理选择.调度模型建立过程中,虽然堆垛机需访问的货物或货位在仓库两端各有一个端口可供选择,但从实际情况来看,不管是SC作业还是DC作业,其所对应的出/入库端口是由堆垛机执行该任务时所耗较少行程时间来决定的.

将堆垛机看作服务节点,系统完成批次订单任务的总作业时间可定义为堆垛机完成所有SC任务与所有DC任务时间之和.假设订单内有m个入库任务,n个出库任务,且m≠n.取

Z1=max{m, n} (3)

Z2=min{m, n} (4)

则该订单有Z2个DC任务和Z1-Z2个SC任务组成.堆垛机完成订单所有出/入库任务的总作业时间为

T=∑i=1Z1−Z2TSC,i+∑j=1Z2TDC,jΤ=∑i=1Ζ1-Ζ2ΤSC,i+∑j=1Ζ2ΤDC,j (5)

式中:TSC,i表示堆垛机执行第i个SC任务所用的时间;TDC,j表示执行第j个DC任务所用的时间.

堆垛机执行第i个SC任务所用的时间可表示为

式中:TIOa,Pi表示执行第i个SC任务时,堆垛机由IOa端口运行至Pi货格单元的时间;TPi,IOb表示执行第i个SC任务时,堆垛机由Pi货格单元运行至距离较近的IOb端口的时间;IOa、IOb代表左端口或右端口.

由此,堆垛机执行所有SC任务的总作业时间为

TSC=∑i=1Z1−Z2(TIOa,Pi+TPi,IOb)+(Z1−Z2)TW         (7)ΤSC=∑i=1Ζ1-Ζ2(ΤΙΟa,Ρi+ΤΡi,ΙΟb)+(Ζ1-Ζ2)ΤW         (7)

同理,堆垛机执行第j个DC任务所用的时间可表示为

TDC,j=TIOa,Pj+TPj, Pj+1+TPj+1,IOb+2TW (8)

式中:TIOa,Pj表示执行第j个DC任务时,堆垛机由其中一个端口载货运行至Pj货格单元的时间;TPj, Pj+1表示堆垛机从入库货格单元Pj运行至出库货格单元Pj+1的时间;TPj+1,IOb表示堆垛机从出库货格单元Pj+1运行至距离较近的端口的时间.

由此,堆垛机执行所有DC任务的总作业时间为

TDC=∑j=1Z2(TIOa,Pj+TPj,Pj+1+TPj+1,IOb)+   2Z2TW         (9)ΤDC=∑j=1Ζ2(ΤΙΟa,Ρj+ΤΡj,Ρj+1+ΤΡj+1,ΙΟb)+   2Ζ2ΤW         (9)

综上可得,堆垛机完成订单内所有出/入库任务的总作业时间为

T=TSC+TDC=∑i=1Z1−Z2(TIOa,Pi+TPi,IOb)+   ∑j=1Z2(TIOa,Pj+TPj,Pj+1+TPj+1,IOb)+   (Z1+Z2)TW         (10)Τ=ΤSC+ΤDC=∑i=1Ζ1-Ζ2(ΤΙΟa,Ρi+ΤΡi,ΙΟb)+   ∑j=1Ζ2(ΤΙΟa,Ρj+ΤΡj,Ρj+1+ΤΡj+1,ΙΟb)+   (Ζ1+Ζ2)ΤW         (10)

则系统完成该批次所有订单任务时,堆垛机出/入库作业最优路径模型为

g(T)=min T (11)

在研究双端口紧致化仓储系统堆垛机的路径优化问题时,计算的复杂性随着堆垛机同时存在SC和DC两种作业方式以及需访问的出/入库任务货位数的增多而增加,常规方法很难在这样的搜索空间寻找到最优解,而针对传统堆垛机系统所提出的一些智能算法又难以保证求解精度及优化效果.因此,在建立的出/入库作业调度模型的基础上,采用一种遗传-集束搜索混合优化算法进行求解,并结合系统过程仿真寻找堆垛机的最优路径方案.

集束搜索作为一种启发式图搜索算法,其基本思想与分支定界法类似,区别则是集束搜索并不是对所有节点进行分支[18].为减少搜索所占用的空间与时间,算法在进行每一层深度扩展的时候,会尝试剪掉一些质量较差的节点.如图5所示,首先设定集束宽度γ=2,即从根节点开始,往下层扩展出去的3个节点会按某种规则进行评估,从中选出质量较优的2个节点作为束节点(染色节点),然后将这2个束节点作为搜索起始点,继续进行分支,选出最优的束节点后再进行分支,以此类推,直到获得满足条件的叶子节点.搜索结束后将得到γ个可行路径,对比后选择最优的路径进行输出.

集束搜索算法为寻找堆垛机最优作业路径提供了一种思路,即在一定程度上,能够剪掉一部分输出质量较差的路径,寻优效率较高.但这并不是说算法的寻优过程是与系统完全适配的.

集束搜索在对堆垛机的作业路径进行选择时缺乏一定的约束性,即对每层节点进行评估时,只能发现前γ个满足条件的节点,即使该层还存在其他合适的节点也将不再被保留,搜索稳定性差,容易产生局部最优解.而遗传算法的收敛性较好,同时又具备良好的全局寻优能力,将其引入集束搜索以求解堆垛机的最优出/入库作业路径,能有效减小搜索范围,提高求解精度.

遗传算法部分的主要实现步骤如下.

(1) 编码设计.采用整数编码结构.具体设计过程:① 每批订单出/入库任务的优化由一条染色体代替;② 染色体上的基因数与出/入库任务的总数量相对应,每个基因允许由多个数字组成;③ 染色体上的每一个基因代表着每一个出/入库任务,该基因所在染色体的位置则对应出/入库任务在该处的编码.采用3个整数x,y,x′分别表示货架的列、层和出/入库端口,其中x′∈{1, 2}.现将某批订单的入库任务进行编号,组成一段编码;将出库任务在入库任务编号的基础上进行编号,组成另一段编码;同时将每个出/入库任务所对应的端口写入两段编码,分别用1、2表示对左右两个端口的选择.假设目前有2个入库任务和2个出库任务需要执行,(1, 1, 1)表示将编号为1的入库任务从左端口搬运到坐标为(1, 1)的货格单元中;(6, 2, 2)表示将编号为3的出库任务由(6, 2)货格单元处搬运到右端口,如表1所示.(1, 1, 1)(6, 2, 2)(3, 2, 2)(4, 2, 1)表示一条染色体上的基因,把该基因组合放在一起表示一条完整染色体,即批次出/入库任务的最优解,最优解序列如表2所示.

(2)确定适应度函数.由于本文的目标函数为求堆垛机作业时间T最小,优化效果越好的个体,其目标函数值越小,所以需要在目标函数和适应度函数之间加以改进,使得优化效果越好的个体其适应度函数也越大.适应度函数设定为

f(T)=Cmax-g(T) (12)

式中:Cmax为函数值相对较大的数,以保证f(T)为一正值.

(3) 选择算子.采用轮盘赌选择法选挑选个体,假设种群的规模为mpop,个体的适应度值为f(k),则每个个体被选择的概率p为

p=f(k)∑k=1mpopf(k)p=f(k)∑k=1mpopf(k) (13)

(4) 交叉算子.在本文的研究中,染色体上的每个基因代表着每个出/入库任务及其所对应的端口选择,因此在新生成的染色体中,原有的基因不能消失,也不允许重复,故采用如下交叉策略.

第1步,随机选择一对染色体(父代)中几个基因的起止位置(被选位置相同),具体操作如图6所示.

第2步,交换以上两组基因的位置,如图7所示.

第3步,根据映射关系将存在冲突的基因进行转换,映射关系如图8所示.

经过映射,生成如图9所示的新的子代染色体.

此外,还对交叉算子进行了自适应改进,使适应度值较小的个体能够拥有更大的交叉率得以实现个体改善,同时适当减小适应度值较大的个体的交叉率.具体表达式为

pc=⎧⎩⎨⎪⎪⎪⎪pc,min+(pc,max−pc,min)×  fmax−fcfmax−favg,pc,max,f>favgf≤favg         (14)pc={pc,min+(pc,max-pc,min)×  fmax-fcfmax-favg,f>favgpc,max,f≤favg         (14)

式中:pc,max和pc,min分别表示交叉率的最大值和最小值;fmax、fc和favg分别代表当代种群中的个体适应度最大值、被选中两个个体中的较大适应度值和种群适应度平均值.

(5) 变异算子.采用换位变异的方法,以某一较小变异率pm完成操作.

对于被选中进行变异操作的染色体,其上第i位基因存在pi∈[0,1],将适应度值最大的两个同任务类型基因进行互换,例如存在如图10所示的染色体X.

定义基因1～5位的变异率分别为:p1=0.01,p2=0.05,p3=0.02,p4=0.04,p5=0.03,则将第2、4位基因进行互换,变异后产生新染色体Y,如图11所示.

此外,为增强局部搜索能力,在对指定的数位基因进行变异操作时,引入密集因子λ评估当代个体之间的离散程度.在当前的平均适应度值和最大适应度值趋于集中时,将原有的变异率增大ε倍,有如下表达式:

式中:pm是变异率设定值;fmax和favg分别表示当代种群中的个体适应度最大值和种群适应度平均值.

综上,经过选择、交叉和变异等操作,遗传算法可以输出较为理想的个体,从而为集束搜索提供初始路径选择,然后再按照集束搜索流程正常训练即可实现系统出/入库作业运行效率的优化,并求得堆垛机的最优作业路径.采用遗传算法优化集束搜索的整体流程,如图12所示.

选取某企业实际使用的立体仓库为例进行仿真验证.该立体仓库采用上述双端口紧致化布局设计,订单拣选模式为固定货架批次拣选.每排货架有12层60列,共有12×60×2=1 440 个货格单元,货格单元的动力输送装置上设有5个货位,每条巷道共可完成 1 440×5=7 200 个货物的存储.左右两个出/入库端口的坐标分别标记为(0, 1)和(61, 1).系统各项运行参数如表3所示.

为验证已建立模型的有效性,选取系统10批次任务订单进行仿真实验,每批订单包含50个出/入库作业任务,其中一个批次的出/入库任务序列信息和对应货格坐标在表4中列出.货格属性值:0为入库作业命令,1为出库作业命令.表5为仿真实验与模型计算的对比结果.

由表中实验数据可知,对系统50个出/入库任务进行仿真实验的平均作业时间为959.33 s,模型的计算结果为949.49 s,平均误差为6.43%.可以认为建立的堆垛机出/入库作业过程模型是有效的.

针对表4所列出/入库任务订单,采用GA-BS混合算法对其进行优化求解,同时以GA和BS算法为基准,验证该混合优化算法的优越性.设定混合算法中GA种群规模为 1 000,交叉概率pc=0.95,变异概率pm=0.05,设定BS束宽γ=10,评估函数为g(T),最大迭代次数为500.运用所建立的堆垛机作业调度模型进行优化仿真,堆垛机出/入库任务执行时间的优化曲线如图13所示.图中:η为算法迭代次数.

由图可知,与GA和BS算法相比,GA-BS混合算法在求解双端口紧致化立体仓库出/入库任务调度问题的质量方面表现更优,能够使堆垛机更加快速高效地完成任务,且收敛速度较之BS算法也有很大提升.GA-BS混合算法在迭代至244代时达到最优,此时堆垛机执行所有出/入库任务的总时间为938.88 s,而如果不对订单序列进行优化,堆垛机执行所有出/入库任务的总时间为 1 569 s,优化后的执行效率提高了40.16%.

图14为优化后堆垛机执行所有出/入库任务所用时间最短的调度路径,该路径所对应的出/入库任务序列以及出/入库端口选择即为最优调度方案,如表6所示.

由上述最优出/入库作业调度路径,可以得出堆垛机执行批次订单任务的运行序列:1*→21→37→2*→11→36→2*→26→41→1*→29→44→1*→15→40→2*→18→49→1*→8→42→2*→27→35→1*→5→48→1*→25→43→2*→16→46→2*→3→50→1*→14→33→1*→32→34→2*→4→38→2*→24→39→1*→19→47→1*→22→45→2*→7→2*→10→2*→28→2*→30→2*→9→2*→31→2*→13→2*→20→1*→2→1*→17→1*→23→1*→1→1*→12→1*→6→1*.

综上所述,本文所建立的出/入库作业调度模型适用于双端口布局的紧致化立体仓库,通过GA优化BS算法求解得到了堆垛机出/入库作业路径的最优解,并验证了该混合优化算法的有效性和优越性.

本文针对双端口布局的紧致化仓储系统堆垛机调度优化问题,聚焦于新系统的出/入库任务排序和出/入库端口选择展开研究.主要成果有:

(1) 建立了以堆垛机完成出/入库任务总作业时间最小为评价标准的数学模型,提出更加符合实际生产的DC/SC混合作业模式,并通过对系统工作流程与运行特性的充分分析,将货物对端口的选择以及货物的深度位移综合考虑在堆垛机的调度模型当中,使路径寻优过程更加合理.

(2) 采用GA-BS混合算法对模型进行求解,利用GA较好的全局寻优能力和搜索特性对BS进行优化,将GA得到的最优个体作为BS的初始路径选择,提高了求解精度.算例仿真表明,与GA和BS相比,GA-BS算法能够更加准确地求解该类型仓储系统的出/入库作业调度问题,得到更优的堆垛机作业路径方案.

本文所述研究实现了双端口布局下紧致化仓储系统堆垛机的路径优化,但考虑到系统更适用于生产任务较大与货架货位数量较多的仓储环境,因此当批次出/入库任务序列更多时如何设计更有效的求解方法将会是后续研究的重点.