權(quán)衡預(yù)測(cè)時(shí)間和偏離度的消防車(chē)輛救援調(diào)度算法

陳友榮 盧俊杰 曾江波 孫 萍 諸燕平

1(常州大學(xué)信息科學(xué)與工程學(xué)院 江蘇 常州 213164)2(浙江樹(shù)人大學(xué)信息科技學(xué)院 浙江 杭州 310015)3(臺(tái)州市消防救援支隊(duì)司令部信通科 浙江 臺(tái)州 318000)

0 引 言

伴隨著我國(guó)社會(huì)經(jīng)濟(jì)發(fā)展，城市火災(zāi)的發(fā)生往往造成較大的經(jīng)濟(jì)損失和人員傷亡。在火災(zāi)發(fā)生后，消防中心接到報(bào)警信息，并根據(jù)國(guó)家出警標(biāo)準(zhǔn)進(jìn)行消防車(chē)輛和其人員的調(diào)度派遣。而在車(chē)輛調(diào)度過(guò)程中，往往依靠人工經(jīng)驗(yàn)進(jìn)行調(diào)度，且不考慮道路的擁堵程度，車(chē)輛行駛時(shí)間較高且調(diào)度效率較低[1-2]，因此迫切需要一種消防車(chē)輛救援調(diào)度算法。

目前國(guó)內(nèi)外學(xué)者在調(diào)度優(yōu)化領(lǐng)域已取得一定成果。部分學(xué)者側(cè)重于以救援時(shí)間短，經(jīng)濟(jì)損失小作為模型優(yōu)化目標(biāo)，研究多目標(biāo)調(diào)度分配和調(diào)度優(yōu)化集成問(wèn)題，如：文獻(xiàn)[3]和文獻(xiàn)[4]為解決多發(fā)放點(diǎn)之間潛在的應(yīng)急救援物資調(diào)度沖突問(wèn)題，提出運(yùn)輸時(shí)間最短和成本最小的多目標(biāo)優(yōu)化模型，并采用改進(jìn)蟻群進(jìn)行求解。文獻(xiàn)[5]和文獻(xiàn)[6]針對(duì)應(yīng)急資源分配問(wèn)題，均以人員傷亡、經(jīng)濟(jì)損失和救援開(kāi)支費(fèi)用最小作為約束條件，建立一種在多出救點(diǎn)、多物資和多受災(zāi)點(diǎn)約束條件下的資源分配模型。文獻(xiàn)[7]建立了以搶險(xiǎn)救援工作結(jié)束時(shí)間最早和出救裝備總調(diào)度費(fèi)用最少的雙目標(biāo)優(yōu)化裝備調(diào)度模型，并借助貪婪算法對(duì)該模型進(jìn)行分層序列求解。但是文獻(xiàn)[3-7]未考慮災(zāi)情隨時(shí)間動(dòng)態(tài)變化情況下的調(diào)度問(wèn)題。部分學(xué)者側(cè)重于考慮救援時(shí)間和車(chē)輛行駛距離，研究車(chē)輛的調(diào)度算法[8]，如：文獻(xiàn)[9]考慮避難點(diǎn)分配、路徑規(guī)劃和不確定通行能力等約束，建立不確定信息環(huán)境下救援優(yōu)化模型，并提出基于逆向搜索最短路徑和正向反推安全路徑的求解方法。文獻(xiàn)[10]提出基于風(fēng)險(xiǎn)并結(jié)合消防服務(wù)覆蓋模型，采用進(jìn)化算法解決消防定位和快速救援服務(wù)的問(wèn)題。但是文獻(xiàn)[9-10]沒(méi)有以最小救援時(shí)間作為主要優(yōu)化目標(biāo)。同時(shí)部分學(xué)者側(cè)重于研究消防人員調(diào)度問(wèn)題，如：文獻(xiàn)[11]針對(duì)并發(fā)火災(zāi)的消防力量調(diào)派，以并發(fā)火災(zāi)總體滅火救援效果最優(yōu)為目標(biāo)，應(yīng)用線性規(guī)劃理論建立消防力量供大于求時(shí)的優(yōu)化部署模型，給出了消防力量供求關(guān)系不平衡時(shí)的優(yōu)化部署方案。文獻(xiàn)[12]引入了一種基于數(shù)學(xué)規(guī)劃的滾動(dòng)水平啟發(fā)式算法，對(duì)不同位置設(shè)立不同權(quán)重來(lái)求解分配調(diào)度問(wèn)題。但是文獻(xiàn)[11-12]只是考慮消防車(chē)輛到達(dá)時(shí)間，沒(méi)有考慮多消防車(chē)輛出警時(shí)的離規(guī)定救援時(shí)間的偏離度。

