双向式自动化立体仓库货位分配优化

蔡安江,叶 康,郭师虹,庞飞彪,于海滨

(1.西安建筑科技大学 机电工程学院，陕西 西安 710055；2.西安建筑科技大学 土木工程学院，陕西 西安 710055；3.德州海天机电科技有限公司，山东 德州 253000)

0 引言

货物分配作为制造业仓储运输环节的重要组成部分，对货物的进/出库效率起着决定性作用[1]。合理的货位分配方法可以有效地缩短工作时间，提高工作效率，延长货架的使用寿命，减少企业的运行成本，与企业的效益密不可分[2-3]。但随着企业规模的扩大和仓库存储需求的提高，双向式布局的仓库在货物存储能力及效率方面明显优于单向式仓库，因此对双向式立体仓库货位分配的研究具有重要意义。

对于现代制造模式下立体仓库的货位分配研究，国内外学者已经进行了较为深入的研究。汤洪涛等[4]和WANG等[5]均以堆垛机拣选效率为目标函数，分别提出K-Medoids聚类的粒子群优化算法和蚁群聚类算法，虽然算法有效地提高了仓库拣选效率和货物分配方式，但在其优化过程中均没有考虑货架的稳定性这一要素，无法保证货物摆放时货架的平稳安全；李鹏飞等[6]针对货架稳定性和货物出入库效率建立数学模型，采用病毒协同遗传算法进行优化，取得良好效果，但在建模时没有考虑货物的关联性原则，不适用于同类货物的存储优化。以上研究均在建立货物分配模型时进行，建模的原则考虑不周。张贵军等[7]和焦玉玲等[8]均以货架重心、堆垛机运行时间和货物关联性等为参考因素，分别提出了精英多策略和多种群遗传算法进行优化，取得了良好效果；李小笠等[9]以堆垛机能耗、货架稳定性和运输效率为目标，将多目标转化为单目标函数，并利用嵌套分区算法优化，有效解决了仓库的货位分配问题。上述研究方法可以有效优化单向式仓库货位分配的问题，但由于双向式立体仓库出入口的不确定性导致堆垛机搬运货物时对出/入口选择的不同，影响堆垛机的运行时间，因此此类建模方法不适用于双出/入口布局模式下的立体仓库。鄂晓征等[10]建立了以堆垛机拣选效率和货架稳定性为分配原则的数学模型，采用遗传算法进行货位优化，取得了一定成效，但遗传算法易陷入局部最优，且收敛速度较慢，当存取货物较多时无法找到全局最优解；BOTTANI等[11]和ATMACA等[12]均以自动化立体仓库货位分配原则为前提，建立了货位分配模型，并采用遗传算法、模拟退火算法对模型进行优化求解，验证了所建模型的正确性和智能算法的适用性。上述研究采用的多为标准的智能算法，虽有一定成效，但易陷入“早熟”，鲁棒性较差。

因此，本文以双向式布局模式下的自动化立体仓库为研究对象，建立以出入库效率、物品相关度和货架稳定性为优化原则的数学模型，为避免结果陷入局部最优，采用改进混合蛙跳算法(Improve Shuffled Frog Leading Algorithm, ISFLA)，解决了双向式立体仓库在货位分配问题上采用“逐层放置”等传统方式的弊端，优化了货物的摆放位置，从而提高双向式立体仓库的运行效率。

1 货位分配模型

1.1 模型基本假设

双向式布局模式下的立体仓库每两排货架之间架设有一条巷道，巷道上有一台堆垛机负责货物进/出库的运输，仓库左右两端各有一个进出口。货架的局部俯视图如图1所示。

针对双向式立体仓库分配遇到的相关问题和应遵循的原则，为了便于模型的建立和问题的研究，仅考虑一组货架(即两排)并特别作出如下假设：

(1)假设某仓库有a列，b层，c排货架，为区别单向式立体仓库，定义左端出入库台底部为坐标原点，货架第x列、y层、z排的货物坐标可表示为(x,y,z)。

(3)每个货位只能储存一个货物，且货位的长宽高都相等，设为L。

