汪建偉，宋一丁，董立峰，賈斌

(1.軍事交通學(xué)院，天津300161;2.總后后勤科學(xué)研究所，北京100071)

1 引言

目前，鐵路輸送仍是我軍陸地防御和作戰(zhàn)的一種主要遠程機動方式，部隊鐵路輸送方案編制的核心內(nèi)容之一是確定輸送路徑?？焖儆行У剡x取最優(yōu)路徑對編制部隊鐵路輸送方案具有重要意義。本文設(shè)計了以輸送時間最短為目標(biāo)的基于輔助的雙向A*路徑搜索算法，通過綜合優(yōu)化設(shè)計，使得算法中的路網(wǎng)數(shù)據(jù)減少，存儲結(jié)構(gòu)清晰，搜索范圍縮小，計算速度加快，更符合快速編制部隊鐵路輸送方案要求。

2 路網(wǎng)數(shù)據(jù)模型

路網(wǎng)是搜索最優(yōu)路徑的基礎(chǔ)和對象，而要能夠在路網(wǎng)上進行最優(yōu)路徑的搜索，必須將其轉(zhuǎn)換為算法能夠識別的信息，并以合理的結(jié)構(gòu)組織和存儲。

2.1 路網(wǎng)的表示方法

道路網(wǎng)絡(luò)的經(jīng)典表示方法是賦權(quán)有向圖。通常是分別存儲點狀實體——節(jié)點、線狀實體——兩節(jié)點間的路段、節(jié)點和路段的屬性信息，以及實體間的拓撲關(guān)系［1］(主要是連通性和方向性)。道路網(wǎng)的規(guī)模是影響最短路徑搜索時間的主要因素，當(dāng)在大規(guī)模路網(wǎng)上進行最優(yōu)路徑搜索時，如果將路網(wǎng)中的所有路段和結(jié)點平等對待，其計算量的龐大、搜索效率的低下是可想而知的。鐵路路網(wǎng)的站點與一般網(wǎng)絡(luò)中的節(jié)點不同，其中絕大部分站點只和2個站點關(guān)聯(lián)，連接3個站點及更多站點的車站只不過占百分之十幾。針對這種情況，本文采用了二次讀入邊數(shù)據(jù)的方法［2］來表示鐵路路網(wǎng)。

(1)支點到支點的網(wǎng)絡(luò)表示。首先忽略全部中間站點(連接兩個邊的站點)，形成一個簡單的只有支點(連接三個及三個以上的站點)的網(wǎng)絡(luò)。如圖1(a)的網(wǎng)絡(luò)可以簡化為圖1(b)所示的網(wǎng)絡(luò)。如果要求計算從支點到支點的最短路徑，那么在這個簡化的網(wǎng)絡(luò)上進行即可。

(2)中間站點到發(fā)的網(wǎng)絡(luò)表示.如果出發(fā)站點是中間點，可以查詢該站點至所在邊兩端站點的距離，暫時從網(wǎng)絡(luò)中刪除這條邊，并增加1個站點Vk及2條邊(Vk，Vi)和(Vk，Vj)，其邊長分別等于從數(shù)據(jù)庫讀出的該站點距這2個支點的距離。

如果到達站點是中間點，那么處理方法同上。通過對鐵路網(wǎng)絡(luò)作了如上處理，全國路網(wǎng)即可表示成一個簡化的網(wǎng)絡(luò)，在這個網(wǎng)絡(luò)上進行最短路徑搜索其效率將得到明顯的提高。

2.2 路網(wǎng)的存儲結(jié)構(gòu)

在確定了路網(wǎng)的表示方法之后，下一步的工作就是利用合理的數(shù)據(jù)結(jié)構(gòu)將路網(wǎng)存儲起來，使得路徑選擇算法能夠識別路網(wǎng)，并在路網(wǎng)上進行最優(yōu)路徑的計算。衡量數(shù)據(jù)結(jié)構(gòu)優(yōu)劣的標(biāo)準(zhǔn)有兩個:一是存儲量小，冗余度小;二是便于路徑選擇算法操作。

鐵路路網(wǎng)作為大型稀疏網(wǎng)絡(luò)，具有很多特點。針對路網(wǎng)特點，由Dial等人提出目前公認的一種特別適合道路網(wǎng)絡(luò)特點的存儲結(jié)構(gòu)——前向關(guān)聯(lián)邊結(jié)構(gòu)［3］。該結(jié)構(gòu)的核心在于將由同一個節(jié)點出發(fā)的所有弧存放在一起，在選擇路徑時可以避免一些不必要的判斷。采用前向關(guān)聯(lián)邊存儲結(jié)構(gòu)，可以利用節(jié)點關(guān)聯(lián)的弧段數(shù)目來控制循環(huán)次數(shù)，避開了大量不必要的循環(huán)運算。本文在此基礎(chǔ)上結(jié)合實際需求對弧段權(quán)重進行了重排。