綜上所述，目前國(guó)內(nèi)外學(xué)者較少關(guān)注消防領(lǐng)域急需解決的問(wèn)題——消防救援調(diào)度優(yōu)化問(wèn)題，已取的研究成果較少，可借鑒的算法較少，由此可見(jiàn)，應(yīng)對(duì)火災(zāi)的消防救援調(diào)度優(yōu)化問(wèn)題仍有待解決。因此提出一種權(quán)衡預(yù)測(cè)時(shí)間和偏離度的消防車(chē)輛救援調(diào)度算法(Rescue scheduling algorithm of firefighting vehicle weighing forecast time and deviation degree，RSA)，即根據(jù)接警信息，確定火災(zāi)的受災(zāi)區(qū)域和其需要的車(chē)輛數(shù)，提出受災(zāi)區(qū)域所需消防車(chē)輛數(shù)量約束和消防中心擁有消防車(chē)輛數(shù)量約束，并根據(jù)路段期望通行時(shí)間計(jì)算當(dāng)前路段路況權(quán)重。計(jì)算消防車(chē)輛到達(dá)各個(gè)受災(zāi)區(qū)域的平均調(diào)度預(yù)測(cè)時(shí)間及其離規(guī)定救援時(shí)間的偏離度，建立權(quán)衡預(yù)測(cè)時(shí)間和偏離度的消防車(chē)輛救援調(diào)度算法。采用修正的遺傳算法求解該消防車(chē)輛救援調(diào)度模型，獲得消防車(chē)輛的最優(yōu)路線，通過(guò)精英保留策略在每一輪迭代中保留最優(yōu)解，提高算法的收斂性，使用映射交叉操作保證調(diào)度錯(cuò)解盡可能地減少，在變異的不同階段使用不同變異策略提高局部的搜索能力。修正的遺傳算法能適應(yīng)不同的受災(zāi)救援場(chǎng)景，獲得消防車(chē)輛的最優(yōu)調(diào)度方案，從而降低消防車(chē)輛的行駛時(shí)間，降低調(diào)度預(yù)測(cè)時(shí)間離規(guī)定最大救援時(shí)間的偏離度，實(shí)現(xiàn)救援調(diào)度的高效率和公平性。

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

1.1 問(wèn)題提出

研究消防車(chē)輛在應(yīng)急火災(zāi)場(chǎng)景中的快速調(diào)度優(yōu)化方法，解決的問(wèn)題可描述為：一個(gè)城市有若干個(gè)消防中心，每個(gè)消防中心有多輛消防車(chē)輛，一輛消防車(chē)輛同一個(gè)時(shí)刻只可負(fù)責(zé)一個(gè)受災(zāi)目標(biāo)的救援任務(wù)。當(dāng)發(fā)生報(bào)警時(shí)，消防車(chē)輛根據(jù)調(diào)度預(yù)測(cè)時(shí)間最小和公平性原則進(jìn)行調(diào)度分配。

1.2 假設(shè)前提

(1) 一個(gè)城市已知有若干個(gè)消防中心，并根據(jù)報(bào)警信息和國(guó)家出警標(biāo)準(zhǔn)，獲知當(dāng)前受災(zāi)區(qū)域位置和需要的消防車(chē)輛數(shù)。

(2) 消防中心出發(fā)時(shí)，消防車(chē)輛中存在救援的消防人員，從而實(shí)現(xiàn)消防人員的調(diào)度。

(3) 車(chē)輛移動(dòng)路徑只考慮出發(fā)達(dá)到目標(biāo)火災(zāi)現(xiàn)場(chǎng)時(shí)的距離長(zhǎng)度，不計(jì)算救援總?cè)蝿?wù)完成后的返回距離。

1.3 模型建立

一個(gè)城市有若干個(gè)消防中心，一個(gè)消防中心有若干輛消防車(chē)輛。當(dāng)發(fā)生火災(zāi)時(shí)，首先根據(jù)道路的相關(guān)擁擠情況將消防中心中的消防車(chē)輛分配給火災(zāi)救援點(diǎn)，以盡可能地滿足受災(zāi)需求以及救援的高效率，其次針對(duì)多個(gè)火災(zāi)點(diǎn)引入救援時(shí)間偏離度，盡可能保證其救援公平性，從而實(shí)現(xiàn)火災(zāi)救援的高效率與救援公平的平衡。但是算法仍需要解決以下二個(gè)問(wèn)題：一是如何建立權(quán)衡預(yù)測(cè)時(shí)間和偏離度的消防車(chē)輛救援調(diào)度模型；二是如何求解上述模型，從而獲得最優(yōu)方案，從而降低車(chē)輛到達(dá)災(zāi)區(qū)時(shí)間和離規(guī)定救援時(shí)間的偏離度。具體模型建立如圖1所示。

