面向低能耗的密集仓储货位分配优化

张牧仁，项 前，吕志军，尹英豪，俞卓韬

(东华大学 机械工程学院, 上海 201620)

四向车式密集仓储系统(简称“四向车仓储系统”)是一种新兴的自动化仓储系统,其以设备轻量灵活、空间利用率高等优点,得到了广泛应用[1]。在“节能减排、绿色发展”理念的倡导下,物流仓储系统的节能降耗问题已经引起了工业界和研究学者的共同关注。作为自动化仓储的重要环节,四向车仓储系统的货位分配,不仅受到库型布局、动态库存及作业环境等约束,还与路径优化、仓储作业调度等问题[2-5]复杂耦合,其合理性更会严重影响仓储作业能耗。

国内外关于仓储系统能耗模型的研究主要集中在两个方面。一方面,将能耗作为仓储系统的评价指标指导仓库布局优化配置。Ekren[6]以作业的能耗作为评估标准之一,提出了针对穿梭车的能耗模型;Liu等[7]进一步研究得出,在相同作业条件下,影响穿梭车仓储系统能耗大小的因素主要是提升机的速度和加速度;Leher等[8]提出了一种用于自动化立体仓库优化设计的能效模型。另一方面,将能耗作为优化目标应用于作业路径、任务分配、货位分配等问题中。Ene等[9]提出的一种能耗模型用来优化自动化立体仓库中的复合指令作业拣选;鲁建厦等[10]针对子母穿梭车密集仓储系统,在作业路径规划过程中考虑设备的能耗,并将能耗作为成本添加到路径优化模型中;方磊等[11]在动态储位分配策略下,以堆垛机总能耗最低为目标对堆垛机的复合作业进行任务调度;Li等[12]在KMFS(Kiva mobile fulfilment system)的货位分配问题中考虑设备能耗,并指出能耗的大小与作业距离有关,但该模型忽略了能耗对设备所载货物质量的敏感性;柏乐[13]提出以搬运设备的能耗最低为目标的自动化立体仓库货位优化模型,但没有考虑设备的作业能耗与运动特性的关系。如果能耗模型充分考虑仓储设备的作业距离、运动特性和载货质量等因素,其将更具有应用价值。

货位分配作为一种组合优化问题,目前研究的求解算法多为启发式算法,通常将多种算法混合使用或调整算法的重要步骤以改善算法性能。黄鹏等[14]针对大型重载的立体仓库,提出将遗传算法和延迟接受爬山算法相结合,加快了算法收敛速度;董海等[15]提出一种情绪化细菌觅食算法,求解自动化立体仓库的最优货位,该算法具有较好的收敛性;蔡安江等[16]改进了混合蛙跳算法,通过加入动态自适应同步因子解决了其容易陷入局部最优的问题,货位的分配结果也更合理。差分进化算法是一种较新的启发式算法,与遗传算法相比,在计算速度和稳健性等方面具有一定的性能优势[17],可用于解决实际仓储货位分配优化问题[18]。

综上所述可知,现有文献对仓储能耗模型的研究主要侧重于设备路径优化、仓储布局优化等,而关联仓储货位分配优化的研究较少。因此,面向绿色、节能、高效的四向车仓储系统,本文提出以节能降耗为主要目标的货位分配优化模型及算法。

1 问题描述

四向车仓储系统是一种新型密集自动化立体仓库。四向车作为仓储系统的主要搬运设备,在提升机的配合下,通过在单层纵横两个方向的轨道穿梭可到达立体货架的任一货位,执行入库和出库作业。

四向车仓储系统仓库布局如图1所示。四向车仓储系统主要由货架、输送机、提升机、缓存区、四向车等组成。货架具有可以存储货物的货位以及供四向车行走的轨道。输送机沿y轴方向运动将货物运至提升机处,提升机不仅可以沿z轴方向运动,也可以沿y轴方向取货和放货。四向车通过换向机构实现x轴和y轴方向的运动,在搬运货物时,四向车的顶升机构将货物顶起,到达目标货位后,顶升机构下降将货物放置在货位上。

为求解同批多笔出/入库作业的最优货位集合,满足动态作业环境约束的同时使作业能耗最低,对货位分配优化模型作如下假设:

1)单笔作业只有一个托盘出入库;

2)模型中将目标货位与出入库口之间的曼哈顿距离作为作业搬运距离;

3)四向车仓储系统所有货位大小规格相同,最大承载相同;

4)为避免与出入库口选择问题耦合,将仓库出入库口简化为一个;

5)对于换层作业,提升机的承载质量只考虑货物,不考虑四向车自身的质量。

2 货位分配优化模型

