[發明專利]行駛速度限定的浮動車地圖匹配加速方法

有效

• 申請號: 201410320935.8
• 申請日: 2014-07-08
• 公開（公告）號: CN104061935B
• 公開（公告）日: 2017-01-25
• 發明（設計）人: 曾喆;黃榮剛;張彤;劉善偉
• 申請（專利權）人: 中國石油大學（華東）
• 主分類號: G01C21/30
• 分類號: G01C21/30
• 代理公司: 濟南舜源專利事務所有限公司37205
• 代理人: 王連君

1.行駛速度限定的浮動車地圖匹配加速方法，其特征在于，包括如下步驟：

S1、計算浮動車地圖匹配的最短路徑上界B：

S11、從道路網絡中所有道路弧段的限速值中取出最大限速值v_max，將該最大限速值v_max上浮40％得到速度閾值v_限閾，v_限閾＝(1+0.4)*v_max；

S12、根據待匹配浮動車軌跡的采樣時間間隔T，計算相鄰軌跡點在道路網絡中的最短路徑上界B，B＝v_限閾*T；

S2、對道路網絡進行分割：

首先計算道路網絡的最小外接矩形，然后對道路網絡進行格網分割，

設定道路網絡節點的數量為N、分割閾值為M，N、M均為自然數，且N大于M，計算大于N/M的最小偶數m；找到m的一個因子分解m＝m1*m2，使得m1和m2滿足m1與m2之比和道路網絡的最小外接矩形長寬比最接近，令m1為行數目，m2為列數目，建立基準格網；每個基準格網內道路網絡節點的數量不大于M個；

將每個基準格網的邊界向外拓展長度為B的寬度后得到擴展格網，計算每個擴展格網內部所包含的道路弧段與節點；

S3、在步驟S2得到的每個擴展格網內的道路網絡中，通過改進后的dijkstra算法計算小于步驟S12得到的最短路徑上界B的所有最短路徑：

S31、初始化擴展格網內道路網絡G(V，E)中所有節點對的距離標號表d及前驅節點對表pre，其中，V表示道路網絡中所有節點集，E表示道路網絡中所有道路弧段集；

如果節點對(v,w)的兩節點不是同一節點且通過一條弧段直接相連，則其距離標號d(v,w)設為弧段長度l(v,w)，并將這些節點對(v,w)放入權重最小優先隊列Q中，其在優先隊列Q中的優先權重為d(v,w)，前驅節點對pre(v,w)＝0；

如果節點對(v,w)的兩節點不是同一節點且不通過一條弧段直接相連，則將距離標號d(v,w)設為64位浮點數可表達的最大浮點數dbM；

如果節點對(v,w)的兩節點為同一節點，則距離標號d(v,w)設為0；

S32、重復執行步驟S33～S34，直到優先隊列Q為空、或者優先隊列Q的最小權重值大于步驟S12得到的最短路徑上界B時，轉到步驟S35；

S33、從優先隊列Q中得到權重最小的節點對(v,w)，將其從優先隊列Q中去除；

S34、對于道路網絡中從w出發的所有道路弧段(w,u)，計算d(v,w)+l(w,u)：

如果d(v,w)+l(w,u)<d(v,u)，并且d(v,u)是最大浮點數dbM，則將節點對的距離標號d(v,u)改為d(v,w)+l(w,u)，并將節點對(v,u)加入優先隊列Q中，其前驅節點對pre(v,u)＝(v,w)；

如果d(v,w)+l(w,u)<d(v,u)，并且d(v,u)不是最大浮點數dbM，則將節點對的距離標號d(v,u)改為d(v,w)+l(w,u)，將其在優先隊列Q中的優先權重也重設為d(v,u)，其前驅節點對pre(v,u)＝(v,w)；

S35、保存擴展格網內道路網絡中的所有節點對的最短距離表d和前驅節點對表pre；

S4、在前后軌跡點的候選路段對之間關聯匹配中，首先根據坐標計算前后軌跡點屬于哪個基準格網Ri，然后根據步驟3確定該基準格網Ri內道路網絡中的所有節點對距離表和前驅節點對表的位置；

S5、設定前后軌跡點對應的候選路段對為(e1，e2)，取弧段e1的終止節點v1，e2的起始節點v2，同時計算前一軌跡點到e1的垂足沿弧段e1到v1的距離l1，v2沿弧段e2至后一軌跡點到e2的垂足的距離l2；

S6、以起始點v1、終止點v2為一節點對(v1,v2)，在基準格網Ri的節點對距離表d中直接查詢出其最短路徑距離為dsp，則前一軌跡點在e1上垂足到后一節點在e2上的垂足的距離為l1+l2+dsp；

S7、在基準格網Ri的所有節點對的前驅結點表中，回溯恢復v1到v2的最短路徑：

S71、將v2放入一個隊列H中，H初始化為空，從隊列H尾插入v2；

S72、取出節點對(v1,v2)的前驅pre(v1,v2)對(v1,x)，將x從隊列H尾插入；

S73、將步驟S72中節點對(v1,v2)替換為取出的(v1,x)，重復執行步驟S72，直到取出節點對的前驅為0終止；終止后將v1從隊列H尾插入；

S74、將隊列H中的節點序反向，即為v1至v2的最短路徑。