這種存儲結(jié)構(gòu)的一個明顯好處在于使得路網(wǎng)數(shù)據(jù)結(jié)構(gòu)更加清晰。前向關(guān)聯(lián)邊存儲結(jié)構(gòu)占用的存儲空間少，還能方便地對某一給定節(jié)點發(fā)出的所有弧段進行操作，提高了算法的搜索效率。此外，通過對權(quán)重數(shù)組中各弧段的權(quán)值按大小進行排列，使得在路徑搜索時不再需要比較弧段權(quán)重值，進一步提高了搜索速度。

3 路徑選擇算法的設(shè)計

3.1 基于輔助信息的雙向A*搜索算法

圖2所示為Dijkstra［4］、A*［5］及雙向A* 三種最短路徑算法搜索范圍的比較，從圖中可以看出雙向A*搜索算法在搜索空間上較前兩個算法減少了很多。雙向A*搜索算法的時間復(fù)雜度為O)，其中b為網(wǎng)絡(luò)結(jié)點的平均度數(shù)，d為從起點到終點最短路徑搜索深度。由此可見，雙向A*搜索算法無論從空間復(fù)雜度還是時間復(fù)雜度上都明顯優(yōu)于前兩個算法。該算法的缺點在于復(fù)雜度較大，一般僅用于復(fù)雜的圖形，而鐵路路網(wǎng)就屬于復(fù)雜的大型稀疏網(wǎng)絡(luò)。

圖2 算法搜索范圍比較

在鐵路運輸中，當(dāng)給定始發(fā)站和到達站后，列車可能通過路徑的行政區(qū)域就確定了。例如列車從貴陽站開行至石家莊站，一般可能通過的行政區(qū)域包括貴州、重慶、陜西、山西、河南、湖南、湖北、山東和河北。根據(jù)鐵路運輸?shù)倪@個特點，本文設(shè)計了用于限定搜索區(qū)域的輔助信息數(shù)據(jù)庫。在擴展某一節(jié)點前，首先要判定該節(jié)點是否在限制的搜索區(qū)域之內(nèi)。如果該節(jié)點在限制的搜索區(qū)域內(nèi)則擴展之，否則，認為該節(jié)點不在最短路徑上，不予考慮。算法利用知識來限定搜索區(qū)域，不僅縮小了算法的搜索范圍，而且因為限制區(qū)域是給定的，不需要進行計算，也沒有增加算法的復(fù)雜度。為了便于描述算法搜索過程，本文定義以下相關(guān)符號:x表示起始結(jié)點s或目標(biāo)結(jié)點t，若x=s，則ˉX=t，若x=t，則ˉX=s;gx(n)是在狀態(tài)空間中從結(jié)點x到當(dāng)前節(jié)點n的實際代價;hx(n)從當(dāng)前節(jié)點n到目標(biāo)節(jié)點ˉX最佳路徑的估計代價;f=gx(n)+hx(n)是從初始點x經(jīng)由節(jié)點n到目標(biāo)點ˉX的估價函數(shù);x-OPEN由算法所擴展的結(jié)點集，等待進一步擴展;x-CLOSED由算法所擴展的且不在x-OPEN中的結(jié)點集。

改進后的雙向A*搜索算法具體步驟如圖3所示。

圖3 改進的雙向A*算法流程圖

3.2 估值函數(shù)t(n)的設(shè)計

估值函數(shù)能否正確選取將直接關(guān)系到算法成功與否，而函數(shù)的確定卻與實際情形密切相關(guān)。算法使用者可以依據(jù)實際情況，選擇f(n)的具體形式。估值函數(shù)的估價值應(yīng)與實際值盡量接近，這就要求啟發(fā)函數(shù)h(n)的啟發(fā)信息越多越好，即h(n)的值盡可能大，提高算法搜索效率。另一方面，為了保證算法的正確性，我們又需要適當(dāng)?shù)亟档凸纼r函數(shù)的值，擴大搜索范圍。因而可以根據(jù)實際對求解速度和正確性的要求而設(shè)計出不同的估值函數(shù)，使之更具彈性。

