一種基于浮動車優化地圖匹配方法

田甜　呂芳　王秀玲

摘 要： 地圖匹配方法，對于浮動車技術有著重要的意義。由于浮動車數據自身的特點，傳統的地圖匹配算法難以直接應用在城市道路浮動車數據匹配上。針對目前浮動車地圖匹配算法應用于城市復雜路網時只考慮單一車輛位置數據，聯動性研究較少，導致產生匹配精度不高的問題，考慮車輛運行特征與道路路網的連通信息，同時結合動態GPS數據， 把模糊邏輯推理思想引入到網格地圖匹配方法中，提出一種優化的地圖匹配方法，并對其有效性進行了驗證。研究表明，優化浮動車地圖匹配方法在保持網格地圖匹配實時性優點的同時，提高了算法的匹配精度。

關鍵詞： 浮動車； GPS； 模糊邏輯； 地圖匹配

中圖分類號： TN957.52+9； U495 文獻標識碼： A 文章編號： 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 引 言

交通擁堵現已成為困擾現代城市發展的嚴重問題，及時反映交通狀況，采取合理的預警措施，避免交通擁堵，已成為智能交通領域亟需解決的問題[1]。而隨著科技的進步，以固定型交通采集技術[2]為主的傳統交通信息采集方式，已經不能夠適應快速增長的道路數量和車輛保有量。浮動車技術作為一種嶄新的城市路況信息獲取、道路建設和出行規劃方式，逐步成為研究熱點。

浮動車數據地圖匹配是浮動車技術中亟需解決的關鍵性問題。然而，現有的地圖匹配算法如耿小峰等利用道路幾何特征對車輛進行地圖匹配[3]；蘇海濱等引用模糊神經網絡對車輛特征變量進行學習[4]，提高算法容錯能力；李珂等基于D?S證據理論的地圖匹配算法通過建立信任函數和證據融合，考察可達性進行匹配選擇[5]；楊海強等基于權重的匹配方法考慮定位點時間間隔，充分運用定位信息以加強匹配效果[6]。總的來說，現有算法多重視匹配準確率，少有考慮車輛行駛特點及道路網間復雜連通信息，導致其應用性欠妥。而基于網格搜索的地圖匹配，算法概念簡單，易于編碼實現，滿足浮動車匹配的實時性要求，但其在彎道或道路密集的交叉口等路況復雜時匹配率較低。本文考慮浮動車數據特點及道路網連通信息，把模糊邏輯推理思想引入到網格地圖匹配方法中，提出了一種優化的地圖匹配方法，在保持浮動車數據地圖匹配實時性要求的同時，有效提高了算法的匹配精度。

1 傳統的網格地圖匹配方法

通過網格劃分將電子地圖路網劃分為多個網格并進行編號，根據GPS定位點快速搜索浮動車點相對于電子地圖的位置進行匹配。

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

2 優化的浮動車地圖匹配方法

由上述方法可知，傳統網格地圖匹配方法所需確定的參數不多，操作簡單，使用方便。但其缺點是在匹配過程中未考慮到車輛的行駛特性和路段之間的連通性，匹配率較低，且其在復雜的道路網環境中，難以實現。基于以上缺點，本研究在方法中融入了模糊邏輯思想，有效縮小了傳統網格匹配中網格搜索的待匹配路段的范圍，使得算法在準確性、實時性方面達到了實際應用的要求。

2.1 模糊邏輯推理

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

模糊邏輯推理算法主要分為兩大類，Mandam型和Sugeno型，這兩種類型的模糊邏輯推理都是If?then規則的語言模型。基于If?then規則的模糊邏輯是定義了一個將輸入和輸出聯系起來的模糊推理系統[7]。本文研究采用Sugeno型算法，其模糊推理規則如下：

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

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

根據模糊推理算法原理，基于模糊數學和概率統計學理論，通過模糊邏輯評判各候選鏈路選擇待匹配道路。邏輯評判規則如下：

（1） 浮動車點位置距待匹配路段距離是否在可靠范圍內；

（2） 當前車輛行駛方向是否與待匹配路段取向相同；

（3） 車輛的實時速度是否符合駛在（駛入）待匹配路段要求。

在Ochieng W.Y.等人的研究[8]中，考慮到數據的穩定性，對浮動車行駛方向與準確匹配的道路，方向角度差范圍基本在120°以內。而考慮到由GPS定位誤差、坐標轉換誤差、電子地圖誤差等種種原因導致的浮動車本身誤差距離（10～15 m）和道路路幅寬度，浮動車點到鏈路的最短距離選定為25 m。綜合評判規則，將以下三個條件同時作為浮動車候選鏈路的確定條件：

（1） 浮動車點到鏈路的最短距離（Distance）

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

（2） 浮動車與鏈路方向角度差

