陸文琦，谷遠(yuǎn)利，李萌，王碩，張源

(北京交通大學(xué)城市交通復(fù)雜系統(tǒng)理論與技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，北京 100044)

隨著計算機(jī)和地理信息技術(shù)的快速發(fā)展，智能導(dǎo)航與位置查詢服務(wù)在輔助人們出行方面發(fā)揮出越來越重要的作用，尤其是車載導(dǎo)航系統(tǒng)正逐漸成為所有駕駛?cè)藛T的必備產(chǎn)品。但是由于城市汽車保有量的不斷攀升，道路網(wǎng)絡(luò)規(guī)模不斷增大，交通情況愈發(fā)復(fù)雜，用戶急需更加高效、準(zhǔn)確的最短路徑算法以獲取動態(tài)靈活的導(dǎo)航服務(wù)。

最短路徑算法被廣泛應(yīng)用于車輛誘導(dǎo)、交通流分配等領(lǐng)域，最早用來解決點(diǎn)到點(diǎn)最短路徑的算法是經(jīng)典Dijkstra算法[1]，Bellman-Ford算法和Floyd算法也被用來解決過此類問題。Hart等[2-3]在經(jīng)典Dijkstra算法基礎(chǔ)上提出了A*算法，該算法利用當(dāng)前點(diǎn)到目標(biāo)點(diǎn)的最短路徑長度的估值更快地向目標(biāo)點(diǎn)靠近，始終根據(jù)既定的規(guī)則，通過不斷擴(kuò)大“最有希望”[4]的節(jié)點(diǎn)集合進(jìn)行探索，由于在搜索過程中省略大量無謂的搜索路徑，比Dijkstra算法的效率更高。與A*算法類似，Pearl等[5]提出了Weight A*算法(簡稱WA*)，在計算路徑時，A*算法和WA*算法均以兩點(diǎn)間直線距離作為最短路徑長度估值，WA*求解得到的路徑質(zhì)量與其算法運(yùn)行時設(shè)置的參數(shù)有關(guān)，可以在大規(guī)模網(wǎng)絡(luò)上找到一條與標(biāo)準(zhǔn)最短路徑相差不大的路徑。

以上算法主要以標(biāo)號法為主，沒有對圖進(jìn)行預(yù)處理。針對大規(guī)模網(wǎng)絡(luò)計算時間長、占用內(nèi)存空間大、無法應(yīng)對快速查詢的缺陷，在傳統(tǒng)算法的基礎(chǔ)上逐步形成了基于預(yù)處理的最短路徑算法，包括預(yù)處理階段和路徑查詢階段[4]。例如，在A*算法的基礎(chǔ)上，Goldberg等[6]提出了基于預(yù)處理的ALT算法，由A*、Landmark和Triangle inequality方法組合而成。此外，與經(jīng)典單向Dijkstra算法相對應(yīng)，雙向Dijkstra算法可以以源點(diǎn)和終點(diǎn)為圓心同時向外搜索，加快了搜索效率，并且雙向算法可以與其他方法相結(jié)合形成新的算法，解決點(diǎn)到點(diǎn)最短路徑問題。Goldberg等[7]將雙向算法和A*算法、ALT算法結(jié)合，并且通過添加快捷弧的預(yù)處理方法，使查詢效率極大提升。其他常用的預(yù)處理方法有層次化法，包括分割法[8]、層次公路HH算法[9]、HNR算法[10]、THR算法[11]等等。

本文在reach剪枝算法的基礎(chǔ)上，詳細(xì)介紹了reach的計算方法，包括reach精確值和上界值，對兩種reach計算方法在不同規(guī)模路網(wǎng)上進(jìn)行對比，并將基于reach的剪枝算法與雙向Dijkstra算法結(jié)合形成了RE算法，利用EFSS數(shù)據(jù)結(jié)構(gòu)[12-13]建立了包含路段阻抗和交叉口轉(zhuǎn)向延誤的交通路網(wǎng)，通過算例和幾種不同規(guī)模的交通路網(wǎng)測試了RE算法，驗(yàn)證其適用性和算法效率。

