改進(jìn)Dijkstra算法在大型城市軌道交通網(wǎng)計(jì)價(jià)系統(tǒng)中的應(yīng)用*

謝建平，陳治亞，鄧連波，謝宜斌，楊 坤

(1.中南大學(xué) 交通運(yùn)輸工程學(xué)院，湖南 長沙 410075；2.長沙市軌道交通集團(tuán)有限公司，湖南 長沙 410133)

隨著城市地鐵建設(shè)的迅猛發(fā)展，國內(nèi)外眾多城市地鐵線路均已達(dá)到網(wǎng)絡(luò)化運(yùn)營規(guī)模。這將使得兩個(gè)站點(diǎn)間存在多條行走路徑，以哪條路徑作為計(jì)價(jià)路徑，才能確保其計(jì)價(jià)的科學(xué)性、合理性，是當(dāng)前軌道交通行業(yè)研究的熱點(diǎn)課題之一。

針對(duì)地鐵兩個(gè)站點(diǎn)間距離的長短對(duì)軌道交通計(jì)價(jià)的影響，國內(nèi)外許多專家學(xué)者對(duì)此進(jìn)行了深入的研究。文獻(xiàn)[1]通過構(gòu)建城市客運(yùn)系統(tǒng)整體出行時(shí)間最小的雙層規(guī)劃模型，研究了城市軌道交通系統(tǒng)在城市客運(yùn)結(jié)構(gòu)中的作用。文獻(xiàn)[2-6]通過建立模型對(duì)票價(jià)策略進(jìn)行了優(yōu)化，但未對(duì)軌道交通成網(wǎng)后各車站間票價(jià)計(jì)算方式進(jìn)行深入探討。文獻(xiàn)[7-18]分別就節(jié)點(diǎn)約束型、改進(jìn)的Dijkstra算法的最短路程計(jì)算，基于結(jié)合 Dijkstra算法的信息素遞減蟻群( Dijkstra and Ant Colony Optimization based on Pheromone Declining,Dijkstra-PD-ACO)算法的大城市公交線路優(yōu)化等方面進(jìn)行研究和探討，而對(duì)于Dijkstra算法優(yōu)化，并將其應(yīng)用于城市軌道交通各車站票價(jià)計(jì)算方面未做詳細(xì)且深入的研究。文獻(xiàn)[19-20]通過建立兩種定價(jià)方式的雙層規(guī)劃模型對(duì)影響票價(jià)的因素進(jìn)行研究，研究結(jié)果表明對(duì)價(jià)格的敏感度是影響兩種定價(jià)的主要因素。

盡管有眾多的專家學(xué)者針對(duì)Dijkstra算法在大型城市軌道交通線網(wǎng)計(jì)價(jià)系統(tǒng)中的應(yīng)用進(jìn)行了深入研究，但是到目前為止，對(duì)Dijkstra算法進(jìn)行改進(jìn)并將其應(yīng)用在大型城市軌道交通線網(wǎng)計(jì)價(jià)系統(tǒng)中的研究很少。因此，對(duì)Dijkstra算法進(jìn)行改進(jìn)并將其應(yīng)用在大型城市軌道交通線網(wǎng)計(jì)價(jià)系統(tǒng)中具有非常重要的意義。本文對(duì)傳統(tǒng)的Dijkstra算法進(jìn)行了改進(jìn)，使用傳統(tǒng)的Dijkstra算法和改進(jìn)的Dijkstra算法計(jì)算分析了長沙地鐵罐子嶺站至毛竹塘站間的最短距離，并對(duì)結(jié)果進(jìn)行了分析。為進(jìn)一步研究Dijkstra算法在大型城市軌道交通線網(wǎng)計(jì)價(jià)系統(tǒng)中的應(yīng)用提供了參考。

1 改進(jìn)Dijkstra算法的實(shí)現(xiàn)

1.1 改進(jìn)Dijkstra算法的主要思想

本算法主要根據(jù)地鐵線網(wǎng)規(guī)劃、建設(shè)規(guī)劃、線路里程表等相關(guān)資料，提取線網(wǎng)各車站的里程標(biāo)，繪制出地鐵線網(wǎng)示意圖，再篩選出線網(wǎng)所有換乘站，且對(duì)于同一線路中兩換乘站之間無其他換乘站可認(rèn)定為相鄰換乘站。根據(jù)換乘站之間的關(guān)系及換乘站的中心線里程標(biāo)，使用傳統(tǒng)的Dijkstra算法計(jì)算各換乘站之間的最短距離。算法詳細(xì)思路如圖1所示。

