基于時空多圖卷積循環網絡的網約車需求預測

黃官偉，郭 巍

（同濟大學 經濟與管理學院，上海 201804）

0 引 言

目前，許多國家正大力發展以數據為驅動的智能交通系統［1］，預測區域內乘客打車需求是系統中的一個重要組成部分［2］。隨著信息技術在交通領域的廣泛應用，網約車的出現解決了傳統出租車市場“打車難”的問題，成為城市居民出行的主要方式之一。精準的網約車需求預測，可以更合理地指導車輛調度、減少乘客等待時間、提高車輛利用率，進而緩解交通擁堵和節約能源。該任務的主要挑戰在于同時捕獲復雜的時空依賴關系，受到交通拓撲結構和時間動態性的影響，使得網約車的需求量具有復雜的時空關聯。

隨著機器學習和深度學習的發展，已有學者將其應用在交通預測領域。K 近鄰算法（KNN）［3］、支持向量回歸（SVM）［4－6］等基于機器學習的算法比較依賴于特征工程，同時難以計算高維交通數據的時空相關性。由于深度學習技術在語音識別、圖像識別、自然語言處理等領域表現出具有構建復雜模型和捕獲非線性關系的優勢，使得越來越多學者借助深度學習技術捕捉交通數據的動態特征。Zhang 等人［7］根據鄰近時間、周期時間和趨勢時間的交通數據，使用堆疊的殘差單元序列，構建基于卷積的殘差神經網絡（ST－ResNet）。文獻［8－10］融合卷積神經網絡（CNN）和長短時記憶網絡（LSTM）構建模型，提取交通流的時空特征。在此基礎上，Yao 等人［11］引入基于門控機制的局部卷積神經網絡，學習空間不同位置上的動態相似性；Zheng 等人［12］加入注意力機制，為不同時間的交通流數據分配不同的權重；Liu 等人［13］建立了由局部空間、時間演化、全局相關3 個上下文組成的時空網絡（CSTN），捕獲環境信息學習需求特征。但是，傳統的卷積神經網絡（CNN）僅適用于標準的網格數據，不適用于具有圖結構特征的交通數據。圖卷積網絡將歐幾里得空間中傳統的的卷積運算，推廣到非歐幾里得空間中的圖網絡特征運算。Yu 等人［14］構建時空圖卷積網絡（STGCN），處理拓撲結構復雜的交通網絡；Zhao 等人［15］利用圖卷積網絡（GCN）提取路網結構，利用門控循環單元（GRU）學習交通數據動態變化；Guo 等人［16］將時空注意力機制和時空卷積相結合，分別捕獲時間和空間的動態相關性。然而，在空間維度，需求量通常受鄰近區域的影響，同時也會受遙遠但相關性高的區域的影響，并且這些研究考慮的交通拓撲圖結構比較單一，難以全面捕獲空間依賴關系提取需求的空間特征。

針對上述問題，本文提出了時空多圖卷積循環網絡（STMGCRN），對城市區域的網約車需求量進行預測。該模型建立了距離圖、類別相似圖和需求相關圖，從3 個圖中提取不同區域之間的相關關系分別進行圖卷積（GCN）。特征融合后，利用門控循環單元（GRU）學習時間依賴關系。由于交通信息具有較強的周期性，即在時間維度，需求量可能會受到臨近時間片段，一天前、甚至一周前相同時間片段的影響，因此整合3 個時間狀態（臨近、一天前、一周前），捕獲需求數據的周期依賴關系，最后加權融合3 個模型的輸出，得到最終的預測結果。

1 網約車需求預測算法框架

1.1 基本定義和問題描述

定義1城市區域網格V

本文根據交通領域常用的城市區域劃分方法［7，13］，依據經緯度，將研究區域劃分成若干個大小相等的不相交網格，每個網格代表城市的一個子區域v∈V，V代表所有區域的集合，如圖1 所示。采用這種劃分方法，則可以用R（i，j）表示第i行第j列的子區域，便于后續用矩陣或張量處理網約車需求數據。

圖1 城市區域網格Fig.1 The city region grids

定義2網絡圖G