1 算法原理及實(shí)現(xiàn)

1.1 雙向Dijkstra算法

雙向Dijkstra算法即從搜索的源點(diǎn)s和終點(diǎn)t交替使用Dijkstra算法，直到兩端點(diǎn)都找到了到達(dá)同一節(jié)點(diǎn)的最短路徑。在節(jié)點(diǎn)數(shù)量較多的圖上，應(yīng)用雙向Dijkstra算法能大幅減少搜索時間。該算法用df(v)和dr(v)分別記錄正向和反向算法中節(jié)點(diǎn)v至源點(diǎn)s和終點(diǎn)t的距離，用μ記錄最短路徑長度。算法的基本步驟如下：

步驟1：初始化，對于所有節(jié)點(diǎn)v，df(v)=∞，dr(v)=∞，μ=∞；

步驟2：交替使用正向和反向算法，在正向搜索時，若遇到某一被反向搜索作為永久標(biāo)號點(diǎn)的節(jié)點(diǎn)w時，若滿足μ>df(v) +l(v,w) +dr(w)，則更新μ；反向搜索時同理進(jìn)行更新；

步驟3：判斷是否滿足終止條件，若滿足則輸出最短路徑，不滿足則返回步驟2。

雙向Dijkstra算法的終止條件[5]有兩種設(shè)置方式，其中一種是正向搜索每前進(jìn)一步，判斷搜索是否滿足終止條件，同理反向搜索每前進(jìn)一步，也判斷是否滿足終止條件；另一種是完成一個完整正反向搜索后進(jìn)行終止條件判斷，本文選擇后者作為終止條件的設(shè)置方式。雙向Dijkstra算法與單向Dijkstra算法的技術(shù)對比見表1。

表1 雙向Dijkstra算法與單向Dijkstra算法技術(shù)對比Table 1 Technical comparison of bidirectional algorithm and one-way Dijkstra algorithm

1.2 基于reach的預(yù)處理方法

1.2.1 相關(guān)定義

假定一條由s到t的路徑P，并且點(diǎn)v在路徑P上，如圖1所示。

圖1 reach的定義Fig.1 Definition of reach

reach(v,P)代表節(jié)點(diǎn)v關(guān)于最短路徑P的reach，其準(zhǔn)確值是s到v的子路徑長度和v到t的子路徑長度中的最小值。

reach(v,P)=min{dist(s,v),dist(t,v)}。

(1)

那么v關(guān)于整個圖的reach由r(v)表示。

r(v)=max{reach(v,P)}。

(2)

基于reach的預(yù)處理方法又稱為reach剪枝算法，是指在預(yù)處理階段計算出所有節(jié)點(diǎn)的reach值，再根據(jù)相應(yīng)的條件在查詢過程中刪剪掉不滿足條件的節(jié)點(diǎn)。

1.2.2 reach值的計算

計算reach值的基本方法是由Gutman等[14]提出，而后Goldberg等[7]提出了改進(jìn)算法。根據(jù)相關(guān)研究[7,14]，求解reach精確值的效率不高，基于reach剪枝主要用reach上界值(reach bound)來代替精確值，由此產(chǎn)生了許多計算reach上界值的方法，下文分別介紹reach精確值和一種常用的reach上界值的計算方法。

reach精確值的計算過程為：初始化，對于所有節(jié)點(diǎn)r(v)=0，對于每一個節(jié)點(diǎn)x，生成一個根節(jié)點(diǎn)在x的完整最短路徑樹Tx，對于樹上每一個節(jié)點(diǎn)v，計算出v到根節(jié)點(diǎn)x的距離(depth[v])和v到距離自身最遠(yuǎn)的子節(jié)點(diǎn)v*的距離(height[v])，由(3)計算得出v在以x為根的最短路徑樹上的reach的值，記為rx(v)。

