一種改進的交通網(wǎng)絡(luò)路徑選擇算法

段明義，張 文

(中州大學(xué) 信息工程學(xué)院，河南 鄭州 450044)

?

一種改進的交通網(wǎng)絡(luò)路徑選擇算法

段明義，張 文

(中州大學(xué) 信息工程學(xué)院，河南 鄭州 450044)

運用人工智能領(lǐng)域的啟發(fā)式搜索方法，以交通網(wǎng)絡(luò)為研究對象，在深入分析經(jīng)典Dijkstra最短路徑算法的基礎(chǔ)上，提出了一個基于啟發(fā)式的最短路徑算法，并證明了該方法的有效性。經(jīng)過對改進算法仔細分析后，討論了其改進之處。結(jié)合具體應(yīng)用，從啟發(fā)函數(shù)、搜索范圍和排序方法等方面，提出了相應(yīng)的改進策略，并將其應(yīng)用到仿真試驗中。結(jié)果表明：在不同圖層下，該算法具有良好的伸縮性；與已有路徑選擇改進算法相比,在不同路徑權(quán)值選擇下，都能夠有效地縮短路徑查找時間，從而更好地滿足出行需要。同時，也給出了不同地理距離下初始搜索半徑的參考值。

智能交通系統(tǒng)；限制搜索區(qū)域；啟發(fā)式方法；交通網(wǎng)絡(luò)；路徑搜索；左傾樹

0 引言

實現(xiàn)城市的繁榮、有序和快速發(fā)展，一個基本條件是良好的城市交通系統(tǒng)。但隨著各城市機動車保有量的不斷增加，導(dǎo)致對交通需求的急劇增加，緊接而來的一系列如交通擁堵、交通事故頻發(fā)、環(huán)境污染嚴(yán)重及能源短缺等問題，給人們生產(chǎn)、生活等帶來了諸多不便，這些都制約著一個城市的進一步、可持續(xù)的發(fā)展。出行者在交通出行中，一個經(jīng)常關(guān)心的問題是如何迅速選擇一條最優(yōu)的路徑。因此，出行最優(yōu)路徑選擇算法問題的研究已迫在眉睫。

求解兩點間的最短路徑問題，已經(jīng)有很多學(xué)者做了研究，給出了很多的算法，其中以Dijkstra算法[1]最為經(jīng)典。該算法可以在O(n2)(n為節(jié)點數(shù))時間復(fù)雜度情況下，求出某初始點到其他與其有路徑相通的點之間的最短路徑。當(dāng)節(jié)點個數(shù)較少時，O(n2)級別的時間復(fù)雜度是可以接受的，實際系統(tǒng)中，節(jié)點個數(shù)往往較多，該級別的復(fù)雜度就顯得效率低下，因此，直接使用Dijkstra算法的情況不多。

文獻[2-3]針對堆排序算法做了分析；文獻[2]給出了一種基于左傾樹的堆排序改進算法，在輸入數(shù)據(jù)排列任意的情況下，該算法實現(xiàn)排序的時間復(fù)雜性為O(nlogn)；通過只對最短路徑上節(jié)點的臨界點處理，在不涉及其他節(jié)點的情況下，文獻[4]對Dijkstra算法進行優(yōu)化，使得計算的節(jié)點數(shù)大幅減少，從而提高了算法的速度；文獻[5]討論了啟發(fā)式算法在路徑規(guī)劃問題中的一些改進策略，該方法考慮到了一些計算機硬件因素；文獻[6]采用預(yù)先計算存儲的方法，程序運行時，根據(jù)初始節(jié)點和目標(biāo)節(jié)點，直接調(diào)用數(shù)據(jù)庫查詢語句，查詢出事先計算好的兩點間的距離，如果圖中節(jié)點數(shù)目較多，額外存儲空間開銷就較大。

因此，路徑搜索在交通網(wǎng)絡(luò)中是一個比較復(fù)雜的問題，設(shè)計算法時，需要考慮多種方面的因素，然后給出最終解決方案。本文將啟發(fā)式的思想引入Dijkstra算法中，并對搜索區(qū)域加以限制，提出限制搜索區(qū)域的啟發(fā)式最短路徑算法(Restricted Searching Area Heuristic Shortest Path Algorithm, RSAHSPA)，該算法能夠有效縮短路徑搜索時間，為使用者提供出行依據(jù)。