圖1 改進(jìn)Dijkstra算法流程圖Fig.1 Improved Dijkstra algorithm flow chart

1.2 傳統(tǒng)的Dijkstra算法計(jì)算換乘站間最短距離

假定地鐵線網(wǎng)有n個(gè)換乘站，首先參照傳統(tǒng)的Dijkstra算法計(jì)算出線網(wǎng)所有換乘站之間的最短距離，算法實(shí)現(xiàn)如圖2所示。

圖2 傳統(tǒng)的Dijkstra算法計(jì)算換乘站間最短距離流程圖Fig.2 Traditional Dijkstra algorithm to calculate the shortest distance flow chart between transfer stations

算法詳細(xì)描述如下：

Step1：篩選出線網(wǎng)中所有換乘站，導(dǎo)入其里程標(biāo)。

Step2：計(jì)算所有相鄰換乘站之間的距離li,j，令本站的li,i=0且不相鄰換乘站之間的距離li,j=+∞，其中i=1,2,3,…,n。

Step3：初始化，令i=1。

Step4：初始化，令di,j=li,j,mi,j=+∞，其中j=1,2,3,…,n且j≠i。

Step5：比較所有新解且不為站名的di,j大小，即令mi,j=min{di,j}，其中j=1,2,3,…,n且di,j≠j站名。

Step6：對(duì)于所有j=1,2,3,…,n，當(dāng)di,j=mi,j≠+∞時(shí)，則令di,j=j站名。

Step7：對(duì)于所有j=1,2,3,…,n，若di,j≠j站名，則令di,j=min{mi,k+lk,j,di,j}，其中k=1,2,3,…,n。

Step8：檢查是否所有j的di,j=j站名，其中j=1,2,3,…,n，若為否，則跳至Step 5，若為是，則跳至下一步。

Step9：檢查i是否大于等于n，若為否，則令i=i+1且跳至Step 4，若為是，則該算法結(jié)束。

其中：i，j表示換乘站線網(wǎng)中第i或j個(gè)換乘站；n表示換乘站線網(wǎng)總計(jì)有n個(gè)換乘站；li,j表示兩相鄰換乘站i和j之間的距離，若不相鄰，其取值為+∞；mi,j表示換乘站i與換乘站j之間的最短距離；di,j表示換乘站i與換乘站j之間的最短距離求值過程中經(jīng)歷的中間值。

1.3 改進(jìn)的Dijkstra算法計(jì)算線網(wǎng)各車站間最短距離

參考如上算法，計(jì)算出各換乘站之間最短距離表，再參考圖2流程圖中算法的主要思想，細(xì)分三個(gè)部分對(duì)線路各車站間最短距離進(jìn)行計(jì)算，其具體的算法實(shí)現(xiàn)如圖3所示。

圖3 改進(jìn)的Dijkstra算法計(jì)算換乘站間最短距離流程圖Fig.3 Flow chart which used the improved Dijkstra algorithm to calculate the shortest distance between the stations

算法詳細(xì)描述如下：

