[發明專利]一種基于柵格路網的應急路徑規劃架構和方法

有效

• 申請號: 202011509992.2
• 申請日: 2020-12-19
• 公開（公告）號: CN112797997B
• 公開（公告）日: 2022-12-16
• 發明（設計）人: 楊博文;遲遠英;丁治明;侯治剛;伍佳名;袁磊;劉遵豪;劉元柱
• 申請（專利權）人: 北京工業大學
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 北京思海天達知識產權代理有限公司 11203
• 代理人: 沈波

1.一種基于柵格路網的應急路徑規劃架構，其特征在于：該架構分為三部分，由下向上分別為：數據建模層、路網預處理層、路徑規劃層；首先，最下層通過獲取路網的各項數據，將各項數據進行處理和整合后，映射到二維的平面地圖上；中間層為路網預處理層，該層的作用是將路網進行柵格化處理后分成若干個等間距的柵格，每個柵格內分別存儲的有若干不等的路口和道路，并通過排序算法對整個路網進行柵格排序并賦予特征值，該特征值是反應柵格當前的路網通行能力；最上層為路徑規劃層；

數據建模層中，利用層次回溯法能夠對那些缺失GPS點的數據進行補全；層次回溯法是將不同時間同一地理位置的車流量進行疊加處理；將不同時間下相同道路的車流量進行疊加，形成整體車流量狀況；

利用車輛的歷史軌跡數據進行道路流量還原有效的將城市路網進行建模，首先將六個月的出租車軌跡數據進行分時段處理，將通過給定的時間間隔對數據進行 分離，此時將得到不同時段的整個路網的車流量運行狀況；接下來，通過對現有的GPS數據進行路網匹配處理，由于軌跡點可能會偏離到道路的兩側，所以需要對現有的數據進行最近鄰的匹配工作；最后，將城市中每條道路的經緯度點進行整合，將每條GPS數據還原到每條對應的道路上；通過六個月的軌跡數據對城市中每條道路的車流量情況進行回溯；

路網預處理層中，通過對城市道路整體車流量的回溯，根據不同的時間，城市中每個區域都會有所屬的語義標簽去定義區域當前的狀況；等區間劃分柵格使路網數據能夠通過合理的等區間大小被劃分成若干個區域子塊，通過區域子塊的管理能夠對整個路網路口節點情況進行判斷；每個區域內包含路口的數量和出入度情況表示為該區域的聯通能力，路口數量和出入度數量多的區域得到較高的排序值，意味著車輛駛入這些區域時導向其他柵格的概率較高；將對PageRank進行改進并用作排序算法，稱之為Grid PageRank；將整個路網映射成圖結構；

路徑規劃層中，分為兩部分，一部分為車輛的應急疏散方法，另一部分為車輛的繞行路徑規劃方法；疏散路線的選擇是車輛疏散中的關鍵問題，其規劃出的結果直接影響疏散效果；車輛疏散是一個多點到多點的路徑規劃問題，一方面要選擇暢通路段進行疏散，另一方面應盡量均勻的向通行能力較強的路段分配；路線狀況由歷史路網數據進行回溯并建模，即通過對監控車輛數據進行矢量提取，獲取路段的狀態；路段中車輛的密度狀態的大小一定程度上反映路段擁堵狀況；路段車輛密度越大，交通越擁堵；反之，路段車輛密度越小，路段交通狀況越好；路徑疏散根據已經劃分好的柵格區域重要性排序進行疏散，車輛依據多態勢信息的綜合加權計算出疏散路線；在計算路徑時，由于態勢信息不斷改變的特點，所以要求規劃算法考慮時間因素，即車輛到達某點的時間準確的方式規劃路線并抵達安全區域；路徑規劃算法利用柵格雙向Dijkstra算法，該算法是根據雙向Dijkstra算法改進后得到。

2.利用權利要求1所述架構進行的一種基于柵格路網的應急路徑規劃方法，其特征在于：包括如下步驟，

S1讀取軌跡數據及路網數據；將每條軌跡數據進行分析，提取每條信息的經緯度坐標，根據路網坐標并將這些數據匹配到對應的路網中，由此從軌跡數據中獲取路網的速度；路網速度通過歷史回溯方法得到，將六個月的歷史軌跡數據按天進行展開，將每條道路上的按時間進行回溯，并根據每天的車流量進行疊加計算以此來獲得每條道路根據不同時間的車流量；

S2獲得應急事件所在的柵格ID；通過路口所在的經緯度坐標映射到二維的直角坐標系內，使整個路網數據轉成二維坐標格式，經轉換后的路口變成平面內的一個點，接著通過歐氏距離找到處在整個路網離坐標原點最近的路口點代替原點，使得整個路網坐標進行平移；根據平移過的節點坐標對柵格進行等距離的劃分；

S3通過劃分柵格后對每個柵格進行排序賦值；首先計算每個柵格的節點數，接著需要計算每個柵格內連到其他柵格的道路車道數，通過柵格內的路口個數和車道數來計算每個柵格的通行能力，使用Grid PageRank算法對每個柵格進行排序，該算法是改進PageRank后得到的，其思想就是初始將每個柵格先進行預賦值，通過柵格內部鏈入其他柵格道路的權重進行依次賦值，由于一個柵格內通向另一個柵格的道路不止一條，所以要將權重平均化，每個柵格都以這樣的方式進行賦值計算，直到每個柵格經過了一輪賦值；此過程為一次排序；最終經過多次迭代使得每個柵格的排序值與自身上一次的值進行比較后同時都滿足小于一個閾值則Grid PageRank算法結束，并得到每個柵格的最終排序值，該值代表了當前柵格的通行能力值；

S4通過GBD對處在應急區域的車輛進行路徑規劃，并選擇當前通行能力較大的道路提供給車輛；柵格經過排序后都會得到相應的排序值，此時通過GBD算法對車輛進行應急路徑規劃；GBD算法分為兩部分：首先是對每個柵格間進行一個路徑規劃，其次是在每個柵格內進行路徑規劃；在柵格間采用柵格排序值作為判斷依據來推薦所處柵格周圍連通的且通行能力強的柵格，此時被推薦的柵格設置一個標簽，即表示是否被推薦過，此處設置是為了保證車輛不走重復的柵格；柵格內采用雙向Dijkstra算法，此時的起始點為上一個柵格通向此柵格相連的節點，終點為通向下一個柵格的最后一個節點，來加快路徑規劃時間；最終向車輛提供一組柵格集合且加上每個柵格內的所有道路集合。