鐵路網多路徑搜索技術的實踐

李向農

(中鐵工程設計咨詢集團有限公司，北京 100055)

鐵路網多路徑搜索技術即鐵路網中點對之間一條以上較短路徑的計算技術，是鐵路線網分析、徑路比較和OD(Original Destination，即客貨流起點至終點)分配等應用的基礎。

鐵路網多路徑搜索技術簡稱鐵路KSP算法[1]，為通用KSP算法在鐵路網絡計算問題中的應用。國外學者Hoffman和Pavley在1950年首先提出了該問題[2]，并將其分為一般KSP算法和簡單路徑KSP算法。鐵路網多路徑計算求出的路徑不能有環形子路徑，必須用簡單路徑KSP算法求解，同時考慮經濟性和多種運輸方式的競爭。普通簡單路徑KSP算法求出的路徑難以滿足鐵路網實用性要求，需對路徑增加更為嚴格的限制條件。KSP算法在各行各業中都有廣泛應用[3-4]，國內外學者對其有大量研究成果，有Yen的經典算法[5]，也有Martins、Hershberger、Maxel、Suri等對Yen算法的不斷改進[6-7]；通過擴展Dijkstra算法[8]，國內學者柴登峰與張登榮[9]、袁紅濤[10]、高松[11]等也提出了對該問題的多種優化算法；現代優化技術也應用到KSP問題，如馬燁[12]的遺傳算法，黃則漢[13]的蟻群算法，林潔[14]的人工免疫算法等。上述學者算法的共同特征：一是所針對的網絡為一般有向圖，并沒有考慮鐵路網特點而進行優化或簡化；二是主要計算一對節點間的多條路徑。而在鐵路網絡應用如OD分配中，經常需要知道所有節點間的多條路徑(當然通過對每對節點進行多路徑計算，可以得到所有節點間的多條路徑，但其計算時間將會大大延長)，而且記錄所有路徑所需的內存空間也將非常巨大；三是所求路徑為普通無環路徑，沒有考慮鐵路運輸的合理路徑。以下提出一種具有鐵路網絡特征、實用可行和滿足眾多鐵路網絡應用的多路徑計算方法。

1 鐵路網的抽象及有關概念

1.1 鐵路網絡及其特性

鐵路網可表示為有向圖N=(S，L)，其中N為鐵路網，S為鐵路站點集合，可表示鐵路車站、樞紐編組站、OD小區重心點等。對于X個站點的鐵路網，設i為站點，則S={1，2，i，,X}；L為鐵路區段集合，表示兩站點之間直接連接的鐵路線路，設(i，j)為站點i至站點j的區段，(i，j)∈L，鐵路網分上下行，所以(i，j)和(j，i)成對出現；兩站點之間可能有多條鐵路線直接相連，但為了計算和路徑表示方便，可規定兩站點之間只允許一條鐵路線直接相連，對于有兩條及以上鐵路線相連的相鄰站點對，可在其中一條線上強制增加站點來區分，并標記為不可簡化；設w(i，j)為區段(i，j)的權重，可表示相鄰兩站點間鐵路長度、運行時間或廣義權重等，對鐵路網來說，w(i，j)和w(j，i)相差不大，為簡化計算，可令w(i，j)=w(j，i)。

1.2 鐵路網路徑及合理路徑

對于上述鐵路網，從站點o到站點d之間的路徑可表示為r(o，d)=(o，s1，s2，，sk，d)，其中s1，s2，，sk為從站點o到站點d依次經過的相鄰站點，且o，si，d互不相同(無環)。

將站點o到站點d的路徑中相鄰站點間區段的費用相加可得路徑長度，記為dist(o，d)。站點o到站點d的所有路徑中，長度最短的路徑為最短路徑，記為minr(o，d)，其長度記為mind(o，d)，稱dist(o，d)-mind(o，d)為路徑r(o，d)的繞行長度，記為a(o，d)。

在鐵路運輸實踐中，a(o，d)經常有一定的范圍，可用最短路長度mind(o，d)的相對倍數來表示；同時當mind(o，d)很大時，mind(o，d)倍數也將很大，造成繞行長度過大，在現實中不可能發生，所以a(o，d)應有一個絕對的最大控制值M；再則，為保持長路徑和短路徑繞行控制的一致性，一條鐵路合理路徑中，其子路徑應全部滿足同樣的繞行控制，稱滿足以上繞行要求的路徑為合理路徑，即站點o至站點d的合理路徑滿足以下條件：

