考虑时间和能耗的立体仓库三维空间路径优化

夏绪辉，朱 强，王 蕾,2，曹建华

(1.武汉科技大学冶金装备及其控制教育部重点实验室，湖北 武汉，430081；2.武汉科技大学服务科学与工程研究中心，湖北 武汉，430065)

自动化立体仓库系统(Automatic Storage & Retrieval System，AS/RS)集存储、输送、分发、管理等功能于一体，具有存储容量大、占地面积小、运转速度快等特点，是现代物流系统的重要组成部分，在物料供给部门、大型商业系统等领域有着广泛的应用。搬运作业是自动化仓库中最常见的作业方式，合理选择作业路径是提高自动化立体仓库运行效益的有效手段。

近年来，针对AS/RS路径优化问题的研究成果有不少。例如：田国会等[1]在分析立体仓库拣选作业时间组成的基础上建立优化模型，采用混合遗传算法进行求解；方彦军等[2]以轨道引导小车作业距离最短为目标建立数学模型，通过改进人工狼群算法求解，提高了仓库的运行效率；朱文真等[3]研究立体仓库中单一作业和复合作业的路径优化问题，设计了一种遗传禁忌混合算法对堆垛机作业路径进行求解；杨玮等[4]构建了以时间最少为目标且考虑加速度影响的调度优化模型，采用混合蚁群算法求解，提高了密集仓储系统进出库效率；蔡安江等[5]建立以堆垛机调度时间最小为目标的优化模型，采用遗传算法求解，提高了立体仓库的运行效率；Ma等[6]为解决自动化立体仓库的时间规划问题，考虑作业载重和行驶距离等因素建立多目标路径优化模型，设计一种基于集成学习的优化算法，降低了调度时间；Azzi等[7]在堆垛机运行时间模型中考虑加速度的影响，采用蒙特卡洛分析方法来求解，并通过实例验证了模型的可行性；Nia等[8]针对单机负载多机架AS/RS，建立以时间成本和碳排放成本最小为优化目标的低碳数学模型，通过具体实例验证模型的有效性；Meneghetti等[9]研究了立体仓库中货位分配问题并建立能耗模型，将能量消耗最少的位置分配给存取频率最高的货物，减少了仓库货物分配时间和能耗；Lerher等[10]针对微型负载AS/RS建立以电能消耗为基础的能效模型，通过仿真验证了模型的有效性；Ene等[11]在立体仓库订单分配过程中考虑能耗因素，建立以货叉电机耗电量最少为优化目标的数学模型，采用遗传算法对其求解。

现有关于AS/RS路径优化问题的研究多以时间、距离等为优化目标，虽有涉及能耗，但大多只考虑单目标优化。本文针对自动化立体仓库在三维空间内的路径规划问题，在考虑堆垛机运动过程中加速度、搬运距离及载重对能耗影响的基础上，从运动学的角度建立能耗模型，为综合体现时间与能耗两方面因素对路径选择的影响，构建以堆垛机作业过程绿色度[12]最大为目标的优化模型。为提高基本蚁群算法的收敛速度及避免陷入局部最优，提出一种基于免疫蚁群的路径优化算法对模型进行求解，并通过实例仿真验证所建模型的适用性及算法的有效性，以期为堆垛机作业路径选择提供一种新的思路和方法。

1 问题描述和数学模型

1.1 问题描述

自动化立体仓库主要包括巷道式、贯通式、水平旋转式和垂直旋转式等类型，其中巷道式立体仓库是一种最为典型的仓储形式，如图1所示。假设各货位可存储某种尺寸的货物，坐标(x,y,z)分别对应货位所在的排、列和层，各货格的长、宽、高分别为l、w、h。图1中O为出入库台，P为第i次入库货位，R为第j次出库货位，堆垛机在作业巷道往返运动并负责货物搬运。

图1 自动化立体仓库简图

堆垛机的作业形式分为单指令作业和双指令作业。单指令作业指堆垛机进入仓库只完成一次货物的出库或入库作业；双指令作业指堆垛机执行的任务序列中同时存在出库与入库指令，堆垛机进入仓库一次完成一个入库任务和一个出库任务。为了便于分析，将堆垛机运动沿水平和垂直方向分解，每个方向上有其自身的运动形式。

