基于時(shí)空網(wǎng)絡(luò)模型的滅火救援路徑優(yōu)化方法

管 寧

（青島市嶗山區(qū)消防救援大隊(duì)，山東 青島 266000）

目前，對(duì)生產(chǎn)生活威脅最大的仍然是火災(zāi)。對(duì)城市來(lái)說(shuō)，無(wú)論是生產(chǎn)企業(yè)還是大型住宅小區(qū)，因?yàn)樵O(shè)備和人員密集，一旦發(fā)生火災(zāi)，就可能導(dǎo)致不可估量的生命和財(cái)產(chǎn)損失。因此，一旦發(fā)生火情，快速及時(shí)地進(jìn)行救援工作勢(shì)在必行[1]。在滅火救援工作中，救援隊(duì)伍反應(yīng)的實(shí)時(shí)性、滅火救援所配置的裝備都直接關(guān)系到救援工作的效率。其中，對(duì)滅火救援成敗影響最關(guān)鍵的還有救援路徑的設(shè)計(jì)和選擇，這直接影響滅火救援工作的進(jìn)度和準(zhǔn)確性[2]。無(wú)論是生產(chǎn)企業(yè)還是大型住宅小區(qū)，因?yàn)樵O(shè)備配置和建筑結(jié)構(gòu)具有復(fù)雜性，并且火情爆發(fā)后形成各種未知性和復(fù)雜性，所以滅火救援路徑出現(xiàn)選擇障礙[3]。采用合理的算法對(duì)滅火救援路徑進(jìn)行設(shè)計(jì)和規(guī)劃，對(duì)滅火救援工作的順利開(kāi)展具有十分重要的意義。該文采用時(shí)空網(wǎng)絡(luò)模型構(gòu)建滅火救援路徑的優(yōu)化方法，以期在滅火救援工作中找到更好的切入點(diǎn)。

1 滅火救援路徑優(yōu)化的時(shí)空網(wǎng)絡(luò)模型構(gòu)建

以一個(gè)大型園區(qū)為例，一旦發(fā)生火災(zāi)，會(huì)出現(xiàn)一個(gè)或多個(gè)火情點(diǎn)。將滅火救援所需的人員、設(shè)備和物資運(yùn)送到這些火情點(diǎn)，是滅火救援路徑設(shè)計(jì)和優(yōu)化工作的核心任務(wù)。但是，因?yàn)閳@區(qū)內(nèi)各種障礙的存在、火情帶來(lái)的未知性和復(fù)雜性，使滅火救援的人員、設(shè)備和物資配送，成為有約束條件限制下的有限空間內(nèi)的優(yōu)化問(wèn)題。這樣，滅火救援路徑的設(shè)計(jì)和優(yōu)化就成為有限時(shí)間和有限空間內(nèi)的優(yōu)化，所以采用時(shí)空網(wǎng)絡(luò)模型是非常有針對(duì)性的。

時(shí)空網(wǎng)絡(luò)模型是同時(shí)考慮時(shí)間約束條件和空間約束條件，將優(yōu)化問(wèn)題看作一個(gè)同時(shí)包括時(shí)間維度和空間維度的二維網(wǎng)絡(luò)優(yōu)化模型，再充分考慮其他約束條件完成優(yōu)化過(guò)程得到最佳的解決方案。

對(duì)該文的滅火救援工作來(lái)說(shuō)，就是要在最短的時(shí)間內(nèi)以最短路徑完成滅火救援所需的人員、設(shè)備、物資的配送，因此構(gòu)建時(shí)空網(wǎng)絡(luò)模型如公式（1）所示。

式中：R為所有可能的滅火救援路徑上的點(diǎn)的集合；ri為滅火救援路徑上第i個(gè)點(diǎn)；rj為滅火救援路徑上第j個(gè)點(diǎn)；T為滅火救援所有時(shí)間點(diǎn)的集合；ti為救援時(shí)間點(diǎn)集合中第i個(gè)時(shí)間點(diǎn)；tj為救援時(shí)間點(diǎn)集合中第j個(gè)時(shí)間點(diǎn)；Trirjki為滅火救援車(chē)輛在從i點(diǎn)到j(luò)點(diǎn)完成行駛所需要的時(shí)間；tw為新的決策時(shí)間點(diǎn)。

在公式（1）所示的時(shí)空網(wǎng)絡(luò)模型中，涉及2 個(gè)決策變量，第一個(gè)決策變量如公式（2）所示。

在公式（1）所示的時(shí)空網(wǎng)絡(luò)模型中，第二個(gè)決策變量如公式（3）所示。

至此，構(gòu)建了在最短時(shí)間內(nèi)以最短路徑完成滅火救援的時(shí)空網(wǎng)絡(luò)模型。

2 滅火救援路徑優(yōu)化模型的求解

構(gòu)建滅火救援路徑的時(shí)空網(wǎng)絡(luò)優(yōu)化模型后，如何對(duì)模型求解關(guān)系到路徑優(yōu)化的效率和效果。因?yàn)樯婕岸嗉s束、多目標(biāo)優(yōu)化，時(shí)空網(wǎng)絡(luò)模型采用一般方法進(jìn)行求解很難達(dá)到預(yù)期效果，所以該文采取基于遺傳算法的求解策略。

