基于最短路徑Dijkstra算法的鐵路客運中轉徑路優(yōu)化研究.pdf

1、信息技術的不斷發(fā)展促進了其在更多領域的廣泛應用。在鐵路旅客運輸中，對鐵路客運中轉徑路優(yōu)化，既是旅客合理選擇出行方案時十分關心的問題，也是提高鐵路運輸部門工作效率和質量的有效途徑。鐵路客運中轉徑路優(yōu)化是基于鐵路運輸網(wǎng)拓撲結構的最優(yōu)路徑算法問題。因為具有實際的應用背景，最優(yōu)路徑算法考慮的因素和限制條件比經(jīng)典最短路徑算法復雜得多，其核心思想還是源于經(jīng)典最短路徑算法。
　　本文在綜合分析最短路徑算法的基礎上，提出從網(wǎng)絡規(guī)模和搜索技術兩方面

2、改進Dijkstra算法。結合鐵路客運網(wǎng)絡的空間分布特點，對路網(wǎng)分層模型、客運中轉計算模型、客運網(wǎng)的存儲數(shù)據(jù)結構和最短路徑算法的運行數(shù)據(jù)結構等關鍵技術進行了研究，最后實現(xiàn)了改進的鐵路客運中轉徑路計算算法。主要工作包括：
　?、賹ψ疃搪窂剿惴ǖ拇鎯?shù)據(jù)結構和搜索節(jié)點采用的數(shù)據(jù)結構，及最短路徑算法的分類體系進行了介紹；分析了Dijkstra算法的主要思想，并對Dijkstra算法的優(yōu)化途徑進行研究。
　?、趯﹁F路網(wǎng)的拓撲關系進行

3、研究，提出了采用兩級分層的層次模型來表示鐵路網(wǎng)，以減少分析過程中搜索節(jié)點的數(shù)量；對非基點車站參與徑路計算提出了動態(tài)基點化的解決方法。
　?、蹖瓦\中轉徑路計算模型進行分析研究，提出了包含車站和車次信息的可擴展的計算模型。
　?、軐Π嚧涡畔⒌蔫F路客運網(wǎng)絡的存儲結構進行研究，提出了采用車次-到站鄰接表作為網(wǎng)絡的存儲結構，使搜索的結果是基于車次的而不僅是基于線路的；采用優(yōu)先隊列來優(yōu)化算法的運行結構，提高了算法的運行效率。

4、>　?、莶捎萌壏謱拥募軜嬻w系進行系統(tǒng)框架設計，運用面向對象方法提出用車站、車次、線路、時刻表等類表示鐵路客運網(wǎng)絡，并進行了數(shù)據(jù)庫分析設計和徑路計算流程設計。
　　本文將Dijkstra算法應用于鐵路客運中轉徑路優(yōu)化問題的研究中，提出了鐵路網(wǎng)的層次模型和新的客運中轉徑路計算模型，具有實際應用價值。結合鐵路運輸網(wǎng)拓撲結構的實際情況，對Dijkstra算法中的數(shù)據(jù)結構和運行結構進行了改進，對相關的研究及實際系統(tǒng)分析設計也具有一定的參考