Step1：導(dǎo)入換乘站間的最短距離即圖2算法的結(jié)果，并參考換乘站在線網(wǎng)中的實(shí)際位置對(duì)算法結(jié)果進(jìn)行適當(dāng)?shù)恼{(diào)整。

Step2：導(dǎo)入線網(wǎng)中各車站的線路里程標(biāo)，并令a=1、b=1、i=1、j=1。

Step3：檢查i和j是否為換乘站線網(wǎng)以內(nèi)的車站，若為否，則跳至下一步，若為是，則令：

Za,i,b,j=min{|La,i-La,c|+mc,k+|Lb,j-Lb,k|}

(1)

Step4：檢查i和j其中之一是否為換乘站線網(wǎng)以內(nèi)的車站，若為否，則跳至下一步，若為是，則令：

Za,i,b,j=min(|La,i-La,c|+mc,e+|Lb,j-Lb,e|，

|La,i-La,c|+mc,k+|Lb,j-Lb,k|)

(2)

Step5：檢查i和j是否均為換乘站線網(wǎng)以內(nèi)的車站，若為否，則跳至下一步，若為是，則令：

Za,i,b,j=min(|La,i-La,c|+mc,e+|Lb,j-Lb,e|,

|La,i-La,c|+mc,k+|Lb,j-Lb,k|,

|La,i-La,g|+mg,e+|Lb,j-Lb,e|,

|La,i-La,g|+mg,k+|Lb,j-Lb,k|)

(3)

Step6：判斷是否已經(jīng)擴(kuò)展并巡視所有線網(wǎng)所有車站，若為否，則跳至Step 3，若為是，則該算法結(jié)束。

其中：a、b表示線路編號(hào)，當(dāng)算法巡視所有車站時(shí)，a和b均等于線路總數(shù)；i表示第a條線路中第i個(gè)車站，i不大于第a條線路車站總數(shù)；j表示第b條線路中第j個(gè)車站，j不大于第b條線路車站總數(shù)；La,i表示線路a中第i個(gè)車站的中心線里程標(biāo)；Lb,j表示線路b中第j個(gè)車站的中心線里程標(biāo)；Za,i,b,j表示第a條線路中第i個(gè)車站與第b條線路中第j個(gè)車站的最短距離；c、g表示為圖3中離線路a第i個(gè)車站最近的換乘站，是線路a上的第c和g個(gè)車站；e、k表示為圖3中離線路b第j個(gè)車站最近的換乘站，是線路b上的第e和k個(gè)車站；mc,e、mc,k表示換乘站c與換乘站e或k的最短距離，是根據(jù)圖2算法求出的結(jié)果。

1.4 線網(wǎng)各車站間票價(jià)計(jì)算算法

根據(jù)圖3中算法求出線網(wǎng)各車站之間最短距離Za,i,b,j，再參考如圖4所示算法，核算線網(wǎng)各車站之間的票價(jià)。

圖4 線網(wǎng)各車站間票價(jià)計(jì)算算法Fig.4 Algorithm flow chart of ticket price between stations in line network

算法詳細(xì)描述如下：

Step1：導(dǎo)入線網(wǎng)各車站間最短距離Za,i,b,j，即圖3的計(jì)算結(jié)果。

Step2：初始化，令p1=0，F(xiàn)、Pa,i,b,j均為+∞，f1=0。

Step3：初始化，令m=1。

Step4：判斷第a條線路第i個(gè)車站與第b條線路第j個(gè)車站之間的最短距離Za,i,b,j是否等于p1，即Za,i,b,j=p1，若為是，則跳至Step 6，若為否，則跳至Step 5。

Step5：判斷第a條線路第i個(gè)車站與第b條線路第j個(gè)車站之間的最短距離Za,i,b,j屬于哪個(gè)計(jì)價(jià)區(qū)間，即檢查pm

Step7：檢查所有Pa,i,b,j是否不等于+∞，即Pa,i,b,j≠+∞，若為否，則跳至Step 3，若為是，則該算法結(jié)束。

其中：m表示城市地鐵第m個(gè)計(jì)價(jià)區(qū)間；pm表示在第m個(gè)計(jì)價(jià)區(qū)間乘客可乘坐的距離，F(xiàn)表示城市地鐵起步票價(jià)；Pa,i,b,j表示第a條線路中第i個(gè)車站與第b條線路中第j個(gè)車站的票價(jià)，fm表示第m個(gè)計(jì)價(jià)區(qū)間較第m-1個(gè)計(jì)價(jià)區(qū)間需要調(diào)整的票價(jià)。

2 改進(jìn)Dijkstra算法實(shí)例與分析

2.1 算法實(shí)例

以長沙地鐵罐子嶺站至毛竹塘站、罐子嶺站至赤崗嶺站、湖南師大站至赤崗嶺站的最短距離計(jì)算為例。對(duì)于傳統(tǒng)算法需要根據(jù)長沙地鐵1～5號(hào)線線網(wǎng)布局及各車站的中心線里程標(biāo)，計(jì)算線網(wǎng)中各相鄰車站之間的距離，以罐子嶺站(或湖南師大站)為目標(biāo)節(jié)點(diǎn)，并建立集合1，開始遍歷長沙地鐵1～5號(hào)線線網(wǎng)各車站，逐步將計(jì)算出最短距離的車站納入集合1，算法在完成長沙地鐵線網(wǎng)99個(gè)車站間最短距離的計(jì)算后結(jié)束，并根據(jù)要求提取出罐子嶺站至毛竹塘站(或罐子嶺站至赤崗嶺站，或湖南師大站至赤崗嶺站)的最短距離。改進(jìn)的Dijkstra算法需根據(jù)長沙地鐵1～5號(hào)線線網(wǎng)布局及各車站里程標(biāo)，將線路中換乘站篩選出來，根據(jù)長沙地鐵1～5號(hào)線線網(wǎng)布局，共計(jì)有12個(gè)換乘站，若任意兩個(gè)換乘站在同一線路且其之間無其他換乘站，則認(rèn)定其為相鄰換乘站，將相鄰換乘站連接起來，形成換乘站線網(wǎng)(如圖5所示)，并計(jì)算相鄰換乘站之間的距離；再根據(jù)傳統(tǒng)Dijkstra算法，計(jì)算各換乘站之間最短距離，而長沙地鐵的換乘站線網(wǎng)圖只有12個(gè)換乘站，較線網(wǎng)99個(gè)車站，計(jì)算難度及消耗時(shí)間大大縮減；再詳細(xì)按照?qǐng)D3將線網(wǎng)各車站細(xì)分為三類，計(jì)算罐子嶺站至毛竹塘站、罐子嶺站至赤崗嶺站，湖南師大站至赤崗嶺站的最短距離，如罐子嶺站和毛竹塘站均為換乘站線網(wǎng)以外的車站，則罐子嶺站至毛竹塘站的計(jì)算方法可參考圖3中第一種情況，對(duì)于罐子嶺站至赤崗嶺站而言，其中赤崗嶺站為換乘站線網(wǎng)以內(nèi)車站，則罐子嶺站至赤崗嶺站的計(jì)算方法可參考圖3中第二種情況，湖南師大站和赤崗嶺站均為換乘站線網(wǎng)以內(nèi)車站，則湖南師大站至赤崗嶺站的計(jì)算方法可參考圖3中第三種情況。圖6和圖7以罐子嶺站至毛竹塘站為例，使用兩種算法時(shí)所涉及的站點(diǎn)及最短距離行走路徑標(biāo)記如下所示。

