陳良健 許建秋

摘要：路網(wǎng)匹配是道路網(wǎng)軌跡數(shù)據(jù)分析領(lǐng)域的一項(xiàng)關(guān)鍵技術(shù)，一個(gè)快速且準(zhǔn)確的路網(wǎng)匹配算法能夠?yàn)樯蠈討?yīng)用提供良好的技術(shù)支持.隨著軌跡數(shù)據(jù)的爆炸式增長，現(xiàn)有的在線路網(wǎng)匹配算法存在延時(shí)的現(xiàn)象，尤其是在低頻軌跡數(shù)據(jù)的環(huán)境下，無法快速地對軌跡數(shù)據(jù)進(jìn)行路網(wǎng)匹配.神經(jīng)網(wǎng)絡(luò)和深度學(xué)習(xí)的發(fā)展為解決這些問題提供了新的方法.提出了一種利用門控循環(huán)單元（Gated Recurrent Unit，GRU）模型快速定位軌跡采樣點(diǎn)的候選路段、從而加速在線路網(wǎng)匹配計(jì)算的方法，并將此方法和最新的在線路網(wǎng)匹配算法進(jìn)行了實(shí)驗(yàn)比較.結(jié)果表明，基于GRU模型的在線路網(wǎng)匹配算法能夠有效地加快匹配過程，提高匹配效率.

關(guān)鍵詞：在線路網(wǎng)匹配;移動(dòng)對象;門控循環(huán)單元模型

中圖分類號(hào)：TP392

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1000-5641（2020）06-0063-09

0引言

近年來，隨著位置感知技術(shù)的發(fā)展以及定位系統(tǒng)（如GPS、北斗系統(tǒng)）的普及，出現(xiàn)了越來越多的位置感知類應(yīng)用，如網(wǎng)約車、共享單車等.這些應(yīng)用在系統(tǒng)使用過程中跟蹤和記錄移動(dòng)對象的位置信息，產(chǎn)生大量的時(shí)空軌跡數(shù)據(jù).但是由于設(shè)備精度或地理環(huán)境因素，收集到的軌跡數(shù)據(jù)與真實(shí)的路線存在一定的偏差.如圖1所示，GPS軌跡采樣點(diǎn)并沒有落在移動(dòng)對象實(shí)際行駛的道路上，存在一定的空間偏移.這對位置感知類應(yīng)用的服務(wù)質(zhì)量和軌跡數(shù)據(jù)分析帶來一些挑戰(zhàn).路網(wǎng)匹配技術(shù)就是根據(jù)軌跡的采樣點(diǎn)分布，并結(jié)合路網(wǎng)信息推斷移動(dòng)對象實(shí)際行駛路徑的過程.路網(wǎng)匹配技術(shù)是交通管理、路由規(guī)劃、實(shí)時(shí)導(dǎo)航等應(yīng)用中的基礎(chǔ)技術(shù)，已被廣泛地運(yùn)用于城市計(jì)算與智能交通領(lǐng)域.

現(xiàn)有的路網(wǎng)匹配算法按照運(yùn)用場景一般分為兩大類：離線匹配和在線匹配.離線匹配針對的是歷史軌跡數(shù)據(jù)，即在得到移動(dòng)對象產(chǎn)生的一條完整的軌跡之后再推斷移動(dòng)對象實(shí)際行駛的路徑.離線匹配在匹配時(shí)可以充分考慮軌跡的上下文信息.相反地，在線匹配算法針對的是實(shí)時(shí)數(shù)據(jù)，在接收到移動(dòng)對象的最新位置信息時(shí)，立即返回移動(dòng)對象所行駛的路徑，這種情況下只能獲得移動(dòng)對象在當(dāng)前采樣點(diǎn)及其之前的軌跡信息，而無法獲得完整的軌跡信息，所以具有一定的難度.例如（見圖2），如果利用在線匹配算法，在匹配到t₃采樣點(diǎn)時(shí)，因?yàn)閠₃距離路段2較近，且路段2的道路寬度更寬，表明從路段1到路段2的轉(zhuǎn)移概率較大，所以按照目前的許多在線匹配算法，很可能就匹配到了錯(cuò)誤的路線上.而離線匹配算法在匹配t₃采樣點(diǎn)時(shí)可以獲取到t₄采樣點(diǎn)的信息，能夠直接匹配到正確的路段3，從而獲得更高的匹配準(zhǔn)確率.但是，實(shí)際生活中的很多應(yīng)用，如汽車實(shí)時(shí)導(dǎo)航、交通實(shí)時(shí)監(jiān)測系統(tǒng)，這些與位置有關(guān)的應(yīng)用需要在接收到移動(dòng)對象的位置信息后立即計(jì)算匹配結(jié)果，并對其做出響應(yīng)，所以需要采用在線路網(wǎng)匹配技術(shù).而且隨著智慧城市以及智能交通系統(tǒng)等概念的提出和推廣，在線匹配算法的應(yīng)用場景將變得越來越廣泛且重要.