1 路徑搜索算法描述

1.1 尋徑問題網(wǎng)絡(luò)模型

尋徑問題是在圖論中研究的熱點之一，目標(biāo)是設(shè)計一個算法，尋找圖中從初始節(jié)點到目標(biāo)節(jié)點的一條通路。城市路網(wǎng)除具有一般路網(wǎng)的特點之外，還有其特殊之處：數(shù)據(jù)量大和結(jié)構(gòu)復(fù)雜。這都使得城市路網(wǎng)的結(jié)構(gòu)變得非常復(fù)雜，現(xiàn)實中的城市路網(wǎng)實體只有抽象化為圖論中的網(wǎng)絡(luò)圖后，才能做最佳路徑分析，一般的方法是采用GIS技術(shù)生成其對應(yīng)的電子地圖。本文的研究在已生成的電子地圖上進行，以此討論最短路徑算法的實現(xiàn)過程。

1.2 Dijkstra尋徑算法

定義1 圖是由1個頂點集V和1個弧集VR構(gòu)成的數(shù)據(jù)結(jié)構(gòu)，Graph=(V,VR)，其中，VR={|v,w∈V∧P(v,w)}，表示從v到w的1條弧，P(v,w)定義了弧的意義或信息，一般設(shè)置為該弧的權(quán)重[7]。

Dijkstra算法采用貪婪策略，描述如下。

算法1：

(1)初始，從節(jié)點集合V′={vs|vs∈V}出發(fā)，vs為路徑初始節(jié)點。

(3)在所有滿足vi∈V′∧vj∈M的弧中，選擇權(quán)重最小的邊，設(shè)該邊在M中依附的節(jié)點為vj，若vj=ve(ve為路徑目標(biāo)節(jié)點)，則算法結(jié)束。

(5)返回(2)。

當(dāng)圖中節(jié)點個數(shù)很多的時候，Dijkstra算法的性能就顯得有些低。此時，為了提高搜索的效率，可以在犧牲一定精確性的情況下達到提高查找速度的目的。啟發(fā)式算法就是這樣一種策略。在每次擴展過程中，盡量選擇離最終路徑近的那些節(jié)點。

1.3 啟發(fā)式方法

定義2 設(shè)評價函數(shù)f(vj)=g(vs,vj)+h(vj,ve)[8]，式中，g(vs,vj)為從初始節(jié)點vs經(jīng)過尋徑算法到達節(jié)點vj的權(quán)值之和，且g(vs,vs)=0；h(vj,ve)為節(jié)點vj的代價函數(shù)，h(ve,ve)=0，它預(yù)測從vj到終點ve的代價。一個點是否能被優(yōu)先選用進行搜索，主要由評價函數(shù)f(vj)的值來決定。

引入代價函數(shù)h(vj,ve)后，每次對節(jié)點的擴散不再是盲目的，而是有方向性的。其值越大，算法的解也就越偏離最優(yōu)解，但同時時間耗費也越小；其值越小，搜索所花費的時間越大，算法的解也就越逼近最佳解?；趩l(fā)式的路徑搜索算法如下。

算法2：

(4)返回(1)。

定理1 設(shè)有序序列V′={vs,v1,v2,…,vj,…,vn,ve}，j=1,…,n，為使用啟發(fā)式方法求出的從初始點vs到目標(biāo)點ve的路徑上的點，該路徑P′=(vs,v1,v2,…,vj,…,vn,ve)，j=1,…,n，distmin(vk,vl)用來記錄節(jié)點vk到節(jié)點vl最小權(quán)值之和，若滿足(?vj)[h(vj,ve)≤distmin(vj,ve)∧(vj∈V′)]，則P′為最短路徑。

fp(ve)=gp(vs,ve)+hp(ve,ve)=gp(vs,ve)。

引入記號d(vk,vl)來表示邊的權(quán)，則：

即：

2 算法的改進

2.1 評價函數(shù)

