基于DA* 算法的路徑誘導(dǎo)優(yōu)化研究

趙 沖 賀春林

(西華師范大學 計算機學院，四川 南充437000)

近年來，隨著我國經(jīng)濟的飛速發(fā)展，車輛的人均占有率呈現(xiàn)幾何級增長，隨之而來的交通擁堵及交通事故也頻繁發(fā)生。為了改善該狀況，有以下兩種可行方法：①拓寬道路，合理建設(shè)和布局城市規(guī)劃，但道路的擴充和增加受各種情況制約，發(fā)展水平遠不如車輛增加的速度;②對行駛中的車輛進行動態(tài)路徑誘導(dǎo)，將車輛合理分布在不同的道路上，以提高空閑路段的道路利用率，分散車流，防止擁堵。

基于GIS 的智能交通系統(tǒng)(intelligent transportation system，ITS)越來越受到學者的關(guān)注，各種路徑選擇算法和策略的研究為改善交通狀況提供了方向。1973 年，日本CACS(comprehensive automobile traffic control system)實現(xiàn)了基于RF 射頻通信的車載動態(tài)路徑誘導(dǎo)系統(tǒng);1986 年，歐洲智能交通發(fā)起名為“EUREKA”的聯(lián)合研發(fā)計劃，包含以車輛定位信息為主的“PROMETHEUS”部分和道路基礎(chǔ)設(shè)計為主的“DRIVE”部分;1992年，美國的TravTek(travel technology)開始運行，這是一種典型的自治型路徑誘導(dǎo)系統(tǒng);我國的路徑誘導(dǎo)系統(tǒng)研究起步較晚，1995 年，由上海交警總隊和同濟大學研發(fā)出多段接力式動態(tài)標志路線引導(dǎo)系統(tǒng)，其基本方法是通過道路兩旁的可變交通牌及廣播來實現(xiàn)交通分流的目的［1］。

路徑誘導(dǎo)系統(tǒng)可視為基于圖論的尋找最短路徑問題。路徑的起點為圖的初始節(jié)點，路徑的終點為圖的目標節(jié)點。但兩點間的最短問題，并不僅僅是“空間距離最短”，有時要根據(jù)現(xiàn)實情況，改變?yōu)樗琛皶r間最短”或“費用最少”［2-3］。解決最短路徑常用的算法有基于盲目式搜索的Dijkstra 算法和Floyd 算法、基于啟發(fā)式搜索的A*算法、基于生物習性的蟻群算法和遺傳算法，以及神經(jīng)網(wǎng)絡(luò)算法。筆者主要介紹經(jīng)典的Dijkstra 算法和A* 算法，并提出了帶動態(tài)權(quán)值的DA* 算法，通過仿真實驗來驗證其有效性和可行性。

1 交通流的表示

路徑誘導(dǎo)系統(tǒng)依賴于交通信息的準確性和實時性，一般需要道路狀況信息、交通狀況信息、氣象信息及交通法規(guī)信息等。其中交通狀況信息包括流量、道路占有率、行程時間和行車速度等信息。收集交通信息的方法主要有自動采集法和非自動采集法兩種。自動采集法主要利用檢測線圈、超聲波檢測器、紅外檢測器及微波檢測器采集信息;非自動檢測法則利用人工、試驗車及攝影視頻裝置來采集信息［4］。

1.1 交通流數(shù)學模型

車輛勻速運動時，路程= 速度× 時間(s=ut)，但在實際生活中，車輛并不可能始終保持勻速運動，因此，用u=s/t來計算實際的車流速度是不可取的。有關(guān)如何計算道路上行駛車輛的速度，有下面幾種方法：

1935 年，格林希爾茲提出了速度-密度線性模型［5］，可知：

式中：uf為暢行速度;ρx為阻塞密度。當車流密度較大時，車速降低;當車流密度較小時，車速升高;當車流密度為0，即路段沒有車流時，實際車速等于車輛自由行駛的速度uf;當車流密度最大，即ρ=s/l時，實際車速u=0，其中l(wèi)為車輛平均長度。

根據(jù)格林希爾茲提出的速度-密度模型，可以推導(dǎo)出速度-流量模型。

由式(1)可得：

將式(2)代入q=ρu可得：

式中，qx為交通流量。當交通密度為0 時，流量為0;當交通流量增大時，直至達到道路的通行能力上限，交通密度為最佳密度ρm，即道路通行情況達到最佳狀態(tài);交通密度繼續(xù)增大，此時車流速度降低，流量減少，直至交通密度達到ρx，即阻塞密度時，速度與流量均接近于零。

1975 年，DANIEL 與MARTHOW 在《交通流理論》中提出時間-流量模型：

式中：cx為當前路段的容量;α，β 為參數(shù)，大量實驗表明，當α=2.62，β=5 時，模型最優(yōu)［6］。