四向车仓储系统的货架可以看作一个三维立体高层货架,货架规模由货架的总行数X、总列数Y和总层数Z描述,l、w、h分别表示货位的长、宽、高,出入库口的坐标设置为(x0,y0,z0),针对单笔作业q的目标货位坐标为(xq,yq,zq)。J=(J1,J2,…,Jq,…,Jn)表示单批作业,Jq表示第q笔作业,n表示作业总数。货位分配优化模型以作业能耗少、货架重心低和作业分布均衡为优化目标分配货位。

2.1 减少作业能耗

四向车作业能耗主要由搬运能耗、托盘顶升能耗和转向能耗组成,提升机作业能耗主要由搬运能耗组成。搬运能耗与作业功率和时间有关,目标货位的远近会影响作业时间,载货质量会影响牵引力的大小,进而影响作业功率。

设备运行可分为启动加速、匀速行驶、到达减速3个阶段,由于设备行程有长短差别,实际作业过程中会出现两种运动过程:设备可达到最大运行速度vmax;设备未达到最大运行速度vmax。两种运动过程的设备运行速度-时间曲线图如图2所示。

基于图2所示的速度-时间曲线,可得四向车与提升机的作业能耗计算如表1所示。表1中每种设备要考虑两种运动过程,当两种运动过程的计算方法相同时共用同一个计算公式,且设备只有在达到最大运行速度时才会有匀速运动,故未达到最大运行速度的设备在匀速运动时无计算公式。

表1 设备搬运能耗计算方法Table 1 Calculation method of equipment handling energy consumption

以四向车为对象研究能耗计算方法。式(1)中Gq为四向车所载货物受到的重力,f为四向车和轨道之间的摩擦因数,g为重力加速度,as为四向车的加速度,Fas为四向车在加速过程中所受牵引力;式(3)中vsmax为四向车最大运行速度,η为运行效率,Pas为四向车加速运动的功率;式(5)和(6)是根据时间速度曲线和搬运距离得出的两种搬运时间计算方式,tas为加速运动的时间,式(5)中sas为加速运动位移;式(9)中Was为四向车加速运动的能耗;式(11)和(13)中,Fcs和Pcs分别为四向车匀速运动的牵引力和功率;式(15)中tcs为匀速运动的时间,ss为四向车搬运货物的总位移,sds为减速运动的位移;式(17)中Wcs为四向车匀速运动的能耗;式(19)中Fds为四向车减速运动所受牵引力;式(21)中Pds为四向车减速运动的功率;减速运动的搬运时间计算方式如式(23)和(24),tds为减速运动的搬运时间;式(27)中Wds为四向车减速运动的能耗。

提升机的运动过程与四向车基本一致。式(2)中ae为提升机的加速度;式(4)中vemax为提升机最大运行速度;式(7)中sae为提升机的加速位移;式(16)中se为提升机的总位移,sde为提升机减速运动的位移。

托盘顶升能耗发生在四向车取放货物时,四向车需要将承载货物的托盘从货位上顶起或放置在货位上,能耗计算方法如式(29)所示。

(29)

式中:Wqlift为执行作业q时托盘顶升和下降的能耗;dlift为四向车顶升或下降托盘的距离。

四向车将货物搬运到指定货位,搬运途中不可避免要做转向运动,四向车的转向运动实际上是对不同方向运动轮的顶升运动,故四向车转向时的能耗计算如式(30)所示。

(30)

式中:Wqturn为执行作业q时转向的能耗;dturn为四向车换向机构的行程。

根据仓库布局特点得出货位分配后目标货位与出入库口在x、y、z轴方向的距离分别为

dqx=(xq-x0)·w

(31)

dqy=(yq-y0)·l

(32)

dqz=(zq-z0)·h

(33)

由式(31)～(33)得出的距离可得作业q在x、y和z轴方向的搬运能耗Wqx、Wqy、Wqz如表2所示。

表2 单笔作业搬运能耗计算方法Table 2 Calculation method of energy consumption for single operation

由单笔作业能耗可得单批作业四向车与提升机的总能耗W为

(40)

2.2 降低货架重心

实际仓储过程中,应该尽可能地让质量较大的货物放置在货架的低层,从而降低货物与货架的整体重心,以保证出入库作业安全。货架垂直方向的重心计算如式(41)所示。

(41)

式中:Oz为货架垂直方向的重心;mxyz为坐标(x,y,z)货位上的货物质量。

2.3 均衡作业分布

当多个作业的目标货位被分配在同一层时,由于该层四向车数量的限制易造成作业堵塞,从而影响整体仓储效率,因此,在货位分配时应尽可能使各层的作业数量分布均衡。作业分布均衡度B表示分布在每层的作业数量离散程度,反映作业在层间分布的均衡程度,B值越小,表示作业分布越均衡。B计算如式(42)所示。

(42)

2.4 货位分配优化模型

