资源描述：
《时间依赖的交通网络模型及最短路径算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第6卷第6期解放军理工大学学报(自然科学版)Vol.6No.62005年 月JournalofPLAUniversityofScienceandTechnologyDec.2005文章编号:100923443(2005)0620541204时间依赖的交通网络模型及最短路径算法1,3213何 俊, 戴 浩, 宋自林, 刘 刚(1.解放军理工大学指挥自动化学院,江苏南京210007;2.中国电子设备系统工程公司,北京100039;3.解放军通信指挥学院,湖北武汉430010)摘 要:为了解决传统最短路径算法不能很好地应用于实时公交查询系统的问题,研究了时间依赖的交通网络模型和理
2、论基础,提出了一种时间依赖的最短路径算法,以此算法为基础实现了南京市公交查询系统。实践证明,时间依赖的交通网络模型能更好地反映实际交通网络的运行情况。关键词:时间依赖的交通网络;最短路径算法;网络拓扑中图分类号:TP393.08文献标识码:ATime2dependenttrafficnetworksmodelandshortestpathalgorithm1,3213HEJun,DAIHao,SONGZi2lin,LIUGang(1.InstituteofCommandAutomation,PLAUniv.ofSci.&Tech.,Nanjing210007,China;2
3、.InstituteofChinaElectronicSystemEngineeringCorporation,Beijing100039,China;3.InstituteofCommunicationandCommandofPLA,Wuhan430010,China)Abstract:Classicshortestpathalgorithmsbroughtsomequestionswhenappliedtotimedbusquerysystem.Emphasesofresearchwerelaidonthetime2dependenttrafficnetworksand
4、theirbasictheoryinthispaper.Atime2dependentshortestpathalgorithmwaspresentedandabusquerysysteminNanjingbasedonthisshortestpathalgorithmwasrealized.Experimentalresultsdemonstratethatthetime2dependenttrafficnetworkscanwelldescribehowactualtrafficnetworksrun.Keywords:time2dependent;trafficnet
5、worksshortestpathalgorithmnetworkstopology 随着计算机技术和网络技术的迅速发展,地理信息系统GIS(geographicinformationsystem)尤其是电子地图系统的应用越来越广泛。最短路径算法是地理信息系统中最重要最基本的内容之一。传统的最短路径算法以Dijkstra算法和Floyd算法为代表,这些算法假设网络拓扑和权值不变,以“整体最优则局部也最优”为指导思想。例如,如果dk图1 不遵守经典规则的例子Fig.1Examplethatdoesn’tkeeptheclassicalrule是顶点v1到vj的最短路径,vi
6、是路径上到vj的前一点,则认为v1到vi的长度也是v1到vi的最短间,从图中可计算出从①到③的最短路径应该是[1]路。举例说明此理论的局限性,如图1所示。①→④→②→③,所用时间为13min。这条线路上①图中gij(t)表示在t时刻从i出发到j所用的时到②所用时间为10min,而直接从①到②所用时间收稿日期:2004211222.为5min,可见①到③的最短路径上的子路径不一定作者简介:何 俊(1979-),男,博士生,助教.是最短的。这说明“整体最优则局部也最优”的原则联系人:戴 浩,研究员,博士生导师;研究方向:指挥自动化理论与技术;E2mail:dai-hao@sin
7、a.com.在时间依赖的网络中不一定正确。542解放军理工大学学报(自然科学版)第6卷 本文描述了时间依赖的交通网络模型,研究了infirst2out)模型和非FIFO模型。如果gij(t)连续,时间依赖的交通网络的性质,进行了严密的推导,指处处可微,并且Pt,gij(t)≤$t+gij(t+$t);则称弧出了文献[2]中推导的不严密性和错误。基于时间依(vi,vj)为FIFO弧。对于离散情况,设(vi,vj)∈E,若赖的交通网络模型,提出了一种时间依赖的最短路对Ps,t∈S,s
