基于行程時間預測的城市車輛出行路徑推薦方法

李曉玉,邢 雪

(吉林化工學院信息與控制工程學院,吉林 吉林 132022)

隨著汽車數量逐年遞增,部分一線城市交通擁堵已由中心城區向邊緣城區擴散,給居民的工作生活帶來諸多不便。行程時間可靠性對于良好的駕駛體驗和保障順暢的公共交通具有至關重要作用,因此,在考慮路網交通均衡的基礎上,考慮車輛的行程時間,進行動態的路徑推薦,可最大限度提高路網整體出行效率[1]。目前,諸多學者對路網復雜狀況下車輛行程時間相關的路徑推薦問題進行了大量研究。車輛出行路徑選擇問題是智能交通系統(Intelligent Transportation System,ITS)中出行者信息服務系統主要解決的任務,而動態交通信息的獲取也是行程時間預測優化路徑推薦的前提[2]。郭保青等[3-4]提出的基于優化蟻群算法的路徑推薦模型,考慮了有障礙物的環境下臨時規避障礙物,提高了尋路成功率。一些學者從最大路徑可靠性和行程時間可靠性出發,提出應急車輛路徑選擇的優化方法[5-7]。另一些人提出結合A*算法和行程時間的搜尋實時最快路徑的方法[8-9]。智路平等[10]使用行程時間可靠性作為關鍵控制變量,結合權值異化的Dijkstra算法,提高路徑選擇效率。白紫秀等[11]結合路網狀態判別和行程時間,對私家車進行預約出行路徑推薦。Shen等[12]構造了一種混合圖結構,設計了考慮動態邊權的最短旅行時間路徑分析算法。綜上所述,對于城市路網車輛路徑選擇問題,學者們多從行程時間、路網行程時間可靠性的角度研究,但對動態路網行程時間的預測和通過最短路徑算法中求得的最短路徑不一定最優等問題考慮不足。研究依托于吉林市自然基金項目,通過構建動態圖卷積神經網絡(DGCN)對路網各路段進行多時間步行程時間預測,根據出行需求并考慮避讓擁堵區和均衡路網因素進行車輛出行路徑推薦。

1 基于行程時間預測的區域狀態識別

1.1 基于DGCN的路段行程時間預測模型

準確的行程時間預測是進行路徑推薦的基礎[2]。采用圖神經網絡對行程時間進行預測,特別是交通數據這種具備時空關系的特殊數據,可以很好地解決兩個節點之間的相關性以及路網的復結構和動態性能的學習問題。因此,本研究采用動態圖卷積網絡(Dynamic Graph Conrolutional Nerwork,DGCN)模型對行程時間進行預測。模型主要包含拉普拉斯矩陣潛在網絡(Laplacian Matrix Latent Network,即LMLN)模塊和基于圖卷積網絡(Graph Convolutional Network,GCN)的交通預測模塊。

拉普拉斯矩陣預測單元包括三部分:(1)特征采樣:對每天最近15、30、45 min的數據進行采樣,在減少特征的數據維度的同時對最近鄰的交通數據進行采樣;(2)空間注意力機制:為建立動態的交通路網的空間關系,采用注意力機制對路網當前近鄰時間的鄰接矩陣進行估計;(3)長短期記憶(Long Short-term Memory,LSTM)單元:通過LSTM單元提取時間和路網鄰接矩陣序列的特征。

基于GCN的交通預測模塊包含:(1)時間卷積層(Temporal Convolution Layer):主要包含四個卷積核為(1×ts)的二維卷積層,來提取數據中高維局部時間數據。(2)圖時間卷積層(Graph Temporal Convolution Layer):將GCN與TCL堆疊為時空模塊,集成GTCL模塊[13]。

1.2 基于交通信息加權路網的區域劃分模型

加載交通信息的路網滿足復雜網絡的基本特征,因此采用基于層次劃分復雜網絡的社區劃分算法中的GN算法。GN算法效率較高,可將所有節點及邊的有向關系考慮到網絡劃分之中,實驗的劃分結果具有層次性。路網分區結果的評判標準是模塊度Q,見公式(1),模塊度越大,則劃分的社團結構也越明顯[14]。

(1)

式中:m為網絡中節點總數,個;v、w為路網中任意兩個節點;Av、w為v、w兩個節點之間邊的權重;kw為節點w的度;kv為節點v的度;CvCw表示若v、w兩節點在同一社團,則δ=1,反之δ=0。

加權GN算法的具體流程為:(1)初始狀態下,每一個節點為一個獨立的社區,即該狀態下社區數與節點數相同;(2)忽略數據中邊的權重,求所有邊的邊介數;(3)將邊介數除以對應邊的權重,得邊權比;(4)移除邊權比最大的邊,計算當前網絡的模塊度Q;(5)對其余邊重復步驟(1)到步驟(4),并計算每一步的邊權比和模塊度,直至網絡中所有邊均被移除;(6)運行結束,取Q最大時對應的社團劃分數量和分區結果。

