基于两阶段狼群算法的自动化立体仓库作业集成优化

何 李 陶翼飞 罗俊斌 荀洪凯

1.昆明理工大学机电工程学院，昆明，650504 2.昆明昆船逻根机场系统有限公司，昆明，650236

0 引言

自动化立体仓库(automated storage/retrieval systems，AS/RS)具有空间利用率高、存储容量大、人工成本低等优点。影响AS/RS工作效率的关键点有货物的货位分配和出入库任务的作业调度。合适的货位分配和作业调度可以充分利用存储空间，缩短堆垛机作业时间和运行距离，从而降低成本。

针对AS/RS的货位分配优化问题，众多学者根据出入库频率[1]、货架稳定性[2]、货物相关性[3]、空间利用率[4]等优化目标构建多目标优化模型，提出许多改进式/混合式优化算法。张贵军等[5]提出一种精英多策略差分进化算法，该算法针对基本差分进化算法的变异操作，根据多个精英个体的信息选择变异策略指导变异，提高了算法的可靠性和效率；JIAO等[6]将多种群遗传算法用于归一化后的目标函数，结果表明该算法所得的各个目标函数值均优于简单加权遗传算法；蔡安江等[7]建立了适用于两端式同轨双车立体仓库的多目标货位优化模型，并提出了一种集成多目标生物地理优化算法用于求解。针对作业调度，研究人员将堆垛机的路径优化问题转化为类似的旅行商问题[8]，并使用各种启发式算法求解。AMIRHOSSEIN等[9]针对多载具AS/RS建立了一种0-1模糊数学规划模型，并使用遗传算法求解；蔡安江等[10]针对两端式自动化立体仓库，建立了考虑货物出入库台分配的堆垛机调度模型，并运用漩涡搜索算法求取最优解。

AS/RS在实际运行中，不同的货位分配与作业调度组合会导致不同的运行结果，单独对某个部分进行优化只能起到部分优化的作用。为更好地提高优化效果，缩短AS/RS的运行时间，开展针对货位分配与作业调度的集成优化研究十分必要。CHEN等[11]以单载具AS/RS最短作业时间为优化目标，先后利用有向连接图优化储位分配，利用禁忌搜索算法优化堆垛机作业路径，但这在本质上仍是分开优化。杨朋等[12]以多载具AS/RS一次指令周期耗时最短为研究目标，设计了两阶段禁忌搜索算法用于求解，货位分配与作业调度两阶段能以反馈的方式相互影响，但其研究只针对多载具堆垛机一次行程所消耗时间，并未考虑对后续任务的影响。杨玮等[13]在此基础上，按照先到先服务规则对任务进行指令分组，提出一种双层遗传算法同时优化指令分组后的货位分配和子行程作业调度。汤洪涛等[14]在优化单载具AS/RS拣选作业时间时考虑空闲时间移库的操作，提出一种基于K-中心点聚类的粒子群优化算法。移库不仅能够缩短作业时间，还能将待出库货位直接空出作为备选入库货位，但这只适用于特定的立体仓库。

综上可知，尽管已有学者对AS/RS集成优化进行了研究，但缺少对单载具AS/RS通用作业集成优化模型的研究，因此，本文针对单载具AS/RS的一系列出入库任务，同时对入库任务的货位分配和出库任务的作业调度进行决策、建立集成优化模型，采用货架预分区策略使货物分区分类存储，缩短算法的运算时间，并提出一种两阶段狼群算法用于模型求解。

1 问题描述

自动化立体仓库的作业集成优化是指同时对货位分配与作业调度进行优化，达到作业时间最短、作业效率最高的效果。本文的研究对象为单载具堆垛机自动化立体仓库，该立体仓库会根据接收的出入库任务形成单指令(single command，SC)作业和双指令(dual command，DC)作业两种运行方式。对于一系列入库任务和出库任务，不同的安排会导致不同的作业效率。因此，在货架现有货位状态下，本文针对入库任务的货位选择问题，以及出库任务的出库顺序问题进行集成优化，使得在整个指令序列下的堆垛机作业时间最短。

1.1 基本假设

为便于研究，针对问题作如下假设：研究对象为单巷道、单载具堆垛机立体仓库；出入库任务针对巷道左右的两排货架；所有货位尺寸相同且只存放一个货物；巷道出入库台在同一侧；堆垛机初始位置在巷道出入库台；堆垛机运行加速度恒定；堆垛机货叉装/卸货时间恒定；入库任务采用先到先服务规则，出库任务顺序可调。

