計及車輛信息的隱馬爾可夫地圖匹配優(yōu)化算法

【摘要】為解決車輛在路況重疊的高架區(qū)域進(jìn)行地圖匹配時信號傳輸受到遮擋，導(dǎo)航易出現(xiàn)誤匹配、輸出時延增加和車道偏移等問題，提出記及車輛信息的隱馬爾可夫地圖匹配優(yōu)化算法消除導(dǎo)航系統(tǒng)的此類缺陷。算法采用剔除采樣數(shù)據(jù)中冗余和漂移的定位點；確定候選道路時生成網(wǎng)格索引，利用道路拓?fù)鋭h除不相連道路，減少計算量，降低輸出時延；利用道路和車輛信息生成可信度函數(shù)，融合速度相似性改進(jìn)轉(zhuǎn)移概率，確定匹配路段。實驗結(jié)果表明，車輛行駛至高架區(qū)域時，匹配時間更短，時長未隨路段的增多而增加；且具有高準(zhǔn)確率，滿足車輛在三維區(qū)域的匹配需求。

主題詞：城市路網(wǎng) 隱馬爾可夫模型 地圖匹配 車輛信息

中圖分類號：P208" "文獻(xiàn)標(biāo)志碼：A" "DOI： 10.19620/j.cnki.1000-3703.20230173

Hidden Markov Map Matching Optimization Algorithm Considering Vehicle Information

Teng Zhijun1 Huangfu Zenan2 Wang Anchen2

（1. Northeast Electric Power University Key Laboratory of Modern Power System Simulation and Control amp; Renewable Energy Technology， Ministry of Education， Jilin 132012; 2. School of Electrical Engineering， Northeast Electric Power University， Jilin 132012）

【Abstract】The signal transmission is obscured when vehicles are matched in elevated areas， and navigation is prone to mismatching， increased output latency and lane drift， etc.. To address such navigation defects， this paper proposes the hidden Markov map matching optimization algorithm with vehicle information. The algorithm eliminates redundant and drifting localization points in the sampled data; generates a grid index when determining the candidate roads， and uses the road topology to delete unconnected roads to reduce the computation and output delay; generates a confidence function using the road and vehicle information， and improves the transfer probability by fusing the speed similarity to determine the matching road sections. The experimental results show that the matching time is shorter when the vehicle drives to the elevated area， and the duration does not increase with the increase of road sections; and it has a high accuracy rate to meet the matching demand of vehicles in the 3D area.

Key words： Urban road network， Hidden Markov model， Map matching， Vehicle information

【引用格式】 滕志軍， 皇甫澤南， 王安晨. 計及車輛信息的隱馬爾可夫地圖匹配優(yōu)化算法[J]. 汽車技術(shù)， 202X（XX）： XX-XX.

TENG Z J， HUANGFU Z N， WANG A C. Hidden Markov Map Matching Optimization Algorithm Considering Vehicle Information[J]. Automobile Technology， 202X（XX）： XX-XX.

1 前言

為更好地將云計算、大數(shù)據(jù)和區(qū)塊鏈等先進(jìn)技術(shù)與傳統(tǒng)交通導(dǎo)航相融合，需融合大量衛(wèi)星定位信息和城市地理信息來確定車輛位置從而做出路徑規(guī)劃[1-5]。由于大氣層或高樓林立的城市峽谷地區(qū)會影響衛(wèi)星信號傳輸，使車輛位置出現(xiàn)偏離，此時需要通過地圖匹配技術(shù)將車輛定位信息與道路交通網(wǎng)結(jié)合后的軌跡點匹配至正確的道路上。

現(xiàn)有的地圖匹配算法主要分為4種：幾何匹配算法、拓?fù)淦ヅ渌惴ā⒏怕势ヅ渌惴ê透呒壠ヅ渌惴?。幾何匹配算法[6-7]采取定位點與路網(wǎng)之間的幾何關(guān)系，通常是點到線之間的算法，計算方式較為簡單。拓?fù)淦ヅ渌惴╗8]利用車輛行駛信息和城市道路拓?fù)涮卣鱽砑s束定位點的候選匹配。概率匹配算法[9-10]賦予定位點一個定位誤差區(qū)域，將此范圍內(nèi)的道路視為候選匹配路段，根據(jù)定位點與待匹配道路之間的距離分配概率值，將其概率最高的路段視為匹配路段。高級匹配算法[11-16]綜合考慮道路全部信息，結(jié)合路網(wǎng)拓?fù)浜透怕蔬\算，采用較精致的數(shù)學(xué)模型如卡爾曼濾波、模糊邏輯模型和隱馬爾可夫模型等進(jìn)行推算。

