面向多受災區域與受限應急中心的雙層耦合動態應急調度任務分配模型

段在鵬,俞思雅,黃月鈴*,陽富強

(1.福州大學經濟與管理學院,福建 福州 350108;2.福建省應急管理研究中心,福建 福州 350108;3.福州大學環境與安全工程學院,福建 福州 350108)

近年來,頻發的事故災害給現代社會系統提出了巨大的挑戰[1],高效的應急救援是減少人員傷亡和財產損失的重要措施。Kemball-Cook等[2]于1984年首次提出應急物資調度的概念,之后應急物資調度優化問題已成為國內外學術界研究的熱點問題。不同于一般的物資調度,災后物資調度具有強時效性和弱經濟性等特點[3],并且災害初期,公眾對物資調度的時效性和物資分配的合理性較為敏感,快速、高效地調配應急救援物資對應急資源調度尤為重要。基于此,多數的研究主要集中在應急物資調度模型的優化設計方面[4-5]。如:Yao等[6]為了優化傳統車輛的調度,將路徑不可靠性最小和車輛總體調度時間最少作為目標,構建了多目標應急車輛調度優化模型;Bodaghi等[7]以最小化調度完成時間和救援響應時間為目標,構建了雙目標混合整數規劃模型;Zhang等[8]通過引入分配公平性和需求緊迫度,構建了應急資源調度模型,旨在使物資短缺的損失最小化;王付宇等[9]考慮災害初期資源稀缺性、運輸路徑破壞隨機性、救援公平性等要素,建立了應急調度總成本最低及災民滿意度最大的多目標應急資源調度優化模型。除了以時間、成本最小或者需求滿足率最大為研究目標外,也有學者認為在應急救援過程中應關注災民的心理因素。如:王治瑩等[10]考慮輿情傳播中群眾的風險感知能力,構建了以能力擴充為特色的0-1混合整數非線性模糊規劃調度模型;宋英華等[11]通過設置最小化災民痛苦心理效應目標,進而構建了應急資源分配-路徑選擇決策模型;王熹徽等[12]利用數值評定量表構造痛苦函數,估算了災民的痛苦感知成本,并將該痛苦函數引入應急避難所選址-物資分配優化模型中。隨著計算機技術的廣泛應用,多種智能算法被開發出來,并成功應用于應急救援調度研究中。如:黃彩霞等[13]設計并改進了飛蛾撲火算法用于求解多目標應急資源調度模型;劉姝昱等[14]構建了多供應點-多需求點的應急食品供應優化調配模型,并借助Gurobi求解器編程對模型進行了求解;唐紅亮等[15]為了實現多目標的并行協同優化,構建了多目標非線性離散混合整數規劃地震應急物資調度模型,并利用自適應多目標粒子群優化算法對模型進行了啟發式求解;Niu等[16]利用0-1的編碼方式,設計出多目標遺傳算法,用來求解受災地區應急資源調度的最優方案;胡華等[17]針對地鐵運營中斷下公交橋接運輸車輛應急調度問題中“運輸需求遠超單輛公交車輛運能”的特征,將動態系統仿真方法整合到帶特定變異算子的改進遺傳算法中用于求解模型;劉長石等[18]結合受災群眾非理性的攀比心理,構建了應急物資分配和運輸雙層模型,兼顧了公平和效率的應急物資調度和分配,并根據模型特點設計一種混合遺傳算法求解模型。

災害發生時,存在多個受災區域、多個救援能力有限的出救點,但是學者們的研究往往較少考慮到救援能力受限和復雜應急救援調度的問題,而針對應急調度模型的目標多為最小化應急調度救援的時間,多將應急調度研究放置于靜態應急救援情景中,認為應急物資的調度和分配是一次性完成的,沒有考慮到受災點的應急需求具有隨機性、不確定性,且綜合考慮動態和多層規劃的模型較少,仍存在進一步研究的必要。此外,研究多從應急物資角度出發,沒有考慮其他要素,但在實際救援中,應急救援并非單純的物資派發,需求點往往涉及通訊維護、道路搶修、醫療救援等多類需求。基于此,本文將救援隊伍作為特殊的應急救援資源,構建面向多受災區域與受限應急中心的復雜雙層耦合動態應急調度任務分配模型,并應用遺傳算法對模型進行求解。

1多受災區域與應急中心的雙層耦合動態應急調度任務分配模型

1.1 模型的提出

