基于預測堵車信息的路徑動態規劃系統

侯辰飛, 朱健慧, 劉可昕, 楊峻, 劉蕊

(1.蘭州交通大學, 機電工程學院, 甘肅, 蘭州 730070;2.南京理工大學, 機械工程學院, 江蘇, 南京 210094)

0 引言

路徑規劃是研究無人駕駛領域的一個重要環節,也是智能交通系統的重要組成之一,合理的規劃方案極具現實應用意義。近年來,國內外學者將Floyd算法[1]、Dijkstra算法[2-3]、A*算法[4-5]、粒子群算法[6-7]、遺傳算法[8-9]等各類算法用于路徑規劃,并通過改進使之具有更好的應用效果。但不少規劃算法實時性較差,為此本文引入ARIMA-WNN組合預測模型對未來道路交通流量進行預測,基于預測數據對道路進行動態規劃,解決路徑規劃中的滯后性問題。

1 系統結構

本文提出的規劃系統由汽車、交通流量監測設備、導航中心等3部分組成。交通流量監測設備用于路口流量的實時記錄,并每隔一段時間將數據發送至導航中心,導航中心用于接收監測設備發送的流量數據并依據流量數據進行規劃。

2 ARIMA-WNN加權預測模型

2.1 ARIMA模型

整合移動平均自回歸(ARIMA)模型結構簡單,具有良好的可靠性,是重要的時間序列預測方法。對于短時期的時間序列分析適用性好,但前提是輸入的時間序列必須是穩定的。模型的基本思想是將被預測單位隨著時間的向后推移產生的新序列作為一個隨機序列,假設隨機序列是線性且平穩變化的,則近似描述這個隨機數列,利用序列的現在值及過去值預測未來值,數學表達式通常為

(θ1εt-1+θ2εt-2+…+θqεt-q)

(1)

2.2 小波神經網絡預測模型

小波神經網絡以BP神經網絡的拓撲結構為基礎,以小波基函數為隱含層節點的傳遞函數,在信號前向傳播的同時誤差反向傳播[10]。小波神經網絡的拓撲結構如圖1所示。

圖1 小波神經網絡拓撲結構

圖1中,X、Y分別為小波神經網絡的輸入、輸出參數,ωij、ωjk均為小波神經網絡的權值。

輸入xi(i=1,2,…,k)時,隱含層的輸出公式為

(2)

式(2)中,bj為小波基函數的平移因子,aj為小波基函數的伸縮因子,hj為小波基函數。本文采用Morlet母小波基函數,其公式為

y=cos(1.75x)e-x2/2

(3)

小波神經網絡的權值修正與BP的修正算法類似,采用梯度修正法修正網絡權值和基函數參數。

神經網絡的訓練時,應按照以下順序進行。

第一步:網絡初始化。

第二步:利用訓練集樣本訓練神經網絡。

第三步:計算預測輸出值和誤差。

第四步:根據網絡輸出和期望輸入的誤差來修正權值和小波函數的參數,進一步逼近期望值。

第五步:利用測試集樣本測試精度。

第六步:判斷是否滿足算法結束條件(達到設定的迭代次數或期望精度),不滿足則返回第三步。

小波神經網絡算法流程如圖2所示。

圖2 小波神經網絡算法流程

2.3 組合預測模型

ARIMA僅能對交通流量的線性部分進行預測分析,無法分析非線性部分,數據挖掘能力一般,而WNN對數據的非線性成分有良好的挖掘能力。本文使用ARIMA-WNN組合預測模型[11],使2種模型優勢互補,綜合利用歷史數據中的線性和非線性部分。

利用ARIMA對原始觀測數據Q={Q1,Q2,…,Qt}進行擬合,得到擬合序列P={P1,P2,…,Pt},將兩序列相減得到ARIMA的殘差序列E={E1,E2,…,Et},其中:

Et=Qt-Pt

(4)

(5)

組合預測模型的流程如圖3所示。

圖3 ARIMA-WNN組合預測模型流程