圖1 消防車(chē)輛調(diào)度示意圖

由于消防中心的消防車(chē)輛數(shù)量固定，因此消防中心擁有消防車(chē)輛數(shù)量約束為：

根據(jù)式(4)計(jì)算所得的行程時(shí)間比值，通過(guò)對(duì)比同一路段的相鄰兩個(gè)時(shí)間段車(chē)輛通行速度預(yù)測(cè)路段是否處于擁堵減輕或加重，獲得當(dāng)前路段路況權(quán)重。

當(dāng)城市中出現(xiàn)多起或重大火災(zāi)等突發(fā)事件時(shí)，困于消防力量的有限性，不能在規(guī)定救援時(shí)間內(nèi)滿足所有受災(zāi)區(qū)域的消防調(diào)度需求，則考慮讓所有受災(zāi)區(qū)域的消防車(chē)輛分配盡可能公平，即到每一個(gè)受災(zāi)點(diǎn)的車(chē)輛救援調(diào)度時(shí)間距離規(guī)定的救援車(chē)輛抵達(dá)時(shí)間的偏離程度盡可能小，則：

式中：ω表示救援時(shí)間偏離度；ωv表示車(chē)輛v的調(diào)度預(yù)測(cè)時(shí)間的偏離值；tv表示車(chē)輛v的調(diào)度預(yù)測(cè)時(shí)間；V表示受災(zāi)區(qū)域所需要的消防車(chē)輛數(shù)量；μ表示規(guī)定消防車(chē)輛到達(dá)受災(zāi)區(qū)域的最大救援時(shí)間，通常為5～8分鐘。

則建立權(quán)衡車(chē)輛調(diào)度預(yù)測(cè)時(shí)間和偏離度的優(yōu)化模型為：

minaT/Tyu+βω/ωyu

s.t. 式(1)-式(7)

a+β=1

(8)

式中：a表示車(chē)輛調(diào)度預(yù)測(cè)時(shí)間因子；Tyu表示車(chē)輛調(diào)度預(yù)測(cè)時(shí)間閾值；β表示偏離度因子；ωyu表示偏離度閾值。

2 模型求解

由于多火災(zāi)點(diǎn)的消防車(chē)輛調(diào)度問(wèn)題是NP-Hard問(wèn)題，目前國(guó)內(nèi)外學(xué)者通常采用人工智能算法進(jìn)行求解。而遺傳算法相較于粒子群算法，蟻群算法和模擬退火具有較高的魯棒性和較強(qiáng)的搜索能力等特性，更適合求解較為復(fù)雜的調(diào)度優(yōu)化問(wèn)題，因此采用遺傳算法求解消防車(chē)輛救援調(diào)度模型，具體求解過(guò)程如下。

2.1 消防車(chē)輛的調(diào)度模型求解

當(dāng)遺傳算法被應(yīng)用到調(diào)度問(wèn)題中，一個(gè)有效的調(diào)度序列被稱作染色體，每個(gè)染色體都有自己的適應(yīng)度值。遺傳算法以迭代的方式運(yùn)行，每次迭代代表了種群的一代。每一代種群染色體包括上一代的幸存者和新的經(jīng)過(guò)交叉、變異和選擇后而新產(chǎn)生的比較優(yōu)秀的染色體。不同的染色體是否被選擇是由它們的適應(yīng)度值來(lái)決定的，適應(yīng)度越值大，被選中的概率越大。重復(fù)這種選擇機(jī)制，直至滿足給定條件為止。

2.2 染色體編碼設(shè)計(jì)

改進(jìn)遺傳算法采用自然數(shù)編碼，在消防調(diào)度中，擬設(shè)定一個(gè)城市有j個(gè)消防中心，有V個(gè)消防車(chē)輛以及k個(gè)受災(zāi)區(qū)域，編寫(xiě)長(zhǎng)度為V的染色體編碼。如圖2所示，第一行代表已被調(diào)度消防車(chē)輛編號(hào)，第二行代表消防車(chē)輛所出發(fā)的消防中心點(diǎn)，第三行代表受災(zāi)區(qū)域。例如第一列(1，1，2)代表1號(hào)消防中心派遣車(chē)輛編號(hào)為1的消防車(chē)輛前往2號(hào)受災(zāi)區(qū)域。依次循環(huán)類推，形成對(duì)每一輛消防車(chē)輛的調(diào)度指示。

