基于DK算法的石化企業滅火救援路徑優化技術

張建軍

（青島消防救援支隊，山東 青島 266000）

石化企業發生火災將會危及人民生命和財產安全，必須進行及時有效的救援。從實際情況看，石化企業的火災成因復雜、燃燒物質種類繁多并伴有爆炸等其他危險，導致救援工作困難[1]。同時，石化企業廠區內道路網絡的復雜性，也進一步增加了救援難度。因此，要完成石化企業火災的救援工作，首先要制定合理的救援路線，確保救援隊伍和救援設備能夠安全可靠、快速及時地到達救援現場[2]。在火災現場中，救援路線可能由多個方案組成，哪一個方案更合理就需要通過路徑優化技術來搜尋[3]。該文針對石化企業的救援問題特點，建立一種基于DK算法的救援路線優化方法。

1 基于DK算法的路徑規劃

石化企業的火災救援路線的最佳選擇，最重要的指標之一就是可以使救援總路徑最短，從而提升救援效率。而DK算法就是一種最有針對性的最短路徑搜索算法。DK算法的基本原理是，按照決策樹的理論構建搜索救援的路徑樹，路徑樹的根節點應該滿足到達其他節點的路徑之和最短。

DK算法的具體實現過程如下：構建一個節點集合，并用S表示這個集合。在DK算法的初始狀態下，S中就有一個節點，這個節點用v0表示。隨著DK算法的搜索過程展開，不斷會有新的路徑搜索結果產生。設一條路徑可以用其經歷的節點集合為（v0，…，vk），那么就可以將vk添加到集合S中。按照這樣的辦法搜索到所有路徑之后，全部節點都會納入集合S中。

對找到的每條路徑的長度，可以用下面的方法表示第k條最短路徑，如公式（1）所示。

式中：參數dk為最短路徑的長度，函數min{}為求取集合中所有元素的最小值，參數di為所有可能路徑的長度，參數vi為節點集合中第i個節點，它可以是集合S中除去v0以外的任意一個節點。

隨著搜索深度的增加，原有路徑會有新的節點加入，使路徑長度進一步延伸。當一個新的路徑終點vk進入節點集合S以后，那么任意一條原有路徑di應該按照下面的方式進行長度上的更新處理，如公式（2）所示。

式中：參數（vk，vi）為節點vk到節點vi的弧的長度，參數c（vk，vi）則為節點vk到節點vi的弧上的權重大小。

根據有向圖理論的最小權重值路徑搜索策略如下。

第一，對最短路徑長度的上界進行處石化處理，如公式（3）～公式（5）所示。

式中：參數d（v）為已經搜索到的全部路徑的最短長度的上界，參數k（v）是設定的一個BOOL型變量，只有真（True）和假(false)兩種取值，參數p（v）為一個定點的向后方向上的指針。

第二，不但執行對k（v）= 的掃描處理，計算其中的節點，是否會出現一個能夠計算出新的最小長度的節點，如果可以得到，將其記錄下來d（v）。

第三，與第二步相同的操作在相鄰節點w上執行，即對k（w）=flase掃描處理，計算其中的節點，是否會出現一個能夠計算出新的最小長度的節點，如果可以得到，將其記錄下來d（w）。如果d（w）滿足如公式（6）所示的條件。

則更新d（w）和p（w）。

第四，不斷執行第二步和第三步，當k（v）=true是搜索過程結束，此時找到的路徑即為優化后的最短路徑。

2 DK算法的改進策略

2.1 DK算法的局限性

DK 算法的局限性有以下2點：第一，最短路徑一般是基于單一條件限制下的最短，這時DK算法是有效的。但是，很多情況下最短路徑的限制條件，同時包括多個指標，包括距離、時間、費用等。石化企業的救援工作中，這種路徑的最短判定就包括更多因素。第二，DK算法的靈活性稍差，對一些突發情況難以應對。而石化企業的火災救援，卻經常會出現突發情況。

2.2 DK算法的改進

為了解決DK算法的局限性問題，也為了更好地解決石化企業的火災救援問題，該文在DK算法的常規執行框架下，提出兩點改進策略。

第一，同時進行正向和反向搜索，其策略如圖1和圖2所示。

圖1 DK算法的正向搜索策略

圖2 同時進行正向和反向搜索的改進策略

圖1和圖2中，方框區域代表了石化企業火災現場救援區域，白色圓點代表了救援路徑搜索的起點，黑色圓點代表了救援路徑搜索的終點，黑色實線代表了搜索路徑和可能的搜索方向。

