[發明專利]用于路線規劃的按需捷徑計算

在審

• 申請號: 201780045817.2
• 申請日: 2017-07-27
• 公開（公告）號: CN109642799A
• 公開（公告）日: 2019-04-16
• 發明（設計）人: D·R·戴玲;D·施埃佛迪克;C·索莫
• 申請（專利權）人: 蘋果公司
• 主分類號: G01C21/32
• 分類號: G01C21/32;G01C21/34
• 代理公司: 中國國際貿易促進委員會專利商標事務所 11038
• 代理人: 周磊

計算在移動導航系統中基于小區的路線規劃中所使用的小區的捷徑基于經更新的交通狀況和進入所述小區的入口處的估計到達時間(ETA)來重新計算捷徑。捷徑被按需計算并且被存儲在最近最后使用(LRU)緩存中。捷徑是利用存儲在LRU緩存中的成本函數來計算。捷徑是根據存儲在LRU緩存中的元數據來計算。捷徑任選地是基于所預測的ETA和未來交通狀況，以提供最佳成本路線的準確估計。

背景技術

位置感知設備中的移動導航系統現在是常見的。移動設備導航和汽車導航系統由于能夠在路途中為用戶提供最新導航信息以及基于地圖的視覺導航輔助而越來越普及。

搜索一天中某些時間的最佳路線由于需要基于用戶的位置和當前交通狀況對結果進行調整而可能在導航系統中出現問題。然而，基于當前交通狀況計算經更新的路線可能是計算代價高的。另外，僅僅適應交通狀況的另選路線可能并非始終是最好的選擇。

發明內容

描述了用于最佳成本路徑路線規劃(包括移動導航系統中的最低成本路徑標識、實時交通路線規劃、和按需捷徑計算)的方法、過程、裝置、機器可讀有形存儲介質、和數據處理系統。在移動設備上的導航系統中，實時交通路線規劃幫助用戶選擇與其當前路線相比從源S到目的地D的最佳另選路線，包括顯示具有最佳成本路徑的另選路線中的一者或多者，其中成本可以根據行程時間、行程距離、交通量和/或行程期間遇到繞行的數量中任意一者或多者來度量。最佳成本路徑確定是基于當前路線狀況，例如行程時間、交通和道路封閉。

在一個實施方案中，最低成本路徑標識提供了一種計算高效的方式來標識避開局部繞行的最低成本路徑，其中局部繞行是在使得否則可接受的最低成本路徑不可接受的被阻止子路徑周圍的臨時路徑。在一個實施方案中，最低成本路徑標識通過基于靜態成本評估被阻止子路徑的局部最優性來確定哪些另選路線避開所述子路徑。每個子路徑是完整的路徑或路線的部分或區部。

根據一個實施方案，實時交通路線規劃標識被標識成具有最低成本路徑的另選路線的哪些通過節點生成最佳成本路徑。通過節點是路線規劃信息一般已經可供使用的已知交通結點。通過節點通過從始發地到通過節點的最低成本路徑、和從通過節點到目的地的最低成本路徑來限定道路網絡中的路徑。在一個實施方案中，實時交通路線規劃基于動態成本來評估子路徑的局部最優性，以消除包含非最佳路段的另選路線。在一個實施方案中，基于動態成本評估子路徑的局部最優性可以考慮沿所述子路徑所覆蓋的完整路徑或路線的一部分的當前交通或狀況(例如，事故、受損道路、等等)。

在一個實施方案中，局部最優性是在忽略完整路線或路徑的其余部分時沿完整路徑或路線的僅僅所述部分所推導或計算的最佳或近于最佳方案。所述方案可以使用常規技術來確定什么是最佳或近于最佳的，但被約束到所述部分而不是完整路徑或路線。所述約束實際上設定限定完整路徑或路線的所述部分的起點和終點。

根據一個實施方案，實時交通路線規劃還確定另選路線與移動設備上的導航應用程序正遵循的當前路線之間的重疊量。

根據一個實施方案，實時交通路線規劃基于所評估的局部最優性和相應另選路線的重疊量中任意一者或多者來在最佳成本路徑順序中對另選路線的通過節點進行排名。

根據一個實施方案，按需捷徑提供路線的一部分的最低成本路徑的計算高效的確定。例如，按需捷徑計算根據需要在最近最后使用(LRU)緩存中的已有捷徑不可用或需要更新時重新計算捷徑。

通過附圖以及通過以下具體描述，本發明的其他特征將顯而易見。

附圖說明

本發明以舉例的方式進行說明，并且不限于各個附圖的圖形，在附圖中類似的附圖標號指示類似的元件，并且其中：

圖1是根據本發明一個實施方案的移動導航系統中實時交通路線規劃和按需捷徑計算的框圖概述；

圖2是根據本發明一個實施方案在移動導航系統中實時交通路線規劃和按需捷徑計算的準備中可導航區域可以被劃分成的示例性小區的例示；