1.3 路網區域的動態交通狀態識別模型

由公安部2020年頒布的《道路交通擁堵度評價方法》可得,區間路段交通擁堵度評價應采用平均行程速度[15]。路段限速為40 km/h時,區間路段平均行程速度與交通擁堵度的對應關系,如表1所示。

表1 限速40 km/h時平均行程速度與交通擁堵度的對應關系

(1)用該評價方法求某路段的平均行程速度Vi,如公式(2)所示。

(2)

式中:Vi為路網內第i條道路平均行程速度,km/h;n為路段的數量,個;ti為車輛i通過區間路段的時間,h。

(2)計算路網或某區域內道路平均速度V,如公式(3)所示。

(3)

式中:Vi為路網內第i條道路平均行程速度,km/h;n為路段的數量,個。

(3)根據區域平均速度結合平均行程速度與交通擁堵度識別關系,確定區域交通狀態分級。

2 考慮擁堵區避讓的路徑推薦模型

為了量化城市路網中考慮避讓擁堵區前后整體擁堵程度的變化,引入路網擁堵均衡指數概念。對于整個城市路網,在時間幀為t時段內,將路網擁堵均衡指數定義為一個二維向量:Mt[N,V],路網擁堵均衡指數M計算方式如公式(4)所示。

(4)

式中:N為路網中路段數量,個;Ti為基于DGCN預測所得的路段i的行程時間,h;Li為對應的路段i長度,km;a為歸一化系數,算法中取10。

根據需求將最優路徑問題可分為基于距離最短或權重最小,基于距離最短方法中又可分為自由路徑和限制路徑。本研究采用Flody算法,是解決任意兩點之間的最短路徑算法,可解決交通網絡結構的最短路徑問題,該算法的核心是通過局部最優求解全局最優,進行動態規劃。首先尋找出目標OD的最短路徑長度,然后記錄下該長度的路徑,即可尋找到推薦的路線;將路徑中處于重度擁堵狀態區域中的路段進行移除,再重復以上步驟,即可尋找到基于擁堵區避讓的推薦路徑矩陣和路由矩陣。

基于擁堵區避讓的Flody算法流程如下。

(1)初始狀態:根據DGCN預測所得的行程時間數據,求得圖G初始基于行程時間的初始路由矩陣R0=[ri,j]n×n和鄰接矩陣W。

(5)

(6)

(2)k=0:即對于每一對頂點vi和vj,途徑頂點的下標≤k時,該路徑可分為兩段,即(vi,vo)和(v0,vj),這一長度就是兩段路徑的行程時間之和,比較這一新路徑和路徑(vi,vj),就可以確定vi到vj途經下標≤k的最短路徑。

(3)k=1:同理,該路徑可拆成(vi,…,vk)和(vk,…,vj)兩段,當長度在k=0時就確定路徑,再比較新路徑和前面已知的路徑(vi,vj),就可以確定途經下標≤k的最短路徑。

(4)重復以上步驟,直到k=n-1為止,得到從vi到vj所有可能的時間矩陣和對應的路由矩陣。

(5)選取部分路徑,去除其中有重度擁堵路段的邊,組成新的路網圖G1,重復步驟(1)～(4),得到基于避讓擁堵區的時間矩陣和路由矩陣,得出對應的路徑和行程時間。

3 實例驗證

3.1 基于DGCN的行程時間預測結果

本研究所使用的數據集來源于安徽省宣城市中心城區公開卡口數據集,openITS平臺整理發布,該區域內的總道路長度為174 km,包含2017年12月3日至9日全天的卡口過車數據和卡口GIS-T布點數據,卡口過車數據中一天的過車量數據大約有83萬條,刪除未識別的車牌號后數據量約74萬條,篩選后數據量約56萬條,日全天行程時間數據,包含一個交通特征即路段行程時間,在模型中將預測行程時間作為輸出;時隙劃分為15 min,每天的數據包含96個時隙,每小時所有數據有4個樣本,因此設置T=4,模型中訓練集、驗證集、測試集的數量占比為3∶1∶1。

實驗運用于Linux操作系統Ubuntu 18.04,GPU為RTX 3090×2,顯存為48G,采用Python 3.7代碼編寫,模型架構采用基于PyTorch 1.2.0的深度學習架構進行開發。在圖卷積和時間卷積中使用4個1×3的卷積核,預測時間步長c為12,學習率設為0.000 5,每一輪的衰減率為0.92,批次大小為8,使用l2_loss為損失函數,利用Adam作為優化器,在GTCL中設置切比雪夫多項式M=3,卷積核ts=3,多頭注意力機制k=4,預測時間間隔Tp=12。

