基于哈希和路網(wǎng)邊權(quán)的地圖匹配算法及其應(yīng)用

邵天浩，張宏軍，程 愷，唐新德，莫 斐，張 可

(陸軍工程大學(xué) 指揮控制工程學(xué)院，江蘇 南京 210000)

0 引 言

近年來，隨著車載導(dǎo)航的普及率越來越高，海量的車輛行駛數(shù)據(jù)被導(dǎo)航收集并上傳至車聯(lián)網(wǎng)系統(tǒng)。這些數(shù)據(jù)可以體現(xiàn)車輛在行駛過程中的各種信息，如經(jīng)緯度、方位角、GPS速度、行駛里程等。如何從海量的行駛數(shù)據(jù)中分析出車輛駕駛行為的特征，將數(shù)據(jù)轉(zhuǎn)化為價值，是當(dāng)前研究的一個熱點問題[1-2]。但是由于車載導(dǎo)航自身的局限性以及數(shù)據(jù)采集的不穩(wěn)定性，采集到的行駛數(shù)據(jù)往往質(zhì)量不高，這會導(dǎo)致其分析出的結(jié)果與實際情況有所偏差。因此，對車輛行駛數(shù)據(jù)進行有效的預(yù)處理以提高其質(zhì)量，是后續(xù)數(shù)據(jù)分析的重要前提。

通過地圖匹配來修正車輛行駛數(shù)據(jù)是如今最常用的方法，目前地圖匹配算法主要有確定性地圖匹配算法和不確定性地圖匹配算法兩種[3]。

確定性地圖匹配算法是指匹配的結(jié)果是確定而非隨機的，主要通過幾何方式進行匹配，包括點到點、點到弧、弧到弧三種方式[4]。它考慮了車輛方位角與道路方向的相似性、采樣點與道路的距離以及車輛行駛速度等多個方面，將各要素加權(quán)之后選擇最合適的匹配路段。這類算法原理簡單，實現(xiàn)容易，但其穩(wěn)定性不高，尤其是在選擇初始匹配路段時沒有進行初步篩選[5]，導(dǎo)致匹配的精度下降。

不確定性地圖匹配算法是指相同數(shù)據(jù)點多次匹配的結(jié)果是非確定的，依據(jù)一定概率進行匹配，主要分為概率統(tǒng)計算法和模糊邏輯算法兩種。概率統(tǒng)計算法主要依據(jù)采樣點信息設(shè)置置信區(qū)域，利用概率準(zhǔn)則來確定需要搜索的道路閾值，在匹配過程中需要通過復(fù)雜的數(shù)學(xué)公式來推導(dǎo)定位誤差橢圓，這一方法雖然有較高的匹配精度，但大量的推導(dǎo)使其匹配速度下降[3]。模糊邏輯算法與傳統(tǒng)的模糊推理系統(tǒng)類似，通過模糊化、模糊推理機和去模糊化三個部分搭配隸屬度函數(shù)在推理過程中進行道路匹配，這一算法的實現(xiàn)雖然較概率統(tǒng)計算法來說容易，但其模糊推理機中參數(shù)的設(shè)定主要依靠專家知識，缺少一定的推理支撐[6]。

總的來說，相對容易實現(xiàn)的匹配算法其匹配精度較低，匹配精度高的算法計算復(fù)雜，匹配速度較慢。同時，上述匹配算法均沒有提出存在大段異常點時的匹配模式。為了兼顧高效與匹配速度，文中在確定性地圖匹配算法的基礎(chǔ)上，提出了一種新型地圖匹配算法。首先將路網(wǎng)信息以鄰接表形式存儲，然后通過geohash函數(shù)來篩選數(shù)據(jù)點周圍的道路，并添加一個滑動窗口來減小匹配錯誤率，最后通過修正路網(wǎng)邊權(quán)來填充空白數(shù)據(jù)點。該算法實現(xiàn)簡單，較傳統(tǒng)的地圖匹配算法有更高的匹配精度，較概率統(tǒng)計算法和模糊邏輯算法有更快的匹配速度，并且在數(shù)據(jù)存在大段異常時也能很好工作，匹配結(jié)果提高了車輛行駛數(shù)據(jù)的質(zhì)量，可以推廣到車輛的實時定位。