(4)假设堆垛机的运行速度恒定，堆垛机的水平、垂直和叉货速度分别设为Vx，Vy，Vz且不互相干涉，忽略堆垛机启动和制动的时间。

1.2 货位多目标分配模型的建立

定义(x,y,z,Pk,Mk,j)为货架中某一待入库货物的信息，其中：(x,y,z)表示该货物在仓库中货架中的位置坐标，它决定着货物分配的最终结果，属于决策变量；Pk表示(x,y,z)货位中货物的出入库频率(也可称为周转率);Mk表示货物的质量，它们是待入库货物本身的固有参数；j表示货物出入库台的列数，j=0或j=a+1。其中j=0表示最左端出入库台所对应列数，j=a+1表示最右端出入库台做对应列数。左出入台位置可表示为(0,1,0)，右出入台位置可表示为(a+1,1,0)。

(1)建立以出入库效率为目标的函数F1

货物出入库时，一方面要尽可能地缩短货物到货架的之间的距离，进而达到缩短堆垛机运行时间的目的，同时还要考虑货物的周转频率。即堆垛机运送货物到指定货位的时间与货物的周转率乘积最小(将周转率看作频率系数)，则建立的待优化函数为：

(1)

(2)建立以货品相关性为目标的函数F2

同种类型产品尽可能存放在相邻或相近的货位，可降低相关性高的产品的储存距离，减少堆垛机的运行距离。因此，当有一批待入库的货物进行存放时，在空余货位确定一位置为中心货位，使待存放货物距离中心货位的距离尽可能短，这样可减少堆垛机存取同类货物运行的时间。

当有n个货位可以提供k类产品储存时，定义此时的组内平均坐标(中心货位)为(ak,bk,ck)，其取值根据实际订单决定，则待存放货品(x,y,z)距离平均坐标的距离

(2)

根据双向式自动化立体仓库货位布局特点，为使所有待存放货品距离平均坐标(中心货位)距离最短，则优化的目标函数为：

(3)

(3)建立以货架稳定性为原则的目标函数F3

货架应该符合上轻下重的原则，尽可能地降低货架重心，把轻的货物放在上层，重的货物放在下层，防止货架因为重心不稳而导致倾覆，即货物质量与其所在层数的乘积的和最小。

建立以货架稳定性为原则优化的目标函数为：

(4)

显然，所建立的模型是一个多目标函数，3个目标函数之间相互影响。为方便计算，要将多目标函数转化为单目标函数，并根据仓库实际情况确定相关系数。

Fmin(x,y,z)=μF1min(x,y,z)+

μ2F2min(x,y,z)+μ3F3min(x,yz)。

(5)

s.t.

0<μ1<1;

0<μ2<1;

0<μ3<1,

μ1+μ2+μ3=1。

2 算法设计及验证

2.1 混合蛙跳算法设计

混合蛙跳算法(SFLA)是一种新的启发式群体优化算法，由EUSUFF等[13]于2003年最先提出，主要模拟池塘中青蛙寻找食物路径的过程，来模拟算法的搜索过程，通过局部搜索和全局搜索来完成[14]。子群中的青蛙通过群内的局部信息交流来优化个体，迭代到一定次数后再进行全局的搜索交流。在局部搜索过程中，按照混合蛙跳算法的更新公式，对每一个子群中表达最差的蛙Pworse进行更新替换，公式如下：

STEP=rand()×(Pbest-Pworse)((Dmin)

≤STEP≤Dmax),

(6)

混合蛙跳算法在寻找最优解的过程中，青蛙的移动步长决定着算法的搜索速度和准确度，步长过大容易跳过最优解，过小则使收敛速度过慢。在标准混合蛙跳算法更新公式中，rand()是0～1间的随机数，使得移动步长STEP随机更新。这种更新方式容易使结果陷入局部最优，无法充分发挥算法的优越性，因此，设计了以余弦函数为基础的动态自适应同步因子：

(7)

2.2 ISFLA算法步骤

针对所建立的双向式立体仓库模型，采用ISFLA进行优化，算法具体步骤如下：

