面向動態(tài)路網(wǎng)的最優(yōu)路徑GCN 深度搜索方法

費 珂，秦小麟，遲賀宇，李 瑭

南京航空航天大學計算機科學與技術學院，南京211106

在路網(wǎng)中，最優(yōu)路徑以時間衡量，而交通情況受位置、時間、整體交通態(tài)勢等影響動態(tài)變化，成為相關研究的難點。探索更高效、準確、實時的算法，在路網(wǎng)中進行最優(yōu)路徑的搜索規(guī)劃，對更好地提供各類位置服務（location based services，LBS）具有重要的意義。

當前主流的定位技術有衛(wèi)星定位和基站定位，前者包括全球定位系統(tǒng)、北斗等，后者包括射頻識別技術（radio frequency identification，RFID）定位等。不同技術在各場景中表現(xiàn)各有優(yōu)劣[1]：衛(wèi)星定位的移動對象數(shù)據(jù)具有較強連續(xù)性，但易受高樓隧道等干擾，精度較低；基站定位如RFID 在基站密度較高的城市中，數(shù)據(jù)精確度較高、信息量大，但數(shù)據(jù)離散化、多冗余。近年來RFID 技術因其特有優(yōu)勢漸漸受到青睞，在各大城市逐漸普及。第五代通信技術、智能移動設備、定位技術的發(fā)展，使基于位置的社交、服務等隨之興起，推薦系統(tǒng)[2]、智慧城市[3]、智能交通[4]等領域都有了長足發(fā)展。

某交通局已部署大量RFID 私家車檢測基站，覆蓋城市交通的主體區(qū)域，應用于智能識別、流量監(jiān)測、違規(guī)監(jiān)控等方面。安裝RFID 電子標簽的車輛產(chǎn)生了海量移動對象數(shù)據(jù)，交通工作者當前重要任務之一就是從海量數(shù)據(jù)中挖掘有效信息，以優(yōu)化各類位置服務。

在動態(tài)路網(wǎng)中搜索最優(yōu)路徑面臨著許多難點：城市道路復雜，交通情況多變，海量的交通數(shù)據(jù)難免存在冗余、缺失等問題；現(xiàn)實場景中，城市內(nèi)出行對路況尤為敏感，查詢路徑時當前、未來交通信息未知；路網(wǎng)內(nèi)在模式具有時空相關性[5]，理想的搜索依賴于對時間、空間信息的有效利用。

當前許多研究引入了啟發(fā)算法、神經(jīng)網(wǎng)絡等，在不同場景都取得一定效果。啟發(fā)式的蟻群算法搜索時通過迭代逼近最優(yōu)解，可結合聚類及自適應機制等用于動態(tài)環(huán)境[6]；部分神經(jīng)網(wǎng)絡方法如RNN（recurrent neural network）、LSTM（long short-term memory）等適合處理時序數(shù)據(jù)，學習出符合數(shù)據(jù)模式的模型[7]，偏向于生成與歷史軌跡相近的路線；強化學習通過智能體與環(huán)境交互獲得處理未知場景的能力，使用獎賞函數(shù)尋求最大長期收益[8]，結合深度學習框架來提升對各類信息的利用率以面對復雜場景。此外當前工作中還存在一些不足，例如忽視了現(xiàn)實場景中未來交通狀況未知、需建模預測，而基于完全已知或隨機的場景設計算法；此前基于機器學習的交通模型多使用卷積神經(jīng)網(wǎng)絡，因此無法直接用于圖問題，需將地圖網(wǎng)格化處理，在圖結構與網(wǎng)格化的映射中存在失真。近年研究者提出了定義在圖結構上的一系列圖神經(jīng)網(wǎng)絡[9]，如圖卷積網(wǎng)絡（graph convolutional networks，GCN）、時空圖卷積網(wǎng)絡（spatial-temporal graph convolutional networks，STGCN）[10]等，在交通、社交網(wǎng)絡等領域表現(xiàn)良好[11]。

針對上述情況，本文提出了一種基于GCN 的動態(tài)路網(wǎng)最優(yōu)路徑深度搜索模型。模型使用圖神經(jīng)網(wǎng)絡以避免網(wǎng)格化處理，挖掘時空數(shù)據(jù)、圖蘊含的信息，同時利用歷史交通數(shù)據(jù)對未來路網(wǎng)狀況進行建模，使模型更貼近現(xiàn)實出行場景：基于RFID 數(shù)據(jù)集，將基站作為圖節(jié)點、交通流量等信息作為節(jié)點屬性，使用時空圖卷積網(wǎng)絡建模路網(wǎng)的動態(tài)變化；加深搜索深度，使用神經(jīng)網(wǎng)絡計算深度估價、搜索最優(yōu)路徑；最后在某交管局提供的RFID 數(shù)據(jù)集上進行測試。實驗結果表明，該方法能夠有效處理具有多維性和時效性的交通數(shù)據(jù)，整合路網(wǎng)中的時空語義信息并建模，通過深度搜索提高了最優(yōu)路徑查詢的準確度。

