張 銳，鄧桂星 ，李世春 ，金福才

（1.蘭州鐵路局集團有限公司 信息處，蘭州 730000；2.中國鐵道科學研究院集團有限公司 電子計算技術研究所，北京 100081）

近年來大規(guī)模鐵路建設，鐵路網(wǎng)規(guī)?？焖贁U大，路網(wǎng)結(jié)構不斷優(yōu)化，運輸能力有了顯著提升，如何利用好路網(wǎng)資源，使鐵路運力資源的配置更加符合市場需求，是我國鐵路走向市場過程中需要深入研究的一個重大課題。鐵路貨物運輸徑路的制定是提升路網(wǎng)整體通過能力的重要技術手段。高效率的鐵路貨物運輸徑路計算對于支撐貨物運到時限用時計算、貨物及列車運行軌跡準確追蹤、鐵路運輸效益評價都具有重要意義。目前，我國鐵路在用的徑路系統(tǒng)[1]，已經(jīng)解決了由于路網(wǎng)復雜性和運輸方式特殊性而產(chǎn)生的技術難題。但是，隨著鐵路貨物運輸業(yè)務改革的深化，徑路系統(tǒng)在智能化程度、運算效率和平臺擴展上都需要進一步提升。本文從數(shù)據(jù)結(jié)構、圖論和業(yè)務邏輯的角度出發(fā)，重點解決當前存在的問題。

1 鐵路路網(wǎng)數(shù)據(jù)結(jié)構的建立

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

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

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

2.1 經(jīng)典Dijkstra算法

Dijkstra算法思想為：設G=(V,E)是一個帶權有向圖，把圖中頂點集合V分成兩組，第1組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以后每求得一條最短路徑 ,就將該終點加入到集合S中，直到全部頂點都加入到S中，算法就結(jié)束了）。第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）的距離（經(jīng)過頂點k）比原來距離（不經(jīng)過頂點k）短，則修改頂點u的距離值，修改后的距離值為頂點k的距離加上邊上的權。

（4）重復步驟（2）和（3）直到所有頂點都包含在S中。至此，源點到其余頂點的最短徑路都以得出。

每次以一個頂點為源點，重復執(zhí)行Dijkstra算法n次（圖中共有n個頂點），便可求的每一對定點之間的最短徑路。總的執(zhí)行時間為O(n^3)[3]。

2.2 算法的實現(xiàn)

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

2.3 算法運用的關鍵點

最短徑路算法是徑路系統(tǒng)的靈魂，是能否支撐特定徑路算法的核心之所在。最短徑路計算關鍵在于特殊情況的處理。在我國鐵路路網(wǎng)中有個別線路僅限本線各站發(fā)到貨物使用，如齊晏線、溝海線等線，如表1所示，該類型線路不納入最短徑路計算，不能有通過濟南—晏城北或晏城北—濟南的最短徑路出現(xiàn)，其本線里程僅供本線各車站到發(fā)使用。

表1 濟晏線 濟南-晏城北（國鐵）

又如文獻[5]中規(guī)定“太中線北中段、榆北線、定銀線、包西線、神大線店塔-大保當段、甘鐘線辦理互為最短徑路的本線到發(fā)?！蹦且馕吨搸讞l線路組成了一個局部的網(wǎng)絡。車站之間相互到發(fā)可以使用網(wǎng)絡中的線路里程，車站與網(wǎng)絡外車站相互間的到發(fā)可以使用網(wǎng)絡中的線路里程。

隨著我國合資和地方鐵路數(shù)量的增加，以上兩種類型線路在路網(wǎng)中的比重在逐年增加，在算法設計時需要重點考慮[6]。

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

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

3.1 集結(jié)類

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

通過集結(jié)類的設計便可實現(xiàn)特定徑路，層層遞歸的業(yè)務邏輯。

3.2 改變經(jīng)由類

改變經(jīng)由類是特定徑路中最為常見的一種類型，按照業(yè)務邏輯不同可分為兩小類：原經(jīng)由改變經(jīng)由類、發(fā)到域改變經(jīng)由類，下面舉例說明。

文獻[5]中第十二條上海、南昌相關線中規(guī)定“（四）凡經(jīng)向塘西支點裝到成都局（廣漢-廣元間各站除外）的重車，均經(jīng)滬昆線、按株洲北支點運輸?！贝藯l是最為普通的原經(jīng)由改變經(jīng)由類，條文中并沒有規(guī)定具體有哪些發(fā)站是經(jīng)由向塘西支點的，發(fā)站是要經(jīng)過最短徑路和特定徑路計算來判定的，每一個到站都有可能對應著不同的發(fā)區(qū)域。

文件中第十三條進出西南相關線中規(guī)定“（三十三）成都局成昆線各站裝到南寧局黎塘以南各站重車，均經(jīng)攀枝花分界站運輸?！?。此條為典型的發(fā)到域改變經(jīng)由類，條文中明確地說明了發(fā)到域的范圍，在此不再贅述。

3.3 修改里程類

修改里程類是徑路里程統(tǒng)計中較為特殊的一種類型，主要用于計費里程的修改。如貨物運價里程表中對淮南線的規(guī)定“裕溪口至蕪湖東間按50 km計費”，但實際里程只有20 km，所以在計算路網(wǎng)最短徑路時按照20 km計，而在里程統(tǒng)計時，上海鐵路局里程加30 km、計費里程加30 km、基金里程加30 km、電氣化里程加30 km。類似這樣的實例，路網(wǎng)中還存在多處，需要在算法設計中特殊對待。

特定徑路參數(shù)語言的設計諸如此類，但在參數(shù)語言編譯算法上仍是一個非常復雜的工程，區(qū)域的定義、特定徑路的對接、執(zhí)行的效率和圖形的展示需要設計者精心設計，并且最為關鍵的是對業(yè)務邏輯必須有最全面的掌握。

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

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

4 結(jié)束語

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