基于A H P-Dijkstra 算法的高速鐵路選線方案研究

高鵬展

（中國鐵路設(shè)計集團(tuán)有限公司，天津 300000）

引言

隨著國家經(jīng)濟(jì)發(fā)展，旅客出行需求提高，列車運(yùn)行速度提升。依據(jù)2020 年4 月國家發(fā)展改革委、交通運(yùn)輸部關(guān)于印發(fā)《長江三角洲地區(qū)交通運(yùn)輸更高質(zhì)量一體化發(fā)展規(guī)劃》以及地方發(fā)展規(guī)劃，部分鐵路線路需要進(jìn)行改擴(kuò)建。而鐵路選線方案設(shè)計是鐵路勘察設(shè)計中的基礎(chǔ)工作, 目前在鐵路選線方案設(shè)計方面有許多研究方法。其中，孟曉鵬[1]等人通過層次分析法，對內(nèi)馬鐵路內(nèi)羅畢公園生態(tài)選線方案進(jìn)行了評估。羅圓[2]等人基于變權(quán)理論提出了鐵路選線方案中的評估指標(biāo)體系，利用云模型，對選線方案進(jìn)行了有效評估。董賢凱[3]利用風(fēng)險決策理論對不同地質(zhì)條件進(jìn)行不同風(fēng)險等級評估，并加入工程投資期望換算，使得評估結(jié)果更加科學(xué)化。

從以上的研究中可以看出，都是將該段鐵路選線看作線性堆疊的過程，再選線方案進(jìn)行評估中，忽略了鐵路線路的網(wǎng)狀特征與各個節(jié)點之間的相互聯(lián)系。而在其他的研究方向中，如高鵬展[4]利用Dijkstra 算法對旅客的出行距離、時間、費(fèi)用三方面進(jìn)行了分析，從而對旅客出行行為得出了更為明晰的結(jié)論。因此本研究提出，采用運(yùn)輸網(wǎng)絡(luò)的思維，將鐵路選線過程中的影響因素量化為網(wǎng)絡(luò)圖中的損失值，進(jìn)而得出更加科學(xué)的選線方案。

1 Dijkstra 算法

Dijkstra 算法是用于計算復(fù)雜有向賦權(quán)圖中，從起點位置到終點位置的算法。對于任意賦權(quán)有向圖G=（V，E，W），其中：V 代表節(jié)點的集合，即V={s，v1，v2，…vn}；E 代表連接邊的集合；W 代表邊上權(quán)重的集合；s 表示源點，對于任一節(jié)點，將源點到該節(jié)點的距離記為dist[v，vi]，將源點到該節(jié)點的最小距離記為short[s，vi]，其基本運(yùn)算過程為

a. 令S={s}。

b.計算dist[s，s]=0。

c. 對于任意vi∈V-S，計算dist[s，vi]，如果dist[s，vj]+ωj，i＜dist[s，vi]，則令dist[s，vi]=dist[s，vj]+ωj，i，其中無法到達(dá)的點將其距離記為∞。

e. 重復(fù)步驟c、d，直到S=V。

通過以上步驟可以在有向賦權(quán)圖中，找到從源點到終點的最短路徑，因此本研究以此為主要思路，以合肥至武漢段的高速鐵路為案例，將其在計劃內(nèi)的15個地區(qū)抽象為網(wǎng)絡(luò)圖中的節(jié)點，見圖1。

圖1 各個地區(qū)節(jié)點之間相對位置關(guān)系網(wǎng)絡(luò)圖

2 鐵路主要概況

文章研究的路段主要位于安徽、湖北省境內(nèi)，線路所經(jīng)地區(qū)地處北亞熱帶長江中下游濕潤季風(fēng)氣候區(qū)，無特殊不利于建造鐵路天氣。在環(huán)保控制點與地質(zhì)條件方面，由于存在大別山國家森林公園和天馬國家自然保護(hù)區(qū)，因此節(jié)點K-G、G-L、L-H、H-M、M-I、I-N 之間互聯(lián)互通困難；線路經(jīng)過地區(qū)其地層巖性復(fù)雜多樣，C-F、D-G、E-G 之間工程地質(zhì)條件差；J-F 與F-D 之間存在既有鐵路。

結(jié)合上述不利因素，各個節(jié)點之間實際可行網(wǎng)絡(luò)圖見圖2。

圖2 實際可行狀況下各個站點連通網(wǎng)絡(luò)圖

3 選線評估指標(biāo)

