鐵路運輸徑路的研究

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

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

關(guān)鍵詞：鐵路網(wǎng)；鄰接表；Dijkstra算法；最短徑路；特定徑路

1鐵路路網(wǎng)數(shù)據(jù)結(jié)構(gòu)

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

2最短徑路算法實現(xiàn)

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

2.1經(jīng)典Dijkstra算法

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

2.2算法實現(xiàn)

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

2.3算法運用的關(guān)鍵點

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

3特定徑路參數(shù)語言設(shè)計

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

3.1集結(jié)類

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

3.2改變經(jīng)由類

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

3.3修改里程類

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

3.4實例與結(jié)論分析

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

4結(jié)束語

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

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