應急救援效果會隨著救援時間的延長而逐漸下降,“十四五國家應急體系規劃”明確指出,救援中心應按照“就近調配”原則開展應急救援。在實際應急救援中,應急中心不僅要考慮時效性,更應該考慮調度的合理性,多數研究為避免資源浪費常以成本最小化進行應急資源分配,但由于災情的隨機性,災點的應急需求情況會因為災情的變化而不確定,而考慮經濟性的應急救援任務分配方案往往會造成災區救援力量不足[19]。因此,在災害初期就要求應急中心不僅要滿足災點需求,更要調配具有較強救援能力的隊伍前往災區救援。

基于此,在應急救援過程中,救援距離、救援隊伍數量以及救援隊伍的救援能力均會影響應急救援效果。此外,為了合理分配應急救援任務,應急中心派遣的救援力量與受災區域所需的救援力量應盡量滿足供需平衡。因此,應急調度問題中任務分配方案優劣的評判標準主要有以下幾點:

1) 應急中心距離受災區域越近越好[20-21],應急中心距離受災區域越近,受災區域的人員得到救助的時間越早,受到二次傷害的風險越低。

2) 應急中心一次性派出的救援隊伍應盡可能滿足受災區域的救援需求[22-23]。為了避免救援力量的分散,單位時間派出較多的救援隊伍將有利于救援管理,并減少救援隊伍在路上的損耗,提高應急救援效率。

3) 救援隊伍的救援能力越強越好[24]。救援隊伍的救援能力越強,救援隊伍的救援效果越好,受災區域得到的救援就越好。

4) 應急中心的救援任務負荷不能大于其救援力量儲備[11-12]。若救援任務負荷大于應急中心救援力量儲備,應急中心無法滿足救援任務的需求,應急救援效果無法達到預期的目標。

由于災害的突發性,應急中心的救援力量儲備是有限度的,一旦派出的救援力量超過限度便無法提供持續救援,本文稱為受限應急中心。本文構建多受災區域與應急中心的雙層耦合動態應急調度任務分配模型的優化目標是:在現有的應急中心中選出最優的應急中心,并在此基礎上根據評判標準進行應急調度任務分配。

1.2 模型的構建

設共有n個應急中心,記應急中心集合為C={Ci|1≤i≤n},Ci為第i個應急中心,第i個應急中心其救援隊伍儲備為tCi,其中救援隊伍儲備tCi綜合配備了救援人員、救援裝備和交通車輛等應急資源[25]。應急中心C所轄救援隊伍災情處理能力為capture,capture具體表現為搜救能力、急救能力、護理能力、協助能力[26],應急中心基本救援能力為Ui,其中用capture與救援中心至災點的距離distance來衡量應急中心的基本救援能力Ui,Ui隨著各應急中心處理救援任務經驗的變化而變化。

雙層耦合動態應急調度任務分配模型的上層模型可描述為:根據應急中心的基本救援能力Ui,從n個應急中心中選出最適合救援m個受災區域的s個參與應急救援的救援隊伍;設受災區域共有m個,將任務集合記為θ={θj|1≤j≤m},θj為第j個受災區域,即第j項任務,第j個受災區域θj所需的救援隊伍總數為tθj,即第j項任務所需的救援隊伍總數。

雙層耦合動態應急調度任務分配模型的下層模型可抽象描述為:設有m個任務需要分配給s個應急中心完成。

表1 應急中心的基本救援能力表

表2 應急中心的應急調度任務分配表

上層模型為

(1)

式中:f(a)為最優應急中心選擇適應度函數;s為被選中參與應急救援的救援隊伍數量;Ui為應急中心基本救援能力;ε為救援隊伍供需懲罰系數;f(b)為應急調度任務分配適應度函數,如式(2)所示。

下層模型為

(2)

式中:uij為應急中心救援能力系數;α為應急中心儲備量懲罰系數;β為應急中心隊伍派遣量懲罰系數。

在上述雙層耦合模型的基礎上,針對不同階段受災區域的災情變化程度,引入時間變量,建立雙層耦合動態模型。在不同時刻下根據災情的動態變化對應急調度最優任務分配方案進行調整,即在已經計算出的應急調度最優任務分配方案的基礎上,對救援隊伍進行調整。通過雙層耦合動態模型計算出的結果為T=0時刻受災區域的應急調度最優分配方案,但隨著災害發生后時間的變化,受災區域所需的救援力量會發生變化。此時,救援隊伍的救援能力增加經驗系數ω,即:若受災區域θj對救援力量的需求增加,優先從參與受災區域救援的應急中心中調配救援隊伍。根據受災區域發生的變化,對應急救援方案做出調整。

