資源描述:
《時間依賴的交通網絡模型及最短路徑算法》由會員上傳分享,免費在線閱讀,更多相關內容在行業(yè)資料-天天文庫。
1、第6卷第6期解放軍理工大學學報(自然科學版)Vol.6No.62005年 月JournalofPLAUniversityofScienceandTechnologyDec.2005文章編號:100923443(2005)0620541204時間依賴的交通網絡模型及最短路徑算法1,3213何 俊, 戴 浩, 宋自林, 劉 剛(1.解放軍理工大學指揮自動化學院,江蘇南京210007;2.中國電子設備系統(tǒng)工程公司,北京100039;3.解放軍通信指揮學院,湖北武漢430010)摘 要:為了解決傳統(tǒng)最短路徑算法不能很好地應用于實時公交查詢系統(tǒng)的問題,研究了時間依賴的交通網絡模型和理
2、論基礎,提出了一種時間依賴的最短路徑算法,以此算法為基礎實現(xiàn)了南京市公交查詢系統(tǒng)。實踐證明,時間依賴的交通網絡模型能更好地反映實際交通網絡的運行情況。關鍵詞:時間依賴的交通網絡;最短路徑算法;網絡拓撲中圖分類號: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 隨著計算機技術和網絡技術的迅速發(fā)展,地理信息系統(tǒng)GIS(geographicinformationsystem)尤其是電子地圖系統(tǒng)的應用越來越廣泛。最短路徑算法是地理信息系統(tǒng)中最重要最基本的內容之一。傳統(tǒng)的最短路徑算法以Dijkstra算法和Floyd算法為代表,這些算法假設網絡拓撲和權值不變,以“整體最優(yōu)則局部也最優(yōu)”為指導思想。例如,如果dk圖1 不遵守經典規(guī)則的例子Fig.1Examplethatdoesn’tkeeptheclassicalrule是頂點v1到vj的最短路徑,vi
6、是路徑上到vj的前一點,則認為v1到vi的長度也是v1到vi的最短間,從圖中可計算出從①到③的最短路徑應該是[1]路。舉例說明此理論的局限性,如圖1所示。①→④→②→③,所用時間為13min。這條線路上①圖中gij(t)表示在t時刻從i出發(fā)到j所用的時到②所用時間為10min,而直接從①到②所用時間收稿日期:2004211222.為5min,可見①到③的最短路徑上的子路徑不一定作者簡介:何 俊(1979-),男,博士生,助教.是最短的。這說明“整體最優(yōu)則局部也最優(yōu)”的原則聯(lián)系人:戴 浩,研究員,博士生導師;研究方向:指揮自動化理論與技術;E2mail:dai-hao@sin
7、a.com.在時間依賴的網絡中不一定正確。542解放軍理工大學學報(自然科學版)第6卷 本文描述了時間依賴的交通網絡模型,研究了infirst2out)模型和非FIFO模型。如果gij(t)連續(xù),時間依賴的交通網絡的性質,進行了嚴密的推導,指處處可微,并且Pt,gij(t)≤$t+gij(t+$t);則稱弧出了文獻[2]中推導的不嚴密性和錯誤?;跁r間依(vi,vj)為FIFO弧。對于離散情況,設(vi,vj)∈E,若賴的交通網絡模型,提出了一種時間依賴的最短路對Ps,t∈S,s