1.2 货架预分区

以往对AS/RS货位分配的研究通常考虑货物出入库频率、货物质量等影响因素，虽能对AS/RS作业效率和货架稳定性进行一定的优化，但研究大多基于货架初始状态全为空的静态条件，实用性不高。对入库任务进行动态货位分配具有较高的实用性，但当货架容量较大时，较多的备选货位会使算法计算时间大大延长。因此本文在进行动态货位分配之前，考虑货物的出入库频率及货物质量，使用多色集合理论对货架进行分区[15]。对货架上的货物进行分区分类存储，不仅使货物的存放有条不紊，便于管理，而且能减少入库任务备选货位的选择项，缩小可行解空间，提高运算效率。

传统集合论用于各种系统仿真，但在对生产系统、工艺过程等复杂离散事件系统进行仿真时，不能描述集合及其元素的性质，导致其应用受限。多色集合理论[16]应用矩阵论、模糊数学等对传统集合论进行改进，建立了标准的数学模型，可仿真不同对象，使得仿真系统更具柔性，且其基本成分是布尔矩阵，易于计算机编程实现。

(1)

(2)

针对本文所研究的单巷道立体仓库，以10列10层的单侧货架为例进行货架分区说明。该立体仓库出入库的货物共4类，每类货物的出入库频率(货物出入库任务数量占总任务数量的比例)和质量如表1所示，按货物类别将货架分为4个区域。为建立立体仓库货位分区的数学模型，将各货位视为元素ai，则货位编号可视为多色集合的统一颜色；将货位特征(层数、列数)、货物的出入库频率和货物的质量设为设计元素，组成布尔围道矩阵，见表2。

表1 货物特征表

表2 货架分区围道布尔矩阵

集合A由货架中100个货位组成，即A={a1，…，ai，…，a100}，其中，i=10(y-1)+x，x、y分别对应货位所在的列数和层数。F1～F12组成设计元素F(A)，表示货位ai的性质，其中，F1表示货物出入库频率大于30%，F2表示货物出入库频率位于10%～30%，F3表示货物出入库频率位于10%以下，F4表示货物出入库质量大于600 kg，F5表示质量为200～600 kg，F6表示质量小于200 kg，F7表示位于货架1～4层，F8表示位于货架5～8层，F9表示位于货架9～10层，F10表示位于货架1～4列，F11表示位于货架5～8列，F12表示位于货架9～10列。F(ai)表示元素ai的个人着色，例如一层一列的货位a1，F(a1)=(F1，F4，F7，F10)，用布尔矢量表示为F(a1)=(1，0，0，1，0，0，1，0，0，1，0，0)。对于每个元素ai，将对应的布尔矢量中的0和1分别用空格和“●”代替填入表2所示的围道布尔矩阵中，则该表从整体上表现了货位与货位特征、货物出入库频率和货物质量之间的关系。根据表2所示的布尔围道矩阵，将上述单侧10行10列货架分为区域Ⅰ、Ⅱ、Ⅲ、Ⅳ，分别存放A、B、C、D这4类货物。如图1所示，对单巷道立体仓库左右两排货架进行区域划分，以此作为入库任务货位分配的前提。

图1 货架分区示意图

2 作业集成优化模型构建

本文的研究对象为单巷道立体仓库，用(x，y，z)表示货位坐标，其中，x为货位列数，y为货位层数，z为货位排数，由于研究的是单巷道，所以z为1或2。堆垛机在巷道内进行水平和垂直的运动即可完成左右两排货架的出入库任务，因此在计算堆垛机运行时间时可只考虑坐标(x，y)，取堆垛机出入库台I坐标为(0，1)。

在考虑堆垛机加速度的情况下，堆垛机从点(xa，ya)运行到点(xb，yb)的运行时间Ta，b=max(tc，tr)，其中，tc为水平方向运动时间，tr为垂直方向运动时间，它们的求解公式分别为

(3)

(4)

其中，l为单个货位宽度；h为单个货位高度；vc为堆垛机水平方向最大速度；ac为堆垛机水平加速度；vr为堆垛机垂直方向最大速度；ar为堆垛机垂直加速度。由此，可以得出堆垛机完成第i个双指令作业任务的时间：

Yi，qTq，I)+4tsc

(5)

堆垛机完成第i个单指令作业任务的时间：

(6)

