王志建，李達(dá)標(biāo)，崔 夏

(北方工業(yè)大學(xué)北京市城市道路交通智能控制技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京100144)

0 引 言

日漸擁堵的城市道路給人們出行帶來(lái)了巨大的困擾，正確地選擇一條合適的出行路徑會(huì)給出行者節(jié)約不少成本.路徑的選擇取決于該路線的行程時(shí)間和在該時(shí)間內(nèi)順利到達(dá)目的地的可靠性.出行天氣的不同會(huì)對(duì)行程時(shí)間產(chǎn)生較大影響，在降雨天氣下高德地圖對(duì)易擁堵路段進(jìn)行了標(biāo)定，方便出行者更好地選擇出行方式和路徑.國(guó)內(nèi)外不少學(xué)者在降雨的背景下對(duì)城市道路運(yùn)行狀態(tài)和行程時(shí)間的計(jì)算和預(yù)測(cè)展開(kāi)了大量的研究.許方經(jīng)[1]結(jié)合降雨對(duì)城市道路通行能力和道路網(wǎng)可靠性進(jìn)行了分析；姜桂艷[2]等用傳統(tǒng)的數(shù)學(xué)模型和支持向量機(jī)對(duì)行程時(shí)間進(jìn)行預(yù)測(cè)分析；丁宏飛[3]等采用了基于神經(jīng)網(wǎng)絡(luò)的BP 算法計(jì)算行程時(shí)間并取得了一定的成果；DUAN Y.J.[4]，Siripanpornchana[5]等采用不同的神經(jīng)網(wǎng)絡(luò)算法對(duì)行程時(shí)間預(yù)測(cè)做了大量的研究分析.綜上，計(jì)算行程時(shí)間的研究方法主要集中在數(shù)學(xué)理論模型和神經(jīng)網(wǎng)絡(luò).傳統(tǒng)的數(shù)學(xué)理論模型有較差的可移植性.前饋神經(jīng)網(wǎng)絡(luò)在學(xué)習(xí)速度上較慢且容易陷入局部最優(yōu)，而支持向量機(jī)更適合小樣本下的計(jì)算.

本文對(duì)軌跡數(shù)據(jù)進(jìn)行分析和預(yù)處理，把車(chē)輛軌跡劃分成若干條由最小路段組成的子路徑.把軌跡數(shù)據(jù)和降雨數(shù)據(jù)作為模型的輸入，通過(guò)LSTM神經(jīng)網(wǎng)絡(luò)對(duì)每條子路徑做行程時(shí)間的預(yù)測(cè)，最后把所有子路徑的行程時(shí)間求和得到最終的行程時(shí)間.同時(shí)與應(yīng)用較廣的算法Kalman、BP 神經(jīng)網(wǎng)絡(luò)和SVM 方法進(jìn)行對(duì)比分析.結(jié)果表明，本文算法在行程時(shí)間預(yù)測(cè)上有較高的準(zhǔn)確性和可靠性.

1 數(shù)據(jù)準(zhǔn)備

1.1 數(shù)據(jù)預(yù)處理

本文數(shù)據(jù)為中關(guān)村西區(qū)2018年7月1～7，10，17和24日，共10 d經(jīng)處理后的1 500萬(wàn)余條軌跡數(shù)據(jù).采集設(shè)備每12 s 上傳一條定位及車(chē)輛行駛狀態(tài)，數(shù)據(jù)集包含字段信息：CreateData、CreateTime、CarID、Longitude、Latitude、Velocity等.為提高數(shù)據(jù)的利用率，需要對(duì)原始數(shù)據(jù)進(jìn)行除冗處理.刪除GPS 狀態(tài)為0、速度異常、同一時(shí)刻重復(fù)記錄的數(shù)據(jù)，以及經(jīng)緯度超出地圖研究范圍和相鄰定位點(diǎn)存在較大偏移的數(shù)據(jù).

