基于多圖時空圖卷積神經網絡的網約車需求預測①

周云彤,熊衛華,姜 明

1(浙江理工大學 機械與自動控制學院,杭州 310018)

2(杭州電子科技大學 計算機學院,杭州 310018)

1 引言

網約車是當今社會的主要出行方式之一,為人們的生活帶來了便捷,然而這一行業也存在許多問題,如乘客等待時間長,司機空車率高[1].造成這些問題的主要原因是網約車調度不合理,過多的車輛集中在繁忙區域導致車輛的供給大于需求,而在較為偏遠的地區,網約車數量極少,分布極為稀疏[2].網約車需求預測可以有效應對這一問題,通過預測區域內網約車的需求,提前引導司機前往不同的區域,從而避免出現網約車分布不均勻的問題[3].

網約車需求預測是智能交通系統的重要組成部分,也是交通大數據分析的一項難題,這是因為其受到多種時空因素的共同影響,單一因素的建模方式很難實現準確的預測.目前研究人員提出了許多方法來解決這一問題,大致可以分為機器學習和深度學習兩類,前者需要的訓練數據較少但準確率較低,后者則恰好相反.其中機器學習的方法主要有線性回歸[4]和支持向量回歸[5];深度學習的方法有卷積神經網絡(CNN)[6]、卷積神經網絡與長短時神經網絡(LSTM)相結合[7]和圖卷積神經網絡(GCN)[8].但這些方法考慮的影響因素不足,仍然無法避免模型不完善的問題.在時間因素方面,出租車需求預測會受季節、節假日和工作時間的影響;同時歷史的出行信息也會有一定的影響,這是因為乘客在到達目的地后,大概率會在一段時間后從目的地再次出發前往下一個區域.在空間因素方面,出租車需求預測在空間上受到地理位置的限制;同時不同的地理位置可能具有相似的社會意義也會影響出租車的需求.

針對上述問題,本文提出了一種多圖時空圖卷積網絡(MGSTGCN),以提高網約車需求預測的準確性.該網絡在空間上使用圖卷積神經網絡進行特征捕獲,針對不同地區的地理位置屬性、交通起止點(OD)屬性和社會意義相似性建立了3 種圖,隨后進行聚合;在時間上使用長短期記憶網絡(LSTM).最后使用了成都網約車軌跡數據和曼哈頓區出租車數據對所建立網絡進行驗證.

2 算法框架

2.1 出租車需求預測建模

本文采用了交通領域的經典處理方法[9],將待處理區域平均分為多個網格,若將網格分為9 個,每個網格由最大坐標與最小坐標定義,如圖1所示,通過這樣的方式,研究每個小格子區域內的出租車需求.隨后將每個格子看作圖的一個頂點,用于構建出租車需求預測的圖模型.

圖1 網格劃分方法

在空間建模方面,文獻[10]考慮了地理位置因素和OD的影響,本文則在此基礎上研究了不同區域的社會屬性對預測問題的影響,包括商業街、大學城、工業園等,通過研究發現,即使相隔距離很遠,具有相似社會屬性的地區在交通流上具有高度相似性.最終本文采用地理位置因素、OD 因素以及社會屬性因素分別構筑了地理圖、OD 圖和社會屬性圖.

在時間建模方面,則考慮歷史出行特征,通過LSTM和注意力機制進行時間特性的捕獲,來掌握時間維度上的出租車需求變化,可以預測每對網格間的需求.

2.2 空間網絡模型

2.2.1 空間建模

以圖1劃分為例,將每個網格看作一個圖的節點,本文在此基礎上建立了3 種圖來捕獲空間特征,如圖2所示.其中,圖2(a)為地理圖結構,將每個網格的中心點視作網格的地理位置中心,中心點的距離視作地理圖結構的邊權值.設中心距離的單位為u,那么網

格8和9 之間距離記作dist(m8,m9)=u,網格8和4 之間距離記作dist(m8,m4)=,距離越近權值則越小,兩者間的出租車需求也會有一定的相似性,可將地理圖范圍集 φi定義為式(1):

其中,L為可設定閾值.

圖2(b)為OD 圖結構,本文使用了OD 矩陣來對OD 圖進行定義:只要任意兩個頂點間有出租車需求存在,那么它們就是相關的.同時,OD 圖會受時間因素的影響,這是因為在不同的時間段內,兩個區域間的OD信息常常是不同的,所以建模時要考慮到不同時間下OD 圖的變化情況.

本文假定兩個地區社會屬性相似,相距距離較大,則此時在地理圖和OD 圖上,這兩個地區的關聯度較小,但由于社會屬性的相似性,兩個地區的出租車需求相似性較高.為了應對這種情況,本文設計了社會屬性圖,其結構如圖2(c)所示.本文將每個網格的社會屬性分為:工業、生活、出行、商業、娛樂和住宿,每個柵格的社會屬性由其所包括的非地理意義點(POI)的屬性所決定.

圖2 空間圖結構

本文爬取了成都部分地區的POI 點,將每個柵格內的POI 點進行了社會意義分類,柵格的社會屬性與相同屬性最多的POI 點保持一致,隨后在建立圖結構時,應用動態時間規劃法(DTW),來量化社會屬性相似的網格間的相似度,公式如式(2)所示:

