基于車輛GPS軌跡數據的農村公路地圖匹配算法

毛海臻 毛華

摘 要：為了提升農村地區車輛軌跡與縣鄉路網的匹配精度，解決車輛行駛軌跡飄移、點位跳躍等問題，本研究基于隱形馬爾可夫理論，通過劃分農村公路網格，計算觀測概率與轉移概率乘積的最大值，然后通過編程建模篩選出最佳候選路線，實現車輛軌跡與農村路網的在線匹配。筆者選取平頂山市寶豐縣某農村公路為研究對象，現場驗證了該算法的可行性和有效性。試驗結果表明：該算法能夠提升農村公路車輛軌跡的匹配精度，在路線十字、T形交叉及平曲線中點等區域的軌跡匹配精度提升效果明顯。

關鍵詞：農村公路;GPS軌跡數據;地圖匹配

中圖分類號：U418.6 ? ? ?文獻標志碼：A ? ? 文章編號：1003-5168（2022）11-0022-04

DOI：10.19968/j.cnki.hnkj.1003-5168.2022.11.004

Rural Road Map Matching Algorithm Based on Vehicle GPS Trajectory Data

MAO Haizhen1? ? MAO Hua2

（1.Henan Communications Planning & Design Institute Co.，Ltd，Zhengzhou 450000，China;

2.Hebi Qibin District Transportation Bureau，Hebi 458030，China ）

Abstract：In order to improve the matching accuracy between vehicle trajectory and county and township road network in rural areas，and solve the problems of vehicle trajectory drift，point jumping and so on.With the help of hidden Markov theory，this paper divides the rural road grid，calculates the maximum product of observation probability and transfer probability，selects the best candidate route through programming modeling，and realizes the online matching between vehicle trajectory and rural road network.A rural highway in Baofeng County，Pingdingshan City is selected as the experimental object to verify the feasibility and effectiveness of the algorithm.The results show that the algorithm can improve the track matching accuracy of rural road vehicles.In the areas of route cross，T-shaped cross and the midpoint of horizontal curve，the track matching accuracy is obviously improved.

Keywords：rural highway;GPS track data;map matching

0 引言

近年來，我國鄉村公路發展迅速，截至2021年10月，全國農村公路通車里程達到438.2萬 km。但部分鄉村地區受通信基站數量少、地形地貌復雜等因素的影響，導致車輛GPS軌跡點位與實際路線存在偏差大、匹配度低等問題，如何有效提升鄉村公路車輛軌跡匹配精度已成為研究的重點問題。

地圖匹配（map-matching）技術是在車輛處于行駛狀態下，實時收集、分析車輛的地理空間信息，借助算法模型來實現車輛經緯度與路線位置的動態關聯[1]。針對路網軌跡算法模型，國內外學者已相繼提出幾何模型、權重模型、網絡拓撲模型等，但在路網匹配精度和軌跡匹配時間方面仍存在諸多問題[2]。鄉村公路具有線多面廣、路網復雜的特點，傳統的軌跡匹配模型已無法滿足農村公路車輛軌跡匹配的精度要求。對此，本研究基于隱馬爾可夫模型，建立基于車輛GPS軌跡數據的農村公路地圖匹配模型，通過劃分路線網格，計算觀測概率、轉移概率，尋找最大的似然路徑，從而實現車輛行駛軌跡與農村路網的動態匹配。本研究選取平頂山市寶豐縣某農村公路為研究對象，現場驗證算法模型的可行性、準確性，從而有效提升農村路網車輛軌跡的匹配程度。

1 農村公路車輛軌跡匹配模型

1.1 劃分農村公路網格

隨著采集頻率和行駛時間的增加，車輛GPS軌跡點位與路網經緯度的數據集合會成倍數關系增長，從而造成算法模型遍歷計算任務重，導致匹配耗時長。依據農村公路路線長度遠大于寬度的特征，近似將農村公路看作一條曲線，將路線的集合作為路網。在電子地圖基礎上，預先將路網進行網格化劃分（網格間距約為100 m）[3]，并將網格單元進行分類排序、編碼存儲，進而提升數據庫的計算運行效率。