常見的在線匹配算法一般采用時(shí)間窗口技術(shù)，即存儲(chǔ)最近一段時(shí)間的軌跡采樣信息，當(dāng)滿足一定的收斂條件時(shí)推測出的最可能路段序列，這種算法在一個(gè)采樣點(diǎn)到達(dá)之后并不能立即計(jì)算得到移動(dòng)對象目前行駛的路段，而是需要達(dá)到一定的收斂條件，所以存在一定的滯后性.并且這種算法需要在兩個(gè)連續(xù)采樣點(diǎn)之間計(jì)算所有可能的路徑，算法代價(jià)較大.最近幾年出現(xiàn)了一系列基于隱含馬爾科夫模型（Hiddenmarkovmodel，HMM）的在線路網(wǎng)匹配算法，但是基于隱含馬爾科夫模型的算法復(fù)雜度較高，仍然存在一定的延時(shí)，在稀疏的軌跡數(shù)據(jù)集上表現(xiàn)不好;且現(xiàn)有的路網(wǎng)匹配算法在計(jì)算候選集時(shí)一般借助空間索引比如R-tree或者Quad-tree來剪枝，搜索效率不高，不適用于大規(guī)模實(shí)時(shí)數(shù)據(jù)并發(fā)的場景.

近年來隨著神經(jīng)網(wǎng)絡(luò)和深度學(xué)習(xí)的發(fā)展，人工智能技術(shù)滲透到數(shù)據(jù)處理領(lǐng)域的方方面面.在處理時(shí)間序列數(shù)據(jù)時(shí)，循環(huán)神經(jīng)網(wǎng)絡(luò)（Recurrent Neural Network，RNN）以其特殊的結(jié)構(gòu)擁有一定的記憶能力，是處理時(shí)間序列數(shù)據(jù)的一個(gè)很好的工具.但是直接利用RNN進(jìn)行路段預(yù)測在軌跡過長的情況下會(huì)帶來長程依賴問題.基于此，本文提出了一種基于RNN變體——門控循環(huán)單元（GRU）的路網(wǎng)匹配加速算法，在計(jì)算候選路段時(shí)，根據(jù)軌跡之前的信息和目前收集到的軌跡采樣點(diǎn)直接定位最大概率的候選路段，不需要對道路網(wǎng)建立空間索引，減少了根據(jù)時(shí)空位置計(jì)算候選路段集以及搜尋所有可能路徑的過程，加速了路網(wǎng)匹配計(jì)算過程.測試結(jié)果表明，基于GRU模型的在線路網(wǎng)匹配算法在匹配效率上遠(yuǎn)高于目前的在線匹配算法.

本文結(jié)構(gòu)如下：第1章簡要介紹路網(wǎng)匹配，尤其是在線路網(wǎng)匹配的研究現(xiàn)狀;第2章定義在線路網(wǎng)匹配問題;第3章介紹基于GRU模型的路網(wǎng)匹配算法過程，包括路網(wǎng)模型的建立、GRU模型的構(gòu)建和優(yōu)化目標(biāo)的提出;第4章將本文提出的算法與現(xiàn)有的在線路網(wǎng)匹配算法進(jìn)行分析和比較;第5章總結(jié)全文.

1研究現(xiàn)狀

