[發明專利]擁塞感知的路網移動對象連續K近鄰查詢方法

有效

• 申請號: 202110494786.7
• 申請日: 2021-05-07
• 公開（公告）號: CN113377828B
• 公開（公告）日: 2022-04-19
• 發明（設計）人: 董天陽;劉洋;胡鋯
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06F16/9537;G06F16/29
• 代理公司: 杭州天正專利事務所有限公司 33201
• 代理人: 王兵

本發明的擁塞感知的路網移動對象連續K近鄰查詢方法，首先基于擁塞感知的路網擴展方式，感知出每條道路的擁塞性，以擁塞權重的路網距離作為移動對象和查詢點之間的距離衡量標準。然后設置合理的監測范圍構建局部路網，高效地查詢出時間段[t_i,t_j]內任意時刻K個距離查詢點帶權路網距離最近鄰的移動對象。本發明的優點是：引入道路的擁塞性，以擁塞權重的路網距離作為移動對象和查詢點之間的距離衡量標準，提高在了現實應用中的準確性和適用性，使連續K近鄰查詢結果更接近真實路網環境下的最優解。然后使用合理的監測范圍構建局部路網，提高了算法的查詢效率。

技術領域

本發明涉及一種路網連續K近鄰查詢方法。

背景技術

隨著無線通信和GPS等定位技術的快速發展，以及移動通信設備的大規模普及，用戶可以更加輕松獲取到自己的位置信息。基于移動設備位置信息的移動端應用程序也越來越多，這些應用程序中幾乎都用到了K近鄰查詢技術。例如，在地圖導航軟件中，用戶希望找到周圍最近的幾家工商銀行；在導游應用中，游客在西湖游玩時可能會尋找幾個最近的“杭幫菜餐廳”。在上述查詢場景中，用戶查詢的對象都是空間中的靜態對象，所以K近鄰技術還能有效地滿足這類查詢需求。當查詢的對象處于移動狀態時，例如，用戶使用打車軟件搜尋離他最近的3輛出租車。由于出租車位置信息在不斷在發生改變，系統需要重復進行多次K近鄰查詢，計算代價太大。由此可以看出K近鄰查詢技術不能滿足類似于打車這類場景下的查詢需求，存在一定的局限性。然而，連續K近鄰查詢技術可以有效地解決這類問題。連續K近鄰查詢是K近鄰查詢的擴展，K近鄰查詢是查詢某一時刻的K個近鄰的對象，而連續K近鄰查詢是在某一段時間內連續查詢K個近鄰的對象，返回的結果集是連續動態監測的查詢結果。

現有的連續K近鄰查詢方法中主要關注距離因素，很少關注道路擁塞對路網下的K近鄰查詢結果的影響。然而，在真實路網中道路擁堵情況對查詢結果的影響很大。比如用戶在呼叫一輛網約車時，該用戶有急事必須盡快到達目的地。若系統在給用戶分派車輛時只考慮了距離因素，分派的車輛是距離用戶最近的，但是如果該車輛處在嚴重擁堵路段，那么這樣的查詢結果對用戶而言不是一個最優解決方案。將道路的擁塞性也作為一個影響查詢結果的因素添加到路網環境下的連續K近鄰查詢中，有助于提高在現實應用中的準確性和適用性。

發明內容

本發明要克服現有技術的上述缺點，提出一種擁塞感知的路網移動對象連續K近鄰查詢方法。

本發明首先在路網擴展過程中利用基于道路交通流特征參數設計的道路擁塞判斷算法感知出道路的擁塞狀態；接著根據擁塞系數對道路長度進行加權處理，以擁塞權重的路網距離作為移動對象和查詢點之間的距離衡量標準；然后在局部路網內進行連續K近鄰查詢，以提高查詢效率；最后按照帶權路網距離由近到遠的順序，查詢出在時間段[t_i,t_j]內任意時刻距離查詢點最近的K個移動對象，其中t_i為連續K近鄰查詢開始時刻，t_j為結束時刻。

本發明的擁塞感知的路網移動對象連續K近鄰查詢方法，包括如下步驟：

1初始時刻擁塞感知的K近鄰查詢；

初始時刻擁塞感知的K近鄰查詢用于獲得在連續查詢時間段[t_i,t_j]開始時刻t_i距離查詢點帶權路網距離最近的K個移動對象。該階段采用基于擁塞感知的增量式路網擴展策略。在路網擴展的同時判斷出道路的擁塞性，確定道路擁塞性系數，對道路長度進行加權處理。具體包括：