[發明專利]一種基于等效路阻分析和考慮消防栓動態可用性的路徑規劃方法

有效

• 申請號: 202110087151.5
• 申請日: 2021-01-22
• 公開（公告）號: CN112819212B
• 公開（公告）日: 2023-05-02
• 發明（設計）人: 饒瀚偉;楊海芬;林水生;周亮;于良;張輝
• 申請（專利權）人: 電子科技大學
• 主分類號: G06Q10/047
• 分類號: G06Q10/047;G06Q50/26
• 代理公司: 電子科技大學專利中心 51203
• 代理人: 陳一鑫

1.一種基于等效路阻分析和考慮消防栓動態可用性的路徑規劃方法，包含以下步驟：

步驟1：將全局路網符號化，為城市路網中的每個路段均設置全局唯一的ID；

I＝{i₁,i₂,……,i_N}，其中的元素表示路段；

步驟2：引入密度-速度關系公式，由歷史通行數據和當前路段的車輛密度k，預估各個路段消防車的通行速度V(k)；

其中，該路段的歷史通行數據包括V_min為阻塞流速度，k_max為阻塞流密度，V_free為自由流速度，k_min為自由流密度，k為當前密度，a、b為常數；

步驟3：選取主要影響道路通行狀態的因素，運用層次分析法，得到單一路段的量化后的通行狀態系數

具體為采用層次分析法對影響道路通行狀態的屬性賦予不同的權值ω_i，然后將各路段相應屬性進行無量綱化處理得到m_i，與通過層次分析法得到的評價指標體系各因素影響權重進行相乘與加總，得到單一路段的通行狀態系數：

步驟4：考慮道路通行狀態系數與道路實際長度d_i對道路通行實際情況共同起作用，且兩者相互獨立，定義路段的當量長度為：

步驟5：基于各個路段的當量長度和預估通行速度，得到各個路段預估的通行時間t_i：

完成各路段通行代價的計算后，得到各路段預估通行時間數據集合T＝{t₁，t₂，……，t_N}，存入數據庫中以備調取，并以一定的時間間隙不斷更新各路段的預估通行時間；

步驟6：當火情發生時，調取監測范圍內的消防資源點可用性情況，確定起點和終點{a，b}；可用且需要通過的消防栓所屬的路段節點集合{i_x,i_y，i_z，……}，其中各元素表示可用消防栓所在路段ID；需要經過的消防栓個數k；各路段預估通行時間數據集合T＝{t₁，t₂，……，t_N}，然后進行路徑規劃，得到路網中起點、終點以及各消防栓所屬路段節點之間預估通行時間的代價矩陣；

步驟6.1：用啟發式搜索法進行路徑搜索，公式表示為：

f(i_n)＝g(i_n)+h(i_n)

式中，f(i_n)為起始點經由道路節點i_n到目標節點的代價；

g(i_n)為起始點到當前節點i_n的實際通行代價，也就是起點到該點的預估通行總時長；

h(i_n)為從當前節點n到目標節點路徑的代價估計；

步驟6.2：選擇路段集合I中的兩個節點作為起始點和目標點，設起點為a和終點為b，建立兩個存儲節點元素的集合，開集O＝{}：表示待選擇的路段節點，閉集C＝{}：表示可能需要通過的路段節點；然后將起始點a放入到開集O中；

步驟6.3：判斷開集O是否為空，若是空則結束計算；若否則執行步驟6.4；

步驟6.4：遍歷O集合，選擇開集中到目標節點b啟發距離f(n)最小的路段節點i_min作為當前節點，然后判斷當前節點是否為目標節點；若是則不斷回溯父節點，得到從a到b的路徑以及總的預估通行時間，總的預估通行時間作為后續步驟里代價矩陣M中兩點間通行代價的數據來源，并跳出步驟6；若不是，則執行步驟6.5；

步驟6.5：將當前路段節點從開集O中移除，并加入到閉集C中，對當前路段節點進行松弛操作，即遍歷當前路段節點的所有鄰接路段節點，并進行如下判斷：

(1)若該路段節點在C中，則跳過該節點；

(2)若該路段節點不在O中，則將該路段節點加入到開集O中，計算并記錄下該路段節點的f(i_n)，g(i_n)，h(i_n)的值，并將當前節點i_min記作該節點i_n的父節點；其中f(i_n)＝g(i_n)+h(i_n)，g(i_n)＝g(i_n的父節點)+t_n，h(i_n)為該路段節點i_n到目標節點的歐式距離與當前預估通行速度的比值；

(3)若該路段節點在O中，則比較此時新計算出的g(i_n)與之前記錄的該路段節點的g(i_n)作比較；如果新的g(i_n)值更小，則更新其g(i_n)和f(i_n)的值，并將該節點的父節點更新為當前的i_min；

然后返回執行步驟6.3；

步驟7：對從a到b，且經過所有P中道路階段點的路徑可行域中的解進行全局搜索，計算全局最優解；

步驟7.1：設H＝1，由輸入的起點a、終點b、和消防栓路段節點集合P隨機產生一組初始解S₀，令最終結果S＝S₀；即由起點a出發，以某種順序依次通過P中隨機選取的k個路段節點，并最終到達終點b的一條路徑；結合代價矩陣計算路徑總代價C(S₀)；

步驟7.2：隨機產生一組新解S₁，即由起點a出發，以另一種與S₀不同的順序依次通過P中隨機選取的k個路段節點，并最終到達終點b的一條路徑；計算路徑代價C(S₁)，得到代價差ΔC＝C(S₀)-C(S₁)，判斷ΔC是否小于等于0；若是，則接受新解S＝S₁，C(S)＝C(S₁)；若否，則按概率接受新解；

步驟7.3判斷當前是否達到迭代次數，若是執行步驟7.4，若否執行步驟S7.2；

步驟7.4判斷當前是否滿足終止條件，若是，則結束計算，輸出產生的最優的通過消防栓與救援路徑；若否，降低溫度H＝H*0.85，重置內循環迭代次數；

步驟8：輸出路徑，結束算法循環。