田甜　呂芳　王秀玲

摘 要： 地圖匹配方法，對(duì)于浮動(dòng)車(chē)技術(shù)有著重要的意義。由于浮動(dòng)車(chē)數(shù)據(jù)自身的特點(diǎn)，傳統(tǒng)的地圖匹配算法難以直接應(yīng)用在城市道路浮動(dòng)車(chē)數(shù)據(jù)匹配上。針對(duì)目前浮動(dòng)車(chē)地圖匹配算法應(yīng)用于城市復(fù)雜路網(wǎng)時(shí)只考慮單一車(chē)輛位置數(shù)據(jù)，聯(lián)動(dòng)性研究較少，導(dǎo)致產(chǎn)生匹配精度不高的問(wèn)題，考慮車(chē)輛運(yùn)行特征與道路路網(wǎng)的連通信息，同時(shí)結(jié)合動(dòng)態(tài)GPS數(shù)據(jù)， 把模糊邏輯推理思想引入到網(wǎng)格地圖匹配方法中，提出一種優(yōu)化的地圖匹配方法，并對(duì)其有效性進(jìn)行了驗(yàn)證。研究表明，優(yōu)化浮動(dòng)車(chē)地圖匹配方法在保持網(wǎng)格地圖匹配實(shí)時(shí)性?xún)?yōu)點(diǎn)的同時(shí)，提高了算法的匹配精度。

關(guān)鍵詞： 浮動(dòng)車(chē)； GPS； 模糊邏輯； 地圖匹配

中圖分類(lèi)號(hào)： TN957.52+9； U495 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2015）11?0159?04

Optimized map?matching method for floating car

TIAN Tian， L? Fang， WANG Xiu?ling

（Institute of Electronic Information Engineering， Inner Mongolia University of Technology， Hohhot 010000， China）

Abstract： Map?matching method has great significance for floating car technology. It is hard for the traditional map?matching algorithm to be directly applied to floating car data matching of city road due to the characteristics of floating car data. Currently， since the floating car map?matching algorithm used in city complex road network considers the single vehicle location data only， and the research on co?movement is less， it results in low matching precision. Considering the vehicle operating characteristics and the intercommunication information of road network， the optimized map?matching method is proposed with the dynamic GPS data， in which the fuzzy logic theory is introduced into the grid map?matching method. The effectiveness of the method was verified. The research results show that the optimized map?matching method for floating car can improve the matching precision of the algorithm while keeping the advantage of real?time performance of grid map?matching.

Keywords： floating car； GPS； fuzzy logic； map?matching

0 引 言

交通擁堵現(xiàn)已成為困擾現(xiàn)代城市發(fā)展的嚴(yán)重問(wèn)題，及時(shí)反映交通狀況，采取合理的預(yù)警措施，避免交通擁堵，已成為智能交通領(lǐng)域亟需解決的問(wèn)題[1]。而隨著科技的進(jìn)步，以固定型交通采集技術(shù)[2]為主的傳統(tǒng)交通信息采集方式，已經(jīng)不能夠適應(yīng)快速增長(zhǎng)的道路數(shù)量和車(chē)輛保有量。浮動(dòng)車(chē)技術(shù)作為一種嶄新的城市路況信息獲取、道路建設(shè)和出行規(guī)劃方式，逐步成為研究熱點(diǎn)。

浮動(dòng)車(chē)數(shù)據(jù)地圖匹配是浮動(dòng)車(chē)技術(shù)中亟需解決的關(guān)鍵性問(wèn)題。然而，現(xiàn)有的地圖匹配算法如耿小峰等利用道路幾何特征對(duì)車(chē)輛進(jìn)行地圖匹配[3]；蘇海濱等引用模糊神經(jīng)網(wǎng)絡(luò)對(duì)車(chē)輛特征變量進(jìn)行學(xué)習(xí)[4]，提高算法容錯(cuò)能力；李珂等基于D?S證據(jù)理論的地圖匹配算法通過(guò)建立信任函數(shù)和證據(jù)融合，考察可達(dá)性進(jìn)行匹配選擇[5]；楊海強(qiáng)等基于權(quán)重的匹配方法考慮定位點(diǎn)時(shí)間間隔，充分運(yùn)用定位信息以加強(qiáng)匹配效果[6]?？偟膩?lái)說(shuō)，現(xiàn)有算法多重視匹配準(zhǔn)確率，少有考慮車(chē)輛行駛特點(diǎn)及道路網(wǎng)間復(fù)雜連通信息，導(dǎo)致其應(yīng)用性欠妥。而基于網(wǎng)格搜索的地圖匹配，算法概念簡(jiǎn)單，易于編碼實(shí)現(xiàn)，滿(mǎn)足浮動(dòng)車(chē)匹配的實(shí)時(shí)性要求，但其在彎道或道路密集的交叉口等路況復(fù)雜時(shí)匹配率較低。本文考慮浮動(dòng)車(chē)數(shù)據(jù)特點(diǎn)及道路網(wǎng)連通信息，把模糊邏輯推理思想引入到網(wǎng)格地圖匹配方法中，提出了一種優(yōu)化的地圖匹配方法，在保持浮動(dòng)車(chē)數(shù)據(jù)地圖匹配實(shí)時(shí)性要求的同時(shí)，有效提高了算法的匹配精度。