研究路網(wǎng)范圍為中關(guān)村西區(qū)，經(jīng)度為東經(jīng)116.273 2°～116.342 0°，緯度為北緯39.959 6°～39.996 2°.未打斷路網(wǎng)道路前該區(qū)域共計(jì)1 284 條道路，存在不同道路相交的節(jié)點(diǎn)處進(jìn)行打斷處理，分析其拓?fù)浣Y(jié)構(gòu)[6].打斷后路網(wǎng)數(shù)據(jù)集包含了4 686條路段和2 769個(gè)節(jié)點(diǎn)元素.打斷后的部分路網(wǎng)如圖1所示.

1.2 節(jié)點(diǎn)時(shí)刻及路段平均速度計(jì)算

地圖匹配完畢后，得到每輛車(chē)的行駛軌跡GIS數(shù)據(jù)，接下來(lái)計(jì)算浮動(dòng)車(chē)經(jīng)過(guò)每個(gè)節(jié)點(diǎn)(交叉口)的時(shí)刻，由于軌跡數(shù)據(jù)采樣時(shí)間間隔為12 s，按照城市道路一般行駛速度標(biāo)準(zhǔn)在一個(gè)采樣周期內(nèi)大概可以行駛130 m 左右.為方便計(jì)算通過(guò)節(jié)點(diǎn)的時(shí)刻，采用下面的方法進(jìn)行計(jì)算：

(1)一個(gè)采樣周期內(nèi)僅出現(xiàn)一個(gè)節(jié)點(diǎn).

圖1 路網(wǎng)局部拓?fù)銯ig.1 Local topology of road network

圖2中，Sn表示路段編號(hào)，Pn表示定位點(diǎn)，dn與dn+1表示定位點(diǎn)與節(jié)點(diǎn)之間的距離.

圖2 一個(gè)周期內(nèi)只有一個(gè)節(jié)點(diǎn)Fig.2 Only one node in a cycle

當(dāng)pn點(diǎn)速度為0時(shí)，考慮可能在等待紅燈，所以車(chē)輛經(jīng)過(guò)節(jié)點(diǎn)N時(shí)的時(shí)間計(jì)算為

當(dāng)pn點(diǎn)速度不為0 時(shí)，節(jié)點(diǎn)N的時(shí)刻可由前定位或后定位點(diǎn)獲取.

式中：N車(chē)輛經(jīng)過(guò)節(jié)點(diǎn)，Tn為車(chē)輛經(jīng)過(guò)節(jié)點(diǎn)N的時(shí)刻；dn和dn+1為兩個(gè)定位點(diǎn)距離節(jié)點(diǎn)的距離；tn和tn+1分別為相鄰兩點(diǎn)的定位時(shí)間；vn,n+1為相鄰兩點(diǎn)間的平均速度.

(2)一個(gè)采樣周期內(nèi)存在兩個(gè)及兩個(gè)以上節(jié)點(diǎn).

圖3中，N,N+j表示路段節(jié)點(diǎn)，j=1,2,3,…,n,經(jīng)過(guò)途中任意節(jié)點(diǎn)的時(shí)間為

式中：Tn+i為車(chē)輛經(jīng)過(guò)相鄰兩個(gè)定位點(diǎn)間某一個(gè)節(jié)點(diǎn)的時(shí)刻；dn+i為節(jié)點(diǎn)到定位點(diǎn)的距離.

圖3 一個(gè)周期內(nèi)有多個(gè)節(jié)點(diǎn)Fig.3 Multiple nodes in a cycle

計(jì)算行駛距離時(shí)會(huì)出現(xiàn)路段為非直線型和直線型路段，為方便計(jì)算定位點(diǎn)到節(jié)點(diǎn)的距離，采用混合距離計(jì)算方法.距離計(jì)算分為為兩部分：

①道路線型類(lèi)似于直線時(shí)，可根據(jù)經(jīng)緯度信息直接計(jì)算其歐式距離為