以上雙層耦合動態模型中,上層模型是選擇適合進行應急救援工作的最佳應急中心,下層模型是在已選定的最佳應急中心的基礎上對各應急中心的救援隊伍進行任務派遣分配。上層模型是最終優化目標,下層模型的目的是應急調度任務分配,而上層模型的結果直接決定了下層模型的任務分配情況,同時下層模型在上層給出最佳應急救援方案的基礎上做出最優的任務分配方案,再反饋給上層模型,從而對上層模型的目標進一步優化。最終的應急調度任務分配結果是上下層模型相互耦合計算的結果。

1.3 模型的展開

模型參數設置會影響最終結果,以下著重對模型中的關鍵參數進一步建模展開研究。

1)應急中心基本救援能力Ui。假定受災區域有m個,表示有m項任務,記distanceij為第i個應急中心Ci與第j項任務(受災區域θj)的距離,captureij為應急中心Ci所轄救援隊伍執行第j項任務θj的處理能力,從低到高分為1～4個等級,一般地認為距離distanceij越小越好,處理能力captureij越大越好。Uij表示第i個應急中心執行第j項任務的基本救援能力;Ui表示第i個應急中心執行m個救援任務的基本救援能力,可表示為

(3)

2) 救援隊伍供需懲罰系數ε。救援隊伍供需懲罰系數可表示為

(4)

3) 應急中心救援能力系數u。記tij為第i個應急中心Ci對第j項任務(受災區域θj)需派遣的救援隊伍數量。除了距離distanceij和處理能力captureij外,應急中心一次性派遣的救援隊伍數量也能表達救援能力的大小,避免資源的分散,節約運輸成本。因此,第i個應急中心執行第j項任務的應急中心救援能力系數uij可表示為

(5)

4) 應急中心儲備量懲罰系數α。應急中心儲備量懲罰系數α可表示為

(6)

5) 應急中心救援隊伍派遣量懲罰系數β。應急中心救援隊伍派遣量懲罰系數β可表示為

(7)

2 基于遺傳算法的模型求解

上層遺傳算法針對應急中心選擇,在滿足應急中心受限的情況下,考慮應急中心儲備量限制及其他約束條件并附帶下層遺傳算法的求解目標,選出最佳的應急中心,進而得到下層模型各救援隊伍的應急調度最優任務安排。遺傳算法[5]的求解步驟主要包括編碼、定義適應度函數、確定遺傳策略 (群體大小、選擇、交叉、變異等)。本文著重對編碼、策略適應度函數、交叉策略、變異策略4個關鍵步驟進行闡述。

2.1 編碼方案與個體表示

1) 上層模型0或1編碼。上層模型的目標是選出最優的應急中心,因此上層遺傳算法采用0-1編碼的方式。如圖1所示,隨機產生一個長度為n的0或1組成的基因序列,1表示該應急中心被選中,0表示該應急中心未被選中。上層模型0或1編碼的基因序列示例如圖2所示。

圖1 長度為n的0或1組成的基因序列Fig.1 Gene sequence consisting of 0 or 1 of length n

圖2 上層模型0或1編碼的基因序列示例Fig.2 Examples of gene sequences encoded by upper model 0 or 1

如圖2所示的基因序列,表示應急中心C2、C3未被選中參與應急救援任務,應急中心C1、C2被選中參與應急救援任務。

2) 下層模型整數編碼。下層模型的目標是在選出的應急中心基礎上進行應急調度任務分配,因救援隊伍數量為整數,故下層遺傳算法采用整數編碼的方式。如圖3所示,隨機產生一個長度為m×n的整數序列。

圖3 長度為m×n的整數基因序列Fig.3 Integer gene sequences of length m×n

(8)

例如如圖4所示的基因序列,表示有3個受災區域θ1、θ2、θ3,以及根據圖2選出的2個應急中心C1、C4,未被選中的應急中心對受災區域派遣的救援隊伍數量均為0。應急中心C1派遣5支救援隊伍,C4派遣1支救援隊伍參與救援第一項任務(受災區域θ1);應急中心C1派遣5支救援隊伍,應急中心C4派遣2支救援隊伍參與救援第二項任務(受災區域θ2);同理,可理解任務θ3。

圖4 下層模型整數編碼基因序列示例Fig.4 Example of integer coding gene sequence of the lower model

2.2 適應度函數定義

