四向穿梭车式密集仓储入库货位分配方法研究

李 佳，何 非，谢刚伟，杨 洋，房逸鹤

1.南京理工大学 机械工程学院，南京 210094

2.南京小智智能科技有限公司，南京 210000

3.江苏正贸仓储设备制造有限公司，南京 211111

在全球化和市场化的背景下，仓储物流行业已经成为经济活动中不可缺少的关键环节。货位分配作为仓储运输环节的重要组成部分，对货物的进、出库效率起着决定性作用[1]。合理的货位分配方法可以有效地缩短工作时间，提高工作效率，延长设备的使用时间。目前密集式存储、自动化仓储逐渐成为仓储行业的技术发展方向。四向穿梭车式密集仓储系统相较于传统的巷道式存储，仓库布局更加灵活，进一步提高了存储空间利用率。因此，对密集仓储货位分配方法的研究有重要意义。

对于自动化立体仓库的货位分配问题，国内外学者研究主要以堆垛机系统和子母穿梭车系统[2]为主。针对堆垛式立体仓库，黄鹏等[3]以堆垛机运行效率、货架稳定性和堆垛机负载均衡要求的货位分配多目标优化模型，采用集成遗传算法和延迟接受爬山算法的两阶段混合算法进行优化求解，算法解有较好的稳定性和精度。对于双向式自动化立体仓库，蔡安江等[4]以出入库效率、货架重心和产品聚集度为目标简历货位分配数学模型，使用引入动态自适应同步因子改进混合蛙跳算法对模型进行求解，解决了堆垛机选择不同出入口对运行时间的影响，取得良好效果。Wang等[5]针对子母穿梭车不同阶段的服务进行划分，建立排队网络模型，并利用聚类算法对商品进行存储区域划分。上述研究方法可以有效解决堆垛式和子母穿梭车式立体仓库货位分配问题，但由于密集仓储货位密集分布、穿梭车多轨道行驶的特点，分配货位的离散程度、提升机的选择策略等会严重影响仓库作业效率，此类建模方法不适用于对多批次作业、四向穿梭车式密集仓储。

针对四向穿梭车式自动化密集仓储系统，付晓锋等[6]在制定货物入库上架作业规则和流程的基础上，提出了入库上架过程的货位分配算法。即以货物出库时搭载穿梭车和提升机的行走距离作为衡量下架出库效率的指标，将入库周转频率较高的货物存储在下架出库效率较高的货道。该方法将仓库简单分区实现货物分类存放，并未考虑多穿梭车同时作业过程中的轨道拥堵、货架稳定性等因素。宋佼蓉等[7]基于四向穿梭车式全货位密集仓储系统的实时货位分配问题，提出了货位分配策略、原则以及优化目标，并以改进的遗传算法和A-star算法结合的方式进行了算例的求解验证，但并未考虑密集仓储中货架多深度对存取货作业流程的影响。在现有针对密集型仓储货位分配的研究中学者们通常将问题简化，并未深入考虑多深度货架对货物出入库流程带来的影响。

近年来采用遗传算法[8-9]、模拟退火算法[10]、粒子群算法[11]等优化算法的货位分配研究不断增多。而混合蛙跳算法（shuffles frog leaping algorithm，SFLA）结合了模因算法和粒子群算法的优势[12]，计算速度快，寻优能力强，目前已应用于求解组合优化问题，但是基于混合蛙跳算法的货位分配问题的研究还相对较少。

本文在对密集仓储建模、获取动态的货位信息基础上，对仓库货位进行货道划分。首先通过货物按类分货道进行货位分配、货道内制定货格的优先存储位置的策略，减少出现货物移位任务的可能性，简化穿梭车的作业流程和作业复杂度。其次通过建立以路径最短、货物分布均衡及货架重心稳定为目标的数学模型，使用改进的混合蛙跳算法得到了符合要求的货位分配方案，实现货物以货道为单位的离散分布，极大提高了仓库的运行效率。

1 问题描述

1.1 密集仓储货位分配问题

