A算法在基于电子地图的动态路径诱导中的应用.pdf

《A算法在基于电子地图的动态路径诱导中的应用.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、交通科学武汉理工大学学报()第30卷　第5期与工程版Vol.30No.52006年10月JournalofWuhanUniversityofTechnologyOct.2006(TransportationScience&Engineering)3A算法在基于电子地图的3动态路径诱导中的应用1)2)3)邹　亮　徐建闽　朱玲湘(1)深圳大学建筑与土木工程学院　深圳　518060)(2)3)华南理工大学交通学院　广州　510640)(华南农业大学理学院　广州　510642)3摘要:动态网络中两节点间最短路径问题是目前尚未

2、解决的一个难题.文中提出利用A算法来求解电子地图中的这一问题,并利用电子地图中的地理信息来得到网络中两节点间最短距离的下3界,运用这些下界来设计有效的A算法.以广州市电子地图为基础,随机产生了一个满足先进先出原则的动态网络,利用这个网络对提出的算法进行了试验及性能分析.试验结果证明了该方法的有效性.3关键词:A算法;动态路径诱导;电子地图;最短路径问题中图法分类号:TP3010　引　　言合;A={1,⋯,m}为边集合;S={sijû(i,j)∈A}为边的长度集合;D={dij(t)û(i,j)∈A}为各边权动态网络中

3、的最短路径计算问题一直是智能值时间函数集合,函数dij(t)为(i,j)∈A在t∈[0,交通系统(intelligenttransportationsystem,M-1]上定义的正整数矩阵函数,T={0,⋯,MITS)的研究热点.最短路径计算不仅是动态路径-1}为时间间隔集合;K={kijûi,j∈N}为图中任诱导系统(dynamicrouteguidancesystem,意两节点通过其经纬度计算出的直线距离;MVDRDS)的核心部分,而且在ITS中的大量模型都为网络中所允许的最大行车速度.由于G=(N,需要在动态网

4、络中寻找大量的最短路径.ChabiniA,S,D,K,MV)为基于真实电子地图的动态网3[122]络,因此必须满足以下条件.等人第一次将A算法应用于动态网络.考虑到A3算法用于求解点到点最短路径问题的优势,(sii+sii+⋯+sij)≥kij113l文中提出在求解基于电子地图的动态最短路径问P(i,i1),(i1,i2),⋯,(il,j)∈A(1)3题中运用A算法,并利用电子地图所提供的交叉(sijöMV)≤dij(t)t∈[0,M-1](2)3路口的经纬度信息来获取其A算法所需的两节式(1)表示直线距离最短,式(

5、2)表示道路的最快点间最短路径下界.通行时间小于道路长度除以最快车速.3以下的符号是用于描述A算法的.1基于电子地图的动态网络和符号Li(t)为在t时刻由起点o到点i的最短距离;定义eij(t)为在t时刻由点i到点j的最短距离;Fi(t)为d在t时刻经过点i从o到终点p的最短距离;Li(t)d假设G=(N,A,S,D,K,MV)为一个基于电为在t时刻由起点o到点i的最短距离的上界;eijd子地图的动态网络.式中:N={1,⋯,n}为节点集为由点i到点j的最短距离的一个下界;Fi(t)为对　　　　收稿日期:200620

6、5225　　　　邹　亮:男,27岁,博士,主要研究领域为ITS技术3广东省自然科学基金项目(批准号:020945)和国家自然科学基金项目资助(批准号:50578064)·886·武汉理工大学学报(交通科学与工程版)2006年　第30卷dddFi(t)的一个估计,Fi(t)=Li(t)+eip;B(i)={jûj法只选择在最短路径上的节点.3∈N,(i,j)∈A}为从节点i不需要经过其他节点从以上两个性质可以得出,A算法的搜索效3dd3能够直接到达的节点集合;C为A算法所能够选率依赖于eij的质量.如果eij(t)=0

7、,那么A算法将3d3择的节点集合;S为A算法所选择的节点集合.变成Dijkstra算法;如果eij=eij(t),那么A算法只d一致性原则:如果Pi,j,p∈N,(i,j)∈A,t选择在最短路径上的节点;如果0

8、dij(t+1),那么就认为这一网络是满足先进先出原则的3.3A算法中的下界设计33.1　静态下界2A算法首先利用电子地图所提供的地理信息来产生A3算法是一种启发式搜索方法,它利用已有两节点间的下界,如下式min的一些先验知识来对解空间进行搜索.由于已经eij=kijöMV(3)3　　命题1Pi,j∈N,Pt∈[0,M-1],emin有了问题的