1 算法的設(shè)計與實現(xiàn)

基于哈希函數(shù)與路網(wǎng)邊權(quán)修正的地圖匹配算法的具體流程如圖1所示[7]。

圖1 地圖匹配算法流程

主要包括剔除明顯異常點、路網(wǎng)信息的獲取與存儲、數(shù)據(jù)點與路網(wǎng)匹配、明顯異常點填充四個步驟，其中數(shù)據(jù)點與路網(wǎng)匹配、明顯異常點填充又包含相應(yīng)的子流程。下面分別闡述每個步驟及子流程的設(shè)計實現(xiàn)方法。

1.1 剔除明顯異常點

由于GPS信號有時候存在不穩(wěn)定性，車輛行駛數(shù)據(jù)中包含了大量的漂移數(shù)據(jù)，這些數(shù)據(jù)與正常的數(shù)據(jù)偏差很大，是明顯的異常點，首先需要對這樣的明顯異常點進行剔除。

信號漂移會導(dǎo)致最后一個正常的數(shù)據(jù)點和第一個異常的數(shù)據(jù)點之間有較大的經(jīng)緯度差異，可以根據(jù)這一差異對數(shù)據(jù)集中明顯的異常點進行剔除[8]。

已知地表上兩點的經(jīng)緯度，可以得出兩點間的最短距離De，如式(1)所示。

De=R·arccos(cosxbcosybcos(ya-xa)+

sinxbsinyb)

(1)

根據(jù)兩個數(shù)據(jù)點i、j采集到的經(jīng)緯度數(shù)據(jù)，可以求出兩個數(shù)據(jù)點之間的平均速度，并用平均速度代替后一個數(shù)據(jù)點的瞬時速度，如式(2)所示，其中De為兩數(shù)據(jù)點的經(jīng)緯度距離。

(2)

若某一數(shù)據(jù)點i的經(jīng)緯度速度與GPS速度滿足式(3)，則認(rèn)為其是正常數(shù)據(jù)點，否則將其剔除，選擇下一數(shù)據(jù)點繼續(xù)判斷。

VG<|Vi-VG|×30%

(3)

利用上述過程對明顯錯誤的異常點進行剔除的方式較為粗糙，會留下一些異常點沒有剔除干凈，但這種方法的好處是可以處理大段的連續(xù)異常數(shù)據(jù)，這是利用隱馬爾可夫模型[9]來進行預(yù)處理所不能達到的，因為過長的隱馬爾可夫鏈會失去預(yù)測的準(zhǔn)確性。未被剔除的不太明顯異常點可以通過道路匹配的方式來進行修正。同時，針對明顯異常點剔除之后的大片缺失數(shù)據(jù)，可以通過修正路網(wǎng)邊權(quán)來進行填補。

1.2 路網(wǎng)信息的獲取與存儲

想要將數(shù)據(jù)點與道路進行匹配，從而修正數(shù)據(jù)點的值，首先需要獲取路網(wǎng)信息，獲取的信息主要包括地圖上的每條道路和每個點，以及它們之間的內(nèi)在聯(lián)系。

將路網(wǎng)信息中的道路信息和交叉點信息進行提取，分別用ways道路和nodes點來表示，對兩者進行簡化，留下各自的唯一標(biāo)識id、經(jīng)緯度坐標(biāo)以及其關(guān)聯(lián)關(guān)系。最后用鄰接表來存儲化簡之后的信息，鄰接表中的頂點對應(yīng)nodes點，有向邊對應(yīng)兩個nodes點之間有一條單向的道路。

式(4)表示鄰接表存儲的數(shù)據(jù)結(jié)構(gòu)，其中id表示某一數(shù)據(jù)點的唯一標(biāo)識id，該數(shù)據(jù)點與附近n個數(shù)據(jù)點相鄰；idn表示與該數(shù)據(jù)點相鄰的第n個數(shù)據(jù)點；widn表示對應(yīng)兩數(shù)據(jù)點連接而成的道路的唯一標(biāo)識符id；dn表示對應(yīng)兩數(shù)據(jù)點之間的距離；an表示對應(yīng)兩數(shù)據(jù)點連接而成的道路的方位角，以正北方向為基準(zhǔn)線。

id:[id1,wid1,d1,a1;…;idn,widn,dn,an]