評價函數(shù)f(vj)的任務(wù)主要是用來估計搜索路徑上某節(jié)點vj的重要性。理論上講，它可以是任意的函數(shù)，具體應(yīng)用中采用什么樣的形式，主要由應(yīng)用而定。一個節(jié)點的價值一般從兩方面考慮：搜索到該節(jié)點時算法已經(jīng)付出的代價g(vs,vj); 如果選擇從該節(jié)點出發(fā)到達目標(biāo)節(jié)點ve，算法將要付出的代價h(vj,ve)。 一般來說，已經(jīng)付出的代價g(vs,vj)的值是一定的，而最關(guān)鍵的就是根據(jù)具體應(yīng)用來選擇合適的h(vj,ve)。

在網(wǎng)絡(luò)地圖中，設(shè)兩點vj和ve的坐標(biāo)分別為(xj，yj)與(xe，ye)，常用的啟發(fā)式函數(shù)主要有：

曼哈頓距離：h(vj,ve)=(|xj-xe|+|yj-ye|)；

切比雪夫距離：h(vj,ve)=max{|xj-xe|,|yj-ye|}。

其他形式的代價函數(shù)也可以選擇，只要滿足最優(yōu)解條件即可。歐氏距離代表了兩點間的直線距離，是一般情況的首選。在此，考慮到計算機做乘方和開方運算，耗時比加減大很多，故選擇曼哈頓距離作為啟發(fā)函數(shù)。

2.2 搜索區(qū)域

Dijkstra算法的搜索區(qū)域，可近似地看成以初始節(jié)點Vs為圓心所構(gòu)成的一系列同心圓，各個節(jié)點依離初始節(jié)點的距離遠近而先后被搜索到。整個過程沒有涉及終點Ve所在的方向或位置，因此，其被搜索到的概率與其他節(jié)點Vj是相同的。若圖中頂點數(shù)目較多，或初始節(jié)點Vs與終點Ve間距離較大，算法實際運行效率將大大降低[10-11]。

啟發(fā)式的搜索方法能夠改變這種狀況。文獻[12]提出了一種矩形限制搜索區(qū)域，縮小了搜索的范圍，提高了效率。在此基礎(chǔ)上，本文將搜索區(qū)域進一步縮小，限制在一個條狀范圍內(nèi)，如圖1所示。以初始節(jié)點Vs和終點Ve分別畫半徑為r(r為搜索半徑，該值可調(diào)整)的圓，與兩圓相切的直線分別為L1和L2，則兩直線與兩圓圍成的條狀區(qū)域即為搜索區(qū)域。

圖1 搜索區(qū)域示意圖Fig.1 Schematic diagram of searching area

實際算法實現(xiàn)時，為了進一步簡化計算，可以將搜索區(qū)域的橫坐標(biāo)值進一步簡化為(xs-r,xe+r)，而縱坐標(biāo)軸限定在兩平行線L1，L2間不變。

初始時，根據(jù)經(jīng)驗，設(shè)置r值，運行算法，進行搜索，如果搜索到終點，則算法結(jié)束，否則，按預(yù)設(shè)增量增大r值，在一個更大的搜索區(qū)域上進行搜索，直至搜索到終點。最壞的情況即是搜索擴展到了整個區(qū)域。實際算法中，搜索半徑r值設(shè)定為一個遞增序列ri，形如ri={1, 1.5, 2, 2.5, 3, …}，如果根據(jù)前一個半徑序列的值沒有在搜索區(qū)域內(nèi)找到終點，則選擇半徑序列中的下一個值來進行搜索。

由于程序首先考慮的是位于條狀區(qū)域內(nèi)的點，而不是所有的點，這樣就減少了對無用節(jié)點的考察，加速了程序的運行。

2.3 排序方法

定義3 堆是滿足下列性質(zhì)的數(shù)列{k1,k2,…,kn}：

前者稱為小頂堆，后者稱為大頂堆[7]。在此主要關(guān)注前者，并且采用一種改進的堆結(jié)構(gòu)來進行排序。