根據圖3的預測流程,首先確定預測間隔。不同時間下對同一路段進行預測,每次的預測結果都不相同,可能導致同段路徑的優化方案也不同。為了避免算法的靈敏度過高,以s作為1個子時間段g,多個子時間段組成1個父時間段G,假設1個父時間段由y個子時間段組成,即Gy={g1,g2,…,gy},共涵蓋s×y。要求組合預測模型每s×y進行1次預測,每次預測s×y的交通流量,犧牲部分動態性換取穩定性。

其次,確定s和y預測數據是導航中心進行局部優化的基礎,預測越準確、穩定,優化的可靠性越高。本文選取15 min作為1個子時間段,即s=15,計算Gy內預測數據的平均絕對誤差MAE、平均絕對百分比誤差MAPE和均方根誤差RMSE,結合生活實際路口情況和數理基礎,倘若Gy滿足:

(6)

則認為Gy={g1,g2,…,gy}是一個有效預測時間段,該時間段內的預測結果準確性高,可以為后續的局部優化提供數據基礎。

每個指標的計算公式如下:

(7)

(8)

(9)

式(7)～式(9)中,n為樣本數。

3 堵車情況下路徑動態規劃

3.1 堵車損耗

確定堵車損耗的關鍵在于確定發生擁堵的車輛數量。本文通過組合預測模型預測未來交通流量,基于預測數據判斷未來發生擁堵的車輛數量,計算方法如下:

cm,i=nm,i-nm

(10)

式(10)中,cm,i為i時刻m節點發生擁堵的車輛數量,nm,i為i時刻m節點的車輛數量,nm為m節點所能承受的不發生擁堵的最大車輛數。假設只在節點位置發生堵車,并參考文獻[12]中車輛在i時刻通過堵車節點時會有額外損耗。額外損耗計算方法如下:

km,i=α×cm,i

(11)

式(11)中,km,i為i時刻通過節點m節點的額外損耗,α為單位額外損耗。

3.2 路徑規劃

本文采用改進的Dijkstra算法結合未來交通流量預測進行路徑規劃。傳統Dijkstra算法的基本思路是從起點開始,每次向一個距離最短的點擴展,與其相鄰的點的距離也隨之更新。由于所有邊的權值均不小于0,不存在一個距離更短的、沒擴展過的點,因此這個點的距離不再發生變化,保證了算法的正確性。在二維空間中,假設起點為m,終點為n,每個點都有一對規定的坐標(kn,ln),其中,kn為m到n的最短距離,ln為m到n的最短路徑中的上一節點,則m到n的最短路徑求解步驟如下。

第一步:對起點、終點及其他點坐標進行初始化,標記起點為m,記j=m,其他所有節點不作標記。

第二步:對所有已標記的點k到與其直接相連的未標記的點n的距離進行檢驗,即kn=min{kn,dkn+kn},其中dkn表示k到與其直接相連的點n的距離。

第三步:選取點w,使ki=min{kn},其中n表示所有未標記的點,則w為最短路徑上的一點,更新其狀態為已標記。

第四步:對所有點進行遍歷,直至所有點均已被標記,否則j=w,返回第二步。

傳統的Dijkstra算法沒有考慮道路堵車情況的影響,導致規劃出的路徑存在一定的滯后性,因此本文通過考慮未來道路堵車情況,使規劃更加合理,減少滯后性,其中規劃步驟如下。

第一步:使用Dijkstra進行初始的路徑規劃。

第二步:依據正常情況下汽車的平均行駛速度依次計算到達初始路徑上各個節點的時間,到達時間大于其中一個有效預測時間段的則不納入考慮。利用歷史數據對一個有效預測時間段內可能通過的節點的交通流量進行預測,再結合預測結果判斷車輛到達某節點時是否會發生堵車,倘若發生堵車則賦予該節點堵車損耗,并將該節點和周圍r內的所有節點加入集合H中。計算H中所有節點的到達時間,并依據到達時的交通流量判斷到達時是否會發生堵車,倘若堵車則同樣賦予該節點堵車損耗。最后使用Dijkstra算法對該區域進行局部優化。

通過流量預測發現車輛行駛至X節點時會發生堵車現象,計算X周圍節點的到達時間并判斷是否會發生堵車,發現其周圍的節點P、Q同樣發生堵車,賦予節點X、P、Q各自的堵車損耗,結合堵車損耗進行路徑的局部優化。