圖5 長沙地鐵1～5號(hào)線換乘站線網(wǎng)圖Fig.5 Transfer station network of Changsha metro line 1～5

圖6 傳統(tǒng)Dijkstra算法計(jì)算罐子嶺站至毛竹塘站最短距離時(shí)行走路徑Fig.6 Traditional Dijkstra algorithm to calculate the shortest walking path between Guanziling station and Maozhutang station

由圖6和圖7可知，使用傳統(tǒng)Dijkstra算法計(jì)算罐子嶺站至毛竹塘站間最短距離時(shí)，參與計(jì)算的站點(diǎn)數(shù)為99，使用改進(jìn)的Dijkstra算法計(jì)算罐子嶺站至毛竹塘站間最短距離時(shí)，參與計(jì)算的站點(diǎn)數(shù)為14。具體情況如表1和圖8～10所示，圖中①～⑥與表1中標(biāo)號(hào)相對(duì)應(yīng)。

圖7 改進(jìn)Dijkstra算法計(jì)算罐子嶺站至毛竹塘站最短距離時(shí)行走路徑Fig.7 Improved Dijkstra algorithm to calculate the shortest walking path between Guanziling station and Maozhutang station

圖8 參與計(jì)算的站點(diǎn)數(shù)比較圖Fig.8 Comparison chart of the number of stations participating in calculation

由表1可知，傳統(tǒng)Dijkstra算法與改進(jìn)的Dijkstra算法的行走路徑和最短距離大致相同，但在參與計(jì)算的站點(diǎn)數(shù)、計(jì)算次數(shù)、數(shù)據(jù)存儲(chǔ)及運(yùn)行時(shí)間方面，改進(jìn)的Dijkstra算法都進(jìn)行了大量縮減。

表1 傳統(tǒng)Dijkstra算法和改進(jìn)Dijkstra算法的算例比較Tab.1 Example compared with traditional Dijkstra algorithm and improved Dijkstra algorithm

注：目前長沙地鐵票價(jià)政策是“起步價(jià)2元可乘坐6 km(含6 km)，超過6 km采用‘遞遠(yuǎn)遞減’的計(jì)價(jià)原則，6～16 km(含16 km)范圍每遞增5 km加1元，16～30 km(含30 km)范圍內(nèi)每遞增7 km加1元，30 km以上每遞增9 km加1元”，參考表1可知，罐子嶺站至毛竹塘站的最短距離為31.349 km，屬于30 km以上范圍，票價(jià)為7元，罐子嶺站至赤崗嶺站的最短距離為21.673 km，屬于16～23 km(含23 km)范圍，票價(jià)為5元，湖南師大站至赤崗嶺站的最短距離為8.607 km，屬于6～11 km(含11 km)范圍，票價(jià)為3元。

圖9 計(jì)算次數(shù)比較圖Fig.9 Comparison chart of calculation times

圖10 數(shù)據(jù)存儲(chǔ)比較圖Fig.10 Data storage comparison chart

2.2 比較分析

當(dāng)使用傳統(tǒng)Dijkstra算法和改進(jìn)的Dijkstra算法求任意兩車站之間最短距離時(shí)，所需參與計(jì)算的站點(diǎn)數(shù)、計(jì)算次數(shù)及數(shù)據(jù)存儲(chǔ)比較如表2所示。