左傾樹排序方法是眾多排序方法中較快的一種。在原始輸入數(shù)據(jù)任意排列的情況下，該算法的時間復(fù)雜度可以達到O(nlog2n)[2]。左傾樹實際上就是經(jīng)典堆結(jié)構(gòu)的一個改進。

定義4 左傾樹T是1棵具有特殊性質(zhì)的二叉樹,其中每個結(jié)點滿足下列性質(zhì)。

(1)給樹中每個節(jié)點k賦予1個Ek值：如果該節(jié)點具有不多于1個孩子，則Ek=1；如果該節(jié)點有兩個孩子k1和k2，則Ek=min{Ek1,Ek2}+1。

(2)根節(jié)點的值小于(僅考慮小頂堆)以該節(jié)點為根的子樹上所有節(jié)點的值；如果節(jié)點k無左孩子，則它必然無右孩子；如果k同時具有兩個孩子(分別為k1和k2)，則左孩子節(jié)點的Ek值Ek1大于等于右孩子節(jié)點的Ek值Ek2。

用左傾樹實現(xiàn)排序的過程和普通的堆排序相似，也分為構(gòu)造和排序兩個階段：第1階段執(zhí)行構(gòu)造過程，輸入含有n個節(jié)點的待排序序列，經(jīng)過n-1次左傾樹的合并過程，構(gòu)造1棵新的左傾樹；第2階段執(zhí)行排序過程，再經(jīng)過n-1次左傾樹的合并過程，從而最終實現(xiàn)排序。

合并過程描述如下(僅考慮兩棵樹的情況)：

(1)如果有一棵左傾樹為空樹，合并后的結(jié)果為另一棵左傾樹。

(2)將根節(jié)點值小的左傾樹的右子樹與另一棵左傾樹進行合并，使用合并后的結(jié)果代替該右子樹。

(3)如果合并后的結(jié)果不滿足左傾樹的條件，則可以通過交換該左傾樹的左右子樹，使之成為一棵左傾樹。

假設(shè)一棵左傾樹含有n個節(jié)點，由于“左傾”的性質(zhì)，從該樹根結(jié)點出發(fā)，一路沿著右子樹向前走，最多走log2(n+1)步(等于樹的高度)。又因為左傾樹的合并過程總是從右子樹方向進行的，這樣至多只需要O(log2n)步就可以訪問該樹右邊的子樹，同時完成合并工作，這是最壞的情況。顯然，左傾樹樹型最壞的情況是當(dāng)它的左右子樹較為平衡時；最佳樹型是當(dāng)它的所有節(jié)點的右指針為空時。

3 結(jié)果與分析

試驗?zāi)康氖菫榱俗C明改進算法在某市電子地圖不同圖層上尋徑的有效性，并分析搜索半徑r和兩點間直線距離k對有效性的影響。仿真試驗在處理器為Intel酷睿i5 4570(3.2 GHz)、內(nèi)存4 GB、硬盤1 TB、操作系統(tǒng)為Microsoft Windows 7的微機環(huán)境下進行。

3.1 尋徑時間

該市電子地圖有多個不同的圖層，分別含有508，1 033，2 013，3 998條邊。選定固定的兩個地理位置作為起點和終點，兩點間直線距離為k=10 km，同時，搜索半徑r設(shè)定為2 km，以尋徑時間作為衡量算法效率的指標(biāo)參數(shù)，分別從地理距離和擁堵時間兩方面來設(shè)定邊的權(quán)值，以對Dijkstra算法、RRSA算法和RSAHSPA算法的效率進行測試，其中RRSA指矩形限制搜索區(qū)域算法[12]。

圖2描述了在地理距離最短權(quán)值下3種算法的尋徑時間，在開始邊數(shù)為508的條件下，Dijkstra、RRSA和RSAHSPA所花費的尋徑時間分別為2 110，1 143，632 ms。隨著邊數(shù)的逐漸增加，3種算法花費的尋徑時間都逐漸增加，但Dijkstra比RRSA和RSAHSPA增加得更快，同時，RRSA和RSAHSPA所花費的尋徑時間增加變化緩慢，并且RSAHSPA算法一直低于RRSA算法。當(dāng)圖層邊數(shù)增加為3 998條時，3種算法的尋徑時間分別為34 412，6 617，3 216 ms。圖3描述了在擁堵時間最短權(quán)值下3種算法的尋徑時間，因此，本文所提方法優(yōu)于其他兩種方法。