1 相關工作

隨著定位技術、時空數(shù)據(jù)庫技術等各方面的發(fā)展，海量交通數(shù)據(jù)得以獲取，關于路網(wǎng)中最優(yōu)路徑搜索問題的研究不斷深入。動態(tài)路網(wǎng)中的最優(yōu)路徑搜索主要包含交通數(shù)據(jù)預處理、動態(tài)路網(wǎng)模型建立、動態(tài)圖路徑搜索等關鍵步驟。

路網(wǎng)中采集的數(shù)據(jù)信息，是典型的時空數(shù)據(jù)，具有維度高、語義復雜、時空動態(tài)關聯(lián)的顯著特征。對于RFID 交通數(shù)據(jù)，研究者很早就提出了借助數(shù)據(jù)庫管理技術進行流處理[12]以及自適應清潔[13]的方法。近年研究者提出了基于動態(tài)標簽、考慮數(shù)據(jù)冗余等改進方法[14]，使得從龐雜數(shù)據(jù)中提取有效數(shù)據(jù)變得更加高效準確，適合后續(xù)的分析挖掘任務；針對交通軌跡數(shù)據(jù)中缺失、異常等數(shù)據(jù)缺陷，研究者提出了許多基于聚類、閾值劃分的方法。劉云恒等人[15]在清洗策略引入了最大熵原理，適用于不確定RFID 數(shù)據(jù)流；Birant等人[16]在聚類算法上增加時間屬性，提出了STDBSCAN（spatial-temporal density-based spatial clustering of applications with noise）算法處理時空數(shù)據(jù)；Cai 等人[17]使用數(shù)字孿生技術進行優(yōu)化，使用改進的掃描線算法和F1 評估來確定閾值，更準確地發(fā)現(xiàn)數(shù)據(jù)缺陷。

目前，在交通領域研究者提出了大量機器學習模型，高效處理路網(wǎng)中相關問題。Zhang 等人[18]將時空處理單元引入殘差神經(jīng)網(wǎng)絡，提出ST-ResNet模型，深度學習與時空數(shù)據(jù)的結合在行人流量預測等任務上表現(xiàn)卓越；Qiao 等人[19]將適合處理時序數(shù)據(jù)的LSTM模型應用于路網(wǎng)問題，預測短期交通流量；近年來圖卷積網(wǎng)絡因具有處理圖結構與非歐氏空間數(shù)據(jù)的能力[20]備受關注，Yu 等人[21]設計基于圖卷積網(wǎng)絡的深度學習模型，高質(zhì)量利用圖中空間結構等信息，以時空卷積單元進一步學習移動對象軌跡的時序信息。

路網(wǎng)中的路徑搜索問題，算法通常包含動態(tài)圖的預處理和路徑查詢搜索兩個主要步驟，研究者提出了不同處理方法。Wang 等人[22]基于圖注意力網(wǎng)絡，采用循環(huán)卷積網(wǎng)絡與強化學習方法改進A*算法及其估價函數(shù)，得到基于歷史數(shù)據(jù)的個性化路徑。啟發(fā)式的A*算法是一種求解最短路徑最有效的直接搜索方法，Nannicini 等人證明了A*算法在動態(tài)圖上的可行性[23]，而Wang 的工作則證明了使用機器學習進行啟發(fā)式搜索的有效性。此外，Demiryurek 等人[24]系統(tǒng)研究了傳統(tǒng)最短路徑算法在時變空間網(wǎng)絡的適用性；Li等人[25]使用具有自波動性的脈沖耦合神經(jīng)網(wǎng)絡（pulse-coupled neural network，PCNN），自適應地學習路網(wǎng)中信息；Panov 等人[26]使用深度強化學習框架（deep reinforcement learning，DRL），以交互、獎賞函數(shù)機制學習地圖模式進而尋找最優(yōu)路徑，可用于智能體路徑規(guī)劃、城市導航等領域；結合其他一些啟發(fā)式算法如遺傳算法、蟻群算法的改良與混合模型也在不同場景中獲得了不錯效果[27]。

2 問題定義與深度搜索模型