遺傳算法本身是從生物學(xué)領(lǐng)域借鑒過(guò)來(lái)的一種智能優(yōu)化算法，在隨機(jī)巡游的過(guò)程中遵循生物種群基因序列進(jìn)化的各項(xiàng)操作，并且?guī)в幸欢ǖ脑獑l(fā)特點(diǎn)，對(duì)該文的滅火救援路徑優(yōu)化求解具有很好的適應(yīng)性。在遺傳算法的優(yōu)化過(guò)程中，更優(yōu)的路徑方案被保留下來(lái)，一直到最優(yōu)的路徑方案生成。任何可能的救援路徑方案將成為時(shí)空網(wǎng)絡(luò)模型的初始解，也就是遺傳算法的初始種群，進(jìn)而按照遺傳算法的交叉、變異、選擇等操作處理，得到進(jìn)化后的最優(yōu)解，相應(yīng)的處理流程如圖1 所示。

圖1 遺傳算法求解滅火救援路徑時(shí)空網(wǎng)絡(luò)模型的流程

從圖1 中可以看出，采用遺傳算法完成滅火救援路徑時(shí)空網(wǎng)絡(luò)模型求解的流程：第一步，根據(jù)滅火救援路徑優(yōu)化的實(shí)際問(wèn)題，構(gòu)建時(shí)空網(wǎng)絡(luò)優(yōu)化模型，形成對(duì)實(shí)際問(wèn)題的抽象化和數(shù)學(xué)建模。第二步，根據(jù)各種約束條件、各優(yōu)化目標(biāo)進(jìn)行染色體編碼設(shè)計(jì)，形成從實(shí)際問(wèn)題到遺傳算法的對(duì)應(yīng)。第三步，根據(jù)火災(zāi)現(xiàn)場(chǎng)的實(shí)際火情情況，根據(jù)時(shí)空網(wǎng)絡(luò)模型中可能的各種救援路徑方案，隨機(jī)生成救援路徑的初始解，即滅火救援路徑的初始方案。第四步，根據(jù)滅火救援路徑形成的初始種群，進(jìn)行遺傳算法的適應(yīng)度計(jì)算，如果適應(yīng)度計(jì)算的結(jié)果滿足遺傳算法的終止條件，則將當(dāng)前的滅火救援路徑方案輸出，從而解決了對(duì)應(yīng)的實(shí)際問(wèn)題，算法結(jié)束。第五步，如果適應(yīng)度函數(shù)的計(jì)算結(jié)果沒(méi)有滿足遺傳算法的終止條件，則按照遺傳算法的選擇、交叉、變異三項(xiàng)操作進(jìn)行種群進(jìn)化，生成下一代種群，再次重復(fù)第四步的操作。如果第四步一直不能滿足算法終止條件，則反復(fù)執(zhí)行第五步、第四步，直到算法終止條件得到滿足。

為了便于說(shuō)明遺傳算法的操作處理過(guò)程，這里給出一個(gè)具體的實(shí)例。

假設(shè)火災(zāi)救援現(xiàn)場(chǎng)有2 個(gè)救援中心，那么這2 個(gè)救援中心，分別用1、2 兩個(gè)數(shù)字進(jìn)行表示。同時(shí)，現(xiàn)場(chǎng)發(fā)現(xiàn)了15個(gè)火情點(diǎn)都需要救援，延續(xù)救援中心的編碼排列，那么從3～17 這樣15 個(gè)數(shù)字分別表示15 個(gè)火情點(diǎn)。按照遺傳算法的第三步，隨機(jī)生成一個(gè)救援路徑的初始解，如圖2 所示。

圖2 實(shí)例中的初始救援路徑方案

在圖2 中，初始救援路徑方案形成了10-9-8-12-4-14-6-13-7-16-11-15-17-5-3 的救援順序。假設(shè)火災(zāi)救援過(guò)程中共投入了一、二、三、四一共4 組救援力量，那么根據(jù)時(shí)空網(wǎng)絡(luò)模型以及遺傳算法的處理，得到的救援方案如下。第一組救援力量：救援中心1-火情點(diǎn)10-火情點(diǎn)9-火情點(diǎn)8-救援中心1。第二組救援力量：救援中心2-火情點(diǎn)12-火情點(diǎn)4-火情點(diǎn)14-火情點(diǎn)6-救援中心2。第三組救援力量：救援中心1-火情點(diǎn)13-火情點(diǎn)7-火情點(diǎn)16-火情點(diǎn)11-火情點(diǎn)15-救援中心1。第四組救援力量：救援中心2-火情點(diǎn)17-火情點(diǎn)5-火情點(diǎn)3-救援中心2。

可見(jiàn)，救援中心1 負(fù)責(zé)第一組救援力量和第三組救援力量的輸送，并為這兩組救援力量配置了合理的優(yōu)化路徑。救援中心2 負(fù)責(zé)第二組救援力量和第四組救援力量的輸送，并為這兩組救援力量配置了合理的優(yōu)化路徑。

