[發明專利]基于角度限制和雙向搜索的城市路網最短路徑獲取方法

有效

• 申請號: 202110235456.6
• 申請日: 2021-03-03
• 公開（公告）號: CN112991800B
• 公開（公告）日: 2022-03-15
• 發明（設計）人: 丁建勛;馮戰雨;江宇鵬;周潤東;丁衛東;滿忠運;查菲菲;夏力;徐小明;龍建成
• 申請（專利權）人: 合肥工業大學
• 主分類號: G08G1/0968
• 分類號: G08G1/0968
• 代理公司: 安徽省合肥新安專利代理有限責任公司 34101
• 代理人: 陸麗莉;何梅生

本發明公開了一種基于角度限制和雙向搜索的城市路網最短路徑獲取方法，包括：1.由實時路況信息構建城市網絡；2.引入前向搜索邊界內外部交叉口集合U_n^F、后向搜索邊界內外部交叉口集合U_n^B、雙向邊界交叉口集合為M_n、行程時間上下界T；3.更新集合前后向搜索邊界內外部交叉口集合U_n^F、U_n^B、4.通過標號修正法得到出發點經雙向邊界交叉口集合M_n中交叉口到目的點的最短路徑；5.最短路徑行程時間等于行程時間下界T或者前后向搜索邊界內部交叉口集合U_n^F、U_n^B不再更新，則可獲得最短路徑，否則更新轉步驟3。本發明考慮在城市路網的導航中加入角度限制以及雙向搜索，從而有效地縮小搜索范圍，提高導航效率并能提供更快捷、高效的行駛路徑。

技術領域

本發明屬于現有城市路網的導航優化領域，具體的說是一種基于角度限制和雙向搜索的城市路網最短路徑獲取方法。

背景技術

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

現階段的城市路網中，各個等級道路(快速路、主干道、次干道、支路)交宗錯雜，道路等級因素嚴重影響導航行程各個方面，現階段的導航產品在導航過程中往往無法有效利用這一因素進而提高導航過程的時效性，嚴重影響了駕駛員的出行體驗以及城市路網的利用效率。此外；在具體導航過程中的路徑搜索階段，已有路徑搜索方法往往是在根據實時路網信息在全局范圍內從起點到終點單個方向地進行進行路徑搜索，這種路徑搜索的方法沒有考慮到導航的中駕駛員行駛的方向性，降低了導航過程的路徑搜索的時效性以及與駕駛員出行意愿的匹配程度。

發明內容

本發明是為了解決上述現有技術存在的不足之處，提出一種基于角度限制和雙向搜索的城市路網最短路徑獲取方法，以期能在城市路網導航中加入方向性誘導以及角度限制縮小搜索范圍，并通過雙向搜索提高路徑搜索效率，從而能提高導航效率并提供給駕駛員一種更人性化、更高效的最短路徑，讓行駛過程更高效。

本發明為達到上述發明目的，采用如下技術方案：

本發明一種基于角度限制和雙向搜索的城市路網最短路徑獲取方法的特點按如下步驟進行：

步驟1：構建城市路網并獲取任意交叉口的平面坐標；