令抽象路網(wǎng)G=G(V,E,W)是無向全連通的動態(tài)圖，其中V是圖頂點的集合，E?V×V是邊的集合，W是邊權重矩陣。RFID 數(shù)據(jù)集T中的記錄Ti(carID,vertex,time…)是某一時刻某一基站收集到的車輛信息，其中還包括環(huán)境等其他屬性。車輛運動軌跡H={T1,T2,…,Th}是多個連續(xù)記錄的序列化。文中關鍵符號及含義如表1 所示。

表1 關鍵符號及含義Table 1 Key symbols and their description

定義1（交通路網(wǎng)最優(yōu)路徑搜索）已知過去時間段t0至tl的路網(wǎng)G=G(V,E,W)的結構與信息，以及該段時間有效的車輛軌跡數(shù)據(jù)H={T1,T2,…,Th} 等信息。在未來的tl至tm時段，路網(wǎng)情況未知，給定出行的出發(fā)時間、起始點、終點三元組{n,n0,T}，搜索擁有最小總時間代價的最優(yōu)路徑。

2.1 數(shù)據(jù)預處理

原始的RFID 數(shù)據(jù)以基站為主體，存儲在時空數(shù)據(jù)庫中，數(shù)據(jù)呈離散化，缺乏時空連續(xù)性，分布不均勻，因此需要進行預處理，轉化為適當軌跡數(shù)據(jù)并進一步挖掘信息。

預處理過程包括：數(shù)據(jù)重組，由原始點數(shù)據(jù)集T計算出所有單次移動記錄Hi(Ti,Ti+1)；刪除冗余數(shù)據(jù)與孤立數(shù)據(jù)，初步清洗數(shù)據(jù)；通過無監(jiān)督方法，從大量數(shù)據(jù)中篩選出具有運動連續(xù)性的軌跡H={T1,T2,…,Th}。

不同任務對于軌跡數(shù)據(jù)具有不同程度的要求。位置預測問題要求數(shù)據(jù)具有時間的上下連續(xù)性；交通流量預測問題關注節(jié)點屬性信息。在最優(yōu)路徑問題中，要求數(shù)據(jù)反映車輛的持續(xù)運動。兩基站間的通行時間消耗受到時間、車型、周圍路段情況等的影響。長時間跨度的數(shù)據(jù)中可能存在早出晚歸、意外事故等情景，使得移動對象呈現(xiàn)“動-停-動”的運動狀態(tài)，使得數(shù)據(jù)連接形成的軌跡不合理，進而影響對路網(wǎng)建模的準確度。因此，需要清洗數(shù)據(jù)使得軌跡H={T1,T2,…,Th}具有運動連續(xù)性。如圖1 所示，將離散點連接為軌跡后，刪除非連續(xù)運動狀態(tài)的部分生成多段合理軌跡。

圖1 劃分軌跡數(shù)據(jù)Fig.1 Divide trajectory data

在RFID 原始數(shù)據(jù)得到的單次移動時間消耗中，異常值主要集中在非運動狀態(tài)導致的過長時間消耗，數(shù)據(jù)整體上呈現(xiàn)半正態(tài)分布（half-normal distribution）。依照相同的起始、終止節(jié)點將初步篩選后的行駛記錄劃分為多個數(shù)據(jù)集合Ck，以廣泛使用的K均值聚類算法檢測異常數(shù)據(jù)，拉格朗日多項式插值對數(shù)據(jù)樣本缺失時段進行填充[12]。數(shù)據(jù)預處理總體流程如算法1 所示。

算法1RFID 數(shù)據(jù)預處理算法

輸入：原始數(shù)據(jù)集合T，頂點集合V。

輸出：連續(xù)的運動軌跡H={T1,T2,…,Th}。

1.Tsorted←T//數(shù)據(jù)重排序

2.forTi,Ti+1inTsorteddo

3.drop isolated and redundantTi//刪除孤立數(shù)據(jù)點、冗余數(shù)據(jù)等

4.Hi←Ti+1-Ti//計算單段移動軌跡

5.end for

6.Ck←divideHset//按頂點分類單段軌跡

7.for eachCkdo

8.thresholdck←Ck//計算閾值

9.drop out-of-range data//按閾值刪除數(shù)據(jù)

10.ifHilacks data:

11.Hi←Interpolation(…Hi-1,Hi+1…)//插值法填充缺失數(shù)據(jù)

12.end for

13.H←∑Ck//整合軌跡