a(o，d)≤c×mind(o，d)且a(o，d)≤M

(1)

(其中c為大于1的數值，一般可取1～1.5)；

a(i，j)≤c×mind(i，j)且a(i，j)≤M

(2)

(其中i∈r(o，d)，j∈r(o，d)，且i≠j)。

2 鐵路網的簡化

2.1 鐵路網簡化的概念

鐵路網的復雜性一般以其所含站點和區段數量來衡量，實際鐵路網的站點數量往往很大，如我國鐵路網目前車站數達到6 000個以上，如果按照原始鐵路網絡進行多路徑搜索計算，其時間復雜性和內存空間占用都將達到不可忍受或不可能的程度。所以，在實際應用中，都要將原始網絡進行簡化。如我國鐵路OD統計將全國鐵路劃分為483個OD小區，將OD小區重心點作為路網站點，可大大降低網絡復雜度，又對研究結論不會造成太大影響；李旭華[15]采用分層思想對網絡進行分級，降低了路網復雜性。本節主要探討在不改變路網多路徑計算最終結果的情況下簡化鐵路網的方法。

2.2 鐵路網站點分類及簡化方法

為簡化網絡，將網絡站點分為枝站點、中間站點和支點。采用遞歸定義法定義枝站點為在鐵路網N(S，L)中相鄰站點非枝站點數不大于1的站點。中間站點定義為在鐵路網N(S，L)中相鄰非枝站點數為2的站點。定義支點為既非枝站點又非中間站點的站點。

圖1為15個站點的鐵路網絡。圖中虛線框內站點為枝站點。有如下特征：一是和站點8組成一個樹形結構；二是兩兩之間只有一條合理路徑；三是刪除這些站點后不會對其他站點間合理路徑個數和長度有影響。

圖1 鐵路網簡化情況示意

站點1、3、7、9為中間站點。有如下特征：一是相鄰非枝站點數為2個；二是刪除這些站點，并將其與2個相鄰的非枝站點拼接后形成的網絡，不影響其他站點間合理路徑個數和長度計算結果。

站點2、4、5、6、8為支點。消除枝站點和中間站點后的路網稱為簡化路網N*(標記為不可簡化的站點且不可刪除)。鐵路網多路徑計算只需在簡化路網上計算支點間的多條路徑。

圖1中，經簡化后的路網只含5個支點，復雜度大大降低。

2.3 鐵路網多路徑檢索

支點與支點間的多路徑檢索只需根據簡化路網上的經由站點遞歸求出。

兩站點都為中間站點的多路徑檢索，其路徑須經由其相鄰支點間路徑。由于一個中間站點有兩個相鄰支點，所以共有4種路徑組合方式，可通過窮舉簡化路網上4個相關支點間的路徑并消除重復路徑求出。兩站點其中之一為中間站點的多路徑檢索為上述情況的特殊情形，可采用類似方法求出。

兩站點中有枝站點的情況下，多路徑檢索分兩種情況，一種為兩枝站點在一個樹形結構下，定義該樹形結構的根為根站點，這時只有一條路徑，可在原路網上向根站點回朔求出；另一種為其他情況，這時可由樹形結構根站點代表相關枝站點進行多路徑搜索求出。

3 鐵路網多路徑計算

一次計算所有站點間最短路徑，比較有效的方法為Floyd法[16]，但Floyd法僅能計算一條最短路徑，為了計算K條較短路徑，需擴展Floyd法。以下多路徑計算采用擴展Floyd法的思路。

設有簡化路網N*(S*，L*)，|S*|=Q，Q為網絡中支點數，需計算所有支點之間的前K條較短路徑。

第一步：初始化。支點i到支點j間的第k短路徑記為rout(i，j，k)={t，w，v，x，y}。其中t為標識數字，唯一標識支點i到支點j間的某條路徑；w為該路徑長度(權重)；v為該路徑所經由的支點；x表示經由支點i到支點v由x標識的路徑;y表示經由支點v到支點j由y標識的路徑。以上表示法可唯一確定N*中一條路徑，通過遞歸函數可提取出路徑所含站點序列。記K維向量R(i，j)={rout(i，j，k)|k=1，2，，K}。構造矩陣Dk={R(i，j)|i=1，2，，Q；j=1，2，，Q}。