本文用無向圖G＝（V，E）定義城市區域。其中V是圖的頂點集合，即城市中的所有網格區域。V＝｛v1，v2，…，vN｝，N是區域的數量，E是邊的集合，代表區域間的關系，邊的權重代表區域間的關系強度，A∈RN×N表示圖的鄰接矩陣。

定義3特征矩陣X

首先將時間軸劃分成間隔相等的時間段，網約車需求量定義為乘客在t時刻o區域請求出發的數量。Xt＝∈RN代表所有區域在t時刻請求出發的數量，則特征矩陣X＝｛X1，X2，…，XT｝∈RN×T表示所有區域的T個時間片段的歷史需求量數據。其中，T是時間序列的長度。

因此，本研究是在已知拓撲圖結構G的基礎上，利用歷史需求量的特征矩陣X，預測未來F個時間片段的所有區域的需求矩陣Y＝｛YT＋1，YT＋2，…，YT＋F｝ ∈RN×F，是一個多步需求預測問題。

1.2 模型框架

STMGCRN模型總體框架如圖2 所示，主要由具有相同網絡結構的3 個子模型構成。

圖2 STMGCRN模型Fig.2 The Spatial－ Temporal Multi－ Graph Convolutional Recurrent Network

首先將歷史數據沿時間軸劃分成3 個長度相等的時間序列，分別表示臨近時間的需求量、前一天相同時間的需求量、上一周相同時間的需求量，提取時間的臨近特征和周期特征。

每一個子模型由多圖卷積循環網絡MGCRN 構成，如圖3 所示。其基本單元是由多圖卷積和門控循環單元結合形成的多圖卷積循環單元MGCRU。通過學習需求的動態變化規律，來捕獲復雜的時空相關性，進而對時空依賴關系進行建模。最后將3個時空模型的輸出結果利用參數矩陣進行加權融合，得到最終的預測結果。

圖3 MGCRN 子模型Fig.3 Multi－graph convolutional recurrent network

1.3 空間相關性建模

1.3.1 關系圖定義

從不同角度構建關系網絡，準確描述各區域之間的不同類別的相關性是圖卷積的重要工作。通常，區域之間的需求模式越相似，則相關性越強，反之相關性越弱。本文定義了距離圖、需求相似圖和類別相關圖，3 種圖結構描述區域之間的相關性。

1.3.1.1 距離圖

根據Tobler［17］的地理學第一定律可知，距離近的地圖比距離遠的相關性大?；谶@一思想，在本文中體現為兩個地理位置相近的網格，其需求量的相關性大。因此，本文用距離作為衡量區域相關性的一個因素。將網格中心點視為圖的頂點，兩個相鄰網格間的中心距離記為D0，計算i和j兩個區域間實際距離Di，j，任意兩個網格中心的相對距離為，則距離圖的鄰接矩陣可用相對距離的倒數表示，如公式（1）：

考慮到區域之間的距離不同，對需求量的影響大小不同。當距離相關性較小時，對需求量幾乎沒有影響。因此，為減少模型復雜度，當兩個區域的相關性小于閾值δD時，則這兩個區域視為不相關。

1.3.1.2 需求相似圖

一般情況下，在城市區域層面，人們的出行軌跡具有規律性。如果兩個始發區域到其他目的地區域的訂單量分布比較相似，那么這兩個區域之間的相關性較強。若用表示乘客從i區域出發到u區域的歷史訂單量，則i區域的流出量定義為Ci＝，即從i區域出發到其他區域的訂單量。用Pearson 相關系數計算兩個區域之間訂單量的相關性作為邊的權重，計算方法如下：

1.3.1.3 類別相關圖

區域的建筑設施類型和數量在一定程度上影響網約車的分布，比如寫字樓、火車站、住宅等集中的地區，對網約車的需求較多。本文用POI（興趣點）來衡量區域的類別屬性，如果兩個區域的類別相似度較高，那么其具有一定的關聯性。用Pi∈RM表示i區域的POI，M是POI 的種類數量，則兩個區域間的類別相關性可用Pearson 相關系數計算得到：

其公式參數參考需求相似圖。

1.3.2 圖卷積

現有圖卷積方法大致可以分為譜域圖卷積和空域圖卷積。譜域圖卷積是根據圖譜理論，利用圖傅里葉變換，將圖信號從空域轉換到譜域進行卷積操作；而空域圖卷積是直接在拓撲圖上定義卷積操作，計算復雜度較高。因此，本文采用譜域圖卷積方法，圖信號為每個網格的需求量數據。

