陳芳芳

（阿里巴巴集團(tuán) 北京市 100102）

在我國(guó)，車輛的管理是一個(gè)很重要的問題，目前國(guó)內(nèi)很多城市都出現(xiàn)了停車難、車位貴等現(xiàn)象。由于人們出行越來(lái)越多導(dǎo)致交通壓力增大，交通擁堵問題也越來(lái)越突出，車輛管理的智能化成為人們關(guān)注和解決的熱點(diǎn)?；贕PS車輛軌跡數(shù)據(jù)技術(shù)能夠?qū)崿F(xiàn)對(duì)道路路段信息采集并進(jìn)行實(shí)時(shí)更新與控制，通過衛(wèi)星定位系統(tǒng)獲取到最新路況情況和周邊環(huán)境狀況以及用戶需求變化等相關(guān)路況資料，利用地圖數(shù)據(jù)庫(kù)存儲(chǔ)在服務(wù)器中以便調(diào)用地理信息系統(tǒng)，提高運(yùn)輸效率及準(zhǔn)確性的同時(shí)也能節(jié)省人力資源成本、增強(qiáng)競(jìng)爭(zhēng)力。由于這些原因，基于GPS車輛軌跡數(shù)據(jù)的路徑匹配算法在交通領(lǐng)域得到了廣泛研究和應(yīng)用。

1 地圖匹配算法研究

1.1 地圖匹配的概念

車輛的軌跡匹配是基于地圖數(shù)據(jù)集進(jìn)行路徑規(guī)劃，以滿足用戶需求，實(shí)現(xiàn)對(duì)路段、道路和時(shí)間點(diǎn)等信息在計(jì)算機(jī)中顯示，并根據(jù)實(shí)際情況選擇合適路線。定位技術(shù)結(jié)合地圖匹配算法，實(shí)現(xiàn)車輛的三維地形圖和交路GPS數(shù)據(jù)。該方法能夠有效地減少人工操作過程中存在著錯(cuò)誤率高、計(jì)算量大等問題，同時(shí)還能避免算法在實(shí)際應(yīng)用中路由過采樣點(diǎn)處的布設(shè)誤差以及由于天氣原因產(chǎn)生局部精度差值造成定位失敗，提高了系統(tǒng)運(yùn)行速度并降低成本。

地圖匹配算法主要包含兩個(gè)重要的過程：一是要先定位到該物體當(dāng)前正在形式的道路，并根據(jù)路線圖確定目的地，從而得到地圖匹配方測(cè)量點(diǎn)。二是將當(dāng)前的定位點(diǎn)投影到道路上，計(jì)算出匹配方的位置。車輛軌跡數(shù)據(jù)是基于GPS實(shí)時(shí)導(dǎo)航系統(tǒng)而產(chǎn)生，該算法可以根據(jù)道路信息生成路線圖，并能獲取當(dāng)前時(shí)間段內(nèi)的車流量、車道數(shù)和方向等基礎(chǔ)參數(shù)。

1.2 常用的地圖匹配算法

（1）直接投影法。直接投影方法的應(yīng)用是基于在車輛運(yùn)動(dòng)方向上，通過計(jì)算車輪與軌道間距離，從而得到地面點(diǎn)坐標(biāo)。該算法的基本思想是根據(jù)實(shí)際的車輛運(yùn)動(dòng)軌跡，在計(jì)算機(jī)上計(jì)算車輪與軌道間距離，從而得到地面點(diǎn)坐標(biāo)，該算法采用的是輪軌測(cè)距和軌道數(shù)據(jù)匹配，可以在計(jì)算機(jī)上通過GPS軌跡數(shù)據(jù)計(jì)算出車輛運(yùn)動(dòng)速度和加速度，該算法的實(shí)現(xiàn)需要硬件、軟件以及數(shù)據(jù)庫(kù)。直接投影方法如圖1所示。

圖1：直接投影方法

圖1中P點(diǎn)可以看做為一個(gè)定位點(diǎn)，而道路A和道路B是離該定位點(diǎn)最近的兩條道路，該車輛軌跡上有一條起始點(diǎn)，且相鄰兩條道路之間距離較近，根據(jù)交通流分析的方法計(jì)算出兩條車道數(shù)和A、B路段間平均坐標(biāo)。通過公式（1）可以分別計(jì)算道路的距離度量值：

式中ri表示點(diǎn)P到各條道路的隱射聚力，θi是物體行駛方向與道路之間的夾角，分別為距離和方向的權(quán)重系數(shù)。

