時間依賴的交通網絡模型及最短路徑算法

ID:38259706

大小:342.22 KB

頁數(shù):4頁

時間:2019-05-24

時間依賴的交通網絡模型及最短路徑算法_第1頁
時間依賴的交通網絡模型及最短路徑算法_第2頁
時間依賴的交通網絡模型及最短路徑算法_第3頁
時間依賴的交通網絡模型及最短路徑算法_第4頁
資源描述:

《時間依賴的交通網絡模型及最短路徑算法》由會員上傳分享,免費在線閱讀,更多相關內容在行業(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

當前文檔最多預覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當前文檔最多預覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學公式或PPT動畫的文件,查看預覽時可能會顯示錯亂或異常,文件下載后無此問題,請放心下載。
2. 本文檔由用戶上傳,版權歸屬用戶,天天文庫負責整理代發(fā)布。如果您對本文檔版權有爭議請及時聯(lián)系客服。
3. 下載前請仔細閱讀文檔內容,確認文檔內容符合您的需求后進行下載,若出現(xiàn)內容與標題不符可向本站投訴處理。
4. 下載文檔時可能由于網絡波動等原因無法下載或下載錯誤,付費完成后未能成功下載的用戶請聯(lián)系客服處理。
关闭