式中，SL为备选入库货位集合，由空货位与取货货位组成；RL为取货货位集合；m为入库任务数量；n为出库任务数量；Xi，p为0-1变量，第i个入库指令选择备选货位p为目的地址，Xi，p取1，否则取0；Yi，q为0-1变量，第i个出库指令选择货位q为源地址，Yi，q取1，否则取0；TI，p为堆垛机从巷道出入库台I到入库货位p的时间；Tq，I为堆垛机从出库货位q到巷道出入库台I的时间；Tp，q为堆垛机从入库货位p到出库货位q的时间；tsc为堆垛机货叉装/卸一次货物所用时间。

对于一批出入库任务，取P1=max(m，n)，P2=min(m，n)，则这批出入库任务可拆解为P2个双指令作业和P1-P2个单指令作业。由此，本文建立的数学模型如下：

(7)

(8)

(9)

(10)

式(8)确保分配一个空货位给入库的货物，式(9)确保每个空货位只能存储一个货物，式(10)确保每个取货货位都有出库任务。

3 算法描述

狼群算法(wolf pack algorithm，WPA)[17]模拟狼群分工协作的狩猎过程，效仿游走、召唤和围攻三种智能行为，以“胜者为王”“强者生存”两种生成机制对狼群进行更新，能以较大概率搜索到问题的更优解，具有较好的寻优性能。为实现针对货位分配和作业调度问题的集成优化，本文提出基于集成分层优化思想的两阶段狼群算法，在不同优化层之间对所得的最优解进行及时反馈，从而获取集成优化问题的最优解。

算法的基本思想是：首先根据出入库订单和初始货位状态分配初始货位，安排1个符合逻辑的进出库任务；算法第一层是作业调度层，通过狼群算法对出库任务进行合理的安排，生成最优作业调度；将第一层所得的最优解作为约束条件并使用狼群算法来优化货位分配，完成一个循环；然后将上一循环的货位分配结果反馈到作业调度层，构成闭环，开始下一循环。算法流程如图2所示。由于编码方式不同，因此下文将从作业调度、货位分配两个阶段，详细描述算法的关键步骤。

图2 两阶段狼群算法流程

3.1 作业调度阶段

此阶段采用整数编码，编码长度等于出库任务个数n。将1、2、…、n随机排列产生初始狼群，根据编码的排序安排出库顺序，1个编码个体代表1个可行的作业调度方案。根据式(7)计算初始狼群个体的适应度，选择适应度最小的个体作为头狼，记其适应度为Ylead，将除头狼之外的Ns个适应度最小的个体作为探狼，将剩余个体作为猛狼。

3.1.2游走

探狼在解空间中搜索猎物。计算探狼i的目标适应度Yi，若Yi

3.1.3召唤

头狼召唤所有猛狼向头狼所在位置迅速靠拢，猛狼快速向头狼位置奔袭，即在头狼的编码中随机选取长度为Sb的一段，来替换猛狼编码中与该编码段的起始或末尾编码相同且长度也为Sb的编码段，并更新猛狼编码。如图3所示，假设Sb=3，随机选取的头狼编码段为[4，5，6]，该编码段的起始编码与猛狼奔袭前的第5个编码相同，因此在执行召唤操作时需将猛狼编码中的[4，1，2]替换为[4，5，6]，并根据位置映射关系5→1、6→2对其他冲突位置的编码进行调整。根据奔袭规则，猛狼编码中“1”和“2”分别被替换成“5”和“6”。为避免重复，根据映射关系，猛狼编码中原来的“5”和“6”被映射替换成“1”和“2”。这种调整方式保留了猛狼大部分的编码，将猛狼的部分编码段替换为头狼对应位置的编码段，体现了头狼对个体的指导作用。奔袭途中，若Yi

图3 猛狼奔袭过程

3.1.4围攻

奔袭之后的狼群距离头狼较近，因此，可将头狼位置视为猎物所在位置，头狼指挥探狼和猛狼对猎物进行围攻，即视探狼和猛狼为围攻狼，保留围攻狼编码中与头狼相同编码位的相同编码，对围攻狼编码中与头狼相同编码位的不同编码进行随机变换，使之符合编码要求。

回到家里，紫云拿出那个黑色公文包，里面有一张调令文书。所有的手续都办好了，新的工作单位是华夏出版社。她把房子卖了，带着儿子，到上海去了。

3.2 货位分配阶段

3.2.1编码和初始化种群