步骤1初始化参数。随机生成m(memeplex)个子群，其中每个子群有n只青蛙，每只青蛙代表一种货位分配方式。设置青蛙最大跳跃的最大步长Dmax，子群内青蛙迭代次数gn，种群最大迭代次数Gn。

步骤2初始化种群。在可行解范围内生成F=m×n只青蛙，代表初始分配方式有m×n种，设置青蛙的维度S，每只青蛙可以表示为{X1,X1,…,XF}。

步骤3重新划分子群Z1,Z2,…,Zm。将所有青蛙按计算适应值，记每个青蛙的适应值为f(i)，按照从大到小的顺序将青蛙排列并按照如下规则划分子群：

Zk={X(j)k,f(j)k|X(j)k

=X(k+m(j-1)),f(j)k=f(k+m(j-1))}。

(8)

式中：j=1,2,…,n;k=1,2,…,m。

步骤4记每个子群中适应度最大的青蛙为Pbest，适应度最小的青蛙为Pworse。

步骤5记青蛙子群tm=0，表示子群进化的数目;tn=0，用来表示子群内局部搜索的迭代数。

步骤6设tm=tm+1。

步骤7设tn=tn1。

步骤8按照式(10)的更新策略，更新子群中表现最差的青蛙。

STEP=φ×(Pbest-Pworse),

Dmin≤STEP≤Dmax,

(9)

步骤9若更新后的青蛙适应值优于Pworse，则替之；若不如，则用全局最优解PB代替Pbest，返回步骤8进行重新选择；若还是不如Pworse，则随机生成一只青蛙代替。

步骤10判断是否tn

步骤11判断是否tm

步骤12迭代达到规定次数时，算法结束。输出全局最优解PB，并输出对应的目标函数值。解码之后，得到最优的货位分配坐标及出入库台坐标。

改进混合蛙跳算法的流程图，如图2所示。

2.3 算法验证

为验证改进算法的正确性和有效性，选取4个测试函数来进行实验仿真验证，通过与改进前的标准算法作对比，来说明改进算法的有效性和优越性。测试函数的表达式、维数、搜索域、最优解等如表1所示，表中前两个为单峰函数，后两个为多峰函数。算法所用参数如表2所示。

表1 测试函数参数

表2 测试函数算法参数

进行算法验证时，为保证实验不受偶然因素的影响，每个函数分别进行20次实验，取20次实验的最优(BEST)、最差(WORSE)以及平均值(AVERAGE)作为评价标准，各仿真数据如表3所示，函数迭代图如图3所示。

表3 函数实验数据

由表3可以看出，改进后的算法在测试函数上的表现要明显优于改进前。在各个函数的表现上，ISFLA的实际最优明显强于SFLA且无线趋近于理论最优值0，说明ISFIL的搜索性能较好。从图3可以，ISFIL在迭代速率上相比SFIL也明显更快，且不容易陷入“早熟”，具有较强的鲁棒性。仿真结果表明了ISFIL的有效性和优越性。

3 实例仿真验证

3.1 编码设计

基于任务编码是算法求解问题的关键步骤，常用的编码方式有二进制编码、整数编码、符号编码等，通常需要根据实际要解决的问题选择合适的编码方式。在用ISFLA进行双向式立体仓库货位分配优化时，由于货位坐标的特殊性，采用十进制整数编码方式，每只青蛙代表一种货位分配方式。

在初始化种群时，货位分配坐标随机生成。首先对待入库的货物进行编码，编码对应周转率、质量等信息；其次对货位进行编码，编码的长度由待入库分配货物的数量决定，编码分为若干小段，每段代表着一个货位的坐标，由于货位坐标是(x,y,z)三维存在的，定义行、列、排分别用x,y,z三个数表示，即货位编码长度N=3Na。

假设现有3个待入库货物，则Nα=3，N=9。对其的货物编号分别为1，2，3。1货物准备放入(2，4，7)货位，2货物准备放入(1，3，2)货位，3货物准备放入(3，3，4)货位，则货位的编码为(2，4，7，1，3，2，3，3，4)，具体编码如图4所示。