1 傳統(tǒng)的網(wǎng)格地圖匹配方法

通過(guò)網(wǎng)格劃分將電子地圖路網(wǎng)劃分為多個(gè)網(wǎng)格并進(jìn)行編號(hào)，根據(jù)GPS定位點(diǎn)快速搜索浮動(dòng)車(chē)點(diǎn)相對(duì)于電子地圖的位置進(jìn)行匹配。

先將柵格化電子地圖劃分為若干個(gè)網(wǎng)格，根據(jù)提取到的有效GPS定位信息，在網(wǎng)格列表中搜尋所處的網(wǎng)格，確定網(wǎng)格編號(hào)，在其內(nèi)有效行駛路徑上對(duì)浮動(dòng)車(chē)點(diǎn)進(jìn)行匹配處理。然而，僅限于浮動(dòng)車(chē)點(diǎn)所在網(wǎng)格內(nèi)待匹配行駛路徑是不合理的，若定位點(diǎn)在網(wǎng)格邊界處，其位置很可能在與網(wǎng)格相連的其他網(wǎng)格路段中，考慮到此種情況，在搜索待匹配行駛路徑時(shí)，搜索范圍定為浮動(dòng)車(chē)點(diǎn)所在網(wǎng)格及其相連的九個(gè)網(wǎng)格。計(jì)算浮動(dòng)車(chē)點(diǎn)到路段的投影距離，進(jìn)行匹配，用以得到當(dāng)前車(chē)輛的具體行駛位置。

2 優(yōu)化的浮動(dòng)車(chē)地圖匹配方法

由上述方法可知，傳統(tǒng)網(wǎng)格地圖匹配方法所需確定的參數(shù)不多，操作簡(jiǎn)單，使用方便。但其缺點(diǎn)是在匹配過(guò)程中未考慮到車(chē)輛的行駛特性和路段之間的連通性，匹配率較低，且其在復(fù)雜的道路網(wǎng)環(huán)境中，難以實(shí)現(xiàn)?；谝陨先秉c(diǎn)，本研究在方法中融入了模糊邏輯思想，有效縮小了傳統(tǒng)網(wǎng)格匹配中網(wǎng)格搜索的待匹配路段的范圍，使得算法在準(zhǔn)確性、實(shí)時(shí)性方面達(dá)到了實(shí)際應(yīng)用的要求。

2.1 模糊邏輯推理

模糊邏輯是1965年加州大學(xué)伯克力分校Lotfi Zadeh在《Fuzzy Sets》的學(xué)術(shù)論文中提出的。20世紀(jì)80年代，E.H.Mamdani把模糊語(yǔ)言應(yīng)用在工業(yè)控制中，并提出了模糊控制論，使模糊邏輯進(jìn)入實(shí)用階段。Zhao（1997） and Kim et al.（1999）最先將模糊邏輯應(yīng)用于地圖匹配中，提出了一種模糊適用方法來(lái)確定正確的鏈路。

模糊邏輯推理算法主要分為兩大類(lèi)，Mandam型和Sugeno型，這兩種類(lèi)型的模糊邏輯推理都是If?then規(guī)則的語(yǔ)言模型。基于If?then規(guī)則的模糊邏輯是定義了一個(gè)將輸入和輸出聯(lián)系起來(lái)的模糊推理系統(tǒng)[7]。本文研究采用Sugeno型算法，其模糊推理規(guī)則如下：

If input1 is [x] and input2 is [y] then output [z=px+qy+r]

