基于局部搜索的GPS地圖匹配算法

原文翻譯基于局部路徑搜索的浮動車數(shù)據(jù)地圖匹配算法摘要道路交通流信息的獲取對于城市交通控制與管理是必要的。浮動車數(shù)據(jù)（FCD）是采樣城市大規(guī)模道路網(wǎng)絡(luò)交通流的新興技術(shù)，它可以提供有效的手段來模擬和分析道路交通狀況。地圖匹配是FCD的關(guān)鍵技術(shù)之一。典型的導(dǎo)航地圖匹配技術(shù)不適合處理浮動車數(shù)據(jù)大采樣間隔。通過分析浮動車數(shù)據(jù)的特點，我們首先提出基于局部路徑搜索的浮動車數(shù)據(jù)地圖匹配算法。可以利用之前已經(jīng)匹配的GPS點信息顯著減少搜索空間。矩形置信區(qū)的構(gòu)造用于減少候選路段的數(shù)量。該算法不僅可以達(dá)到高精度浮動車數(shù)據(jù)定位要求，而且可以監(jiān)測車輛的運動軌跡。實驗結(jié)果表明，我們的方法適用于不同的浮動車數(shù)據(jù)采樣間隔。關(guān)鍵字：浮動車數(shù)據(jù)；局部路徑搜索；地圖匹配；采樣間隔；矩形置信區(qū)1. 引言道路交通流信息的獲取對于城市交通控制、管理以及交通規(guī)劃是必要的?，F(xiàn)有的道路交通流采集方法主要采用定點模式，包括感應(yīng)圈、微波、雷達(dá)和視頻技術(shù)，這些方法有一些缺點如覆蓋區(qū)域限制、成本高及維修困難等。與定點模式采樣相比，F(xiàn)CD具有覆蓋區(qū)域廣、易于維護(hù)及成本低等優(yōu)點。它可以提供大規(guī)模的動態(tài)交通信息，因此有效運用于實時指導(dǎo)、管理和控制中。FCD在過去幾十年受到顯著關(guān)注。地圖匹配算法已經(jīng)成為浮動車數(shù)據(jù)研究的一個課題。到目前為止，浮動車數(shù)據(jù)地圖匹配主要依賴于導(dǎo)航地圖匹配算法。導(dǎo)航地圖匹配算法在文獻(xiàn)中被歸納為四類：幾何分析法、拓?fù)浞?、概率法和其他的高級方法。常用的幾何分析法包括點-點、點-線、線-線地圖匹配算法?？紤]道路的形狀，這些方法利用空間路網(wǎng)數(shù)據(jù)的幾何信息實現(xiàn)地圖匹配，具有簡單、快速的優(yōu)點。由于沒有考慮道路之間的連接關(guān)系，這些方法在交叉口、平行道路、環(huán)形道路下的匹配效果較差?；谕?fù)涞牡貓D匹配算法是指結(jié)合路段的幾何特性、路段之間連通性和鄰接關(guān)系的地圖匹配算法。但拓?fù)浞]有考慮車輛的行駛方向和速度信息，所以此方法法對異常值非常敏感。概率匹配法在定位附近構(gòu)建橢圓或是矩形的誤差區(qū)。誤差區(qū)域可以由GPS定位誤差的方差來確定。誤差區(qū)域內(nèi)的道路路段是候選方案。這些算法使用行駛方向、連接性、遠(yuǎn)近程度等來進(jìn)行地圖匹配。高級地圖匹配算法利用卡爾曼濾波、證據(jù)理論、模糊邏輯和神經(jīng)網(wǎng)絡(luò)等方法。這些方法在相同條件下優(yōu)于其他三種方法，但是高級地圖匹配算法通常需要更多的輸入數(shù)據(jù)，并有一些缺點如較慢的匹配速度實現(xiàn)復(fù)雜等。導(dǎo)航地圖匹配算法在高采樣頻率下也能夠獲得好的結(jié)果（如1Hz）。然而FCD的采樣間隔從10s到2分鐘之間，并且它可能由于噪聲和錯誤隨時間變化。因此很難利用導(dǎo)航地圖匹配算法處理浮動車數(shù)據(jù)。到目前為止，只有少量與浮動車數(shù)據(jù)地圖匹配的工作成果。Liao et al等人提出了基于數(shù)據(jù)結(jié)構(gòu)交叉點的雙向啟發(fā)式地圖匹配算法以應(yīng)對十字路口。該算法利用交叉的數(shù)據(jù)結(jié)構(gòu)將交叉點從普通地圖匹配中分離出來，并且降低了浮動車數(shù)據(jù)地圖匹配的錯誤。然而由于增加了過多的節(jié)點和鏈路使得計算復(fù)雜性顯著增加?；贕IS數(shù)字地圖網(wǎng)格劃分。Wang et al提出一種快速的浮動車數(shù)據(jù)地圖匹配算法。這種方法設(shè)計了一種道路網(wǎng)絡(luò)結(jié)構(gòu)，其將道路網(wǎng)絡(luò)劃分為兩個層次，并將道路網(wǎng)絡(luò)劃分成網(wǎng)格。然而要確定網(wǎng)格的大小卻十分困難。這項工作的目的是研究適用于數(shù)據(jù)量大及動態(tài)的采樣的浮動車數(shù)據(jù)的地圖匹配算法。根據(jù)對浮動車數(shù)據(jù)的特征分析，我們首先提出了基于局部路徑搜索的浮動車數(shù)據(jù)地圖匹配算法。最大可能距離作為啟發(fā)式信息以減少搜索空間。矩形置信區(qū)中心位置由GPS確定，它的建立用來確定候選匹配路段的有效性，并且在中心位置的車的方向和距離用來糾正與浮動車數(shù)據(jù)匹配的路段。本文的其余部分安排如下：第2節(jié)介紹浮動車數(shù)據(jù)匹配，啟發(fā)式局路徑搜索原理和矩形置信區(qū)方法提出的解釋。第3節(jié)給出了浮動車數(shù)據(jù)地圖匹配算法的描述。在第4節(jié)，給出了實驗測試的結(jié)果并討論。最后一節(jié)總結(jié)了全部工作。2. FCD地圖匹配原理地圖匹配是浮動車數(shù)據(jù)技術(shù)的關(guān)鍵技術(shù)。每個浮動車數(shù)據(jù)記錄包括車輛ID、經(jīng)度與維度、時間、行駛方向、瞬時速度等。FCD技術(shù)主要被應(yīng)用于給交通管理者和使用者提供道路網(wǎng)絡(luò)的交通狀況?？紤]到通信成本，浮動車數(shù)據(jù)采樣的頻率是10到120秒之間。環(huán)境的干擾可能導(dǎo)致兩個FCD的時間間隔大于30秒在遠(yuǎn)程監(jiān)測中心。針對FCD動態(tài)采樣間隔我們提出了一個基于局部路徑搜索的的地圖匹配算法。該方法可以確定車輛在兩個GPS位置間的移動路徑，這也是基于浮動車數(shù)據(jù)技術(shù)獲取交通指導(dǎo)、控制和交通狀態(tài)估計所必要的。該算法主要包括三個步驟：局部路徑搜索，矩形置信區(qū)確定和地圖匹配。對與浮動車數(shù)據(jù)包中第一個GPS點的位置固定問題，考慮到相關(guān)信息不可用，我們采用點-線法定位以獲取高精度的GPS點。2.1 局部路徑搜索GIS（GIS：地理信息系統(tǒng)）數(shù)字地圖是一個有向連通圖。該匹配算法首先搜索當(dāng)前匹配點的前一個匹配點作為起始點，獲得候選路徑集合。由于城市道路網(wǎng)絡(luò)規(guī)模龐大，所以引入了最大可能行駛距離作為路徑搜索的限制條件，從而降低搜索算法的復(fù)雜度。它的定義如下： (1)這里是車輛城市道路上所允許的最高速度，是車輛在兩個相鄰GPS點的時間間隔。路徑搜索的終止條件為： (2)其中，是路徑長度，是由于環(huán)境干擾造成的GPS誤差 。搜索空間可以通過引入最大可能距離顯著降低。在遍歷路網(wǎng)后，所有滿足公式(2)且不是回路的路徑都是候選路徑。2.2 矩形置信區(qū)的確定經(jīng)過局部路徑搜索處理所得到的候選匹配路徑集還是較大。因此，定義矩形置信區(qū)以進(jìn)一步減少候選路徑的數(shù)量。矩形置信區(qū)的確定根據(jù)中心點和距離（如圖1所示）。具體描述如下。假設(shè)是當(dāng)前GPS匹配點，是上一個匹配點。中心點的坐標(biāo)是(,)， 的坐標(biāo)是(,)，這里的和是經(jīng)度，和是緯度。矩形置信區(qū)的定點坐標(biāo)可以根據(jù)到每一個邊和中心點的距離來計算。緯度的誤差可以由公式(3)獲得。 (3)這里。經(jīng)度的誤差可以有公式(4)和(5)計算得到。 (4)(5)最終，矩形置信區(qū)的頂點坐標(biāo)可以如下獲得：矩形置信區(qū)可用于進(jìn)一步選擇候選匹配的路徑。如果候選路段的結(jié)尾路段在矩形置信區(qū)內(nèi)，則該路段是有效的。下一步是確定匹配路段。候選路段是否被選取取決于糾正后的浮動車數(shù)據(jù)記錄中的車倆的方向信息。如果車輛方向和和候選道路結(jié)束方向的差滿足誤差范圍（如15度），那么這條路保留，否則，將它從候選路段集合中除去。最終，從固定點到終點之間的所有候選路段都是符合計算要求的候選路徑。其中具有最短距離的就是目標(biāo)匹配。GPS固定點由匹配路段的結(jié)束來確定。3. FCD地圖匹配的描述設(shè)為GPS誤差閾值，是方向角誤差閾值，為車輛的最大行駛速度?；诰植柯窂剿阉鞯腇CD地圖匹配算法描述如下。初始化參數(shù)、和；如果當(dāng)前的待處理的GPS點是浮動車數(shù)據(jù)包中的第一個點，則利用點-線法進(jìn)行匹配處理；否則重復(fù)以下步驟；為前一個GPS匹配點，取同一輛車FCD中的GPS數(shù)據(jù)賦值給計算，從開始遍歷路網(wǎng)，一個無回路且滿足的路徑是匹配的候選路徑，將其存儲在，這里的是路徑長度，矩形置信區(qū)由坐標(biāo)頂點確定：從集合刪除路段終端不在矩形置信區(qū)的路徑，計算候選路段終點方向和FCD記錄中車輛方向的差值，如果，則將該候選路段保留，否則從集合去除，對于集合中的所有候選路段，計算路段終端和GPS點之間的距離，距離最短的路段將會被選取，將點投影在路段終端，直到處理完所有的FCD記錄。4. 試驗與討論為了評價這個算法，我們調(diào)查了中國合肥市道路網(wǎng)絡(luò)的相關(guān)數(shù)據(jù)。通過2000多條FCD記錄建立一個采樣庫以驗證我們的算法。首先，分別用我們的算法和“點-線”法進(jìn)行較準(zhǔn)確的試驗。在實驗中，F(xiàn)CD的采樣間隔是10秒鐘，一共使用了5組數(shù)據(jù)FCD數(shù)據(jù)包，每一組有400條FCD記錄。試驗結(jié)果記錄在表1，從表1中我們可以看出我們算法的匹配準(zhǔn)確度達(dá)到85.2%，相應(yīng)的“點-線”發(fā)匹配準(zhǔn)確度達(dá)到82.4%。另外，我們分別采用了50秒和100秒的FCD記錄以測試采樣間隔對于該算法的影響。在這個試驗中，選取了三組試驗。每一組有200條FCD記錄。試驗結(jié)果在表2中顯示。很明顯我們的算法對于不同F(xiàn)CD采樣間隔的匹配精度不會有大的變化。5. 結(jié)論FCD地圖匹配是城市交通動態(tài)路線指導(dǎo)的關(guān)鍵技術(shù)之