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

有效

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

1.一種基于角度限制和雙向搜索的城市路網最短路徑獲取方法，其特征按如下步驟進行：

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

獲取實時道路網絡數據并得到城市路網G＝(V,A)，其中，V表示交叉口集合，V＝{v₁,v₂,…,v_q,…,v_Q}，v_q表示第q個交叉口，q＝1,2,…,Q；Q表示交叉口的總數，A表示交叉口之間的路段集合，且A＝{a_ij＝(v_i,v_j)|i,j＝1,2,...Q}，a_ij表示第i個交叉口v_i與第j個交叉口v_j之間的路段，且a_ij∈{A₁,A₂,A₃,A₄}，其中A₁表示快速路，A₂表示主干道，A₃表示次干道，A₄表示支路；令路段a_ij上的時間權重屬性為t_ij，且d_ij表示路段a_ij的長度，v_ij表示路段a_ij的預期通行車速；若第i個交叉口v_i與第j個交叉口v_j之間沒有路段，則令t_ij＝+∞；

根據實時道路網絡數據得到城市道路中第i個交叉口v_i的平面坐標為(x_i,y_i)和第j個交叉口v_j的平面坐標為(x_j,y_j)，則第i個交叉口v_i與第j個交叉口v_j之間的路段向量記為

步驟2：假設駕駛員的出發點為第s個交叉口，目的點為第t個交叉口v_t，并以出發點到目的點的方向的行駛方向為前向搜索方向，以目的點到出發點方向的行駛方向為后向搜索方向，給定路徑搜索的限制角度為α，且0≤α≤π；

步驟3：定義參數并初始化；

步驟3.1：定義基礎參數：

定義n為當前迭代次數，則第n次迭代的第s個交叉口v_s到第j個交叉口v_j的最短行程時間為T_n(v_s,v_j)；定義第s個交叉口v_s與第t個交叉口v_t的歐式距離記為l_st，定義v_max為所有路段類型中行駛的最大速度，則定義第s個交叉口v_s到第t個交叉口v_t的理論最短行程時間為并作為行程時間下界；定義第n次迭代的出發點的交叉口v_s和目的點的交叉口v_t之間的最短行程時間為T_n(v_s,v_t)，并作為行程時間上界

步驟3.2：定義前向搜索參數：

定義第n次迭代的前向搜索邊界內部交叉口集合為定義第n次迭代的前向搜索邊界外部交叉口集合為定義前向搜索擴充邊界交叉口集合記為

步驟3.3：定義后向搜索參數：

定義第n次迭代的后向搜索邊界內部交叉口集合為定義第n次迭代的后向搜索邊界外部交叉口集合為定義后向搜索擴充邊界交叉口集合記為

步驟3.4：定義第n次迭代的雙向邊界交叉口集合為定義第n次迭代的邊界內部交叉口

步驟3.5：參數初始化：

初始化n＝1，

步驟4：更新第n次迭代的前向搜索邊界內部交叉口集合前向搜索邊界外部交叉口集合后向搜索邊界內部交叉口集合后向搜索邊界外部交叉口集合

步驟4.1：更新第n次迭代的前向搜索邊界內部交叉口集合和向搜索邊界外部交叉口集合

將滿足a_sk＝(v_s,v_k)∈A的第k個交叉口v_k作為鄰居交叉口；并遍歷第s個交叉口v_s的所有鄰居交叉口，如果成立，則將賦值給將第k個交叉口v_k加入擴充邊界交叉口集合否則，將賦值給其中，表示第s個交叉口v_s和第k個交叉口v_k之間的路段向量，表示第s個交叉口v_s和第t個交叉口v_t之間的路段向量；

步驟4.2：更新第n次迭代的后向搜索邊界內部交叉口集合和后向搜索邊界外部交叉口集合

將滿足a_lt＝(v_l,v_t)∈A的第l個交叉口v_l作為鄰居交叉口；遍歷第t個交叉口v_t的所有鄰居交叉口，如果成立，則將賦值給將第l個交叉口v_l加入擴充邊界交叉口集合否則，將賦值給其中，表示第t個交叉口v_t和第l個交叉口v_l之間的路段向量，表示第t個交叉口v_t和第s個交叉口v_s之間的路段向量；