修建高架橋不僅避免了道路平面交叉也可以起到疏散交通的作用，但使得城市電子道路愈加復(fù)雜。三維空間中不同高度的道路映射在二維平面時，多條道路會交織在一起，采樣點在誤差區(qū)域內(nèi)待匹配路段數(shù)量急劇增加，影響實時匹配的輸出效率。現(xiàn)有匹配算法對車輛在高架橋行駛的研究較少。文獻(xiàn)[9]利用出租車載客量、乘客狀態(tài)等數(shù)據(jù)，結(jié)合車輛駕駛速度與駕駛習(xí)慣，通過模糊推理理論推斷車輛是否行駛在高架橋上。文獻(xiàn)[12]利用手機(jī)傳感器來監(jiān)測車輛瞬時動態(tài)，結(jié)合隱馬爾科夫地圖匹配（Hidden Markov Map matching，HMM）模型來描述車輛行駛過程中高程動態(tài)變化來判斷車輛行駛位置。文獻(xiàn)[13]對傳統(tǒng)的證據(jù)理論（Dempster/Shafer，D-S）進(jìn)行改進(jìn)，對位置信息證據(jù)及方向信息證據(jù)融合后的聯(lián)合支持度函數(shù)添加了高程信息用以判斷車輛是否上高架。

本文對傳統(tǒng)隱馬爾可夫模型進(jìn)行優(yōu)化，提出考慮車輛信息的隱馬爾可夫地圖匹配（Vehicle Information based Hidden Markov Map matching，VIHMM）算法。優(yōu)化算法充分考慮高程和速度等車輛信息，提高匹配算法在帶有高程信息的特殊路段匹配性能。

2 路網(wǎng)匹配問題描述

地圖匹配的關(guān)鍵問題是對于未加工的定位數(shù)據(jù)O和道路交通網(wǎng)，如何在定位數(shù)據(jù)所建議的道路和實際道路之間的可行性進(jìn)行權(quán)衡。位置數(shù)據(jù)作為道路的唯一指示物是很重要的，但將每個定位點與距離最近的道路進(jìn)行匹配會導(dǎo)致極其不合理的道路，包括奇怪的循環(huán)駕駛和整體怪異的駕駛行為。

高架與立交橋大多修建于城市重要的道路交匯處，道路網(wǎng)密集，地理因素和電子地圖精度兩方面的原因會造成數(shù)據(jù)接收誤差。在使用地圖進(jìn)行可視化時，定位點并不能準(zhǔn)確地反映用戶所處的真實地理位置，因此使用地圖匹配技術(shù)準(zhǔn)確找到定位點所處道路的具體位置。圖1為地圖匹配問題描述，定位點獲取的GPS軌跡數(shù)據(jù)為（p1，p2，p3，p4，p5）。在復(fù)雜的高架交通網(wǎng)中，候選路段較多且高架與地面高度差較大，圖1中，軌跡點p3和p4為高架與地面重疊路段，若按照傳統(tǒng)距離因素進(jìn)行簡單匹配而不考慮高程問題，較易發(fā)生匹配錯誤。

3 基于HMM的地圖匹配

在基于HMM的路網(wǎng)匹配算法中，HMM模型通過對道路的不可觀察狀態(tài)和車輛可觀察狀態(tài)進(jìn)行建模，考慮車輛誤差區(qū)域內(nèi)相連接的道路解決路網(wǎng)匹配問題。假設(shè)車輛在路網(wǎng)中行駛，且行駛的動作滿足馬爾可夫模型的要求，在算法運行過程中，對于每一個定位采樣點，首先根據(jù)定位方差值確定定位誤差范圍，在誤差范圍內(nèi)確定候選路段，每條候選路段都不會距離匹配點過遠(yuǎn)，均具備匹配的可能性，由定位點的運動軌跡反推出車輛實際所經(jīng)過的道路，此時這些道路稱為馬爾可夫鏈中的隱含狀態(tài)，定位采樣點與路段的匹配概率稱為觀測概率。若發(fā)現(xiàn)采樣點與某條路段相距較近，則給定這條路段一個較高的匹配值。然后，計算車輛在兩個時間段，在兩條候選路段之間移動的概率，即狀態(tài)轉(zhuǎn)移概率。最后，在馬爾可夫鏈上找到具有最高觀測概率和狀態(tài)轉(zhuǎn)移概率的車輛行駛最優(yōu)路徑。通常采用維特比算法（Viterbi algorithm）進(jìn)行數(shù)學(xué)分析，分析出一個實時數(shù)學(xué)演算法在道路網(wǎng)絡(luò)中快速找到觀測概率和轉(zhuǎn)移概率乘積最大的道路。