表2 傳統(tǒng)Dijkstra算法和改進(jìn)Dijkstra算法比較Tab.2 Comparison between original Dijkstra algorithm and improved Dijkstra algorithm

表2中，S為地鐵線網(wǎng)站點(diǎn)總數(shù)；n為地鐵線網(wǎng)中換乘站總數(shù)；x為已經(jīng)尋找出最短路徑的站點(diǎn)，初始值為1；t為固定參數(shù)值，當(dāng)兩車站均為換乘站線網(wǎng)(含換乘站)以外車站時(shí)t取1，其中之一為換乘站線網(wǎng)以內(nèi)車站時(shí)t取3，兩個(gè)均為換乘站線網(wǎng)(含換乘站)以內(nèi)車站時(shí)t取5。

在計(jì)算過程中，使用傳統(tǒng)Dijkstra算法計(jì)算某兩個(gè)站點(diǎn)的最短距離時(shí)，就需要先根據(jù)里程表計(jì)算各站點(diǎn)之間的距離初始值，相鄰站點(diǎn)之間的距離為|La,i-La,i+1|，非相鄰車站之間的距離為+∞，其計(jì)算次數(shù)為S2。而改進(jìn)的算法中，需要先篩選相應(yīng)換乘站，并根據(jù)換乘站之間的關(guān)系，求出各換乘站之間的距離初始值，其計(jì)算次數(shù)為n2。

在計(jì)算過程中，傳統(tǒng)的Dijkstra算法需要的第一個(gè)數(shù)組，大小為S2，存儲(chǔ)所有車站的初始距離值，并可以用來存儲(chǔ)計(jì)算中間值；第一個(gè)數(shù)組，大小為S，存儲(chǔ)起點(diǎn)至所有車站的最短距離；第三個(gè)數(shù)組，大小為S，存儲(chǔ)所有節(jié)點(diǎn)里程標(biāo)。而改進(jìn)的Dijkstra算法，需要存儲(chǔ)的換乘站數(shù)組及參與計(jì)算車站里程表的數(shù)組總數(shù)為n2+2n+2，此外，還需要一個(gè)變量存儲(chǔ)起點(diǎn)至要求節(jié)點(diǎn)的最短距離。

2.3 算法延展

以長沙地鐵1號(hào)線北延線一期為例，假定La,i表示線路a中第i個(gè)車站的中心線里程標(biāo)，Lb,j表示線路b中第j個(gè)車站的中心線里程標(biāo)，使用改進(jìn)Dijkstra算法求解如下：

Step1：當(dāng)i，j均為1號(hào)線北延線一期車站，則最短距離Z1,i,1,j=|L1,i-L1,j|。

Step2：當(dāng)i或j之一為1號(hào)線北延線一期車站，假定i為1號(hào)線北延線一期車站，則最短距離Z1,i,b,j=|L1,i-L1,1|+Z1,1,b,j，由于i車站為1號(hào)線北延線一期車站，離其最近的車站為1號(hào)線第1個(gè)車站。

Step3：當(dāng)i和j均非1號(hào)線北延線一期車站，則最短距離Za,i,b,j=Za,i,b,j。

算法實(shí)例如表3所示。

表3 改進(jìn)的Dijkstra算法的延展性算例Tab.3 Example of extension of improved Dijkstra algorithm

由于長沙地鐵1號(hào)線北延線為1號(hào)線新增車站，若按照傳統(tǒng)的Dijkstra算法的原理計(jì)算線網(wǎng)中所有車站(含新增車站)間最短距離，需遍歷線網(wǎng)所有車站進(jìn)行求解，計(jì)算煩瑣性增加，顯然其延展性較改進(jìn)的Dijkstra算法差。

3 結(jié)論

1)改進(jìn)后的Dijkstra算法克服了傳統(tǒng)算法時(shí)間冗長的缺陷，創(chuàng)新地將換乘站從線網(wǎng)中獨(dú)立出來，再通過換乘站線網(wǎng)拓展至線網(wǎng)各站，實(shí)際中，換乘站數(shù)量遠(yuǎn)遠(yuǎn)小于線網(wǎng)車站總數(shù)，這就減少了節(jié)點(diǎn)遍歷數(shù)和查詢時(shí)間，增強(qiáng)了設(shè)計(jì)的可行性；

2)若需知道線網(wǎng)各車站間最短距離，無須逐一核算各相鄰車站之間的距離，減少了產(chǎn)生誤差的可能性；

3)在換乘站不變，但有新線開通時(shí)，只需將車站里程標(biāo)導(dǎo)入，便可直接計(jì)算出該站至其他車站的最短距離，可延展性更強(qiáng)。