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

（1.蘭州鐵路局集團(tuán)有限公司 信息處，蘭州 730000；2.中國(guó)鐵道科學(xué)研究院集團(tuán)有限公司 電子計(jì)算技術(shù)研究所，北京 100081）

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

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)中可以稱之為節(jié)點(diǎn)的車站，從圖論的角度上講，就是度＞2的節(jié)點(diǎn)，我們將度＞2的車站、鐵路局分界站、線路屬性臨界站和編組站均視為路網(wǎng)節(jié)點(diǎn)，大約有1 200個(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)的第一要?jiǎng)?wù)是運(yùn)算速度，是平臺(tái)擴(kuò)展和空間利用。在綜合分析當(dāng)前各種計(jì)算機(jī)語(yǔ)言特性的基礎(chǔ)之上，采用C++語(yǔ)言[4]實(shí)現(xiàn)Dijkstra算法。當(dāng)前全路共有近7 000個(gè)車站，最短徑路運(yùn)算速度在10萬(wàn)條／s以上。

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

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

表1 濟(jì)晏線 濟(jì)南-晏城北（國(guó)鐵）

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

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

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

特定徑路參數(shù)語(yǔ)言設(shè)計(jì)是徑路系統(tǒng)能否滿足業(yè)務(wù)邏輯的關(guān)鍵之所在。假如全路的車流徑路都按照最短徑路來(lái)運(yùn)輸，那勢(shì)必會(huì)造成在路網(wǎng)中比較短的線路上車流擁堵，而在路網(wǎng)中較長(zhǎng)的線路上卻沒(méi)有車流，運(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流已占到了全路車流的65%，可見(jiàn)特定徑路比重之高。并且隨著近年來(lái)路網(wǎng)復(fù)雜度的增加，特定徑路的復(fù)雜度也隨之提升，特定徑路參數(shù)語(yǔ)言的設(shè)計(jì)要求：既要滿足復(fù)雜的業(yè)務(wù)需求，又要考慮徑路運(yùn)算的效率，還需兼顧系統(tǒng)參數(shù)維護(hù)的復(fù)雜度。本文將特定徑路業(yè)務(wù)邏輯分為3類：集結(jié)類、改變經(jīng)由類和修改里程類。

3.1 集結(jié)類

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

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

3.2 改變經(jīng)由類

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

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

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

3.3 修改里程類

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

特定徑路參數(shù)語(yǔ)言的設(shè)計(jì)諸如此類，但在參數(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)東-撈刀河-廣州西，里程為2 611 km。再以文獻(xiàn)[5]為特定徑路依據(jù)，進(jìn)行特定徑路參數(shù)語(yǔ)言的編寫，所得特定徑路的經(jīng)由和里程完全符合《全路車流徑路查詢系統(tǒng)》的查詢結(jié)果，如武威南到榆次站的徑路為武威南-迎水橋-定邊-綏德-榆次，里程為982 km，并且徑路計(jì)算速度在Win 32環(huán)境下達(dá)到5萬(wàn)條／s以上。

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

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