由于各个子目标的量纲不同且计算结果的数值大小差异较大,故需要对目标函数进行归一化处理,具体如下:

(43)

(44)

(45)

Wmax=Wqxmax+Wqymax+Wqzmax,Wmin=0

(46)

Ozmax=Z·h,Ozmin=h

(47)

(48)

(49)

式(43)中Wmax为货物重量达到货位承载最大载荷时,目标货位被分配到离出入库口在3个方向都达到最远时的能耗值,Wmin为最小能耗值;式(44)中Ozmax为货架重心最大值,Ozmin为货架重心最小值;式(48)中W*、Oz*和B*分别为归一化后的作业能耗、货架重心高度和作业分布均衡度;式(49)中Omax为货位能承载的最大载荷,Aq为作业q的货位可行域,Aq是实时变化的。当为入库作业q分配货位时,Aq是在此时的空货位集合Semp中去除已经被其他入库作业占用的货位集合Sin,即Aq=Semp-Sin。当为出库作业q分配货位时,Aq是在满足当前出库需求的库存货位集合Sinv中去除已经分配给其他出库作业的货位集合Sout,即Aq=Sinv-Sout。

在实际出库作业中,可能会出现库存货位上的物料种类或数量无法满足出库需求的情况,为了最大限度地为出库作业分配货位,每个出库货位k引入出库能力服务系数βk,其计算如式(50)所示。

(50)

式中:S为出库作业所需物料种类总数;okc为货位k存有物料c的数量;rkc为货位k需要物料c的出库数量。

(51)

由式(51)可知,出库能力服务系数βk∈[0,1],βk值越大,该货位的出库能力越强,βk值越小,该货位的出库能力越弱。根据实际仓储环境,设置βk的最低阈值,系统从数据库中筛选出高于此阈值的货位,动态生成出库货位可行域。

通过多目标加权建立考虑能耗的货位优化模型(简称“能耗模型”)如式(52)所示,其中,ω1、ω2和ω3分别为W*、Oz*和B*的权重。在面向低能耗的货位分配优化模型中,主要优化目标是节省设备作业能耗,故为W*子目标分配最大权重。由于降低重心与节能两个子目标都倾向于把货物放在较低的货架层,又因为在货架可靠性设计时,通常已经充分考虑重心对力学稳定性的影响[19],所以在货位优化时为Oz*子目标分配较小权重。在W*和Oz*两个子目标的共同作用下,货物易被分配在较低层货位,为避免作业被集中分配在较低层,造成作业堵塞进而降低仓储效率,为B*子目标分配较大权重。权重大小设置为ω1>ω3>ω2。

FW=min(ω1·W*+ω2·Oz*+ω3·B*)

(52)

为了验证能耗模型的有效性,引入考虑距离最短的货位优化模型(简称“距离模型”)进行对比,如式(53)所示。

Fd=min(ω4·S*+ω5·Oz*)

(53)

(54)

式中:S*为单批作业的总距离,其计算方式如式(54)所示;ω4和ω5分别为子目标S*和Oz*的权重。距离模型重点对作业距离进行优化,权重大小设置为ω4>ω5。

3 自适应变异差分进化算法

自适应差分进化算法通过自适应调整进化算子提高算法的收敛性能。基于自适应差分进化的货位优化算法步骤如下所述。

3.1 初始化及编码

首先进行种群初始化,种群由多个个体向量x组成。个体向量x=(x1,x2,…,xj,…,xn),j为基因在向量内部的索引,基因索引对应作业编号,j∈[1,n],n为个体长度,即作业个数。xj如式(55)所示,每个基因采用0～1的实数编码。

xj=rand(0,1)

(55)

3.2 解码

将作业q对应的基因值解码后可获得作业的目标货位(xq,yq,zq),解码过程如图3所示,解码计算方法如式(56)所示。货位可行域通过对数据库动态查询进行更新。

图3 解码过程示意图Fig.3 Decoding diagram

(56)

式中:v为作业对应的基因编码值;L为货位可行域中的货位总数;I为求解货位在货位可行域中的索引,索引为向下取整的结果。

当可行域货位数量L=10,编号为2的作业基因编码为0.2,经过计算货位索引I为1,对应于可行域中货位是(5,4,3)。

3.3 变异

个体变异计算如式(57)所示,自适应产生变异缩放因子F,其由Fi1和Fi2两部分[20]组成,三者的计算如式(58)～(60)所示。其中:Fi1按时间呈非线性自适应衰减,保证算法前期有较好的全局搜索能力,以及后期有较好的局部勘探能力;Fi2按每个个体自身与种群最优个体目标函数值差异来自适应调整。

(57)

(58)

(59)

(60)

3.4 交叉

(61)

3.5 选择

