趙 沖 賀春林

(西華師范大學(xué) 計(jì)算機(jī)學(xué)院，四川 南充437000)

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

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

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

1 交通流的表示

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

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

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

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

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

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

由式(1)可得：

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

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

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

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

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

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

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

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

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

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

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

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

2 路徑搜索算法描述

2.1 Dijkstra 算法

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

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

2.2 A* 算法

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

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

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

2.3 DA* 算法

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

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

圖1 DA* 算法流程圖

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

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

3 實(shí)證分析

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

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

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

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

表1 中數(shù)據(jù)由百度地圖測距工具測得。根據(jù)實(shí)際情況作出如下假設(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ù)時(shí)段不同呈現(xiàn)圖3 所示曲線分布［10-11］。

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

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

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

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

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

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

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

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

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

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

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