如图1所示，图中为单层密集型仓库的货位分布示意图。密集仓储模式下的自动化仓库主要由多层固定货架、四向穿梭车和提升机组成。其中，四向穿梭车搭载货物，通过轨道、空闲货道和提升机，实现货物的出入库流程。在执行出入库作业时，多个穿梭车和提升机可同时工作。假定货架垂直方向为z方向，沿货架主轨道方向为y方向，沿货位巷道方向为x方向。

图1 四向穿梭车式密集型仓库布局Fig.1 Layout of four-way shuttle storage and retrieval system

立体仓库货位分配问题中通常的优化原则有效率优先原则和货架稳定性原则[13]。但由于密集仓储货位巷道内货格多深度密集型分布的特点，货位分配问题需要考虑货物存放的密集程度对系统作业效率的影响。一方面，若简单地将货物存放在距出入库位置较近且较低层的货位上，则货物将在出入库附近聚集，造成集中存放区轨道拥堵，严重影响作业效率。另一方面，若货物以货格为单位离散存储，则穿梭车需要频繁执行货物换位任务以运输沿x方向深处货位上的货物，增加了作业复杂度，降低了效率。故针对四向穿梭车式密集仓储系统的货位分配问题，需要在货物分类存放的基础上考虑路径最短、货位分布均衡和货架重心稳定三个原则。

1.2 假设条件

四向穿梭车式密集仓储采用托盘集装、密集存储，通过单辆穿梭车搭载单个托盘货物进行作业。在仓储设备的作业流程中包括穿梭车的移货、换层操作，这限制了货物与货盘、货盘与货位间存在着硬性尺寸匹配关系，故文中合理假设货物与仓储设备等满足数量、尺寸约束。在四向穿梭车实际作业中，由于货架支撑结构的限制，通常货位上只能双向通行。因此，针对密集仓储分配遇到的相关问题和应遵循的原则，为了便于模型的建立和问题的研究，做出以下假设：

（1）整个密集存储系统内部单个货位只能存储一个托盘货物，且货位规格相同。

（2）存储区域的货格由于货架的限制，只能双向移动，即沿x方向行驶。

（3）进行货位分配前，已知仓储系统内剩余空闲货位信息和待入库货物的周转率、质量等信息。

2 入库优化数学模型的构建

2.1 四向穿梭车式货架建模

四向穿梭车式货架模型的主要参数如表1 所示。仓库中共有c层货架，每层货架有b排货架巷道，每层有a列货位。其中第z层y排x列的货位坐标记为：(x,y,z),x={1,2,…,a},y={1,2,…,b},z={1,2,…,c}。根据货位的存储状态，得到动态的空闲货位集合D={(xi,yi,zi)|i=1,2,…,N}。

表1 参数与变量定义Table 1 Parameter and variable definitions

已知待入库的第k种货物的信息(nk,pk,mk),k=1,2,…,K。其中nk表示该类货物的数量，pk表示该类货物的周转率，mk表示该类货物的质量。定义货位分配方案为T={T1,T2,…,TK}，其中Tk={(xi,yi,zi)|i=1,2,…,nk}，表示第k类货物在仓库中的位置坐标，则T中的货位坐标集合为D的子集。

2.2 划分货道

密集型仓库单层货架货位布局如图1所示，为提高货物出入库效率，单个存储货道通常只存储单类货物，以避免在出库作业时需要频繁执行货物移位任务。故货位分配时需要将货位划分货道，并以货道为单位分类存储货物。此外，由于密集仓储中货道内货格的多深度特点，通常采用先进后出的堆栈式货物存储管理策略。执行入库作业时，应优先将货物运送至货道深处，以减少后续货物的入库路径长度，并提高穿梭车作业时动态避堵的能力。

综上，定义单个货道只存放一种货物，从货道最深处货格开始存储货物，并且优先填满当前货道再使用新货道。最终货位分配方案应满足约束条件，即每类货物所选的货格总数不小于货物总数。

2.3 优化目标的提出

根据密集仓储的实际需求，建立如下优化模型。

（1）路径最短

当不考虑穿梭车存取货物和转向时间时，入库货物所分配货位距入库口越近，穿梭车从作业货位到提升机的路径越短，仓库的运行效率越高。