对于单指令作业：在入库环节，堆垛机装载目标货物后，从O点出发，沿着巷道运动到待入库货位所在的列和行，完成入库任务后沿作业巷道回到O点；在出库环节，堆垛机从O点出发，沿着作业巷道运动到待出库货位所在的列和行，装载货物后沿作业巷道返回至O点。

对于双指令作业：堆垛机完成入库环节后，空载运动到待出库货位所在的列和行，装载货物后沿作业巷道返回至O点，完成出库任务。

考虑堆垛机在运动过程中存在加速度，根据其运行速度能否达到额定速度(vmax)，将运动形式分为第I类运动(SI≤Slim)和第II类运动(SII>Slim)，如图2所示。

图2 两类运动的位移-速度曲线

Fig.2Displacement-velocitycurvesoftwokindsofmovement

1.2 数学模型

模型假设：①货物质量小于机器人的额定载荷；②堆垛机在下一轮入库作业时，货物已到达出入库台，以保证任务的连续性；③堆垛机的启动、停止、装载、卸载及定位的时间均为固定值，不考虑其对优化结果的影响。

1.2.1 堆垛机路径时间模型

堆垛机在水平和垂直方向上的运动形式取决于其在两个方向上行驶的距离。根据基本位移公式，堆垛机在两个方向上达到额定速度所需的临界距离为：

(1)

(2)

对于第I类运动，当水平和垂直方向上运行距离分别为Sx和Sz时，其所用的时间为：

(3)

(4)

对于第II类运动，当水平和垂直方向上运行距离分别为Sx和Sz时，其所用的时间为：

(5)

(6)

综合考虑以上两类运动形式，得到水平和垂直方向上的行驶时间tx、tz分别为：

(7)

(8)

机器人从出入库台运行至目标货位，总的行驶时间是水平和垂直行驶时间的最大值，即：

t=max(tx,tz)

(9)

由堆垛机单双指令流程可知，完成Q1次单指令任务及Q2次双指令任务所用的总时间为：

(10)

1.2.2 堆垛机路径能耗模型

堆垛机运动过程中消耗的总能量包括其在水平和垂直方向上变速和匀速时所需的能量，以及克服工作轨道摩擦力所需的能量。

(11)

(12)

因此，堆垛机在水平方向上的能量消耗为：

(13)

在垂直方向上，第I类运动和第II类运动所需能量用于克服重力及摩擦力做功，因此，垂直上升阶段单位质量消耗的能量ez1为：

ez1=(1+μz)gSz

(14)

垂直下降阶段单位质量消耗的能量ez2为：

ez2=(1-μz)gSz

(15)

由堆垛机单双指令流程可知，完成Q1次单指令任务及Q2次双指令任务总能耗为：

(16)

1.2.3 目标函数的建立

考虑堆垛机作业过程的环境友好性，可通过量化计算体系的绿色度来判断作业的绿色性[12]。以时间和能耗作为堆垛机作业过程绿色度G的定量指标，以最大化绿色度为目标，建立堆垛机作业路径优化数学模型：

(17)

约束条件：

l≤Sx≤L

(18)

h≤Sz≤H

(19)

0

(20)

(21)

2g(H+L+W)]

(22)

约束条件中，式(18)和式(19)为堆垛机在水平和垂直方向上运行距离的取值范围；式(20)保证堆垛机每次搬运货物的质量不超过其额定载荷；式(21)和式(22)为堆垛机完成一次搬运任务时的时间和能耗的取值范围。

2 基于免疫蚁群算法的模型求解

2.1 免疫蚁群算法数学描述

堆垛机路径优化已被证明是NP-hard问题，通常采用启发式优化算法求解[13]。蚁群算法具有并行计算、无中心控制等优点，是求解复杂优化问题的一种常用方法，但由于其在搜索初期缺乏有效的信息素，导致初期寻优时间较长、求解效率低且较易落入局部最优。免疫算法具有有效的全局寻优能力，搜索过程具有随机性、多样性，可获得很好的随机解，因此可以考虑利用免疫算法获得的随机解为蚁群算法提供初始信息，以避免蚁群算法因初值选择不当而陷入局部最优的问题。免疫蚁群算法流程如图3所示。