觀測概率通常可描述為矩陣A，A=[a]N×M，其中a=P（O[|]L）表示車輛處于道路L時可觀測到定位數(shù)據(jù)O的概率。

[A=a11…a1M???aN1…aNM] （1）

式中：N為采樣點的時間個數(shù)，M為采樣點的個數(shù)。

轉(zhuǎn)移概率通常可描述為矩陣B；B=[bij]N×M，其中b=P（Lj[|]Li）表示車輛在道路Li的情況下轉(zhuǎn)移到道路Lj的概率。

[B=b11…b1N???bN1…bNN] （2）

本文在Newson提出地圖匹配算法[15]的基礎(chǔ)上展開進(jìn)一步改進(jìn)。Newson算法中以距離為評判標(biāo)準(zhǔn)，認(rèn)為距離匹配點較遠(yuǎn)的路段不易匹配，正確的匹配會導(dǎo)致極短的行駛路線，因此使用候選路段間的最短路徑距離計算轉(zhuǎn)移概率，路線距離越短，轉(zhuǎn)移概率越大。該算法中，由于未對冗余道路進(jìn)行處理，導(dǎo)致候選路段較多，在匹配過程中最短路徑距離的計算量較大且最優(yōu)路徑的計算包含了車輛附近的所有道路，導(dǎo)致其匹配輸出有一定的延時，且該算法以傳統(tǒng)二維地理信息為基礎(chǔ)的匹配方法，未對高架橋、立交橋等立體化復(fù)雜路況進(jìn)行處理，不進(jìn)行改進(jìn)，僅利用二維信息在復(fù)雜路況顯然不能準(zhǔn)確推斷出車輛的準(zhǔn)確位置；另一方面，該檢索算法基于定位點至候選路段的距離建立高斯分布計算觀測概率，未考慮行駛航向與路段方向的相似性，對實時交通狀況不敏感。

針對上述2個問題，本文首先進(jìn)行數(shù)據(jù)預(yù)處理，剔除多余道路減少轉(zhuǎn)移概率的計算量，縮短匹配結(jié)果的輸出延遲，提高算法的時間效率，在觀測概率的計算中同時考慮距離因素和方向因素，提高了算法的準(zhǔn)確性。在轉(zhuǎn)移概率中加入高程信息，提高算法增強(qiáng)算法在高架、城市立交區(qū)域的匹配準(zhǔn)確率。

4 地圖匹配算法實現(xiàn)

本文提出的算法主要包括3部分：數(shù)據(jù)預(yù)處理、獲取候選路段集及地圖匹配。算法主要流程如圖2所示。數(shù)據(jù)預(yù)處理主要包括建立有向地圖、生成網(wǎng)格索引和剔除定位異常點，獲取候選路段集。地圖匹配主要包括計算觀測概率、計算轉(zhuǎn)移概率、最終通過維特比算法求解出輸出最優(yōu)路徑。

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

當(dāng)車輛行駛在擁擠路段時車速較為緩慢，相同路段會出現(xiàn)重復(fù)定位，算法中會計算兩定位點之間的距離，若兩點間的距離小于剔除閾值時，應(yīng)當(dāng)對定位點前后時間段的定位點進(jìn)行刪除。當(dāng)車輛行駛至隧道、高架橋和人口稠密的城市峽谷建筑群時，定位信號遭受阻攔準(zhǔn)確率降低，信號反射引起多徑效應(yīng)，導(dǎo)致信號延時增大、數(shù)據(jù)缺失，接收機(jī)獲取的定位點產(chǎn)生瞬時漂移。因此為提高地圖匹配性能，對GPS采樣點進(jìn)行預(yù)處理，去除異常點并彌補(bǔ)缺失的定位點，剔除原理如圖3所示。

