基于多种群空间映射遗传算法的立体仓库储位优化

隋 振, 张天星, 吴 涛, 陈华锐

(吉林大学 通信工程学院, 长春 130012)

货物在流通过程中, 会有大量的库存积压, 从而产生储位分配模式混乱的问题, 对囤积的货物进行合理的摆放是物流业中的重要环节. 一旦仓储环节存在问题, 则后续的生产和流通都将无法对接, 运输系统将发生混乱.

目前, 对储位优化问题已有大量研究, 在系统模型方面, Park等[1]提出了物品关联度的数学模型, 并设计了一种启发式算法, 再结合传统遗传算法解决问题； Muppani等[2]用物品的临界值指数(COI)值作为检测货物摆放优劣的一种指标； 李小笠等[3]改进了货位分配模型, 加入了货物分区的概念； 蔡安江等[4]不仅研究了分离式仓库优化问题, 还对堆垛机的调度方案进行了探究, 将其视为一个旅行商问题； 张鹏[5]对仓储系统用Flexsim设计了一种仿真软件, 上述几种不同的改进方法, 都将储位优化问题引入到约束条件中, 使数学模型更复杂.

对于优化算法的研究, Poulos等[6]选择遗传算法解决此问题, 用交叉算子的方法改进了原有算法, 最终得到较好的结果, 也证明了启发式算法对组合优化问题有较大帮助； Deng[7]也通过遗传算法进行寻优, 计算涉及到3个实际的优化方向, 进一步靠近工业领域； 李鹏飞等[8]提出了一种病毒协同遗传算法, 解决了多目标优化模型； 焦玉玲等[9]也对传统遗传算法进行了改进. 算法的不断更新使求解的效率逐步提升. 但针对不同类型的仓库, 当存取任务不断改变时, 储位分配的方式也应随着变化的需求进行相应地调整. 在算法方面, 多数启发式算法在寻优过程中易陷入局部最优, 性能还可以提升.

为解决上述问题, 本文构建一个带权重的多目标组合优化模型, 同时提出一种改进的遗传算法, 从编码方式、 种群构成和交叉算子等方面对储位分配问题进行改进, 使其具有较强的针对性, 仿真实验结果表明, 该算法易跳出局部最优, 寻优能力更好, 并分析了算法的适用范围.

1 模型构建

1.1 运行环境及优化目标的选择

本文以分离式货架结构为系统的运行环境, 如图1和图2所示, 其中z轴为仓库高度,y轴为仓库行数,x轴为仓库列数, 每个货格H都有一个静态坐标(a,b,c)与其对应, 对于单个货格, 其长、 宽、 高分别用dx,dy,dz表示,Wx为巷道宽度,Wy为起始宽度,x轴方向上所有y=0的点皆为入库起点.

若用静态坐标(a,b,c)找到实际空间位置, 即动态坐标(xk,yk,zk), 有如下变换公式：

约束条件为

(4)

其中Nx,Ny,Nz分别表示货架的总列数、 总行数和总层数, 使用约束条件一是为避免因为忽略了巷道宽度对实际距离的影响, 二是为可在随意更改Wx和Wy的条件下不用修改(a,b,c), 降低了重复计算次数, 为后续算法计算和仿真实验奠定基础.

在实际运行过程中, 有任务T={S1,S2,…,Sn}, 其中S1,S2,…,Sn为货物, 每个货物Si都有下属信息{P,M,K},P为货物周转率,M为货物质量,K为货物类别.储位分配方式应满足以下要求： 周转率大的货物更靠近出口, 货架的整体重心要尽可能低, 尽量缩短同类物品的摆放距离[10].因此, 本文根据P,M,K分别构建相应的目标函数, 使其与动态坐标(xk,yk,zk)相联系, 并进行组合优化.

1.2 效率最优模型构建

周转率也可表示为货物出入库的频率, 需要多次进出库的物品离仓库入口的距离应尽可能小, 这样会缩短拣选时间, 达到提高分拣速度和效率的要求, 建模方案为

(5)

其中：n为本次任务中入库货物的总数量；Pi为第i个物品的周转率；Ti为存货时间,

(6)

(7)

(8)

式中Tiy,Tiz分别表示y轴和z轴方向所需的时间,vy,vz分别表示提升机在y轴和z轴所需的速度, 由于该模型的x轴为入口, 所以不考虑该方向时间, 其中坐标yi,zi的值是经过式(2),(3)变换后的值, 故通过式(6)～(8)可得最终的周转率模型为

(9)

1.3 稳定性模型构建

货物在货架的摆放过程中, 如果总质量分配不合理, 即重心过于偏向某一侧, 会导致货架倾覆, 因此一个稳定的货架可保证流通的安全性, 因此该目标函数设计为

(10)

其中Mi为第i个货物的质量, 单位为kg.求式(10)最小值的目的是使货架结构在垂直方向(z轴)上达到稳定, 即z轴方向数值较大,f2值越大, 货物的整体重心越高.

1.4 离散程度模型构建

在处理任务时, 通常是同类物品一起出现, 因此缩短彼此的距离可减少堆垛机反复调度的时间.物品中心坐标的计算方法为