以正北方向為零度，浮動車行駛方向夾角與道路指向夾角之差稱為方向角度差（Heading Angle Difference，HAD），以此角度為論域[Y。]隸屬函數關系如圖1（b）所示。

（3） 速度（velocity）

浮動車行駛速度范圍為[0，120]，以此為論域[Z。]隸屬函數關系如圖1（c）所示。

圖1 模糊系統隸屬函數圖

以上述三個隸屬函數作為基礎，就可以對浮動車待匹配路段的可能性做出綜合評判。取綜合隸屬函數為[U，]則論域為：

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

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

2.2 基于模糊的網格地圖匹配

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

在此誤差橢圓內，計算浮動車點到待匹配行駛徑路的投影距離，取距離最短的路段進行匹配。誤差橢圓定義：

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

式中：[δx，δy]為傳感器向東、向北方向測量誤差的標準差；[δ2x，δ2y]為傳感器向東、向北方向測量誤差的方差；[δxy]為傳感器向東、向北方向測量誤差的協方差；[a]為誤差橢圓長半軸；[b]為誤差橢圓短半軸；[φ]為誤差橢圓長半軸與正北方向的夾角；[δ0]為擴展因子（可調整以獲取不同可信度）匹配完成，如若仍找不到匹配位置，則可以改變網格劃分精度，細劃網格，再次進行搜索、匹配，確定浮動車位置點的最終匹配位置。

整個優化匹配方法由兩個重要過程組成，通過模糊邏輯推理選定待匹配的浮動車行駛路徑和通過網格搜索匹配確定浮動車點的具體位置。其中可根據具體情況宏觀調控模糊邏輯隸屬規則或改變網格劃分方式以達到最佳匹配效果，方法流程如圖3所示。步驟如下：

（1） 數據預處理：對采集到的GPS浮動車原始數據進行數據的預處理[9]，剔除無效、異常數據，篩選出有效數據，提取其中經緯度坐標、速度、方向角等信息。保存此信息為有效定位數據。

（2） 初步定位：按照預處理過后的浮動車車輛有效數據中的經緯度坐標，用Google Earth把車輛初步匹配到配準好的電子地圖上，在一定范圍內確定浮動車匹配候選鏈路。

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

（4） 網格法匹配：建立路網組織結構，找出浮動車位置點所在網格中待匹配的浮動車行駛徑路，計算其到該路徑的投影距離，選取距離最小的路徑作為最佳匹配路段，進行匹配。

3 仿真實驗及結果

本文采用錫林浩特市出租車GPS數據對算法進行驗證，接收機每隔30 s發送一次數據，樣本數量滿足道路信息采集需求[10?11]。算法在Matlab環境下仿真實現，所使用的電子地圖是錫林浩特市區街區道路矢量圖，其規模是1[∶]3 000。算法匹配結果如圖4所示，圖4（a）為浮動車傳統網格地圖匹配車輛行駛軌跡，圖4（b）為浮動車優化地圖匹配車輛行駛軌跡。從圖4中可看出，相對于傳統網格匹配，優化的匹配算法，定位點更能準確回到車輛實際運行的線路上，且在路段交匯處，定位點能基本正確匹配到路段上，匹配效果較好。

優化的地圖匹配方法進一步提高了匹配精度，使匹配準確率達到98.8%以上且算法的計算效率較其他算法有所提高，表1列出了本文提到的幾種不同匹配算法的匹配性能比較結果，從表1可以看出，優化的地圖匹配方法準確率和計算時間均有所提高。

4 結 語

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

參考文獻

[1] 吳佩莉，劉奎恩，郝身剛，等.基于浮動車數據的快速交通擁堵監控[J].計算機研究與發展，2014（1）：189?198.

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

[3] 耿小峰，王山東，季軍.浮動車快速道路匹配算法[J].水利與建筑工程學報，2013，11（1）：122?125.

[4] 蘇海濱，王光政，王繼東，等.基于模糊神經網絡的地圖匹配算法[J].北京科技大學學報，2012，34（1）：43?47.

[5] 李珂，楊揚，邱雪松.城市汽車導航中一種改進的D?S證據理論地圖匹配算法[J].測繪學報，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] 劉宇環.浮動車地圖系統匹配算法及信息采集周期優化的研究[D].北京：北京交通大學，2012.

[8] 蘇海濱，陳永利，劉強.基于權重的地圖匹配算法[J].華北水利水電學院學報，2008，29（1）：81?83.

[9] 鄒珍.基于GPS的浮動車數據與實地圖匹配的算法研究[D].武漢：武漢理工大學，2013.

[10] 廖孝勇，孫棣華，周舒杰，等.混合浮動車交通狀態估計的樣本數量研究[J].計算機工程與應用，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] 徐吉謙，陳學武.交通工程總論[M].3版.北京：人民交通出版社，2008.