對DK算法而言，最優路徑的常規搜索策略，就是從起點開始，按照DK算法的搜索規則，一邊尋找可能的路徑一邊比較，直至找到一條到達終點的最短的路徑。這種情況如圖1所示。為了提高搜索效率并更好地滿足多車輛協調救援任務的全局性要求，該文提出同時進行正向和反向搜索的改進策略，如圖2所示。從圖2可以看出，在DK算法的既定搜索規則下，最優路徑同時從起點和終點開始進行搜索。從起點開始的搜索目標點是終點，這一搜索是正向搜索。從終點開始的搜索目標點是起點，這一搜索是反向搜索。同時進行正反向搜索，不僅提高了搜索效率，也可以在最優路徑之后提供更多的次優路徑被選，在多車輛集體救援時，可以根據優先級將最優路徑、次優路徑分別配置給各個車輛。

第二，對大場景的復雜區域，執行分區域搜索，其策略如圖3所示。

圖3中，外部的矩形框表示了整個的大場景復雜區域，其內部又被分割成4個小的區域，每個區域都有一些白色的圓點，這些圓點代表了分區域內的關鍵點，即救援路徑必須經過的點。因為救援區域的場景大并且內部情況復雜，直接從起點到終點或者直接從終點到起點的路徑搜索都會比較困難。為此，提出的分區域搜索策略，是將原始區域進行區域分割，形成一個個更小的區域。在每個小區域內，根據關鍵點必須經過的原則，在關鍵點之間執行路徑搜索。在每個小區域內的局部路徑確定后，再使各個區域之間的路徑連接，從而形成完整的最優救援路徑。

圖3 大場景復雜區域的分區域搜索策略

通過以上兩種改進措施，可以有效地解決DK算法的局限性，提升其靈活性、改善其全局最優的搜索性能。

3 石化企業火災救援路徑優化仿真試驗

為了驗證該文方法對石化企業火災救援的有效性，接下來以仿真試驗的形式對DK算法的救援路徑優化性能進行驗證性試驗。

試驗過程中，仿真試驗所有的計算機配置情況如下：計算機的CPU為雙核多線程處理器，單核主頻為3.0GHz，計算機的內存大小為16GB，計算機的硬盤大小為500GB。仿真試驗所使用的軟件環境為MapX平臺，這一平臺專門為路徑優化算法的驗證試驗提供試驗環境。

首先，執行該文改進的DK算法，在石化企業復雜場景的模擬火情場地下進行救援路徑搜索試驗，分別得到最優救援路徑和兩個次優救援路徑，救援路徑規劃的試驗結果如圖4所示。

在圖4中，石化企業的整個火災火場模擬區域設定為400個柵格大小，x方向上配置了20個柵格長度，y方向上配置了20個柵格長度。在這個400個柵格大小的火場區域上，救援車輛的起點位于x方向上位置為1、y方向上位置為20的柵格處，救援車輛的終點位于x方向上位置為18、y方向上位置為1的柵格處。從視覺效果上，救援車輛的起點位于場景中的左上方，終點位于右下方。同時，火場區域內有多個形狀各異的障礙物干擾，障礙物所在位置設定為背景為叉剖面線的柵格區域，這些模擬障礙物在實際中可能對應著石化企業的廠房、儲罐、原材料堆放區域等。

圖4 應用該文提出的改進DK算法進行的石化企業火災救援路徑規劃仿真試驗結果

圖4中，DK算法一共搜索到1條最優路徑，如圖中的黑色粗實線所示。同時，DK算法還搜索到2條次優路徑，如圖中的黑色粗虛線和黑色粗點線所示。三條路徑都存在相互的重疊區域，全部以黑色粗實線覆蓋。從DK算法的規劃結果可以看出，最優次優路徑都有效地避開了障礙物，并從起點順利到達目標終點。

為了將該文采用的改進DK算法與傳統 DK 算法進行對比，將另一組試驗結果展示為表格形式，見表1。

表1 該文改進DK算法和傳統DK算法的性能對比

表1中分別說明了石化企業14組火災救援的模擬任務，對傳統DK算法和改進DK算法分別比較了路徑規劃時間和規劃出的路徑長度。從兩項參數的對比結果可以明顯看出，該文提出的改進DK算法，完成路徑規劃的時間更少，并且規劃的最優路徑更短。該結果說明了該文提出的改進DK算法對火災救援的有效性，可以應用于石化企業的火災救援工作。

4 結論

該文針對石化企業火災救援難度大的問題，提出一種基于改進DK算法的救援路徑規劃方法。首先，介紹了傳統DK算法的實現原理和操作流程。其次，分析了傳統DK算法的局限性，提出了正方向搜獲和分區域搜索的改進策略，提升了DK算法的靈活性和全局尋優性能。最后，在Mapx仿真環境下，針對石化企業火災救援場景進行模擬，并分別采用傳統DK算法和改進DK算法進行最優路徑規劃的對比試驗。試驗結果表明：該文提出的改進DK算法得到的最優路徑更短，完成路徑規劃的時間更少，適合石化企業的火災救援。