將式(3)代入式(4)可得時間t與速度u的函數(shù)關(guān)系為：

在式(2)～式(5)中，僅車輛速度ux是未知量，速度可通過車輛行駛過程中接收到的廣播信息來獲取。目前我國的交通誘導(dǎo)系統(tǒng)(traffic guidance system，TGS)主要通過無線電信號向行駛中的車輛進行廣播，播發(fā)的實時交通信息包括主要路段的行程時間、交通擁擠情況、交通法規(guī)、交通事故信息、廣域的最優(yōu)路徑選擇信息、道路施工信息、天氣情況及停車場信息等。

1.2 路段權(quán)值計算

路段的權(quán)值與距離s、時間t及速度u有關(guān)。當距離s增大時，權(quán)值也增大，即權(quán)值w與距離s成正比;當時間t增加時，權(quán)值w也增大，因為距離與時間成正比，所以權(quán)值w與時間t的函數(shù)為單調(diào)遞增的曲線;當速度u增大時，權(quán)值w減小，因為速度與時間成反比，所以權(quán)值w與速度u的函數(shù)為單調(diào)遞減的曲線。

根據(jù)以上描述，可得出權(quán)值w與距離s、時間t、速度u的函數(shù)表達式為：

其中，λ 為距離與時間的比例，其取值受車型和車主主觀意識影響。例如，載重貨車在擁堵路段，頻繁起步與剎車所消耗的燃油費用比小型汽車消耗的燃油費用高得多，因此，載重貨車的λ值要低于小型汽車，即在路徑選擇上，載重貨車會優(yōu)先選擇路程較長但道路暢通的路段。對于小型汽車司機而言，過長的距離費用可能帶來大量的時間消耗與燃油費用，因此，小型汽車司機在路徑選擇時會傾向于略為擁堵但路程較短的道路;而對于初學車者而言，擁堵路段的路況較復(fù)雜，根據(jù)交通流理論跟馳原理，在擁堵路段上對司機的反應(yīng)速度及精神集中度要求較高［7-8］，因此，在距離代價可以接受的情況下，初學者會優(yōu)先選擇道路暢通的路段。

對于任一條路段，s是固定值，且s=ut;λ 由自主設(shè)置且固定不變。將s=ut代入式(5)可得：

其中僅ux為變量，即對于該路段，權(quán)值僅受車流速度的影響。對于城市道路而言，每個時刻的車流量可能并不相同，車流速度在不同的時間段取不同的值，因此路段權(quán)值隨著車流速度的變化而變化，即道路擁有動態(tài)權(quán)值。

2 路徑搜索算法描述

2.1 Dijkstra 算法

Dijkstra 算法是基于廣度優(yōu)先算法，其優(yōu)點是必定能找到一條路徑使得初始節(jié)點到目標節(jié)點間的距離最短［9］。但因為廣度優(yōu)先算法搜索的節(jié)點數(shù)量多，時間復(fù)雜度高，因此在中間節(jié)點較多的情況下，算法的實用性不高。

Dijkstra 算法是盲目的搜索方法，即沒有利用問題本身的特性信息，在決定被擴展的節(jié)點時，既沒有考慮該節(jié)點在解的路徑上的可能性有多大，又沒有考慮是否有利于問題求解及求出的解是否為最優(yōu)。Dijkstra 算法需要遍歷圖中所有的節(jié)點，在城市交通網(wǎng)絡(luò)中，每一個路口都是一個節(jié)點，因此Dijkstra 算法的時間復(fù)雜度和空間復(fù)雜度都較高，不太適用于要求實時性的路徑誘導(dǎo)。

2.2 A* 算法

A* 算法是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的方法，利用估價函數(shù)和實際值的對比來選擇最佳路徑，屬于啟發(fā)式搜索的優(yōu)化，在搜索中加入了與問題有關(guān)的啟發(fā)性信息，用于指導(dǎo)搜索朝著最有希望的方向進行，加速問題的求解過程并找到最優(yōu)解，其核心公式為f(n) =g(n) +h(n) 。其中：f(n) 為初始節(jié)點經(jīng)節(jié)點n到目標節(jié)點的估價函數(shù);g(n) 為初始節(jié)點到節(jié)點n的實際代價;h(n)為從節(jié)點n到目標節(jié)點的最佳路徑的估計代價，可以取兩節(jié)點間歐幾理德距離作為估價值，即

這樣估價函數(shù)f在g值一定的情況下，受估價值h的制約，節(jié)點距目標點越近，h值越小，f值也相對越小，這樣就能保證最短路的搜索向終點的方向進行。故A* 算法優(yōu)于毫無方向地向四周搜索的Dijkstra 算法。