(4)

需要注意的是，在實際應(yīng)用中，為了減少搜索空間，會先確定車輛軌跡的經(jīng)緯度范圍矩陣，根據(jù)范圍矩陣來生成鄰接表，從而減少數(shù)據(jù)點匹配所用時間。

1.3 數(shù)據(jù)點與道路匹配

剔除了大部分異常點之后行駛數(shù)據(jù)在地圖上表示為多段行駛軌跡，每行駛軌跡之間缺失的數(shù)據(jù)即是被剔除掉的明顯異常點。需要將每段行駛數(shù)據(jù)進行更進一步的處理，使其具有一定的規(guī)律性，處理依據(jù)如下：

如果相鄰兩個數(shù)據(jù)點之間的采樣間隔超過2分鐘，則認(rèn)為兩者屬于不同的行駛段；如果某一段行駛段的起始點和終點的采樣間隔小于2分鐘，則拋棄這一行駛段。

對數(shù)據(jù)分段之后，可以將每個數(shù)據(jù)點與附近的道路進行匹配，并且修正數(shù)據(jù)點?？梢园凑杖缦虏襟E來完成，以每個數(shù)據(jù)點作為基本操作單位：

Step1：利用geohash函數(shù)求出每個數(shù)據(jù)點周圍的nodes點，并將找到的nodes點通過其與ways道路的關(guān)系連接成線段arc；

Step2：求出數(shù)據(jù)點與arc線段的距離distance和夾角angle，依據(jù)數(shù)據(jù)點的行駛速度對兩者進行加權(quán)，求出每個數(shù)據(jù)點與周圍arc線段的匹配值match；

Step3：依照一定的篩選規(guī)則，選出與每個數(shù)據(jù)點最匹配的arc線段，使其與上一數(shù)據(jù)點匹配的arc線段相連，并修正數(shù)據(jù)點的屬性值；

Step4：對下一個數(shù)據(jù)點計算Step1，直到該行駛段的數(shù)據(jù)點計算完為止。

其中Step1～Step3的具體實現(xiàn)過程如下。

1.3.1 篩選數(shù)據(jù)點周圍道路

由于數(shù)據(jù)點與路網(wǎng)信息的鄰接表之間沒有直接的關(guān)聯(lián)關(guān)系，因此，若需要尋找數(shù)據(jù)點周圍的nodes點是十分困難的，需要遍歷整個鄰接表，通過計算數(shù)據(jù)點與nodes點之間的距離來篩選符合條件的nodes點。雖然已經(jīng)通過范圍矩陣將鄰接表中的數(shù)據(jù)進行初選，但逐條計算的方式仍然要耗費大量時間，因此在尋找數(shù)據(jù)點周圍的nodes點時，文中利用了空間搜索算法中的geohash函數(shù)。

geohash函數(shù)的基本思想是將地球根據(jù)經(jīng)緯度看成一個二維平面，將二維的經(jīng)緯度轉(zhuǎn)換成字符串編碼[10]，例如，圖2展示了某一地區(qū)中9個區(qū)域的geohash編碼，每一個5位字符串編碼代表了一塊矩形區(qū)域。而不同的編碼長度表示不同的范圍區(qū)間，字符串越長，表示的范圍越精確。geohash的前5位編碼精度大約在2 km，文中使用的算法需要篩選每個點周圍500 m內(nèi)的nodes點，因此5位geohash編碼可以滿足條件。

圖2 geohash編碼示意圖

利用geohash函數(shù)求出每個nodes點的geohash值，通過字符串匹配的方式，尋找與數(shù)據(jù)點的geohash值前5位相同的nodes點。需要注意的是，雖然前5位geohash值匹配的精度在2 km，但如果數(shù)據(jù)點的位置靠近劃分矩形的邊緣，那么某些距離數(shù)據(jù)點500 m內(nèi)的nodes點也不在矩陣內(nèi)。因此，在經(jīng)過geohash函數(shù)計算之后，還需要基于nodes值對數(shù)據(jù)進行進一步拓展篩選。對于數(shù)據(jù)點所在矩陣內(nèi)的每個nodes點，拓展尋找其500 m范圍內(nèi)的nodes點，尋找的方法是基于給定Limit的深度優(yōu)先搜索。鄰接表的深度優(yōu)先搜索可以基于棧結(jié)構(gòu)快速進行，當(dāng)搜索深度大于500 m時即停止該分支的搜索進行回溯。這樣就對原有矩陣進行了拓展，保證了原本距離數(shù)據(jù)點500 m內(nèi)但不在矩陣內(nèi)的點也在拓展之后的nodes點內(nèi)。