(11)

其中(xkm,ykm,zkm)为第k类物品的中心坐标.则物品相对于该点的距离可表示为

Xi=((xki,ykj,zkk)-(xkm,ykm,zkm)),

(12)

(13)

(14)

其中fk为第k类货物的离散程度,Xi表示距离向量, ‖Xi‖2表示每个货物与中心坐标的距离差值,kn为类别总数, 由式(12)～(14)可知离散程度模型为

(15)

1.5 组合优化模型

在得到上述3个独立模型的基础上, 经过组合后得到的多目标函数将不再拥有单方向的最优解, 只能得到一个综合考虑后的可行最优解, 整合后的数学模型为

f(x,y,z)=f1(x,y,z)+f2(x,y,z)+f3(x,y,z).

(16)

若对3个目标有不同的需求, 可在每个独立函数前增加权重系数ω, 最终的优化模型为

minf(x,y,z)=ω1f1(x,y,z)+ω2f2(x,y,z)+ω3f3(x,y,z),

(17)

约束目标为

(18)

2 改进遗传算法寻优

遗传算法在解决组合优化问题上效果较好, 其模拟自然界的适者生存法则, 通过生成种群、 染色体的选择、 交叉、 变异等步骤, 逐代选择优秀个体, 直到满足终止条件[11].算法的优点是其可以给出多目标优化问题的可接受解, 但搜索速度较慢, 易陷入局部最优, 且编码过程繁琐, 因此本文提出空间映射编码, 多种群协同寻优, 最后结合爬山算法设计一种改进的遗传算法.

2.1 空间映射编码

图3 空间映射转换Fig.3 Space mapping transformation

编码是遗传算法的起点, 它影响后序所有步骤的计算.当一个任务T到来时, 其包含若干个待处理货物S1,S2,…,Sn, 每个货物Si在仓库模型中都有唯一的静态坐标(a,b,c)与其对应.假设货格总数为n, 则解集空间就是n个正整数序列, 每个正整数对应一个(a,b,c), 映射方式如图3所示.以z,y,x轴的顺序依次进行编码, 第一个坐标(1,1,1)的编号m=1, 编码步骤如下：

1)c+1,m+1, 直到c=Nz；

2)c=0,b+1, 返回步骤1), 直到b=Ny;

3)b=0,a+1, 返回步骤1), 直到a=Nx时, 编号结束.

对应关系为

f(a,b,c)=m,m∈[1,Nz·102+Ny·10+Nx], 且m为整数.

(19)

该编码方式将三维空间解集降为一维线性解集处理, 常规二进制编码较复杂, 且其在高维空间中易导致无效交换.例如(1,2,3)和(5,2,7), 这两个货位如果交换了y轴信息, 则其结果是无效的, 如图4所示.而对于空间映射编码, 用唯一整数去对应静态坐标, 避开了对自身内部信息进行交换的问题, 只存在整体交换, 且交换后不存在无效结果, 如图5所示.在整个算法流程中, 所有数据都将以编号的形式参与计算, 可读性更高.

2.2 初始种群的生成

若任务T中有n个待入库货物, 假设种群规模为m, 则初始种群是一个m×n的矩阵Xa=(m1,m2,…,mm)T,Xa中有m个行向量, 这样的向量称为一个染色体, 每个染色体中包含n个元素:

mi=(ai1,ai2,…,ain)1n,

(20)

其中aij为通过上述编码方式得到的货格编号.

2.3 适应度函数

由于本文所求是一个最小值, 所以单个货物的适应度函数为

(21)

其中fit(aij)的值越大, 越符合要求.对于一条染色体mi, 其适应度为

(22)

2.4 多种群协同寻优

通过fit(m)已经求得种群中每个染色体的适应度, 经过概率的归一化后, 进行优质子代的选择：

(23)

其中Pm为每条染色体被选择的概率, 通过保留概率PGA, 使得在原种群中, 有一定几率留下(m×PGA)个优秀个体.本次操作后, 得到的种群矩阵称为父类种群, 表示为Xb=(b1,b2,…,br)T.在父类种群Xb中, 由于概率选择导致存在多个相同的染色体, 染色体出现次数越高, 证明适应度越好, 通过选择机制筛选出了更适应问题的结果.

空间映射编码虽然减少了无效交换, 但由于不产生初始解集外的新解, 所以也更易陷入局部最优.为解决该问题, 在Xg生成时, 同时再生成k个父类种群Xbk=(bk1,bk2,…,bkr)T, 该过程相当于增大了种群规模, 在达成终止条件时, 选出k个种群中的最优解.剩下(m-r)个染色体由Xb中两两相邻的染色体进行交叉运算, 若满足交叉概率Pc,

(24)

图6 第k个/单个种群的进化演变方式Fig.6 Evolution mode of kth/single population

则进行交叉产生新的子代个体, 本文所用的交叉方式是随机生成两个整数e和s, 在染色体对应的位置上进行两两交换, 避开了产生不可行解的可能, 如图6所示.通过变异概率Pr, 对单个染色体的某个或几个位置在编号范围内进行更改, 变异的范围和产生的新值均为可行解, 组成待选种群Xg.

