GPS物流車輛導航系統中地圖匹配算法的實現

滕威

(陜西交通職業技術學院 經濟管理學院， 陜西 西安 710014)

0 引言

目前車輛監控系統主要通過結合使用GPS定位及計算機數據處理等技術手段實現車輛監控過程，物流行業隨著電子商務的快速發展而得以快速成長和完善，在社會經濟中起到非常重要的作用，行業內的競爭也愈發激烈，科學高效的物流信息系統有助于物流企業提升競爭力，而作為物流信息系統的關鍵環節之一，定位系統對物流信息系統產生直接影響，因此提升物流信息系統的質量需最大程度減小定位誤差，將更加穩定可靠的服務提供給用戶，目前多種車輛定位技術在資源等原因的限制下存在不同程度的誤差，本文完成了物流車輛運輸定位監控系統的設計，系統基于GPS的地圖匹配技術，具有較高的實際應用價值。

1 物流行業需求分析

物流管理的主要目的在于降低成本的同時提升服務水平，對車輛的詳細信息能夠做到及時準確掌握和獲取十分重要的作用，信息技術的使用為物流運輸管理提供了有利支撐，在物流企業的發展過程中，4G (GPS/GIS/GSM/GPRS)起到了積極的促進作用，物流車的GPS監控和管理功能的有效實現對物流行業具有重要意義。物流行業的實際發展過程中所表現出的主要需求特點在于：物流業務范圍及覆蓋地域極為廣泛，運輸車輛較多，涵蓋了大量的數據信息；用戶大多要求及時掌握位置服務信息，在運輸過程中需對不同的區域和線路進行嚴格準確的監控，并同貨運單據有效對接起來；要求具有較高的安全性，運輸監控系統響應需靈活、及時；要求車輛定位監控系統中的數據具有較高的共享程度。車輛管理信息有待進一步完善，本文主要對物流車輛運輸定位監控系統進行了設計[1]。

2 車輛運輸定位監控系統設計

2.1 GPS車輛管理系統功能

本文所設計的系統基于GPS的地圖匹配技術，具備動態、實時、精確、雙向等優勢，核心在于能夠進行遠程指揮和監控的管理平臺，通過將GPS監控設備安裝在運輸車輛上，通過設備上的GPS模塊即可將運輸車輛的地理位置信息傳輸至監控中心(通過無線網絡)，通過電子地圖即可查看車輛所在的具體地理位置，實現遠程監控，同時可對常用功能進行設置(上傳間隔、車輛信息記錄等)，遠程控制設備通過發放指令實現對啟動狀態等的限制。

完整的監控系統由GPS終端、傳輸網絡及監控平臺3個要素構成，GPS/GSM/CDMA車載終端與中心間的通訊連接以網絡為載體實現，具有較高的數據傳輸能力，查詢監控的時效性更高，誤碼率比較低，可有效實現較大范圍穩定可靠的監控過程。將GPS終端安裝在不同的車輛上，通過GPRS/CDMA無線通信網絡或短信的方式完成數據傳輸，GSM網絡主要負責將GPS定位和收集到的信息傳遞至信息調度中心，及時掌握入網移動目標的地理位置，再將調度中心的信息傳輸給不同的車載設備，實現不同車輛具體地理位置信息的檢測及確定(顯示在電子地圖上)，在此基礎上可實現安全有效的監控和調度。此外還可實現導航的過程，具體如圖1所示。

圖1 導航處理過程

在地圖上尋找起始和終點間的最優路線，使穿越耗時最少[2]。

2.2 地圖匹配算法

指通過載體上的GPS接收機設備完成地理位置的確定，在復雜的交通網中完成車輛的精確定位并實時更新，不斷更正地理位置。地圖匹配過程的順序為：首先通過使用GPS系統確定車輛行駛路線，在將其同電子地圖中的行駛路線比對，找出最優路線，所使用的電子地圖匹配算法會對車輛定位的準確度產生直接影響，該算法的重點在于找到校正點，具體的算法流程為：(1) 首先以車輛所在的位置為圓心，根據實際需要恰當選取半徑后畫圓，判斷公路圖層中對象同圓間的位置關系(相交則計算相交對象的個數)，對于一個以上的對象需縮小圓的半徑，無對象則擴大圓的半徑直至找到符合條件的對象(圓的半徑大于限定值時表示車輛進入了停車場類的位置，則以圓心為校正點跳至第四步)。(2) 根據不同判斷時間存在循環中公路對象名稱不一致的情況，若相同則表明兩點位于同一公路，可直接跳至第四步；若不一致，則可能存在車拐彎情況，無法判斷車輛點同時保存記錄(包括車輛點和最近路線)，若需取下一個點則返回步驟(1)重新開始。(3) 對公路對象的全部拐點進行讀取，找出車輛點到相鄰兩拐點連線的垂足，計算出車輛點同垂足的距離，有垂足且距離最小時垂足即為校正點。(4) 標記所獲取的校正點，取下一車輛點進行判斷[3]。

2.3 基于曲線擬合的地圖匹配算法

矢量電子地圖由圖元組成道路，各元位置精確，電子地圖中的道路通常由直線或折線表示，能夠用直線來模擬歷史行車軌跡(在一定行駛距離內)，本文擬合用直線，選取5個觀測點作為一次模擬曲線，即用直線來擬合，具體原理如下。

