面向動態路網的最優路徑GCN 深度搜索方法

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

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

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

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

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

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

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

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

1 相關工作

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

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

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

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

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

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

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

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

2.1 數據預處理

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

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

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

圖1 劃分軌跡數據Fig.1 Divide trajectory data

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

算法1RFID 數據預處理算法

輸入：原始數據集合T，頂點集合V。

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

1.Tsorted←T//數據重排序

2.forTi,Ti+1inTsorteddo

3.drop isolated and redundantTi//刪除孤立數據點、冗余數據等

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

5.end for

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

7.for eachCkdo

8.thresholdck←Ck//計算閾值

9.drop out-of-range data//按閾值刪除數據

10.ifHilacks data:

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

12.end for

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

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

2.2 動態路網建模

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

2.2.1 整體結構

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

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

圖3 特征傳播與網絡細節Fig.3 Feature transfer and network details

2.2.2 時間域卷積模塊

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

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

2.2.3 空間域卷積模塊

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

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

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

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

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

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

2.3 深度搜索

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

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

估價最優的節點next移動至C，其不在C中的鄰接節點更新距離并添加至O。基于A*算法的啟發式思想進一步優化，提升擴展時的搜索深度，使用深度估價神經網絡替代人為設計的估價函數，以改進搜索效果。

2.3.1 深度搜索定義

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

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

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

2.3.2 深度搜索復雜度

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

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

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

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

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

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

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

2.3.3 深度搜索方法

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

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

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

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

算法2最優路徑深度搜索算法

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

輸出：路網中最優路徑{n,v1,v2,…,n0}。

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

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

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

4.forepochinepochsdo:

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

6.Adjust STGCN parameters//反向傳播調整網絡參數

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

8.end for

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

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

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

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

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

14.updateCandO//更新狀態集

15.end while

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

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

3 實驗與分析

3.1 數據集與實驗環境

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

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

3.2 路網建模效果及深度搜索方法比較

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

3.2.1 不同參數對STGCN 建模效果的影響

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

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

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

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

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

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

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

3.2.2 深度搜索方法效果比較

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

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

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

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

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

3.3 不同算法對比分析

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

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

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

4 結束語

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