由于進(jìn)行地圖匹配的車輛均處于運行狀態(tài)且市區(qū)道路行駛速度通常限速為60 km/h，因此將汽車的行駛速度設(shè)定為10 km/h～60 km/h。車載導(dǎo)航系統(tǒng)通常要求地圖匹配后的定位誤差在95%的時間內(nèi)不超過20 m，因此以定位點為中心設(shè)定半徑K=20 m的緩沖區(qū)，緩沖區(qū)外的定位點為漂移點，可直接剔除；在緩沖區(qū)內(nèi)，可能存在較短路徑里重復(fù)定位，利用車輛行駛速度設(shè)定一個距離閾值來剔除冗余點，距離閾值公式為：

[k=v×Δt+vs×Δt] （3）

式中：v為車輛實時行駛速度；Δt為前后定位點的時間間隔；vs為實時速度誤差。

4.2 獲取候選路段集

基于網(wǎng)格索引確定軌跡點所處的區(qū)域中，根據(jù)定位點的誤差方差確定候選路段集的范圍大小。一般選用誤差橢圓來篩選候選路段。誤差橢圓公式為：

[a=σ012（σ2X+σ2Y）+σ2X-σ2Y+4σ2XY] （4）

[b=σ012（σ2X-σ2Y）+σ2X-σ2Y+4σ2XY] （5）

[φ=π2-12arctan（2σXYσ2X-σ2Y）] （6）

式中：a、b分別為橢圓長、短半軸，σX和σY分別為定位點經(jīng)度和緯度的標(biāo)準(zhǔn)差，σXY為協(xié)方差，φ為橢圓長半軸與正北方向的夾角，σ0為可調(diào)因子。

從上述誤差橢圓的推導(dǎo)公式中可以看出長短軸公式較為復(fù)雜難以計算，為減少匹配時間可以將橢圓簡化為圓，將橢圓的中心與圓心重合，誤差圓的半徑為：

[R=σ012（σ2X+σ2Y）+σ2X-σ2Y+4σ2XY] （7）

確定檢索區(qū)域后，檢索區(qū)域內(nèi)的道路包含車輛正在行駛的道路和將要行駛的候選道路，隨著道路網(wǎng)的密集程度加大，該集合內(nèi)的道路條數(shù)可能較多，逐一計算會消耗大量的匹配冗余時間。為提高匹配時效，本文提出考慮道路拓?fù)浣Y(jié)構(gòu)剔除不相連道路的策略。如圖4所示，在誤差區(qū)域內(nèi)提取到的全部候選道路集合為L1、L2、L3、L4和L5。點O為軌跡點，對于該點距離R范圍內(nèi)的路段有L2、L3、L4、L5 4條路段，并將軌跡點在可能路段做投影，得到投影點M1、M2、M3、M4。假設(shè)車輛正在道路L2上行駛，考慮道路的拓?fù)浣Y(jié)構(gòu)、道路連通性以及車輛的行駛方向，與道路L2相連的有道路L3、L4，車輛下一時刻不可能出現(xiàn)在道路L5上，故將路段L1、L5剔除。最終得到點O的候選路段為L2、L3、L4，候選點為M1、M2、M3。節(jié)省大量的道路檢索時間，提高匹配的時效性。

4.3 地圖匹配實現(xiàn)

4.3.1 觀測概率

觀測概率即位于某條道路（隱含狀態(tài)）觀測到定位樣本點的概率。本文中觀測概率的推算主要由2個因素構(gòu)成，算式中綜合考慮距離和方向因素對匹配精確度的影響。

Newson等認(rèn)為觀測到的軌跡點符合標(biāo)準(zhǔn)高斯分布，可以使用高斯函數(shù)來表達(dá)距離因素的觀測概率，相對應(yīng)的計算公式為：

[Pd（Oi|Li）=12πσe-oi-Li22σ2] （8）

式中：σ為GPS的誤差的標(biāo)準(zhǔn)差，本文取值為4 m，在定位誤差的合理區(qū)間內(nèi)；‖Oi-Li‖為從軌跡點至候選路段的直線距離。

由于交通網(wǎng)絡(luò)是一個有向圖，匹配過程中易受到噪聲的影響。將距離因素作為參考的唯一依據(jù)可能會造成怪異的駕駛路線，且方向發(fā)生變化意味著車輛正在改變其正在行駛的道路。通常，兩相鄰時刻定位點匹配至同一路段的概率高于分別匹配到兩條路段的概率，因此汽車的行駛方向與路段的方向通常是一致的，車輛行駛方向與候選路段的夾角越小，則定位點與該路段匹配的可能性越大。方向因素的計算公式為：