圖2 編碼結(jié)構(gòu)

2.3 種群初始化

種群的初始化就是依據(jù)編碼規(guī)則給出種群的初始解。通常使用常用的隨機(jī)數(shù)生成器和修正的方法獲得符合約束條件式(1)-式(2)的初始種群，作為有效初始解。初始化染色體的具體程序流程如下：

步驟3如果集合S中元素個(gè)數(shù)小于V，則向集合S中添加0元素，使集合S中元素個(gè)數(shù)等于V。隨后從中隨機(jī)抽取V個(gè)不重復(fù)的元素，將其放置在第三行中。獲得符合約束條件式(1)和式(2)的車(chē)輛編號(hào)不重復(fù)的車(chē)輛調(diào)度序列。

2.4 染色體適應(yīng)度評(píng)價(jià)

算法目標(biāo)函數(shù)是最小化消防車(chē)輛調(diào)度預(yù)測(cè)時(shí)間和救援時(shí)間偏離度，則令染色體的適應(yīng)度函數(shù)為：

FitnessC(i)=1/(aT/Tyu+βvar/vyu)

(9)

其中，適應(yīng)度函數(shù)值越大，則該調(diào)度方案越優(yōu)，反之越差。

2.5 選擇操作

遍歷計(jì)算父代種群中所有染色體的適應(yīng)度值，將適應(yīng)度最優(yōu)的染色體直接存入下一代新種群。隨后從父代種群中隨機(jī)選擇2個(gè)染色體進(jìn)行兩兩比對(duì)，選擇適應(yīng)度較優(yōu)的染色體，直至下一代新種群染色體數(shù)量與父代種群染色體數(shù)量一致。

2.6 交叉操作

算法使用部分映射交叉算子產(chǎn)生下一代染色體。由于染色體的三維構(gòu)造特殊性，在進(jìn)行交叉操作時(shí)需要將消防車(chē)輛與消防中心出發(fā)點(diǎn)進(jìn)行綁定。使用映射交叉方法可以避免染色體出現(xiàn)異常解，保證染色體都滿足約束式(1)-式(2)。隨機(jī)選擇兩個(gè)父代染色體，隨機(jī)選擇基因段的兩處位置，以此為起止位置，交換基因，并根據(jù)映射關(guān)系進(jìn)行修正。具體步驟如下：

步驟1在[0,1]范圍內(nèi)產(chǎn)生一個(gè)隨機(jī)浮點(diǎn)數(shù)，若其值小于預(yù)先設(shè)定的交叉概率，則進(jìn)行交叉操作，從下一代新種群中隨機(jī)選擇一對(duì)染色體，跳到步驟2。反之，不進(jìn)行交叉操作，退出。

步驟2產(chǎn)生兩個(gè)小于染色體長(zhǎng)度的隨機(jī)正整數(shù)r1和r2，作為兩染色體交叉段的基因起止位置。對(duì)基因起止位置中，第一行和第二行的基因數(shù)據(jù)進(jìn)行交換，第三行保持不變，并獲得根據(jù)兩個(gè)染色體的交換基因位置，建立一一映射關(guān)系。

步驟3檢查交叉后兩個(gè)染色體中是否存在重復(fù)的消防車(chē)輛調(diào)度編號(hào)。如果存在重復(fù)的數(shù)字編號(hào)，則選擇交叉段外的重復(fù)基因，根據(jù)已獲得的基因映射關(guān)系，替換成對(duì)應(yīng)映射基因，若替換后仍存在重復(fù)沖突，則繼續(xù)尋找和替換成當(dāng)前基因?qū)?yīng)的映射基因，直到染色體中不存在重復(fù)基因。

具體實(shí)例如圖3-圖4所示，隨機(jī)選擇兩個(gè)整數(shù)1和3，在父代染色體1和父代染色體2中都以此為起止位置，選擇需要的交叉基因段為[2 3 4,1 2 2]和[4 5 2, 3 1 2]，對(duì)其進(jìn)行交叉得到兩個(gè)原始子代，獲得映射關(guān)系1?1，2?4，5?3。交叉后原始子代1中出現(xiàn)數(shù)值為5的重復(fù)沖突，原始子代2中出現(xiàn)3的重復(fù)沖突，選擇交叉段外的重復(fù)基因，根據(jù)已獲得的基因映射關(guān)系，替換成對(duì)應(yīng)映射基因，若替換后仍存在重復(fù)沖突，則繼續(xù)尋找和替換成當(dāng)前基因?qū)?yīng)的映射基因，直到染色體中不存在重復(fù)基因，最終消除沖突獲得子代。

