[發明專利]移動環境下基于大規模反近鄰查詢的物流調度系統

在審

• 申請號: 201610082750.7
• 申請日: 2016-02-05
• 公開（公告）號: CN105787585A
• 公開（公告）日: 2016-07-20
• 發明（設計）人: 季長清;陶帥;王寶鳳;汪祖民;王慧
• 申請（專利權）人: 大連大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06Q50/28
• 代理公司: 大連智高專利事務所(特殊普通合伙) 21235
• 代理人: 畢進

技術領域

本發明涉及LBS(LocationBasedService)領域，是一種移動環境下基于大 規模反近鄰查詢的物流調度系統，包含大規模時空數據分布式的處理以及智能 移動終端應用的開發。

背景技術

計算機及其網絡技術的飛速發展，移動智能終端的出現以及移動定位技術的 不斷成熟為物流行業的信息化提供了夯實的基礎。通過移動互聯，將分散在不 同地理位置的物流貨車以及發件客戶緊密聯結在了一起，將物流貨車、發件客 戶作為節點，構成了一個信息傳遞與信息共享的網絡?？蛻艨梢詫崟r了解附近 物流貨車的位置以及運作狀況，同時物流貨車司機也可以實時準確的接收到附 近客戶的請求，便于各方業務的洽談，實現了物流的高效調度。

結合近年來隨著基于位置的服務和移動互聯網的快速發展，物流調度系統 中，對于物流網絡中各節點臨近節點的實時查詢成為一大技術難題。一方面是 由于地理空間數據的數據量的迅猛增長，另一方面也是因為物流調度業務中對 于實時性的特殊要求。因此，如何實現高效的近鄰查詢成為移動云計算環境下 的物流調度系統新的需求和挑戰?，F在已經有幾種近鄰查詢的方法，如最基礎 的kNN方法，以及作為kNN問題變種的RNN(ReverseNearestNeighbor)反近 鄰查詢，已經成為典型的空間查詢算法并得到了業界的普遍關注。自從Korn等 人首次給出RNN查詢的定義以來，作為一個熱點研究問題，目前已有了大量的 研究成果，并具備很好的應用價值。

由于現存的大部分RNN算法因為其索引或算法的結構化的特征，導致潛在的 順序執行問題。另外，也有著不具備可擴展性，缺失精度，或者產生維數災難 等問題。同時基于位置服務相關研究與應用的興起，單機環境因為計算與存儲 能力有限，故無法支持大規?？臻g查詢方法，解決方案就是同時利用多計算節 點參與計算，這就需要設計新的分布式索引與并行查詢方法。盡管RNN查詢與 其它的空間查詢方法一樣重要，但有效地支持大規模RNN查詢的算法方面的工 作成果還是相對較少。MRVoronoi除了設計空間索引結構之外，也簡略地描述了 利用MapReduce進行RNN查詢的方法。但該方法需要額外的時間進行定位查詢 點，當維度增加時就會導致高的維護與計算代價。RankReduc方法通過MapReduce 來支持處理大規模近似kNN查詢，但該方法是不精確的，只能用于高維條件， 且沒有描述解決RNN的過程。所以現有的方法均不能很好地直接用來解決大規 模RNN查詢問題。

從大規模空間數據集中進行查找RNN的問題不僅作為一個智能物流配送算 法求解優化問題，同時也在智能導航、交通控制、救災援助、氣象預報、空間 聚類等領域中有著廣泛的應用。但是面對海量、大規模的時空數據，傳統的RNN 方法，很難滿足移動互聯物流系統對于實時性的需求，基于該出發點，我們設 計并實現了該發明。

發明內容

根據上述背景技術中存在的缺陷和不足，本發明提供了移動環境下基于大 規模反近鄰查詢的物流調度系統，以解決現有物流調動系統中發件客戶與物流 貨車近鄰問題計算的不足。本發明也針對現有技術中存在的反近鄰查詢方法中 的不足進行了改進，用以提高準確度和實時性。

為了實現上述目的，本發明所采用的技術方案是：移動環境下基于大規模 反近鄰查詢的物流調度系統，該系統包括云中心服務系統和智能移動客戶端系 統，云中心服務系統用于進行倒排網格索引的建立，以及執行分布式大規模反 近鄰算法，智能移動客戶端適應不同用戶功能需求與使用習慣，通過內置的定 位系統和運營商的基站，以及依托網絡獲取自身的實時空間地理位置，發起物 流快遞相關查詢請求，并與云中心服務系統進行信息交互。

作為技術方案的補充，該大規模反近鄰查詢物流調度系統所使用的云中心 端服務系統由不少于一個云數據中心的網絡服務器或虛擬主機所構成的，采用 云計算這種并行化計算來處理大規模數據應對于大量的需要發快遞的客戶，并 以客戶為查詢中心，在此位置發起查詢清求，多個物流貨車位置信息作為可供 查詢的數據集，在這種模式下，保證了高物流量時的調度穩定性，加快了物流 信息搜索時的反應速度，同時增強了可擴展性。云中心服務系統通過使用采集 到的客戶位置以及物流貨車位置，建立位置信息的分布式倒排網格索引。

由云中心服務系統使用倒排網格索引進行分布式時空信息的大規模反近鄰 查詢，并返回最優物流貨車給發件客戶。