[Pθ（Oi|Li）=θOi，Oi+1θLi.，Li+1] （9）

式中：[θOi，Oi+1]為相鄰定位點與北向夾角，[θLi.，Li+1]為相鄰時刻候選道路夾角與北向夾角。

綜合距離因素與方向權(quán)重因子，觀測概率的計算為：

[p（Oi|Li）=pd（Oi|Li）pθ（Oi|Li）] （10）

4.3.2 基于車輛信息的轉(zhuǎn)移概率

在面對高架橋或立交橋入口時，不可避免地會出現(xiàn)交叉路口或平行路口等復(fù)雜路況，由于GPS定位的誤差，二維信息的匹配算法難以在數(shù)字地圖中準(zhǔn)確修正車輛位置信息，無法確定車輛是否上下橋從而造成車輛導(dǎo)航路線錯誤。本文在隱馬爾可夫模型的基礎(chǔ)上進(jìn)行改進(jìn)，在城市高架區(qū)域進(jìn)行試驗，解決在高架橋或立交橋入口路網(wǎng)上行駛車輛的定位問題，提高匹配準(zhǔn)確率，使算法更好地適應(yīng)復(fù)雜路網(wǎng)環(huán)境。

以高架橋入口為例，假設(shè)車輛在當(dāng)前時刻正在上橋的過程中，通過車輛設(shè)備監(jiān)測到車輛的行駛信息，利用速度、經(jīng)緯度等值計算坡度值，具體公式如下：

[D=ti-1tiv（t）dt] （11）

式中：D為車輛行駛的總路程，[v]為[ti-1]至[ti]時刻的平均速度。

車輛在[ti-1]至[ti]時刻中車輛高程信息變化情況為：

[H=111.12cos1/sinlati-1sinlati+" " " " coslati-1coslaticos（loni-loni-1）] （12）

式中：lon、lat分別為車輛的經(jīng)緯度信息。

[ψ=arccosHD] （13）

[I=tanψ] （14）

式中：[ψ]為運用反三角函數(shù)計算出的車輛行駛道路的夾角，I為道路的坡度值。

在計算出坡度的前提下構(gòu)建出車輛在路段Li行駛的高程信息支持度：

[PI（Li→Lj）=Iii=1nIi] （15）

式中：n為采樣點個數(shù)。

由于立交橋入口處道路狀況復(fù)雜，存在許多與立交橋上下平行的道路，為了降低在緊密相連的平行路段中因測量不足引起的誤差，在出入口處引入速度相似性。通常認(rèn)為車輛行駛速度不會超過道路最高限速，且當(dāng)車輛行駛至出入口時速度相較于直行路段會有所降低，采取速度相似性可以最大限度區(qū)分從同一路口分叉出的可能具有不同速度限制的緊密間隔的平行道路。速度相似性表示為：

[Svti，ti-1=vlim+（vi-1-vi）vlim] （16）

式中：[vlim]為道路限速標(biāo)準(zhǔn)；[（vi-1-vi）]為車輛在[ti-1]至[ti]時刻的速度；若[Svtgt;1]，車輛大概率行駛在高架出入口或進(jìn)行變道，若[Svt≤1]，車輛可能行駛在直線道路上。

綜合高程信息和速度相似性，對轉(zhuǎn)移概率進(jìn)行優(yōu)化，使其在面對不同路段時可以有更好的匹配性能。本文算法的轉(zhuǎn)移概率為：

[P（Lj|Li）=ω11βe-dtβ×ω2Svti，ti-1P（Lj|Li）×ω3Iii=1nIi]" "（17）

式中：ω1、ω2、ω3為權(quán)重參數(shù)；[dt=Oi-Oi+1dist-Li-Li+1s]；[β]為魯棒性估計函數(shù)[，β=1ln（2）median（Oi-Oi+1dist-Li-Li+1s）]，其中[Oi-Oi+1dist]為兩個定位點的直線距離，[Li-Li+1s]為定位點到達(dá)下一時刻定位點匹配道路的路程。

5 仿真分析

5.1 實測論證

本文試驗數(shù)據(jù)是由Bigemap GIS軟件直接采集到的車輛所處位置的經(jīng)緯度、高度信息和車輛的瞬時速度。路網(wǎng)數(shù)據(jù)為某市的道路交通網(wǎng)，路網(wǎng)包括普通路段、高架路、橋梁道路等8條路段，接收到5 000個行車軌跡點，采樣間隔為15～20 s，將收集的異常GPS數(shù)據(jù)進(jìn)行剔除，在平行路段與高架路出入口環(huán)境下進(jìn)行測試。圖5為本文算法在高架快速干道入口的匹配圖，采樣點可以準(zhǔn)確地匹配到車輛行駛路線上。