為估計不同輸入的影響,使用最近鄰的數據建立輸入矩陣,用DGCN_r表示。為了進一步評估不同拉普拉斯矩陣對GCN的效率,特別是GAT,實驗將本方法與四種基于DGCN的其他方法進行了比較,其他方法分別為:(1)ASTGCN,其中使用了注意力拉普拉斯矩陣;(2)DGCN_Mask,使用了掩模拉普拉斯矩陣;(3)DGCN_Res,使用殘差拉普拉斯矩陣;(4)5 dGCN_GAT,一種用GAT代替模型的空間特征層GTCL的方法。所有方法比較的性能指標為:平均絕對百分比誤差(MAPE)、平均絕對誤差(MAE)和均方誤差(RMSE)。

在數據集上平均一小時交通預測精度如表2所示,結果表明,DGCN_Res模型的所有指標具有最佳性能。拉普拉斯潛在矩陣可以更好的提取道路網絡的動態空間關,DGCN_Res模型用經驗拉普拉斯矩陣代替了全局優化的殘差拉普拉斯矩陣,故精度優于其他模型,預測未來12個時段的結果。

表2 預測精度結果

實驗數據集來源于卡口GIS-T布點數據,其中包括39個卡口點,結合行程時間數據選取60個路段作為邊,采用傳統GN算法和加權GN算法對城市路網進行劃分,不同分區數和對應模塊度如表3所示。傳統GN算法和加權GN算法,隨著分區數量的增加,模塊度都在逐漸降低,說明實際路網中,各邊之間的相關性也在降低,結合擁堵區避讓的條件和實際路網中路段相關度,選擇分區數量為20,分區結果為[2,26,1]、[3,31,35]、[4,9,7]、[5]、[6,8,39,24]、[10,11,12]、[14,13]、[16,15]、[18,17]、[29,19,28]、[20]、[21]、[22]、[27,23]、[25,33]、[30]、[32]、[34,36]、[37]、[38],其中,加粗部分為重度擁堵區。根據分區結果,按順序將區域劃分為G1至G20,以便表示下一節擁堵區識別結果。

表3 加權GN算法分區結果

根據上一節行程時間預測的結果,可得預測的60個路段的行程時間數據,結合路網分區結果和區域狀態識別的步驟,得重度擁堵區域為:G3、G4、G6、G8、G11、G12、G15、G16,中度擁堵區域:G1、G2、G5、G6、G9、G13、G18,輕度擁堵區域:G10、G15、G17、G20,暢通區域G14、G19,部分區域交通狀態如表4所示。

表4 區域狀態識別結果

3.2 考慮避讓擁堵區的路徑推薦分析

初始狀態下基于行程時間的路網鄰接矩陣中,兩點之間的權重代表基于DGCN預測未來15 min后該路段的行程時間,記為v(i,j)。依次遍歷v(1,j)和v(i,1),比較v(1,j)、v(i,1)和v(i,j)的大小,如果v(1,j)+v(i,1)

若從敬亭湖公園附近卡口點19至檔案局附近卡口點1,可由第39輪的鄰接矩陣和路由矩陣得到所需時間和對應路徑;通過去除擁堵區所在節點進行重度擁堵區的避讓,也可得相對應的鄰接矩陣和路由矩陣從而得到避讓擁堵區的最短時間和路徑,并對A、B、C三組路徑進行展示。將初始最短時間路徑和考慮避讓擁堵區的條件下的路徑、所需的時間和路網擁堵均衡指數進行對比,如表5所示。引入路網擁堵均衡指數作為考慮避讓擁堵區前后路網擁堵狀態對比的重要參數,可得在避讓擁堵區的情況下,路網整體擁堵均衡指數降低,對重度擁堵區域的交通也有一定的緩沖。

表5 兩種方法的路徑推薦結果比較

4 結 論

出行路徑僅考慮路徑最短,可能造成交通網絡關鍵區的擁堵;以當前交通狀態進行路徑誘導,可能出現車輛到達某路段時路段交通狀態已經發生變化的情況。以實例中等城市路網為實驗對象,對每天最近鄰15 min、30 min、45 min數據進行采樣,使用殘差拉普拉斯矩陣的DGCN模型預測行程時間;通過加權GN算法結合實際路網情況進行分區,并根據平均行程時間識別區域擁堵狀態;建立考慮擁堵區避讓的路徑推薦模型,對比不同方案的路網均衡指數,避讓擁堵區前后路段,可在一定程度上降低路網全局擁堵狀態。因而通過多時間步預測路段交通狀態變化,再從全局考量針對已發生擁堵的區域進行避讓推薦路徑,一定程度上可減緩擁堵區的交通壓力,對中型城市交通具有一定的借鑒意義。