基于Yen算法与蚁群算法融合的路径规划方法.pdf

(19)国家知识产权局(12)发明专利申请(10)申请公布号CN115824242A(43)申请公布日2023.03.21(21)申请号202211446912.2(22)申请日2022.11.18(71)申请人东南大学地址210096江苏省南京市玄武区四牌楼2号(72)发明人陈茜郭璐张钰(74)专利代理机构南京经纬专利商标代理有限公司32200专利代理师陈月菊(51)Int.Cl.G01C21/34(2006.01)权利要求书1页说明书8页附图4页(54)发明名称基于Yen算法与蚁群算法融合的路径规划方法(57)摘要本发明公开了一种基于Yen算法与蚁群算法融合的路径规划方法，包括如下步骤：根据目标路网中交叉口和路段的分布情况构建路网拓扑图，将目标路网定义为一个有向图；应用A*+Yen算法求解目标路网的前K条最短路径，并将其作为备选路径集；保留备选路径集w1中所涉及到的节点及路段，将其余节点及路段删除，对现有道路网进行简化；使用距离和时间之比的方法计算简化后道路网中各个路段的行程时间；结合路段行程时间和交叉口数目对基本蚁群算法进行改进，用改进后的蚁群算法做路径寻优，求解一定数量的备选路径作为最优路径集。本发明解决了传统Yen算法规划路径考虑因素单一及蚁群算法在大型路网中计算效率较低的问题，提高了规划路径的有效性和合理性。CN115824242ACN115824242A权利要求书1/1页1.一种基于Yen算法与蚁群算法融合的路径规划方法，其特征在于，包括如下步骤：S1、根据目标路网中交叉口和路段的分布情况构建路网拓扑图，将目标路网定义为一个有向图G＝(V，E)，建立各节点连接关系的邻接矩阵，用权值表示各道路节点之间路段的长度；S2、应用A*+Yen算法求解目标路网的前K条最短路径，并将其作为备选路径集，记为W1；S3、保留备选路径集W1中所涉及到的节点及路段，将其余节点及路段删除，对现有道路网进行简化，简化后的道路网记G′＝(V，E)；S4、使用距离和时间之比的方法计算简化后道路网中各个路段的行程时间；S5、结合路段行程时间和交叉口数目对基本蚁群算法进行改进，用改进后的蚁群算法做路径寻优，求解备选路径作为最优路径集，记为W2。2.根据权利要求1所述的方法，其特征在于，步骤S1中：V＝{v1，v2，v3，……vn}表示路网中包括起节点和中间节点在内的所有节点集合，E＝{(vi～vj)|i，j＝0，1，2，……n}表示由所有节点组成的路段集合，(vi～vj)表示由节点i和j连成的一条路段，确定起始点和目标点；G中每条边均赋有权值。3.根据权利要求1所述的方法，其特征在于，步骤S3中：利用浮动车历史GPS数据，使用距离和时间之比的方法估计简化后道路网中各个路段的行程时间。4.根据权利要求1所述的方法，其特征在于，步骤S5中，将两节点间路段行程时间作为蚂蚁选择下一节点的依据，期望函数改为节点之间路段行程时间的倒数，如式(1)所示：其中ηij为期望函数，表示蚂蚁选择节点i、j之间路线的期望程度，tij表示i、j两节点之间的路段行程时间。5.根据权利要求4所述的方法，其特征在于，蚂蚁每一次所走路径中的交叉口数目加入到信息素更新函数中，改进后的信息素浓度函数τ(t)的更新机制如式(2)和式(3)所示：其中τij表示由i到j的信息素浓度，m表示蚂蚁个数，ρ表示信息素的蒸发率，Q表示每只蚂蚁能分泌的信息素的总量，wk表示蚂蚁经过路径中所含交叉口的数量。6.一种计算机可读存储介质，其上存储有计算机程序，其特征在于：该程序被处理器执行时实现如权利要求1～5中任一项所述的基于Yen算法与蚁群算法融合的路径规划方法中的步骤。7.一种计算机设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，其特征在于，所述处理器执行所述程序时实现如权利要求1～5中任一项所述的基于Yen算法与蚁群算法融合的路径规划方法中的步骤。2CN115824242A说明书1/8页基于Yen算法与蚁群算法融合的路径规划方法技术领域[0001]本发明属于交通工程技术领域，更具体地说，涉及一种基于Yen算法与蚁群算法融合的路径规划方法。背景技术[0002]K条最短路问题(Kshortestpaths,KSP)最早由Hoffman和Pavley在20世50年代提出，目的是寻找网络图中从起点大终点间的多个备选路径，形成最短路径集以满足用户出行需求。目前根据路径限制的条件，可以将KSP求解问题分为限定无环KSP问题和一般KSP问题。限定无环KSP算法中的Yen算法是解决前K条最短简单路径问题的经典算法，也是目前应用最广泛的算法。Yen算法与其他KSP算法相比的优势在于运算效率较高，时间复杂度较低，可以在节点较多的大型路网中快速筛选出K条备选路径，但很少有学者结合其他道路因素对Y