（2）基于幾何關(guān)系的算法?；趲缀侮P(guān)系的路徑匹配算法是一種常見且實(shí)用性較高的車輛軌跡匹配方法，它把GPS導(dǎo)航和無(wú)人機(jī)航拍相結(jié)合，根據(jù)地理位置、周邊環(huán)境等信息對(duì)車輛位置進(jìn)行定位。通?；趲缀侮P(guān)系的地圖匹配算法具體分為三種：點(diǎn)到點(diǎn)的匹配、點(diǎn)到線的匹配及線到線的匹配。

點(diǎn)到點(diǎn)的匹配，指的是將GPS定位點(diǎn)匹配到附近道路網(wǎng)絡(luò)中的節(jié)點(diǎn)或形狀點(diǎn)上，以一定的比例、位置計(jì)算出所匹配到點(diǎn)處的坐標(biāo)，并按照某種規(guī)則進(jìn)行組合，從而得到車輛軌跡。此算法匹配速度快，但計(jì)算量大，且在車輛運(yùn)動(dòng)軌跡數(shù)據(jù)中，該算法可以有效的處理大量道路數(shù)據(jù)。點(diǎn)到點(diǎn)匹配的具體數(shù)學(xué)計(jì)算模型如圖2所示。

圖2：點(diǎn)到點(diǎn)匹配

點(diǎn)到線的匹配是指車輛從起點(diǎn)到終點(diǎn)間的所有路段上的數(shù)據(jù)信息匹配，是基于GPS定位技術(shù)實(shí)現(xiàn)，其原理是通過GPS定位點(diǎn)做所有待匹配路段的投影距離，并將其與已匹配路段的實(shí)際距離進(jìn)行對(duì)比，從而得出車輛在起點(diǎn)到終點(diǎn)間所有道路上運(yùn)行軌跡信息。具體做法是當(dāng)?shù)缆窞橹本€道路時(shí)，通過GPS地圖數(shù)據(jù)計(jì)算出車輛的坐標(biāo)，再將其平分成不同路段，分別匹配到直線路和交叉口，再做垂線段。點(diǎn)到線的匹配的數(shù)學(xué)模型如圖3所示。

由圖3中可知，P點(diǎn)到直線AB的距離為的計(jì)算如公式（2）所示：

圖3：點(diǎn)到線的匹配

P點(diǎn)到直線AB的投影點(diǎn)C即為候選匹配點(diǎn)，k為直線AB的斜率，則C點(diǎn)的坐標(biāo)計(jì)算如公式（3）所示：

線到線的匹配算法是交通領(lǐng)域中的一個(gè)重要內(nèi)容，也是解決數(shù)據(jù)匹配問題最常用且有效、最快速和最有效率途徑之一，在車輛運(yùn)動(dòng)控制和智能導(dǎo)航等方面得到了廣泛研究。該算法不僅利用了當(dāng)前GPS定位數(shù)據(jù)，還利用了歷史軌跡數(shù)據(jù)，可以在地圖數(shù)據(jù)中添加導(dǎo)航信息，使車輛軌跡的匹配更加準(zhǔn)確。與前面兩種算法相比，該算法是一種更先進(jìn)的算法，具有很強(qiáng)的實(shí)時(shí)性，可以在地圖數(shù)據(jù)中添加導(dǎo)航信息。線到線的匹配算法的具體數(shù)學(xué)計(jì)算模型如圖4所示。

圖4：線到線的匹配

用積分來(lái)計(jì)算兩條曲線之間的距離，則曲線的平均距離計(jì)算如公式（4）所示：

（3）概率統(tǒng)計(jì)算法。概率統(tǒng)計(jì)算法是根據(jù)實(shí)測(cè)值或歷史測(cè)得的數(shù)據(jù)，對(duì)所有可能出現(xiàn)的情形，按一定規(guī)則進(jìn)行統(tǒng)計(jì)運(yùn)算分析。該算法的基本思想是依據(jù)GPS 接收到的定位數(shù)據(jù)設(shè)置一個(gè)誤差區(qū)域，根據(jù)實(shí)際數(shù)據(jù)和已知的車輛軌跡分析出兩者之間的關(guān)系，計(jì)算出相應(yīng)誤差區(qū)域，再將得到結(jié)果與真實(shí)軌道差值進(jìn)行比較以驗(yàn)證匹配算法正確性。概率統(tǒng)計(jì)算法利用誤差橢圓確定了置信區(qū)域，然后從數(shù)字地圖數(shù)中提取候選路段，然后根據(jù)已提取的路段信息計(jì)算出車輛行駛方向、運(yùn)行距離等行車狀態(tài)，最后將結(jié)果與真實(shí)軌道差值進(jìn)行比較，得到匹配情況。按照統(tǒng)計(jì)理論，定位誤差橢圓的推導(dǎo)如公式（5）所示：