1.2 車輛軌跡匹配模型

為了進一步提升軌跡點位匹配的效率及精度，通過設定圓形誤差檢索區域，縮小候選路線范圍。檢索區域的路線數量Φ分為以下3種情況：①當路線數量Φ為0時，說明受地形環境或數據精度的影響，該GPS點位發生跳躍，無法與路網進行關聯匹配，在路網匹配過程中需要將此類無效數據進行剔除;②當路線數量Φ為1時，說明檢索區域范圍僅存在1條候選路線，車輛軌跡能夠真實有效地反映出路網空間線形，該候選路線可作為最終結果進行直接匹配;③當路線數量Φ為2時，表明檢索區域內存在2條候選路線，此情況多出現在路線交叉的區域，無法明確與GPS點位相匹配的具體路線，需借助計算模型比較軌跡點位與各路線間的最小距離ε。B4580923-1B7C-4064-8555-C506F1A371D8

依據數據點位匹配特征，發現最小距離ε與匹配概率成反比，即最小距離ε越小，匹配概率越高。選取高斯分布公式建立正態分布，計算軌跡點位于某候選路線的觀測概率，見式（1）[4]。

[Pd（Trn︱Φi）=12πσze?12D（Φi，Trn）2σ2z]? （1）

式中：[Trn]為軌跡點位;[σz]為GPS點位的標準差，取20 m[5];[D（Φi，Trn）]表示點到候選路線的垂直距離。

候選路線的選取受相鄰軌跡點的路線連續性的影響。同時，考慮到農村公路路線交叉多等特征，車輛行駛軌跡可能存在頻繁轉彎、點位跳躍等情況。對此，依據上個軌跡點所在的候選路線計算下個軌跡點所在候選路段的概率時，選用Manhattan公式來計算點間距[D1]，依次遍歷最小距離[ε]與[D1]的差值，可得出車輛軌跡中連續點位的轉移概率，見式（2）（3）[4]。

[dij]=[Dsp（Φi，Φj）]-[D1（Trn，Trn+1）]? ?（2）

[Pd（Φi，Trn，Φj，Trn+1）]=[? 1βedijβ0]? ? （3）

式中：[Dsp（Φi，Φj）]<[THDsp]時，[Pd]取[1βedijβ]，反之則取0;[THDsp]為最短路徑閾值，該值取決于車輛行駛速度;[β]為模型參數[2]。

1.3 車輛軌跡匹配

在已知觀測概率及轉移概率的基礎上，采用維特比算法（Viterbi algorithm）來尋找最大似然路線[2]，即通過n個GPS軌跡點的觀測概率、轉移概率來計算所有情況下兩者的乘積結果，乘積最大值的組合方式就是最接近真實路徑的車輛軌跡，如圖1所示。

1.4 編程建模開發應用

依據車輛軌跡的數據特征，建立涵蓋車輛經緯度（lng，lat）、方位角[θ]、速度v、間隔時間t等參數的專題數據庫，數據庫類型選取目前應用廣泛的MySQL。通過編程語言建立軌跡點位與路網數據的動態匹配模型，基于Java語言定制開發Android手機軟件（見圖2），通過高德地圖API將處理前后的車輛行駛軌跡展示出來。由于高德地圖采用的是GCJ-02火星坐標系，若直接使用WGS84坐標會造成點位偏差，因此在傳遞經緯度數據時應將坐標系格式進行統一[6]。

2 車輛軌跡匹配流程

依據數據采集、編程建模、開發驗證等環節，總結車輛GPS軌跡數據與農村公路地圖匹配算法流程，具體如下。

①采集車輛軌跡GPS點位數據（包括經緯度、間隔時間、瞬時速度等），調用農村公路電子地圖，對初始數據進行篩選、清洗，創建數據庫、數據表。

