基于預(yù)測堵車信息的路徑動態(tài)規(guī)劃系統(tǒng)

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

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

0 引言

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

1 系統(tǒng)結(jié)構(gòu)

本文提出的規(guī)劃系統(tǒng)由汽車、交通流量監(jiān)測設(shè)備、導(dǎo)航中心等3部分組成。交通流量監(jiān)測設(shè)備用于路口流量的實時記錄,并每隔一段時間將數(shù)據(jù)發(fā)送至導(dǎo)航中心,導(dǎo)航中心用于接收監(jiān)測設(shè)備發(fā)送的流量數(shù)據(jù)并依據(jù)流量數(shù)據(jù)進行規(guī)劃。

2 ARIMA-WNN加權(quán)預(yù)測模型

2.1 ARIMA模型

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

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

(1)

2.2 小波神經(jīng)網(wǎng)絡(luò)預(yù)測模型

小波神經(jīng)網(wǎng)絡(luò)以BP神經(jīng)網(wǎng)絡(luò)的拓撲結(jié)構(gòu)為基礎(chǔ),以小波基函數(shù)為隱含層節(jié)點的傳遞函數(shù),在信號前向傳播的同時誤差反向傳播[10]。小波神經(jīng)網(wǎng)絡(luò)的拓撲結(jié)構(gòu)如圖1所示。

圖1 小波神經(jīng)網(wǎng)絡(luò)拓撲結(jié)構(gòu)

圖1中,X、Y分別為小波神經(jīng)網(wǎng)絡(luò)的輸入、輸出參數(shù),ωij、ωjk均為小波神經(jīng)網(wǎng)絡(luò)的權(quán)值。

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

(2)

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

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

(3)

小波神經(jīng)網(wǎng)絡(luò)的權(quán)值修正與BP的修正算法類似,采用梯度修正法修正網(wǎng)絡(luò)權(quán)值和基函數(shù)參數(shù)。

神經(jīng)網(wǎng)絡(luò)的訓(xùn)練時,應(yīng)按照以下順序進行。

第一步:網(wǎng)絡(luò)初始化。

第二步:利用訓(xùn)練集樣本訓(xùn)練神經(jīng)網(wǎng)絡(luò)。

第三步:計算預(yù)測輸出值和誤差。

第四步:根據(jù)網(wǎng)絡(luò)輸出和期望輸入的誤差來修正權(quán)值和小波函數(shù)的參數(shù),進一步逼近期望值。

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

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

小波神經(jīng)網(wǎng)絡(luò)算法流程如圖2所示。

圖2 小波神經(jīng)網(wǎng)絡(luò)算法流程

2.3 組合預(yù)測模型

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

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

Et=Qt-Pt

(4)

(5)

組合預(yù)測模型的流程如圖3所示。

圖3 ARIMA-WNN組合預(yù)測模型流程

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

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

(6)

則認為Gy={g1,g2,…,gy}是一個有效預(yù)測時間段,該時間段內(nèi)的預(yù)測結(jié)果準(zhǔn)確性高,可以為后續(xù)的局部優(yōu)化提供數(shù)據(jù)基礎(chǔ)。

每個指標(biāo)的計算公式如下:

(7)

(8)

(9)

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

3 堵車情況下路徑動態(tài)規(guī)劃

3.1 堵車損耗

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

cm,i=nm,i-nm

(10)

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

km,i=α×cm,i

(11)

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

3.2 路徑規(guī)劃

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

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

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

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

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

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

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

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

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

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

4 實驗結(jié)果

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

圖4 道路無向圖

圖4中,1為起點,16為終點,以道路長度(km)為權(quán)值,范圍內(nèi)共20個節(jié)點。調(diào)用路口交通流量監(jiān)測系統(tǒng)中的歷史數(shù)據(jù),以節(jié)點7為例,歷史數(shù)據(jù)如圖5所示,其余節(jié)點的計算與節(jié)點7相同。

圖5 某路口實際交通流量

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

建立ARIMA-WNN組合模型,步驟見2.3節(jié),權(quán)值選擇為0.01,參數(shù)學(xué)習(xí)率為0.001,迭代學(xué)習(xí)次數(shù)為100。

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

表1 ARIMA-WNN擬合效果表

由表1可知,有效預(yù)測時間段內(nèi)的MAE、MAPE、RMSE值均較小,預(yù)測效果較好,數(shù)據(jù)的準(zhǔn)確性為后續(xù)的路徑規(guī)劃奠定了基礎(chǔ)。

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

圖6 初始路徑

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

圖7 局部優(yōu)化路徑

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

圖8 最終路徑

5 總結(jié)

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

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

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

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

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