式中：r是地球半徑；φ1和φ2是點(diǎn)1 和點(diǎn)2 的緯度；λ1和λ2是點(diǎn)1和點(diǎn)2的經(jīng)度.

②當(dāng)路段成非直線時(shí)，采用速度—積分模型估計(jì)車(chē)輛行駛距離，即

已知車(chē)輛在時(shí)間段內(nèi)行駛的距離，可求的車(chē)輛在子路段里的平均速度為

式中：為最小路段平均車(chē)速；va為子路徑平均車(chē)速.

完成地圖匹配和節(jié)點(diǎn)時(shí)刻、平均速度計(jì)算后，將原始的GPS軌跡數(shù)據(jù)轉(zhuǎn)換成基于路段ID的軌跡信息表，數(shù)據(jù)表包含4條屬性，分別為：車(chē)輛ID、路段ID、路段末端節(jié)點(diǎn)時(shí)刻和路段平均行駛速度.

2 路徑行程時(shí)間計(jì)算方法

現(xiàn)有的研究方案中，通常將整個(gè)行駛路徑劃分為最小路段進(jìn)行旅行時(shí)間計(jì)算.在求解的過(guò)程中將最小路段行駛時(shí)間和交叉口損失時(shí)間相加，這樣計(jì)算固然簡(jiǎn)單，但是因?yàn)榻徊婵趽p失時(shí)間的不確定性，使得計(jì)算結(jié)果存在較大誤差.本文以行駛軌跡數(shù)據(jù)和GIS地圖數(shù)據(jù)支撐，對(duì)數(shù)據(jù)進(jìn)行分析利用數(shù)據(jù)流向如圖4所示.

在已知出行起點(diǎn)及終點(diǎn)的情況下，以最短路徑或最優(yōu)路徑為條件選擇路徑的基礎(chǔ)上，對(duì)每條路徑進(jìn)行行程時(shí)間的預(yù)測(cè).S表示路徑集合，每個(gè)元素是由道路名稱首字母縮寫(xiě)和編號(hào)組成.假設(shè)某出行者的路徑規(guī)劃如圖5所示.

圖4 數(shù)據(jù)流向圖Fig.4 Data flow diagram

圖5 出行路徑示意圖Fig.5 Travel path diagram

圖5中推薦的路徑一共經(jīng)過(guò)了7 條道路共計(jì)17個(gè)路段，可以表示為

本文計(jì)算行程時(shí)間不再是將每個(gè)最小路段的行程時(shí)間單獨(dú)計(jì)算出來(lái)最后單純相加，而是將路徑S根據(jù)已存在的歷史車(chē)輛行駛軌跡逐次匹配，將整條路徑S分成若干子路徑，子路徑是由最小路段累加獲得.匹配方法是把路徑S對(duì)應(yīng)的路段ID 序列起始點(diǎn)與基于路段ID 序列的每條歷史軌跡進(jìn)行匹配，記錄能連續(xù)匹配上的路段數(shù)和軌跡的條數(shù).計(jì)算每次匹配的權(quán)重確定最佳子路徑.

匹配路徑匹配算法：?jiǎn)栴}描述：已知路徑S={x1,x2,…,xn}，歷史軌跡數(shù)據(jù)庫(kù)carID 為文件列表，以路徑S 為參考依次與carID匹配，并記錄匹配上的路段 ID 和數(shù)量.1：For(int i=1;i ＜=length(i);i=i+a)2： NuCar=Nu(CarID)3： For(int Nu=1;Nu＜=NuCar;Nu++)4： CarID=NuCar 5： String TraCar=CarID.line 6： Int a=1 7： For(int y=1;y ＜=length[TraCar]；y++)8： String StrID=l[i]9： If StrID==TraCar[y]10： StrID=l(i++)11： a++12： printf(‘打印出相同路段數(shù)a’)13： Else a=1 14： Return(0)15： Return(0)16：Return(0)