rx(v)=min{depth[v],height[v]}。

(3)

若rx(v) >r(v)，則令rx(v) =r(v)，最后得到的r(v)是reach的精確值，計算過程如圖2所示。

圖2 reach精確值計算流程圖Fig.2 Flow diagram of calculating exact reach

計算reach上界值的基本過程為：

步驟1：以每個節(jié)點(diǎn)x為根節(jié)點(diǎn)按照一定條件生成部分最短路徑樹；

步驟2：計算部分最短路徑樹上某些節(jié)點(diǎn)的reach的上界值和reach的精確值；

步驟3：根據(jù)得到的精確的r(v)，對圖進(jìn)行收縮修改，保存刪除后的圖；

步驟4：不斷重復(fù)步驟1、2、3，不斷更新相關(guān)節(jié)點(diǎn)reach的上界值，直到所有的上界值都被計算出來。

reach上界值與reach精確值相比，其優(yōu)勢在于引入了生成部分樹(partial tree)的概念，計算reach精確值時每次都要生成完整的最短路徑樹，在小網(wǎng)絡(luò)中，每條完整最短路徑樹的長度不會很長，但是在上百乃至上千個節(jié)點(diǎn)的大網(wǎng)絡(luò)中，生成完整最短路徑樹就會消耗大量的時間，而reach上界值算法采用必要條件[7]終止樹的生成，在更新隊(duì)列和計算上界值時節(jié)約了時間。因此，在小規(guī)模網(wǎng)絡(luò)中，優(yōu)先采用reach的精確值算法，而在中等以及大規(guī)模網(wǎng)絡(luò)上，優(yōu)先采用reach的上界值算法。

1.3 RE算法

1.3.1 算法原理

通常情況下，若一個節(jié)點(diǎn)在一條很長的最短路徑的中間，那么這個節(jié)點(diǎn)的reach值應(yīng)該是一個很大的數(shù)，直觀上來看，如果在運(yùn)行雙向Dijkstra算法時處理某一個節(jié)點(diǎn)，該節(jié)點(diǎn)的reach值太小以至于不能到達(dá)目標(biāo)終點(diǎn)的情況下，可以忽略該點(diǎn)，將其從正向隊(duì)列和反向隊(duì)列中刪除，從而提高效率，這是RE算法的一般原理。

圖3 RE算法原理Fig.3 Principe of RE algorithm

r(w)

(4)

r(w)

(5)

具體刪剪方法如圖3所示，在一條由s到t的路徑上，w為當(dāng)前需要處理的節(jié)點(diǎn)，r(w)為節(jié)點(diǎn)w的reach值，如果同時滿足公式(4)和公式(5)，則將節(jié)點(diǎn)w刪剪掉，使其不再進(jìn)入優(yōu)先隊(duì)列(priority queue)中，減少搜索過程中隊(duì)列的節(jié)點(diǎn)個數(shù)。

1.3.2 算法步驟

假設(shè)，在一般路網(wǎng)上，兩節(jié)點(diǎn)間的路段是雙向的并且具有阻抗，首先通過預(yù)處理得到rf(v)和rr(v)，分別記錄前向鏈表和反向鏈表計算的reach精確值或上界值，結(jié)構(gòu)體df[V]和dr[V]記錄兩個方向Dijkstra算法每個節(jié)點(diǎn)的編號(ID)、標(biāo)號距離(label)以及是否成為永久標(biāo)號點(diǎn)(scaned)，結(jié)構(gòu)體df[V]和dr[V]分別放入兩個優(yōu)先隊(duì)列(priority queue)中按標(biāo)號距離由小到大自動更新排列。Ωf、Ωr分別作為在正向、反向搜索中一個被標(biāo)記節(jié)點(diǎn)的最小距離標(biāo)記，即正向隊(duì)列(forward_q)和反向隊(duì)列(reverse_q)隊(duì)首元素的標(biāo)號距離，prune(v)記錄節(jié)點(diǎn)是否被刪剪，μ1和μ2分別記錄正向和反向搜索得到的臨時最短路徑值，具體RE算法以雙向Dijkstra算法為基礎(chǔ)，以下是RE算法在該假設(shè)下的迭代過程：