其中,Fi∈R1×T表示離開第i個網格的出租車流出向量,T為向量長度,由所選定的對照時間尺度所決定.得到矩陣S后對其進行歸一化即可得到社會屬性圖的權重.

2.2.2 圖模型聚合器

如果將每種圖模型單獨進行訓練會大大提升算法的復雜度,為避免這一缺點,本文在傳統聚合函數的基礎上進行改進[11],綜合考慮了3 種圖模型對預測結果的不同影響程度,設計了一種圖聚合器.地理圖的聚合器方式如式(3)所示:

其中,表示時間t′時的地理圖嵌入矢量;Wl是可訓練的權重矩陣;而和分別是地理聚合操作之前的mi和mj的特征.同理可進行出OD 圖和社會圖的特征聚合,OD 圖的特征聚合如式(4)所示:

式中,num(mj)表示于mj開始或結束的需求量,Wq是可訓練的權重矩陣.而表示時間t′下的OD 圖嵌入矢量,和分別是OD 聚合操作之前的mi和mj的特征.

社會圖的特征聚合如式(5)所示:

式中,S(mi,mj)表示mi和mj的社會屬性相似度,表示時間t′下的社會圖嵌入矢量,Wq是可訓練的權重矩陣和分別是社會屬性聚合操作之前的mi和mj的特征.

將3 種聚合器加以整合即可得到圖的最終聚合表示:

2.3 時空網絡架構

MGSTGCN的時間架構部分與LSTM 一樣都有LSTM的輸入門、忘記門和輸出門,但均由圖卷積算子而得,且引入了注意力機制,其中時間序列為輸入.時間結構與空間結構相結合構成了MGSTGCN 網絡,MGSTGCN的層結構如圖3所示.

圖3 MGSTGCN 網絡結構

注意力機制的引入目的是增強關鍵節點的信息,如式(7)所示:

其中,σ (·)為sigmoid 函數,⊙為同或運算符,i,f,o,c分別代表輸入門,遺忘門,輸出門和細胞狀態向量.當它們中的每一個都被更新時,有相應的可訓練權重W和偏差向量b,fatt代表注意力網絡,可以在增強關鍵節點信息的同時保證信息的完整性,所得為注意力矩陣.注意力矩陣設為V=(V1,V2,···,Vt,···,VN),Vt為列向量,計算公式如式(8)所示.

式(8)中,通過softmax(·)函數進行歸一化,得到注意力矩陣V.Vt在語義上理解為輸出時刻t時,節點間的相互依賴程度向量.

3 實驗

3.1 數據集處理

本文選用數據集為成都市局部區域的滴滴快專車平臺的軌跡數據和紐約市曼哈頓區出租車數據集.

其中成都市數據集的時長為2016年11月1日至11月30日,該數據集來自于滴滴公司的蓋亞數據開放計劃,軌跡點的采集間隔是2-4 s.軌跡點經過了綁路的處理,保證了數據都能夠對應到實際的道路信息.司機及訂單信息進行了加密脫敏匿名化處理.紐約市曼哈頓區出租車數據集的時長為2018年7月1日至7月30日.本文分別選取前20 天數據作為訓練集,后10 天數據作為測試集.

3.2 評估指標

本文選取的評估指標為均方根誤差(RMSE)和對稱平均絕對百分比誤差(SMAPE),用以評估預測準確性.RMSE和SMAPE的計算公式如式(9)和式(10)所示:

3.3 實驗結果

為證明模型的有效性和準確性,本文選取了4 種主流模型與本文算法進行對照試驗,分別是:HA[10]、LSTNet[11]、GCRN[12]、GEML[8]、MGSTGCN.實驗結果如表1所示.

表1 與4 種主流模型的實驗對照結果

同時為檢驗該模型的穩定性,本文選取了32,64,128,256,512的網格維度與模型進行了對照實驗,以GEML 模型為例,實驗結果如圖4所示.可以看出在不同的網格維度下,該模型的算法性能均優于GEML 模型,且維度越高,劃分越精密,該模型的優越性越明顯.

4 結論

本文提出了多圖時空圖卷積神經網絡來解決網約車需求預測問題,該網絡將區域網格看作圖的頂點,結合了地理屬性、出入流屬性和社會屬性構建空間圖模型,結合歷史出行規律構建時間模型,并引入了注意力機制,從而可以有效地預測區域內的出租車需求.成都市局部區域的滴滴快專車平臺的軌跡數據和紐約市曼哈頓區出租車數據集用于訓練和測試,實驗結果表明,該模型的RMSE和SMAPE指標均優于其余主流模型,其中相較于GEML 模型,在成都市和曼哈頓區的數據集上,MGSTGCN的RMSE指標分別降低了16.03%和15.46%,SMAPE指標分別降低了11.57%和4.77%,且隨著網格維數的增加,本文算法的優越性越明顯,可以更有效地進行網約車需求預測.

進一步還需要探索的問題是找到更好的網格劃分標準,同時再結合網約車的營收數據,擴展模型功能,有效提高網約車的運營效率和營收情況.