图3 免疫蚁群算法流程

2.1.1 编码方式选择

采用混合整数编码方式，如图4所示。假设有P个入库货位及R个出库货位，当P=R时，机器人需进行P次双指令作业；当P≠R时，机器人需进行min(P,R)次双指令作业及|P-R|次单指令作业。P个入库货位编码为1～P，R个出库货位编码为 (P+1)～(P+R)，每个编码都与货位一一对应，各编码组成一条路径规划方案，入库和出库货位分别是第奇数个元素和第偶数个元素。

图4 混合整数路径编码图

2.1.2 亲和度函数

针对堆垛机三维空间路径优化问题的特点，用每次迭代路径总长度作为亲和度评价算子。假设路径有N个节点，基于欧式距离构造亲和度函数aff如下：

(23)

式中：dis(i,i+1)为路径(i,i+1)(即从货位i到货位i+1)的距离。

2.1.3 自适应变异算子

为避免无指导突变导致突变结果优劣不定，从而使变异后的路径均不包含某一关键的优秀解决方案，因此本文提出采用基于亲和度的自适应变异率，根据迭代次数的不同，将每代中具有最大亲和度的抗体考虑到变异算子中，自适应调节变异算子，保证算法往更好的空间搜索。

foru=1∶Nmax

ifu==1

变异率=p

else

end

end

2.2 免疫蚁群算法步骤

步骤1参数初始化。迭代开始之前，设置蚂蚁数量A、终止条件NC_max、信息和期望启发因子α和β、每只蚂蚁携带的信息素蒸发系数ρ(0<ρ<1)。

步骤2确定初始信息素。采用混合整数编码，利用rand函数随机生成一定数量的初始种群，根据亲和度函数选择执行免疫操作的抗体，对其进行克隆复制，克隆得到的抗体进行自适应变异处理，改变抗体的亲和度；再次对变异结果进行选择以抑制具有低亲和度的抗体并保留亲和度高的抗体。

要使上述免疫算法求解结果有效，关键是要保证免疫算法的迭代次数。次数过大，蚁群算法得不到最优值；次数过小，无法提供有用的信息素值。选取10代为一个单位，若迭代曲线连续20个单位的目标值相同则停止迭代。免疫算法按照上述规则执行完后，将迭代后的可行路径对应的亲和度值作为蚁群算法部分初始信息素，因此，本文算法信息素的初值可以表示为：

τs=τc+τd

(24)

式中：τc表示信息素常数，相当于τ0；τd表示免疫算法提供的信息素。

步骤3初始化蚁群。把A只蚂蚁随机分派至n个货位上，并在禁忌表tau中记录各自位置。

步骤4每只蚂蚁从随机分配的货位出发，将走过的货位加入到禁忌表中，初始化解空间。

步骤5蚂蚁根据式(25)计算各可选货位的转移概率[14-15]，再根据轮盘赌法则选择下一步转移的货位并继续前进。

(25)

式中：tovisitk=(s-tau(k))，其中s为所有货位集合。

步骤6若k≥A，则表明每只蚂蚁已经遍历完所有货位，继续进行下一步，否则返回步骤4。

步骤7更新全局信息素。当所有蚂蚁对货位进行了一次遍历之后，选出一只路径最短的蚂蚁，作为本次迭代的最优蚂蚁，并按下式更新信息素[15]：

τij(t+1)=ρτij(t)+Δτij(t)

(26)

(27)

(28)

式中：Q为常数，表示信息素强度；Lk为最优蚂蚁所走路径的长度。

3 案例分析

3.1 案例数据与算法参数设置

以某中纤板切分企业自动化立体仓库为工况背景，该仓库设置有26排8层14列的固定货架，货物的质量分别为100、120、150 kg。堆垛机的最大承载数量为一个托盘，表1为堆垛机实际运行参数。为了更好地体现算法的优越性能，分别选取堆垛机执行30次和50次作业任务进行分析计算，表2和表3所示为30次作业的货位及其编码。采用Matlab R2014b进行仿真计算，运算平台配置为：处理器Inter®Celeron®CPU 1005M@2.5 GHz和内存4 GB的个人计算机。免疫蚁群算法的参数设置为：A=16，Q=100，α=1，β=5，ρ=0.5。