（4）模糊邏輯算法。模糊邏輯算法是利用計(jì)算機(jī)對(duì)輸入信息進(jìn)行判斷，并根據(jù)相應(yīng)的規(guī)則來(lái)處理輸出。它通過模擬人腦中多角度和空間經(jīng)驗(yàn)而得出一個(gè)較為理想化結(jié)果，其優(yōu)點(diǎn)在于能夠在一定范圍內(nèi)實(shí)現(xiàn)最優(yōu)控制。該方法主要有兩種形式：一種情況是將所有信息按不同方式劃分成許多集合，然后再進(jìn)行劃分，這種方法在計(jì)算過程中能夠?qū)崿F(xiàn)快速準(zhǔn)確的運(yùn)算，并且能將時(shí)間分割為若干個(gè)小區(qū)間。另一種則為根據(jù)集合確定出一個(gè)規(guī)則函數(shù)來(lái)實(shí)現(xiàn)模糊邏輯推理，通過GPS車輛軌跡數(shù)據(jù)的特點(diǎn)來(lái)確定出離散點(diǎn)在同一地點(diǎn)下所對(duì)應(yīng)的位置。

1.3 改進(jìn)的基于權(quán)重的地圖匹配算法

基于權(quán)重的地圖匹配算法是在車輛軌跡數(shù)據(jù)中引入了一些權(quán)重，這些指標(biāo)和層次分析法可以有效地對(duì)采集到的交通信息進(jìn)行處理。它能夠?qū)⒏鞣N不同類型道路之間存在著一定差異性，但是由于其本身具有主觀因素導(dǎo)致計(jì)算過程復(fù)雜、運(yùn)算量大等問題限制了其應(yīng)用范圍與實(shí)際價(jià)值不相符甚至出現(xiàn)偏差，同時(shí)也無(wú)法準(zhǔn)確獲得所需匹配路段的具體位置以及車輛在整個(gè)路網(wǎng)中所處地理位置，因此不能很好地利用這些數(shù)據(jù)對(duì)路徑優(yōu)化算法進(jìn)行設(shè)計(jì)和實(shí)現(xiàn)。

基于權(quán)重的地圖匹配算法是局部修正算法，它的計(jì)算量比較大，但在實(shí)際應(yīng)用中，由于車輛運(yùn)動(dòng)軌跡具有不確定性，所以需要進(jìn)行大量數(shù)據(jù)處理。本文進(jìn)行GPS車輛軌跡研究時(shí)，主要是將基于權(quán)重的地圖匹配算法和道路拓?fù)浣Y(jié)構(gòu)相結(jié)合，通過GPS車輛軌跡數(shù)據(jù)進(jìn)行匹配，同時(shí)，將車輛軌跡數(shù)據(jù)和道路信息相結(jié)合，從而獲得更加精確的匹配結(jié)果。

2 影響地圖匹配質(zhì)量的因素

2.1 GPS定位誤差

在車輛路徑規(guī)劃中，定位誤差是不可避免的，GPS數(shù)據(jù)采集到的是行駛距離、車道位置信息以及方向偏差等多種因素引起的車跡地別的偏移而產(chǎn)生，從而影響到車輛行駛的準(zhǔn)確性。由于這些信息存在于不同載體上且具有不確定性和非連續(xù)性特征，因此對(duì)衛(wèi)星導(dǎo)航系統(tǒng)造成了一定程度上損失?；谲囕v軌跡匹配算法可以實(shí)現(xiàn)道路資源合理分配并提高道路運(yùn)輸效率：通過使用GIS地圖定位軟件，可有效避免交通擁堵情況，GPS軌跡數(shù)據(jù)中蘊(yùn)含著大量的車輛位置和行程信息，可以在地圖上顯示停車位、路徑等相關(guān)參數(shù)，利用GIS地理信息系統(tǒng)（如衛(wèi)星定位系統(tǒng)）獲取道路資源時(shí)，可實(shí)現(xiàn)對(duì)地面交通流進(jìn)行實(shí)時(shí)監(jiān)控。