圖的拉普拉斯矩陣經過對稱歸一化后可表示為L＝IN－D－1／2AD－1／2。其中，IN是單位矩陣；A是圖的鄰接矩陣；D是度矩陣；。拉普拉斯矩陣的特征分解可寫為L＝UΛ UT，其中U和Λ是特征向量和特征值對角矩陣。傳統傅里葉變換的基函數是拉普拉斯算子的特征函數，而圖上的拉普拉斯算子就是拉普拉斯矩陣。因此，圖傅里葉變換的基函數對應拉普拉斯矩陣的特征向量，圖的傅里葉反變換公式為，圖的傅里葉變換為Tx，則圖卷積公式如下：

其中，x是圖上信號（2.1 中定義的需求量的特征矩陣）；g是空域內的卷積核；gθ是頻域內的卷積核；*G表示圖卷積運算；F是圖的傅里葉變換；F－1是圖的傅里葉反變換；☉是hadamard 乘積。

然而，在處理大規模圖數據時，拉普拉斯矩陣的特征值分解消耗時間過多，參數復雜度較大，因此采用Chebyshev 多項式近似求解［18］：

其中，K是卷積核的感知域大??；βk是Chebyshev 多項式系數，βk∈是縮放后的拉普拉斯矩陣；λmax是最大的特征值；是k階Chebyshev 多項式。這種方法通過空間關系提取每個節點到其（K－1）階鄰居的信息并進行特征融合。

本文的多圖卷積模型如圖4 所示，采用4 階Chebyshev 多項式的圖卷積建模，即通過每個節點的三階鄰域來捕獲空間特征進行自身的特征更新，公式如下：

圖4 空間相關性模型MGCNFig.4 The spatial correlation model MGCN

g（x（l），Ai）代表第l層通過提取區域拓撲圖的空間關系，得到圖卷積的輸出特征。其中，Ai是定義的3 種關系圖的鄰接矩陣Ai∈｛AD，AC，AP｝。本文使用ReLU作為激活函數，針對每個時間片段，x(l) ∈RN是第l層的輸入，W（l）和b（l）分別是第l層訓練過程中的權重矩陣和偏置向量。因此，每個節點都通過其0～3 階鄰居的信息進行自身的特征更新，得到下一層的輸出x（l＋1）。在此基礎上，通過堆疊2 層圖卷積，最大程度地擴大卷積核的感受野半徑，從而捕獲更多的空間依賴關系：

通過以上步驟，可以分別得到3 個關系圖的卷積運算結果f（x（l），Ai），最后需要對這些結果進行加權融合：

其中，☉代表hadamard乘積；WD、WC、WP是特征融合的權重矩陣；φ（x（l），A）是融合后的輸出結果。

1.4 時間相關性建模

長短期記憶（LSTM）［19］和門控循環單元（GRU）［20］是常用的處理時間序列問題的循環神經網絡。GRU 作為LSTM 的一種變體，在相同數據集上的表現和LSTM 相差不大，但由于GRU 訓練參數少，收斂速度更快，可以加速迭代進程，甚至可以增強模型的泛化能力，所以本文使用基于GRU 的循環神經網絡來捕獲時間依賴關系，如圖5 所示。

圖5 時間相關性模型GRUFig.5 The temporal correlation model GRU

在每個時間片段，將圖卷積得到的每個節點的空間鄰域信息，輸入到GRU 門控循環單元中。在門控循環單元的傳遞中，通過重置門和更新門可以有效地結合上一時刻的累積歷史信息和當前時刻的信息，同時將隱藏狀態和歷史數據經過多圖卷積后的結果作為輸入，可以繼續保持節點的空間依賴關系，公式如下：

其中，ht－1是t－1 時刻的隱藏層狀態；xt是t時刻的輸入；br、bz和bh是偏置向量；［ ］是張量拼接操作，即將上一時刻的隱藏層狀態和當前時刻的輸入拼接起來作為圖卷積的輸入特征；*代表矩陣相乘操作；☉代表hadamard 乘積；σ是sigmoid 激活函數；rt是重置門；決定上一時刻隱藏層狀態ht－1中有多少保留在當前記憶內是更新門，決定記憶細胞內有多少信息保留到當前隱藏狀態ht，余下部分用上一時刻的隱藏層狀態ht－1進行更新。