圖3 染色體交叉

圖4 重復(fù)項(xiàng)消除

2.7 變異操作

在基本遺傳算法的基礎(chǔ)上，采用了移位變異操作和非均勻變異兩次變異操作，改善遺傳算法的局部搜索能力，維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象。具體步驟如下：

步驟1在[0,1]范圍內(nèi)產(chǎn)生一個(gè)隨機(jī)浮點(diǎn)數(shù)，若其值小于預(yù)先設(shè)定的變異概率，則對(duì)該染色體進(jìn)行變異操作，并獲知當(dāng)前迭代次數(shù)，跳到步驟2。反之，則不進(jìn)行變異操作。

步驟2如果當(dāng)前迭代次數(shù)不大于20(取經(jīng)驗(yàn)值)，則采用非均勻變異方法，即根據(jù)2.3節(jié)中第三行序列的步驟2和步驟3，重新對(duì)該染色體的第三行序列進(jìn)行初始化，退出，結(jié)束變異操作，否則跳到步驟3。

步驟3重復(fù)執(zhí)行K-1次操作：隨機(jī)指定兩個(gè)基因位置，交換其基因碼。退出，結(jié)束變異操作。

由于染色體在初始化時(shí)即已滿足約束條件式(1)-式(2)，在后續(xù)的選擇、交叉、變異操作中，對(duì)染色體的基因僅在位置上發(fā)生變換，不做數(shù)值的隨機(jī)變換，因此新生成的染色體仍滿足約束條件式(1)-式(2)，不需要對(duì)染色體進(jìn)行修正。

3 算法實(shí)現(xiàn)

如圖5所示，本文模型主要使用遺傳算法進(jìn)行計(jì)算求解，在算法初始階段，獲取模型必要數(shù)據(jù)以及設(shè)置算法初始參數(shù)，其具體步驟如下所示：

步驟2經(jīng)百度地圖開(kāi)源平臺(tái)獲取車(chē)速、道路擁堵等參數(shù)，更新RCW值，計(jì)算各個(gè)消防中心預(yù)計(jì)抵達(dá)災(zāi)區(qū)所需時(shí)間，并根據(jù)對(duì)各個(gè)消防中心車(chē)輛進(jìn)行三維度實(shí)數(shù)編碼。

步驟3初始化Mc個(gè)滿足式(1)-式(2)的車(chē)輛調(diào)度染色體；初始化車(chē)輛調(diào)度種群中染色體個(gè)數(shù)為Mc，車(chē)輛交叉概率為Pc，變異概率為Pm，迭代次數(shù)rc=0，最大迭代次數(shù)為Rc，初始化Mc個(gè)滿足式(1)-式(2)的車(chē)輛調(diào)度染色體。

步驟4以車(chē)輛調(diào)度預(yù)測(cè)時(shí)間和救援時(shí)間偏離度最小作為染色體適應(yīng)度，通過(guò)式(9)計(jì)算每個(gè)車(chē)輛調(diào)度染色體的適應(yīng)度值，更新最優(yōu)車(chē)輛調(diào)度染色體。

圖5 算法模型求解流程

步驟5將當(dāng)前車(chē)輛調(diào)度最優(yōu)的染色體放入下一代種群，隨后重復(fù)執(zhí)行Mc-1次以下操作，直至下一代種群與當(dāng)前種群規(guī)模大小一致：隨機(jī)選擇兩個(gè)染色體，選擇其中適應(yīng)度較好的染色體放入當(dāng)前選擇種群。

步驟6令當(dāng)前操作序號(hào)i=0，從當(dāng)前選擇種群中選擇染色體ic，隨機(jī)生成[0,1]范圍內(nèi)的一個(gè)浮點(diǎn)數(shù)f。如果f

步驟7隨機(jī)生成[0,1]范圍內(nèi)的一個(gè)浮點(diǎn)數(shù)f。當(dāng)f

步驟8i=i+1；如果i≤Mc，跳到步驟7，否則rc=rc+1，如果rc≤Rc，跳到步驟5，否則獲得所有車(chē)輛的調(diào)度方案，即派往每一個(gè)受災(zāi)區(qū)域的車(chē)輛數(shù)量和到達(dá)所有受災(zāi)區(qū)域的時(shí)間。

4 算法仿真分析

4.1 仿真參數(shù)

