自动化立体仓库具有高层货架存储、自动货物存取和计算机管理等优点, 已经成为物流系统的重要组成部分, 被应用于机械、汽车、烟草、交通运输、医药等众多行业领域。

高层货架和堆垛机 (堆垛起重机) 是自动化立体仓库的重要组成部分, 其中货物的出入库作业主要由堆垛机按照拣选作业指令来完成, 堆垛机的拣选作业调度直接影响着自动化立体仓库的作业效率。因此, 自动化立体仓库的拣选作业优化问题也成为自动化仓库的一个关键技术组成部分[1]。

自动化拣选作业调度问题主要是针对多个拣选货位点进行拣选路径的优化, 当拣选货位点数量增加时, 拣选作业路径优化问题的规模和求解难度也逐渐增加, 其具有典型的NP-hard问题特性。因此, 不少学者采用启发式算法[2]、遗传算法[3]、蚁群算法[4]、人工鱼群算法[5]和粒子群算法[6]等求解自动化仓库的拣选作业调度问题, 也取得了较好的优化效果。

演化策略算法 (Evolutionary Strategy, 简称ES) , 也称为进化策略算法, 和遗传算法一样, 也是进化算法的一个分支。与遗传算法相比, 演化策略算法更注重“优胜劣汰, 适者生存”的选择策略, 并且演化策略算法直接在问题解空间进行操作和实现, 其个体表示方式与遗传算法也存在差异[7]。由于演化策略算法与遗传算法存在一定的相似性, 从而使得演化策略算法的应用没有遗传算法那样得到广泛应用。因此, 本文将演化策略算法用于求解自动化仓库的拣选作业优化问题, 在对自动化仓库拣选作业问题进行建模的基础上, 并对演化策略算法的个体编码、重组算子、变异算子进行了设计。

自动化仓库拣选作业问题可以描述为:设有n个拣选任务, 即有n个货位点等待堆垛机进行拣选作业, 堆垛机从出入库台处出发, 分别到达高层货架中的n个不同货位点, 并且每个货位点只去一次, 最后返回出入库台处, 拣选作业的目标是堆垛机的总运行时间最少。

对于高层货架的不同货位点位置用 (列, 层) 表示, 对于第i列第j层的货位点可以表示为 (i, j) 。定义整个货架的高度为H, 长度为L, 出入库台处的坐标位置为 (0, 0) , 如果设定整个货架有r列, l层, 那么, 货位点k (a, b) (k=1, 2, …, n) 的坐标位置可以定义为 (xk, yk) , 即有

这里假设堆垛机在水平方向和垂直方向的工作速度为恒定的, 令vx表示水平运行速度, vy表示垂直运行速度, 那么, 就可以计算出拣选作业过程中相邻两个货位点k (a, b) 和k+1 (c, d) 之间的运行时间, 即水平方向运行时间tkx和垂直方向运行时间tky分别如公式 (3) 和 (4) 所示。

相邻两个货位点之间的运行时间tk是取其水平方向运行时间tx和垂直方向运行时间ty之间的最大者, 即有

于是, 可以得到n个货位点拣选作业的总运行时间T为

其中, t0表示从出入库台处到第一个货位点的时间, tn表示从最后一个货位点返回到出入库台处的时间, tw表示所有货位点的拣选作业总时间, wk为每个货位点的拣选作业时间, (x1, y1) 和 (xn, yn) 分别表示第一个货位点和最后一个货位点的坐标位置。因此, 自动化仓库拣选作业优化的目标可以表示为:

演化策略算法主要包含选择策略、重组算子和变异算子, 其中根据选择策略的不同形成了 (1+1) 、 (μ+1) 、 (μ+λ) 和 (μ, λ) 等几种选择策略。这里主要采用基于 (μ+λ) 选择策略的演化策略算法。在 (μ+λ) -ES进化策略中, 由μ个父体通过重组和变异产生λ个后代, 然后从μ个父代和λ各后代中选择μ各最好的个体作为下一代的父体。

针对自动化仓库拣选作业问题, 采用实数编码方式, 个体编码的长度为所有货位点的数量n, 个体编码如表1所示。

