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

有效

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

1.基于動態路網的層級優先最優路徑計算方法，其特征是，包括：

步驟1，根據道路等級將路網劃分成K個等級的路網，對K個等級的路網進行分層，獲得K個層級的路網，分別生成各層級路網對應的Voronoi圖；其中，第k層級的路網由第k等級、第k-1等級……第1等級的路網構成，k=1，2…K，K值取路網的道路等級數量；

步驟2，基于Voronoi圖進行路徑搜索，本步驟包括搜索最優路徑的主體部分和分支部分；

所述的搜索最優路徑的主體部分進一步包括：

2.1利用線性搜索算法由源點O和目標點D匹配路網的起始搜索層級，將起始搜索層級路網對應的Voronoi圖作為當前Voronoi圖，O和D所在的V區分別記為起點V區和終點V區，V區即Voronoi區域；

2.2基于當前Voronoi圖進行最短路徑搜索；

2.3順次檢查最短路徑所包含路段的連通性，對不連通的前后兩路段，以前后兩路段所在V區的并集的最小外接矩形為搜索范圍，執行子步驟2.4；若所包含所有路段均連通，結束，執行子步驟2.5；

2.4判斷當前搜索層級路網是否為最低層級路網，若是，基于搜索范圍內的所有層級路網數據進行最短路徑搜索，將搜索到的路徑保存到候選路徑數據集；否則，將當前搜索層級路網的下一層級路網所對應的Voronoi圖作為當前Voronoi圖，搜索范圍內遍歷當前Voronoi圖的所有V區，根據當前Voronoi圖中道路路段間的空間關系確定當前Voronoi圖中的起點V區和終點V區，執行子步驟2.2；

所述的搜索最優路徑的分支部分進一步包括：

2.5當前搜索層級路網初始化為子步驟2.1所匹配的起始搜索層級路網的下一層級路網；

2.6基于當前搜索層級路網對應的Voronoi圖，以O或D所在的V區為搜索范圍，在當前搜索層級路網中尋找與該搜索范圍相交的V區；

2.7判斷該相交的V區是否為主體部分所在的V區，若是，將當前搜索層級路網的下一層級路網作為當前搜索層級路網，執行子步驟2.6；否則，基于當前搜索層級路網對應的Voronoi圖，以O所在的V區為起點V區或以D所在的V區為終點V區，以主體部分所在V區為終點V區或起點V區；

2.8基于當前搜索層級路網對應的Voronoi圖進行最短路徑搜索；

2.9將當前搜索層級路網的下一層級路網作為當前搜索層級路網，基于當前搜索層級路網對應的Voronoi圖，以O所在的V區為起點V區或以D所在的V區為終點V區，以所搜索的最短路徑所在的V區為終點V區或起點V區，執行子步驟2.8；

2.10重復子步驟2.8~2.9直至O或D落至最短路徑或當前搜索層級路網為最低層級路網；

步驟3，根據步驟2所獲得最優路徑的主體部分和分支部分生成最優路徑。

2.如權利要求1所述的基于動態路網的層級優先最優路徑計算方法，其特征是：

步驟1中所述的對K個等級的路網進行分層，具體為：

（1）采用如下規則對路段進行分裂和合并：

所述的分裂原則為：

當多條路段相交于一交點，且該交點不同時為該多條路段的端點時，對該多條路段進行分裂，分裂時遵循“低等級路網被高等級路網打斷，高等級路網不被低等級路網打斷”；

所述的合并原則為：

對僅有一個交點的兩條路段，若該交點同時為兩條路段的端點，對該兩條路段進行合并；

（2）基于路段分裂和合并后的路網進行分層，其中，第k層級的路網由第k等級、第k-1等級……第1等級的路網構成。

3.如權利要求1所述的基于動態路網的層級優先最優路徑計算方法，其特征是：

子步驟2.1中所述的利用線性搜索法確定搜索路網的起始層級，具體為：

將源點O和目標點D的連線延長至連線總長度的10%，即得到搜索算子，獲取與搜索算子相交的所有路段的層級，最高層級即起始層級。

4.如權利要求1所述的基于動態路網的層級優先最優路徑計算方法，其特征是：

子步驟2.1中，若O和D所在的V區相同，將該相同V區中路段保存到候選路徑數據集后，結束，然后執行子步驟2.5。