GPS定位誤差包括內(nèi)部誤差和外部誤差。內(nèi)部誤差是指由衛(wèi)星接收引起的固定誤差，主要原因是衛(wèi)星運(yùn)行速度太慢，并且在經(jīng)過若干年后，GPS車輛軌跡數(shù)據(jù)精度已經(jīng)很難滿足用戶的需求。外部誤差則有環(huán)境因素和天氣原因等方面引起，主要包括GPS系統(tǒng)自身存在的一些缺陷,例如氣象條件、地形地貌以及道路狀況等，這些都會(huì)對(duì)定位精度造成影響。基于GPS車輛軌跡數(shù)據(jù)的定位方法，通過對(duì)已有算法原理進(jìn)行分析歸納，提出了利用多傳感器網(wǎng)絡(luò)相結(jié)合來(lái)提高車位計(jì)算精度、增強(qiáng)地圖匹配速度和滿足用戶需求等優(yōu)化方案。

2.2 電子地圖誤差

由于通過GPS軌跡數(shù)據(jù)中的車輛位置、速度、方向等信息來(lái)匹配到當(dāng)前車主所處地點(diǎn)，并在這些內(nèi)容記錄下行駛時(shí)間，根據(jù)地圖上顯示出來(lái)的路線圖和對(duì)應(yīng)路段進(jìn)行坐標(biāo)計(jì)算。因此在交通系統(tǒng)中占有重要地位，其性能優(yōu)劣直接影響到車輛運(yùn)行速度、道路數(shù)據(jù)傳輸質(zhì)量和處理效率等?；贕PS軌跡數(shù)據(jù)采集與分析技術(shù)是一種新型地理信息系統(tǒng)，該數(shù)據(jù)庫(kù)采用了GIS地圖管理系統(tǒng)來(lái)管理平臺(tái)上所有存儲(chǔ)空間位置分布圖譜，并根據(jù)道路信息數(shù)據(jù)建立了基于地圖數(shù)據(jù)庫(kù)的車輛軌跡庫(kù)。電子地圖的精度誤差對(duì)地圖匹配效果的影響很小，但出現(xiàn)道路變更、道路情況復(fù)雜以及電子地圖精度較低的情況時(shí)，將會(huì)加大電子地圖的誤差，導(dǎo)致地圖匹配失效。

2.3 坐標(biāo)變換誤差

坐標(biāo)變換的精度是指計(jì)算出車輛在坐標(biāo)系中點(diǎn)相對(duì)于車軸或線下兩點(diǎn)間軌跡角度。它可以消除由軌道誤差所引起的數(shù)據(jù)處理上出現(xiàn)錯(cuò)誤。由于GPS定位系統(tǒng)采用的是車載天線，因此其坐標(biāo)變化對(duì)車上車輛位置也有一定影響，因此需要在車輛軌跡匹配過程中對(duì)其坐標(biāo)進(jìn)行準(zhǔn)確的調(diào)整以保證數(shù)據(jù)能夠滿足實(shí)際需求。

3 地圖匹配軟件的實(shí)現(xiàn)

3.1 開發(fā)工具及環(huán)境

車輛軌跡數(shù)據(jù)的匹配是一個(gè)過程,它需要根據(jù)實(shí)際情況進(jìn)行選擇和分析。在開發(fā)工具上，主要采用Microsoft Visual Studio 2010開發(fā)平臺(tái)和MapInfo公司提供的MapX控件進(jìn)行地圖匹配模塊的集成二次開發(fā)，利用MATLAB、Java語(yǔ)言和C++編程語(yǔ)言對(duì)車輛軌跡進(jìn)行數(shù)據(jù)處理，同時(shí)結(jié)合數(shù)據(jù)庫(kù)技術(shù)，完成了基于GPS的車輛路徑軌跡匹配算法。其中硬件環(huán)境使用的是智能手機(jī)定位模塊和計(jì)算機(jī)硬件。

3.2 地圖匹配的總體設(shè)計(jì)與實(shí)現(xiàn)

地圖匹配的應(yīng)用目的不同，對(duì)地圖匹配的實(shí)時(shí)性、效率等的要求不同，導(dǎo)致車輛軌跡匹配的方法也不同?；贕PS數(shù)據(jù)平臺(tái)，通過合理安排車道、車速等基本信息，根據(jù)道路情況確定路線并實(shí)現(xiàn)實(shí)時(shí)路況顯示，利用GPS軌跡信息進(jìn)行車輛路徑匹配，可以大大提高路況數(shù)據(jù)的實(shí)時(shí)性，為司機(jī)提供一條準(zhǔn)確、快速且易于操作控制和保護(hù)的道路。根據(jù)本文的應(yīng)用需求，地圖匹配軟件的總體設(shè)計(jì)如圖5所示。

圖5：地圖匹配軟件的總體設(shè)計(jì)

4 實(shí)驗(yàn)效果分析