2.5 爬山算法

对Xg中的每条染色体, 都生成两个随机点位e和s, 类似于交叉时的操作, 对点位中所有编号进行倒序排列并重新写入原染色体, 计算当前的染色体适应度, 若fit(gi)

(25)

爬山算法属于局部范围内寻优, 本文只在邻域内搜索一次, 即fit(gi)与fit(gj)之间的比较, 在局部解中加强寻优效果, 再通过多种群并行求解的方式跳出局部最优, 二者结合使优势互补.

至此第一次子代生成结束, 同时产生了k个子代种群Xc, 其中每个都包含了r个父代染色体和(m-r)个经过交叉变异的优秀个体, 若未达到迭代次数要求, 则将Xck视为下一轮计算中的Xa, 每轮解集的单个种群更新过程如图6所示.解集的寻优可视为一种矩阵拼接过程, 其中虚线表示阈值r.重复上述过程, 若满足迭代次数, 则根据式(21)计算出适应度最高的一组解Xfin, 将该解作为最终结果.改进的遗传算法流程如图7所示.

图7 改进的遗传算法流程Fig.7 Flow chart of improved genetic algorithm

3 仿真实验与结果分析

3.1 实验参数设置

本文使用MATLAB2016a对改进的遗传算法进行仿真实验, 为验证模型和算法的有效性和稳定性, 将系统参数设定为： 巷道宽度和起点宽度分别为2 m和1 m, 仓库的容量为10×10×4, 共400个固定货格, 货格长度为1 m, 堆垛机在x轴和y轴的运行速度分别为1 m/s和0.6 m/s. 遗传算法的参数设为： 最大迭代次数为1 000, 种群规模为100, 交叉概率为0.8, 变异概率为0.2, 协同种群数量为10, 保留概率为0.2. 实验选用某图书类仓库的入库任务信息列于表1. 其中, No.为货物编号, 任务T中共有30个待入库货物, 容量S=30,P为周转率,M为质量,K为类别, 这里已用数字进行了实际含义的替换.

表1 入库任务信息

3.2 算例分析

3.2.1 算法有效性验证

在目标函数(17)中, 每个优化方向f1,f2,f3分别可作为验证模型优化程度的3个性能指标[9]. 对表1的数据分别用传统遗传算法(GA)和多种群空间映射/改进遗传算法(IGA)进行优化求解, 给出三维仿真结果和各项指标的数值. 图8为GA优化效果, 图9为IGA优化效果. 由图8和图9可见, 同颜色为同一类别, 可从物品的摆放位置直观看出IGA的排列更紧密有序. 表2为目标函数各项求解结果. 由表2可见, IGA的目标函数值为98.71, 相比于GA的结果降低27.61%, 各性能指标(出入库时间, 整体重心, 相关性距离和)结果都较优, 分别低于GA各项的35.71%,17.64%,27.94%, 验证了IGA的有效性, 相比于GA, 在本问题上的寻优能力更强, 更易跳出局部最优.

表2 目标函数各项求解结果

3.2.2 算法稳定性验证

由于遗传算法(启发式算法)每次求解的结果不唯一, 所以为避免出现特殊情况, 需要对算法的稳定性进行实验, 对上述入库任务进行20次优化求解, 每隔5次实验计算一次f的均值和标准差, 结果列于表3.

表3 两种算法在不同实验次数下的均值和标准差

由表3可见, 经过不同次数的实验, IGA的标准差增长率为15%～17%, 小于GA, 在完成20次实验后, IGA的均值小于GA 22.63%, 标准差小于GA 16.67%, 可证明IGA在处理本问题上没有过多的震荡, 有足够的稳定性.

3.2.3 算法对不同任务容量的处理能力分析

实验改变任务容量, 考察优化效率随任务容量S的变化情况.下面以S=10为间隔, 分别对不同容量进行分析讨论. 表4列出了不同任务容量下IGA较GA的各项指标提升程度.

表4 不同任务容量下IGA较GA的各项指标提升程度

由表4可见, 各项优化指标在IGA的优化下总体优于GA, 但IGA的优化能力随着S的提升, 逐渐变小, 这种情况当S=80时尤为显著. 在常规的立体库任务分配上, 通常一次任务的容量不超过总容量的10%, 如图10所示, 当容量比约达到17%时(S=65), 优化空间已经受限, 目标函数的优化过程不再过分依赖于不同算法.

图10 IGA优化能力随S的变化趋势Fig.10 Change trend of IGA optimization capability with S

综上所述, 本文对自动化立体仓库中的储位分配问题进行了研究, 为应对不同的生产需求, 通过建立组合优化函数实现了对货位的动态分配, 从而提高了物流运输效率. 在问题优化过程中, 本文提出了一种多种群空间映射遗传算法. 在算法对比实验和不同任务容量的处理实验中, 用三维视图、 指标数据和迭代曲线3个指标验证了该算法在常规运行时对货位分配的能力更好, 3个性能指标均优于传统方案, 但在任务量过大时, 优化能力会减弱.