張建軍

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

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

1 基于DK算法的路徑規(guī)劃

石化企業(yè)的火災(zāi)救援路線的最佳選擇，最重要的指標(biāo)之一就是可以使救援總路徑最短，從而提升救援效率。而DK算法就是一種最有針對性的最短路徑搜索算法。DK算法的基本原理是，按照決策樹的理論構(gòu)建搜索救援的路徑樹，路徑樹的根節(jié)點(diǎn)應(yīng)該滿足到達(dá)其他節(jié)點(diǎn)的路徑之和最短。

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

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

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

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

式中：參數(shù)（vk，vi）為節(jié)點(diǎn)vk到節(jié)點(diǎn)vi的弧的長度，參數(shù)c（vk，vi）則為節(jié)點(diǎn)vk到節(jié)點(diǎn)vi的弧上的權(quán)重大小。

根據(jù)有向圖理論的最小權(quán)重值路徑搜索策略如下。

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

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

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

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

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

第四，不斷執(zhí)行第二步和第三步，當(dāng)k（v）=true是搜索過程結(jié)束，此時找到的路徑即為優(yōu)化后的最短路徑。

2 DK算法的改進(jìn)策略

2.1 DK算法的局限性

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

2.2 DK算法的改進(jìn)

為了解決DK算法的局限性問題，也為了更好地解決石化企業(yè)的火災(zāi)救援問題，該文在DK算法的常規(guī)執(zhí)行框架下，提出兩點(diǎn)改進(jìn)策略。

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

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

圖2 同時進(jìn)行正向和反向搜索的改進(jìn)策略

圖1和圖2中，方框區(qū)域代表了石化企業(yè)火災(zāi)現(xiàn)場救援區(qū)域，白色圓點(diǎn)代表了救援路徑搜索的起點(diǎn)，黑色圓點(diǎn)代表了救援路徑搜索的終點(diǎn)，黑色實線代表了搜索路徑和可能的搜索方向。

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

第二，對大場景的復(fù)雜區(qū)域，執(zhí)行分區(qū)域搜索，其策略如圖3所示。

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

圖3 大場景復(fù)雜區(qū)域的分區(qū)域搜索策略

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

3 石化企業(yè)火災(zāi)救援路徑優(yōu)化仿真試驗

為了驗證該文方法對石化企業(yè)火災(zāi)救援的有效性，接下來以仿真試驗的形式對DK算法的救援路徑優(yōu)化性能進(jìn)行驗證性試驗。

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

首先，執(zhí)行該文改進(jìn)的DK算法，在石化企業(yè)復(fù)雜場景的模擬火情場地下進(jìn)行救援路徑搜索試驗，分別得到最優(yōu)救援路徑和兩個次優(yōu)救援路徑，救援路徑規(guī)劃的試驗結(jié)果如圖4所示。

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

圖4 應(yīng)用該文提出的改進(jìn)DK算法進(jìn)行的石化企業(yè)火災(zāi)救援路徑規(guī)劃仿真試驗結(jié)果

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

為了將該文采用的改進(jìn)DK算法與傳統(tǒng) DK 算法進(jìn)行對比，將另一組試驗結(jié)果展示為表格形式，見表1。

表1 該文改進(jìn)DK算法和傳統(tǒng)DK算法的性能對比

表1中分別說明了石化企業(yè)14組火災(zāi)救援的模擬任務(wù)，對傳統(tǒng)DK算法和改進(jìn)DK算法分別比較了路徑規(guī)劃時間和規(guī)劃出的路徑長度。從兩項參數(shù)的對比結(jié)果可以明顯看出，該文提出的改進(jìn)DK算法，完成路徑規(guī)劃的時間更少，并且規(guī)劃的最優(yōu)路徑更短。該結(jié)果說明了該文提出的改進(jìn)DK算法對火災(zāi)救援的有效性，可以應(yīng)用于石化企業(yè)的火災(zāi)救援工作。

4 結(jié)論

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