鐵路運(yùn)輸徑路的研究

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

摘要：Dijkstra算法是鐵路運(yùn)輸徑路實(shí)現(xiàn)計(jì)算機(jī)判定的重要基礎(chǔ)算法。以Dijkstra為最短徑路算法，結(jié)合我國(guó)鐵路運(yùn)輸現(xiàn)狀，設(shè)計(jì)特定徑路參數(shù)描述語(yǔ)言，實(shí)現(xiàn)了計(jì)算機(jī)對(duì)鐵路運(yùn)輸徑路的智能化判定。徑路計(jì)算速度達(dá)到5萬(wàn)條／s以上，正確率達(dá)到100%，滿(mǎn)足了不同業(yè)務(wù)對(duì)徑路的需求。是計(jì)算機(jī)理論知識(shí)轉(zhuǎn)化為鐵路運(yù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)系到徑路運(yùn)算效率的高低和存儲(chǔ)空間的大小。本文采用鄰接表的方式存儲(chǔ)路網(wǎng)結(jié)構(gòu)[2]，在這種存儲(chǔ)方式中，對(duì)路網(wǎng)中每一個(gè)節(jié)點(diǎn)建立一個(gè)鏈表，在路網(wǎng)中可以稱(chēng)之為節(jié)點(diǎn)的車(chē)站，從圖論的角度上講，就是度＞2的節(jié)點(diǎn)，我們將度＞2的車(chē)站、鐵路局分界站、線路屬性臨界站和編組站均視為路網(wǎng)節(jié)點(diǎn)，大約有1200個(gè)節(jié)點(diǎn)。空間復(fù)雜度為O(n^m)。

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

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

2.1經(jīng)典Dijkstra算法

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

2.2算法實(shí)現(xiàn)

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

2.3算法運(yùn)用的關(guān)鍵點(diǎn)

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

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

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

3.1集結(jié)類(lèi)

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

3.2改變經(jīng)由類(lèi)

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

3.3修改里程類(lèi)

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

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

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

4結(jié)束語(yǔ)

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

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