步驟1：初始化所有變量，把起點(diǎn)s和終點(diǎn)t放入正向優(yōu)先隊(duì)列和反向優(yōu)先隊(duì)列；

步驟2：使用正向Dijkstra算法，當(dāng)處理節(jié)點(diǎn)v時，若scanned_r[v]=false、rf(v)

步驟3：使用反向Dijkstra算法，當(dāng)處理節(jié)點(diǎn)v時，若scanned_f[v]=false、rr(v)

步驟4：μ=min{μ1,μ2}；

步驟5：判斷是否滿足終止條件Ωf+Ωr≤μ，若滿足，輸出最短路徑和距離，否則返回步驟2繼續(xù)迭代。

2 算法測試

2.1 交通網(wǎng)絡(luò)構(gòu)建

將RE算法應(yīng)用于車載導(dǎo)航路徑優(yōu)化需要構(gòu)建交通網(wǎng)絡(luò)，由于實(shí)際道路網(wǎng)絡(luò)是有條件限制的網(wǎng)絡(luò)[15]，比如交通管理手段帶來的交叉口禁止轉(zhuǎn)向限制，不同流向車輛之間的干擾和信號控制手段產(chǎn)生的交叉口轉(zhuǎn)向延誤等等，為了更好地描述這一問題，本文引入擴(kuò)展的前向星形結(jié)構(gòu)(extend forward star structure，EFSS)來組建交通網(wǎng)絡(luò)。

EFSS是在文獻(xiàn)[12-13]中提到的一種較為經(jīng)典的限制網(wǎng)絡(luò)表示方法，是一種如圖4所示的鏈表結(jié)構(gòu)，在原有的星形鏈表基礎(chǔ)之上加以擴(kuò)展，加入了對交叉口轉(zhuǎn)向延誤的存儲，并方便檢索。該結(jié)構(gòu)能有效存儲交叉口之間的路段阻抗以及交叉口的交通延誤，與傳統(tǒng)的采用鄰接矩陣建立路網(wǎng)拓?fù)潢P(guān)系相比，EFSS數(shù)據(jù)結(jié)構(gòu)節(jié)省了大量的內(nèi)存空間，便于預(yù)處理和查詢搜索。

圖4 EFSS數(shù)據(jù)結(jié)構(gòu)Fig.4 EFSS data structure

2.2 結(jié)果分析

本文為使用小規(guī)模網(wǎng)絡(luò)蘇福爾斯網(wǎng)絡(luò)來對RE算法的準(zhǔn)確性進(jìn)行驗(yàn)證，利用EFSS數(shù)據(jù)結(jié)構(gòu)搭建了如圖5所示的交通網(wǎng)絡(luò)，為方便顯示預(yù)處理以及刪剪節(jié)點(diǎn)的過程，該路網(wǎng)設(shè)置交叉口轉(zhuǎn)向延誤時間為0，兩節(jié)點(diǎn)間的路段不考慮道路方向不均勻系數(shù)的影響，即道路兩個方向的阻抗相同，目標(biāo)是查找節(jié)點(diǎn)1到節(jié)點(diǎn)20的最短路徑距離，首先通過預(yù)處理，可以獲得如表2所示的每個節(jié)點(diǎn)的reach值，預(yù)處理時間為16 s。

表2 蘇福爾斯測試網(wǎng)絡(luò)預(yù)處理結(jié)果Table 2 Results of preprocessing on Sioux Falls test network

圖5 蘇福爾斯測試網(wǎng)絡(luò)算例Fig.5 Example of Sioux Falls test network