實(shí)驗(yàn)主要根據(jù)杭州市主城區(qū)的消防中心實(shí)際位置數(shù)據(jù)，采用Python語(yǔ)言和其編譯軟件Pycharm2019進(jìn)行仿真實(shí)驗(yàn)，其中道路中各路段的距離長(zhǎng)度、車(chē)輛行駛速度、深夜通行時(shí)間均可通過(guò)百度地圖開(kāi)源API獲得。在杭州市區(qū)范圍內(nèi)選擇了10個(gè)消防中心作為實(shí)驗(yàn)出發(fā)起點(diǎn)。受災(zāi)場(chǎng)景1為2017年杭州十五家園小區(qū)火災(zāi)，當(dāng)時(shí)出動(dòng)艮山、湖濱、景芳消防中隊(duì)共9輛消防車(chē)輛。受災(zāi)場(chǎng)景2為2020年4月杭州蕭山區(qū)湖頭陳花園發(fā)生火災(zāi)，當(dāng)時(shí)由湘湖、蕭山、濱江共3個(gè)消防站共出動(dòng)7輛消防車(chē)輛。受災(zāi)場(chǎng)景3為2016年杭州艮山西路汽配倉(cāng)庫(kù)的大火災(zāi)，共調(diào)配52輛消防車(chē)輛進(jìn)行救援。受災(zāi)場(chǎng)景4為考慮同時(shí)發(fā)生上述3種實(shí)際場(chǎng)景的情況。后續(xù)受災(zāi)場(chǎng)景為在杭州市范圍內(nèi)隨機(jī)產(chǎn)生多個(gè)受災(zāi)坐標(biāo)點(diǎn)進(jìn)行仿真實(shí)驗(yàn)，其中受災(zāi)場(chǎng)景8-10為受災(zāi)區(qū)域的消防車(chē)輛需求數(shù)較多的實(shí)驗(yàn)場(chǎng)景。在實(shí)驗(yàn)仿真中，各個(gè)消防中心的車(chē)輛數(shù)由浙江消防網(wǎng)所公布的數(shù)據(jù)模擬生成。同時(shí)設(shè)置以下參數(shù)：車(chē)輛調(diào)度模型的種群大小為100，模型的終止迭代次數(shù)均為100，車(chē)輛調(diào)度預(yù)測(cè)時(shí)間因子a為0.3，偏離度因子β為0.7，車(chē)輛調(diào)度預(yù)測(cè)時(shí)間閾值Tyu為69，偏離度閾值ωyu為42，規(guī)定消防車(chē)輛最大救援時(shí)間μ為8。可通過(guò)改變參數(shù)的大小來(lái)影響模型在求解過(guò)程中對(duì)于救援時(shí)間和救援公平的傾向性。

其次，實(shí)驗(yàn)生成如表1所示的10種受災(zāi)場(chǎng)景，其受災(zāi)區(qū)域個(gè)數(shù)不同，受災(zāi)車(chē)輛需求數(shù)不同，受災(zāi)區(qū)域位置在杭州百度地圖中隨機(jī)生成。例受災(zāi)場(chǎng)景編號(hào)4中受災(zāi)車(chē)輛需求數(shù)為[9,7,52]，其數(shù)組長(zhǎng)度3代表受災(zāi)區(qū)域總個(gè)數(shù)，數(shù)組中其值對(duì)應(yīng)各個(gè)受災(zāi)區(qū)域的車(chē)輛需求數(shù)，如第一個(gè)受災(zāi)區(qū)域需要9輛消防車(chē)輛，第二個(gè)受災(zāi)區(qū)需要7輛消防車(chē)輛，第二個(gè)受災(zāi)區(qū)需要52輛消防車(chē)輛。

表1 受災(zāi)區(qū)需求表

4.2 算法參數(shù)和效果分析

為驗(yàn)證RSA在火災(zāi)仿真場(chǎng)景下的性能，令RSA-1代表Pc=0.95，Pm=0.08的RSA，RSA-2代表Pc=0.85，Pm=0.05的RSA，RSA-3代表Pc=0.75，Pm=0.03的RSA，RSA- 4代表Pc=0.99，Pm=0.1的RSA，其中Pc表示交叉概率，Pm表示變異概率?，F(xiàn)選擇4.1節(jié)中其他仿真參數(shù)和表1內(nèi)的10類受災(zāi)場(chǎng)景，并20次循環(huán)計(jì)算每一個(gè)RSA的收斂代數(shù)和最優(yōu)適應(yīng)度值，取其平均值作為仿真結(jié)果值。如表2和圖6所示，4種不同參數(shù)情況下的RSA均能求解得到一致的最優(yōu)適應(yīng)度值，但其收斂能力存在一定差異，相較于其他3類RSA，RSA-1算法最早完成收斂的迭代次數(shù)最小，其收斂速率最快。因此RSA選擇Pc=0.95和Pm=0.08。

