本文提出的货位规划与路径规划协同优化算法的基本思路为,首先计算货品间的相似度,按照货架最大载货种类数对货品进行聚类操作,再计算聚类后各个类别间货品的相似度,之后再计算各个货架的最佳出库路径.利用计算完成的数据以及当前地图信息,使用改进的遗传算法计算出货架布局情况,也就是货架的摆放方式,从而完成货位布局和路径规划两者的共同优化.

图 3-2 货位规划与路径规划协同优化算法流程图

货位路径协同优化算法的具体流程如图 3-2 所示.首先,基于上文货品相似度算法的描述,使用余弦相似度算法将实验数据的货品间的相似度计算出来,并统计出库次数.然后结合相似度,依据货架的载货种类数,对当前货品进行分类,并且赋予每个分类属性.分类的出库频率为当前分类物品中出库频率最高的物品的出库频率,分类的出库批次为当前分类物品中出库频率数前 20%的货品出库批次总和.

举个例子,假设 1 至 10 号物品在一个分类中,此时若 1,4 号货品的出库频率最高,且 1,4 号货品的出库批次向量分别为[1, 0, 1, 1, 1, 0, 1, 0]和[1, 0, 1, 1, 1, 1, 1, 0],则该分类的出库批次向量为[1, 0, 1, 1, 1, 1, 1, 0].此时,一个分类有着货品的属性,且集成了更多的货品,将这个分类看作是一个未被放入货架位置的待入库货架,即将所有货品转化为待入库货架.

计算货架间的相似度,同样使用余弦相似度算法来进行计算.在计算出相似度后,对所有值减去 1 再取其绝对值,绝对值越小越相似.设定一个阈值∂,此时计算出的相似度一切小于∂的货架认定为是高相似度货架.高相似度货架会参与到适应值的计算中,∂过大会认定多数货架是都是相互相似的,算法会难以选出真正优秀的解.∂过小会导致选择不到足够的相似度货架,虽然算法可以给出一个它认为“优秀”的解.但在任务单来临时,可能仍旧会造成拥堵的状况,这也标志着算法的失败.本文仓储实际运维数据（200件货品,14个批次的数据）为数据样本对仓储数据进行实验,调整∂取值,观察了余弦值的取值规律,最终确选取 0.25 为本文提出的协同优化算法中∂的值.

货位路径协同优化的第二步为计算每个应摆放货架的位置.基于上文给出的路径规划算法,我们计算从该位置单独出货时的最佳出货路径.以获得每个可能摆放货架的位置其出库的最佳路径,即最快出库方式.在获取并记录了各个货架位置的最佳出库路径后,开始对货架位置进行综合运算.

货位路径协同优化算法的求解算法基于遗传算法设计,首先对遗传算法进行编码.根据需要解决的问题,需要把未入库的货架,摆放到货架位置上,需要计算的是货架如何入库的问题.在编码上选用排列编码即可.在排列上,选取货架位置作为空位,将未入库货架放入其中.例如[5,4,2,3,1],意为将5号未入库货架放入1号货架位,将4号未入库货架放入2号货架位以此类推.完成编码的选择和实现后即可以生成初始种群.初始种群的建立是生成一组随机数,随机数区间在未入库货架号区间范围内.具体实现为,先获取所有未入库的货架号放入集合A.再生成随机数,将其放入到个体的基因中记为集合B,此时该货架号从之前的集合A除去,防止再次选中,经过不断的生成,直到取完集合A中所有数.在随机生成的种群中,考虑个体重合问题,使用生成新的个体来替代重合个体,直到该种群中个体的数量满足设定的值.完成初始种群的生成后,计算该种群中个体的适应值.适应值fit计算方式如式3-9所示,系数f是该货架的出入库频率,此参数可以放大整体适应度,使出库频率影响到货架摆放位置.Bestpath为当前货架出库的最佳路径,参数∑i=1NRelatpathi为与所有当前货架相似度较高的货架的出库路径重合量的和,该参数可用来降低冲突发生的情况,将避免冲突考虑到货架排放中.α和β为权重系数,在满足α+β=1的约束下,调节两个参数间的权重比,基于后续实验调整,本文的α系数取值为 0.8,β系数取值为 0.2. 此外,根据适应度函数分析来看,适应度与该未入库货架的出库频率、最佳出库路径长度以及与其相关性高的其他货位路径冲突数成正相关.

完成适应度的计算,算法开始代数迭代.首先,使用锦标赛法选取算子,基于已计算出的适应度,在种群中随机挑选个体并比较适应度,适应度大的被淘汰,最终选择出一定量的个体进行交叉生成下一代.在基本的锦标赛基础上,本文加入了被选择系数以提高锦标赛选择算子的效率,有效消弱了为了减少劣质个体被多次比较从而导致选择出不优秀个体的情况发生.具体来说,我们为每个个体赋予一个被选择系数,其默认初值为1.一开始各个个体的被选择系数相等,开始选择使为每个个体生成区间为[0,1]的随机数,再用该随机数乘以被选择系数,最终获得的按从小到大顺序取进入锦标赛.一旦某一个体被淘汰,则减少它的被选择系数.

基于上述获得的算子,算法开始依次进行交叉和变异操作.交叉操作时,选取集合B中任意两个体,进行交叉操作.本文提出协同优化算法选用有序交叉方法进行交叉,将父代中的某一段截取出来留给子代,再将另一个父代的基因按其顺序,在保证解的完整性下依次放入子代中.例如两父代x为[1, 2, 3, 4, 5],y为[3, 2, 5, 1, 4]进行交叉.截取x的中间三个为子代部分,当前子代状态为[ , 2, 3, 4, ].再将y的基因按顺序,在不重复的情况下,依次填入其中,最终子代结果为[5, 2, 3, 4, 1].变异操作选用离散变异的方式进行,变异率P取0.7/chrom_length（chrom_length为编码长度）.同时,在变异的过程中,考虑变异检测和变异位数因素.对种群中的个体进行变异检测即产生随机值看是否小于变异率,当小于时执行变异.在变异位数方面,如果货位数大于货架数,取奇数.如果货位数等于货架数时,变异位数取偶数.基于交叉、变异的执行,新的个体重新放入种群中.算法判断是迭代代数否满足迭代终止要求,若满足,选取最优个体为最终解.