李曉玉,邢 雪

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

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

1 基于行程時(shí)間預(yù)測(cè)的區(qū)域狀態(tài)識(shí)別

1.1 基于DGCN的路段行程時(shí)間預(yù)測(cè)模型

準(zhǔn)確的行程時(shí)間預(yù)測(cè)是進(jìn)行路徑推薦的基礎(chǔ)[2]。采用圖神經(jīng)網(wǎng)絡(luò)對(duì)行程時(shí)間進(jìn)行預(yù)測(cè),特別是交通數(shù)據(jù)這種具備時(shí)空關(guān)系的特殊數(shù)據(jù),可以很好地解決兩個(gè)節(jié)點(diǎn)之間的相關(guān)性以及路網(wǎng)的復(fù)結(jié)構(gòu)和動(dòng)態(tài)性能的學(xué)習(xí)問(wèn)題。因此,本研究采用動(dòng)態(tài)圖卷積網(wǎng)絡(luò)(Dynamic Graph Conrolutional Nerwork,DGCN)模型對(duì)行程時(shí)間進(jìn)行預(yù)測(cè)。模型主要包含拉普拉斯矩陣潛在網(wǎng)絡(luò)(Laplacian Matrix Latent Network,即LMLN)模塊和基于圖卷積網(wǎng)絡(luò)(Graph Convolutional Network,GCN)的交通預(yù)測(cè)模塊。

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

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

1.2 基于交通信息加權(quán)路網(wǎng)的區(qū)域劃分模型

加載交通信息的路網(wǎng)滿(mǎn)足復(fù)雜網(wǎng)絡(luò)的基本特征,因此采用基于層次劃分復(fù)雜網(wǎng)絡(luò)的社區(qū)劃分算法中的GN算法。GN算法效率較高,可將所有節(jié)點(diǎn)及邊的有向關(guān)系考慮到網(wǎng)絡(luò)劃分之中,實(shí)驗(yàn)的劃分結(jié)果具有層次性。路網(wǎng)分區(qū)結(jié)果的評(píng)判標(biāo)準(zhǔn)是模塊度Q,見(jiàn)公式(1),模塊度越大,則劃分的社團(tuán)結(jié)構(gòu)也越明顯[14]。

(1)

式中:m為網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù),個(gè);v、w為路網(wǎng)中任意兩個(gè)節(jié)點(diǎn);Av、w為v、w兩個(gè)節(jié)點(diǎn)之間邊的權(quán)重;kw為節(jié)點(diǎn)w的度;kv為節(jié)點(diǎn)v的度;CvCw表示若v、w兩節(jié)點(diǎn)在同一社團(tuán),則δ=1,反之δ=0。

加權(quán)GN算法的具體流程為:(1)初始狀態(tài)下,每一個(gè)節(jié)點(diǎn)為一個(gè)獨(dú)立的社區(qū),即該狀態(tài)下社區(qū)數(shù)與節(jié)點(diǎn)數(shù)相同;(2)忽略數(shù)據(jù)中邊的權(quán)重,求所有邊的邊介數(shù);(3)將邊介數(shù)除以對(duì)應(yīng)邊的權(quán)重,得邊權(quán)比;(4)移除邊權(quán)比最大的邊,計(jì)算當(dāng)前網(wǎng)絡(luò)的模塊度Q;(5)對(duì)其余邊重復(fù)步驟(1)到步驟(4),并計(jì)算每一步的邊權(quán)比和模塊度,直至網(wǎng)絡(luò)中所有邊均被移除;(6)運(yùn)行結(jié)束,取Q最大時(shí)對(duì)應(yīng)的社團(tuán)劃分?jǐn)?shù)量和分區(qū)結(jié)果。

1.3 路網(wǎng)區(qū)域的動(dòng)態(tài)交通狀態(tài)識(shí)別模型

由公安部2020年頒布的《道路交通擁堵度評(píng)價(jià)方法》可得,區(qū)間路段交通擁堵度評(píng)價(jià)應(yīng)采用平均行程速度[15]。路段限速為40 km/h時(shí),區(qū)間路段平均行程速度與交通擁堵度的對(duì)應(yīng)關(guān)系,如表1所示。

表1 限速40 km/h時(shí)平均行程速度與交通擁堵度的對(duì)應(yīng)關(guān)系

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

(2)

式中:Vi為路網(wǎng)內(nèi)第i條道路平均行程速度,km/h;n為路段的數(shù)量,個(gè);ti為車(chē)輛i通過(guò)區(qū)間路段的時(shí)間,h。

(2)計(jì)算路網(wǎng)或某區(qū)域內(nèi)道路平均速度V,如公式(3)所示。

(3)

式中:Vi為路網(wǎng)內(nèi)第i條道路平均行程速度,km/h;n為路段的數(shù)量,個(gè)。

(3)根據(jù)區(qū)域平均速度結(jié)合平均行程速度與交通擁堵度識(shí)別關(guān)系,確定區(qū)域交通狀態(tài)分級(jí)。

2 考慮擁堵區(qū)避讓的路徑推薦模型

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

(4)

