[發明專利]一種路徑推薦方法與裝置

有效

• 申請號: 201710842396.8
• 申請日: 2017-09-18
• 公開（公告）號: CN107643085B
• 公開（公告）日: 2021-02-12
• 發明（設計）人: 許佳捷
• 申請（專利權）人: 蘇州大學
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 羅滿

本發明實施例公開了一種路徑推薦方法與裝置，依據獲取的歷史軌跡數據，構建在目的地點確定的情況下所對應的有向圖；所述有向圖中包含的任意兩個相鄰節點之間所對應的線段有其對應的轉向概率值；依據最大概率尋路算法，從所述有向圖中選取出從起始節點達到所述目的地點概率值最大的一條路徑作為推薦路徑。該技術方案不再局限于使用先驗知識建立大量模型來解決路況復雜多變的難題，相較于目前主流導航應用以算法模型及策略計算產生的軌跡規劃而言，該技術方案通過分析歷史軌跡數據來挖掘用戶出行的模式，更加的符合真實環境下路況的復雜變化，依據構建的有向圖，可以挖掘出一條最熱門的路徑即推薦路徑，可以更好的滿足用戶的出行要求。

技術領域

本發明涉及路徑規劃技術領域，特別是涉及一種路徑推薦方法與裝置。

背景技術

隨著智能手機等移動通訊設備的廣泛使用和移動通訊技術的迅猛發展，移動互聯網及其應用在近年來呈井噴之勢。據權威數據顯示，在2016年1月中國移動互聯網用戶數量達到了7.59億，超越了傳統PC用戶的總量，形成了萬億規模產值的龐大市場。隨之而來，以各種地圖應用為代表的基于位置的服務(Location based Service)成為大眾化的工具，深入地改變了人們的工作和生活方式。在使用這些服務時大量的記錄被持久化到企業服務器中，這些記錄包含了位置、時間、方向、速度等信息，在時間軸上將采樣點序列構成移動軌跡，反映了用戶的行為歷史。

大量的用戶產生了海量的軌跡數據，從宏觀上看蘊含了群體移動模式和規律，對車輛導航、行程推薦、城市規劃等具有重要的價值。在大數據時代，依賴處理能力的提升，使得海量軌跡數據分析與應用成為可能。通過分析移動軌跡所蘊含的信息，可以提高路徑規劃的質量，大大方便了人們的出行，提高了出行的效率。

軌跡數據挖掘已經成為了數據挖掘領域的一個重要的新興分支，目的是從軌跡數據中提取有價值的知識，運用到各類應用中去。頻繁模式挖掘(frequent patterns)是指從大規模軌跡中發現時序模式，如在給定時間間隔內有超過一定數量的對象行駛的公共路徑，對于目的地的預測、路徑推薦、行為理解有著重要的價值。

傳統方式中，往往通過先驗知識建立多種模型，以適應復雜多變的路況變化，通常會劃分不同的時段調用不同的模型，甚至不同的天氣都有對應的模型使用。但是復雜的模型導致維護代價大，隨著應用場景的復雜化，機械化的模型使用難以界定模型適用邊界，如將早晨8點至10點定義為早高峰時段，使用早高峰模型，7點59分就使用非早高峰模型，顯然這種人為對于模型的劃分并不是合理的。因此先進的路徑規劃引擎應該可以自行發現出行模式，調整路徑規劃的模型。

可見，如何提高路徑規劃質量，更好的滿足用戶的需求，是本領域技術人員亟待解決的問題。

發明內容

本發明實施例的目的是提供一種路徑推薦方法與裝置，可以提高路徑規劃質量，更好的滿足用戶的需求。

為解決上述技術問題，本發明實施例提供一種路徑推薦方法，包括：

依據獲取的歷史軌跡數據，構建在目的地點確定的情況下所對應的有向圖；所述有向圖中包含的任意兩個相鄰節點之間所對應的線段有其對應的轉向概率值；

依據最大概率尋路算法，從所述有向圖中選取出從起始節點達到所述目的地點概率值最大的一條路徑作為推薦路徑。

可選的，所述依據獲取的歷史軌跡數據，構建在目的地點確定的情況下所對應的有向圖包括：

依據獲取的歷史軌跡數據，建立在目的地點確定的情況下所對應的路網圖；所述路網圖由各個節點連接組成，一個節點對應表示一個路口；

根據如下公式，計算出所述路網圖中任意兩個相鄰節點之間的轉向概率值，從而將所述路網圖轉化為有向圖；