算法1 首先將原始RFID 數(shù)據(jù)集轉換為移動記錄并進行數(shù)據(jù)清洗、缺失數(shù)據(jù)填充，生成了具有運動連續(xù)性的軌跡H={T1,T2,…,Th}，以提供更準確的交通信息，包括路網(wǎng)G=G(V,E,W)中不隨時間變化的頂點鄰接關系、頂點集V與權重矩陣W隨時間變化的動態(tài)屬性等。面對海量、高維、時空相關的交通數(shù)據(jù)，采用了低復雜度方法：對高維數(shù)據(jù)排序時由于需同時依照時間、地點等多維度信息，使用復雜度O(nlbn)的快排；排序后冗余與孤立數(shù)據(jù)清洗、軌跡計算、聚類及基于閾值的篩選清洗復雜度都為O(n)；對缺失數(shù)據(jù)的填充復雜度O(n)，且需要插值計算的缺失數(shù)據(jù)少，相對計算代價較低；因此數(shù)據(jù)預處理算法整體時間復雜度為O(nlbn)。通過數(shù)據(jù)預處理過程，有效解決了原始數(shù)據(jù)中的冗余、稀疏、缺失等問題，使數(shù)據(jù)可靠性更高。

2.2 動態(tài)路網(wǎng)建模

圖卷積網(wǎng)絡主要用來處理分類、預測等任務[18]，針對路網(wǎng)最優(yōu)路徑搜索問題，將模型分為兩大部分：對動態(tài)路網(wǎng)進行建模的STGCN 網(wǎng)絡部分，使用以圖卷積參數(shù)優(yōu)化的深度估價網(wǎng)絡函數(shù)的部分，整體模型如圖2 所示。這一節(jié)將主要介紹對動態(tài)路網(wǎng)建模預測的STGCN 部分。

2.2.1 整體結構

記t時段交通路網(wǎng)為Gt=Gt(Vt,E,Wt)，節(jié)點集Vt的空間屬性不變，時間屬性動態(tài)變化。STGCN 網(wǎng)絡的任務是根據(jù)給定的t0至tl時段信息，建模tl至tm時段路網(wǎng)節(jié)點狀況：

STGCN 模型中，使用空域卷積聚合鄰接節(jié)點的空間信息，使用時域卷積傳遞輸入序列的時序信息，使得網(wǎng)絡處理具有時序特征的動態(tài)交通數(shù)據(jù)圖的能力。經(jīng)過時空卷積后節(jié)點特征將在時間、空間上聚合，如圖3（a）所示。圖3（b）展示了時空卷積模塊（ST-conv Block）的結構，由兩個時域卷積和一個空域卷積組成。依次進行時域、空域卷積計算。輸入數(shù)據(jù)中，n為節(jié)點個數(shù)，Ci為特征通道數(shù)，網(wǎng)絡輸入M個時間步的數(shù)據(jù)序列X∈RM×n×Ci及對應的鄰接矩陣。

圖3 特征傳播與網(wǎng)絡細節(jié)Fig.3 Feature transfer and network details

2.2.2 時間域卷積模塊

該模塊如圖3（c）所示，屬于一維時序卷積，由一維卷積和門控線性單元（gated linear unit，GLU）[28]構成。對于輸入的特征，沿著時間維度進行一維卷積，計算后分為不經(jīng)激活的P、使用Sigmoid 激活的Q兩部分，作為門控單元的輸入，再通過門單元GLU 進行權重篩選，整體時域卷積定義及計算過程如下：

式中，Γ是時域卷積核，*Γ是時域卷積操作；Wa和Wb為一維卷積核，*a和*b是卷積操作；⊙是按元素的Hadamard 乘積，σ(·)此處為Sigmoid 激活函數(shù)。一維卷積聚合時序上的前后信息，而引入門控單元GLU可以減輕梯度彌散，加速收斂，并使模型在深度增加時保留長期記憶（long-term memory），有利于深度網(wǎng)絡建模。

2.2.3 空間域卷積模塊

定義2（鄰接域）定義相互可達的兩個節(jié)點之間最小無權重距離記為鄰接階數(shù)、鄰接距離，節(jié)點與自身鄰接階數(shù)為0。定義節(jié)點n的k階鄰接域：所有與n鄰接距離小于等于k的節(jié)點組成的集合。

空間維度上的圖卷積按提取特征方式分為兩種：spatial domain，直接對鄰接節(jié)點采樣、聚合更新節(jié)點特征；spectral domain，通過傅里葉變換與拉普拉斯矩陣計算的頻譜方法。Monti 提出了統(tǒng)一的框架，將兩種方法概括到這個框架中[29]。STGCN 中空間域卷積為spectral domain，其卷積形式為：

圖的度對角矩陣D和鄰接矩陣A構成拉普拉斯矩陣L=D-A。式中U是拉普拉斯矩陣L的特征向量構建的矩陣，Λ是特征值構成的對角矩陣，gΘ(Λ)是卷積核，σ(·)是激活函數(shù)。