最后，遍歷所有拓展后得到的nodes點，篩選出數(shù)據(jù)點500 m范圍內(nèi)的nodes點，并將其依據(jù)鄰接表的信息進行連接，得到基于ways數(shù)據(jù)的線段，將其稱為arc線段。

1.3.2 計算道路與數(shù)據(jù)點的匹配度

對于每一個數(shù)據(jù)點，已經(jīng)得到其周圍500 m范圍內(nèi)的arc線段，對數(shù)據(jù)點與arc線段之間的距離和夾角進行加權(quán)，計算數(shù)據(jù)點與每個arc線段的匹配值match，該值越大，說明數(shù)據(jù)點與道路越匹配。兩者的距離distance用點到線段的最小距離表示，夾角angle為點的方位角與線段的夾角，兩者的值越小，說明數(shù)據(jù)點與道路越匹配，匹配度應(yīng)該越高，因此它們之間有負(fù)相關(guān)的關(guān)系。

得到distance與angle之后，首先對其進行歸一化，然后利用式(5)計算數(shù)據(jù)點到每個arc線段的match值[11]：

match=1-[(1-λ)×distance+λ×angle]

(5)

其中，λ表示angle指標(biāo)的權(quán)重，λ的值與數(shù)據(jù)點的GPS速度有關(guān)：當(dāng)數(shù)據(jù)點的速度小于1 m/s時λ的值為0，速度大于10 m/s時λ的值為0.5，速度介于兩者之間時λ的值按線性從0到0.5增長[12]。假設(shè)distance指標(biāo)的權(quán)重永遠大于0.5，這是因為本文認(rèn)為距離指標(biāo)的重要性大于夾角指標(biāo)，因為數(shù)據(jù)點需要選擇更相鄰的道路進行匹配。

1.3.3 求最佳匹配道路

有了數(shù)據(jù)點與arc線段的匹配值match，就可以將兩者進行匹配，這一過程主要分為三步。

首先，根據(jù)distance對arc線段進行初選，依據(jù)為arc線段中“highway”屬性的值，選出距離數(shù)據(jù)點100 m內(nèi)的所有道路，距離數(shù)據(jù)點200 m內(nèi)的所有主要道路，距離數(shù)據(jù)點400 m內(nèi)的所有干線道路，距離數(shù)據(jù)點500 m內(nèi)的所有高速公路。

其次，將初選之后arc線段依m(xù)atch值從大到小排序，選擇match值最大的5條arc線段[13]，作為最終匹配的候選線段。若需要匹配的數(shù)據(jù)點為行駛段的起始點，則選擇match值最大的那條線段作為匹配的道路；若需要匹配的數(shù)據(jù)點為非起始點，需要判斷5條arc線段是否滿足以下兩個條件之一[14]：

(1)該arc線段與上一數(shù)據(jù)點匹配的線段是否重復(fù)；

(2)該arc線段與上一數(shù)據(jù)點匹配的線段是否相連。

若5條arc線段中存在某條線段滿足上述兩個條件之一，則認(rèn)為這條線段是與該數(shù)據(jù)點匹配的arc線段，將其與前一數(shù)據(jù)點匹配的arc線段相連，將其認(rèn)為是車輛的真實行駛軌跡。

若不存在arc線段滿足上述條件中的任意一個，則計算上一數(shù)據(jù)點匹配的arc線段尾端點到5條arc線段首端點的最短路徑，這一最短路徑并非直線最短，而是在鄰接表中通過可達邊的最短路徑。最終選擇最短路徑最小的arc線段作為該數(shù)據(jù)點匹配的arc線段，將前一數(shù)據(jù)點匹配的arc線段經(jīng)過最短路徑上的nodes點與其連接，將其認(rèn)為是車輛的真實行駛軌跡。