利用RE算法求解節(jié)點(diǎn)1到節(jié)點(diǎn)20的最短路徑的迭代過程如表3所示。

表3 RE算法求解最短路徑迭代過程Table 3 Iterative process for solving the shortest path by RE algorithm

在此算例中，RE算法共完成更新節(jié)點(diǎn)18次，在迭代過程中刪剪節(jié)點(diǎn)10個。用經(jīng)典Dijkstra算法求解該算例需要更新節(jié)點(diǎn)28次，而且需要完成對全部節(jié)點(diǎn)的搜索，造成了運(yùn)算時間和運(yùn)算空間的浪費(fèi)。RE算法保證了計算結(jié)果的準(zhǔn)確性。為了驗(yàn)證RE算法的效率，利用蘇福爾斯測試路網(wǎng)隨機(jī)生成若干對查詢節(jié)點(diǎn)，選擇Dijkstra、ALT和RE算法進(jìn)行查詢，如圖6所示，結(jié)果表明在小規(guī)模路網(wǎng)上，RE算法效率略高于Dijkstra算法和ALT算法。

圖6 相同路網(wǎng)下不同算法效率對比Fig.6 Comparison of the efficiency of different algorithms on the same network

為檢驗(yàn)新算法在實(shí)際交通應(yīng)用中的適用性，需要在大規(guī)模路網(wǎng)上進(jìn)行測試，本文利用EFSS數(shù)據(jù)結(jié)構(gòu)建立了5個不同規(guī)模的交通網(wǎng)絡(luò)，利用隨機(jī)數(shù)生成交叉口延誤數(shù)據(jù)與道路阻抗模擬實(shí)際路況，并在各個路網(wǎng)上隨機(jī)生成1 000對節(jié)點(diǎn)，用Dijkstra算法、ALT算法和RE算法分別進(jìn)行查詢，并且計算出平均查詢時間，得到如表4所示的數(shù)據(jù)。

表4 不同規(guī)模路網(wǎng)上3種算法平均查詢時間Table 4 Comparison of average running time of three algorithms on networks of various scales

通過在各種規(guī)模的網(wǎng)絡(luò)中運(yùn)行RE算法可以發(fā)現(xiàn)，路網(wǎng)規(guī)模越大，節(jié)點(diǎn)數(shù)量越多，RE算法的性能越好，在查詢速度上的優(yōu)勢越明顯。在大規(guī)模網(wǎng)絡(luò)上，RE算法與Dijkstra相比運(yùn)算效率提升了90% 以上，與ALT算法相比提升了65%，所以RE算法更加適用于大規(guī)模的路網(wǎng)，并且隨著reach預(yù)處理技術(shù)的不斷改進(jìn)，算法效率可以得到進(jìn)一步提高。因此，RE算法在車載導(dǎo)航系統(tǒng)中可以發(fā)揮路徑規(guī)劃的作用，也可用于物流配送線路優(yōu)化等實(shí)際問題，具有良好的適用性和應(yīng)用前景。

3 結(jié)語

本文在經(jīng)典的最短路徑Dijkstra算法的基礎(chǔ)上，將雙向Dijkstra算法與基于reach的預(yù)處理方法相結(jié)合形成RE算法，針對RE算法預(yù)處理階段計算reach精確值效率不高，時間較長的問題，引入reach的上界值算法來取代reach的精確值進(jìn)行計算。本文分析了RE算法的一般步驟，并且利用EFSS鏈表結(jié)構(gòu)建立了考慮交叉口延誤和路段阻抗的交通網(wǎng)絡(luò)，測試RE算法的性能，將其與Dijkstra算法和ALT算法進(jìn)行對比。實(shí)驗(yàn)結(jié)果表明，RE算法在不同規(guī)模網(wǎng)絡(luò)上較Dijkstra算法和ALT算法相比有一定的優(yōu)勢，并且隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，RE算法其優(yōu)勢也逐步擴(kuò)大，體現(xiàn)出該算法較好的適用性。

