Page 157 - 《软件学报》2020年第9期

2778 Journal of Software 软件学报 Vol.31, No.9, September 2020

数间的权重比,基于后续实验调整,本文的α系数取值为 0.8,β系数取值为 0.2.此外,根据适应度函数分析来看,适
应度与该未入库货架的出库频率、最佳出库路径长度以及与其相关性高的其他货位路径冲突数成正相关.
完成适应度的计算,算法开始代数迭代.首先使用锦标赛法选取算子,基于已计算出的适应度,在种群中随
机挑选个体并比较适应度,适应度大的被淘汰,最终选择出一定量的个体进行交叉生成下一代.在基本的锦标赛
基础上,本文加入了被选择系数以提高锦标赛选择算子的效率,有效消弱了为了减少劣质个体被多次比较从而
导致选择出不优秀个体的情况发生.具体来说,我们为每个个体赋予一个被选择系数,其默认初值为 1.一开始,各
个个体的被选择系数相等,开始选择时为每个个体生成区间为[0,1]的随机数,再用该随机数乘以被选择系数,最
终获得的按从小到大顺序取进入锦标赛.一旦某一个体被淘汰,则减少它的被选择系数.
基于上述获得的算子,算法开始依次进行交叉和变异操作.交叉操作时,选取集合 B 中任意两个体,进行交叉
操作.本文提出协同优化算法选用有序交叉方法进行交叉,将父代中的某一段截取出来留给子代,再将另一个父
代的基因按其顺序,在保证解的完整性下,依次放入子代中.例如两父代 x 为[1,2,3,4,5],y 为[3,2,5,1,4]进行交叉.
截取 x 的中间 3 个为子代部分,当前子代状态为[⋅,2,3,4,⋅].再将 y 的基因按顺序,在不重复的情况下,依次填入其
中,最终子代结果为[5,2,3,4,1].变异操作选用离散变异的方式进行,变异率 P 取 0.7/chrom_length(chrom_length
为编码长度).同时,在变异的过程中,考虑变异检测和变异位数因素.对种群中的个体进行变异检测即产生随机
值,看是否小于变异率,当小于时执行变异.在变异位数方面,如果货位数大于货架数,取奇数;如果货位数等于货
架数时,变异位数取偶数.基于交叉、变异的执行,新的个体重新放入种群中.算法判断是迭代代数否满足迭代终
止要求:若满足,选取最优个体为最终解.

3 实验结果及分析

基于昆山某智能仓储的实际运维数据,我们在智能仓储仿真平台对本文提出的货位规划和路径规划协同
优化算法进行了实验,并与传统遗传算法 [24] 、基于出货频率的贪心算法 [25] 进行了对比分析,实验结果验证了本
文所提出的智能仓储货位规划与路径规划协同优化算法的有效性.

3.1 实验数据和评价指标
本次实验数据来自于昆山某生产厂商仓储物流数据,并额外加入一些干扰数据来模拟突发情况.实验数据
涉及库存总货品 200 种,其中,物品间的相似度比例大致为 6:2:2:1:1,分别代表货物间两种货品间强相关、3 种货
品间强相关直到 6 种货品间强相关,该比例的获取是从该厂商 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 运行耗时)、完成出库任务总耗时(即出