式中:N為路網(wǎng)中路段數(shù)量,個(gè);Ti為基于DGCN預(yù)測(cè)所得的路段i的行程時(shí)間,h;Li為對(duì)應(yīng)的路段i長(zhǎng)度,km;a為歸一化系數(shù),算法中取10。

根據(jù)需求將最優(yōu)路徑問(wèn)題可分為基于距離最短或權(quán)重最小,基于距離最短方法中又可分為自由路徑和限制路徑。本研究采用Flody算法,是解決任意兩點(diǎn)之間的最短路徑算法,可解決交通網(wǎng)絡(luò)結(jié)構(gòu)的最短路徑問(wèn)題,該算法的核心是通過(guò)局部最優(yōu)求解全局最優(yōu),進(jìn)行動(dòng)態(tài)規(guī)劃。首先尋找出目標(biāo)OD的最短路徑長(zhǎng)度,然后記錄下該長(zhǎng)度的路徑,即可尋找到推薦的路線(xiàn);將路徑中處于重度擁堵?tīng)顟B(tài)區(qū)域中的路段進(jìn)行移除,再重復(fù)以上步驟,即可尋找到基于擁堵區(qū)避讓的推薦路徑矩陣和路由矩陣。

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

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

(5)

(6)

(2)k=0:即對(duì)于每一對(duì)頂點(diǎn)vi和vj,途徑頂點(diǎn)的下標(biāo)≤k時(shí),該路徑可分為兩段,即(vi,vo)和(v0,vj),這一長(zhǎng)度就是兩段路徑的行程時(shí)間之和,比較這一新路徑和路徑(vi,vj),就可以確定vi到vj途經(jīng)下標(biāo)≤k的最短路徑。

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

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

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

3 實(shí)例驗(yàn)證

3.1 基于DGCN的行程時(shí)間預(yù)測(cè)結(jié)果

本研究所使用的數(shù)據(jù)集來(lái)源于安徽省宣城市中心城區(qū)公開(kāi)卡口數(shù)據(jù)集,openITS平臺(tái)整理發(fā)布,該區(qū)域內(nèi)的總道路長(zhǎng)度為174 km,包含2017年12月3日至9日全天的卡口過(guò)車(chē)數(shù)據(jù)和卡口GIS-T布點(diǎn)數(shù)據(jù),卡口過(guò)車(chē)數(shù)據(jù)中一天的過(guò)車(chē)量數(shù)據(jù)大約有83萬(wàn)條,刪除未識(shí)別的車(chē)牌號(hào)后數(shù)據(jù)量約74萬(wàn)條,篩選后數(shù)據(jù)量約56萬(wàn)條,日全天行程時(shí)間數(shù)據(jù),包含一個(gè)交通特征即路段行程時(shí)間,在模型中將預(yù)測(cè)行程時(shí)間作為輸出;時(shí)隙劃分為15 min,每天的數(shù)據(jù)包含96個(gè)時(shí)隙,每小時(shí)所有數(shù)據(jù)有4個(gè)樣本,因此設(shè)置T=4,模型中訓(xùn)練集、驗(yàn)證集、測(cè)試集的數(shù)量占比為3∶1∶1。

實(shí)驗(yàn)運(yùn)用于Linux操作系統(tǒng)Ubuntu 18.04,GPU為RTX 3090×2,顯存為48G,采用Python 3.7代碼編寫(xiě),模型架構(gòu)采用基于PyTorch 1.2.0的深度學(xué)習(xí)架構(gòu)進(jìn)行開(kāi)發(fā)。在圖卷積和時(shí)間卷積中使用4個(gè)1×3的卷積核,預(yù)測(cè)時(shí)間步長(zhǎng)c為12,學(xué)習(xí)率設(shè)為0.000 5,每一輪的衰減率為0.92,批次大小為8,使用l2_loss為損失函數(shù),利用Adam作為優(yōu)化器,在GTCL中設(shè)置切比雪夫多項(xiàng)式M=3,卷積核ts=3,多頭注意力機(jī)制k=4,預(yù)測(cè)時(shí)間間隔Tp=12。

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

在數(shù)據(jù)集上平均一小時(shí)交通預(yù)測(cè)精度如表2所示,結(jié)果表明,DGCN_Res模型的所有指標(biāo)具有最佳性能。拉普拉斯?jié)撛诰仃嚳梢愿玫奶崛〉缆肪W(wǎng)絡(luò)的動(dòng)態(tài)空間關(guān),DGCN_Res模型用經(jīng)驗(yàn)拉普拉斯矩陣代替了全局優(yōu)化的殘差拉普拉斯矩陣,故精度優(yōu)于其他模型,預(yù)測(cè)未來(lái)12個(gè)時(shí)段的結(jié)果。

表2 預(yù)測(cè)精度結(jié)果