步驟5：如果擴充邊界交叉口集合則轉入步驟6，否則按照步驟5.1和步驟5.2繼續更新第n次迭代的前向搜索邊界內部交叉口集合前向搜索邊界外部交叉口集合后向搜索邊界內部交叉口集合后向搜索邊界外部交叉口集合

步驟5.1：繼續更新第n次迭代的前向搜索邊界內部交叉口集合和第n次迭代的前向搜索邊界外部交叉口集合

步驟5.1.1：判斷前向搜索擴充邊界交叉口集合中第i個交叉口v_i：

步驟5.1.2：將滿足a_ij＝(v_i,v_j)∈A的第j個交叉口v_j作為鄰居交叉口，且

遍歷第i個交叉口v_i的所有鄰居交叉口，如果成立，則將賦值給將第i個交叉口v_i從前向搜索擴充邊界交叉口集合中刪除，將賦值給并執行步驟5.1.3；其中，表示第i個交叉口v_i和第j個交叉口v_j之間的路段向量，表示第i個交叉口v_i和第t個交叉口v_t之間的路段向量；否則，將賦值給將第i個交叉口v_i從前向搜索擴充邊界交叉口集合中刪除；并按照步驟5.1.2的過程判斷前向搜索擴充邊界交叉口集合中的下一個交叉口；

步驟5.1.3：按照步驟5.1.2的過程判斷前向搜索擴充邊界交叉口集合中的第j個交叉口v_j；

步驟5.2：繼續更新第n次迭代的后向搜索邊界內部交叉口集合和第n次迭代的后向搜索邊界外部交叉口集合

步驟5.2.1：判斷后向搜索擴充邊界交叉口集合中第m個交叉口v_m：

步驟5.2.2：將滿足a_mn＝(v_m,v_n)∈A的第n個交叉口v_n作為鄰居交叉口，且

遍歷第m個交叉口v_m的所有鄰居交叉口，如果則將賦值給將第m個交叉口v_m從后向搜索擴充邊界交叉口集合中刪除，將賦值給并執行步驟5.2.3；其中，表示第m個交叉口v_m和第n個交叉口v_n之間的路段向量，表示第m個交叉口v_m和第s個交叉口v_s之間的路段向量；否則，將賦值給將第m個交叉口v_m從后向搜索擴充邊界交叉口集合中刪除；并按照步驟5.2.2的過程判斷后向搜索擴充邊界交叉口集合中的下一個交叉口；

步驟5.2.3：按照步驟5.2.2的過程判斷后向搜索擴充邊界交叉口集合中的第n個交叉口v_n；

步驟6：更新第n次迭代的雙向邊界交叉口集合M_n并得到經過第n次迭代的雙向邊界交叉口集合M_n內交叉口的最短行程時間；

步驟6.1：通過標號修正法得到出發點的交叉口v_s到第n次迭代的前向搜索邊界內部交叉口集合內任一交叉口的最短行程時間及最短路徑，其中，出發點的交叉口v_s到第n次迭代的雙向邊界交叉口集合M_n內的第k個交叉口v_k的最短行程時間為T_n(v_s,v_k)；

步驟6.2：通過標號修正法得到目的點的交叉口v_t到第n次迭代的后向搜索邊界內部交叉口集合內任一交叉口的最短行程時間及最短路徑，其中，目的點的交叉口v_t到第n次迭代的雙向邊界交叉口集合M_n內的第k個交叉口v_k的最短行程時間為T_n(v_t,v_k)；

步驟6.3：遍歷第n次迭代的雙向邊界交叉口集合M_n內第k個交叉口v_k，則出發點的交叉口v_s到目的點的交叉口v_t的最短行程時間

步驟6.4：判斷行程時間最優性并更新行程時間上界

步驟6.4.1：如果T_n(v_s,v_t)＝T，則轉入步驟12；否則，轉入步驟6.4.2；

步驟6.4.2：將第s個交叉口v_s到第t個交叉口v_t的時間上界更新為令前后向搜索擴充邊界交叉口轉入步驟7；

步驟7：基于行程時間上界繼續更新第n次迭代的前向搜索邊界內部交叉口集合前向搜索邊界外部交叉口集合后向搜索邊界內部交叉口集合后向搜索邊界外部交叉口集合