為了簡化傅里葉變化的矩陣譜分解、矩陣特征向量計算等操作，降低計算量，模型使用Chebyshev多項式作為圖卷積核。每層空域卷積有C0個卷積核Θ，Θ∈RK×Ci，輸入特征向量X∈RM×n×Ci，計算公式為：

最后的輸出模塊包括一個時域卷積層和一個全連接層。全連接層有權重矩陣Z、偏置向量b，輸出圖中所有節(jié)點屬性的估計值=Z(Γ*τX)+b。以估計值與真實值V的距離度量loss=||-V||2定義STGCN 的損失函數(shù)。

STGCN 交替使用時域卷積、空域卷積，使得不同時序的鄰接信息向節(jié)點聚合。對動態(tài)路網(wǎng)進行建模時，每個節(jié)點的屬性由過往各時段自身、K階鄰接域內(nèi)所有鄰接點的屬性計算而來。相較于傳統(tǒng)方法，時空信息的全面處理使得其能在動態(tài)路網(wǎng)的建模上取得更好效果。

2.3 深度搜索

啟發(fā)式A*搜索算法廣泛使用于路徑搜索等任務，結合了最佳優(yōu)先搜索和Dijkstra 算法的優(yōu)點。其核心為估價函數(shù)：

式中，n為任意節(jié)點，g(n)是n與起始點之間的實際距離計算函數(shù)，h(n)是對n與目標點距離的評估函數(shù)。搜索路徑時，A*算法維護兩個集合：closed setC記錄關閉節(jié)點，初始為空；open setO記錄待拓展節(jié)點，初始僅包含源節(jié)點。通過最佳優(yōu)先的方式進行拓展：

估價最優(yōu)的節(jié)點next移動至C，其不在C中的鄰接節(jié)點更新距離并添加至O?；贏*算法的啟發(fā)式思想進一步優(yōu)化，提升擴展時的搜索深度，使用深度估價神經(jīng)網(wǎng)絡替代人為設計的估價函數(shù)，以改進搜索效果。

2.3.1 深度搜索定義

在對動態(tài)路網(wǎng)建模后，路況雖然可以估算但仍存在誤差，信息無法保證絕對準確。極小化極大搜索、蒙特卡洛樹搜索等方法在信息不完全情況與博弈中，增加搜索深度可以有效改善搜索效果。在啟發(fā)式搜索方法中，提高搜索深度，也有利于繞開路網(wǎng)中局部最優(yōu)的節(jié)點，進而尋找最優(yōu)的路徑。

記n為待評估節(jié)點，其不在C中的鄰接域節(jié)點集合為N，改進算法擴展節(jié)點時的評估方式，定義深度估價函數(shù)進行深度為2 的搜索，以加權形式得到的深度估價函數(shù)及擴展節(jié)點方式如下式：

式中，α為加權系數(shù)，f′(n)為深度估價函數(shù)。評估O中節(jié)點n時，需評估其鄰域內(nèi)其他節(jié)點：計算n與起始點之間的實際距離的g(n)不變，h′(n)則以鄰域內(nèi)節(jié)點估值的加權計算，從而定義n的深度2 估價f′(n)，選取具有最小深度估價的節(jié)點進行拓展。深度搜索效果取決于深度估價函數(shù)的效果，除了加權計算外，也可以樸素地取鄰域內(nèi)節(jié)點的最小估價，或者使用機器學習方法進行估價計算。原始方法可視為深度1 搜索，在深度2 搜索的基礎上進行推廣，可以定義其他深度的搜索。

2.3.2 深度搜索復雜度

搜索深度的增加會對搜索的復雜度造成影響，需要確保其復雜度可控。

定理1（深度搜索復雜度約束）將一次A*算法搜索時訪問過的節(jié)點記為集合A，A?V。設n為圖節(jié)點數(shù)，k為節(jié)點度的最大值。當搜索深度增為1+h時，搜索計算的節(jié)點數(shù)小于k×(k-1)h-1×|A|。

證明記n0,0為某步深度搜索的開始節(jié)點，Ni為其i階鄰域，與n0,0鄰接距離為i編號為j的節(jié)點為ni,j，節(jié)點的度記為d(n)。k為圖節(jié)點度的最大值且k＞2，k≤2 時圖極簡且不符合任務場景。以sum(h)表示n0,0深度1+h搜索所需訪問計算節(jié)點的總次數(shù)，以s(h)表示第1+h深度搜索訪問次數(shù)。由于路網(wǎng)的復雜性，ni,j節(jié)點在n0,0的i階鄰域首次出現(xiàn)后，仍存在被更長路徑訪問到并得到新的編號、剪枝保留最小代價路徑的情形，不影響證明。