货位分配的目的是根据货架当前状态为入库货物选择合适的货位，提高作业效率。本文研究的是动态货位分配，货物根据分区约束在相应的区域随机选择合适的货位。为避免将一些较好的货位闲置，影响作业的效率，因此将出库货位重新设为入库任务的存储货位。货位分配阶段的编码由两层构成，上层为备选货位层，由当前货架空货位号和取货货位号组成。货位编号采用自然数编码，水平方向按照从出/入库台一侧至立库另一侧的顺序依次递增，垂直方向按照货架层级由低到高的顺序依次递增。下层采用0-1编码，决定对应的上层货位能否作为入库货位。如图4所示，以10层10列货架为例，因本文研究对象为单巷道左右两排货架，故上层编码的选择范围是1～200。根据货架分区情况对上层进行划分，分区编码按从小到大顺序排列，满足货物依次从低层货位向高层货位存放的原则，保证货架的稳定性。下层编码为“1”的货位为被选中的存货货位。如图4所示，下层编码为“1”的位置对应上层货位即选取的入库货位，如上层编码为2、134、16、26等的货位。根据入库任务，在编码第二层相应区域内随机分配“0”“1”(共计m个“1”)，产生初始狼群，并计算适应度，选择头狼、探狼和猛狼。后续的编码变换中，上层的编码不会改变，下文所述编码操作只针对下层编码。由于货位分配阶段的编码方式有别于3.1节的作业调度阶段的编码方式，因此，货位分配阶段的游走、召唤和围攻操作也有别于作业调度阶段，下文将进行详细描述。

图4 货位分配编码示例

3.2.2游走

计算探狼i的目标适应度Yi，若Yi

3.2.3召唤

头狼召唤所有猛狼向头狼迅速靠拢，猛狼快速向头狼位置奔袭。奔袭途中，若Yi

3.2.4围攻

奔袭之后的狼群距离头狼较近，因此，可将头狼位置视为猎物所在位置，指挥探狼和猛狼对猎物进行围攻。若头狼与围攻狼相同编码位的编码均为“1”，则保留围攻狼当前编码位的编码；否则，将相同编码位的编码“1”随机变换至其他编码位上，并使之符合编码要求。

3.3 方案可行性判断

本文研究的动态货位分配问题将货物出库后闲置货位重新考虑为入库任务的存储货位，所以一个符合逻辑的进出库指令安排需保证同一货位对应的出库任务在入库任务执行之前完成。在算法运行过程中，并非所有编码个体都能满足上述要求，因此每个编码个体在进行适应度计算之前都需进行可行性判断。把判断之后可行的编码个体按照式(7)计算适应度，将不可行的编码个体对应的适应度设置为相对较大值，以避免不可行解的出现，导致计算错误。

3.4 算法终止条件

算法经过一次作业调度阶段和一次货位分配阶段后完成一次完整迭代。判断算法当前迭代次数是否大于设置的最大迭代次数Gmax：若是，则算法终止；否则，将当前最优解个体进行保留，并反馈给作业调度层开始新一次循环。

4 实验与分析

4.1 仿真实验设计

以10列10层、单巷道左右两排货架为研究对象，每侧货架都被分为4个区域。相邻货位水平方向间距l=2.5 m，垂直方向间距h=1.2 m，堆垛机水平方向的最大速度vc=1.0 m/s，加速度ac=0.4 m/s2，垂直方向的最大速度vr=0.5 m/s，加速度ar=0.5 m/s2，堆垛机货叉装/卸一次货物所用时间tsc=5 s。

算例采取随机生成的方式：随机在单巷道左右两排货架上各生成60个货物(已在库中货物)。AS/RS中，单载具堆垛机全程采取双指令周期作业，即令出库指令数量n等于入库指令数量m。选择20、40、60三种入库规模，四类货物A～D的入库数量相同，并从在库货物中随机选择同等数量的货物出库。仿真实验中，各算例运算10次，结果取平均值。

本文仿真优化模型的建立均在Plant Simulation 15.0软件中完成，通过HBW(high bay warehouse)模块可实现一组出入库订单的完整运行，同时也能验证当前作业安排是否符合实际工况，采用Simtalk语言编写优化算法，仿真实验在Inter i5-9300H CPU主服务器构建的分布式仿真优化环境上运行。

为证明本文算法的适用性和优越性，除将两阶段狼群算法用于AS/RS集成作业，还分别应用狼群算法、禁忌搜索(tabu search，TS)[12]算法、遗传算法(genetic algorithm，GA)[13]、粒子群优化(particle swarm optimization，PSO)[14]算法对所述问题进行优化。为验证集成优化的优越性，对货位分配和作业调度的分开优化与集成优化进行仿真比较。各算法的最大迭代次数Gmax都取500。在货位分配阶段和作业调度阶段结束时分别记录结果，故每次运算所得最终结果记录数G为2Gmax。