如果试验向量ui的目标函数值小于等于目标向量xi的目标函数值,那么试验向量在下一代中取代目标向量,否则目标向量会继续保持到下一代,选择操作如式(62)所示。

(62)

4 试验与分析

为验证上述模型和算法的有效性,本文使用图1所示的四向车仓储系统布局结构为例进行试验,仓库规模与生产企业的中小型仓库规模相仿。用于试验的仓库规模、货位参数、四向车、提升机主要规格参数如表3所示。

表3 四向车仓储系统参数

将分别考虑能耗和距离的货位分配模型进行对比试验,试验作业信息如表4所示。试验计算机基本配置参数为AMD/Ryzen 5 4600U/2.1 GHz/16 GB,操作系统为Windows 10,使用C#编写算法,Python分析试验结果。

表4 不同载荷的作业信息Table 4 Operation information of different loads

设置3种库存占有率分别为30%、50%和70%,库存平均分布在每层和每排。设置3种载荷类型:低载(m<600 kg)、中载(600 kg≤m≤1 200 kg)、重载(m>1 200 kg),每种载荷类型随机生成10笔作业。两个模型在不同库存规模和不同载荷类型情况下各进行两组试验,每组试验测试8次,每次试验10笔作业。差分进化算法的最大迭代次数为500,初始种群规模为50,变异参数自适应变化范围为0.1～0.5,交叉概率为0.5。经过多次试验对结果进行分析并调整权重,最终设置能耗模型的子目标权重比为ω1∶ω2∶ω3=3∶1∶2,距离模型的子目标权重比为ω4∶ω5=4∶1。

选择不同库存情况下两组试验中综合目标函数值最低的一组试验为例,货位分配结果如图4所示,其中,绿色标识为预设库存,橙色标识为货位分配结果。货位分配优化求解的迭代曲线如图5所示。

图5 不同模型的货位分配优化求解迭代曲线Fig.5 Iterative curve for optimal solution of storage allocation for different models

由图5可知,能耗模型在库存占有率为30%、50%、70%条件下求解出货位分配结果所需要的迭代次数分别为66、85、95,而距离模型需要的迭代次数分别为196、176、189,显然能耗模型的求解速度优势明显。

统计不同库存规模下2种模型的试验结果,并计算得出各目标的平均值如表5所示,表中数据经过归一化处理,故没有量纲。在3种不同库存条件下,能耗模型求解8次试验所需的平均迭代次数分别为70、87和88,距离模型需要的迭代次数分别为141、138和155。能耗模型在求解速度方面普遍较优,至多可以提高50%。

表5 不同库存规模两种模型的试验结果Table 5 Experimental results of two models with different inventory sizes

由表5可知,能耗模型在不同库存规模下的重心高度全部小于距离模型下的重心高度,因此前者货架更稳定。

由表5可知,在3种库存规模下能耗模型和距离模型的作业分布都比较均衡,可以有效避免作业过于集中于某一层而造成作业堵塞。能耗模型在节能降耗的同时,兼顾了作业均衡。

不同库存规模下,能耗模型与距离模型相比,前者搬运距离分别增加了6%、4%和4%,即搬运效率有所下降,而在总体能耗方面,即同时考虑提升机和四向车的作业能耗,总能耗分别节约了12%、10%和14%。由此可见,在搬运效率稍微下降的情况下,能耗模型节能显著。

在四向车能耗方面,由于四向车受到自身电池电量的限制,作业一段时间后需要进入仓库中的充电位充电,由于充电位数量有限,可能会出现四向车排队充电进而堵塞交通的情况,这将影响仓库整体的作业效率。减少四向车的作业能耗,可以降低充电频次,节省充电位资源。由表7可知,在3种不同的预设库存规模下,能耗模型与距离模型相比,前者四向车执行同批作业分别节能7%、7%和5%左右。

预设库存规模为50%,在3种不同载荷类型下进行试验,试验结果如表6所示。

表6 不同载荷类型两种模型的试验结果Table 6 Experimental results of two models with different load types

由表6可知,不同载荷类型下,与距离模型相比,能耗模型在总体节能和求解效率方面具有明显优势,在降低重心和四向车节能方面继续保持优势,两者的作业分布都较均衡。综上所述,对于不同质量分布的作业,能耗模型都可以合理有效地分配货位。

5 结 语

针对四向车式密集仓储系统的货位分配问题,提出一种面向低能耗的货位分配优化模型以及自适应的差分进化求解算法。经过仿真试验得出,上述模型及算法在减少仓储能耗与提高求解效率两方面均具有显著优势,对促进绿色、节能、高效仓储具有积极意义。

实际仓储作业能耗与搬运设备的路径规划、作业调度密切相关,综合考虑货位决策、设备路径规划及作业调度的仓储节能降耗问题有待进一步研究。