式中：p，q，r為常數(shù)；output為輸出變量；input1，input2為輸入變量；x，y為推理前模糊集合。

根據(jù)模糊推理算法原理，基于模糊數(shù)學(xué)和概率統(tǒng)計(jì)學(xué)理論，通過(guò)模糊邏輯評(píng)判各候選鏈路選擇待匹配道路。邏輯評(píng)判規(guī)則如下：

（1） 浮動(dòng)車(chē)點(diǎn)位置距待匹配路段距離是否在可靠范圍內(nèi)；

（2） 當(dāng)前車(chē)輛行駛方向是否與待匹配路段取向相同；

（3） 車(chē)輛的實(shí)時(shí)速度是否符合駛在（駛?cè)耄┐ヅ渎范我蟆?/p>

在Ochieng W.Y.等人的研究[8]中，考慮到數(shù)據(jù)的穩(wěn)定性，對(duì)浮動(dòng)車(chē)行駛方向與準(zhǔn)確匹配的道路，方向角度差范圍基本在120°以?xún)?nèi)。而考慮到由GPS定位誤差、坐標(biāo)轉(zhuǎn)換誤差、電子地圖誤差等種種原因?qū)е碌母?dòng)車(chē)本身誤差距離（10～15 m）和道路路幅寬度，浮動(dòng)車(chē)點(diǎn)到鏈路的最短距離選定為25 m。綜合評(píng)判規(guī)則，將以下三個(gè)條件同時(shí)作為浮動(dòng)車(chē)候選鏈路的確定條件：

（1） 浮動(dòng)車(chē)點(diǎn)到鏈路的最短距離（Distance）

設(shè)P（x，y）為當(dāng)前的浮動(dòng)車(chē)位置定位點(diǎn)，N1（x1，y1）為P在路段上的投影點(diǎn)，把浮動(dòng)車(chē)點(diǎn)到鏈路的垂直投影距離[d=（x-x1）2+（y-y1）2]作為其到鏈路的最短距離，節(jié)點(diǎn)處以浮動(dòng)車(chē)點(diǎn)到節(jié)點(diǎn)距離為其到鏈路的最短距離，以此距離為論域[X。]隸屬函數(shù)關(guān)系如圖1（a）所示。

（2） 浮動(dòng)車(chē)與鏈路方向角度差

以正北方向?yàn)榱愣?，浮?dòng)車(chē)行駛方向夾角與道路指向夾角之差稱(chēng)為方向角度差（Heading Angle Difference，HAD），以此角度為論域[Y。]隸屬函數(shù)關(guān)系如圖1（b）所示。

（3） 速度（velocity）

浮動(dòng)車(chē)行駛速度范圍為[0，120]，以此為論域[Z。]隸屬函數(shù)關(guān)系如圖1（c）所示。

圖1 模糊系統(tǒng)隸屬函數(shù)圖

以上述三個(gè)隸屬函數(shù)作為基礎(chǔ)，就可以對(duì)浮動(dòng)車(chē)待匹配路段的可能性做出綜合評(píng)判。取綜合隸屬函數(shù)為[U，]則論域?yàn)椋?/p>

[U=X×Y×Z={（x，y，z）x∈X，y∈Y，z∈Z}]

確定權(quán)向量[p=[a，b，c]；]其中[a，][b，][c]分別表示因素x，y，z在綜合評(píng)判中比重大小，[a+b+c=1。]在匹配過(guò)程中，考慮到方向一致平行路段易引起匹配錯(cuò)誤，設(shè)定參數(shù)[a>b，]即：距離在可信度中的權(quán)值比方向大。以此模糊邏輯推理輸出，選出各候選鏈路中可能性大的候選鏈路作為待匹配的浮動(dòng)車(chē)行駛徑路。

2.2 基于模糊的網(wǎng)格地圖匹配

根據(jù)在前述篩選出的模糊邏輯判斷的待匹配行駛路徑，用網(wǎng)格搜索匹配方法確定浮動(dòng)車(chē)在其上行駛的具體位置。其中，通過(guò)建立誤差區(qū)域排除不相關(guān)路段，減少所需計(jì)算量，定義誤差范圍。以概率統(tǒng)計(jì)法為基礎(chǔ)，定義誤差橢圓[9]，如圖2所示。

在此誤差橢圓內(nèi)，計(jì)算浮動(dòng)車(chē)點(diǎn)到待匹配行駛徑路的投影距離，取距離最短的路段進(jìn)行匹配。誤差橢圓定義：