4.2 算法参数选择

算法参数的选择会对优化问题的结果产生一定的影响。为在相同条件下进行不同算法的对比仿真实验，设计正交试验获取不同算法的参数。下面以狼群算法为例进行说明：对种群大小Npop、判断距离dnear、探狼召唤阶段步长Sb、游走最大次数Tmax设计L9(34)正交试验(每个因素有3个水平)，共计9个试验组合。通过查阅大量狼群算法相关文献，选择常用参数值作为本文正交试验的参数值。文献[17-18]中的种群规模为50和100，因此选择种群规模为50、80、100；文献[18-19]中的游走最大次数为10和15，因此选择游走最大次数5、10、15；判断距离dnear、探狼召唤阶段步长Sb都与编码长度n相关，根据现有文献，选定dnear为2n/5、n/2、3n/5，Sb为n/5、n/4、3n/10。确定狼群算法参数的正交试验选择订单规模n=20，探狼数量Ns=Npop/2。每种实验组合单独运行10次并取平均值，所得结果如表3所示。

表3 正交试验结果

由实验结果可知，组合8的结果最优，故后续实验中，不同订单规模n的狼群算法均采用以下参数：狼群大小Npop=100，召唤阶段dnear=n/2，步长Sb=n/4，探狼最大游走次数Tmax=10。

同理，对TS算法、GA、PSO算法的参数采取相同的方式设计正交试验，由于篇幅有限，仅在表4中列出以上算法最终确定的关键参数。

表4 对比算法参数选择

4.3 结果分析

表5给出了3种订单规模下，双指令周期作业使用两阶段狼群算法集成优化所得结果。从实验结果看，与初代最优解相比，优化后的作业时间都显著缩短，不同订单规模下的作业时间缩短约15%；随着订单规模的增大，算法计算时间也稍微延长，但变化幅度不大，不影响AS/RS实际应用场景下的决策。

表5 两阶段狼群算法优化结果

双指令周期作业使用狼群算法进行集成优化和分开优化的过程如图5所示。从实验结果来看，不同订单规模下，集成优化下的狼群算法基本能在750次内搜索到对应问题的最优解，且算法的求解性能不受订单规模改变的影响，具有良好的鲁棒性；在相同订单规模情况下，狼群算法集成优化所得结果更好。

(a)20对指令

图6所示为对比算法求解的寻优过程。3个订单规模下，使用各算法进行分开和集成优化后的实验结果如表6所示。由表6可知：相同算法下，集成优化与分开优化的计算时间接近，但集成优化较分开优化有明显提高，且改进量随订单规模的增大而增大。这是因为在使用同种算法时，分开优化和集成优化的算法复杂度是相近的，而集成优化不仅能将作业调度层生成的出库指令顺序传递到货位分配层，货位分配层也能将所得到的入库货物存储位置反馈给作业调度层，从而形成一个闭环。此外，在相同的情况下，WPA所得结果比TS算法、GA、PSO算法所得结果更优。算法运行时间上，WPA所用时间略长于TS算法、GA、PSO算法，其原因在于算法中狼群的游走、召唤、围攻操作虽然具有更好的寻优能力，但增加了算法的复杂度。尽管如此，从算法最终寻优效果的角度进行分析，WPA运行所增加的时间较短，即WPA能以增加较短的运算时间为代价换来更好的寻优效果。以上实验结果分析证明了两阶段狼群算法在求解AS/RS作业集成优化问题上的有效性和实用性。

(a)TS算法 (b)GA算法 (c)PSO算法

表6 不同优化方法的结果比较

5 结语

本文研究的AS/RS作业集成优化问题立足于自动化立体仓库运行的实时性，提出的求解算法能对同时存在的出入库任务进行合理安排。本文提出两阶段狼群算法通过对基本狼群算法中的游走、召唤和围攻机制的重新设计，实现了算法在较优解附近的精细搜索，具备的随机性搜索能力避免了在寻优过程中陷入局部最优。将货位分配和作业调度进行集成优化，求解过程体现了两优化问题之间的关联和反馈。实验结果表明，两阶段狼群算法在不同的订单规模下均能得出满意解，且求解性能不受订单规模变化的影响，体现了算法的鲁棒性。对比实验表明：两阶段狼群算法所得结果相对更优，与初代最优解相比，作业时间缩短约15%。