對于路網(wǎng)中路徑選擇問題，已經(jīng)確定輸送時間最短為最優(yōu)目標(biāo)。輸送時間一般由單梯隊運行時間和部隊輸送進度兩部分組成，故可定義部隊從起始站點經(jīng)過站點n到達終點輸送時間的估值函數(shù)為:

式(1)中，N為列車梯隊數(shù)，h為當(dāng)前已選路徑中第一限制區(qū)段的通過能力，f為鐵路線路軍用占用率，g(n)為從起始站點到達當(dāng)前站點n的輸送時間實際代價函數(shù)，h(n)為當(dāng)前站點n到達終點的輸送時間啟發(fā)函數(shù)。

式(2)中，wi為兩車站之間區(qū)段長度，vi為列車在區(qū)段i上的運行速度。

式(3)中，D為兩點間的直線距離計算公式，vmax為已選路徑的區(qū)段中列車最大運行速度，β為常量系數(shù)，由輔助信息數(shù)據(jù)庫提供。β值是這樣確定的:假設(shè)某行政區(qū)域內(nèi)相鄰兩站點實際距離為S實，直線距離為S直，行政區(qū)域內(nèi)任意相鄰站點實際距離與直線距離比值最小值就是該區(qū)域的常量系數(shù)，即βi=min

4 實驗及結(jié)果分析

為驗證改進的算法，本文繪制了部分鐵路線路圖(圖4)，共包含87個站點和124條鐵路區(qū)段，利用Java 6.0、Oracle 9i和Myeclipse 8.0作為實驗環(huán)境，分別采用Dijkstra算法、A*算法、雙向A*搜索算法和本文設(shè)計的基于輔助信息的雙向A*搜索算法求解四對站點的最優(yōu)路徑。

各算法運行情況比較見表1。運行結(jié)果顯示各算法都能找到最優(yōu)路徑，但各算法在搜索時間和遍歷節(jié)點次數(shù)上存在著一定的差異。從表中可以看出，Dijkstra算法搜索時間是最長的，遍歷節(jié)點次數(shù)也是最多的，因為該算法的搜索基本上是以起點為圓心以圓的方式向外拓展;A*算法從所搜時間和遍歷節(jié)點次數(shù)兩個方面都優(yōu)于Dijkstra算法，但優(yōu)勢不是很明顯，主要是給定的鐵路線路圖站點和線路區(qū)段數(shù)較少，沒有充分發(fā)揮A*算法的特點;雙向A*搜索算法在時間上優(yōu)于前兩個算法，但遍歷節(jié)點次數(shù)卻多于A*算法，這一方面是因為給定的鐵路線路圖相對簡單，雙向選擇算法難以發(fā)揮優(yōu)勢，另一方面是因為我們在程序中凡有節(jié)點放入源點或目標(biāo)點的OPEN表時算法計數(shù)均加1，一些點在實際搜索過程中并沒有使用;本文設(shè)計的基于輔助信息的雙向A*搜索算法，從搜索時間和遍歷節(jié)點次數(shù)上相對前面的算法都是最少的，這充分證明了改進算法的先進性。

表1 四種算法的運行情況比較(時間單位:ms)

圖4 鐵路輸送路徑選擇流程圖

5 結(jié)語

本文從部隊快速選擇鐵路輸送最優(yōu)路徑的需求出發(fā)，根據(jù)鐵路路網(wǎng)特點，從路網(wǎng)表示、存儲結(jié)構(gòu)、搜索區(qū)域、估值函數(shù)四個方面對雙向A*路徑搜索算法進行了優(yōu)化，提高了搜索效率，具有較好的實用性，可以應(yīng)用于路徑選擇相關(guān)的決策信息系統(tǒng)中。

1 夏立民.交通系統(tǒng)中最優(yōu)路徑選擇算法的研究［D］.北京:首都大學(xué)，2007.

2 楊斌，魏佳.鐵路超限貨物最短運輸徑路查詢系統(tǒng)的研究［J］.鐵道運營技術(shù)，2010，16(2):1-7.

3 萬瑋，劉曄，李立宏，等.采用聯(lián)合優(yōu)化方式的最佳路徑算法研究［J］.計算機工程與應(yīng)用，2007，43(30):97-100.

4 DIJKSTRA E W.A Note on two Problems in Connexion with Graphs［J］.Numerische Math-ematik，1959(1):269-271.

5 HART E P，NILSSON N J，RAPHAEL B.A Formal basis for the Heuristic Dtermination of Minimum Cost Paths［C］.IEEE Trans.Sci.Cyhern，1968，SCC-4(2):100-107.