3.3 路径规划算法

基于对遗传算法的改进,本文设计的基于遗传算法的多AGV路径规划算法,将路径长度、转弯数加入适应度函数,即转弯次数越少,路径总长越短,该个体越优秀.同时,采用改进的静态地图法来解决多AGV路径冲突问题.路径的规划是货位路径协同优化的基础,是本文的重要内容之一,主要使用遗传算法执行规划路径的操作,其伪代码如下所示.

输入：地图信息,起点,终点
输出：规划完成的路径点集合

具体来说,在遗传算法计算过程中,首先对目标结果进行编码,路径编码方式为排列编码,例如[1, 2, 5, 6, 7, 8]表示从 1 号点出发,途径 2、5、6、7 这些点最终到达 8 号点.路径坐标点序号作为基因参与算法运算.根据起始点到目标点序号,生成随机可行的路径序列,称为初始种群.

然后,对此种群进行适应值计算,使公式 3-7 所示.其中pathlength参数与fit适应度值成反比,表示路径越短适应度值越优秀,选择出来的路线也越贴近最优解.适应值越大意味着这个个体越优秀.表示转弯次数,取值大于等于1,nodenum参数的添加是考虑到转弯因素对路径规划的影响,

系数对pathlength参数的微调使算法在路径选择中尽可能避免选择拐弯次数过多的路线.经过实验验证,nodenum的加入有效的减少了算法选择转弯次数过多的路线.将基于该公式计算出的初始种群中所有个体的适应值记录下来,再对此种群进行交叉和变异操作.

本文基于轮盘赌法对交叉和变异操作的对象进行选取,以使得适应度越大的个体被选中的概率越大.轮盘赌选算子可以根据个体适应值在群体中所占比例,结合该算子被选中的累积概率,再取一个0到1之间的随机值,比较子代个体的适应度比例和随机值大小,选取子代适应值高的个体参与到遗传运算中,进一步提高整个种群的适应值,从而取得更优的最终结果,或者让该种群向更优的结果发展.具体来说,我们先计算该种群的适应值总和fit_sum,然后,计算每个个体的适应值占比rfit= fit/fit_sum和各部分累积概率cfit（如公式3-8所示）.其中,i≤popsize(种群大小),popnexti为第代种群, popcurrenti为第代种群的副本）.

随后,遍历种群副本popcurrenti,而后生成一个0-1之间的随机数p.比较子代个体的cfit和p的值,直到cfit比p大时该个体代替popcurrenti中此位置的个体.最后将current的所有值赋给popnexti.

在交叉操作的实现中,交叉次数是路径点总数的1/4,具体计算出的次数向下取整.每次交叉操作方法相同,首先随机选取此种群中的某一条路径.在此路径上找到一个随机点设为交叉点q,然后寻找另一条也通过此点的基因.设p1,p2为原选出基因.将p1中q点以后的点被P2中q点以后的点代替生成新的基因P1,再将P2中q点以后的点由p1中q点以后的点代替生成新的基因P2.对P1和P2进行路径再优化,然后计算并更新P1和P2的适应值、路径长度和转弯次数,完成交叉操作.

在变异操作中,首先判定是否发生变异.基于预设变异几率(mutationRate),根据random=Math.random()*(1.0 /mutationRate)计算变异率(Math.random()为随机数生成函数).此时random若为0则执行变异.变异时,先随机挑选种群中的一条染色体（即一个完整的可行路径）,再在此路径上随机选取一个路径点,分别计算此条染色体上该路径点的前一个点pre和后一个点next.而后在地图上分别搜索pre和next所有相邻点,并分别寻找所有相邻点中的重合点.我们将这些重合点视为可变异点,以保证变异后路径为通路.在重合点中随机选取一个点作为新的连接点代替一开始选中的点,生成新的染色体.计算并更新新染色体的适应值、路径长度、转弯次数,完成变异操作.最后,检查是否迭代到最大代数,若没有则继续进行变异和交叉,若达到最大代数则对种群进行筛选,即比较所有染色体（个体）的适应值,适应值最大即为最优结果.

除此之外,本文基于改进的静态地图法来解决多AGV路径冲突问题,以保证算法在多任务下各AGV车辆不会相撞.本文对已有的静态地图法进行了改进,在假设车辆保持匀速运行时,估算了车辆的运行位置,以此将车辆已走过的路径实时释放掉,车辆未走过的路径保持封锁状态,弥补静态地图法存在的缺陷.具体来说,在计算新的任务路径时,先获取之前所有未完成的任务执行情况,即在运行中的AGV的当前位置,并获取他们未来将要走的路径.通过对每一个新任务执行路径封锁,在优化最初避免冲突,使得冲突不可能发生.对于可能会造成的当前时间点车辆无法搜索到可行路径的情况,设置车辆等待.详细来说,算法中使用的地图不是创建的原始的地图,而是将其他AGV车已占用的道路排除后的新地图,这意味着每个AGV车进行路径规划时都有一个属于他自己地图.该地图将其他AGV已规划但未走过的路径点进行封锁,已封锁路径上点和货架、充电桩等一样视为不可通过的障碍物,以此保证新的车辆规划避开这些障碍物,解决AGV的路径冲突问题.

3.4 货位路径协同优化算法

本文对正在运维的智能仓储出入口数据进行分析,发现如果相似度高的货物摆放集中且密集,极有可能导致路径堵塞.相反,相似度高的货物摆放分散则容易出现高频货物所在货架出库距离长这一问题.而分散与否则是由最佳货架出库路径的重合程度判断的.因此,将货架最佳出库路径和货品的相关性结合起来可有效的找到一个缓解AGV路径拥堵,提高出库效率的货品摆放结果.基于以上数据分析,本文提出的货位规划与路径规划协同优化算法的适应度函数包含两个参数,货架的出库代价,以及该货架和周边货架的冲突代价.实验表明该设置的适应值可以用来筛选出合格的个体,从而产生合适的解.

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

图 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].此时,一个分类有着货品的属性,且集成了更多的货品,将这个分类看作是一个未被放入货架位置的待入库货架,即将所有货品转化为待入库货架.