圖2 尋路訪問時間對比(按地理距離最短)Fig.2 Comparison of path finding access time(by geographical distance shortest)

圖3 尋路訪問時間對比(按擁堵時間最短)Fig.3 Comparison of path finding access time(by congestion time shortest)

3.2 初始半徑r的選擇

保持上述試驗運行環(huán)境不變，針對RSAHSPA算法修改k數(shù)值，以地理距離最短作為路徑權(quán)重的情況為例，測試搜索半徑r值對算法所花費尋徑時間的影響。取k=10 km，初始半徑r分別選擇r=1,1.5,2,2.5,3 km，運行結(jié)果圖4所示。

圖4 不同初始r值對算法訪問時間的影響(k=10 km)Fig.4 Influence of different initial r values on accesstime of algorithm (k=10 km)

另外，取k=5 km，初始半徑r分別選擇r=0.5,0.7，1,1.5,2 km，運行結(jié)果圖5所示。

圖5 不同初始r值對算法訪問時間的影響(k=5 km)Fig.5 Influence of different initial r values on accesstime of algorithm (k=5 km)

為了對照，再取k=20 km，初始半徑r分別選擇r=1,2,4,6,8 km，運行結(jié)果圖6所示。

圖6 不同初始r值對算法訪問時間的影響(k=20 km)Fig.6 Influence of different initial r values on accesstime of algorithm (k=20 km)

試驗結(jié)果表明，在不同數(shù)值k的條件下，隨著圖層中邊數(shù)的增加，相同r值下，RSAHSPA算法的尋徑時間都會逐漸增大；在同一個數(shù)值k的條件下，不同的初始r值對RSAHSPA算法的尋徑時間影響顯著。例如，在圖4的k=10 km條件下，初始r=2, 2.5, 3 km的運行曲線幾乎在一起，說明在設(shè)置r=2 km 的搜索區(qū)域內(nèi)，已經(jīng)能夠找到一條起點到終點的最短路徑，此時，增加r值，對尋徑時間影響不大；r=1, 1.5 km需要更多的運行時間，說明在這樣的搜索范圍內(nèi)沒有找到最短路徑，需要增加r值在一個更大的范圍內(nèi)進行搜索，因此時間花費更多。圖5和圖6中，當(dāng)r分別增加至1 km和4 km后，再增大搜索半徑，對尋徑時間影響不大。根據(jù)圖4～圖6結(jié)果分析，r=k/5時算法運行效果最好，繼續(xù)增加r值，效率提高不明顯。

4 結(jié)論

本文將啟發(fā)式方法應(yīng)用到經(jīng)典的最短路徑算法之中，給出了網(wǎng)絡(luò)地圖中的一個新的路徑搜索算法。同時，在啟發(fā)式函數(shù)搜索范圍和排序方法方面，討論了算法的改進之處，并將其應(yīng)用到實現(xiàn)的算法中。仿真試驗結(jié)果證明了新的路徑搜索算法的優(yōu)越之處，與已有路徑選擇改進算法相比，能夠有效縮短路徑查找時間，從而更好地滿足出行需要。

[1] DIJKSTRA E W. A Note on Two Problems in Connexion with Graphs[J]. Numerische Mathematics, 1959, 1(1): 269-271.

[2] 湯彬. 一個用左傾樹實現(xiàn)O(nlog2n)排序的算法[J]. 微型電腦應(yīng)用, 1996 (1): 79-83. TANG Bin. A Sorting Algorithm Taking O(nlog2n) Time Using Leftist Tree[J]. Microcomputer Applications, 1996 (1): 79-83.

[3] WEISS M A, 陳越. 數(shù)據(jù)結(jié)構(gòu)與算法分析: C語言描述 [M]. 2版. 北京:人民郵電出版社, 2005. WEISS M A, CHEN Yue. Data Structures and Algorithm Analysis in C Language[M]. 2nd ed. Beijing: Posts & Telecom Press, 2005.

