權衡預測時間和偏離度的消防車輛救援調度算法

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

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

0 引 言

伴隨著我國社會經濟發展，城市火災的發生往往造成較大的經濟損失和人員傷亡。在火災發生后，消防中心接到報警信息，并根據國家出警標準進行消防車輛和其人員的調度派遣。而在車輛調度過程中，往往依靠人工經驗進行調度，且不考慮道路的擁堵程度，車輛行駛時間較高且調度效率較低[1-2]，因此迫切需要一種消防車輛救援調度算法。

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

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

1 數學模型

1.1 問題提出

研究消防車輛在應急火災場景中的快速調度優化方法，解決的問題可描述為：一個城市有若干個消防中心，每個消防中心有多輛消防車輛，一輛消防車輛同一個時刻只可負責一個受災目標的救援任務。當發生報警時，消防車輛根據調度預測時間最小和公平性原則進行調度分配。

1.2 假設前提

(1) 一個城市已知有若干個消防中心，并根據報警信息和國家出警標準，獲知當前受災區域位置和需要的消防車輛數。

(2) 消防中心出發時，消防車輛中存在救援的消防人員，從而實現消防人員的調度。

(3) 車輛移動路徑只考慮出發達到目標火災現場時的距離長度，不計算救援總任務完成后的返回距離。

1.3 模型建立

一個城市有若干個消防中心，一個消防中心有若干輛消防車輛。當發生火災時，首先根據道路的相關擁擠情況將消防中心中的消防車輛分配給火災救援點，以盡可能地滿足受災需求以及救援的高效率，其次針對多個火災點引入救援時間偏離度，盡可能保證其救援公平性，從而實現火災救援的高效率與救援公平的平衡。但是算法仍需要解決以下二個問題：一是如何建立權衡預測時間和偏離度的消防車輛救援調度模型；二是如何求解上述模型，從而獲得最優方案，從而降低車輛到達災區時間和離規定救援時間的偏離度。具體模型建立如圖1所示。

圖1 消防車輛調度示意圖

由于消防中心的消防車輛數量固定，因此消防中心擁有消防車輛數量約束為：

根據式(4)計算所得的行程時間比值，通過對比同一路段的相鄰兩個時間段車輛通行速度預測路段是否處于擁堵減輕或加重，獲得當前路段路況權重。

當城市中出現多起或重大火災等突發事件時，困于消防力量的有限性，不能在規定救援時間內滿足所有受災區域的消防調度需求，則考慮讓所有受災區域的消防車輛分配盡可能公平，即到每一個受災點的車輛救援調度時間距離規定的救援車輛抵達時間的偏離程度盡可能小，則：

式中：ω表示救援時間偏離度；ωv表示車輛v的調度預測時間的偏離值；tv表示車輛v的調度預測時間；V表示受災區域所需要的消防車輛數量；μ表示規定消防車輛到達受災區域的最大救援時間，通常為5～8分鐘。

則建立權衡車輛調度預測時間和偏離度的優化模型為：

minaT/Tyu+βω/ωyu

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

a+β=1

(8)

式中：a表示車輛調度預測時間因子；Tyu表示車輛調度預測時間閾值；β表示偏離度因子；ωyu表示偏離度閾值。

2 模型求解

由于多火災點的消防車輛調度問題是NP-Hard問題，目前國內外學者通常采用人工智能算法進行求解。而遺傳算法相較于粒子群算法，蟻群算法和模擬退火具有較高的魯棒性和較強的搜索能力等特性，更適合求解較為復雜的調度優化問題，因此采用遺傳算法求解消防車輛救援調度模型，具體求解過程如下。

2.1 消防車輛的調度模型求解

當遺傳算法被應用到調度問題中，一個有效的調度序列被稱作染色體，每個染色體都有自己的適應度值。遺傳算法以迭代的方式運行，每次迭代代表了種群的一代。每一代種群染色體包括上一代的幸存者和新的經過交叉、變異和選擇后而新產生的比較優秀的染色體。不同的染色體是否被選擇是由它們的適應度值來決定的，適應度越值大，被選中的概率越大。重復這種選擇機制，直至滿足給定條件為止。

2.2 染色體編碼設計

改進遺傳算法采用自然數編碼，在消防調度中，擬設定一個城市有j個消防中心，有V個消防車輛以及k個受災區域，編寫長度為V的染色體編碼。如圖2所示，第一行代表已被調度消防車輛編號，第二行代表消防車輛所出發的消防中心點，第三行代表受災區域。例如第一列(1，1，2)代表1號消防中心派遣車輛編號為1的消防車輛前往2號受災區域。依次循環類推，形成對每一輛消防車輛的調度指示。

圖2 編碼結構

2.3 種群初始化

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

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

2.4 染色體適應度評價

算法目標函數是最小化消防車輛調度預測時間和救援時間偏離度，則令染色體的適應度函數為：

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

(9)

其中，適應度函數值越大，則該調度方案越優，反之越差。

2.5 選擇操作

遍歷計算父代種群中所有染色體的適應度值，將適應度最優的染色體直接存入下一代新種群。隨后從父代種群中隨機選擇2個染色體進行兩兩比對，選擇適應度較優的染色體，直至下一代新種群染色體數量與父代種群染色體數量一致。

2.6 交叉操作

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

步驟1在[0,1]范圍內產生一個隨機浮點數，若其值小于預先設定的交叉概率，則進行交叉操作，從下一代新種群中隨機選擇一對染色體，跳到步驟2。反之，不進行交叉操作，退出。