[a=δ012δ2x+δ2y+（δ2x-δ2y）2+4δ2xyb=δ012δ2x+δ2y-（δ2x-δ2y）2+4δ2xyφ=π2-12xarctan2δxyδ2x-δ2y]

式中：[δx，δy]為傳感器向東、向北方向測(cè)量誤差的標(biāo)準(zhǔn)差；[δ2x，δ2y]為傳感器向東、向北方向測(cè)量誤差的方差；[δxy]為傳感器向東、向北方向測(cè)量誤差的協(xié)方差；[a]為誤差橢圓長(zhǎng)半軸；[b]為誤差橢圓短半軸；[φ]為誤差橢圓長(zhǎng)半軸與正北方向的夾角；[δ0]為擴(kuò)展因子（可調(diào)整以獲取不同可信度）匹配完成，如若仍找不到匹配位置，則可以改變網(wǎng)格劃分精度，細(xì)劃網(wǎng)格，再次進(jìn)行搜索、匹配，確定浮動(dòng)車(chē)位置點(diǎn)的最終匹配位置。

整個(gè)優(yōu)化匹配方法由兩個(gè)重要過(guò)程組成，通過(guò)模糊邏輯推理選定待匹配的浮動(dòng)車(chē)行駛路徑和通過(guò)網(wǎng)格搜索匹配確定浮動(dòng)車(chē)點(diǎn)的具體位置。其中可根據(jù)具體情況宏觀調(diào)控模糊邏輯隸屬規(guī)則或改變網(wǎng)格劃分方式以達(dá)到最佳匹配效果，方法流程如圖3所示。步驟如下：

（1） 數(shù)據(jù)預(yù)處理：對(duì)采集到的GPS浮動(dòng)車(chē)原始數(shù)據(jù)進(jìn)行數(shù)據(jù)的預(yù)處理[9]，剔除無(wú)效、異常數(shù)據(jù)，篩選出有效數(shù)據(jù)，提取其中經(jīng)緯度坐標(biāo)、速度、方向角等信息。保存此信息為有效定位數(shù)據(jù)。

（2） 初步定位：按照預(yù)處理過(guò)后的浮動(dòng)車(chē)車(chē)輛有效數(shù)據(jù)中的經(jīng)緯度坐標(biāo)，用Google Earth把車(chē)輛初步匹配到配準(zhǔn)好的電子地圖上，在一定范圍內(nèi)確定浮動(dòng)車(chē)匹配候選鏈路。

（3） 模糊邏輯推理：計(jì)算浮動(dòng)車(chē)點(diǎn)到鏈路的最短距離、浮動(dòng)車(chē)與鏈路方向角度差及其速度，以此為輸入，模糊判別確定行駛路徑，選擇可能性大的候選鏈路作為待匹配的浮動(dòng)車(chē)行駛路徑。

（4） 網(wǎng)格法匹配：建立路網(wǎng)組織結(jié)構(gòu)，找出浮動(dòng)車(chē)位置點(diǎn)所在網(wǎng)格中待匹配的浮動(dòng)車(chē)行駛徑路，計(jì)算其到該路徑的投影距離，選取距離最小的路徑作為最佳匹配路段，進(jìn)行匹配。

3 仿真實(shí)驗(yàn)及結(jié)果

本文采用錫林浩特市出租車(chē)GPS數(shù)據(jù)對(duì)算法進(jìn)行驗(yàn)證，接收機(jī)每隔30 s發(fā)送一次數(shù)據(jù)，樣本數(shù)量滿(mǎn)足道路信息采集需求[10?11]。算法在Matlab環(huán)境下仿真實(shí)現(xiàn)，所使用的電子地圖是錫林浩特市區(qū)街區(qū)道路矢量圖，其規(guī)模是1[∶]3 000。算法匹配結(jié)果如圖4所示，圖4（a）為浮動(dòng)車(chē)傳統(tǒng)網(wǎng)格地圖匹配車(chē)輛行駛軌跡，圖4（b）為浮動(dòng)車(chē)優(yōu)化地圖匹配車(chē)輛行駛軌跡。從圖4中可看出，相對(duì)于傳統(tǒng)網(wǎng)格匹配，優(yōu)化的匹配算法，定位點(diǎn)更能準(zhǔn)確回到車(chē)輛實(shí)際運(yùn)行的線路上，且在路段交匯處，定位點(diǎn)能基本正確匹配到路段上，匹配效果較好。