路網(wǎng)匹配算法主要分成基于幾何的匹配算法、基于拓?fù)浣Y(jié)構(gòu)的匹配算法、基于概率的匹配算法以及其他先進(jìn)匹配算法.基于幾何的路網(wǎng)匹配算法利用路網(wǎng)和GPS軌跡的幾何形狀特征進(jìn)行匹配，包括點(diǎn)到點(diǎn)（point-to-point）匹配、點(diǎn)到曲線（point-to-curve）匹配、曲線到曲線（curve-to-curve）匹配.基于拓?fù)浣Y(jié)構(gòu)的匹配算法利用路網(wǎng)的拓?fù)浣Y(jié)構(gòu)信息，如路段之間的相連、相交等關(guān)系，再結(jié)合歷史數(shù)據(jù)和車輛速度等信息來對候選匹配路段進(jìn)行剪枝.如Brakatsoulas等利用道路網(wǎng)的幾何拓?fù)湫畔⒓癎PS數(shù)據(jù)之間的各項(xiàng)相似性標(biāo)準(zhǔn)進(jìn)行路網(wǎng)匹配，并采用弗雷歇距離（Frechet distance）來衡量兩者的匹配程度.其他先進(jìn)的路網(wǎng)匹配算法包括卡爾曼濾波、模糊邏輯模型、隱含馬爾科夫模型（HMM）、機(jī)器學(xué)習(xí)等.這些算法利用先進(jìn)的技術(shù)手段或數(shù)學(xué)模型，匹配準(zhǔn)確度較高，但是當(dāng)采樣頻率較低時(shí)，效果仍然不佳.高文超等和Ta等對目前的路網(wǎng)匹配算法做了全面的分類、總結(jié)和分析.

3.3模型優(yōu)化目標(biāo)

路網(wǎng)匹配可以視為一個(gè)多分類（Multiclass Classification）問題，每一個(gè)GPS采樣點(diǎn)可能匹配到整個(gè)路網(wǎng)中的任意路段.所以對于損失函數(shù)的選擇，一種樸素的方案是直接使用交叉熵.具體地，1條GPS序列可以看作1個(gè)樣本，單個(gè)樣本的交叉熵?fù)p失Loss_i定義為

然而，在路網(wǎng)匹配任務(wù)中，路段之間存在拓?fù)浣Y(jié)構(gòu).采用這種簡單的方法無法捕獲路段之間的位置關(guān)系，對預(yù)測錯(cuò)的路段不管距離遠(yuǎn)近都施加同樣的懲罰，導(dǎo)致模型無法感知路網(wǎng)空間距離，訓(xùn)練時(shí)收斂較慢，而且容易帶來過擬合問題.例如，假設(shè)有如圖4所示的道路網(wǎng)，移動(dòng)對象行駛路線如圖中帶箭頭黑色實(shí)線所示，其正確的匹配路徑結(jié)果應(yīng)當(dāng)為①②③④，當(dāng)其行駛到②路段時(shí)，產(chǎn)生一個(gè)在圖中黑點(diǎn)所示的軌跡采樣點(diǎn)，如果模型錯(cuò)誤地匹配到⑤，那么實(shí)際上和錯(cuò)誤地匹配到⑥產(chǎn)生的懲罰效果是一樣的，但是在實(shí)際應(yīng)用中，人們更能接受算法將其匹配到⑤，而不是毫不相關(guān)的⑥.

為了在模型預(yù)測的結(jié)果中同時(shí)考慮路網(wǎng)之間的位置信息，對原損失乘一個(gè)距離乘數(shù)k，給實(shí)際路段偏差較大的預(yù)測結(jié)果施加更大的懲罰因子，這樣就可以讓模型感知到路段之間的空間距離，從而加快模型收斂速度.具體地，定義損失函數(shù)

上述目標(biāo)可以通過梯度下降法進(jìn)行優(yōu)化.模型訓(xùn)練完畢后，即可對新樣本進(jìn)行預(yù)測.預(yù)測過程的簡要流程見算法1.

算法1首先初始化隱藏狀態(tài)（行1）.對于每次接收到的移動(dòng)對象的采樣點(diǎn)t_i，算法將對其進(jìn)行歸一化處理得到輸入向量u_i（行3），隨后，模型對輸入向量進(jìn)行預(yù)測并輸出結(jié)果o_i（行4），根據(jù)輸出結(jié)果直接定位當(dāng)前的預(yù)測路段，然后采用最短路徑連接上一回合的預(yù)測路段和當(dāng)前預(yù)測路段，直到移動(dòng)對象產(chǎn)生一條完整的軌跡序列.

4實(shí)驗(yàn)結(jié)果分析

4.1實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)的路網(wǎng)數(shù)據(jù)采用南京市的路網(wǎng)數(shù)據(jù).軌跡數(shù)據(jù)采用南京出租車產(chǎn)生的真實(shí)GPS軌跡數(shù)據(jù).在訓(xùn)練過程中，采用離線路網(wǎng)匹配算法HMMM對軌跡采樣點(diǎn)所在的路段進(jìn)行標(biāo)記.在實(shí)驗(yàn)中，分別測試不同采樣頻率下各個(gè)算法的準(zhǔn)確率和性能，不同采樣頻率的軌跡是在原始軌跡下通過二次采樣產(chǎn)生的.實(shí)驗(yàn)數(shù)據(jù)的基本信息見表2.