表1 堆垛机实际运行参数

表2 入库作业序列

表3 出库作业序列

为满足用户多样化的需求偏好，确定ω1和ω2时采用组合加权法将主观权重和客观权重综合考虑，使其更具实用性。先采用层次分析法确定主观权重，再采用变异系数法获得客观权重，通过式(29)计算出最终的组合权重系数[16]：

ωj=λAj+(1-λ)Vj

(29)

式中：ωj为第j个指标的组合权重系数；Aj和Vj分别为通过层次分析法和变异系数法确定的权重；λ表示偏好系数，λ∈(0,1)。

根据该企业对于时间、能耗的需求偏好度，采用层次分析法确定的权重A=[0.431,0.569]，采用变异系数法分析时间和能耗数据，确定权重V=[0.397,0.603]，本文λ取0.5，根据式(29)计算出组合权重系数ω=[0.414,0.586]。

3.2 仿真实验结果与分析

为了验证算法的优越性，根据目前对路径优化的研究方法，按照优化目标的不同将堆垛机路径优化问题分为以下3种：①)以作业时间最小为优化目标(记为PT)；②以能耗最小为优化目标(记为PE)；③以绿色度最大为优化目标(记为PW)。针对不同规模(30次和50次)的作业任务，分别采用传统蚁群算法、免疫算法和免疫蚁群算法进行路径优化，得到各算法的迭代收敛过程如图5所示，各优化目标(总时间、总能耗及绿色度)的求解结果如表4和表5所示。

(a) 30次作业PT收敛曲线 (b) 30次作业PE收敛曲线 (c) 30次作业PW收敛曲线

(d) 50次作业PT收敛曲线 (e) 50次作业PE收敛曲线 (f) 50次作业PW收敛曲线

图5 不同作业规模下3种算法的收敛曲线

表5 50次作业规模的仿真结果

由图5可知，对于不同规模的作业任务，本文提出的免疫蚁群算法收敛速度最快，对时间和能耗的优化值也有一定的改善，且算法的求解性能不会因为任务规模的增加而受到影响，具有较好的鲁棒性，而另外两种算法由于没有引入改进策略导致易陷入局部最优值。由此可见，免疫算法的解提供了有效的初始信息素，提高了蚁群算法的搜索能力，使得免疫蚁群算法可以有效解决堆垛机的路径优化问题。

由表4和表5可知，以PT为优化目标时，采用各算法得到的优化方案作业时间较少，但能耗较大且绿色度很低，因为在路径优化时，载重对能耗有一定的影响，单独优化时间会以增加能耗为代价达到时间最少的目标；以PE为优化目标时，优化方案的能耗最小，但作业时间较长且绿色度偏低，因为能耗的大小取决于运输距离和载重，在路径优化时，一味追求低能耗而忽视距离与载重的配合关系，会导致工作效率降低；以PW为优化目标时，可兼顾作业时间与能耗，优化方案的绿色度最大，例如30次作业采用免疫蚁群算法所得优化方案的总时间与以PT为目标的优化方案相比仅增加2.07%，但能耗降低了11.33%，而与以PE为目标的优化方案相比能耗仅增加4.45%，但作业时间降低了13.41%，其路径优化结果如图6所示。综合比较，PW优化方案明显优于其余两个优化方案，因此，在路径优化时不能一味追求高效率或者低能耗，而应该考虑机器人作业过程的绿色度，提高自动化立体仓库的综合运行效益。

图6 堆垛机30次作业的优化路径

4 结语

本文系统分析了AS/RS中堆垛机作业时间和能耗的构成，在此基础上，针对其三维路径规划问题，建立了以绿色度最大为目标的优化模型。针对该模型特点，采用免疫蚁群算法进行寻优求解，利用免疫算法结果提供蚁群算法的初始信息素，加快了算法收敛速度，同时避免了蚁群算法因初值选择不当而陷入局部最优。通过具体案例，分别从时间、能耗及绿色度三方面分析验证了本文提出的路径优化方法的可行性和实用性，其能够很好地平衡作业时间与能耗之间的关系。