原始算法僅計算n0,0，搜索深度為2 時，訪問并計算n0,0節(jié)點的d(n0,0) 個鄰接節(jié)點n1,0,n1,1,…,n1,m；若n0,0非全局搜索的起始點則為d(n0,0)-1，排除其父節(jié)點。因此sum(1)≤k。

由A*算法性質(zhì)，合理的啟發(fā)式估價函數(shù)可以優(yōu)化搜索過程，以最差情形作為搜索節(jié)點上限，深度搜索對每個節(jié)點進行深度1+h的搜索擴展，約束整體訪問計算總節(jié)點次數(shù)|A′|：

不等式中supE為定義在實數(shù)域上的集合上確界，任意節(jié)點的sum(h)可由最差無剪枝情況的值進行縮放限定。綜上，進行深度搜索擴展后，搜索計算節(jié)點次數(shù)小于k×(k-1)h-1×|A|。

定理1 定義于任意結構的圖，對任意階深度搜索的復雜度進行分析與約束。在理想的網(wǎng)格形交通路網(wǎng)中，節(jié)點度最大值k=4 且存在剪枝，除初始節(jié)點外每個節(jié)點有三個子節(jié)點，每個深度存留節(jié)點nh,j數(shù)量為4×h，此時sum(h)≤6×h×(h-1)+4，由定理1 中不等式|A′|≤sup{sum(h)|n∈A}×|A|，整體復雜度也大大降低。相較于定理1 中假設的任意圖結構且無剪枝最差情形，現(xiàn)實路網(wǎng)與理想網(wǎng)格路網(wǎng)更為接近，結構稍復雜，原始算法的時間復雜度為O(|V|2)，深度搜索算法的時間復雜度為O(k2h2|V|2)，由于h、k是遠小于|V|的常數(shù)，也可視其復雜度階數(shù)未增加仍為O(|V|2)。

2.3.3 深度搜索方法

深度搜索方法效果取決于深度估價函數(shù)的準確性，設計了僅考慮最小值的深度估價方法、基于距離差的加權深度估價方法以及使用神經(jīng)網(wǎng)絡進行深度估價的方法。其中，僅考慮最小值的方法以待評估節(jié)點鄰接域中的最小估價函數(shù)值作為深度估價；基于距離差的加權方法，以鄰接域內(nèi)節(jié)點與終點的距離計算加權系數(shù)α，使用歸一化指數(shù)函數(shù)（Softmax）使得各權重占比更平滑，計算如下：

式中，n0為終點，d(n,n0) 為兩節(jié)點的曼哈頓距離，d′(ni)為待評估節(jié)點n、節(jié)點ni距離終點的距離差，數(shù)值越小則距離越遠，節(jié)點權重占比越低。

深度估價是對鄰域節(jié)點信息的聚合與計算，因此可以使用深度估價神經(jīng)網(wǎng)絡替代人為設計的深度估價函數(shù)，通過訓練學習深度估價，并結合圖卷積單元權重系數(shù)進行優(yōu)化。其結構如圖2 右側深度估價網(wǎng)絡部分，計算公式如下：

式中，G是全連接權重矩陣，其中Gk借助圖卷積單元參數(shù)進行構造，K是鄰接域階數(shù)，E表示默認的隨機參數(shù)構造；Nk由待評估節(jié)點K階鄰接域內(nèi)節(jié)點構成，與終點n0、時間戳t一起作為網(wǎng)絡輸入；以W示意其他全連接層的計算。深度估價網(wǎng)絡通過聚合鄰接域內(nèi)信息進行深度估價計算，同時關注了時間信息。最優(yōu)路徑深度搜索算法GCN-Search整體流程如下：

算法2最優(yōu)路徑深度搜索算法

輸入：頂點屬性序列{V0,V1,…,Vl}，鄰接矩陣A，查詢起點、終點、時間三元組{n,n0,T}，T＞t。

輸出：路網(wǎng)中最優(yōu)路徑{n,v1,v2,…,n0}。

1.Input {V0,V1,…,Vl}//由算法1 獲得輸入序列

2.divide {V0,V1,…,Vl} to train &validation set//將數(shù)據(jù)劃分為訓練集與驗證集

3.Put train set into STGCN//輸入訓練集

4.forepochinepochsdo:

5.Calculate prediction andloss//通過模型計算結果與損失函數(shù)

6.Adjust STGCN parameters//反向傳播調(diào)整網(wǎng)絡參數(shù)

7.early stopping//在驗證集使用早停法

8.end for

9.{Vt+1,Vt+2,…,Vm}←STGCN({V0,V1,…,Vl})//未來路網(wǎng)建模

10.train setH←{Vt+1,Vt+2,…,Vm}//生成訓練集

11.as step 4～7,train Deep Valuation Network withH//訓練深度估價網(wǎng)絡