5.2 根據(jù)不同路段設(shè)定權(quán)重參數(shù)

本文選取Paul Newson和John Krumm論文公開的數(shù)據(jù)集[15]中6車道平行路段進(jìn)行模擬測試，用正確匹配的定位點數(shù)與獲得的總定位點數(shù)的比值來衡量算法的準(zhǔn)確率。仿真驗證結(jié)果如圖6所示，當(dāng)ω1=0.9、ω2=0.8、ω3=0.85時準(zhǔn)確率最高。

車輛駛?cè)虢徊媛房跁r，對候選路段進(jìn)行特征分析，由于候選路段密集且方向差別較大，故相對于考慮位置信息，方向信息的可靠性更高。選取路網(wǎng)中多個交叉路段作為試驗點對改進(jìn)后的匹配算法進(jìn)行了仿真。仿真結(jié)果如圖7所示，當(dāng)ω1=0.93、ω2=0.95、ω3=0.85時準(zhǔn)確率最高。

汽車行駛至類似高架橋入口的分岔較多的路段時，其匹配過程十分復(fù)雜，此時的定位點很有可能位于多個路段之間。此種情況類似于交叉路口，但此時道路存在三維信息，因此應(yīng)當(dāng)著重參考車輛行駛路段與周圍候選路段的高程信息支持度。仿真結(jié)果如圖8所示，當(dāng)ω1=0.95、ω2=0.9、ω3=0.95時準(zhǔn)確率最高。

5.3 不同候選路段匹配時間分析

選取了3種匹配算法與本文算法（VIHMM）進(jìn)行對比：

a. 時間空間匹配算法（Space Time Map Matching，ST-Matching）。該算法結(jié)合時間和空間特征，將觀測概率使用正態(tài)分布進(jìn)行模擬，轉(zhuǎn)移概率中添加了車輛速度信息。該算法將GPS點匹配到距離較近的路段上，不考慮相鄰點的關(guān)系。

b. 互交式投票匹配算法（Interactive Voting Map Matching，IVMM）。觀測概率和轉(zhuǎn)移概率與ST-Matching算法相同，IVMM算法從全局角度考慮觀測點之間的相關(guān)性。該算法對候選點匹配路段的其他候選點進(jìn)行投票，將得分最高的候選點連接起來形成匹配路徑。

c. 隱馬爾可夫算法（Hidden Markov Map matching，HMM）。與ST-Matching算法相近，但該算法未引入車輛航向數(shù)據(jù)，是用相鄰時間段兩個采樣點的距離與采樣點的行駛距離只差表示路線的接近程度，越接近，概率就越大。

對車輛行駛至不同數(shù)量候選道路的匹配時間進(jìn)行對比，圖9～圖12為匹配時間對比。匹配時間為接收機(jī)獲取定位信息至找出車輛行駛道路后進(jìn)行垂直投影所需平均時間。由圖中可以看出，在候選區(qū)域內(nèi)存在4條候選道路時，本文算法單點匹配時間約為4.45 ms；當(dāng)汽車行駛至道路密集區(qū)時，隨著候選道路數(shù)量增加，其它算法的匹配時間大幅增加，因本文算法使用拓?fù)湓硖蕹硕嘤嗦窂?，從而匹配時間增幅較少，即使候選區(qū)域道路增加至7條，本文算法單點匹配時間仍穩(wěn)定保持在5.5 ms的輸出時延，而其它比較算法均在6 ms以上，因此本文算法在復(fù)雜道路下仍具有較突出的時效性。

6 不同路況下匹配準(zhǔn)確率對比分析

