[發明專利]基于拓撲和權重的超標排放車輛最短路徑跟蹤匹配方法

在審

• 申請號: 201810192623.1
• 申請日: 2018-03-09
• 公開（公告）號: CN108571978A
• 公開（公告）日: 2018-09-25
• 發明（設計）人: 蔣鵬;孫浩澤;佘青山
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 杭州君度專利代理事務所(特殊普通合伙) 33240
• 代理人: 朱月芬

1.基于拓撲和權重的超標排放車輛最短路徑跟蹤匹配方法，其特征在于：該方法具體包括以下步驟；

步驟一：數據清洗；進行刪除無效數據和重復數據，其中在每個GPS定位數據輸入之前對無效數據進行處理，先將跟蹤匹配區域的經度和緯度范圍作為條件添加到輸入的判斷條件，如果輸入的GPS定位數據不符合該條件，那么刪除該無效數據進行下一個數據的輸入判斷；重復數據對應著超標排放車輛的狀態為駐車，遙測設備一直監測到同一輛超標排放車輛的本體數據以及定位數據超過一段時間不發生變化，本體數據指車牌、車型、車身顏色；注意不發生變化并不是指超標排放車輛的數據所有屬性均為一個固定值，GPS定位數據與定位時間還是會發生變換；

步驟二：一般提取和構建道路網絡的拓撲結構是指：從電子地圖中提取道路網絡中各個路段的屬性數據以及各交叉路口的坐標信息，并利用提取的網絡拓撲信息，構建道路網絡拓撲結構；

道路網絡的拓撲構建就是根據拓撲關系把地理空間數據進行組織，表現在道路網絡中就是記錄和表示每條道路與對應節點之間的相互連通和關聯的情況；

步驟三：在步驟二的拓撲約束條件下，再結合空間約束構建出超標排放車輛軌跡跟蹤的鄰近候選路段集合，把候選路段的距離、方向和相對位置關系三個權重值之和作為求解最短路徑的條件，以鄰近候選路段集合中軌跡起點至終點的最短路徑作為匹配結果；

通過Dijkstra算法確定跟蹤匹配路徑的連接關系，候選路段本身包含路徑長度信息，運用候選路段總權重，將路段長度除以該路段的總權重得到新權值，創建出新的加權圖，權為非負數，利用Dijkstra算法求解；

①、輸入一個非負有向圖G(V,E)，其中V、E均為集合，分別用來存放所有的頂點、所有的邊，而函數W:定義的是邊的新權值；

②、設置一個輔助數組Dist，其中每個分量Dist[i]表示當前所求的從起始點到其余各個頂點v_i(v_i∈V)的最短路徑長度；在所有從起點出發的路段中選取一條權重最小的路段，即為第一條最短路徑；

③、設置一個頂點集合S，用來存放已求得最短路徑終點，在進行路徑探索之前S中只包含起點v，再計算起點到其他各個頂點的距離，選取路徑最短的那個頂點U加入到S中；從集合V-S中選取具有最短特殊路徑的頂點l，作為下次最短路徑探索的起點，同時對數組Dist做相應的修改:

若Dist[i]+W(v_i,v_j)<Dist[j]，則將Dist[i]+W(v_i,v_j)替換Dist[j]；

④、重復步驟②、③，直至所有的項點都加入到S中。

2.根據權利要求1所述的基于拓撲和權重的超標排放車輛最短路徑跟蹤匹配方法，其特征在于：在選取鄰近候選路段時，GPS定位點的緩沖半徑為40m。

3.根據權利要求1所述的基于拓撲和權重的超標排放車輛最短路徑跟蹤匹配方法，其特征在于：采用基于廣度優先遍歷的源點擴散法實現拓撲構建，得到各路段節點間拓撲結構信息。