3 滅火救援路徑優(yōu)化測(cè)試試驗(yàn)

為了驗(yàn)證該文提出的滅火救援路徑時(shí)空網(wǎng)絡(luò)模型及遺傳算法求解方案的正確性和有效性，進(jìn)一步展開(kāi)滅火救援路徑優(yōu)化的測(cè)試研究。仍然按照前文實(shí)例的配置原則，設(shè)定2個(gè)救援中心、15 個(gè)火情點(diǎn)，并按照1，2，3，……，17 的方式排列。根據(jù)時(shí)空網(wǎng)絡(luò)優(yōu)化模型的配置原則，首先要給15個(gè)火情點(diǎn)X、Y兩個(gè)決策變量配置需求量表，見(jiàn)表1。

表1 15 個(gè)火情點(diǎn)決策變量的需求量表

在表1 中，給出了各個(gè)火情點(diǎn)的需求，其中T表示所需的救援水量的需求。在這樣的需求下，按照該文構(gòu)建的遺傳算法進(jìn)行求解，得到的救援路徑配置方案如圖3 所示。

圖3 測(cè)試試驗(yàn)中得到的滅火救援路徑配置方案

對(duì)應(yīng)于圖3 的救援路徑配置方案，各救援車(chē)輛的路徑以及需求配置見(jiàn)表2。

表2 各救援車(chē)輛的路徑及需求配置滿足情況

綜合圖3 和表2 的結(jié)果，可以看出：從救援中心1 出發(fā)的消防車(chē)一共有3 輛，其中：消防車(chē)1 的滅火救援路徑是火情點(diǎn)9-火情點(diǎn)5-火情點(diǎn)15-火情點(diǎn)17，可以滿足4 個(gè)火情點(diǎn)的19t 水量需求；消防車(chē)2 的滅火救援路徑是火情點(diǎn)13-火情點(diǎn)12-火情點(diǎn)14，可以滿足3 個(gè)火情點(diǎn)的16.5t 水量需求；消防車(chē)3 的滅火救援路徑是火情點(diǎn)16，可以滿足1個(gè)火情點(diǎn)的5.5t 水量需求。

從救援中心2 出發(fā)的消防車(chē)一共有2 輛，其中：消防車(chē)1 的滅火救援路徑是火情點(diǎn)8-火情點(diǎn)7-火情點(diǎn)10，可以滿足3 個(gè)火情點(diǎn)的16.5t 水量需求；消防車(chē)2 的滅火救援路徑是火情點(diǎn)6-火情點(diǎn)13-火情點(diǎn)11-火情點(diǎn)4，可以滿足4 個(gè)火情點(diǎn)的19t 水量需求。

按照類(lèi)似的方法，設(shè)定10 組仿真案例，其救援路徑的優(yōu)化效果見(jiàn)表3。

表3 10 組仿真案例的救援路徑優(yōu)化結(jié)果

為了便于表3 中優(yōu)化結(jié)果的直觀展示，將其繪制成柱狀圖，如圖4 所示。

圖4 表3 中結(jié)果的柱狀圖顯示

圖4 中，橫坐標(biāo)為仿真案例的組序，縱坐標(biāo)為救援路徑的長(zhǎng)度，單位是公里。從圖中的結(jié)果可以看出，經(jīng)過(guò)該文方法提出的優(yōu)化模型獲得的救援路徑優(yōu)化結(jié)果，10 組案例的路徑長(zhǎng)度都有明顯縮短，從而提升了救援效率。

4 結(jié)論

火災(zāi)仍然是生產(chǎn)生活的重要威脅，如果處理不當(dāng)或救援不及時(shí)將導(dǎo)致重大的生命和財(cái)產(chǎn)損失。該文中以滅火救援路徑優(yōu)化方法為核心研究?jī)?nèi)容，首先從救援時(shí)間和救援距離2 個(gè)約束出發(fā)，構(gòu)建了滅火救援路徑的時(shí)空網(wǎng)絡(luò)模型。針對(duì)時(shí)空網(wǎng)絡(luò)模型，進(jìn)一步提出基于遺傳算法的滅火救援路徑優(yōu)化方案，在給出具體的求解流程以后進(jìn)一步給出了一個(gè)實(shí)例，闡述遺傳算法求解過(guò)程中的編碼設(shè)計(jì)、初始種群生成、對(duì)應(yīng)滅火救援實(shí)際問(wèn)題的求解過(guò)程。在滅火救援路徑優(yōu)化的測(cè)試試驗(yàn)中，配置了2 個(gè)救援中心和15 個(gè)火情點(diǎn)，在構(gòu)建時(shí)空網(wǎng)絡(luò)模型后采用遺傳算法進(jìn)行路徑優(yōu)化和求解，2 個(gè)救援中心分別派出了3 輛消防車(chē)和2 輛消防車(chē)，不僅得到了各個(gè)火情點(diǎn)的合理救援路徑，也能滿足各個(gè)火情點(diǎn)的救援水量需求。