由于密集仓储的轨道特点，穿梭车、提升机搭载货物沿x、y或z方向移动，故使用曼哈顿距离计算坐标(xk,yk,zk)处货位到i入库口的距离。

假设仓库内入库口数量为L，得到穿梭车的作业总路径为：

（2）货位分布均衡

密集型仓储中，穿梭车沿轨道、空闲的货位巷道行走作业，其中轨道的畅通对仓储运行效率至关重要。不同主轨道区域的存储差别将极大影响穿梭车的拥堵情况，进而影响仓库运行效率。货位分配方案在x、y方向上的离散程度将影响穿梭车在不同主轨道的行走频率。同样若某种货物的货位分配集中在某一层，也将极易造成拥堵，影响工作效率。

为避免周转率较高的货物在临近的货道聚集、穿梭车拥堵等情况发生，用货道内货物的周转率之和表示货道的拥挤程度。以货道x、y、z方向上货道拥挤程度的标准差来反映货位分布的均衡程度，其值越小表示该方向上的货位分布越均衡。

式中，Xi、Yi、Zi分别表示第i列、排、层货架的货物的周转率总和；Xˉ、Yˉ、Zˉ分别表示理想状况下平均每列、排、层货位的平均周转率。

通过对三个方向的标准差进行加成得到衡量货位分配离散程度的函数：

（3）货架重心稳定

密集型仓储的货位分布较为集中，货物质量分布不均匀、重心较高等会影响货架的力学性能及稳定性。并且提升机运输货物换层时，作业能耗与货物质量成正比，质量较小的货物放在低层有利于减少能耗。考虑到货位均衡的原则，在此主要降低仓库内货物整体z方向的重心，以提高货架的稳定性并降低提升机能耗。

式中，mxyz表示在第z层y排x列货位上的货物质量；H表示该货位的高度。

2.4 入库货位优化的数学模型

由上述目标函数及约束条件，可建立如下自动化仓库货位多目标优化模型：

由于上文中三个目标函数的量纲、数值范围存在较大差异，故分别根据各个分目标函数的最优解fimin和最差解fimax，根据式（11）对目标函数进行归一化。

为了简化模型求解，对各目标进行主观赋权，采用层次分析法（analytic hierarchy process，AHP）构造判断矩阵求得特征向量，经过一致性检验确定特征向量的有效性后，得到各优化目标的权值αi。使用权重系数法将多目标优化问题转化为单目标优化问题。

3 基于改进的混合蛙跳算法的入库货位分配

SFLA 中，问题的解X用青蛙的位置表示，虚拟青蛙的种群集合为可能解的集合。SFLA算法具体流程如下：产生初始种群P后，种群中的解按照适应度值排序，将整个种群划分为s个模因组；然后执行局部搜索和模因组重构，重复初始化之后的各个步骤，直到满足终止条件。

SFLA有算法概念简单、控制参数少、易于实现的优点，目前已应用于求解旅行商、调度问题，但在解决高维优化问题时易出现早熟、解精度不够的情况[14]。并且对于约束较为复杂的问题，SFLA在寻找最优解的过程中，根据青蛙的移动步长更新青蛙个体极易不满足约束条件而用最优解替代，最终无法充分发挥算法的优越性。因此，本文借鉴遗传算法求解离散优化问题采用的交叉、变异算子方法[15]，提出一种改进的SFLA算法以解决在货道约束条件下的密集仓储货位分配问题。

3.1 编码及解码

根据仓库地图和货道划分标准，进行货道的划分，得到空闲货道总个数为N，采用十进制数对货道进行编号。假设当前仓库内有n个空闲货道(n≤N)，将n个货道的编号随机排列，即货位编码长度为n。

