消防出警路線選擇算法的研究

瞿詩(shī)高 (長(zhǎng)江大學(xué)工程技術(shù)學(xué)院,湖北荊州434020)

我國(guó)每年有大量的火災(zāi)發(fā)生,對(duì)人民生命財(cái)產(chǎn)安全造成了嚴(yán)重的威脅。如果能夠提高消防戰(zhàn)士的出警速度,減少消防官兵到達(dá)火災(zāi)現(xiàn)場(chǎng)所需要的時(shí)間,將會(huì)極大地減少火災(zāi)帶來(lái)的損害。我國(guó)現(xiàn)有的消防系統(tǒng)在出警道路的選擇上采用人工方式,即由調(diào)度人員根據(jù)火警現(xiàn)場(chǎng)、道路等情況為出警戰(zhàn)士選擇和指示出警道路。當(dāng)可選道路較多、人流等復(fù)雜情況下,調(diào)度人員就無(wú)法確保選出最優(yōu)出警路線。為此,筆者基于遺傳算法研究了一種消防出警道路選擇算法,利用該算法可選擇最佳消防出警路線,從而保證消防戰(zhàn)士利用最短出警時(shí)間到達(dá)火警現(xiàn)場(chǎng)。

1 數(shù)學(xué)模型

1.1 主要定義

使用有向圖G(V,E)表示當(dāng)前的道路交通圖(見(jiàn)圖1)。其中,V={v0,v1,…,vn},是道路的拐點(diǎn)的集合,v0是消防隊(duì)的位置;E為道路的集合,其元素eij用于描述從道路節(jié)點(diǎn)vi到vj的道路,該元素使用三元組(lij,wij,dij)進(jìn)行描述,其中l(wèi)ij表示道路的長(zhǎng)度,wij表示道路的寬度,dij表示道路當(dāng)前的人流密度。

Psd表示從節(jié)點(diǎn)vs到節(jié)點(diǎn)vd之間的通路表達(dá)式:

圖1 有向圖G(V,E)

1.2 相關(guān)計(jì)算

消防車(chē)通過(guò)道路eij的時(shí)間為tij,即:

式中,v表示當(dāng)前消防車(chē)的行駛速度,m/s。

消防車(chē)通過(guò)通路Psd的時(shí)間Ts d為消防車(chē)通過(guò)道路eij的時(shí)間之和:

通路Ps d的長(zhǎng)度L(Psd)表示該通路上所有道路的長(zhǎng)度之和:

1.3 優(yōu)化目標(biāo)的設(shè)定

由于消防出警的目標(biāo)是以最快的速度到達(dá)火警現(xiàn)場(chǎng),因此,將消防出警道路選擇問(wèn)題描述為:已知道路交通情況,包括每條道路的寬度、長(zhǎng)度、人流密度等的情況下,將車(chē)輛出警時(shí)間最小化,同時(shí)將出警通路長(zhǎng)度最小化,即在有向圖上尋找2個(gè)目標(biāo)節(jié)點(diǎn)之間的一條可行路徑 (見(jiàn)圖2)。

圖2 節(jié)點(diǎn)1-節(jié)點(diǎn)5之間的一條可行路徑

2 消防出警路線選擇算法

路徑選擇算法是NP難問(wèn)題[1],當(dāng)消防出警路線較多時(shí),可選擇遺傳算法[2]求解。下面對(duì)該算法進(jìn)行具體描述。

2.1 解的編碼

采用數(shù)值編碼方式,遺傳算法中的每個(gè)染色體對(duì)應(yīng)一個(gè)解,染色體的長(zhǎng)度等于n(n代表道路交通路中的節(jié)點(diǎn)數(shù)量);基因值為0,表示對(duì)應(yīng)的道路拐點(diǎn)在通路上,否則不在。由此,染色體是以1開(kāi)頭的一組基因。種群中的染色體是隨機(jī)生成的,種群規(guī)模為P。染色體中的基因組可能無(wú)法構(gòu)成一條通路,否則為不合法染色體,應(yīng)由新生成的染色體替換。

2.2 適應(yīng)度函數(shù)設(shè)計(jì)