實(shí)驗(yàn)數(shù)據(jù)集來(lái)源于卡口GIS-T布點(diǎn)數(shù)據(jù),其中包括39個(gè)卡口點(diǎn),結(jié)合行程時(shí)間數(shù)據(jù)選取60個(gè)路段作為邊,采用傳統(tǒng)GN算法和加權(quán)GN算法對(duì)城市路網(wǎng)進(jìn)行劃分,不同分區(qū)數(shù)和對(duì)應(yīng)模塊度如表3所示。傳統(tǒng)GN算法和加權(quán)GN算法,隨著分區(qū)數(shù)量的增加,模塊度都在逐漸降低,說(shuō)明實(shí)際路網(wǎng)中,各邊之間的相關(guān)性也在降低,結(jié)合擁堵區(qū)避讓的條件和實(shí)際路網(wǎng)中路段相關(guān)度,選擇分區(qū)數(shù)量為20,分區(qū)結(jié)果為[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],其中,加粗部分為重度擁堵區(qū)。根據(jù)分區(qū)結(jié)果,按順序?qū)^(qū)域劃分為G1至G20,以便表示下一節(jié)擁堵區(qū)識(shí)別結(jié)果。

表3 加權(quán)GN算法分區(qū)結(jié)果

根據(jù)上一節(jié)行程時(shí)間預(yù)測(cè)的結(jié)果,可得預(yù)測(cè)的60個(gè)路段的行程時(shí)間數(shù)據(jù),結(jié)合路網(wǎng)分區(qū)結(jié)果和區(qū)域狀態(tài)識(shí)別的步驟,得重度擁堵區(qū)域?yàn)?G3、G4、G6、G8、G11、G12、G15、G16,中度擁堵區(qū)域:G1、G2、G5、G6、G9、G13、G18,輕度擁堵區(qū)域:G10、G15、G17、G20,暢通區(qū)域G14、G19,部分區(qū)域交通狀態(tài)如表4所示。

表4 區(qū)域狀態(tài)識(shí)別結(jié)果

3.2 考慮避讓擁堵區(qū)的路徑推薦分析

初始狀態(tài)下基于行程時(shí)間的路網(wǎng)鄰接矩陣中,兩點(diǎn)之間的權(quán)重代表基于DGCN預(yù)測(cè)未來(lái)15 min后該路段的行程時(shí)間,記為v(i,j)。依次遍歷v(1,j)和v(i,1),比較v(1,j)、v(i,1)和v(i,j)的大小,如果v(1,j)+v(i,1)

若從敬亭湖公園附近卡口點(diǎn)19至檔案局附近卡口點(diǎn)1,可由第39輪的鄰接矩陣和路由矩陣得到所需時(shí)間和對(duì)應(yīng)路徑;通過(guò)去除擁堵區(qū)所在節(jié)點(diǎn)進(jìn)行重度擁堵區(qū)的避讓,也可得相對(duì)應(yīng)的鄰接矩陣和路由矩陣從而得到避讓擁堵區(qū)的最短時(shí)間和路徑,并對(duì)A、B、C三組路徑進(jìn)行展示。將初始最短時(shí)間路徑和考慮避讓擁堵區(qū)的條件下的路徑、所需的時(shí)間和路網(wǎng)擁堵均衡指數(shù)進(jìn)行對(duì)比,如表5所示。引入路網(wǎng)擁堵均衡指數(shù)作為考慮避讓擁堵區(qū)前后路網(wǎng)擁堵?tīng)顟B(tài)對(duì)比的重要參數(shù),可得在避讓擁堵區(qū)的情況下,路網(wǎng)整體擁堵均衡指數(shù)降低,對(duì)重度擁堵區(qū)域的交通也有一定的緩沖。

表5 兩種方法的路徑推薦結(jié)果比較

4 結(jié) 論

出行路徑僅考慮路徑最短,可能造成交通網(wǎng)絡(luò)關(guān)鍵區(qū)的擁堵;以當(dāng)前交通狀態(tài)進(jìn)行路徑誘導(dǎo),可能出現(xiàn)車(chē)輛到達(dá)某路段時(shí)路段交通狀態(tài)已經(jīng)發(fā)生變化的情況。以實(shí)例中等城市路網(wǎng)為實(shí)驗(yàn)對(duì)象,對(duì)每天最近鄰15 min、30 min、45 min數(shù)據(jù)進(jìn)行采樣,使用殘差拉普拉斯矩陣的DGCN模型預(yù)測(cè)行程時(shí)間;通過(guò)加權(quán)GN算法結(jié)合實(shí)際路網(wǎng)情況進(jìn)行分區(qū),并根據(jù)平均行程時(shí)間識(shí)別區(qū)域擁堵?tīng)顟B(tài);建立考慮擁堵區(qū)避讓的路徑推薦模型,對(duì)比不同方案的路網(wǎng)均衡指數(shù),避讓擁堵區(qū)前后路段,可在一定程度上降低路網(wǎng)全局擁堵?tīng)顟B(tài)。因而通過(guò)多時(shí)間步預(yù)測(cè)路段交通狀態(tài)變化,再?gòu)娜挚剂酷槍?duì)已發(fā)生擁堵的區(qū)域進(jìn)行避讓推薦路徑,一定程度上可減緩擁堵區(qū)的交通壓力,對(duì)中型城市交通具有一定的借鑒意義。