路段數(shù)量統(tǒng)計(jì)之后，確定第一次匹配的子路徑，采用mapminmax[0,1]函數(shù)，對(duì)權(quán)值進(jìn)行歸一化分析.

式中：Y為歸一化后的權(quán)重值；Xmax,Xmin為數(shù)列X的最大值和最小值；xi表示匹配連續(xù)路段的數(shù)；Ni表示在樣本中連續(xù)路段數(shù)為xi的數(shù)量.最大Y值對(duì)應(yīng)的子路徑作為此次匹配結(jié)果，依次重復(fù)匹配直至路徑L完全匹配成功，過(guò)程圖如圖6所示.

路徑S可表示為子路徑的集合，即

路徑S組合之后，把每條子路徑與基于路段ID 的歷史軌跡進(jìn)行匹配，獲取起始時(shí)刻，子路徑行程時(shí)間和子路徑平均速度.此時(shí)的數(shù)據(jù)集并不是固定時(shí)間間隔的序列，為方便模型的訓(xùn)練和預(yù)測(cè)，對(duì)序列進(jìn)行了時(shí)間間隔為5 min 的數(shù)據(jù)處理.時(shí)間戳精確到分鐘，以5 的倍數(shù)存儲(chǔ).若5 min 間隔內(nèi)存在多條數(shù)據(jù)，行程時(shí)間和平均速度為多條數(shù)據(jù)均值；若5 min 內(nèi)無(wú)匹配數(shù)據(jù)的，取相鄰前后兩個(gè)5 min 數(shù)據(jù)的均值存儲(chǔ).具體的字段信息如表1所示.

圖6 分段匹配流程Fig.6 Piecewise matching process

表1 子路徑信息表Table1 Information of sub-path

總的行程時(shí)間為

式中：T為總的行程時(shí)間；ti表示通過(guò)LSTM 神經(jīng)網(wǎng)絡(luò)算法預(yù)測(cè)的每個(gè)子路徑的行程時(shí)間.

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

近年來(lái)交通數(shù)據(jù)量的快速增長(zhǎng)，導(dǎo)致傳統(tǒng)的計(jì)算方法和數(shù)學(xué)模型不能滿足對(duì)數(shù)據(jù)分析的要求，利用神經(jīng)網(wǎng)絡(luò)算法對(duì)大數(shù)據(jù)的分析得到了快速發(fā)展.部分學(xué)者采用LSTM 循環(huán)神經(jīng)網(wǎng)絡(luò)模型對(duì)行程時(shí)間的預(yù)測(cè)展開(kāi)深入研究，該模型可以自動(dòng)保存歷史序列信息，有特殊的時(shí)間特性結(jié)構(gòu)，對(duì)于行程時(shí)間預(yù)測(cè)有著良好的適應(yīng)性.單個(gè)模型結(jié)構(gòu)如圖7所示.

圖7 單個(gè)LSTM 單元的內(nèi)部結(jié)構(gòu)Fig.7 Internal structure of a single LSTM unit

遺忘函數(shù)為

輸入函數(shù)為

輸出函數(shù)為

式中：Wf、Wi、Wa、Wo和Uf、Ui、Ua、Uo為線性關(guān)系系數(shù)，即權(quán)重；bf、bi、ba、bo為計(jì)算偏倚；σ則是Sigmoid激活函數(shù)；⊙為Hadamard積.

細(xì)胞狀態(tài)更新為

3.1 構(gòu)建LSTM神經(jīng)網(wǎng)絡(luò)

本文構(gòu)建了一個(gè)LSTM 循環(huán)神經(jīng)網(wǎng)絡(luò)如圖8所示，該方法是在RNN 循環(huán)網(wǎng)絡(luò)中嵌入LSTM 的神經(jīng)單元.在t時(shí)刻下，網(wǎng)絡(luò)的輸入為觀測(cè)的歷史數(shù)據(jù)x(t)，輸出為未來(lái)的預(yù)測(cè)數(shù)據(jù)，通過(guò)LSTM單元的輸出h(t)得到

