[發(fā)明專利]基于兩階段法與方向誘導(dǎo)的城市路網(wǎng)最短路徑獲取方法及應(yīng)用

有效

• 申請(qǐng)?zhí)枺?/td>: 202211152024.X
• 申請(qǐng)日: 2022-09-21
• 公開(kāi)（公告）號(hào): CN115547087B
• 公開(kāi)（公告）日: 2023-06-27
• 發(fā)明（設(shè)計(jì)）人: 丁建勛;楊貝諾;陳語(yǔ);黃軍鵬;段睿;王予悅;詹興斌;龍建成
• 申請(qǐng)（專利權(quán)）人: 合肥工業(yè)大學(xué)
• 主分類號(hào): G08G1/0968
• 分類號(hào): G08G1/0968
• 代理公司: 安徽省合肥新安專利代理有限責(zé)任公司 34101
• 代理人: 陸麗莉;何梅生

本發(fā)明公開(kāi)一種基于兩階段法與方向誘導(dǎo)的城市最短路徑獲取方法及應(yīng)用，該方法包括：1.由路況信息構(gòu)建城市網(wǎng)絡(luò)；2.計(jì)算方向權(quán)βsubgt;ij/subgt;；3.第一階段基于βsubgt;ij/subgt;通過(guò)標(biāo)號(hào)設(shè)置法獲取起點(diǎn)交叉口節(jié)點(diǎn)到終點(diǎn)交叉口節(jié)點(diǎn)的初始最短行程時(shí)間及路徑，更新行程時(shí)間上界4.第二階段基于通過(guò)標(biāo)號(hào)修正法得到起點(diǎn)交叉口節(jié)點(diǎn)到終點(diǎn)交叉口節(jié)點(diǎn)的最終最短行程時(shí)間及路徑；5.回溯輸出最短路徑及最短行程時(shí)間。本發(fā)明考慮在城市路網(wǎng)的導(dǎo)航中加入方向性的誘導(dǎo)有效地縮小搜索范圍，并結(jié)合啟發(fā)式算法與標(biāo)號(hào)修正法兩種最短路算法的優(yōu)勢(shì)，能提高導(dǎo)航效率，從而促進(jìn)交通的高效運(yùn)行。

技術(shù)領(lǐng)域

本發(fā)明屬于城市路網(wǎng)的導(dǎo)航優(yōu)化領(lǐng)域，具體的說(shuō)是一種基于兩階段法與方向誘導(dǎo)的城市最短路徑獲取方法及其應(yīng)用。

背景技術(shù)

隨著社會(huì)的發(fā)展，基于互聯(lián)網(wǎng)的交通導(dǎo)航給用戶帶來(lái)了越來(lái)越大的便利，用戶可以在導(dǎo)航開(kāi)始階段輸入自己的出發(fā)地和目的地，就可以獲取導(dǎo)航產(chǎn)品自動(dòng)規(guī)劃的路徑。但隨著城市汽車保有量逐步攀升，路網(wǎng)建設(shè)相對(duì)滯后，交通資源浪費(fèi)，出行效率低的現(xiàn)象時(shí)有發(fā)生，不僅給城市居民出行帶來(lái)不便，也大大降低城市運(yùn)轉(zhuǎn)效率，給經(jīng)濟(jì)發(fā)展造成一定的損失。因而,需要研究一種提高出行水平以及城市路網(wǎng)利用率的路徑導(dǎo)航方法。隨著GPS、網(wǎng)絡(luò)技術(shù)、計(jì)算機(jī)技術(shù)的發(fā)展，車輛導(dǎo)航系統(tǒng)建立的條件已經(jīng)成熟，能否在城市路網(wǎng)范圍內(nèi)實(shí)現(xiàn)車輛的道路導(dǎo)航，實(shí)現(xiàn)車輛快速、暢通地到達(dá)目的地，已經(jīng)成為當(dāng)前研究的目標(biāo)。

然而，在具體導(dǎo)航過(guò)程中的路徑搜索階段，已有路徑搜索方法往往是在根據(jù)實(shí)時(shí)路網(wǎng)信息在全局范圍內(nèi)從起點(diǎn)到終點(diǎn)單個(gè)方向地進(jìn)行路徑搜索，這種路徑搜索的方法沒(méi)有考慮到導(dǎo)航的中駕駛員行駛的方向性，降低了導(dǎo)航過(guò)程的路徑搜索的時(shí)效性以及與駕駛員出行意愿的匹配程度。

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

本發(fā)明是為了解決上述現(xiàn)有技術(shù)存在的不足之處，提出一種基于方向誘導(dǎo)與兩階段法的城市最短路徑獲取方法及應(yīng)用，以期能在城市路網(wǎng)導(dǎo)航中加入方向性誘導(dǎo)縮小搜索范圍，并通過(guò)結(jié)合啟發(fā)式算法與標(biāo)號(hào)修正法兩種最短路算法提高導(dǎo)航效率，從而能更快速地得到最短路，促進(jìn)交通的高效運(yùn)行。

本發(fā)明為達(dá)到上述發(fā)明目的，采用如下技術(shù)方案：

本發(fā)明一種基于兩階段法與方向誘導(dǎo)的城市最短路徑獲取方法的特點(diǎn)在于，是按如下步驟進(jìn)行：

步驟1：構(gòu)建城市路網(wǎng)并獲取任意交叉口節(jié)點(diǎn)的平面坐標(biāo)；

獲取城市路網(wǎng)數(shù)據(jù)并得到城市道路網(wǎng)絡(luò)G＝(V,A)，其中，V表示交叉口節(jié)點(diǎn)集合，V＝{v₁,v₂,…,v_i,…,v_K}，v_i表示第i個(gè)交叉口節(jié)點(diǎn)，i＝1,2,…,K，K為所述城市路網(wǎng)G中的交叉口節(jié)點(diǎn)總數(shù)，A表示交叉口之間的路段集合，且A＝{(v_i,v_j)|i,j＝1,2,…,K}，(v_i,v_j)表示第i個(gè)交叉口節(jié)點(diǎn)v_i到第j個(gè)交叉口節(jié)點(diǎn)v_j的有向路段，t_ij為有向路段(v_i,v_j)的時(shí)間權(quán)重，且l_ij表示有向路段(v_i,v_j)的長(zhǎng)度，s_ij表示有向路段(v_i,v_j)的通行車速；若第i個(gè)交叉口節(jié)點(diǎn)v_i到第j個(gè)交叉口節(jié)點(diǎn)v_j之間存在有向路段(v_i,v_j)，則第j個(gè)交叉口節(jié)點(diǎn)v_j為第i個(gè)交叉口節(jié)點(diǎn)v_i的鄰接交叉口節(jié)點(diǎn)，第i個(gè)交叉口節(jié)點(diǎn)v_i為第j個(gè)交叉口節(jié)點(diǎn)v_j的前驅(qū)交叉口節(jié)點(diǎn)，且t_ij≥0；若第i個(gè)交叉口節(jié)點(diǎn)v_i到第j個(gè)交叉口節(jié)點(diǎn)v_j之間不存在有向路段，則令t_ij＝+∞；