將Tsd和L(Psd)的加權(quán)和作為算法的適應(yīng)度函數(shù):

式中,s是問(wèn)題的解;α和β代表權(quán)重系數(shù),α+β=1,由于減少時(shí)間是最重要的優(yōu)化目標(biāo),因而α需要占更大比例。

2.3 遺傳算子及算法中止條件

1)遺傳算子 遺傳算子分為如下3種:①交叉算子。在交叉操作中采用單點(diǎn)平行交叉策略,隨機(jī)選擇某個(gè)基因位執(zhí)行交叉。②變異算子。在變異操作中也采用單點(diǎn)變異策略,根據(jù)交叉概率用隨機(jī)生成的新數(shù)值替換隨機(jī)選取的基因位al的值。為保證新的染色體合法,新基因位的取值范圍要滿足解的編碼規(guī)范。在進(jìn)化過(guò)程中,每代的最優(yōu)染色體不參與變異操作。③選擇算子。選擇操作中應(yīng)用精英保留策略,即最優(yōu)染色體直接進(jìn)入下一代種群中,其余染色體通過(guò)賭輪法進(jìn)行選擇[3]。

2)終止條件 使用最大不進(jìn)化代數(shù)作為算法終止條件,若安全閥中的精英染色體經(jīng)過(guò)最大進(jìn)化次數(shù)后仍沒(méi)有更新,即種群沒(méi)有進(jìn)化,則算法結(jié)束。

2.4 算法流程

使用遺傳算法的基本步驟如下:①根據(jù)結(jié)點(diǎn)編碼和種群規(guī)模P,隨機(jī)生成P個(gè)染色體,作為初種群。②根據(jù)式 (5)計(jì)算每個(gè)染色體的適應(yīng)度函數(shù)值即適應(yīng)值。③根據(jù)交叉和變異算子對(duì)種群執(zhí)行交叉和變異操作,則種群中規(guī)模會(huì)增加。④根據(jù)選擇算子執(zhí)行選擇操作,使新種群的規(guī)模恢復(fù)到P。⑤根據(jù)終止條件,判斷是否滿足終止條件,如果不滿足終止條件,則轉(zhuǎn)步驟②。⑥算法結(jié)束。

3 仿真試驗(yàn)

大連市局部道路交通圖如圖3所示。筆者根據(jù)該交通圖進(jìn)行仿真試驗(yàn)。種群規(guī)模取20,消防站的位置和起火點(diǎn)從節(jié)點(diǎn)中隨機(jī)選擇,試驗(yàn)數(shù)據(jù)為算法運(yùn)行500次所得結(jié)果的平均值。試驗(yàn)結(jié)果如表1所示。

從表1可以看出,隨著最大不進(jìn)化代數(shù)的增加,算法的解與最優(yōu)解適應(yīng)度比值也隨之增加,說(shuō)明解的搜索空間增大,算法的解在逐步優(yōu)化。仿真試驗(yàn)表明,利用該算法可以選擇最優(yōu)消防出警路線,從而保證消防戰(zhàn)士在最短時(shí)間內(nèi)到達(dá)火警現(xiàn)場(chǎng)。

表1 算法解與最優(yōu)解的比較

圖3 大連市局部道路交通圖

4 結(jié) 語(yǔ)

為解決消防戰(zhàn)士出警道路選擇的問(wèn)題,研究了基于遺傳算法的出警道路選擇算法。仿真試驗(yàn)表明,筆者提出的算法是可行的,并且可以獲得與最優(yōu)解較為接近的近優(yōu)解,從而解決目前國(guó)內(nèi)消防出警依靠人工調(diào)度的問(wèn)題。

[1]王宇,許都.多約束路由的簡(jiǎn)單求解方法 [J].計(jì)算機(jī)應(yīng)用研究,2007,24(11):268-277.

[2]劉立平,牛熠.遺傳算法綜述 [J].東莞理工學(xué)院學(xué)報(bào),2005,12(3):68-72.

[3]吉根林.遺傳算法研究綜述 [J].計(jì)算機(jī)應(yīng)用與軟件,2004,21(2):69-73.