圖8 LSTM 循環(huán)神經(jīng)網(wǎng)絡(luò)Fig.8 LSTM recurrent neural network

圖8中，x(t)為歷史觀測(cè)數(shù)據(jù)，Win是輸入層到隱藏層的權(quán)值矩陣，Wout則為隱藏層到輸出層的權(quán)值矩陣，bout是輸出偏倚.本文設(shè)置的輸入為表1中連續(xù)的7條數(shù)據(jù).

3.2 訓(xùn)練模型

降雨程度的不同，導(dǎo)致行程時(shí)間不確定.把降雨量分為0～6共計(jì)7個(gè)等級(jí)[7]其中0表示無(wú)降雨，降雨量和降雨等級(jí)關(guān)系如表2所示.在表1的基礎(chǔ)上新增降雨等級(jí)特征，此時(shí)LSTM 的輸入?yún)?shù)為：起始時(shí)刻、行程時(shí)間(s)、路段平均速度(km/h)和降雨等級(jí)4個(gè)特征量.

表2 降雨等級(jí)Table2 Precipitation level

基于時(shí)間序列預(yù)測(cè)的LSTM 模型中，主要的內(nèi)部參數(shù)是隱藏層的維數(shù)和迭代次數(shù)，訓(xùn)練的同時(shí)也會(huì)生成參數(shù)之間的權(quán)重矩陣和參數(shù)偏倚.訓(xùn)練時(shí)將數(shù)據(jù)集分為3個(gè)部分：訓(xùn)練集(80%)，驗(yàn)證集(10%)，測(cè)試集(10%).網(wǎng)絡(luò)依靠訓(xùn)練集對(duì)全局損失函數(shù)進(jìn)行調(diào)整，通過(guò)驗(yàn)證集上的代價(jià)函數(shù)來(lái)選擇模型中隱藏層的維數(shù)，最后通過(guò)測(cè)試集對(duì)預(yù)測(cè)性能進(jìn)行評(píng)估.

最小損失函數(shù)Θ數(shù)學(xué)表達(dá)為

式中：Y表示實(shí)際觀測(cè)的時(shí)間序列；是對(duì)應(yīng)提前一步預(yù)測(cè)出行的時(shí)間序列.

損失函數(shù)為

式中：m是預(yù)測(cè)旅行時(shí)間的個(gè)數(shù).通過(guò)序列的反向傳播計(jì)算損失函數(shù)對(duì)權(quán)值的梯度，公式為

式中：表示t時(shí)刻下預(yù)測(cè)數(shù)據(jù).

影響序列變化關(guān)系的重要計(jì)算步驟是損失函數(shù)L對(duì)隱藏狀態(tài)h(t)和細(xì)胞狀態(tài)C(t)的梯度求解，損失函數(shù)對(duì)狀態(tài)偏倚的梯度求解與對(duì)權(quán)重求解類(lèi)似.

3.3 結(jié)果分析

本文研究路段以蘇州橋?yàn)槠瘘c(diǎn)，成府路與中關(guān)村東路交叉口為終點(diǎn)，途經(jīng)蘇州街路、北四環(huán)輔路和中關(guān)村東路.以出租車(chē)歷史行駛GIS數(shù)據(jù)為研究對(duì)象，對(duì)將來(lái)某時(shí)刻為出發(fā)點(diǎn)途經(jīng)該路程的行程時(shí)間進(jìn)行預(yù)測(cè)分析.分別對(duì)2018年7月10日(晴天)的早高峰和7月17日(雨天)的早晚高峰和平峰時(shí)段的行程時(shí)間進(jìn)行預(yù)測(cè).預(yù)測(cè)數(shù)據(jù)如表3～表6所示.