圖13為4種地圖匹配算法在不同路況下匹配準(zhǔn)確率對比。當(dāng)車輛行駛在二維平行路段時，因行駛中視野開闊且有準(zhǔn)確的定位，4種算法均有較好的表現(xiàn)，匹配準(zhǔn)確率均達(dá)到94%以上。由于本文在確認(rèn)匹配道路時添加了速度相似性，可以較好區(qū)分緊密間隔的平行道路，故本文算法略高；當(dāng)車輛行駛在高架入口時，候選路段可能出現(xiàn)重疊、交織等情況，匹配時易誤匹配從而導(dǎo)致其余3種匹配算法準(zhǔn)確率均有所下降，本文算法VIHMM在基于高程信息的前提下對模型進(jìn)行改進(jìn)，相較于其他算法匹配準(zhǔn)確率存在一定優(yōu)勢；車輛在復(fù)雜路口易引發(fā)誤匹配、不匹配、匹配精度低等問題，這4種算法面對復(fù)雜路況準(zhǔn)確率均表現(xiàn)出不同程度的下降，本文算法相較其余算法，充分考慮了車輛信息中的距離、方向和速度等因素，故在復(fù)雜路口處也保持了較高的準(zhǔn)確率。

7 結(jié)束語

本文針對車輛在高架入口處誤匹配問題，基于車輛的行駛信息提出HMM模型改進(jìn)算法。首先刪除漂移和冗余定位點；處理候選道路集時引入網(wǎng)格索引，將車輛軌跡分割，剔除冗余路段，減少輸出時延，提高匹配時效；使用最短路徑和方向信息確定觀測概率，引用可信度函數(shù)和速度相似性改進(jìn)轉(zhuǎn)移概率，最終確定匹配路段。利用實測數(shù)據(jù)對算法性能進(jìn)行驗證，該算法能更好區(qū)分車輛是否在高架行駛且在高架、立交橋入口等道路密集區(qū)域提高了匹配的準(zhǔn)確性并縮短匹配時間，與其他算法相比匹配精度和匹配速率更優(yōu)。

參 考 文 獻(xiàn)

[1] FAN J C， FU C， KATHLEEN Stewart， et al. Using Big GPS trajectory Data Analytics for Vehicle Miles Traveled Estimation[J]. Transportation Research Part C， 2019， 103（1）： 298-307.

[2] 畢達(dá)天， 馬卓， 劉健. 用戶參與視角下移動社交網(wǎng)絡(luò)互動特征及模式研究[J]. 情報理論與實踐， 2016， 39（9）： 90-95.

BI D T， MA Z， LIU J. Research on Interactive Characteristics and Patterns of Mobile Social Networks from the Perspective of User Participation [J]. Intelligence Theory and Practice， 2016， 39（9）： 90-95.

[3] 甄峰， 席廣亮， 秦蕭. 基于地理視角的智慧城市規(guī)劃與建設(shè)的理論思考[J]. 地理科學(xué)進(jìn)展， 2015， 34（4）： 402-409.

ZHEN F， XI G L， QIN X. Theoretical Reflections on Smart City Planning and Construction from A Geographic Perspective [J]. Advances in Geographic Science， 2015， 34（4）： 402-409.

[4] 高文超， 李國良， 塔娜. 路網(wǎng)匹配算法綜述[J]. 軟件學(xué)報， 2018， 29（2）： 225-250.

GAO W C， LI G L， TA N. Overview of Road Network Matching Algorithms [J]. Journal of Software， 2018， 29（2）： 225-250.

[5] 陳柯勛， 張雪英， 邱偉. 一種改進(jìn)的GNSS接收機(jī)完好性監(jiān)測算法[J]." 哈爾濱理工大學(xué)學(xué)報， 2021， 26（3）： 103-107.

CHEN K X， ZHANG X Y， QIU Wiu Wei. An Improved GNSS Receiver Integrity Monitoring Algorithm[J]. Journal of Harbin Institute of Technology， 2021， 26（3）： 103-107.

[6] 陳菲， 鄒濤， 王倫. 改進(jìn)的基于投影的地圖匹配算法[J]. 計算機(jī)工程與應(yīng)用， 2011， 47（31）： 242-244+248.

CHEN F， ZOU T， WANG L. Improved Projection based Map Matching Algorithm[J]. Computer Engineering and Applications， 2011， 47（31）： 242-244+248.

[7] 劉峰， 郭陽， 鄭辛， 等. 基于道路幾何特征的地圖匹配方法研究[J]. 導(dǎo)航定位與授時， 2020， 7（1）： 67-72.

LIU F， GUO Y， ZHENG X， et al. Research on Map Matching Method Based on Geometric Features of Roads[J]. Navigation and Timing， 2020， 7（1）： 67-72.

[8] 謝金運， 涂偉， 李清泉. 大規(guī)模浮動車流數(shù)據(jù)并行地圖匹配方法[J]. 武漢大學(xué)學(xué)報（信息科學(xué)版）， 2017， 42（5）： 697-703.