需要注意的是，這一方法的基本思想是貪婪的，即倘若在后期發(fā)現(xiàn)某條arc線段完全不符合要求，也無法改變前面的匹配結(jié)果。為了避免這種情況，文中在實際求解中利用一個滑動窗口，該窗口保留當(dāng)前匹配數(shù)據(jù)點前500 m里程內(nèi)所有數(shù)據(jù)點的5條最佳arc線段匹配列表，若發(fā)現(xiàn)當(dāng)前數(shù)據(jù)點的5條arc線段均無法匹配，則說明匹配出錯，應(yīng)該向前回溯至上個數(shù)據(jù)點，選擇下一條最合適的arc線段重新匹配。

完成數(shù)據(jù)點與附近的路網(wǎng)信息匹配之后，倘若數(shù)據(jù)點不在所匹配的道路上，則需要利用投影法[15]對數(shù)據(jù)點的經(jīng)緯度信息進行修正，將數(shù)據(jù)點在道路上的垂足(垂足在arc線段上)或道路中點(垂足不在arc線段上)作為修正的新數(shù)據(jù)點。

1.4 明顯異常點填充

1.3節(jié)將數(shù)據(jù)點與路網(wǎng)信息結(jié)合，通過路網(wǎng)信息對異常的數(shù)據(jù)點進行了有效的修正，但修正的數(shù)據(jù)點并不包含1.1節(jié)中被剔除的明顯異常的數(shù)據(jù)點，這使得修正完之后的數(shù)據(jù)存在大段缺失，導(dǎo)致在車輛行駛軌跡中存在一定的空白段。

為了填充各個行駛段之間的空白數(shù)據(jù)，文中提出通過修正路網(wǎng)邊權(quán)來尋找空白段之間最合適的填補路徑，尋找步驟如下：

Step1：尋找空白數(shù)據(jù)段可能經(jīng)過的nodes點以及nodes點連接成的ways道路；

Step2：按照“highway”屬性修改鄰接表中屬性“d”的值；

Step3：求出空白段之間的最佳路徑；

Step4：依據(jù)最佳路徑填充空白數(shù)據(jù)點。

Step1～Step4的實現(xiàn)過程如下：

在填充明顯異常點之前，首先選擇空白數(shù)據(jù)段前后兩段數(shù)據(jù)的尾部和頭部的nodes點，以前段數(shù)據(jù)尾部的nodes點為圓心，以1.3.1節(jié)中方法來尋找兩個nodes點之間距離1.5倍范圍內(nèi)的所有nodes點。將符合條件的所有nodes點仍然以鄰接表的形式存儲，但必須將兩點之間的經(jīng)緯度距離進行加權(quán)。

1.4.1 修改鄰接表“d”屬性

由于現(xiàn)實中公路的建設(shè)并非是兩點之間的最短路徑，因此在填充兩段行駛段之間空白時不能簡單地通過尋找最短路徑；并且考慮到車輛運輸過程中很少會跨越多等級的公路行駛，即從高速公路直接行駛到縣區(qū)道路的情況是很少的，只有在開頭與結(jié)尾才會出現(xiàn)，因此可以按照“highway”屬性的關(guān)系來對鄰接表中“d”屬性進行修改。

想要對鄰接表中的屬性“d”進行修改，首先需要知道空白數(shù)據(jù)前后兩段數(shù)據(jù)點所匹配道路的“highway”屬性，若需要加權(quán)的ways道路其“highway”屬性與前后兩段的“highway”屬性相同或者相近，則賦予較小的權(quán)重，這樣在搜索時可以更優(yōu)先選擇這一道路。同時依據(jù)需要加權(quán)的ways道路中點與前后兩段數(shù)據(jù)點的直線距離，重新分配前后兩段數(shù)據(jù)點對其的權(quán)重分配。

根據(jù)“highway”屬性賦予權(quán)重的依據(jù)如表1所示。

表1 highway屬性權(quán)重

表1中第一列表示前后兩段數(shù)據(jù)點所匹配道路的“highway”屬性，第一行表示需要加權(quán)的ways道路的“highway”屬性。根據(jù)式(6)重新分配權(quán)重方式。

(6)

其中，ω1、ω2表示前后兩數(shù)據(jù)段賦予的權(quán)重，d1、d2表示ways道路中點距離前后兩數(shù)據(jù)段端點的直線距離。