表1 个体编码  下载原图

表1 个体编码

表1中, xi由一组实数xij组成 (i表示演化策略种群中的第i个个体, j表示个体编码中的第j个基因位置, j=1, 2, …, n) 。初始化时, xij是随机产生的实数。

对表中xij的进行从大到小 (或者从小到大) 的排序, 就会得到n货位点的排序, 从而就可以得到自动化仓库拣选作业的货位点顺序, 进而根据公式 (6) 就可以计算对应的拣选作业时间。

重组算子是演化策略算法产生子代个体的重要步骤, 这里采用三点交叉重组算子。

三点交叉重组算子是在个体编码中选择3个交叉位置, 然后采用隔段交叉的方法进行互换。以表2和表3的父代个体为例, 假设选择的交叉位置分别为j1=3, j2=5和j3=8, 于是将个体编码分割为4段编码串。以表2的父代个体3为例, 分割后的4段编码串分别是S1= (1.2, 0.8) , S2= (3.3, 1.7, 2.3) , S3= (3.4, 4.2) 和S4= (5.7, 2.1) 。交叉重组时采用隔段交叉的方法, 即将两个父代个体的S2和S4编码串进行交叉互换, 如表2和表3中的阴影部分。交叉后的子代个体如表4和表5所示。

表2 父代个体1  下载原图

表2 父代个体1

表3 父代个体2  下载原图

表3 父代个体2

表4 子代个体1  下载原图

表4 子代个体1

表5 子代个体2  下载原图

表5 子代个体2

在生成的子代个体中, 变异算子采用针对个体编码基因值进行随机更新的方法, 即随机选择个体编码第二维xi中一个基因值, 用随机生成的一个新的实数代替原先的xi (可以重复多次选择不同的基因值, 这里采用重复替换次数为2次) 。例如, 对于表4的子代个体1, 假设选择第5个工件操作所对应的x5, 替换前x5=2.5, 假设随机生成的实数为4.1, 那么替换后的子代个体1为如表6所示。

表6 变异后的子代个体1  下载原图

表6 变异后的子代个体1

设定整个货架的长度为60m, 高度为9m, 整个货架有30列, 6层, 堆垛机的水平运行速度vx为1m/s, 垂直运行速度vy为0.2m/s, 每个货位点的拣选作业时间均设定为5s, 随机生成10个货位点和20个货位点的数据, 如表7和表8所示。

为了比较分析, 这里同时采用粒子群算法对上述算例进行优化计算。其中, 演化策略算法中, 父代种群数量μ=40, 子代种群数量λ=30。粒子群算法的种群数量为40, 采用惯性权重线性递减粒子群模型。两种算法的迭代次数均为600次, 每个算例每种算法均独立运行20次, 计算结果如表9所示。

表7 随机产生的10个货位点  下载原图

表7 随机产生的10个货位点

表8 随机产生的20个货位点  下载原图

表8 随机产生的20个货位点

表9 计算结果  下载原图

单位:秒

表9 计算结果

从表9的计算结果看, 对于10个货位点, 本文所采用的演化策略算法的计算结果和计算稳定性均好于粒子群算法, 找到最小作业时间为187s, 对应的货位点拣选作业次序为 (用0表示出入库台处) :0→3→6→2→7→8→10→5→4→9→1→0, 或者

0→1→4→5→8→9→7→2→6→3→10→0。

对于20个货位点, 演化策略算法的计算结果页好于粒子群算法, 演化策略算法找到的最小作业时间为216s, 对应的或喂点拣选作业次序为:

0→1→5→12→11→2→15→16→8→18→4→6→19→20→17→7→3→13→10→9→14→0。

本文采用 (μ+λ) 演化策略算法对自动化仓库拣选作业优化问题进行了研究, 在对个体编码、重组算子和变异算子进行设计的基础上, 针对随机生成的不同算例进行了测试计算, 并与粒子群算法进行了比较分析。从计算结果看, 本文所设计的演化策略算法具有较好优化效果, 对于小规模算例, 算法的优化结果和稳定性好。对于较大规模算例, 算法也能找到比较好的计算结果。