由于適應度函數與群體中的個體優劣相聯系,故本文將雙層耦合動態應急調度任務分配模型如式(1)、(2)所示,分別選取上層模型和下層模型的適應度函數。下層遺傳算法將目標函數值(即應急中心對應的救援隊伍分配方案)反饋到上層,上層遺傳算法輸出目標函數值在上下層遺傳算法的不斷反饋中達到優化,最后基于上下層模型的適應度函數結果,采用輪盤賭策略選擇個體。

上層模型的適應度函數為

(9)

下層模型的適應度函數為

(10)

該雙層動態應急調度任務分配模型的算法框架,如圖5所示。

圖5 雙層動態應急調度任務分配模型的算法框架圖Fig.5 Algorithm framework diagram of two-layer dynamic emergency scheduling task allocation model

2.3 交叉策略確定

雙親交叉能避免局部收斂,單親交叉能加快收斂效率,因此雙層耦合動態應急調度任務分配模型結合兩種交叉方式:在上層模型中,本文選用雙親交叉的單點交叉策略;在下層模型中,本文設計新的單親交叉策略。

1) 上層模型的雙親單點交叉策略。在遺傳算法中產生新個體的基本操作是染色體的交叉(也稱基因重組)。雙親單點交叉策略能避免產生的結果只是局部最優解。上層模型的雙親交叉策略示例,如圖6所示。

圖6 上層模型的雙親單點交叉示例Fig.6 Parental single point crossover example of the upper layer model

如圖6所示的雙親單點交叉操作表示:兩個父代個體中選中參與救援的應急中心C3與另一個父代中未被選中的參與救援的應急中心C3交叉互換,得到兩個新的個體。

2) 下層模型的單親交叉策略。由于在單親交叉中,母體基因段上的任意若干對基因交換的位置是隨機的,所以為了避免無效個體的大量產生,本文規定只有“同一救援任務下的不同應急中心”的情況可以進行互相交叉。下層模型的單親交叉策略示例,如圖7所示。

圖7 下層模型的單親交叉示例Fig.7 Example of single parent mutation of the lower layer model

如圖7所示的單親交叉操作表示:應急中心C4參與任務θ1的1支救援隊伍與參與任務θ3的6支救援隊伍交叉互換,得到一個新的個體。

2.4 變異策略確定

單親變異操作就是隨機地對母體上的若干基因位進行逆轉而產生新的個體。

1) 上層模型的0或1變異策略。在上層模型中,本文規定0或1編碼的染色體變異方式為基因位隨機由0變為1或者由1變為0,如圖8所示。

圖8 上層模型單親突變示例Fig.8 Example of single parent mutation of the upper layer model

如圖8所示的單親突變操作表示:隨機地,第一個基因位由1變為0,第三個基因位由0變為1,即選中參與救援的應急中心C1,C4變為應急中心,C1參與C4救援。

2) 上層模型的整數變異策略。在下層模型中,本文規定只有被選中參與救援的應急中心的救援隊伍數量可在基因位隨機加減一個整數,如圖9所示。

圖9 下層模型單親突變示例Fig.9 Example of single parent mutation of the lower layer model

如圖9所示的單親突變操作表示:隨機地,應急中心C1參與救援任務θ1的救援隊伍減少1支,應急中心C4參與救援任務θ2的救援隊伍增加1支。

3 實例分析

3.1 問題描述

某次地震災害應急中,受災區域和應急中心的拓撲關系見圖10。其中,圓面積的大小表示受災區域對救援隊伍的需求量;連接線上的數值表示各應急中心到受災區域的距離;連接線的粗細程度表示應急中心對該受災區域救援能力的等級大小,本文分為4級,連接線由粗到細依次為4～1級。

圖10 應急中心與受災區域拓撲關系圖Fig.10 Topological relationship between the rescue center and the disaster area

由圖10可知:受災區域共有3個,記為θ={θj|1≤j≤3},θj為第j個受災區域,該3個受災區域所需的救援隊伍數量依次為7、5、6支。應急中心共有4個,記為C={Ci|1≤i≤4},Ci為第i個應急中心,其救援隊伍儲備均為10支。例如表3中,4/14表示應急中心C1到受災區域θ1的距離為14 km,應急中心C1所轄救援隊伍執行任務θ1的處理能力為4級,詳細數據見表3。災害發生后,不同時刻受災區域的救援隊伍需求見表4。

表3 應急中心詳細數據表

表4 不同時刻受災區域的救援隊伍需求