圖3示例表示了實際中的權(quán)重確定方式。

圖3 權(quán)重修改示意圖

圖3中空白數(shù)據(jù)前后兩段端點用三角形表示，前段數(shù)據(jù)匹配的道路屬性為motorway，后端數(shù)據(jù)匹配的道路屬性為trunk。上側(cè)虛線ways道路屬性為trunk，下側(cè)虛線ways道路屬性為primary。上側(cè)虛線中點到前后端點的直線距離分別為2和3；下側(cè)虛線中點到前后端點的直線距離分別為5和1。

若要求圖中虛線所示兩段道路的權(quán)重，結(jié)合屬性和表1，得出上側(cè)虛線道路的ω1=0.5、ω2=0，又因為d1=2、d2=3，因此求出上側(cè)虛線道路的權(quán)重：

同理，上側(cè)虛線道路的ω1=1.0、ω2=0.5，又因為d1=5、d2=1，因此求出上側(cè)虛線道路的權(quán)重：

根據(jù)上述方式求出每條道路的權(quán)重，然后用權(quán)重乘以原始數(shù)據(jù)，即得到修改之后“d”屬性內(nèi)的值d’。

1.4.2 填充異常數(shù)據(jù)點信息

對鄰接表中屬性“d”進行加權(quán)修改之后，利用傳統(tǒng)的Dijkstra算法或者Floyd算法搜索得到空白段之間基于權(quán)重的最佳路徑。將最佳路徑通過的nodes點連接起來，認(rèn)為是車輛實際的行駛軌跡。

有了車輛的行駛軌跡，仍需要在軌跡上尋找數(shù)據(jù)采樣定位點，最終完成填充空白段之間的數(shù)據(jù)。將在1.1節(jié)中被剔除的所有異常數(shù)據(jù)點連成一條直線，算出每個異常點在整條直線上的比例，在空白段的相同比例處添加相應(yīng)數(shù)據(jù)點，這樣保證了重新填充的正常點個數(shù)與剔除的異常點個數(shù)相等。

對于新添加的數(shù)據(jù)點，僅存在經(jīng)度與緯度兩個屬性的值，需要獲取對應(yīng)原始數(shù)據(jù)點中的方位角、GPS速度和行駛里程等信息，作為新添加數(shù)據(jù)點中對應(yīng)屬性的值。

2 實驗驗證

文中以某公司運輸車輛的10份行駛數(shù)據(jù)作為實驗數(shù)據(jù)集，數(shù)據(jù)集包括車號、方位角、經(jīng)緯、緯度、GPS速度和里程6個屬性值。

從網(wǎng)站OpenStreetMapnodes上下載開源地圖數(shù)據(jù)，該網(wǎng)站提供的地圖數(shù)據(jù)是以xml格式存儲的，將全球的地圖數(shù)據(jù)保存為一個大型的xml文件，并用特定的屬性來描述存儲的數(shù)據(jù)。

提取地圖數(shù)據(jù)中屬性為“nodes”的節(jié)點信息和“ways”的道路信息?！皀odes”表示地圖上的節(jié)點，包括唯一標(biāo)識符id和經(jīng)緯度坐標(biāo)lng與lat，其屬性中的“ways”表示該點落于這條道路上；“ways”表示地圖上的道路，包括唯一標(biāo)識符id和道路屬性highway，其屬性中的“nodes”表示該道路所經(jīng)過的點。根據(jù)式(4)的鄰接表存儲格式，將“nodes”信息和“ways”信息轉(zhuǎn)化為鄰接表存儲的一個實例的表示如下：

052:[756,131,128.10,6.67;045,500,244.37,186.81]

其中052表示某一nodes點的id，該nodes點與2個附近nodes點相鄰，756和045分別為兩個相鄰點的id；131和500表示原數(shù)據(jù)點和兩個相鄰數(shù)據(jù)點連接而成的道路的id；128.10和244.37表示原數(shù)據(jù)點和兩個相鄰數(shù)據(jù)點之間的距離；6.67和186.81表示原數(shù)據(jù)點和兩個相鄰數(shù)據(jù)點連接而成的道路的方位角。

以1號車為例，將未經(jīng)數(shù)據(jù)預(yù)處理的車輛行駛軌跡繪制在圖4所示的左側(cè)地圖上。