12.whilen0not in closed setC://深度搜索

13.n∈O,f(n)←GCN//計算深度評估值

14.updateCandO//更新狀態(tài)集

15.end while

16.output the path of query{n,n0,T}

在算法2 中，依次利用訓練集數(shù)據(jù)訓練了建模路網(wǎng)的STGCN、深度估價網(wǎng)絡，關注了空間信息與時間信息的利用，通過深度搜索給出查詢{n,n0,T}的解。其中，STGCN 網(wǎng)絡需要使用路網(wǎng)中所有節(jié)點信息對路網(wǎng)進行完整、準確的建模，深度估價網(wǎng)絡則使用鄰域內(nèi)相關節(jié)點進行計算，將模型分為兩個網(wǎng)絡部分，可使得計算操作更靈活簡便。

3 實驗與分析

3.1 數(shù)據(jù)集與實驗環(huán)境

為驗證模型性能效果，在某交管局提供的RFID車輛數(shù)據(jù)集上進行測試。原始數(shù)據(jù)集包含548 個基站地理位置信息、基站記錄的通過車輛信息，時間跨度2014 年9 月1 日0 時到9 月30 日24 時，包含近百萬車輛，數(shù)據(jù)特征包括通過時間、基站編號、車牌號、車型等。本文主要關注其中的時間位置信息，對數(shù)據(jù)進行抽象簡化、軌跡化等預處理，并構成屬性以5 min為間隔動態(tài)變化的抽象路網(wǎng)，包含10 個節(jié)點的中短距離路徑查詢，作為實驗數(shù)據(jù)集。

模型基于Pytorch 深度學習框架，實驗的運行環(huán)境為：ubuntu16.04（64 bit），Intel Xeon E5-2609 CPU，16 GB RAM，NVIDIA Tesla K40m GPU。

3.2 路網(wǎng)建模效果及深度搜索方法比較

最優(yōu)路徑深度搜索算法經(jīng)由STGCN 得到對路網(wǎng)建模的中間結果，在中間結果的基礎上進行深度搜索。完整算法由兩部分共同組成，針對這兩部分進行獨立的實驗比較。

3.2.1 不同參數(shù)對STGCN 建模效果的影響

對于路網(wǎng)建模結果的優(yōu)劣，用節(jié)點屬性的估計值y～ 與真實值y之間的均方根誤差（root mean square error，RMSE）、平均絕對誤差（mean absolute error，MAE）、平均絕對百分比誤差（mean absolute percentage error，MAPE）等指標進行評價，三者從不同角度反映估計值與真實值之間的誤差，誤差越小則表示建模結果越精確。網(wǎng)絡的損失函數(shù)loss=||V^ -V||2與誤差指標的變化趨勢總體上一致。

STGCN 的訓練中，循環(huán)中的一個epoch指完整的數(shù)據(jù)集在網(wǎng)絡上進行一次完整計算，所有訓練樣本進行正向計算得到損失函數(shù)值loss并反向傳播調(diào)整網(wǎng)絡參數(shù)。為了挖掘數(shù)據(jù)間的模式，往往需要循環(huán)多次，并在每個epoch打亂數(shù)據(jù)順序消除數(shù)據(jù)間的相關性，提高模型泛化能力。同時，在訓練集上迭代次數(shù)過多可能造成過擬合的情況，GLU 單元、dropout方法可以在一定程度上避免過擬合。

圖4 展示了STGCN 部分預測近期路網(wǎng)狀況的損失函數(shù)變化情況。損失函數(shù)值隨著epoch增加變化：在訓練集上，迭代過程中損失函數(shù)值穩(wěn)定下降；在驗證集上，損失函數(shù)值先呈現(xiàn)振蕩下降，逐漸趨向平穩(wěn)，在最后階段損失函數(shù)值略上漲呈現(xiàn)輕微過擬合。為了保證模型預測的準確度與泛化能力，并盡可能避免過擬合狀況，最終選取epoch參數(shù)為30 進行訓練，并采用early stopping 方法，當模型在驗證集上的表現(xiàn)變差時停止訓練。

圖4 訓練集、驗證集損失函數(shù)變化Fig.4 loss on train set and validation set

訓練中，內(nèi)存限制使得數(shù)據(jù)無法一次性載入，而是分批次投入訓練。批次大小batch_size影響著模型效果，過小時收斂效果較差，適當增大可以使得梯度下降方向更準確，但過大會導致模型收斂速度緩慢。

圖5 展示了epoch=30 時不同batch_size對預測結果的影響。隨著樣本批增大，固定的訓練輪次數(shù)下各項誤差指標數(shù)值上升，取值64 時表現(xiàn)相對最佳。最終超參數(shù)epoch、batch_size的值選取30、64 進行訓練測試，保證路網(wǎng)建模的準確性。

