[發明專利]一種通過GPS推斷公交路徑方法

有效

• 申請號: 201711133079.5
• 申請日: 2017-11-15
• 公開（公告）號: CN108132056B
• 公開（公告）日: 2021-04-30
• 發明（設計）人: 孫傳平;邢健;程磊
• 申請（專利權）人: 北京通途永久科技有限公司
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 北京思海天達知識產權代理有限公司 11203
• 代理人: 沈波

1.一種通過GPS推斷公交路徑方法，將所需計算的城市按城市范圍以0.005度作為間隔劃分為n*m個網格LinkGrid組成的矩陣LinkMatrix，n為網格的行數，m為網格的列數；將導航圖中的每條路鏈Link緩存到內存中，將每條路鏈按照兩兩點拆分為有序的路鏈段LinkSection，用于導航圖的匹配；根據LinkSection與LinkGrid的關系，在每個LinkGrid中保存所覆蓋的LinkSection列表；

從每條路鏈起始，生成500米范圍內的路鏈行駛樹RouteTree，路鏈行駛樹的每個節點RouteLinkNode即是一條路鏈，保存了從路鏈行駛樹的根路鏈到此路鏈的行駛距離，其父節點id，此路鏈行駛樹在此路鏈上的行駛方向信息，用于路徑推測，為從右上角加粗路鏈出發，500米范圍內所能到達的所有路鏈；

其特征在于：該方法的實現包括以下步驟，

步驟1：數據預處理

去除車輛位于首末站或首末站的公交場站內的速度為0的點及進出場站的不規則運動方向點；

對于存在首末站中間GPS數據丟失的情況，如果首末站中間GPS數據丟失超過3分鐘，則將首末站中間的路段拆分為兩段，并分別進行匹配；

計算每個GPS序列中的點與前后兩點連線的方向，丟棄存在前后方向差別大的異常點；

步驟2：地圖匹配

1)循環GPS序列中的點，將經緯度轉換為LinkMatrix中的行列號，獲取行列號上所屬的LinkGrid及周邊的八個LinkGrid；

2)循環所有LinkGrid所覆蓋的所有LinkSection，判斷點的距離及行駛方向與LinkSection的關系，對于同一條Link上的多個LinkSection，用距離近的替換遠的；

3)循環找到的所有在匹配距離及匹配角度內的Link，根據匹配距離及匹配角度計算匹配相關度，并按相關度排序，丟棄相關度低或點匹配到路鏈兩端的情況；

步驟3：連續兩點對之間的路徑推測

循環GPS序列中的兩兩點對，循環起點的多個匹配路鏈和終點的多個匹配路鏈，利用緩存的500米范圍內路鏈行駛樹，直接獲取兩個路鏈對之間的導航路徑；

步驟4：點對路徑連接及篩選；

循環兩兩點對之間的路徑，將第1-2點的路徑和2-3點的路徑，根據中間2點的共同匹配合并為1-3點的路徑，然后再合并3-4點的路徑為1-4點的路徑，然后再合并(x-1)-(x)的路徑為1-x點的路徑，x小于等于n，x大于等于1；直到與n-(n+1)點之間沒有推測出軌跡，將這n點的軌跡保存，繼續循環n+1點以后的軌跡重復執行，最后形成m段多點的連續路徑；

步驟5：多段路徑合并；

對于步驟4形成的多點的連續路徑，在中斷處，采用非緩存方法，再次計算中斷處前后兩條路鏈之間的路徑；

如果兩條路鏈中間無法推測出路徑，則先忽略前一段路徑的最后一條路鏈，計算前一段路徑中前一段路徑的倒數第二條路鏈與后一段路徑中的第一條路鏈之間的路徑；還是沒有，則計算前一段路徑的最后一條路鏈與后一段路徑中的第二條路鏈之間的路徑，還是沒有，則計算前一段路徑中倒數第二條的路鏈與后一段路徑中的第二條路鏈之間的路徑；

如果還是無法推測，則忽略前后兩條路徑，計算前一條路徑的倒數第三條路鏈與后一條路徑的第三條路鏈之間的路徑，直到能夠得出路徑，將兩段路徑合并為一條完整的路徑；

最多經過5輪循環，就能將兩段路徑合并；

步驟6：路徑平滑；

經步驟5得出的路徑，仍存在部分地點出現異常拐彎，懸掛線，在主路或輔路間頻繁切換的情況；

采用移動窗口平滑法，以連續的7條路鏈為基礎，判斷起始路鏈到結束路鏈是否有更近的路徑替代，如果有則進行替代，然后往前移動4條路鏈，判斷下一個7條路鏈，直到終止路鏈。