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

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

1 引言

目前，鐵路輸送仍是我軍陸地防御和作戰(zhàn)的一種主要遠(yuǎn)程機(jī)動方式，部隊鐵路輸送方案編制的核心內(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)上進(jìn)行最優(yōu)路徑的搜索，必須將其轉(zhuǎn)換為算法能夠識別的信息，并以合理的結(jié)構(gòu)組織和存儲。

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

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

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

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

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

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

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

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

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

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

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

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

圖2 算法搜索范圍比較

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

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

圖3 改進(jìn)的雙向A*算法流程圖

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

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

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

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

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

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

4 實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

5 結(jié)語

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

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

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

3 萬瑋，劉曄，李立宏，等.采用聯(lián)合優(yōu)化方式的最佳路徑算法研究［J］.計算機(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.