對D0中rout(i，j，k)作初始化：對所有支點i=1，2，，Q和j=1，2，，Q，如果支點i和支點j相鄰，則rout(i，j，1).w=w(i，j)，rout(i，j，1).t=ID(某唯一標識數)；否則rout(i，j，1).w=∞(無窮大，表示無此路徑)；對所有k=2，3，，K，rout(i，j，k).w=∞。

第二步：計算Dk，k=1，2，，K。依次由Dk-1計算Dk。

由rout(i，k，kx)和rout(k，j，ky)計算rout(i，j，kr)，更新Dk-1，其中i=1，2，，Q；j=1，2，，Q，kx=1，2，，K，ky=1，2，，K。

對所有i，j，kx，ky作如下計算：rout(i，j，kr).w=rout(i，k，kx).w+rout(k，j，ky).w；rout(i，j，kr).v=k；rout(i，j，kr).x=rout(i，k，kx).t；rout(i，j，kr).y=rout(k，j，ky).t。如果rout(i，j，kr).w=∞，或者rout(i，j，kr).w≥rout(i，j，K).w，或者該路徑不符合合理路徑要求，則直接舍棄并計算下一條路徑；否則rout(i，j，kr).t=ID(分配唯一標識數)，將該路徑按長度升序插入R(i，j)中，R(i，j)中最后一個元素自動舍棄。循環更新Dk-1，得到Dk。

在鐵路網中，利用w(i，j)=w(j，i)，在第二步計算中，可只處理i

4 效果分析

Floyd算法時間復雜度為O(n3)，其中n為網絡節點數，由于本算法先對路網進行了簡化，僅對鐵路網中的支點應用Floyd算法，可有效降低計算時間。以全路貨運干線網和高速客運鐵路網為例，全路貨運干線網站點為623個，簡化后支點為287個，參加計算的站點數減少53.9%，則計算時間可降低90.2%；高速客運鐵路網站點127個，支點100個，參加計算的站點數減少21.3%，則計算時間可降低51.2%。另外，本算法一條徑路由五元數值組{t，w，v，x，y}表示，若每個數值占內存2字節，則僅用10個字節就可以唯一表示一條徑路，內存占用較小。

采用C++11編程實現本算法，在4核CPU-3.30 GHz、4 G內存64位計算機上進行運算，測試結果如表1所示。

表1 計算時間和內存占用情況

可以看出，貨運干線網上最大路徑數達到2 048條時，計算時間在240 s左右，內存占用在400 Mb以下。對高速客運鐵路網進行同樣條件下的測試，計算時間普遍小于1 s，內存占用在3 Mb以下，一次計算完成后，下次查詢任意兩站點間的多路徑將瞬間完成。

表2 哈爾濱至廣州間主要路徑情況

表2為貨運干線網哈爾濱至廣州間的主要路徑，可以看出，路徑中經由支點數普遍在35個以上，有海量合理路徑，從第1 684條至第2 048條，繞行距離只增加8 km，要列舉全部合理路徑是不可能的。所以，在實際應用中，有必要對路網支點數和合理路徑限制條件進行控制。

5 結束語

鐵路網多路徑搜索技術特別是全部站點間多路徑的一次性計算，在鐵路OD運量分配和車流優化等鐵路規劃、設計和運營工作中有著廣泛的應用。全國鐵路網站點多、區段數量大、計算復雜，在目前常規計算機配置下，尋求在可接受的計算時間和內存占用情形下，一次計算全部站點間多條較短路徑的方法具有重要的現實意義。

鐵路網多路徑搜索的實質為KSP問題，解決全部站點間KSP問題，擴展Floyd法較優。實際測試表明，即使在全路復雜的貨運干線網中計算2048條較優路徑，Floyd方法計算時間和內存占用效果仍然較好，對解決全部站點間KSP問題具有較高的實用價值。現代計算機一般配備多核，利用多核計算機并行計算技術的優化算法，本方法計算時間還有較大的提升空間。