在選線過程中需要進(jìn)行各項指標(biāo)的綜合比選，因此評價指標(biāo)體系的建立關(guān)乎該項方案評價的優(yōu)劣，本研究對于該鐵路項目中進(jìn)行過程中，通過結(jié)合李東俠[5]文章中對重要政治經(jīng)濟(jì)據(jù)點、順直度、地質(zhì)條件等因素，楊鵬[6]在選線過程中認(rèn)為應(yīng)該對鐵路經(jīng)由地區(qū)經(jīng)濟(jì)、文化、環(huán)境等條件進(jìn)行綜合考慮。本研究主要選取了線路長度、經(jīng)濟(jì)水平、人文因素以及線路順直度4個主要影響因素。

4 評估指標(biāo)的計算與分析

4.1 線路長度

鐵路線路長度主要影響鐵路后期修建過程中產(chǎn)生的實際費(fèi)用問題，關(guān)于該方面的研究文獻(xiàn)較多，此處不做贅述，本研究將各個節(jié)點的維度行了統(tǒng)計，由此可以得到各個節(jié)點之間的距離，并將該距離作為施工長度權(quán)重。

4.2 經(jīng)濟(jì)水平

由于該條線路穿過我國14 個集中連片特困地區(qū)之一的大別山區(qū)，麻城、金寨均屬國家級貧困縣。因此本研究對于以上穿越站點進(jìn)行了地區(qū)經(jīng)濟(jì)發(fā)展分析，將其當(dāng)?shù)亟?jīng)濟(jì)發(fā)展中的生產(chǎn)總值狀況進(jìn)行統(tǒng)計分析。

4.3 人文因素

在沿線各個站點之中存在革命先烈誕生地，紅色革命性質(zhì)濃厚。黃永林[7]對紅色旅游景點發(fā)展?fàn)顩r進(jìn)行了分析。黃常軍[8]對金寨的革命歷史與現(xiàn)階段的扶貧成果進(jìn)行分析。為了量化鐵路選線中的地區(qū)人文因素，本研究通過文獻(xiàn)調(diào)研的方式，獲取了有關(guān)相應(yīng)地區(qū)的人文因素研究現(xiàn)狀。

4.4 線路順直度

高速鐵路選線要充分保證高速行車條件，在滿足技術(shù)標(biāo)準(zhǔn)的情況下，使線路盡可能順直，本研究提出以各個路段與線路主要方向的余弦相似度作為主要度量依據(jù)進(jìn)行分析。本研究中的武漢市至長江新城之間為固定的路線，因此，將長江新城至合肥市設(shè)為該路線的主要方向，將主要方向向量記為，其他各個節(jié)點之間的斜率向量記為，其中（x1，y1）表示斜率向量的坐標(biāo)點，（x2，y2）表示斜率向量的坐標(biāo)點，其余弦相似度的計算公式見公式(1)。

4.5 各個指標(biāo)權(quán)重匯總

通過對以上各個指標(biāo)的原始數(shù)據(jù)分析，可由節(jié)點經(jīng)緯度計算得到施工長度權(quán)重；將路徑兩端地區(qū)的生產(chǎn)總值與文獻(xiàn)研究數(shù)量均值作為該段路徑的經(jīng)濟(jì)權(quán)重與人文因素權(quán)重；各路段與鐵路整體走向之間的余弦相似度作為路段的順直度權(quán)重，見表1。

表1 各路段與鐵路整體走向之間的余弦相似度

5 方案比選

由于以上4 種指標(biāo)各自的單位不同，要綜合考慮4 種指標(biāo)，需要進(jìn)行綜合處理，對于線路長度權(quán)重和沿途經(jīng)濟(jì)水平權(quán)重而言需要將其進(jìn)行歸一化，其計算方式見公式(2)、公式(3)。

對于線路的順直度而言，其余弦越接近于1，表明該路段鐵路越與總路線主要方向相一致。同理，對于以上各個地區(qū)的文化研究發(fā)展?fàn)顩r越多，越說明該地文化與旅游事業(yè)發(fā)展越好。因此文章參考李寶鳳[9]提出了一項將最長路轉(zhuǎn)化為最短路的方法，將關(guān)于預(yù)設(shè)站點的順直度權(quán)重與人文權(quán)重進(jìn)行了轉(zhuǎn)化，其轉(zhuǎn)化公式分別見公式(4)、公式(5)。

在完成以上4 種指標(biāo)的轉(zhuǎn)化之后，還需要對以上指標(biāo)進(jìn)行不同權(quán)重賦值。本研究將以上4 種指標(biāo)采用AHP 算法（層次分析法）進(jìn)行分析，邀請相關(guān)行業(yè)內(nèi)部6 位專家對于以上4 種指標(biāo)進(jìn)行了重要程度兩兩比較，得到6 位專家的判斷矩陣，見公式(6)，通過計算可知均通過一致性檢驗。