步驟2產生兩個小于染色體長度的隨機正整數r1和r2，作為兩染色體交叉段的基因起止位置。對基因起止位置中，第一行和第二行的基因數據進行交換，第三行保持不變，并獲得根據兩個染色體的交換基因位置，建立一一映射關系。

步驟3檢查交叉后兩個染色體中是否存在重復的消防車輛調度編號。如果存在重復的數字編號，則選擇交叉段外的重復基因，根據已獲得的基因映射關系，替換成對應映射基因，若替換后仍存在重復沖突，則繼續尋找和替換成當前基因對應的映射基因，直到染色體中不存在重復基因。

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

圖3 染色體交叉

圖4 重復項消除

2.7 變異操作

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

步驟1在[0,1]范圍內產生一個隨機浮點數，若其值小于預先設定的變異概率，則對該染色體進行變異操作，并獲知當前迭代次數，跳到步驟2。反之，則不進行變異操作。

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

步驟3重復執行K-1次操作：隨機指定兩個基因位置，交換其基因碼。退出，結束變異操作。

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

3 算法實現

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

步驟2經百度地圖開源平臺獲取車速、道路擁堵等參數，更新RCW值，計算各個消防中心預計抵達災區所需時間，并根據對各個消防中心車輛進行三維度實數編碼。

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

步驟4以車輛調度預測時間和救援時間偏離度最小作為染色體適應度，通過式(9)計算每個車輛調度染色體的適應度值，更新最優車輛調度染色體。

圖5 算法模型求解流程

步驟5將當前車輛調度最優的染色體放入下一代種群，隨后重復執行Mc-1次以下操作，直至下一代種群與當前種群規模大小一致：隨機選擇兩個染色體，選擇其中適應度較好的染色體放入當前選擇種群。

步驟6令當前操作序號i=0，從當前選擇種群中選擇染色體ic，隨機生成[0,1]范圍內的一個浮點數f。如果f

步驟7隨機生成[0,1]范圍內的一個浮點數f。當f

步驟8i=i+1；如果i≤Mc，跳到步驟7，否則rc=rc+1，如果rc≤Rc，跳到步驟5，否則獲得所有車輛的調度方案，即派往每一個受災區域的車輛數量和到達所有受災區域的時間。

4 算法仿真分析

4.1 仿真參數

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

其次，實驗生成如表1所示的10種受災場景，其受災區域個數不同，受災車輛需求數不同，受災區域位置在杭州百度地圖中隨機生成。例受災場景編號4中受災車輛需求數為[9,7,52]，其數組長度3代表受災區域總個數，數組中其值對應各個受災區域的車輛需求數，如第一個受災區域需要9輛消防車輛，第二個受災區需要7輛消防車輛，第二個受災區需要52輛消防車輛。

表1 受災區需求表

4.2 算法參數和效果分析

為驗證RSA在火災仿真場景下的性能，令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表示變異概率。現選擇4.1節中其他仿真參數和表1內的10類受災場景，并20次循環計算每一個RSA的收斂代數和最優適應度值，取其平均值作為仿真結果值。如表2和圖6所示，4種不同參數情況下的RSA均能求解得到一致的最優適應度值，但其收斂能力存在一定差異，相較于其他3類RSA，RSA-1算法最早完成收斂的迭代次數最小，其收斂速率最快。因此RSA選擇Pc=0.95和Pm=0.08。

表2 不同參數下RSA適應度比較

續表2

圖6 不同參數下RSA的最早完成收斂迭代次數對比圖

現選擇4.1節中仿真參數和表1內的編號1受災場景，獲得RSA的收斂圖。如圖7所示，RSA在第35次迭代收斂到最優適應度值，是收斂的。

圖7 受災場景1的RSA收斂圖

在云端軟件上采用Java語言和其開發軟件Myeclipse軟件，調用RSA，實現百度地圖調度、消防車輛路徑顯示等功能，從而實現消防車輛調度平臺。其消防車輛實際移動路徑如圖8所示。當發生受災場景1時，當時由杭州艮山、湖濱、景芳共派遣9輛消防車輛進行救援，但等到第一輛車到達現場時，已經過了15 min，不符合規定消防車輛到達受災區域的救援時間要求。而基于RSA進行調度，由艮山、湖濱、景芳消防中隊最早抵達十五家園社區的車輛調度預測時間分別只需要7 min、17 min、12 min，較好實現消防車輛的救援調度。

圖8 車輛調度地圖

4.3 算法性能比較

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

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

圖9 車輛平均調度預測時間對比圖

比較RSA、SA、PSO和TNPR算法的救援時間偏離度。如圖9和表3所示，受災場景1-7對消防車輛的需求較少，其周圍消防中心均能滿足實際受災需求，RSA其平均調度時間均小于20 min，且RSA的救援時間偏離度略小于SA、PSO和TNPR算法的救援時間偏離度。受災場景8-10對消防車輛的需求較多，消防車輛較難在規定救援時間內到達所有受災點，導致偏離度大大增加。但是由于RSA考慮消防調度公平性，將車輛調度預測時間距離規定救援時間的偏離度加入到適應度函數，并能尋找到權衡預測時間和偏離度的最優解，因此RSA的救援時間偏離度小于SA、PSO和TNPR算法的救援時間偏離度。

表3 救援時間偏離度對比表

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

圖10 算法運行時間比較圖

5 結 語

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

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