[發明專利]多用戶并發導航路徑查詢均衡控制方法及裝置

無效

• 申請號: 200910088856.8
• 申請日: 2009-07-21
• 公開（公告）號: CN101603836A
• 公開（公告）日: 2009-12-16
• 發明（設計）人: 陸鋒;周亮
• 申請（專利權）人: 中國科學院地理科學與資源研究所
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 北京集佳知識產權代理有限公司
• 代理人: 趙景平;逯長明

技術領域

本發明涉及網絡技術，具體涉及一種多用戶并發導航路徑查詢均衡控制方法及裝置。

背景技術

路徑查詢是地圖網站、公眾出行信息平臺和中心服務式導航系統的核心功能，此類系統均應用于多用戶并發環境。在多用戶并發環境下，任何時刻都可能會有多個用戶同時對系統發出路徑查詢請求。由于此類系統的并發用戶訪問量非常大，在系統硬件限定的條件下，路徑查詢的響應時間將隨著并發訪問的用戶數呈線性增長，用戶的平均等待時間也將急劇增加。在這些系統中，如何保證系統的響應時間限定在用戶可容忍的范圍內是一個瓶頸問題。

為了解決該問題，目前采用的技術包括增加服務器的數量、發展路徑查詢的并行算法、采用路徑查詢緩存技術等。這些方法存在成本高，限定條件苛刻、實現困難、缺乏針對并發用戶數的自適應調整等缺點，而且其核心的路徑查詢算法并未得到優化。

發明內容

本發明要解決的技術問題是：提供一種多用戶并發導航路徑查詢均衡控制方法及裝置，以便在存在多用戶并發導航路徑查詢需求時，自適應地控制路徑查詢算法的精度和效率之間的平衡，在精度可控的前提下，最大限度地提升路徑查詢效率，縮短用戶的等待時間。

本發明的技術解決方案為：

一種多用戶并發導航路徑查詢均衡控制方法，包括：

采用系統抽樣的方法，在路網中抽取車行道段對作為樣本車行道對；

計算樣本車行道對間最優導航路徑搜索的嚴密算法耗時和結果路徑耗費；

計算樣本車行道對間最優導航路徑搜索的不同啟發式算法耗時和結果路徑耗費；

根據計算得到的嚴密算法耗時和結果路徑耗費和不同啟發式算法耗時和結果路徑耗費，計算不同啟發式算法與嚴密算法的耗時比和精度比；

根據計算得到的耗時比和精度比、以及用戶選擇條件，確定最優導航路徑搜索的啟發式算法及參數。

優選地，所述計算不同啟發式算法與嚴密算法的耗時比和精度比包括：

以啟發式算法與嚴密算法的耗時比E作為衡量啟發式算法效率的度量因子，得到啟發式算法的耗時比E為：E＝t₂/t₁，其中，t₁是采用Dijkstra算法的耗時，t₂是啟發式算法的耗時；

以啟發式算法與嚴密算法得到的路徑耗費差的增量百分比P作為啟發式算法精度的度量因子，得到啟發式算法的精度P為：P＝1-(l₂-l₁)/l₁＝(2-l₂/l₁)×100％，其中，l₁為采用Dijkstra算法計算得到的結果路徑耗費，l₂是采用啟發式算法得到的結果路徑耗費；

將所有樣本對的啟發式算法耗時比、精度比計算結果求統計平均值，得出當前啟發因子下該啟發式算法的平均耗時比與平均精度。

優選地，所述根據計算得到的耗時比和精度比、以及用戶選擇條件，確定最優導航路徑搜索的啟發式算法及參數包括：

采用遺傳規劃算法，指定適應度和初始參數，對不同啟發因子下啟發式算法的耗時比與精度進行符號回歸，分別建立耗時比、精度與啟發式因子之間的函數關系；

根據所述函數關系和用戶選擇條件，確定啟發式策略與啟發因子。

優選地，所述算法耗時和結果路徑耗費與實際選取的路網相關。

優選地，所述方法還包括：

利用確定的最優導航路徑搜索的啟發式算法及參數進行導航路徑查詢。

一種多用戶并發導航路徑查詢均衡控制裝置，包括：

抽樣單元，用于采用系統抽樣的方法，在路網中抽取車行道段對作為樣本車行道對；

第一計算單元，用于計算樣本車行道對間最優導航路徑搜索的嚴密算法耗時和結果路徑耗費；

第二計算單元，用于計算樣本車行道對間最優導航路徑搜索的不同啟發式算法耗時和結果路徑耗費；

比較單元，用于根據計算得到的嚴密算法耗時和結果路徑耗費和不同啟發式算法耗時和結果路徑耗費，計算不同啟發式算法與嚴密算法的耗時比和精度比；

確定單元，用于根據計算得到的耗時比和精度比、以及用戶選擇條件，確定最優導航路徑搜索的啟發式算法及參數。

優選地，所述比較單元包括：