解码相当于是编码的逆向过程。把算法的解映射到实际的问题中去，对于双向式立体仓库货位分配问题，把算法得到的最优解按照每3个进行划分，就可得到实际的货位坐标。

3.2 适应度函数设计

适应度函数是改进混合蛙跳算法(ISFLA)进行迭代选择的依据[15]。本文货物分配位置的优化，即堆垛机运行时间最少、货架重心最低和相关联的货物之间的距离最小。根据所建立的目标函数，将适应度设为：

(11)

适应度函数越大，货架的优化程度越好。

3.3 实例仿真

由于货位分配的侧重点不同会导致分配结果的不同，通过层次分析法(Analytic Hierarchy Process, AHP)的计算以及综合考虑立体仓库的实际情况，取μ1=0.426，μ2=0.283，μ3=0.291。

以某汽车配件厂的双向式立体仓库货位分配任务为例，采用MATLAB进行仿真验证，仓库的各项参数如表4所示。

表4 双向式自动化仓库基本参数

现有15件待入库的货物，已知各个货物的质量以及周转率，并按照随机分配的方式给出货位的初始入库坐标和出入台坐标，如5表所示。

表5 优化前货位坐标

针对此次货位分配任务，采用标准遗传算法GA、SFLA和ISFLA分别进行优化。算法的参数如表6所示。

表6 算法参数

运用所建立的双向式自动化仓库货位分配模型并结合GA、SFLA及ISFLA对该货位分配任务进行优化仿真求解，其算法优化过程适应度值变化如图5所示。

ISFLA优化后的货位坐标及出入库坐标如表7所示。

表7 优化后的货位坐标

从图5可以看出，随着迭代次数的增加，目标函数值不断减少，说明其解逐步逼近最优解。相比GA与SFLA，ISFLA明显收敛速度更快，在140代左右达到最优，此时函数值为1.452，SFLA在200代左右达到最优，函数值为2.132，GA在250代左右达到最优，函数值为2.433。可见ISFLA相比SFLA与GA的效率分别提高了28.9%与41.6%左右，证明了ISFLA的有效性和优越性。

为验证算法对双向式仓库不同规模入库任务的实际作用，增加中型货物入库规模和大型货物入库规模的验证，表4和表6参数保持不变，入库货物的基本参数如表8和表9所示。

表8 中规模入库任务货物参数

表9 大规模入库任务货物参数

运用所建立的双向式自动化仓库货位分配模型并结合GA、SFLA及ISFLA对这两批货位分配任务进行优化仿真求解，其算法优化过程如图6所示。

从图6可知，ISFLA处理中、大规模货物的入库货位分配时，相比于GA和SFLA，在迭代速率和解的质量方面都有较大的优势，从而进一步验证了ISFLA在处理双向式布局模式下立体仓库货位分配问题时的有效性和优越性。

4 结束语

本文针对双向式立体仓库货位分配问题，建立了以入库效率、货架重心和产品聚集度为优化目标的数学模型，采用ISFLA改变了局部搜索时的更新策略，减少了堆垛机取/存货时间，提高了货架的稳定性，有效的提升了仓储管理的效率。

通过对标准蛙跳算法局部搜索策略的改进，改变了淘汰最差蛙时的选择策略，可以及时更新最差蛙的位置，使子群内青蛙可以充分信息交互，弥补其在解决多目标优化问题时易陷入局部最优的缺点，增加了算法的搜索速度，并用测试函数验证了改进算法的正确性和有效性，在其解决双向式立体仓库的货位分配优化问题时，效率明显提升。

相比于GA与SFLA，ISFLA具有更好的收敛性。双向式立体仓库货位分配优化时，可以不断对货物位置进行更新，避免了GA与SFLA易陷入局部最优解且收敛过慢的缺点，有效地提高了迭代速率和解的质量。

本文未验证其他布局类型的仓库是否也可用ISFLA来进行优化分配，下一步可以据此展开研究。另外，增加堆垛机的数量和出/入口的数量可以提高仓库的运输效率，在其数量上寻找最优也是未来建立仓库模型时可以考虑和研究的方向。