XIE J Y， TU W， LI Q Q. Parallel Map Matching Method for Large-Scale Floating Traffic Data[J]. Journal of Wuhan University （Information Science Edition）， 2017， 42（5）： 697-703.

[9] 李昊天， 張宇. 改進(jìn)的D-S證據(jù)推理地圖匹配算法[J]. 東北電力大學(xué)學(xué)報， 2020， 40（1）： 90-96.

LI H T， ZHANG Y. Improved D-S Evidence Reasoning Map Matching Algorithm[J]. Journal of Northeast Electric Power University， 2020， 40（1）： 90-96.

[10] ZHAO C， SHE X W， ZHUANG L J， et al. Online Map-Matching Framework for Floating Card Data with Low Sampling Rate in Urban Road Networks[J]. IET Intelligent Transport Systems， 2013， 7（4）： 404-414.

[11] 傅琛， 黃升鈳， 湯焱， 等. 結(jié)合行駛場景語義的軌跡-路網(wǎng)實時匹配方法[J].測繪學(xué)報， 2021， 50（11）： 1617-1627.

FU C， HUANG S K， TANG Y， et al. Real Time Trajectory Road Network Matching Method Combining Driving Scene Semantics[J]. Journal of Surveying and Mapping， 2021， 50（11）： 1617-1627.

[12] 龔垚明. 基于智能手機(jī)的高架路檢測關(guān)鍵技術(shù)研究[D]. 上海： 上海交通大學(xué)， 2016.

GONG Y M. Research on Key Technologies for Elevated Road Detection Based on Smartphones[D]. Shanghai： Shanghai Jiao Tong University， 2016.

[13] 肖維麗， 岳春生， 奚玲. 基于高程的改進(jìn)D-S證據(jù)理論地圖匹配算法[J]. 計算機(jī)應(yīng)用與軟件， 2015， 32（7）： 262-265.

XIAO W L， YUE C S， XI L. Improved D-S Evidence Theory Map Matching Algorithm Based on Elevation[J]. Computer Applications and Software， 2015， 32（7）： 262-265.

[14] QI H， DI X， LI J. Map-Matching Algorithm Based on the Junction Decision Domain and the Hidden Markov Model[J]. PloS one， 2019， 14（5）： 0216476.

[15] NEWSON P， KRUMM J. Hidden Markov Map Matching Through Noise and Sparseness[C]. Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems， Seattle： SIGSPATIAL， 2009.

[16] 劉彪， 王恒陽， 宋昱鵬， 等. 高速公路場景下車輛變道行為探究[J]. 哈爾濱理工大學(xué)學(xué)報， 2022（6）： 13-23.

LIU B， WANG H Y， SONG Y P， et al. Exploration of Vehicle Lane Changing Behavior in Highway Scenarios[J]. Journal of Harbin Institute of Technology， 2022（6）： 13-23.

[17] 劉旻， 李梅， 徐曉宇， 等. 一種基于HMM模型改進(jìn)的地圖匹配算法[J]. 北京大學(xué)學(xué)報（自然科學(xué)版）， 2018， 54（6）： 1235-1241.

LIU M， LI M， XV X Y， et al. A Map Matching Algorithm Improved Based on HMM Model[J]. Journal of Peking University （Natural Science Edition）， 2018， 54（6）： 1235-1241.

[18] 滕志軍， 李昊天， 張宇， 等. 動態(tài)距離權(quán)重因子的隱馬爾可夫模型地圖匹配算法[J]. 河南科技大學(xué)學(xué)報（自然科學(xué)版）， 2020， 41（4）： 40-45+6-7.

TENG Z J， LL H T， ZHANG Y， et al. Hidden Markov Model Map Matching Algorithm with Dynamic Distance Weight Factors [J]. Journal of Henan University of Science and Technology （Natural Science Edition）， 2020， 41（4）： 40-45+6-7.

[19] 王秋惠. 基于空間自回歸模型的電力系統(tǒng)中長期負(fù)荷特性分析與預(yù)測[J]. 東北電力大學(xué)學(xué)報， 2021， 41（3）： 118-123.

WANG Q H. Analysis and Prediction of Medium - and Long Term Load Characteristics in Power Systems Based on Spatial Autoregressive Model[J]. Journal of Northeast Electric Power University， 2021， 41（3）： 118-123.

（責(zé)任編輯 王 一）

修改稿收到日期為2023年5月23日。