A* 算法的搜索效率在很大程度上取決于h(n)，h(n)所攜帶的啟發(fā)性信息越多，搜索時所擴展的節(jié)點數(shù)越少，搜索效率就越高。在實際應(yīng)用中，A* 算法能用較短的時間尋找到一條最優(yōu)路徑，盡管這條最優(yōu)路徑也許不是最短路徑。在城市交通路網(wǎng)中，A* 算法并不能有效地預(yù)防車流堵塞問題，因此提出動態(tài)賦權(quán)的改進A* 算法，筆者將其命名為DA* 算法，實質(zhì)上就是為h(n)函數(shù)增加一條動態(tài)的啟發(fā)性信息，以根據(jù)路段上的實時車流速度來改變h(n) 的函數(shù)值，在路徑選擇上優(yōu)先考慮暢通無阻的路線。

2.3 DA* 算法

由A* 算法的步驟可知，在選擇節(jié)點N的后繼節(jié)點時，f值最小的節(jié)點會優(yōu)先考慮?；谠撛瓌t，筆者將算法的啟發(fā)式函數(shù)f(n) =g(n) +h(n)改進為f(n)=g(n)+h(n)+w(n)。其中，令w(n)=σ(w(x，t))，即w(n)為t時刻x路段的權(quán)值。DA* 算法流程如圖1 所示。

從圖1 可知，當路段中的車速信息變化時，路段的權(quán)值也隨之變化，因此路徑的選擇也會相應(yīng)改變。例如，從起點S出發(fā)，有S→A、S→B兩條路徑可以選擇，且A、B兩點到目標節(jié)點的直線距離滿足：g(A) ＞g(B) ，且h(A) =h(B) 。

圖1 DA* 算法流程圖

(1)當S→A和S→B路段上車速相等，即σ(w(A，t))= σ(w(B，t))時，f(A)＞f(B)，DA*算法會轉(zhuǎn)變成傳統(tǒng)的A* 算法，路徑選擇與傳統(tǒng)算法保持一致，即可以保證尋找到最優(yōu)路徑。

(2)當S→A和S→B路段上車速不等時，假設(shè)S→A路段堵塞，即σ(w(A，t))＜σ(w(B，t))時，不能直接比較f(A) 與f(B) 的大小，而需要根據(jù)權(quán)值計算公式中的λ 取值來決定路徑的選擇，即在付出一定行駛距離代價的情況下，DA* 算法能尋找到一條行駛速度快、時間短，且距離可接受的優(yōu)化路徑。

3 實證分析

DA* 算法主要解決的是城市交通中的道路擁堵問題，而城市路段的交通狀況主要受時間及周圍建筑情況的影響。從時間段來考慮，上下班高峰期與非高峰期的車流量有明顯區(qū)別，節(jié)假日與工作日的車流相比，在時段上呈現(xiàn)均勻分布，對路段交通情況的分析要結(jié)合道路各個時段的特點;從周邊建筑情況來看，車站、學校、政府機關(guān)、商業(yè)寫字樓、大型商場及旅游景點等路段的路況各有其分布規(guī)律。因此筆者在實驗中將引入一條路況比較復(fù)雜的城市交通路網(wǎng)，以四川省南充市西華師范大學華鳳校區(qū)至西華師范大學北湖校區(qū)的路網(wǎng)為實驗對象，該路網(wǎng)模擬圖如圖2 所示。

圖2 中A點表示西華師范大學華鳳校區(qū)，為路網(wǎng)的起點;S點表示西華師范大學北湖校區(qū)，為路網(wǎng)的終點，途徑各路段長度及各路口與終點的直線距離如表1 所示。

圖2 西華師范大學華鳳校區(qū)—北湖校區(qū)路網(wǎng)模擬圖

表1 路網(wǎng)中各路段的距離值

表1 中數(shù)據(jù)由百度地圖測距工具測得。根據(jù)實際情況作出如下假設(shè)：城市道路按等級可以分為4 類，快速路、主干道、次干道和支路，其中A→C、C→G、G→F為快速路，車流速度限制值為60 km/h;H→R、Q→R、R→S為支路，以服務(wù)功能為主，連接次干道與小區(qū)路，除了考慮車流量外，還必須考慮道路間行人數(shù)量，全天限速為20 km/h;其余路段為市區(qū)主、次干道，根據(jù)時段不同呈現(xiàn)圖3 所示曲線分布［10-11］。

圖3 市區(qū)路段不同時段車速曲線圖

從圖3 可以看出，車流速度在上下班高峰期呈現(xiàn)明顯的下降趨勢，而在其他時段則保持平穩(wěn)態(tài)勢。筆者以工作日的路況為基礎(chǔ)，忽略路段與路段之間的差異，按照圖3 所示的速度曲線對車輛行駛過程進行模擬誘導(dǎo)。

