鐵路運輸徑路的研究

前言：想要寫出一篇引人入勝的文章？我們特意為您整理了鐵路運輸徑路的研究范文，希望能給你帶來靈感和參考，敬請閱讀。

摘要：Dijkstra算法是鐵路運輸徑路實現計算機判定的重要基礎算法。以Dijkstra為最短徑路算法，結合我國鐵路運輸現狀，設計特定徑路參數描述語言，實現了計算機對鐵路運輸徑路的智能化判定。徑路計算速度達到5萬條／s以上，正確率達到100%，滿足了不同業務對徑路的需求。是計算機理論知識轉化為鐵路運輸生產力的成果。

關鍵詞：鐵路網；鄰接表；Dijkstra算法；最短徑路；特定徑路

1鐵路路網數據結構

路網數據結構是徑路系統的骨骼，直接關系到徑路運算效率的高低和存儲空間的大小。本文采用鄰接表的方式存儲路網結構[2]，在這種存儲方式中，對路網中每一個節點建立一個鏈表，在路網中可以稱之為節點的車站，從圖論的角度上講，就是度＞2的節點，我們將度＞2的車站、鐵路局分界站、線路屬性臨界站和編組站均視為路網節點，大約有1200個節點。空間復雜度為O(n^m)。

2最短徑路算法實現

鐵路最短徑路算法一直是鐵路各科研院校的重點課題，也是鐵路運輸徑路判定的基礎。Dijkstra最短徑路算法是由荷蘭計算機科學家迪杰斯特拉于1959年提出的，是從一個頂點到其余各頂點的最短徑路算法，解決的是有向圖中最短徑路問題。Dijkstra算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止[2]。

2.1經典Dijkstra算法