1.5 模型融合

本文輸入的時間序列主要包含臨近時間序列、前一天時間序列、上一周時間序列3 部分，。臨近時間序列是指與預測區間直接相鄰的時間序列，前一天、上一周時間序列分別是指在前一天或是上一周和預測區間相同的時間序列：

假設將一天均等地劃分為P個時間片段，每個時間序列包含T個時間片段的歷史數據，to代表當前時間片段，Xto－1代表上一個時間片段的所有區域的歷史訂單量數據，Xrecent、Xday和Xweek分別表示臨近、前一天和上一周的時間序列。例如，預測區間是11 月8 日12：00－13：00，則臨近時間序列為11 月8日11：00－12：00 的每個片段的訂單量，前一天時間序列和上一周時間序列分別是11 月7 日12：00－13：00、11 月1 日12：00－13：00 的每個片段的歷史訂單量。這3 個序列體現了需求量數據的臨近特征和周期特征。

構建3 個時空圖卷積模型分別捕獲需求量數據的特征，得到的3 個輸出結果對最終需求量預測值的影響程度不同，因此利用參數矩陣進行特征融合，得到最終的預測值：

2 實驗與結果分析

2.1 數據集處理

本文的數據集是由滴滴出行“蓋亞”數據開放計劃提供的西安市2016 年10 月1 日～2016 年11月30 日二環局部區域軌跡數據［21］，軌跡點采集間隔為2～4 s，字段包括訂車編號、司機編號、時間戳、經緯度等。將西安市區劃分成邊長為1 km 的正方形網格，POI 數據由高德地圖API 得到，主要以餐飲服務、風景名勝、公司企業、交通設施服務、科教文化服務和商務住宅為統計標準。3 個子模型的超參數完全相同，時間間隔是10 min，關系圖閾值δD＝0.25、δC＝0.1、δP＝0.3，多項式階數K＝4，歷史時間序列的長度T＝6，預測的時間序列長度F＝6。沿著時間軸按照6：2：2 的比例劃分出訓練集、驗證集和測試集。

2.2 評價指標

本文選取交通預測領域常用的均方根誤差（RMSE）與平均絕對誤差（MAE）作為模型的評價指標，來衡量預測的準確性。

其中，M為數據個數，Yi和分別表示真實值和預測值。

2.3 實驗結果分析

實驗選取4 種模型與本文算法進行對比。分別是：圖注意力（GAT）［22］、長短期記憶（LSTM）［19］、圖卷積（GCN）［18］、門控循環單元（GRU）［20］。實驗結果見表1?？梢钥闯?，本文提出的STMGCRN模型的算法性能均優于其它4 種模型。

表1 需求預測模型的性能比較Tab.1 Performance comparison of demand forecasting models

GAT 是一種將注意力機制引入圖卷積模型中的方法，利用注意力機制在卷積過程中對鄰域節點區別對待；LSTM 是一種克服了一般循環神經網絡的長期依賴問題的方法，將歷史網約車需求量數據輸入模型，進行多步預測；GCN 是一種基于Chebyshev 多項式的圖卷積方法，為保持公平性，該方法和GRU 方法均與本文中使用相同的參數設置。

3 結束語

本文提出了一種時空多圖卷積循環網絡（STMGCRN）來對網約車需求進行多步預測。該模型定義了城市區域網絡圖，構建距離圖、需求相似圖和類別相關圖，來描述各區域之間的空間相關性，學習時間序列的動態變化來捕獲需求量數據的時間相關性，從而根據復雜的時空依賴關系，預測每個區域內網約車的需求。在滴滴出行提供的數據集上進行了對比實驗，結果表明，在常用的交通領域評價指標上，STMGCRN模型的算法性能均優于其它模型，可以進行更為精準的預測。但是，網約車的需求量也會受到其它外部因素的影響，在未來的研究中需要考慮人口數量、天氣等更多元化的信息，探究其與需求量之間的關系，進一步提高模型預測的準確率。