第三步:倘若車程大于一個有效預測時間段,則在第一個有效預測時間段駕駛結束后,重復第二步,把此時的位置作為第二步的起點。

4 實驗結果

以某區域道路信息為例進行實驗分析,道路的無向圖如圖4所示。

圖4 道路無向圖

圖4中,1為起點,16為終點,以道路長度(km)為權值,范圍內共20個節點。調用路口交通流量監測系統中的歷史數據,以節點7為例,歷史數據如圖5所示,其余節點的計算與節點7相同。

圖5 某路口實際交通流量

通過圖5可主觀判斷該時間序列是平穩的,需通過ADF單位根檢驗法對其進行單位根檢驗,得到p=0.022<0.05,確定為平穩時間序列,再利用SPSSAU確定當p=1、q=1時模型擬合最好。最后對殘差做Q統計量檢驗,Q6=0.683,p6=0.409>0.1,在0.1的顯著性水平下不能拒絕原假設,即模型殘差是白噪聲,模型基本滿足要求。因此,每15 min為1個時間段,可利用ARIMA(1,1,0)模型預測得到未來的交通流量。

建立ARIMA-WNN組合模型,步驟見2.3節,權值選擇為0.01,參數學習率為0.001,迭代學習次數為100。

最后依據式(6)確定有效預測時間段Gy,若y的取值為5,則有效預測時間段為75 min。有效最終擬合效果見表1。

表1 ARIMA-WNN擬合效果表

由表1可知,有效預測時間段內的MAE、MAPE、RMSE值均較小,預測效果較好,數據的準確性為后續的路徑規劃奠定了基礎。

本文使用Dijkstra算法進行全局規劃,確定最短路徑為91 km。初始路徑如圖6所示。

圖6 初始路徑

結合預測數據對路徑進行局部優化得到:當節點7不發生堵車時最大車輛數量為40,單位額外損耗α=0.032,車輛的平均行駛車速為40 km/h,75 min內車輛可到達節點5與11之間。當車輛開始出發后約1 h到達節點7,則可求得c5,60≈156,k5,60≈5.000,即車輛若想通過節點7就需要付出5 km作為堵車損耗。以同樣的方法確定周圍節點是否發生堵車以及堵車情況如何,發現節點7周圍路口均不堵車。根據堵車情況進行局部優化,此時最短路徑為95 km。局部優化路徑如圖7所示。

圖7 局部優化路徑

由于有效預測時間為75 min,但車輛在75 min內無法到達終點,因此需要在第一次75 min結束后對下一階段路徑再次進行優化,用同樣的方法計算得到節點17、18會發生堵車,路車損耗分別為2.5 km、3.0 km。對第二階段的路程進行局部優化,此時最短路徑為97.0 km,車輛在有效預測時間段內到達終點,倘若不進行局部優化,仍堅持初始路徑則需要98.5 km。最終路徑如圖8所示。

圖8 最終路徑

5 總結

在私家車數量越來越多、道路堵車越來越嚴重的情況下,目前的導航系統均基于當前道路情況進行規劃,且無法對堵車信息進行量化考慮并納入路徑的規劃中,導致車輛時常無法以最短的時間到達目的地。因此,本文提出一種基于預測交通流量的規劃系統,使用Dijkstra算法進行全局規劃的同時利用道路交通數據預測交通流量,基于道路情況選擇合適的α值,判斷道路是否會發生堵車及堵車程度,合理地對路徑進行局部優化,減輕了堵車帶來的影響。本文提出的方法具有以下優勢。

(1) 基于未來道路情況進行規劃,動態性能好,改善了傳統規劃的滯后性。

(2) 利用預測模型對未來短時交通流量進行預測并量化,將量化后的道路情況納入路徑規劃中進行局部優化,從而減輕了道路擁堵給駕駛帶來的影響,縮短了實際行駛距離。

(3) 可操作性強,具備一定的推廣意義,還可類比應用于惡劣天氣下部分交通樞紐癱瘓情況下的列車調度、節假日期間大規模出行情況下的路徑規劃等。

但是利用未來道路情況進行局部優化時,需要存儲的道路交通數據量較大,且在某情況下,局部優化后的路徑不一定是最優路徑,今后可以進一步改進。