Dijkstra算法思想為：設G=(V,E)是一個帶權有向圖，把圖中頂點集合V分成兩組，第1組為已求出最短路徑的頂點集合，用S表示，初始時S中只有一個源點，以后每求得一條最短路徑,就將該終點加入到集合S中，直到全部頂點都加入到S中，算法就結束了。第2組為其余未確定最短路徑的頂點集合，用U表示，按最短路徑長度的遞增次序依次把第2組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度；U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。算法具體步驟：（1）初始時，S只包含源點，即S=v，v到v的距離為0。U包含除v外的其他頂點，U中頂點u距離為邊上的權（若v與u有邊）為∞(若u不是v的出邊鄰接點）。（2）從U中選取一個距離v最小的頂點k，把k加入S中（該選定的距離就是v到k的最短路徑長度）。（3）以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點u（u∈U）的距離（經過頂點k）比原來距離（不經過頂點k）短，則修改頂點u的距離值，修改后的距離值為頂點k的距離加上邊上的權。（4）重復步驟（2）和（3）直到所有頂點都包含在S中。至此，源點到其余頂點的最短徑路都以得出。每次以一個頂點為源點，重復執行Dijkstra算法n次（圖中共有n個頂點），便可求得每一對定點之間的最短徑路。總的執行時間為O(n^3)[3]。

2.2算法實現

算法實現的關鍵是運算速度，以及平臺擴展和空間利用。在綜合分析當前各種計算機語言特性的基礎之上，采用C++語言[4]實現Dijkstra算法。當前全路共有近7000個車站，最短徑路運算速度在10萬條／s以上。

2.3算法運用的關鍵點

最短徑路算法是徑路系統的靈魂，是能否支撐特定徑路算法的核心之所在。最短徑路計算關鍵在于特殊情況的處理。在我國鐵路路網中有個別線路僅限本線各站發到貨物使用，如齊晏線、溝海線等線，該類型線路不納入最短徑路計算，不能有通過濟南—晏城北或晏城北—濟南的最短徑路出現，其本線里程僅供本線各車站到發使用。又如文獻[5]中規定“太中線北中段、榆北線、定銀線、包西線、神大線店塔－大保當段、甘鐘線辦理互為最短徑路的本線到發。”那意味著該幾條線路組成了一個局部的網絡。車站之間相互到發可以使用網絡中的線路里程，車站與網絡外車站相互間的到發可以使用網絡中的線路里程。隨著我國合資和地方鐵路數量的增加，以上兩種類型線路在路網中的比重在逐年增加，在算法設計時需要重點考慮[6]。

3特定徑路參數語言設計

特定徑路參數語言設計是徑路系統能否滿足業務邏輯的關鍵之所在。假如全路的車流徑路都按照最短徑路來運輸，那勢必會造成在路網中比較短的線路上車流擁堵，而在路網中較長的線路上卻沒有車流，運力資源不能有效發揮，所以中國鐵路國家集團有限公司會綜合分析最短徑路、線路流量、編組計劃和貨物運價等因素[7]，制定特定徑路，使路網整體通過能力達到最優。那么，特定徑路就必須由計算機參數語言去實現，當前全國鐵路執行特定徑路的OD流已占到了全路車流的65%，可見特定徑路比重之高。并且隨著近年來路網復雜度的增加，特定徑路的復雜度也隨之提升，特定徑路參數語言的設計要求：既要滿足復雜的業務需求，又要考慮徑路運算的效率，還需兼顧系統參數維護的復雜度。本文將特定徑路業務邏輯分為3類：集結類、改變經由類和修改里程類。

3.1集結類

集結類是特定徑路中最重要的一種類型，簡單來講就是將車流集結到某一個編組站，再執行該編組站對應的徑路條文，該編組站發往某個組號范圍的有可能根據特定徑路再集結到下一個編組站，也有可能根據最短徑路或特定徑路到達到站。如文獻[5]中第12條上海、南昌局相關線中規定“（十）上海局袁寨及其以南、爐橋以西、三十里鋪以北各站與上海局南京及其以東、裕溪口以南、靖江南以南各站相互間裝的重車，按合肥東支點運輸。”此條文規定車流集結到合肥東編組站；“（十一）凡經由合肥東（蕪湖東）支點（含水蚌線、寧蕪線塔橋－馬鞍山各站）與上海局宣城以東、無錫西以南、黃渡以東各站相互間裝的重車，經皖贛線、宣杭線運輸。”此條文規定了合肥東編組站裝到南翔以遠的重車集結到喬司編組站。通過集結類的設計便可實現特定徑路，層層遞歸的業務邏輯。

3.2改變經由類

改變經由類是特定徑路中最為常見的一種類型，按照業務邏輯不同可分為兩小類：原經由改變經由類、發到域改變經由類，下面舉例說明。文獻[5]中第12條上海、南昌相關線中規定“（四）凡經向塘西支點裝到成都局（廣漢－廣元間各站除外）的重車，均經滬昆線、按株洲北支點運輸。”此條是最為普通的原經由改變經由類，條文中并沒有規定具體有哪些發站是經由向塘西支點的，發站是要經過最短徑路和特定徑路計算來判定的，每一個到站都有可能對應著不同的發區域。文件中第13條進出西南相關線中規定“（三十三）成都局成昆線各站裝到南寧局黎塘以南各站重車，均經攀枝花分界站運輸。”。此條為典型的發到域改變經由類，條文中明確地說明了發到域的范圍，在此不再贅述。

3.3修改里程類

修改里程類是徑路里程統計中較為特殊的一種類型，主要用于計費里程的修改。如貨物運價里程表中對淮南線的規定“裕溪口至蕪湖東間按50km計費”，但實際里程只有20km，所以在計算路網最短徑路時按照20km計，而在里程統計時，上海鐵路局里程加30km、計費里程加30km、基金里程加30km、電氣化里程加30km。類似這樣的實例，路網中還存在多處，需要在算法設計中特殊對待。特定徑路參數語言的設計諸如此類，但在參數語言編譯算法上仍是一個非常復雜的工程，區域的定義、特定徑路的對接、執行的效率和圖形的展示需要設計者精心設計，并且最為關鍵的是對業務邏輯必須有最全面的掌握。

3.4實例與結論分析

以鐵路《貨物運價里程表》[8]為路網基礎信息，進行路網數據結構的搭建，以第2節中的最短徑路算法進行程序設計，所得最短徑路和里程全部符合《貨物運價電子里程表信息系統》中環狀徑路的判斷結果，如蘭州北到廣州西站的最短徑路為蘭州北–天水–新筑–商南–襄陽北–益陽東–撈刀河–廣州西，里程為2611km。再以文獻[5]為特定徑路依據，進行特定徑路參數語言的編寫，所得特定徑路的經由和里程完全符合《全路車流徑路查詢系統》的查詢結果，如武威南到榆次站的徑路為武威南–迎水橋–定邊–綏德–榆次，里程為982km，并且徑路計算速度在Win32環境下達到5萬條／s以上。

4結束語

本文的研究方法提升了鐵路運輸徑路選擇的智能化程度，提高了運行效率，解決了平臺擴展的問題，滿足了當前業務邏輯的需求，但是在尋找最優徑路和輔助決策方面還有一定的不足。下一步，我們將繼續進行理論算法[9]的深層次研究，并探索A*[10]、次短徑路、佛洛依德（Floyd）和其他經典理論算法[11]在鐵路運輸徑路中的實現方法，為中國鐵路貨物運輸向現代化物流轉型貢獻技術力量。

作者：張銳 鄧桂星 李世春 金福才 單位：中國鐵路蘭州局集團有限公司 中國鐵道科學研究院集團有限公司 電子計算技術研究所