本次實(shí)驗(yàn)的數(shù)據(jù)來(lái)源為兩部分，一部分為校園實(shí)測(cè)數(shù)據(jù)，該數(shù)據(jù)是通過Android智能手機(jī)的GPS定位技術(shù)，通過數(shù)據(jù)的拼接與處理，生成位置軌跡，再使用GPS車輛運(yùn)動(dòng)控制軟件GPRS模塊獲取到導(dǎo)航信息。另一部分是基于匹配算法中基于對(duì)已有地圖資料進(jìn)行調(diào)整后得到較為精確地車距、時(shí)間等參數(shù)。這些結(jié)果都能在一定程度上減少人為因素造成不必要損失和提高計(jì)算精度降低成本支出，另外該方法可以通過GPS衛(wèi)星定位系統(tǒng)實(shí)現(xiàn)高分辨率的道路數(shù)據(jù)，還可利用車輛軌跡數(shù)據(jù)庫(kù)提供的交通狀況實(shí)時(shí)分析數(shù)據(jù)支持來(lái)滿足用戶需求，通過車輛軌跡數(shù)據(jù)的匹配計(jì)算可以得到道路行程時(shí)間，還能在地圖上提供更加精確地導(dǎo)航路徑，滿足用戶對(duì)車距、速度等參數(shù)的要求。

通過實(shí)驗(yàn)，對(duì)本文所提出的算法進(jìn)行分析研究，圍繞準(zhǔn)確性和實(shí)時(shí)性2個(gè)重要指標(biāo)，來(lái)衡量本文算法的有效性。

4.1 準(zhǔn)確性分析

為了驗(yàn)證本文匹配算法的準(zhǔn)確性，分別采用三組不同地方的GPS軌跡進(jìn)行實(shí)驗(yàn)，并獲取了車輛軌跡數(shù)據(jù)。通過不同的方法，將所獲取到的GPS軌跡與電子地圖進(jìn)行匹配，結(jié)果對(duì)比如表1所示。

表1：基于權(quán)重的匹配算法

4.2 實(shí)時(shí)性分析

在實(shí)驗(yàn)過程中，為了評(píng)價(jià)該算法的實(shí)時(shí)性，我們對(duì)車輛軌跡數(shù)據(jù)的獲取、處理和匹配過程進(jìn)行了研究。通過分析得知,使用GPS導(dǎo)航定位模塊,基于地圖生成算法中最常用到的是曲線擬合。本次實(shí)驗(yàn)通過多線程并行化方法優(yōu)化算法，實(shí)驗(yàn)結(jié)果如表2所示。

表2：實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)結(jié)果表明:基于GPS的車輛軌跡數(shù)據(jù)匹配算法在實(shí)際應(yīng)用中具有較好的效果,能夠滿足用戶對(duì)實(shí)時(shí)信息和路面狀況準(zhǔn)確且及時(shí)地提供相應(yīng)導(dǎo)航服務(wù)。同時(shí),該方法還可以用于交通監(jiān)控領(lǐng)域，如交通擁堵的實(shí)時(shí)監(jiān)測(cè)、高速公路動(dòng)態(tài)流量采集等方面。

5 總結(jié)

綜上所述，隨著GPS技術(shù)的不斷成熟，基于交通信息數(shù)據(jù)領(lǐng)域?qū)囕v軌跡智能化管理已經(jīng)成為現(xiàn)實(shí)，在我國(guó)國(guó)內(nèi)許多大城市和綜合實(shí)力強(qiáng)大、使用方便的公共停車場(chǎng)也越來(lái)越多，基于交通信息數(shù)據(jù)領(lǐng)域的GPS車輛軌跡智能化系統(tǒng)已經(jīng)在國(guó)內(nèi)被廣泛投入使用。本文基于GPS車輛軌跡數(shù)據(jù)采集與匹配算法研究，對(duì)基于個(gè)人GPS軌跡數(shù)據(jù)的地圖匹配算法進(jìn)行了研究，提升位置服務(wù)應(yīng)用的用戶體驗(yàn)，實(shí)現(xiàn)交通信息實(shí)時(shí)匹配。根據(jù)車輛軌跡數(shù)據(jù)獲取和處理的基本原理，提出基于位置、距離等關(guān)鍵參數(shù)，利用GPS車輛運(yùn)動(dòng)學(xué)模型，結(jié)合GIS平臺(tái)進(jìn)行車位分配算法研究。通過實(shí)驗(yàn)結(jié)果表明：基于權(quán)重的地圖匹配算法具有較高的精確度與高效性，同時(shí)也能保證在城市道路擁堵情況下提高運(yùn)輸效率并降低交通事故發(fā)生率，其計(jì)算速度快且可重復(fù)率低是它存在和發(fā)展所要求實(shí)現(xiàn)的目標(biāo)之一。