步驟7.1：基于行程時間上界繼續更新第n次迭代的前向搜索邊界內部交叉口集合和前向搜索邊界外部交叉口集合

對于第n次迭代的前向搜索邊界外部交叉口集合中的第i個交叉口v_i，從出發點的交叉口v_s到第i個交叉口v_i、第i個交叉口v_i到目的點的交叉口v_t兩者的理論最短行程時間之和為其中，l_si表示第s個交叉口v_s與第i個交叉口v_i的歐式距離，l_it表示第i個交叉口v_i與第t個交叉口v_t的歐式距離；如果則將賦值給將第i個交叉口v_i加入前向搜索擴充邊界交叉口集合將第i個交叉口v_i從前向搜索邊界外部交叉口集合中刪除，從而得到更新后的前向搜索邊界外部交叉口集合否則，將第i個交叉口v_i從前向搜索邊界外部交叉口集合中刪除，從而得到更新后的前向邊界外部交叉口集合

步驟7.2：基于行程時間上界繼續更新第n次迭代的后向搜索邊界內部交叉口集合和后向搜索邊界外部交叉口集合

對于第n次迭代的后向搜索邊界外部交叉口集合中的第m個交叉口v_m，從出發點的交叉口v_s到第m個交叉口v_m、第m個交叉口v_m到目的點的交叉口v_t兩者的理論最短行程時間之和為其中，l_sm表示第s個交叉口v_s與第m個交叉口v_m的歐式距離，l_mt表示第m個交叉口v_m與第t個交叉口v_t的歐式距離；如果則將賦值給將第i個交叉口v_i加入后向搜索擴充邊界交叉口集合將第i個交叉口v_i從后向搜索邊界外部交叉口集合中刪除，從而得到更新后的后向搜索邊界外部交叉口集合否則，將第i個交叉口v_i從后向搜索邊界外部交叉口集合中刪除，從而得到更新后的后向邊界外部交叉口集合

步驟8：基于行程時間上界繼續更新第n+1次迭代的前向搜索邊界內部交叉口集合前向搜索邊界外部交叉口集合后向搜索邊界內部交叉口集合后向搜索邊界外部交叉口集合

步驟8.1：基于行程時間上界繼續更新第n+1次迭代的前向搜索邊界內部交叉口集合和前向搜索邊界外部交叉口集合

依次判斷前向搜索擴充邊界交叉口集合中第i個交叉口v_i，遍歷第i個交叉口v_i的鄰居交叉口，即滿足a_ij＝(v_i,v_j)∈A的第個j交叉口v_j，且的第j個交叉口v_j，如果且則將第i個交叉口v_i從前向搜索擴充邊界交叉口集合中刪除，將賦值給否則，將第i個交叉口v_i從前向搜索擴充邊界交叉口集合中刪除，將賦值給其中，表示第i個交叉口v_i和第j個交叉口v_j之間的路段向量，表示第i個交叉口v_i和第t個交叉口v_t之間的路段向量；

步驟8.2：基于行程時間上界繼續更新第n+1次迭代的后向搜索邊界內部交叉口集合和后向搜索邊界外部交叉口集合

依次判斷后向搜索擴充邊界交叉口集合中第m個交叉口v_m，遍歷第m個交叉口v_m的鄰居交叉口，即滿足a_mn＝(v_m,v_n)∈A的第m個交叉口v_m，且的第n個交叉口v_n，如果且則將第m個交叉口v_m從后向搜索擴充邊界交叉口集合中刪除，將賦值給否則，將第m個交叉口v_m從后向搜索擴充邊界交叉口集合中刪除，將賦值給其中，表示第m個交叉口v_m和第n個交叉口v_n之間的路段向量，表示第m個交叉口v_m和第s個交叉口v_s之間的路段向量；

步驟8.3：更新第n+1次迭代的雙向邊界交叉口集合

步驟9：判斷U_n+1＝U_n是否成立，若成立，則執行步驟10；否則，將n+1賦值給n，轉入步驟6；

步驟10：輸出標號修正法所得到的最短路徑，如果n＝1，則最終的最短行程時間為T^*＝T，否則，