②依據農村公路路網密度，設定單元網格尺寸，批量生成單元模塊，并進行分類排序、編碼存儲。

③劃定誤差檢索區域范圍，優選圓形誤差閾值、采點頻率等相關參數及數據標準。

④確定誤差檢索范圍內存在的路線數量Φ，判定是否需要借助模型篩選候選路徑。

⑤計算候選點的觀測概率、轉移概率、最小距離等，確定最大似然路線。

⑥通過編程建模、開發應用模塊、現場采集驗證，最終得到車輛的優化軌跡。

3 試驗結果分析

為驗證車輛軌跡與農村路網匹配模型的有效性，以平頂山市寶豐縣某農村公路為試驗對象，通過現場采集車輛GPS點位信息，對比算法優化前后車輛軌跡匹配結果存在的差異。

車輛行駛點位的采集頻率將影響連續兩點的距離誤差及數據計算效率。隨著采集頻率的增加，采樣點將更為密集，軌跡數據誤差減小，但路網的匹配效率降低。為兼顧采集誤差及計算效率的合理性，現場試驗測試得出車輛連續GPS點位的采集時間間隔為20 s。

在保證車輛行駛速度、采樣頻率、起始時間等因素相同的前提下，平行采集車輛GPS軌跡點位，分別驗證農村公路線形為直線、曲線及交叉口區域的軌跡優化效果，車輛GPS點位的數據處理結果如表1、表2所示。

為了能夠更直觀地展示路網匹配修正效果，將縣鄉道路電子地圖、原始車輛軌跡、優化后軌跡分別導出為CSV或shp文件，借助ArcGIS及奧維地圖軟件，生成可視化的放大圖片，如圖3、圖4所示

通過對圖3、圖4進行分析可以得出：①當農村公路線型為直線時，車輛原始軌跡、模型優化軌跡與路網的偏差較小，均能真實地反映出車輛的行駛軌跡;②當道路線形的平曲線半徑較小時，車輛軌跡易在平曲線中點附近發生偏移，相較于原始數據，經模型優化后的軌跡可以更加準確地反映出車輛行駛軌跡;③當位于農村公路交叉口時，存在檢索區域的路線數量Φ為2的時刻，疊加GPS精度誤差，原始軌跡的部分點位可能跳躍至其他路線，而優化后的車輛軌跡能夠有效保持車輛軌跡的準確性、連續性，避免發生點位偏離距離過大等現象。

4 結論

為提升車輛GPS軌跡與農村路網的匹配程度，本研究基于隱馬爾科夫模型，通過計算觀測概率、轉移概率等參數，得出車輛最佳行駛軌跡，并以平頂山市寶豐縣某農村公路為例，編程驗證匹配模型的可行性、有效性。試驗結果表明，經模型優化后的車輛GPS軌跡與路網的匹配程度較好，在曲線、路線交叉等復雜路網條件下，路網匹配精度良好。

參考文獻：

[1] 于娟，楊瓊，魯劍鋒，等.高級地圖匹配算法：研究現狀和趨勢[J].電子學報，2021（9）：1818-1829.

[2] 高文超，李國良，塔娜.路網匹配算法綜述[J].軟件學報，2018（2）：225-250.

[3] 吉宏梅.基于隱馬爾可夫模型的路網匹配算法研究[D].沈陽：沈陽理工大學，2020.

[4] 陳浩，許長輝，張曉平，等.基于隱馬爾科夫模型和動態規劃的手機數據移動軌跡匹配[J].地理與地理信息科學，2019（3）：1-8.

[5] 文江輝，霍佳琪，楊玲.一種車輛GPS軌跡數據的改進地圖匹配算法[J/OL].武漢理工大學學報（交通科學與工程版），2022：1-11[2022-05-01].http：//kns.cnki.net/kcms/detail/42.1824.U.20220309.2125.093.html

[6] 康路，閆浩文，張黎明.電子地圖間的實時坐標轉換系統[J].遙感信息，2018（2）：122-126.B4580923-1B7C-4064-8555-C506F1A371D8