圖5 批次大小的影響Fig.5 Influence of batch size

3.2.2 深度搜索方法效果比較

對于給定查詢?nèi)M{n,n0,T}，有實際最優(yōu)路徑H，搜索算法得到含冗余的過程集A、預測路徑H′，相關研究中路徑的準確率P(precision)、召回率R(recall)可定義為：

準確率P反映預測的路徑與實際路徑的吻合程度，召回率R反映最優(yōu)路徑的查全比例，路徑中節(jié)點數(shù)相近使兩者數(shù)值上趨于接近。此外，為查找最優(yōu)解，啟發(fā)式的算法在搜索過程中都拓展了大量冗余節(jié)點即A，可以使用|H′|/|A|反映搜索的有效率。

2.3 節(jié)定義了三種深度估價及搜索方法，僅最小值深度估價的搜索（only-min）、以距離差加權深度估價的搜索（dis-α）、基于深度估價網(wǎng)絡的搜索（GCNSearch），并與A*算法進行對比。深度搜索方法效果的實驗與建模部分相互獨立，在信息已知的交通圖上進行。圖6展示了幾種深度方法搜索過程的有效率。

圖6 不同估價方法的結果Fig.6 Results of different valuation algorithms

實驗對比可知，采用深度估價的方法相比A*方法搜索有效率更高。這說明了使用深度估價方法可以有效提高估價函數(shù)準確性，改善搜索效果。其中，僅最小值深度估價方法在復雜路網(wǎng)任務中表現(xiàn)略好于更精細的距離差加權方法，基于圖卷積核參數(shù)的網(wǎng)絡GCN-Search 表現(xiàn)最佳。整合兩部分得到調(diào)參后效果最佳的路網(wǎng)最優(yōu)路徑深度搜索方法GCN-Search。

3.3 不同算法對比分析

針對定義1 的城市出行情景，將貪心策略搜索greedy、神經(jīng)網(wǎng)絡PCNN[25]以及深度強化學習方法DRL[26]，與本文深度搜索模型GCN-Search 進行對比。該情景中進行最優(yōu)路徑搜索時，當前與未來的路網(wǎng)信息是未知量，各模型得到近似最優(yōu)解的預測路徑H′，圖7 展示了幾種算法的準確率、召回率、平均查詢時間。從圖中可以看到，GCN-Search 的準確率、召回率均高于其他算法。相較于效果較好的深度強化學習方法，準確率、召回率分別提高了0.044 2、0.079 1。查詢時依賴大量矩陣運算與路網(wǎng)更新，使機器學習方法平均查詢時間都較高；因僅使用鄰域內(nèi)相關節(jié)點及時間位置信息進行計算，GCN-Search 深度搜索的時間消耗略低于計算路網(wǎng)整體的DRL方法。

圖7 不同算法模型結果比較Fig.7 Results of different algorithms

實驗表明GCN-Search 在城市出行場景中，能有效利用動態(tài)路網(wǎng)中的時空信息，學習路網(wǎng)內(nèi)在模式，對路網(wǎng)進行合理建模并準確地對節(jié)點進行估價，從而找到更接近最優(yōu)的路徑。絕對數(shù)值上，所有算法效果都并非極佳，一個原因是動態(tài)的現(xiàn)實路網(wǎng)存在代價相似的多條路徑，算法得到的結果陷入其中從而與最優(yōu)解有一定差距。

4 結束語

動態(tài)路網(wǎng)中的最優(yōu)路徑規(guī)劃是計算機和交通方向的研究熱點，可為各類基于位置的服務和應用提供重要支持。本文考慮到在動態(tài)路網(wǎng)場景中，充分利用時間、空間信息可以改善最優(yōu)路徑搜索效果，使用STGCN 的建模、加深搜索深度的實驗結果證明了這一思想的可行性。同時相較于以往方法，本文將最優(yōu)路徑搜索問題定義在路網(wǎng)未來狀況未知需建模預測的情景中，更接近現(xiàn)實出行情況，以圖卷積網(wǎng)絡建模路網(wǎng)動態(tài)變化，使用深度估價網(wǎng)絡替代人工設計的估價函數(shù)，獲得了理想的實驗結果，具有一定實用價值，也體現(xiàn)了圖神經(jīng)網(wǎng)絡、啟發(fā)式思想解決交通領域問題的強大能力。但是，該算法對RFID 數(shù)據(jù)的高維度信息利用率較低，接下來將重點關注如何利用多維語義信息使路網(wǎng)建模與現(xiàn)實更吻合，進一步提高效果。