3.2 模型求解

遺傳算法試驗參數設置如下:上層模型種群大小為100,最大進化迭代數為100,遺傳代溝為0.9,雙親交叉概率為0.9,變異概率為0.1;下層模型種群大小為100,最大進化迭代數為150,單親交叉概率為0.9,變異概率為0.1。

具體求解過程見2.2節。求解出的上層迭代圖見圖11。

圖11 上層模型迭代圖Fig.11 Iterative diagram of the upper layer model

在圖11中,上層模型適應度最大的5個值對應的應急中心選擇方案有3種,為①[0,0,1,1]、②[1,1,0,1]、③[0,1,0,1],分別對應下層救援隊伍數量分配迭代圖,如圖12、圖13、圖14所示。

圖12 下層模型迭代圖①Fig.12 Iterative diagram of the lower layer model①

圖13 下層模型迭代圖②Fig.13 Iterative diagram of the lower layer model②

圖14 下層模型迭代圖③Fig.14 Iterative diagram of the lower layer model③

由圖12、圖13、圖14可以看出,應急中心3種選擇方案對應的下層最大適應度值都在23左右,并且應急中心選擇方案②對應的下層模型迭代圖的收斂效果更穩定,因此應急中心選擇的最優方案為方案②[1,1,0,1],對應的救援隊伍任務分配方案為(0 0 0 7|5 0 0 0|0 6 0 0)。以應急中心C2為例,解讀應急中心派遣的救援隊伍最優分配方案為應急中心C2對θ1、θ2、θ3受災區域分別派出0、0、6支救援隊伍,具體見表5。

表5 不同應急中心派遣的救援隊伍最優分配方案表

3.3 動態情景調度

當災害發生一段時間后,此時在T1時刻,根據表4可知受災區域θ1、θ2、θ3所需的救援隊伍數量分別變為5、6、4支救援隊伍。在已經計算出的最優任務分配方案的基礎上,對救援隊伍進行調整,調整原則遵循:①盡可能從參與救援的應急中心調配救援隊伍;②救援力量過剩時,從救援能力弱的應急中心減少參與救援的救援隊伍數量;③參與救援的救援隊伍盡可能為同一個應急中心。最終利用Matlab軟件計算得出的不同時刻應急中心派遣的救援隊伍最優任務分配方案見表6。以應急中心C1為例,解讀不同時刻應急中心派遣的救援隊伍任務分配方案為:T1時刻,應急中心C1對θ1、θ2、θ3受災區域分別派出4、0、0支救援隊伍。

表6 不同時刻應急中心派遣的救援隊伍最優任務分配方案表

4 結 論

1) 根據救援距離、救援隊伍的救援能力、應急中心受限情況以及受災區域的救援需求,定義5個約束函數,設計出上層應急中心選擇和下層救援隊伍數量分配的雙層耦合模型,并在得到最合適的應急中心的基礎上,對救援隊伍數量進行最優應急調度任務分配,再反饋給上層,實現對上層模型的進一步優化。因此,雙層耦合模型在進行應急調度方案選擇時考慮的因素更全面,得出的方案更合理。

2) 隨著時間的發展,需要對應急調度分配的救援力量和物資進行再調整,避免救援資源的浪費。因此,在雙層耦合模型的基礎上引入時間變量,構造雙層耦合動態模型,根據受災區域對救援力量的需求發生變化,遵循優先從參與受災區域救援的應急中心中調配救援隊伍的原則,對應急調度任務分配方案做出了相應的調整,使得救援調度更加靈活和貼合實際。

3) 根據上層模型和下層模型的特點以及上、下層模型之間的耦合關系,設計0或1編碼和整數編碼方式,并設計單親交叉方式,將單親和雙親交叉綜合運用,兼顧高效性和穩定性,同時還設計了0或1變異和整數變異策略,通過仿真計算,結果表明該雙層耦合動態模型結果合理,符合實際。

4) 從仿真結果來看,在上層模型中,由于上層模型的適應度函數受下層模型適應度函數的影響,最大適應度值對應的應急中心應急調度任務分配方案不唯一,因此還需要利用下層模型做進一步分析,從而確定上層應急中心的應急調度任務分配。相比于單層模型,雙層耦合模型計算速度較慢,但考慮的因素更多,得出的應急救援方案也較合理。另外,考慮時間影響的雙層耦合動態模型比雙層耦合模型更靈活、更貼合實際情況,從而使得救援資源利用率達到更大化。