表3 08：00-09：00 預(yù)測(cè)數(shù)據(jù)(2018-07-10)Table3 Prediction data at 08：00-09：00(2018-07-10)

表4 08：00-09：00 預(yù)測(cè)數(shù)據(jù)(2018-07-17)Table4 Prediction data at 08：00-09：00(2018-07-17)

表5 13：00-14：00 預(yù)測(cè)數(shù)據(jù)(2018-07-17)Table5 Prediction data at 13：00-14：00(2018-07-17)

表6 18：00-19：00 預(yù)測(cè)數(shù)據(jù)(2018-07-17)Table6 Prediction data at 18：00-19：00(2018-07-17)

與傳統(tǒng)的BP、SVM 算法對(duì)比分析學(xué)習(xí)速度、預(yù)測(cè)誤差和模型的可靠性[8]，同時(shí)選取均方根誤差(ERMSE)監(jiān)視計(jì)算過(guò)程中預(yù)測(cè)值與真實(shí)值之間的誤差關(guān)系變化.

式中：ERMSE為均方根誤差，m是預(yù)測(cè)旅行時(shí)間的個(gè)數(shù).

使用偏差值95%置信水平下的置信區(qū)間來(lái)表示不同預(yù)測(cè)模型的可靠性.95%置信水平下的置信區(qū)間越小說(shuō)明波動(dòng)性越小，模型的可靠性越高；區(qū)間越靠近X軸誤差越小.

(1)圖9表明在預(yù)測(cè)結(jié)果上，此預(yù)測(cè)算法在保證預(yù)測(cè)精度為90%以上的準(zhǔn)確率為0.75.加入降雨特征比未加入降雨特征預(yù)測(cè)的結(jié)果更準(zhǔn)確，準(zhǔn)確率由0.75上升至0.85.

(2)圖10展示了在學(xué)習(xí)速度方面，BP、LSTM和SVM 存在較大的差異，分別是712，1 054，2 756 s.LSTM 神經(jīng)網(wǎng)絡(luò)的復(fù)雜程度比BP 神經(jīng)網(wǎng)絡(luò)大很多，但是在計(jì)算速率上并未相差太大.

(3)圖11在可靠性上表明，LSTM 模型的置信區(qū)間比BP，SVM和Kalman都要小，說(shuō)明該模型的偏差值波動(dòng)較小，具有較高的可靠性.同時(shí)該模型的置信區(qū)間更接近X軸，說(shuō)明預(yù)測(cè)值更接近于真實(shí)值.

圖9 不同時(shí)段的行程時(shí)間預(yù)測(cè)Fig.9 Prediction of travel time in different time

圖10 鏈路的RMSE 累積分布Fig.10 Distribution of RMSE for each link

圖11 可靠性分析Fig.11 Analysis of reliability

4 結(jié) 論

以北京市中關(guān)村西區(qū)出租車(chē)行駛的GIS 數(shù)據(jù)和北京市區(qū)域降水?dāng)?shù)據(jù)為研究對(duì)象，采用LSTM神經(jīng)網(wǎng)絡(luò)對(duì)行程時(shí)間進(jìn)行預(yù)測(cè)分析.設(shè)計(jì)非最小路段的行程時(shí)間計(jì)算方法，結(jié)果表明，該方法具有更高的計(jì)算效率和更少的誤差計(jì)算.對(duì)比分析BP、SVM 和Kalman 模型預(yù)測(cè)的結(jié)果.結(jié)果表明，在加入降雨特征的情況下，本文所用的LSTM 方法在滿足精確度前提下?lián)碛休^快的訓(xùn)練速度和預(yù)測(cè)可靠性.本文的研究建立在良好的數(shù)據(jù)支撐上，對(duì)數(shù)據(jù)準(zhǔn)確度要求較高.在后續(xù)的研究中應(yīng)適當(dāng)降低數(shù)據(jù)要求，提高該模型的可移植性.