5個觀測點的平面坐標由(x,y)表示，據此計算軌跡擬合直線的斜率為式(1)。

(1)

判斷車輛可能的行駛方向k，在路段誤差范圍內(軌跡夾角小于30度)，需對車輛位置信息進行再次確認，考慮到GPS自身存在的誤差，候選路段需在被測位置點方圓60 m內，k0表示候選路段的斜率，k表示擬合直線的斜率；對于候選路段同測位置點，d表示其垂直投影距離；P1表示夾角；P2表示距離的權值，地圖匹配算法的評價函數s表達式如式(2)。

(2)

最小值即為最優匹配路段[4]。

2.4 基于權重的地圖匹配算法

車輛當前行駛道路以根據道路交通網絡的弧確定的權重為依據，然后確定車輛在當前道路中的位置(即在當前道路上車輛定位點的投影點)，以定位點和道路交通網的弧間的關系為依據確定權重的計算模型[5]，如圖2所示。

圖2 定位點和道路交通網的關系

取n個GPS定位點，各候選道路施加的權重為平均值，以消除偶然誤差的影響，C表示權重為正值的常數值；i表示候選道路的編號;kd表示GPS定位點同道路間的投影距離;ko表示行駛方向同道路間的夾角θi的權值系數，則對各候選道路施加的權重[5]表示如式(3)。

ωi=C-(kd×di+kθ×θi)

(3)

3 地圖匹配算法的實現

3.1 運輸導航的最短路徑算法

物流運輸需從當前位置到達指定位置，最短路徑在于花費最低的代價到達目的地，最佳路徑即為綜合代價最低的路徑，電子地圖導航的搜索最佳路徑功能可有效滿足用戶需求，通過使用某種特定準則的算法實現最優路徑搜索功能，在道路交通拓撲網絡中，以節點—弧線拓撲關系和算法為依據，完成最佳路線的獲取，公路交通網絡中適合使用Dijkstra算法，具體流程如圖3所示。

圖3 Dijkstra算法流程

該算法基于現實情況，尋找節點間的最短路線，算法結束時即為找到了最短路線[6]。

3.2 道路搜索的實現

無法確定車輛初始定位、車輛行駛道路時需進行道路搜索，具體流程如下。

(1) 獲取特定時刻的具體定位后，根據行駛速度值m-speed及PDOP值進行預估，通常在PDOP>6，m-speed>200時表明GPS接收機定位異常，但在道路搜索狀態下需結合下一個定位點信息通過再次搜索進行判斷；PDOP<6、0

(2) 對(1)中的路線進行區域再次篩選，以定位點為圓心、半徑為GPS實時水平的HPE值的二倍，可進一步縮小待匹配路段范圍，直接確定車輛具體所處路段，將相關篩選結果信息保存至指定的結構數組中。若直線數量為m=0，則車輛在該定位點所處的圓域中，若不待匹配路段存在，則繼續道路搜索；若m=1，則該路段可作為車輛目前行駛的道路，道路搜索結束。

(3) 當定位點周圍的道路集中且密度大時，則需展開第三次篩選，有效篩選余下的待匹配路段，需使用精確度較高的篩選方法，在m-speed<8的情況下，GPS接收機給出的方向可信度不高，需根據實際行駛速度進行二次篩選，具體處理方法為：0

篩選結束后選擇范圍僅包括某一線段的道路，即作為該車輛的行駛道路，并傳輸至“正常行駛”的匹配過程。若經過多次道路搜索后仍未完成最優匹配路線的確定，則最終定位結果以原始的定位數據為準，無需誤差校正[6]。

3.3 道路轉換

(1) 將正常行駛時存儲的所有節點編號提出來，再將同該節點相關的所有道路信息通過使用GPS導航中的拓撲關系提取出來，若只有1條道路相連，則該節點只對車輛剛途徑的路段進行顯示，無后續路段，不符合地圖匹配的假設條件，需重新進行道路搜索。

(2) 若與該節點連接道路大于1條，則需將車輛剛途徑的道路信息從所提取的道路信息中刪除，此時剩余道路為1條則代表其屬于下一匹配的路段，結束道路轉換；如果此時剩余道路大于1條則需進行第二次篩選，處理過程同道路搜索的第三次篩選相同，在計算和處理各候選道路權重時，只需適當提高角度權值系數，在此基礎上完成最優匹配道路的確定并保存，向正常行駛匹配階段轉換[7]。

4 總結

隨著GPS導航定位系統和電子狗的普及應用，GPS數據量隨之逐漸增加，海量數據的地圖匹配亟待解決，處理的關鍵在于具備較高的計算效率及匹配精度，以滿足數據實時性匹配需求。地圖匹配的發展趨勢呈現出多種匹配算法的融合，高級的地圖匹配算法比較復雜、精準度較高，適合復雜的道路，以當前的交通擁堵狀況為依據并綜合多種因素得出最優路線，本文在對物流行業需求進行分析的基礎上，完成了物流車輛運輸定位監控系統的設計，詳細闡述了地圖匹配算法及流程，并介紹了物流運輸導航的最短路徑算法，實現了地圖匹配算法，使物流車輛運輸定位監控能力得以顯著提升，對海量數據的處理速度及匹配精度的進一步提高將是下一步研究的重點。