[4] 章永龍. Dijkstra最短路徑算法優(yōu)化[J]. 南昌工程學(xué)院學(xué)報, 2006, 25(3): 31-32. ZHANG Yong-long. Optimization of Dijkstra Algorithm [J]. Journal of Nanchang Institute of Technology, 2006, 25(3): 31-32.

[5] 張本群. 基于啟發(fā)式算法的路徑規(guī)劃[J]. 計算機仿真, 2012, 29(10): 341-343. ZHANG Ben-qun. Path Planning Based on Heuristic Algorithm [J]. Computer Simulation, 2012, 29(10): 341-343.

[6] AGRAWAL R, JAGADISH H V. Materialization and Incremental Update of Path Information[C]∥Proceedings of the 5th International Conference on Data Engineering. Los Angeles:IEEE, 1989: 374.

[7] 嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu)(C語言版) [M]. 北京:清華大學(xué)出版社, 1997. YAN Wei-min, WU Wei-min. Data Structure (in C Language) [M]. Beijing: Tsinghua University Press, 1997.[8] 馬少平. 人工智能[M]. 北京:清華大學(xué)出版社, 2004: 32-34. MA Shao-ping. Artificial Intelligence[M]. Beijing: Tsinghua University Press, 2004: 32-34.

[9] 尼爾松 N J. 人工智能[M]. 北京:機械工業(yè)出版社, 1999:145-150. NILSSON N J. Artificial Intelligence: A New Synthesis [M]. Beijing: China Machine Press, 1999:145-150.

[10]張錦明, 洪剛, 文銳, 等. Dijkstra最短路徑算法優(yōu)化策略[J]. 測繪科學(xué), 2009, 34(5): 105-106. ZHANG Jin-ming, HONG Gang, WEN Rui, et al. Optimization Strategies of the Dijkstra’s Shortest Route Algorithm [J]. Science of Surveying and Mapping, 2009, 34(5): 105-106.

[11]鄧方安, 雍龍泉, 周濤, 等. 基于“矩陣乘法”的網(wǎng)絡(luò)最短路徑算法[J]. 電子學(xué)報, 2009, 37(7): 951-956. DENG Fang-an,YONG Long-quan, ZHOU Tao, et al. Shortest Path Problem Algorithm in Network Based on Matrix Multiplication [J]. Acta Electronica Sinica, 2009, 37(7): 951-956.

[12]王海梅, 周獻中. 一種限制搜索區(qū)域的最短路徑改進算法[J]. 南京理工大學(xué)學(xué)報: 自然科學(xué)版, 2009, 33(5): 638-642. WANG Hai-mei, ZHOU Xian-zhong. Improved Shortest Path Algorithm for Restricted Searching Area[J]. Journal of Nanjing University of Science and Technology: Natural Science Edition, 2009, 33(5): 638-642.

An Improved Path Selecting Algorithm for Traffic Network

DUAN Ming-yi, ZHANG Wen

(School of Information Engineering, Zhongzhou University, Zhengzhou Henan 450044, China)

By using heuristic search method in artificial intelligence, focusing on transport network, on the basis of in-depth analysis of the classical Dijkstra shortest path algorithm, a shortest path algorithm based on heuristic and proved the effectiveness of this method is proposed. After a careful analysis of the improved algorithm, the respects needed to be improved are discussed. Combining with specific applications, the corresponding improvement strategies are proposed from the aspect of heuristic function, searching range and sorting method, and these improvements are applied to the simulation experiment. The result shows that (1)the proposed algorithm has good scalability in different layers; (2) compared with the existing improved path selecting algorithm, the proposed one can effectively shorten the path finding time under different path weight options, thereby to better meet the travel needs. The reference values of the initial search radius for different geographical distance are also given.

ITS; restricted searching area; heuristics; traffic network; path searching; leftist tree

2016-02-16

河南省科技攻關(guān)計劃項目(162102210327)

段明義(1978-)，男，河南鄭州人，碩士，副教授.(duanmingyi@126.com)

10.3969/j.issn.1002-0268.2016.11.018

U491, TP311

A

1002-0268(2016)11-0120-06