已知货道编码序列后，通过解码确定每个货物的货位分配。首先，根据货道序列得到对应货道内的货位数量、坐标等信息，然后将货物依次从序列头部对应货道开始存储，直至存放完所有货物，即满足式的约束条件。最终存储货物的编码子序列为当前货道序列的有效货位编码序列，即为当前编码的货位分配方案。该方案使得待分配的货物能够全部存储于分配货架巷道内。例如图2 所示，现有10 个待入库货物A、10 个待入库货物B，对其的货物编号为1、2。已知空闲货位的编码为（1，3，2，5，4，9…），通过对货道货位数量的计算，得到该条编码的方案为1货物准备放入1、3货道，2货物准备放入2、5 货道。其中，将（1，3，2，5）视为该条编码的有效编码序列。

图2 编码和解码规则Fig.2 Encoding and decoding rules

3.2 算法原理

初始化种群生成N个体，通过解码计算出个体适应度后，将种群内个体按照适应度值降序排序，按式（13）划分为s个子群：

其中，i=1,2,…,s,j=1,2,…,m,m为子群中个体的数目。

SFLA 通常以子群内最差解Pworse为优化对象，通过模因组内的局部搜索产生新解，具体过程如下：首先确定组内最优解Pbest、最差解Pworse以及全局最优解PB，然后根据式（14）、（15），利用Pbest和Pworse产生新个体Pnew：

式中，rand(0,1)表示在区间[0，1]上服从均匀分布的随机数。若Pnew优于Pworse，则替换最差解Pworse；否则，随机产生新解替换Pworse。重复以上步骤，直到达到设定的迭代次数。

其中，也有文献在子群内随机选择两个非劣解产生新个体Pnew[16]，或在式（14）移动步长中加入动态自适应同步因子[4]。本文选用Pworse为优化对象，结合遗传算法（genetic algorithm，GA）采用一种新的优化迭代方法。

（1）交叉

进行交叉操作时，设计了动态自适应同步因子更新个体基因。按照式（16）从Pworse的有效编码序列中随机选取w个编号记为W={p1,p2,…,pw}，其中g为当前种群迭代次数。

将Pbest中与W相同的编号移动到Pbest编码序列的末尾，即在Pbest的有效编码序列中剔除编号为W的因子，如图3示例所示得到新个体Pnew。

图3 交叉因子算法Fig.3 Crossover operation algorithm

（2）变异

本文的变异操作为随机排列n个货道，生成随机编码序列。

具体局部搜索过程描述如下：

步骤1按照适应度值排序结果，选择当前模因组内最优解Pbest、最差解Pworse，将Pworse作为优化对象。

步骤2设定交叉概率pc。进行交叉操作时，从Pworse的有效编码序列中随机选取编号序列W，在Pbest的有效编码序列中剔除W内的因子，得到新个体Pnew。

步骤3设定变异概率pm。进行变异操作时，随机生成新个体Pnew。

步骤4比较Pnew和Pworse。若Pnew优于Pworse，则更新最差解Pworse；否则，用全局最优解PB直接替换Pworse。

步骤5是否达到模因组迭代次数。若是，输出更新后的模因组；否则转到步骤1，直至完成局部搜索。

3.3 算法步骤

所述算法的基本流程图如图4所示，具体步骤如下：

图4 改进混合蛙跳算法流程图Fig.4 Operation flow of improved shuffles frog leaping algorithm

步骤1设置参数。

步骤2初始化种群P，计算根据式（12）计算个体适应度。

步骤3根据适应度值对种群个体排序，根据式（13）划分模因组。

步骤4局部搜索。对每个模因组按3.2节的策略进行个体的更新，直到达到局部搜索次数。

步骤5重新混合各个模因组中的所有个体，更新种群中最优个体。

步骤6是否达到种群迭代次数。若是，则输出PB作为迭代后的最优解；否则，转到步骤3。

4 实例验证分析

4.1 算法验证

以图1所示的仓库布局为例进行实验，该仓库的数据如表2所示。其中单个货位的长和宽、轨道的宽度均为1个距离单位，相邻货位或相邻的轨道和货位间的距离忽略不计。由于货架的结构限制，货格位置处穿梭车无法在y方向上行走。已知待入库的货物信息如表3所示。

表2 密集型仓库数据Table 2 Dense storage data

表3 待入库货物信息Table 3 Inbound cargo information

根据已知的仓库数据，可整理得到货位的数据信息，如图5所示。

