[發明專利]基于時段的熱點路徑的特征識別與快速搜索方法

有效

• 申請號: 201310248692.7
• 申請日: 2013-06-21
• 公開（公告）號: CN103323018A
• 公開（公告）日: 2013-09-25
• 發明（設計）人: 羅吳蔓;譚浩宇;陳雷;倪明選
• 申請（專利權）人: 廣州市香港科大霍英東研究院
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及一種網絡路徑搜索的方法，尤其涉及利用歷史軌跡大數據在路網中進行熱點路徑識別和搜索的方法。

背景技術

在網絡路徑搜索中，最優路徑通常是指從出發地到目的地的所有路徑中，帶權路徑長度最短的一條。根據道路網絡中路段權值含義的不同，最優路徑查詢可演化為路徑長度最短、行使時間最少、收費價格最優，以及能源消耗最低等路徑的計算。在較為復雜的應用中，最優路徑還可以是多權值（如同時考慮行使時間和收費價格）綜合考慮后的最佳結果。

然而，在許多應用場景中，這些基于權值最優的路徑查詢技術無法滿足用戶的出行需求。例如，人們在一個陌生的城市旅行時，往往會綜合考慮諸多因素，如道路關閉與否、路況復雜程度、路面質量好壞、行車安全與否，以及沿途風景如何等等。這些條件不僅繁雜，而且隨時間變化不定，很難作為具體的尋路標準。此時，選擇從出發地到目的地，最常被用戶使用的路徑，即熱點路徑，是較傳統尋路方法更好的選擇。除了在路徑推薦中的應用，熱點路徑也是城市規劃、時空數據挖掘，以及各類位置服務等重要應用的關鍵技術。例如，我們可以通過檢查在不同時段內，相同源點和目的地之間熱點路徑的相同與否，來分析人們在不同時期（如工作日和周末）的出行習慣是否發生變化，以及輔助探測異常及重大事件的發生。

近年來，隨著位置獲取技術（如Global?Positioning?System:?GPS）的快速發展，人們開始收集并處理越來越多的有關車輛、人、動物等物體的歷史運動軌跡信息。例如，從2007年至2012年，北京市收集車輛GPS位置記錄已達1000億條左右。海量軌跡數據的出現，為熱點路徑的識別與查詢提供了可能。

簡而言之，熱點路徑是指從源點到目的地的所有路徑中，最常被使用的路徑。此概念容易理解，其主要特征卻很難提取。專利文獻1（專利申請號201110357525.7）提出的常用路徑和熱點路徑含義類似。具體的說，常用路徑是指從源點到目的地的所有路徑中，經過歷史軌跡數大于某個預設值的路徑。該方法的主要問題在于，由此得到的最優路徑不具備后綴子路徑最優的特性。該特性是指，假設路徑P?=?v_1?→?v_2?→?…?→?v_n是從源點v₁到目的地v_n的熱點路徑，v_i?(1?≤?i?≤?n)是路網中的結點，那么P的后綴子路徑v_i?→?…?→?v_n也應該是v_i到v_n的熱點路徑。否則，在實際導航中，用戶每到一個十字路口（即v_i），就需要重新查詢剩下旅程的熱點路徑，這顯然不滿足實際應用的需求。其次，軌跡數據具備時空多維性，現有的大數據處理技術無法支持軌跡大數據的有效存儲和快速檢索。該方法并沒有給出有效存儲和查詢軌跡大數據的解決方案。最后，受交通流量、天氣情況、道路建設、異常事件等動態因素的影響，熱點路徑具備較強的時效性。但是該方法并不允許用戶在查詢時，選擇感興趣的時段，熱點路徑的計算是基于所有的歷史軌跡完成的。由于時段的任意性和不可預知性，很多復雜的操作（如軌跡數據查詢）必須在線完成，這為路徑的快速查詢提出了巨大挑戰。

澳大利亞昆士蘭大學的科研人員提出了另外一種定義熱點路徑的方法。他們設計了一個新型的熱度函數，用于評估從給定源點到目的地之間每條路徑的熱度，并選擇熱度最高的路徑作為熱點路徑。一條路徑的熱度值，等于該路徑上所有路段到達目的地的概率值的乘積。因此，路段數越多，路徑的熱度值越低。這顯然不利于那些途經較多交叉路口且使用頻率很高的道路（如途經市區的路線）。還有，該方法找出的道路可能包含很少被使用的路段，這樣的熱點路徑是沒有實際意義的。此外，該方法也不允許用戶選擇感興趣的時段，沒有提出在線查詢（如軌跡數據在線查詢）的解決方案。

綜上所述，熱點路徑的有效識別與快速搜索是一個亟待解決的問題。。

發明內容

為了解決現有技術的不足,?本發明提供了一種熱點路徑的新型特征識別策略，一種基于時段的熱點路徑高效搜索方法。其目的有兩點：1)?設計合理的熱點路徑識別機制，盡量準確的反映大眾的尋徑經驗；2)?設計高效的軌跡數據存儲與檢索方法，實現對基于時段的熱點路徑的快速搜索。?