计算货架间的相似度,同样使用余弦相似度算法来进行计算.在计算出相似度后,对所有值减去 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为编码长度）.同时,在变异的过程中,考虑变异检测和变异位数因素.对种群中的个体进行变异检测即产生随机值看是否小于变异率,当小于时执行变异.在变异位数方面,如果货位数大于货架数,取奇数.如果货位数等于货架数时,变异位数取偶数.基于交叉、变异的执行,新的个体重新放入种群中.算法判断是迭代代数否满足迭代终止要求,若满足,选取最优个体为最终解.
4 实验结果及分析
基于昆山某智能仓储的实际运维数据,我们在智能仓储仿真平台对本文提出的货位规划和路径规划协同优化算法进行了实验,并与传统遗传算法[24] 、基于出货频率的贪心算法[25] 进行了对比分析,实验结果验证了本文所提出的智能仓储货位规划与路径规划协同优化算法的有效性.
4.1 实验数据和评价指标
本次实验数据来自于昆山某生产厂商仓储物流数据,并额外加入一些干扰数据来模拟突发情况.实验数据涉及库存总货品200种,其中物品间的相似度比例大致为 6: 2: 2: 1: 1,分别代表货物间两种货品间强相关、三种货品间强相关直到六种货品间强相关,该比例的获取是从该厂商 15 天内共计 14 个批次的出库记录中统计获取的.实验中货架、地图等设置是根据单个货架可放置货品种类数、地图预留的货位位置、路径点数等信息来配置的.基本的环境设置即为实际仓储环境,货位设置为单列连续摆放,总计32个货架,仓库入口和仓库出口分别位于仓储两侧.
本文所有的实验基于以下假设：1）AGV以匀速进行直线行走、转弯、运输等动作且不出现偏离轨道的情况;2）路径点间间距等长.在衡量算法运算效果时,设AGV运行过两路径点间长度的时间为单位时间,即单位时间=路径点间距/AGV速度（本文假定AGV平均运行速度为0.5m/s,路径点间距为1m,即单位时间为2s）;3）AGV车数量充足,能够保证每个任务都有独立的车辆立即执行.
设置的对比算法为其他货架优化算法,一个为传统遗传算法[24] ,另一个为基于出货频率的贪心算法[25] ,采用的路径计算统一为本文所实现的路径规划算法.本文的货位路径协同优化算法（以下实验数据分析中简称协同优化算法）和传统货架优化遗传算法,设定变异率为0.07,交叉率为0.68,迭代代数均为300.为了让遗传算法可以和本文所设计的算法形成对比,在遗传算法的适应性函数中添加了货品相关性β的影响,并为其设置了影响系数0.2,出货频率的系数α为0.8.
在实验结果的分析中,主要评价指标包括为完成出库任务进行路径规划的算法自身耗时（记为出库路径规划耗时）、AGV车辆按规划路径执行完出库任务的预估耗时（记为AGV运行耗时）、完成出库任务总耗时（即出库路径规划耗时和AGV运行耗时之和,记为出库总耗时）、为完成出库任务所需调用的AGV车辆数目（记为动用车辆数）等.
4.2 实验结果及分析
下面我们将基于14个批次的出库数据,从不同的维度来对比分析货位路径协同优化算法的表现情况.首先,我们分析各算法在完成所有批次货物出库的情况下的总体实验结果,即包含各类货品特征的仓储综合场景,该场景对应于实际仓储的综合运行状况.其次,为了分析智能仓储协同优化算法在特定特征场景下的优化效果,我们筛选出符合不同特点的出货批次,分成下列三个特征场景进行各算法间的对比分析,具体包括 1）以货品间相似度高、出货频率高为特点的场景 1;2）以货品间相似度高、出货频率低为特点的场景 2;3）以货品间相似度低、出货频率高为特点的场景 3.下面分别对以上场景的实验结果进行具体描述和分析.