本研究將重點(diǎn)放在算法實(shí)現(xiàn)和路網(wǎng)預(yù)處理問題上，還有可以優(yōu)化和深入探討的部分，比如在構(gòu)建路網(wǎng)數(shù)據(jù)時，考慮的道路阻抗與交叉口延誤取值為靜態(tài)值，沒有體現(xiàn)路網(wǎng)的動態(tài)性，在后續(xù)的研究中，考慮引入路段行程時間函數(shù)與交叉口的轉(zhuǎn)向懲罰函數(shù)，并豐富和完善動態(tài)網(wǎng)絡(luò)加載中的RE最短路徑搜索算法，使算法能更準(zhǔn)確地描述真實(shí)交通狀況。

參考文獻(xiàn)：

[1]DIJKSTRA E W.A note on two problems in connection with graphs [J].Numerical Mathematics,1959,1(1)：269-271.

[2]HART P E,NILSSON N J,RAPHAEL B.A formal basis for the heuristic determination of minimum cost paths [J].IEEE Transactions on System Science and Cybernetics,1968,4(2):100-107.

[3]DORAN J E.An approach to automatic problem-solving [EB/OL].[2017-03-02].https://aitopics.org/search? view=&filters=&sort=score+desc&q=An+approach+to+automatic+problem+solving+.

[4]付強(qiáng).基于預(yù)處理的交通網(wǎng)最短路徑實(shí)時查詢研究[D].合肥：中國科學(xué)技術(shù)大學(xué),2015.

[5]PEARL J.Heuristics: Intelligent search strategies for computer problem solving[M].MA,US： Addison-Wesley Pub.Co.,Inc.,1984.

[6]GOLDBERG A V,HARRELSON C.Computing the shortest path: A search meets graph theory [M]// Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms.Philadelphia,PA,USA: Society for Industrial and Applied Mathematics,2005:156-165.

[7]GOLDBERG A V,KAPLAN H,WERNECK R F.Reach for A*: efficient point-to-point shortest path algorithms [EB/OL].[2017-03-12].http://epubs.siam.org/doi/abs/10.1137/1.9781611972863.13.

[8]SANDERS P,SCHULTES D.Highway hierarchies hasten exact shortest path queries [EB/OL].[2017-03-04].https://link.springer.com/chapter/10.1007/11561071_51.

[9]GEISBERGER R,SANDERS P,SCHULTES D,et al.Contraction hierarchies: Faster and simpler hierarchical routing in road networks[C]// International Workshop on Experimental Algorithms.Provincetown,MA,USA: [s.n.],2008: 319-333．

[10]SCHULTES D,SANDERS P.Dynamic highway-node routing[M]// Proceedings of 6th International Workshop on Experimental Algorithms.Berlin: Springer,2007: 66-79.

[11]BAST H,FUNKE S,MATIJEVIC D,et al.In transit to constant time shortest path queries in road networks[EB/OL].[2017-03-12].http://dx.doi.org/10.1137/1.9781611972870.5.

[12]ZILIASKOPOULOS A K,MAHMASSANI H S.Time dependent shortest path algorithm for real time intelligent vehicle highway system applications [J].Transportation Research Board，1993(1408)：94-100．

[13]ZILIASKOPOULOS A K,MAHMASSANI H S.A note on least time path computation considering delays and prohibitions for intersection movements [J].Transportation Research Part B Methodological,1996,30(5):359-367.

[14]GUTMAN R J.Reach-based routing: A new approach to shortest path algorithms optimized for road networks[C]// Proceedings of the Sixth Workshop on Algorithm Engineering & Experiments & the First Workshop on Analytic Algorithmics & Combinatorics.New Orleans,LA,USA: [s.n.],2004: 100-111.

[15]杜牧青,程琳.考慮交叉口轉(zhuǎn)向延誤的最短路徑拍賣算法[J].西南交通大學(xué)學(xué)報,2010,45(2):249-254.