由圖4左側(cè)地圖可以看出，原始的車輛行駛數(shù)據(jù)由于具有較多異常點而導(dǎo)致軌跡難以辨認(rèn)。將剔除明顯異常點之后的數(shù)據(jù)集與道路進行匹配，并且在匹配的過程中修正和填充數(shù)據(jù)點的值，最終修正完成之后的車輛行駛軌跡如圖4右側(cè)地圖所示，其中，不同灰度的軌跡表示不同的行駛階段。

圖4 1號車初始行駛軌跡與修正軌跡

可以看出，車輛行駛軌跡與未經(jīng)數(shù)據(jù)預(yù)處理時比較有了明顯的改善，這說明文中的地圖匹配算法對車輛行駛數(shù)據(jù)進行預(yù)處理可以取得較好的效果。

文中用匹配時間、匹配率以及匹配完成后數(shù)據(jù)點剩余比例三個指標(biāo)來衡量算法的性能[16]。匹配時間指完成數(shù)據(jù)預(yù)處理以及數(shù)據(jù)點匹配所用總時間；匹配率指數(shù)據(jù)點匹配到真實行駛道路上的比例；數(shù)據(jù)點剩余比例指匹配完成后未被當(dāng)作異常點剔除的數(shù)據(jù)點占總數(shù)據(jù)點的比例。

將文中算法、不使用geohash函數(shù)與異常點填充的確定性匹配算法以及依據(jù)概率統(tǒng)計的不確定性匹配算法分別在10份行駛數(shù)據(jù)上運行，運行的硬件條件是具有Inter Core i7-7700HQ CUP的個人計算機。實驗結(jié)果如圖5～圖7所示。

圖5 三種算法匹配時間對比

圖6 三種算法匹配率對比

圖7 三種算法剩余比例對比

圖5表示三種算法所使用的匹配時間?？梢钥闯?，文中算法所用匹配時間雖然比普通確定性匹配算法略長，但遠小于依概率統(tǒng)計的不確定性匹配算法。

圖6表示三種算法的匹配率?？梢钥闯?，文中算法的匹配率稍高于依概率統(tǒng)計的不確定性匹配算法，遠高于普通確定性匹配算法。

圖7表示三種算法的數(shù)據(jù)點剩余比例?？梢钥闯?，由于進行了異常數(shù)據(jù)點填充，文中算法的剩余比例永遠是100%，遠大于其余兩種算法，原因是文中算法對異常數(shù)據(jù)點進行了按比例填充，將剔除的數(shù)據(jù)點全部填充回原始數(shù)據(jù)集。

綜上所述，文中使用的基于哈希和路網(wǎng)邊權(quán)的地圖匹配算法綜合了效率和準(zhǔn)確率兩個優(yōu)點，并且保留了大部分的原始數(shù)據(jù)?？梢詽M足對車輛行駛數(shù)據(jù)的預(yù)處理，同時也可以推廣至車輛的實時定位修正。

3 結(jié)束語

依據(jù)地圖匹配算法對車輛行駛數(shù)據(jù)進行修正對分析車輛駕駛行為起著至關(guān)重要的作用。文中設(shè)計的新型地圖匹配算法，利用geohash函數(shù)篩選數(shù)據(jù)點附近的道路，并且添加滑動窗口來減小匹配錯誤率，最后通過對路網(wǎng)邊權(quán)進行修正來填充缺失數(shù)據(jù)點。原理易懂，實現(xiàn)簡單，并且具有傳統(tǒng)確定性地圖匹配算法不具有的高準(zhǔn)確率和高時效性，不僅能夠在很大程度上提高車輛行駛數(shù)據(jù)的質(zhì)量，還能應(yīng)用于車輛行駛過程中的實時定位修正，有很高的可推廣性。

目前該地圖匹配算法中兩處用到了加權(quán)法，一處是計算數(shù)據(jù)點與道路的匹配度，另一處是依據(jù)“highway”屬性來修改鄰接表。但權(quán)重的確定對加權(quán)法的使用有很大的要求，文中權(quán)重的確定主要依靠人為經(jīng)驗，這會導(dǎo)致算法缺乏理論依據(jù)，如何確定最佳權(quán)重來提高算法的匹配率，將會是未來研究的重點。