[發明專利]一種低采樣率下的實時車輛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
• 代理人: 劉新瓊

本發明公開了一種低采樣率下的實時車輛K近鄰查詢方法，首先獲取出租車軌跡數據和城市路網數據，統計每條軌跡在當前時刻前數個時間片內的車輛位置和行車速度；然后估計當前車輛速度，考慮車輛當前是否還在在同一路段上對車輛當前位置做預測；接著考慮當前車輛與上一時刻相隔了一個路段以上的情況，使用LSTM深度學習模型預測當前車輛位置；接下來基于層次聚類方法對路網進行劃分，并使用距離矩陣維護單元間的相鄰關系；最后使用K近鄰搜索算法，從查詢點所在單元開始更新搜索區域內的車輛位置，逐步擴展搜索范圍直到找到所有K近鄰車輛。本發明可以在低采樣率下對車輛查詢，既保持用戶了查詢的實時性，又達到在高采樣率下的查詢準確度。

技術領域

本發明屬于大數據處理領域，具體涉及一種車輛位置查詢方法。

背景技術

基于位置的服務(簡稱LBS)通過無線電通訊網絡或外部定位方式獲取移動終端用戶的位置信息，依賴地理信息平臺，為用戶提供相應的服務。隨著無線通信技術的發展和移動終端設備的普及，基于位置的服務在生活服務、地點交友、休閑娛樂得到了廣泛的應用。其中，K近鄰(簡稱KNN)查詢作為LBS中的關鍵技術之一，在智能城市的多個場景中都有重要應用，因而受到國內外研究者的廣泛關注。KNN具體可以描述為：已知數據空間中存在集合P包含n個數據點，對于給定的查詢點q，在集合P中找到大小為k的數據對象子集NN(q)，使得NN(q)中的數據點到查詢點q的距離最近。目前，對于KNN查詢的研究主要是基于歐式空間和路網環境，其中歐式空間中的KNN查詢研究相對成熟。路網環境下的KNN查詢更符合真實的城市交通環境，但因為交通路網的復雜性和連通性，KNN查詢計算量更大，因而受到研究者們更多的關注。以上大多是針對靜態對象的KNN查詢，在城市環境中存在許多移動對象的實時最近鄰查詢技術，比如用戶在請求網約車服務時，由于網約車都存在實時移動狀態，服務提供商需要根據網約車的歷史記錄位置預測車輛的當前位置，并根據預測位置篩選出離用戶最近的幾輛車供其選擇。針對移動對象的NN查詢為了提高準確率，往往需要移動對象具有較高的采樣率，但同時為了滿足實時性要求，必須盡量限制查詢范圍、降低查詢時間，及時為用戶反饋查詢結果。如果想擴大查詢范圍，但同時為了用戶體驗，不降低實時性，則需要降低采樣率。但是在低采樣率下，車輛的實時位置與歷史記錄位置又存在較大偏差。

發明內容

為了克服現有技術的不足，本發明提供了一種低采樣率下的實時車輛K近鄰查詢方法，首先獲取出租車軌跡數據和城市路網數據，統計每條軌跡在目標時刻前數個時間片內的車輛位置和行車速度；然后根據車輛歷史記錄速度估計當前車輛速度，考慮車輛當前是否與上一時間片在同一路段上分情況對車輛當前位置做預測；接著考慮當前車輛與上一時刻相隔了一個路段以上的情況，使用LSTM深度學習模型預測當前車輛位置；接下來基于層次聚類方法對路網進行劃分，并使用距離矩陣維護單元間的相鄰關系；最后使用K近鄰搜索算法，從查詢點所在單元開始更新搜索區域內的車輛位置，逐步擴展搜索范圍直到找到所有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；