費(fèi) 珂，秦小麟，遲賀宇，李 瑭

南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京211106

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

表1 關(guān)鍵符號(hào)及含義Table 1 Key symbols and their description

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

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

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

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

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

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

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

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

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

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

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

2.forTi,Ti+1inTsorteddo

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

4.Hi←Ti+1-Ti//計(jì)算單段移動(dòng)軌跡

5.end for

6.Ck←divideHset//按頂點(diǎn)分類單段軌跡

7.for eachCkdo

8.thresholdck←Ck//計(jì)算閾值

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

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

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

2.2.1 整體結(jié)構(gòu)

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

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

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

2.2.2 時(shí)間域卷積模塊

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

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

2.2.3 空間域卷積模塊

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

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

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

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

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

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

2.3 深度搜索

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

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

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

2.3.1 深度搜索定義

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

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

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

2.3.2 深度搜索復(fù)雜度

搜索深度的增加會(huì)對(duì)搜索的復(fù)雜度造成影響，需要確保其復(fù)雜度可控。

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

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

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

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

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

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

2.3.3 深度搜索方法

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

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

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

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

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

輸入：頂點(diǎn)屬性序列{V0,V1,…,Vl}，鄰接矩陣A，查詢起點(diǎn)、終點(diǎn)、時(shí)間三元組{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ù)劃分為訓(xùn)練集與驗(yàn)證集

3.Put train set into STGCN//輸入訓(xùn)練集

4.forepochinepochsdo:

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

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

7.early stopping//在驗(yàn)證集使用早停法

8.end for

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

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

11.as step 4～7,train Deep Valuation Network withH//訓(xùn)練深度估價(jià)網(wǎng)絡(luò)

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

13.n∈O,f(n)←GCN//計(jì)算深度評(píng)估值

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

15.end while

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

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

3 實(shí)驗(yàn)與分析

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

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

模型基于Pytorch 深度學(xué)習(xí)框架，實(shí)驗(yàn)的運(yùn)行環(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 得到對(duì)路網(wǎng)建模的中間結(jié)果，在中間結(jié)果的基礎(chǔ)上進(jìn)行深度搜索。完整算法由兩部分共同組成，針對(duì)這兩部分進(jìn)行獨(dú)立的實(shí)驗(yàn)比較。

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

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

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

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

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

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

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

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

3.2.2 深度搜索方法效果比較

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

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

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

圖6 不同估價(jià)方法的結(jié)果Fig.6 Results of different valuation algorithms

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

3.3 不同算法對(duì)比分析

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

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

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

4 結(jié)束語

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