表2 不同參數(shù)下RSA適應(yīng)度比較

續(xù)表2

圖6 不同參數(shù)下RSA的最早完成收斂迭代次數(shù)對(duì)比圖

現(xiàn)選擇4.1節(jié)中仿真參數(shù)和表1內(nèi)的編號(hào)1受災(zāi)場(chǎng)景，獲得RSA的收斂圖。如圖7所示，RSA在第35次迭代收斂到最優(yōu)適應(yīng)度值，是收斂的。

圖7 受災(zāi)場(chǎng)景1的RSA收斂圖

在云端軟件上采用Java語(yǔ)言和其開(kāi)發(fā)軟件Myeclipse軟件，調(diào)用RSA，實(shí)現(xiàn)百度地圖調(diào)度、消防車(chē)輛路徑顯示等功能，從而實(shí)現(xiàn)消防車(chē)輛調(diào)度平臺(tái)。其消防車(chē)輛實(shí)際移動(dòng)路徑如圖8所示。當(dāng)發(fā)生受災(zāi)場(chǎng)景1時(shí)，當(dāng)時(shí)由杭州艮山、湖濱、景芳共派遣9輛消防車(chē)輛進(jìn)行救援，但等到第一輛車(chē)到達(dá)現(xiàn)場(chǎng)時(shí)，已經(jīng)過(guò)了15 min，不符合規(guī)定消防車(chē)輛到達(dá)受災(zāi)區(qū)域的救援時(shí)間要求。而基于RSA進(jìn)行調(diào)度，由艮山、湖濱、景芳消防中隊(duì)最早抵達(dá)十五家園社區(qū)的車(chē)輛調(diào)度預(yù)測(cè)時(shí)間分別只需要7 min、17 min、12 min，較好實(shí)現(xiàn)消防車(chē)輛的救援調(diào)度。

圖8 車(chē)輛調(diào)度地圖

4.3 算法性能比較

通過(guò)節(jié)4.2可知，參數(shù)為Pc=0.95，Pm=0.08的情況下，可較快地尋找到算法最優(yōu)解。經(jīng)過(guò)多次實(shí)驗(yàn)發(fā)現(xiàn)慣性因子為0.8，學(xué)習(xí)因子為1.47的粒子群算法計(jì)算的解較優(yōu)，發(fā)現(xiàn)初始溫度Tinit=200，降溫系數(shù)k=0.97，重復(fù)降溫次數(shù)150的模擬退火算法計(jì)算的解較優(yōu)。因此選擇該參數(shù)和4.1節(jié)中其他仿真參數(shù)，循環(huán)20次計(jì)算10個(gè)不同受災(zāi)場(chǎng)景下較優(yōu)參數(shù)下的RSA、SA、PSO和就近優(yōu)先的救援算法(Traditional nearest priority rescue，TNPR)的車(chē)輛平均調(diào)度預(yù)測(cè)時(shí)間和救援時(shí)間偏離度，取其平均值作為仿真結(jié)果值。其中，TNPR算法是傳統(tǒng)救援算法，即根據(jù)救援點(diǎn)位置，選擇調(diào)度所需距離最小的消防中心進(jìn)行救援調(diào)度，直至滿足所有救援點(diǎn)的需求。

首先，比較RSA、SA、PSO和TNPR算法的車(chē)輛平均調(diào)度預(yù)測(cè)時(shí)間。如圖9所示，RSA的車(chē)輛平均調(diào)度預(yù)測(cè)時(shí)間較小，且都小于SA、PSO和TNPR算法的車(chē)輛平均調(diào)度預(yù)測(cè)時(shí)間。這是因?yàn)槿旧w編碼設(shè)計(jì)中使用了三維矩陣，而PSO在處理多維、多峰值的調(diào)度分配問(wèn)題時(shí)容易出現(xiàn)早熟問(wèn)題，從而導(dǎo)致尋優(yōu)效果較差，其適應(yīng)度值較低。SA在重復(fù)迭代計(jì)算過(guò)程中容易出現(xiàn)較差解，從而影響后續(xù)的求解，導(dǎo)致無(wú)法尋找到全局最優(yōu)解。TNPR算法采用比較簡(jiǎn)單的就近原則，即貪心策略，其在較為簡(jiǎn)單的受災(zāi)場(chǎng)景1和2中，其最優(yōu)解質(zhì)量與其他算法相差不大，但在受災(zāi)場(chǎng)景3-10中，需要車(chē)輛數(shù)量或救援點(diǎn)數(shù)量較多，其解質(zhì)量變差。RSA在染色體的編碼設(shè)計(jì)和初始化階段對(duì)隨機(jī)解集進(jìn)行條件約束，并在變異操作中混合兩種變異方法，使得算法具有更好和更穩(wěn)定的尋優(yōu)能力，因此其最優(yōu)適應(yīng)度值最優(yōu)。

