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

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

机挑选种群中的一条染色体(即一个完整的可行路径),再在此路径上随机选取一个路径点,分别计算此条染色
体上该路径点的前一个点 pre 和后一个点 next.而后在地图上分别搜索 pre 和 next 所有相邻点,并分别寻找所有
相邻点中的重合点.我们将这些重合点视为可变异点,以保证变异后路径为通路.在重合点中随机选取一个点作
为新的连接点,代替一开始选中的点,生成新的染色体.计算并更新新染色体的适应值、路径长度、转弯次数,完
成变异操作.最后检查是否迭代到最大代数:若没有,则继续进行变异和交叉;若达到最大代数,则对种群进行筛
选,即比较所有染色体(个体)的适应值,适应值最大即为最优结果.
除此之外,本文基于改进的静态地图法来解决多 AGV 路径冲突问题,以保证算法在多任务下各 AGV 车辆
不会相撞.本文对已有的静态地图法进行了改进,在假设车辆保持匀速运行时,估算了车辆的运行位置,以此将
车辆已走过的路径实时释放掉,车辆未走过的路径保持封锁状态,弥补静态地图法存在的缺陷.具体来说,在计
算新的任务路径时,先获取之前所有未完成的任务执行情况,即在运行中的 AGV 的当前位置,并获取他们未来
将要走的路径.通过对每一个新任务执行路径封锁,在优化最初避免冲突,使得冲突不可能发生.对于可能会造
成的当前时间点车辆无法搜索到可行路径的情况,设置车辆等待.详细来说,算法中使用的地图不是创建的原始
地图,而是将其他 AGV 车已占用的道路排除后的新地图,这意味着每个 AGV 车进行路径规划时都有一个属于
他自己的地图.该地图将其他 AGV 已规划但未走过的路径点进行封锁,已封锁路径上的点和货架、充电桩等一
样视为不可通过的障碍物,以此保证新的车辆规划避开这些障碍物,解决 AGV 的路径冲突问题.
2.4 货位路径协同优化算法
本文对正在运维的智能仓储出入口数据进行分析,发现:如果相似度高的货物摆放集中且密集,极有可能导
致路径堵塞;相反,相似度高的货物摆放分散,则容易出现高频货物所在货架出库距离长这一问题.而分散与否,
则是由最佳货架出库路径的重合程度判断的.因此,将货架最佳出库路径和货品的相关性结合起来,可有效地找
到一个缓解 AGV 路径拥堵、提高出库效率的货品摆放结果.基于以上数据分析,本文提出的货位规划与路径规
划协同优化算法的适应度函数包含两个参数:货架的出库代价以及该货架和周边货架的冲突代价.实验表明:该
设置的适应值可以用来筛选出合格的个体,从而产生合适的解.
本文提出的货位规划与路径规划协同优化算法的基本思路为:首先计算货品间的相似度,按照货架最大载
货种类数对货品进行聚类操作;再计算聚类后各个类别间货品的相似度,之后再计算各个货架的最佳出库路径.
利用计算完成的数据以及当前地图信息,使用改进的遗传算法计算出货架布局情况,也就是货架的摆放方式,从
而完成货位布局和路径规划两者的共同优化.
货位路径协同优化算法的具体流程如图 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 为本文提出的协同优化算
法中η的值.