图5 货位信息Fig.5 Location information

为便于分析和验证算法结果，将货位信息可视化。如图6（a）所示，将连通的货位划分为同一货道。在单个货道内所需入库时间最长的货位为货道最深处，即图6（b）中单个货道中颜色最深的货位。

图6 货位信息可视化Fig.6 Visualization of cargo location information

为验证和分析各个目标函数的优化效果，首先分别将各目标函数在Python中进行仿真。分别仅考虑第一、二、三目标函数，得到的货位分配结果如图7～图9 所示。其中用颜色深浅表示货物周转率、质量大小，货位颜色越深表示此处存放货物周转率越大或质量越大。

图7 第一目标函数的仿真结果Fig.7 Simulation results of first objective function

由图7（a）、图8（a）、图9（a）可见，各目标函数均在240 代左右收敛，函数值降低了大约20%。即在三次迭代中，货物分别按照周转率、质量大小有规则存放。分析具体货位分布方案得：在图7（b）中，根据第一目标函数的约束，货物按照周转率大小依次存放于离提升机较近的货位上，并且周转率较大的货物更靠近提升机；在图8（b）中，在第二目标函数的约束下，货物根据周转率大小在x、y、z方向上较均匀分布，不存在图7（b）、图9（b）中货物聚集的情况；在图9（c）中，质量较大的货物优先存放于低层货架，高层货架货位中更多为质量较轻的货物。综上，充分证明了目标函数及算法的有效性。

图8 第二目标函数的仿真结果Fig.8 Simulation results of second objective function

图9 第三目标函数的仿真结果Fig.9 Simulation results of third objective function

4.2 实验结果与分析

在上文验证各目标函数、算法可行性的基础上，针对表2数据的仓库，对表3中的货物分配货位。

根据公司对该目标的重视程度，采用层次分析法计算得到权重(α1,α2,α3)为（0.291，0.418，0.291），建立评价函数。为了对比算法的优越性，采用标准遗传算法GA、混合蛙跳算法SFLA 和改进的混合蛙跳算法SFLA-GA分别进行计算。算法参数如表4所示。

表4 算法参数Fig.4 Algorithm parameter table

运用所建立的密集仓储货位分配模型并结合GA、SFLA 及SFLA-GA 算法对该货位分配任务进行仿真求解，其算法迭代过程目标函数值变化如图10所示。

图10 算法迭代曲线Fig.10 Algorithm iteration curve

分析图10、表5，随着迭代次数的增加，目标函数不断变化，SFLA-GA算法在300代左右达到最优。并且相比于GA、SFLA，SFLA-GA 迭代效果显著，说明其更逼近最优解，足以证明SFLA-GA算法的有效性和优越性。

表5 算法结果数据对比Table 5 Algorithm resultcomparison table

图11 为最终的货位分配方案，在多目标函数的约束下，周转率较大的货物优先存放于距提升机较近的货位中，沿货架x、y、z方向的周转率分布均衡，质量较大的货物更多地存放在底层货架上。进一步验证了SFLAGA在处理密集式仓储货位分配问题的有效性和优越性。

图11 改进的混合蛙跳算法的货位分配方案Fig.11 Location allocation of improved shuffles frog leaping algorithm

5 结束语

本文重点研究密集仓储下的货位分配问题，针对密集仓储的货位分布特点划分货道，在此基础上对仓库货位分配问题建立了多目标优化模型，分别采用改进的混合蛙跳算法、混合蛙跳算法和遗传算法进行了仿真求解。实验结果表明：

（1）所提优化算法能够响应密集仓储的货位分布特征，符合实际仓储作业需求。

（2）相比于混合蛙跳算法与遗传算法，所提算法具有更好的搜索速度和更优解。通过对混合蛙跳算法局部搜索策略的改进，提高了搜索得到新解的效率，提高了算法效率。

本文所提出的模型与算法可以有效解决四向穿梭车式密集仓储入库货位分配问题，但并没有考虑到出入库混批的复杂情况。在今后需进一步对出入库混批情形下的货位分配方法进行研究，算法性能也有待进一步提升。