圖9 車(chē)輛平均調(diào)度預(yù)測(cè)時(shí)間對(duì)比圖

比較RSA、SA、PSO和TNPR算法的救援時(shí)間偏離度。如圖9和表3所示，受災(zāi)場(chǎng)景1-7對(duì)消防車(chē)輛的需求較少，其周?chē)乐行木軡M足實(shí)際受災(zāi)需求，RSA其平均調(diào)度時(shí)間均小于20 min，且RSA的救援時(shí)間偏離度略小于SA、PSO和TNPR算法的救援時(shí)間偏離度。受災(zāi)場(chǎng)景8-10對(duì)消防車(chē)輛的需求較多，消防車(chē)輛較難在規(guī)定救援時(shí)間內(nèi)到達(dá)所有受災(zāi)點(diǎn)，導(dǎo)致偏離度大大增加。但是由于RSA考慮消防調(diào)度公平性，將車(chē)輛調(diào)度預(yù)測(cè)時(shí)間距離規(guī)定救援時(shí)間的偏離度加入到適應(yīng)度函數(shù)，并能尋找到權(quán)衡預(yù)測(cè)時(shí)間和偏離度的最優(yōu)解，因此RSA的救援時(shí)間偏離度小于SA、PSO和TNPR算法的救援時(shí)間偏離度。

表3 救援時(shí)間偏離度對(duì)比表

由于TRNN算法只是簡(jiǎn)單選擇調(diào)度所需距離最小的消防中心，不含有迭代優(yōu)化的思想策略，僅需對(duì)消防中心和道路距離組合進(jìn)行降序排序，其運(yùn)行所需時(shí)間較小，與SA、PSO和RSA沒(méi)有可比性。因此比較SA、PSO和RSA的運(yùn)行時(shí)間。如圖10所示，SA受降溫系數(shù)影響較大，容易陷入局部最優(yōu)解，短時(shí)間內(nèi)無(wú)法尋找到全局最優(yōu)解，導(dǎo)致其運(yùn)行時(shí)間最長(zhǎng)。PSO在解空間隨機(jī)搜索過(guò)程中產(chǎn)生較多的不滿足預(yù)設(shè)約束的無(wú)效解，而通過(guò)重新初始化的手段往往無(wú)法保證新解的質(zhì)量，從而導(dǎo)致其運(yùn)算時(shí)間較大。RSA在模型中會(huì)產(chǎn)生少量異常解，且通過(guò)染色體修正保證解的質(zhì)量不會(huì)大幅度變差，從而在保證尋找到全局最優(yōu)解的情況下提高了收斂速度，降低了算法迭代次數(shù)，因此RSA的運(yùn)行時(shí)間最短。

圖10 算法運(yùn)行時(shí)間比較圖

5 結(jié) 語(yǔ)

本文提出一種權(quán)衡預(yù)測(cè)時(shí)間和偏離度的消防車(chē)輛救援調(diào)度算法(RSA)。首先，獲得各個(gè)消防中心及受災(zāi)區(qū)位置，需要的車(chē)輛數(shù)等主要信息。其次，根據(jù)百度地圖開(kāi)源平臺(tái)獲得出發(fā)點(diǎn)距離受災(zāi)點(diǎn)的各路段通行時(shí)間，通過(guò)對(duì)比過(guò)往通行時(shí)間重新評(píng)估各路段通行時(shí)間，并建立消防救援調(diào)度優(yōu)化模型。隨后采用修正的遺傳算法求解，即對(duì)染色體進(jìn)行三維實(shí)數(shù)編碼并使其滿足預(yù)先設(shè)定的約束條件，通過(guò)精英選擇、保存歷史最優(yōu)染色體、映射交叉、非均勻變異、移位變異等方法獲得最優(yōu)救援調(diào)度方案。最后基于仿真實(shí)驗(yàn)參數(shù)，比較了在不同火災(zāi)場(chǎng)景下的RSA、PSO、SA和TNPR算法性能。

總之，RSA考慮了多目標(biāo)情景下的消防救援調(diào)度，選擇最優(yōu)參數(shù)下的修正遺傳算法，相比于粒子群算法和模擬退火算法，加快了其收斂速度，并保證其救援方案為最優(yōu)解。而在后續(xù)的研究中將考慮一種計(jì)算復(fù)雜度更低的啟發(fā)式算法，求解救援調(diào)度問(wèn)題。