優(yōu)化的地圖匹配方法進(jìn)一步提高了匹配精度，使匹配準(zhǔn)確率達(dá)到98.8%以上且算法的計(jì)算效率較其他算法有所提高，表1列出了本文提到的幾種不同匹配算法的匹配性能比較結(jié)果，從表1可以看出，優(yōu)化的地圖匹配方法準(zhǔn)確率和計(jì)算時(shí)間均有所提高。

4 結(jié) 語(yǔ)

本文提出的優(yōu)化算法，考慮了道路網(wǎng)的復(fù)雜性和跟馳理論[12]車(chē)輛的制約性和傳遞性，在傳統(tǒng)網(wǎng)格匹配中引入模糊邏輯推理思想，選取GPS浮動(dòng)車(chē)特征數(shù)據(jù)作為輸入，按輸出可能性進(jìn)行匹配道路的篩選，再進(jìn)行匹配。這種模糊評(píng)判行駛路徑的選擇，保證正確路段在待匹配道路中，在減少網(wǎng)格搜索時(shí)間的同時(shí)克服了潛在的匹配錯(cuò)誤。數(shù)據(jù)結(jié)果表明，優(yōu)化匹配方法的實(shí)時(shí)性好、準(zhǔn)確率高，且對(duì)樣本數(shù)量需求較低。此數(shù)據(jù)來(lái)源真實(shí)，可信度高。鑒于城市發(fā)展之迅速，道路的實(shí)時(shí)狀況、浮動(dòng)車(chē)的駕駛行為等因素也會(huì)影響到地圖匹配算法的精度，如何考慮更多的因素，確定車(chē)輛在道路中的準(zhǔn)確行駛位置是一個(gè)難點(diǎn)，將會(huì)成為下一步研究的重點(diǎn)。

參考文獻(xiàn)

[1] 吳佩莉，劉奎恩，郝身剛，等.基于浮動(dòng)車(chē)數(shù)據(jù)的快速交通擁堵監(jiān)控[J].計(jì)算機(jī)研究與發(fā)展，2014（1）：189?198.

[2] KLEIN L A. Sensor technologies and data requirements for ITS [M]. Boston： Arrech House， 2001.

[3] 耿小峰，王山東，季軍.浮動(dòng)車(chē)快速道路匹配算法[J].水利與建筑工程學(xué)報(bào)，2013，11（1）：122?125.

[4] 蘇海濱，王光政，王繼東，等.基于模糊神經(jīng)網(wǎng)絡(luò)的地圖匹配算法[J].北京科技大學(xué)學(xué)報(bào)，2012，34（1）：43?47.

[5] 李珂，楊揚(yáng)，邱雪松.城市汽車(chē)導(dǎo)航中一種改進(jìn)的D?S證據(jù)理論地圖匹配算法[J].測(cè)繪學(xué)報(bào)，2014，43（2）：208?213.

[6] YANG Hai?qiang， CHENG Shao?wu， JANG Hui?fu， et al. An enhanced weight?based topological map matching algorithm for intricate urban road network [C]// Proceedings of the 13th COTA International Conference of Transportation Professionals on Intelligent and Integrated Sustainable Multimodal Transportation Systems. [S.l.]： COTA， 2013， 96： 1670?1678.

[7] 劉宇環(huán).浮動(dòng)車(chē)地圖系統(tǒng)匹配算法及信息采集周期優(yōu)化的研究[D].北京：北京交通大學(xué)，2012.

[8] 蘇海濱，陳永利，劉強(qiáng).基于權(quán)重的地圖匹配算法[J].華北水利水電學(xué)院學(xué)報(bào)，2008，29（1）：81?83.

[9] 鄒珍.基于GPS的浮動(dòng)車(chē)數(shù)據(jù)與實(shí)地圖匹配的算法研究[D].武漢：武漢理工大學(xué)，2013.

[10] 廖孝勇，孫棣華，周舒杰，等.混合浮動(dòng)車(chē)交通狀態(tài)估計(jì)的樣本數(shù)量研究[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（24）：229?232.

[11] LIU X B， CHIEN S， KIM K. Evaluation of floating car technologies for travel time estimation [J]. Journal of Modern Transportation， 2012， 1（1）： 49?56

[12] 徐吉謙，陳學(xué)武.交通工程總論[M].3版.北京：人民交通出版社，2008.