[發明專利]基于動態路網的層級優先最優路徑計算方法

有效

• 申請號: 201610966010.X
• 申請日: 2016-10-28
• 公開（公告）號: CN108009666B
• 公開（公告）日: 2020-04-10
• 發明（設計）人: 賈濤;胡正華
• 申請（專利權）人: 武漢大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 胡艷

本發明公開了一種基于動態路網的層級優先最優路徑計算方法，包括：步驟1，根據道路等級將路網劃分層級，分別生成各層級路網對應的Voronoi圖；步驟2，采用層次化的搜索策略進行路徑搜索，基于最短路徑搜索法分別搜索最優路徑的主體部分和分支部分；步驟3，根據最優路徑的主體部分和分支部分生成最優路徑。本發明可大大減少出行車輛在道路上的行駛時間，并且可響應路網中交通流狀態的變化，進而為車輛出行的路徑選擇提供可靠的實時解決方案，從而使得出行方案更具適應性和可靠性。

技術領域

本發明屬于智能交通技術領域，尤其涉及一種基于動態路網的層級優先最優路徑計算方法。

背景技術

近年來，如何在出行的起點和終點間尋找一條最優路徑已成為智能交通的熱門研究話題。它不僅直接影響了人們的出行效率，同時也涉及到諸如城市發展和環境污染等問題。例如，車輛在一條路況較差的道路上行駛，不僅會增加出行成本，并進一步加劇道路交通堵塞的狀況，以及隨之而來的尾氣污染問題。許多專業的地理信息系統軟件(如ArcGIS)都提供了在道路網中求解由源點位置到目標位置的最短路徑的功能，但是常規方法都是基于靜態交通流信息，并沒有結合城市路網上交通流隨時空變化的特點來對出行車輛進行有效誘導。

隨著信息通信技術的進步和GPS傳感器的廣泛應用，有學者開始利用移動物體的軌跡來對其行為進行分析，并對其進行動態的監測。其中，出租車的GPS軌跡數據因其包含的即時行車速度可準確反映道路通行狀態而備受學者關注。例如，有一些研究學者通過計算每一段道路的通行頻率來提取駕駛員的經驗進而為他人提供有效的導航服務。還有學者從GPS軌跡數據中來研究大件運輸車輛的行車特性。最近有學者開始著手于了解車輛實際的運行路線和GPS模擬線路之間的關系。盡管如此，如何從大量的GPS軌跡數據中提煉出更有用的信息，一直是路線規劃行業中一個懸而未決的問題。

此外，在規劃車輛出行路線的過程中，能夠結合人類的認知行為的研究還不多見，雖然有研究認為人們在出行過程中更傾向于從轉向較少的路線上通過，而不僅僅局限于物理意義上的距離最短，因為這將大大減少人們認知的負擔，但沒有進一步對這些道路的特點進行詳細的分析。實際上，路網的等級是道路的一個基本屬性，它是根據道路的功能、位置和行車容量而將整個城市的路網劃分成了不同的子集。對于距離較長的出行路線，利用路網等級對出行者進行指引會大大降低其認知的負擔。另一個重要的原因是由于高等級路網往往對應了較好的行車路況，出行者從高等級路網通行可以大幅度節省出行的時間。

文中涉及如下參考文獻：

[1]Chen,B.Y.,et al.,2014.Map-matching algorithm for large-scale low-frequency floating car data.International Journal of Geographical InformationScience,28(1),22–38.doi:10.1080/13658816.2013.816427

[2]Daltona A.M.,Jones A.P.,Panter J.,and Ogilvie D.(2015),Are GIS-modeled routes a useful proxy for the actual routes followed by commuters,Journal of Transport &Health,2,219-229

[3]Geisberger R,Sanders P,Schultes D,and Vetter C 2012Exact routingin large road networks using contraction hierarchies.Transportation Science46:388–404