基于DK算法的石化企業(yè)滅火救援路徑優(yōu)化技術(shù)

張建軍

（青島消防救援支隊(duì)，山東 青島 266000）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 DK算法的局限性

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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