鐵路網(wǎng)多路徑搜索技術(shù)的實(shí)踐

李向農(nóng)

(中鐵工程設(shè)計(jì)咨詢集團(tuán)有限公司，北京 100055)

鐵路網(wǎng)多路徑搜索技術(shù)即鐵路網(wǎng)中點(diǎn)對之間一條以上較短路徑的計(jì)算技術(shù)，是鐵路線網(wǎng)分析、徑路比較和OD(Original Destination，即客貨流起點(diǎn)至終點(diǎn))分配等應(yīng)用的基礎(chǔ)。

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

1 鐵路網(wǎng)的抽象及有關(guān)概念

1.1 鐵路網(wǎng)絡(luò)及其特性

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

1.2 鐵路網(wǎng)路徑及合理路徑

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

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

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

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

(1)

(其中c為大于1的數(shù)值，一般可取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 鐵路網(wǎng)的簡化

2.1 鐵路網(wǎng)簡化的概念

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

2.2 鐵路網(wǎng)站點(diǎn)分類及簡化方法

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

圖1為15個(gè)站點(diǎn)的鐵路網(wǎng)絡(luò)。圖中虛線框內(nèi)站點(diǎn)為枝站點(diǎn)。有如下特征：一是和站點(diǎn)8組成一個(gè)樹形結(jié)構(gòu)；二是兩兩之間只有一條合理路徑；三是刪除這些站點(diǎn)后不會對其他站點(diǎn)間合理路徑個(gè)數(shù)和長度有影響。

圖1 鐵路網(wǎng)簡化情況示意

站點(diǎn)1、3、7、9為中間站點(diǎn)。有如下特征：一是相鄰非枝站點(diǎn)數(shù)為2個(gè)；二是刪除這些站點(diǎn)，并將其與2個(gè)相鄰的非枝站點(diǎn)拼接后形成的網(wǎng)絡(luò)，不影響其他站點(diǎn)間合理路徑個(gè)數(shù)和長度計(jì)算結(jié)果。

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

圖1中，經(jīng)簡化后的路網(wǎng)只含5個(gè)支點(diǎn)，復(fù)雜度大大降低。

2.3 鐵路網(wǎng)多路徑檢索

支點(diǎn)與支點(diǎn)間的多路徑檢索只需根據(jù)簡化路網(wǎng)上的經(jīng)由站點(diǎn)遞歸求出。

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

兩站點(diǎn)中有枝站點(diǎn)的情況下，多路徑檢索分兩種情況，一種為兩枝站點(diǎn)在一個(gè)樹形結(jié)構(gòu)下，定義該樹形結(jié)構(gòu)的根為根站點(diǎn)，這時(shí)只有一條路徑，可在原路網(wǎng)上向根站點(diǎn)回朔求出；另一種為其他情況，這時(shí)可由樹形結(jié)構(gòu)根站點(diǎn)代表相關(guān)枝站點(diǎn)進(jìn)行多路徑搜索求出。

3 鐵路網(wǎng)多路徑計(jì)算

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

設(shè)有簡化路網(wǎng)N*(S*，L*)，|S*|=Q，Q為網(wǎng)絡(luò)中支點(diǎn)數(shù)，需計(jì)算所有支點(diǎn)之間的前K條較短路徑。

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

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

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

由rout(i，k，kx)和rout(k，j，ky)計(jì)算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作如下計(jì)算：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，或者該路徑不符合合理路徑要求，則直接舍棄并計(jì)算下一條路徑；否則rout(i，j，kr).t=ID(分配唯一標(biāo)識數(shù))，將該路徑按長度升序插入R(i，j)中，R(i，j)中最后一個(gè)元素自動舍棄。循環(huán)更新Dk-1，得到Dk。

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

4 效果分析

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

采用C++11編程實(shí)現(xiàn)本算法，在4核CPU-3.30 GHz、4 G內(nèi)存64位計(jì)算機(jī)上進(jìn)行運(yùn)算，測試結(jié)果如表1所示。

表1 計(jì)算時(shí)間和內(nèi)存占用情況

可以看出，貨運(yùn)干線網(wǎng)上最大路徑數(shù)達(dá)到2 048條時(shí)，計(jì)算時(shí)間在240 s左右，內(nèi)存占用在400 Mb以下。對高速客運(yùn)鐵路網(wǎng)進(jìn)行同樣條件下的測試，計(jì)算時(shí)間普遍小于1 s，內(nèi)存占用在3 Mb以下，一次計(jì)算完成后，下次查詢?nèi)我鈨烧军c(diǎn)間的多路徑將瞬間完成。

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

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

5 結(jié)束語

鐵路網(wǎng)多路徑搜索技術(shù)特別是全部站點(diǎn)間多路徑的一次性計(jì)算，在鐵路OD運(yùn)量分配和車流優(yōu)化等鐵路規(guī)劃、設(shè)計(jì)和運(yùn)營工作中有著廣泛的應(yīng)用。全國鐵路網(wǎng)站點(diǎn)多、區(qū)段數(shù)量大、計(jì)算復(fù)雜，在目前常規(guī)計(jì)算機(jī)配置下，尋求在可接受的計(jì)算時(shí)間和內(nèi)存占用情形下，一次計(jì)算全部站點(diǎn)間多條較短路徑的方法具有重要的現(xiàn)實(shí)意義。

鐵路網(wǎng)多路徑搜索的實(shí)質(zhì)為KSP問題，解決全部站點(diǎn)間KSP問題，擴(kuò)展Floyd法較優(yōu)。實(shí)際測試表明，即使在全路復(fù)雜的貨運(yùn)干線網(wǎng)中計(jì)算2048條較優(yōu)路徑，F(xiàn)loyd方法計(jì)算時(shí)間和內(nèi)存占用效果仍然較好，對解決全部站點(diǎn)間KSP問題具有較高的實(shí)用價(jià)值?，F(xiàn)代計(jì)算機(jī)一般配備多核，利用多核計(jì)算機(jī)并行計(jì)算技術(shù)的優(yōu)化算法，本方法計(jì)算時(shí)間還有較大的提升空間。