在訓(xùn)練和比較高頻軌跡數(shù)據(jù)集時(shí)（采樣點(diǎn)時(shí)間間隔小于30s），隨機(jī)選擇10000條作為測試數(shù)據(jù)集，其余則劃分為訓(xùn)練集.由于長度較長的軌跡較少，所以在訓(xùn)練低頻軌跡數(shù)據(jù)時(shí)，二次采樣會(huì)進(jìn)行重復(fù)采樣.最后，得到15000條完整軌跡，訓(xùn)練數(shù)據(jù)集大小為10000條，測試數(shù)據(jù)集大小為5000條.

4.2實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)在Ubuntu14.04環(huán)境下進(jìn)行，采用Python3.6語言編寫，利用Pytorch1.0深度學(xué)習(xí)框架;CPU為Intel Xeon（R）1.90GHz×6，GPU為NVIDA Corporation GM107GL[Quadro K2200]，32GB內(nèi)存.

4.3實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)首先采用正交初始化進(jìn)行模型的權(quán)重初始值設(shè)定，初始偏移值設(shè)為0.每訓(xùn)練1條軌跡序列則進(jìn)行1次梯度更新，直到訓(xùn)練完所有的訓(xùn)練數(shù)據(jù).高頻軌跡的訓(xùn)練時(shí)間約為4h，低頻軌跡的訓(xùn)練時(shí)間約為1h.然后將本文的基于GRU模型的路網(wǎng)匹配算法分別與文獻(xiàn)[14]中提出的OHMM算法、文獻(xiàn)[15]提出的INC-RB算法在準(zhǔn)確率和效率這兩個(gè)方面進(jìn)行比較.

圖5給出了準(zhǔn)確率的實(shí)驗(yàn)結(jié)果，橫軸為不同的采樣頻率，縱軸為具體的準(zhǔn)確率值.準(zhǔn)確率的計(jì)算方式為算法預(yù)測準(zhǔn)確的路段與總路段之比，從圖5中可以看出，在高頻采樣段，基于GRU模型的路段預(yù)測算法的準(zhǔn)確率會(huì)稍低于INC-RB算法和OHMM算法，但是也接近94%;隨著采樣頻率的降低，INC-RB算法和OHMM算法的準(zhǔn)確率會(huì)逐漸衰減，而基于GRU的算法的準(zhǔn)確率仍然能夠保持在一個(gè)較高的水平.

圖6給出了基于GRU的路網(wǎng)匹配算法與INC-RB和OHMM在效率方面的比較，橫軸為不同的采樣頻率，縱軸為算法的處理速度，單位為每毫秒處理的采樣點(diǎn)個(gè)數(shù)，在圖中可以看到基于GRU的路網(wǎng)匹配算法不管在低頻軌跡數(shù)據(jù)集還是高頻軌跡數(shù)據(jù)集中，效率上都遠(yuǎn)超上述兩種算法.從高頻數(shù)據(jù)轉(zhuǎn)為低頻數(shù)據(jù)的過程中，由于GPS采樣點(diǎn)之間的距離較遠(yuǎn)，所以INC-RB和OHMM的計(jì)算量較大;而由于在低頻軌跡數(shù)據(jù)中，每條路徑中的采樣點(diǎn)個(gè)數(shù)相對較少，所以基于GRU模型的路網(wǎng)匹配算法需要在測試時(shí)不斷進(jìn)行初始化，導(dǎo)致統(tǒng)計(jì)時(shí)的效率變低.

5結(jié)論

本文提出了一種利用GRU模型對路段直接進(jìn)行定位的在線路網(wǎng)匹配算法，和目前最新的在線路網(wǎng)匹配算法相比，基于GRU模型的路網(wǎng)匹配算法不需要對路網(wǎng)建立索引，匹配時(shí)不需要遍歷索引產(chǎn)生多條候選路段，也不需要搜索多條推測路徑，從而大大加快了路網(wǎng)匹配過程.在以后的研究工作中，為了應(yīng)對更大的道路網(wǎng)環(huán)境，可以將圖進(jìn)行分割，減小GRU的選擇范圍;同時(shí)由于本文算法還未考慮額外的一些信息，如移動(dòng)對象的速度和方向，故將來可以從GPS軌跡中提取這些額外的信息進(jìn)行訓(xùn)練，從而更進(jìn)一步提高算法的精確性.