[發明專利]一種低采樣率下的實時車輛K近鄰查詢方法

有效

• 申請號: 202010958535.5
• 申請日: 2020-09-14
• 公開（公告）號: CN112183589B
• 公開（公告）日: 2022-04-22
• 發明（設計）人: 王亮;王蕾;於志文;周聰;郭斌;郝紅升
• 申請（專利權）人: 西北工業大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06V10/762;G06V10/764;G06N3/04;G06N3/08;H04W4/029;H04W4/40
• 代理公司: 西安凱多思知識產權代理事務所(普通合伙) 61290
• 代理人: 劉新瓊

1.一種低采樣率下的實時車輛K近鄰查詢方法，其特征在于，包括以下步驟：

步驟1：獲取指定城市的城市路網數據，指定城市中指定數量的網約車軌跡數據；利用地圖匹配算法對網約車軌跡數據和城市路網數據進行地圖匹配，為每個軌跡點匹配相應的路段，同時在網約車軌跡數據中利用每個軌跡點相鄰的軌跡點信息計算出網約車在該軌跡點的行駛速度和行車方向；

步驟2：定義車輛的位置歷史記錄為：

hist＝{loc_t-n，...，loc_t-1，loc_t}

其中，t表示距離當前時刻最近的上個采樣時刻，t-n，t-n+1，...，t-1，t表示距離當前時刻最近的前n+1個采樣時刻，loc_t-n，...，loc_t-1，loc_t表示距離當前時刻最近的前n+1個采樣時刻的車輛位置；所述采樣為均勻采樣，采樣間隔為T；

定義：當前時刻為t_c，當前時刻距離最近的上個采樣時刻的間隔時間span＝t_c-t，車輛在距離當前時刻t_c最近的n個采樣間隔的平均速度為vs＝{v_t-n+1，...，v_t-1，v_t}，其中v_t-i＝(loc_t-i-loc_t-i-1)/T，i＝0，1，...，n-1；則車輛當前時刻的預測速度為：

其中v_history表示距離當前時刻最近的前n個采樣時刻之前的指定時間段內該車輛平均速度，ρ為權重；

步驟3：車輛當前所在路段的判斷方法如下：

其中，l表示距離當前時刻最近的上個采樣時刻車輛所在位置距離當前車輛所在路段兩個端點的距離中較近者；

步驟4：根據步驟3的判斷結果預測車輛當前時刻的位置；

情況1：車輛還在當前路段，則車輛當前時刻在當前路段的預測位置p_pre為：

其中，p表示車輛距離當前時刻最近的上個采樣時刻所在位置，0＜p＜1，length表示當前路段的長度；

情況2：車輛離開當前路段，車輛已經行駛到相鄰路段或相隔路段；

采用如下LSTM深度學習模型預測車輛當前時刻的位置：

步驟4-1：選取指定數量的車輛位置信息作為訓練樣本，每連續S個采樣間隔T的車輛位置為一個樣本，其中第S個車輛位置為標簽，采用最大值最小值法進行數據歸一化；

步驟4-2：采用兩層LSTM層結構，輸入為樣本中前S-1個采樣間隔的車輛位置，輸出為第S個車輛位置，對LSTM深度學習模型進行訓練；

步驟4-3：使用訓練完成的LSTM深度學習模型對車輛當前時刻的位置進行預測；

步驟5：基于層次聚類方法對路網進行劃分：

將整個城市路網用G(U，E)表示，其中U表示路網中的節點集合，即交通系統中的路口；E表示路網中的邊集合，即連接兩個路口的路段；將G劃分為M個路網單元G(U，E)＝{G₁(U₁，E₁)，G₂(U₂，E₂)，G_j(U_j，E_j)，...，G_M(U_M，E_M)}，其中G_j(U_j，E_j)表示第j個路網單元，U_j表示第j個路網單元的節點集合，E_j表示第j個路網單元的邊集合，j＝1，2，...，M；(U_j，E_j)滿足：

其中，e_j，k表示E_j中的第k個邊，u_start和u_end分別表示E_j中的第k個邊兩端的節點，u_j，k表示U_j中的第k個節點，|u-u_j，k|表示U_j中任意一個節點u和u_j，k之間的路網距離，|U_j|表示U_j中的節點數量，maxD表示路網距離閾值，maxN表示節點數閾值；

步驟6：計算路網距離：

對第j個路網單元使用矩陣MD_j表示單元內部節點間的路網距離，具體如下：

MD_j(x，y)＝mindistance(u_x，u_y)，u_x∈U_j，u_y∈U_j

其中0＜x≤|U_j|，0＜y≤|U_j|，mindistance(u_x，u_y)表示路網單元G_j(U_j，E_j)中的第x個節點u_x與第y個節點u_y間的最短路網距離；

對第j個路網單元使用矩陣MN_j表示單元內部節點與單元邊界上節點的距離，具體如下：

MN_j(a，b)＝mindistance(u_a，u_b)，u_a∈U_j，a，u_b∈U_j，b

其中U_j，a表示第j個路網單元的節點集合U_j中內部節點的集合，U_j，b表示第j個路網單元的節點集合U_j中邊界節點的集合，U_j，a∪U_j，b＝U_j；mindistance(u_a，u_b)表示路網單元G_j(U_j，E_j)中的內部節點u_a與邊界節點u_b間的最短路網距離；

步驟7：基于路網單元的K近鄰搜索：

步驟7-1：確定查詢點q所在的路網單元；

步驟7-2：根據步驟2、步驟3和步驟4得到當前時刻所在路網單元內所有網約車的預測位置；

步驟7-3：在當前路網單元內，計算查詢點q到當前路網單元邊界上每個節點的路網距離以及查詢點q與當前時刻所在路網單元內所有網約車的路網距離；

步驟7-4：如果在當前路網單元內網約車數量小于K，或者在當前路網單元內網約車數量大于等于K但查詢點q到當前路網單元邊界上任一節點的路網距離小于查詢點q與K個距離最近的網約車的最大路網距離，則將搜索范圍擴展到相鄰路網單元，計算查詢點q到相鄰路網單元內所有網約車的路網距離，最終輸出當前路網單元和相鄰路網單元中距離查詢點q最近的K個網約車位置；

否則，如果在當前路網單元內網約車數量大于或等于K，并且查詢點q到當前路網單元邊界上任一節點的路網距離大于等于查詢點q與K個距離最近的網約車的最大路網距離，則輸出當前路網單元內距離查詢點q最近的K個網約車位置。