基于動態規劃算法的軌跡地圖匹配軟件設計與實現

姜雪原

摘要：針對智能交通領域中動態軌跡點的地圖匹配問題，提出并設計了一種基于動態規劃算法的軌跡匹配軟件，并在路網拓撲構建、最短路徑計算方面進行改進優化，提升了軟件工作性能。工程應用表明，該軟件具有較好的計算精度和效率。

關鍵詞：地圖匹配；GPS軌跡；路網拓撲

中圖分類號：P208 文獻標識碼：A DOI：10.3969/j.issn.1003-6970.2015.05.023

0 引言

智能交通系統（ITS）應用越來越廣泛，常見的包括車輛導航、交通流量分析、位置服務（LBS）等。能夠提供位置信息的傳感器主要是安裝在車輛、手機等移動終端上的GPS設備。連續的GPS采樣點就形成了運動軌跡，由于GPS的采樣精度和頻率、建筑物遮擋等原因，使得軌跡無法直接與道路網絡（簡稱“路網”）重合，存在一定誤差。通過一定算法使得軌跡與數字地圖中的相應道路重合的過程稱為“軌跡匹配”。軌跡匹配的實現能夠為車輛導航、交通流量實時分析、公交線網分析等應用提供較大支撐能力。

1 相關研究

軌跡地圖匹配軟件的核心模塊就是軌跡匹配算法。在軌跡匹配的相關算法資料中，主要分為局部匹配和全局匹配兩類。局部匹配適合于解決在線實時應用問題，全局匹配適合于解決離線應用問題。

局部匹配算法主要是利用當前GPS軌跡點與候選道路幾何關系及前后相鄰軌跡點的關聯信息來進行匹配的。文獻[4]采用軌跡點與道路的方向權重、軌跡點到道路的距離權重、歷史信息權重的綜合來完成軌跡匹配。然而由于局部匹配算法僅采用區域范圍內的軌跡點信息，所以僅適合于高采樣頻率軌跡的實時地圖匹配情況。特別是由于沒有全面考慮到道路拓撲關系，在復雜路網情況下，容易導致誤匹配。

全局匹配算法主要是利用道路拓撲網絡來匹配整個GPS軌跡。文獻[5]使用Frechet距離作為權重來構建拓撲網絡圖，采用最短路徑算法得到匹配道路。文獻[6]使用曲線相似度計算來進行軌跡匹配。然而，全局匹配算法比較明顯問題就是算法實現復雜、計算量大，有一定應用的局限性。

使用隱馬爾科夫（HMM）等概率統計算法，以及多假設技術（MHT）來解決軌跡匹配問題也是對匹配算法的重要補充。

本文工作主要是基于動態規劃的全局匹配算法，設計并實現了一套軟件來解決離線軌跡匹配的問題。

2 軟件構成與功能

軌跡地圖匹配軟件主要由路網拓撲軟件和地圖匹配軟件兩部分組成。

路網拓撲軟件的主要功能是基于導航電子地圖數據構建道路拓撲網絡，為地圖匹配軟件提供路網拓撲結構。

主要的工作流程如圖l所示，首先讀取電子地圖數據，并可對數據進行修改和編輯，然后加載全部路網數據，并對路網數據進行預處理（驗證數據和格式的有效性），基于預處理后數據構建路網拓撲，最后對拓撲結構進行驗證，并發布為路網數據。

地圖匹配軟件的主要功能是基于路網拓撲數據完成對軌跡數據的地圖匹配，支持單軌跡匹配及多軌跡批量匹配，并可對匹配結果進行展示和編輯。

主要工作流程如圖2所示，首先加載軌跡數據文件并進行初始化，然后對軌跡數據進行檢查和重采樣，基于匹配算法進行軌跡匹配，可基于地圖實現結果展示及編輯，最后進行匹配結果的發布。

3 關鍵技術及算法設計

3.1 路網拓撲構建

路網拓撲構建主要是利用電子地圖中的節點和線數據構建拓撲結構圖，如圖3所示。路網拓撲構建是軌跡匹配前的必要工作，路網拓撲的質量也對地圖匹配的效率和準確性至關重要。

路網拓撲構建的主要步驟包括：數據預處理、數據校驗、拓撲建立、拓撲驗證。

數據預處理是根據道路等級、可通行等屬性對道路進行過濾，以減少道路數量，提升查詢和搜索效率。

數據校驗主要進行剔除未與道路連接的節點、邊界道路補點、以及圖幅拼接問題，從而保證路網數據的完整性和一致性。