對路網(wǎng)中的各個路段取不同的λ 值(當λ=0時為傳統(tǒng)A* 算法)來計算權(quán)值，然后進行DA*算法路徑搜索，得到不同路徑所花費的時間和距離耗費，如表2 所示。

表2 A* 算法(λ=0 時)與DA* 算法耗費的時間和距離費用表

從表2 可知，λ 的取值與路徑選擇關(guān)系為：當λ=0 時，DA* 算法與傳統(tǒng)A* 算法相等。當0 ＜λ ＜1 時，λ 取值越趨近于0，時間耗費越少，距離耗費越多;而λ 取值越趨近于1，時間和距離耗費越趨近于傳統(tǒng)A* 算法。因此，車輛可以根據(jù)自身需要來確定λ 的取值。

在車流量比較密集時，即平均車速為20 km/h時，傳統(tǒng)A* 算法所耗費的時間為638 s，而DA* 算法耗費的時間為511 s，節(jié)省了約20%的時間;傳統(tǒng)A* 算法耗費的距離為3 553 m，而DA* 算法耗費的距離為4 466 m，比傳統(tǒng)A* 算法多耗費約20%的距離費用。

在車流量發(fā)生擁堵，即平均車速為10 km/h時，傳統(tǒng)A* 算法耗費的時間為1 125 s，耗費的距離為3 553 m，而DA* 算法耗費的時間為605 s，耗費的距離為3 963 m，即DA* 算法在付出多走約10% 距離代價的情況下，節(jié)省了約46% 的時間。

當車流暢通時，DA* 算法與傳統(tǒng)A* 算法可選擇相同的路徑，因為A* 算法可優(yōu)點是保證可以找到一條最優(yōu)路徑，因此，DA* 算法也能保證找到一條最優(yōu)路徑;當車流開始擁堵時，傳統(tǒng)A*算法無法有效地避開擁堵路段，只能依靠路段的距離耗費值來選擇路徑，而DA* 算法則可以通過接收到的數(shù)據(jù)信息了解將要到達下一路段的擁堵情況，從而動態(tài)變更路段權(quán)值，實現(xiàn)實時的尋路策略。

4 結(jié)論

針對近年來我國的車輛擁有量越來越大、道路擁堵越來越嚴重的情況，通過對交通流的分析和對現(xiàn)有路徑誘導(dǎo)系統(tǒng)的運用，設(shè)計出對道路進行變換權(quán)值計算的方法，并將道路權(quán)值運用于A* 算法搜索路徑的啟發(fā)式函數(shù)中，對實時交通信息做出動態(tài)的響應(yīng)，以實現(xiàn)A* 算法的擁堵控制策略。仿真實驗表明，DA* 算法在道路擁堵時具有節(jié)省20% ～46%的行車時間的優(yōu)越性能。

［1］ 景玲.城市動態(tài)路徑誘導(dǎo)系統(tǒng)框架及最優(yōu)路徑選擇算法研究［D］.重慶：重慶大學，2002.

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

［3］ 王行風，賈凌.GIS 支持下的城市交通網(wǎng)絡(luò)最短路徑研究［J］.計算機與現(xiàn)代化，2005(3)：9 -13.

［4］ 章先陣，吳超仲，初秀民，等.基于機器視覺的公路交通設(shè)施信息采集系統(tǒng)設(shè)計［J］. 武漢理工大學學報(信息與管理工程版)，2004，26(5)：62 -66.

［5］ 曹亞康，劉立英，王衛(wèi)衛(wèi).城市快速路交通流速度-密度模型研究［J］.物流技術(shù)，2013，32(7)：166-169.

［6］ 丁銳.基于VANET 的車輛動態(tài)路徑選擇研究［D］.長春：吉林大學，2013.

［7］ 賀春林.一種基于視頻的車輛檢測算法［J］.計算機科學，2005，32(5)：243 -245.

［8］ 劉建.基于CAPS_WebGIS 的車輛監(jiān)控系統(tǒng)的研究［J］. 武漢理工大學學報(信息與管理工程版)，2012，34(3)：297 -300.

［9］ 田哲文，劉峰宇，鄧亞東，等. 汽車防追尾預(yù)警系統(tǒng)安全距離數(shù)學模型［J］.武漢理工大學學報(信息與管理工程版)，2012，31(4)：590 -593.

［10］ 嚴蔚敏，吳偉明.數(shù)據(jù)結(jié)構(gòu)［M］.北京：清華大學出版社，1997：186 -190.

［11］ 南充市順慶區(qū)人民政府網(wǎng).順慶緩堵保暢：關(guān)鍵要發(fā)揮每條道路的作用［EB/OL］.［2015 -01 -05］. http：//www.shunqing.gov.cn/Detail.php?id=35064.