[發(fā)明專利]實(shí)時(shí)交通路由

在審

• 申請(qǐng)?zhí)枺?/td>: 201780050102.6
• 申請(qǐng)日: 2017-07-27
• 公開（公告）號(hào): CN109642801A
• 公開（公告）日: 2019-04-16
• 發(fā)明（設(shè)計(jì)）人: D·R·戴玲;S·麥特拉;D·施埃佛迪克;C·索莫
• 申請(qǐng)（專利權(quán)）人: 蘋果公司
• 主分類號(hào): G01C21/34
• 分類號(hào): G01C21/34
• 代理公司: 中國國際貿(mào)易促進(jìn)委員會(huì)專利商標(biāo)事務(wù)所 11038
• 代理人: 周磊

移動(dòng)導(dǎo)航系統(tǒng)中的實(shí)時(shí)交通路由基于用戶的當(dāng)前位置、實(shí)時(shí)交通狀況和沿路線的某些位置的估計(jì)到達(dá)時(shí)間生成另選路線。實(shí)時(shí)交通路由重新排列另選路線，考慮哪些路線提供到用戶目的地的最佳成本路徑。

背景技術(shù)

位置感知設(shè)備中的移動(dòng)導(dǎo)航系統(tǒng)現(xiàn)在很常見。移動(dòng)設(shè)備導(dǎo)航和汽車導(dǎo)航系統(tǒng)越來越受歡迎，能夠在途中向用戶提供最新的導(dǎo)航信息和基于視覺地圖的導(dǎo)航輔助。

在一天的特定時(shí)間搜索最佳路線會(huì)在導(dǎo)航系統(tǒng)中出現(xiàn)問題，因?yàn)樾枰鶕?jù)用戶的位置和當(dāng)前的交通狀況調(diào)整結(jié)果。然而，基于當(dāng)前交通狀況計(jì)算更新的路線可能在計(jì)算上是昂貴的。此外，單獨(dú)適應(yīng)交通狀況的替代路線可能并非總是最佳選擇。

發(fā)明內(nèi)容

描述了用于最佳成本路徑路由的方法、過程、裝置、機(jī)器可讀有形存儲(chǔ)介質(zhì)和數(shù)據(jù)處理系統(tǒng)，包括移動(dòng)導(dǎo)航系統(tǒng)中的最小成本路徑識(shí)別、實(shí)時(shí)交通路線和按需捷徑計(jì)算。在移動(dòng)設(shè)備上的導(dǎo)航系統(tǒng)中，實(shí)時(shí)交通路由幫助用戶選擇與其當(dāng)前路線相比從源S到目的地D的最佳另選路線，包括顯示具有最佳成本路徑的另選路線中的一者或多者，其中成本可根據(jù)行進(jìn)時(shí)間、行進(jìn)距離、交通量和/或行進(jìn)期間遇到的繞行數(shù)量中的任何一者或多者來測量。最佳成本路徑確定基于當(dāng)前路線條件，例如，行進(jìn)的時(shí)間、交通和道路封閉。

在一個(gè)實(shí)施方案中，最小成本路徑識(shí)別提供了一種計(jì)算上有效的方法來識(shí)別避免局部迂回的最小成本路徑，其中局部繞行是被阻塞的子路徑周圍的臨時(shí)路徑，其導(dǎo)致可接受的最小成本路徑不可接受。在一個(gè)實(shí)施方案中，最小成本路徑識(shí)別通過基于靜態(tài)成本評(píng)估子路徑的局部最優(yōu)性來確定哪些備選路線避免被阻塞的子路徑。每個(gè)子路徑是完整路徑或路線的一部分或區(qū)段。

根據(jù)一個(gè)實(shí)施方案，實(shí)時(shí)交通路由識(shí)別被識(shí)別為具有最小成本路徑的另選路線的哪些經(jīng)由節(jié)點(diǎn)生成最佳成本路徑。經(jīng)由節(jié)點(diǎn)是已知的交通路口，其路由信息通常已經(jīng)可用。經(jīng)由節(jié)點(diǎn)通過從原點(diǎn)到通過節(jié)點(diǎn)的最小成本路徑以及從通過節(jié)點(diǎn)到目的地的最小成本路徑來定義道路網(wǎng)絡(luò)中的路徑。在一個(gè)實(shí)施方案中，實(shí)時(shí)交通路由基于動(dòng)態(tài)成本評(píng)估子路徑的局部最優(yōu)性，以消除包含非最佳路段的另選路線。在一個(gè)實(shí)施方案中，基于動(dòng)態(tài)成本評(píng)估子路徑的局部最優(yōu)性可考慮沿著子路徑覆蓋的完整路徑或路線的一部分的當(dāng)前交通或狀況(例如，事故、受損道路等)。

在一個(gè)實(shí)施方案中，局部最優(yōu)性是最佳或接近最佳的解決方案，其僅沿著完整路徑或路線的一部分導(dǎo)出或計(jì)算，而忽略整個(gè)路線或路徑的其余部分。該解決方案可使用傳統(tǒng)技術(shù)來確定什么是最佳的或接近最佳的，但是被約束到該部分而不是完整的路徑或路線。實(shí)際上，有效約束設(shè)置了定義完整路徑或路線的部分的起點(diǎn)和終點(diǎn)。

根據(jù)一個(gè)實(shí)施方案，實(shí)時(shí)交通路由進(jìn)一步確定另選路線與移動(dòng)設(shè)備上的導(dǎo)航應(yīng)用程序所遵循的當(dāng)前路線之間的重疊量。

根據(jù)一個(gè)實(shí)施方案，實(shí)時(shí)交通路由基于所評(píng)估的局部最優(yōu)性和相應(yīng)另選路線的重疊量中的任一者或多者來以最佳成本路徑順序?qū)α磉x路線的經(jīng)由節(jié)點(diǎn)進(jìn)行排序。

根據(jù)一個(gè)實(shí)施方案，按需捷徑提供了對(duì)路徑的一部分的最小成本路徑的計(jì)算上有效的確定。例如，當(dāng)最后一次使用的(LRU)高速緩存中的現(xiàn)有捷徑不可用或需要更新時(shí)，按需捷徑計(jì)算根據(jù)需要重新計(jì)算捷徑。

通過附圖并且通過以下具體描述，本發(fā)明的其他特征將顯而易見。

附圖說明

本發(fā)明以舉例的方式進(jìn)行說明，并且不限于各個(gè)附圖的圖形，在附圖中類似的附圖標(biāo)號(hào)指示類似的元件，并且其中：

圖1是根據(jù)本發(fā)明實(shí)施方案的移動(dòng)導(dǎo)航系統(tǒng)中的實(shí)時(shí)交通路由和按需捷徑計(jì)算的框圖概述；

圖2是根據(jù)本發(fā)明實(shí)施方案的示例性小區(qū)的圖示，其中可導(dǎo)航區(qū)域可被分區(qū)以為移動(dòng)導(dǎo)航系統(tǒng)中的實(shí)時(shí)交通路由和按需捷徑計(jì)算做準(zhǔn)備；

圖3是根據(jù)本發(fā)明實(shí)施方案的用于實(shí)時(shí)交通路由的示例性過程邏輯的概述；

圖4是根據(jù)本發(fā)明實(shí)施方案的用于識(shí)別最小成本路徑的示例性過程邏輯的概述；