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

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

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

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

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

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

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

xk=(a−1)dx+⌊a/2Bad mglyph: D:/2201fig/h20.jpg⋅Wx,   (1)yk=(b−1)dy+Wy,   (2)zk=(c−1)dz,   (3)xk=(a-1)dx+⌊a/2⋅Wx,   (1)yk=(b-1)dy+Wy,   (2)zk=(c-1)dz,   (3)

约束条件为

⎧⎩⎨⎪⎪1≤a≤Nx,1≤b≤Ny,1≤c≤Nz,   (4){1≤a≤Νx,1≤b≤Νy,1≤c≤Νz,   (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)相联系， 并进行组合优化.

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

f1(x,y,z)=∑i=1n(Pi⋅Ti),   (5)f1(x,y,z)=∑i=1n(Ρi⋅Τi),   (5)

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

Ti=(Tiy)2+(Tiz)2−−−−−−−−−−−−√,   (6)Tiy=yivy,   (7)Tiz=zivz,   (8)Τi=(Τiy)2+(Τiz)2,   (6)Τiy=yivy,   (7)Τiz=zivz,   (8)

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

f1(x,y,z)=∑i=1n[Pi⋅(yivy)2+(zivz)2−−−−−−−−−−−−−−√].   (9)f1(x,y,z)=∑i=1n[Ρi⋅(yivy)2+(zivz)2].   (9)

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

f2(x,y,z)=∑i=1n(Mi⋅zi⋅dz)∑i=1nMi,   (10)f2(x,y,z)=∑i=1n(Μi⋅zi⋅dz)∑i=1nΜi,   (10)

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

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

(xkm,ykm,zkm)=⎛⎝⎜⎜∑i=1nxkin,∑j=1nykjn,∑k=1nzkkn⎞⎠⎟⎟,   (11)(xkm,ykm,zkm)=(∑i=1nxkin,∑j=1nykjn,∑k=1nzkkn),   (11)

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

Xi=((xki,ykj,zkk)−(xkm,ykm,zkm)),   (12)fk=∑i=1n∥Xi∥2,   (13)f3=∑k=1kn∑i=1n∥Xi∥2,   (14)Xi=((xki,ykj,zkk)-(xkm,ykm,zkm)),   (12)fk=∑i=1n∥Xi∥2,   (13)f3=∑k=1kn∑i=1n∥Xi∥2,   (14)

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

f3(x,y,z)=∑k=1kn∑i=1n[(xki−xkm)2+(ykj−ykm)2+(zkk−zkm)2]1/2.   (15)f3(x,y,z)=∑k=1kn∑i=1n[(xki-xkm)2+(ykj-ykm)2+(zkk-zkm)2]1/2.   (15)

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

f(x,y,z)=f1(x,y,z)+f2(x,y,z)+f3(x,y,z).   (16)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)minf(x,y,z)=ω1f1(x,y,z)+ω2f2(x,y,z)+ω3f3(x,y,z),   (17)

约束目标为

{ω1+ω2+ω3=1,0≤ω1≤1, 0≤ω2≤1, 0≤ω3≤1.   (18){ω1+ω2+ω3=1,0≤ω1≤1, 0≤ω2≤1, 0≤ω3≤1.   (18)

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

编码是遗传算法的起点， 它影响后序所有步骤的计算. 当一个任务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)f(a,b,c)=m, m∈[1,Νz⋅102+Νy⋅10+Νx],  且m为整数.   (19)

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

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

mi=(ai1,ai2,⋯,ain)1n,   (20)mi=(ai1,ai2,⋯,ain)1n,   (20)

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

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

fit(aij)=11+f(aij),  1+f(aij)>0,   (21)fit(aij)=11+f(aij),  1+f(aij)>0,   (21)

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

fit(mi)=∑k=1nfit(aik).   (22)fit(mi)=∑k=1nfit(aik).   (22)

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

Pm=fit(mi)∑i=1mfit(mi),   (23)Ρm=fit(mi)∑i=1mfit(mi),   (23)

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

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

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

对Xg中的每条染色体， 都生成两个随机点位e和s, 类似于交叉时的操作， 对点位中所有编号进行倒序排列并重新写入原染色体， 计算当前的染色体适应度， 若fit(gi)<fit(gj), 则用gi代替gj, 相反则保留原染色体， 该过程即为爬山过程. 通过与新产生的解进行比较， 留下更适合的解， 将适应度函数得到的(m-r)个新染色体向量与Xbk组成Xck, 作为下一轮的Xbk:

Xck=⎛⎝⎜⎜⎜⎜⎜Xbkc(r+1)1⋮cm1⋯⋱⋯c(r+1)n⋮cmn⎞⎠⎟⎟⎟⎟⎟mn.   (25)Xck=(Xbkc(r+1)1⋯c(r+1)n⋮⋱⋮cm1⋯cmn)mn.   (25)

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

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

本文使用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为类别， 这里已用数字进行了实际含义的替换.

在目标函数(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, 在本问题上的寻优能力更强， 更易跳出局部最优.

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

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

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

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

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