5.1 相似度計算

由上文中以上6 位專家的判斷矩陣可以通過余弦相似度進(jìn)行計算，余弦相似度的計算原理已在順直度評估中進(jìn)行了說明，需要將以上6 個判斷矩陣按列展開。通過計算余弦相似度，可以得到專家之間判斷矩陣的相關(guān)程度，并計算每個專家的累計值rk。最后，通過歸一化的方式得到每位專家的判斷矩陣權(quán)重。其運(yùn)算過程見公式(7)，得出λ1=0.157 7、λ2=0.196 5、λ3=0.110 5、λ4=0.144 6、λ5=0.197 4、λ6=0.193 4。

5.2 差異度計算

根據(jù)6 位專家的判斷矩陣，計算其之間的差異度，從而確保減少偏離群體意見的判斷矩陣權(quán)重。令bkj為第k 位專家判斷矩陣下三角的第j 個元素值，σk表示第k 個專家的評價結(jié)果差異性，在計算完成之后還需對對σk進(jìn)行歸一化，計算過程見公式(8)。式中：φk表示第k 個專家的判斷矩陣與所有專家群組整體評價的綜合結(jié)果的差異度，得出φ1=0.184、φ2=0.161、φ3=0.236、φ4=0.180、φ5=0.124、φ6=0.113。

5.3 判斷矩陣綜合權(quán)重計算

為了均衡考慮專家判斷矩陣的權(quán)重，將相似度與差異度聯(lián)合進(jìn)行考慮，形成綜合權(quán)重，計算過程見公式(9)，得到各個專家判斷矩陣的綜合權(quán)重，即γ1=0.153 0、γ2=0.196 1、γ3=0.100 4、γ4=0.140 9、γ5=0.205 6、γ6=0.204 0。

5.4 共識矩陣計算與檢驗

根據(jù)以上綜合權(quán)重，可以將以上6 位專家的判斷矩陣形成共識矩陣S，共識矩陣中各個元素的計算方式見公式(10)，aij（k）為第k 為專家判斷矩陣中第i 行第j 列的元素。

根據(jù)以上計算方式可以得到以上6 位專家聯(lián)合形成的的共識矩陣，結(jié)果見公式(11)。通過幾何平均法計算得到矩陣S 其特征向量為ω= [0.248 7 0.317 7 0.135 2 0.298 4]T，并且通過計算得到C.R.值為0.005 22，可知通過一致性檢驗，得到的權(quán)重可以用于計算。

5.5 計算最終方案

將以上各個參數(shù)輸入到以上各個損失指標(biāo)中，運(yùn)算過程見公式(12)，即令a1=0.248 7、a2=0.317 7、a3=0.135 2、a4=0.298 4，其中a1、a2、a3、a4分別表示線路長度損失值、經(jīng)濟(jì)水平損失值、人文因素?fù)p失值以及順直度損失值的參數(shù)。通過計算可以得到該網(wǎng)絡(luò)中的綜合損失值，運(yùn)算結(jié)果見表2。

表2 綜合損失值計算結(jié)果

通過獲取到的以上綜合損失值，將其賦值到網(wǎng)絡(luò)圖中，見圖3，并利用Dijkstra 算法進(jìn)行計算，以算法迭代步驟為基礎(chǔ)，在visual studio2013 中構(gòu)建了綜合損失函數(shù)，得到最短路徑節(jié)點為：A→B→F→G→H→I→O，鐵路選線方案應(yīng)為：武漢市→長江新城→麻城北→南溪→金寨東→六安北→合肥市。該方案與專家組的推薦方案一致。

圖3 向網(wǎng)絡(luò)圖中賦予綜合損失值

6 結(jié)論

本研究利用Dijkstra 算法對合肥至武漢段高速鐵路選線方案，提出了新的解決方法，即將現(xiàn)有具體地區(qū)站點抽象化為網(wǎng)絡(luò)圖中的節(jié)點，將影響選線方案的主要因素作為該網(wǎng)絡(luò)圖中的路徑權(quán)重，從而得到更加科學(xué)化的選線結(jié)果。在影響選線因素之中著重分析了線路長度、經(jīng)濟(jì)因素、人文因素以及線路順直度因素，對以上4 個影響因素采用AHP(層次分析法)，通過計算各個專家判斷矩陣的相似度與區(qū)別度，求得綜合權(quán)重，通過了一致性檢驗，計算得到綜合損失值。利用Dijkstra 算法求得最優(yōu)選線方案，與專家選線方案一致，證明本研究提出的AHP-Dijkstra 算法具有一定實際應(yīng)用價值。