許德剛，李 凡，王 露，郭奕欣，邢奎杰，梁騰翔

1.河南工業(yè)大學 信息科學與工程學院，鄭州450001

2.中國華能集團有限公司 信息中心，北京100031

近些年，世界范圍性的突發(fā)疫情頻繁爆發(fā)，不僅危害了人類的身體健康，還嚴重影響了國家經(jīng)濟的發(fā)展[1]。從“非典”事件到如今的“新冠肺炎”疫情，每一次傳染病類公共衛(wèi)生事件的突發(fā)，都會造成嚴重的人員傷亡及經(jīng)濟損失，并且因疫情發(fā)生突然，會加劇受災點的醫(yī)療物資消耗，從而導致受災點庫存告急。而在突發(fā)公共衛(wèi)生事件的應對過程中，充足的應急醫(yī)療物資是保護人民生命安全的重要資源，是一線醫(yī)護人員的“鎧甲”“彈藥”，是順利開展應急救援的重要保障。因此，相較于其他類應急物資，醫(yī)療物資是救治病人及防止疫情持續(xù)蔓延的重要物質支撐，也是疫情防控的第一道防線。此次新型冠狀病毒肺炎傳染性強，波及范圍廣，因此防疫物資需求激增，口罩、防疫藥品等物資缺貨嚴重，導致居民防疫能力減弱，感染人數(shù)也不斷增長。為提高醫(yī)療物資的應急救援效率，減少醫(yī)療物資供應不足造成的不良影響，需要對醫(yī)療物資應急調度管理作出進一步的研究與優(yōu)化[2]。

應急醫(yī)療物資在疫情防控中起著決定性的作用，具有不可替代性、時效性、滯后性等特點，是治療患者及緩解疫情蔓延的重要保障，因此對于不可預測的突發(fā)疫情來說，醫(yī)療物資的合理分配和緊急調度是疫情防控的基礎工作[3]。而在此次全球范圍性的新冠肺炎疫情防控中，各個主要疫情國都出現(xiàn)了醫(yī)療物資短缺的情況，反映出目前各個國家的應急醫(yī)療物資調度體系還存在一定缺陷[4]，因此分析及改進目前應急調度管理策略，保障突發(fā)疫情下的醫(yī)療物資及時供給是目前的研究重點。

隨著此次新冠肺炎疫情的爆發(fā)，應急調度作為應急物流研究的分支之一，成為國內外學者廣泛研究的熱點問題[5]。應急調度問題除了包括需求點、供應點、應急物資等幾個基本要素之外，還要有限制車輛載重、資源種類及到達時間等要素的約束條件。與普通物流運輸相比，應急調度主要具有突發(fā)性、不確定性、非常規(guī)性、弱經(jīng)濟性及資源有限性等特點[6]。其目的是在重大疫情突發(fā)后的救援工作中，決策者利用供應點現(xiàn)存的資源及條件，采取有效措施，科學有序地將需求點所需的應急物資快速、準確地送達目的地，從而有效控制疫情的擴大與惡化，最大限度地降低患者的生命損失[7]。

1 國內外文獻綜述

應急調度問題的研究[8]，逐漸從過去的精準算法求解轉向現(xiàn)在的啟發(fā)式算法求解[9]，并且目前大多數(shù)專家和學者不再是利用智能算法的原始規(guī)則進行逐步求解，而是根據(jù)不同算法的優(yōu)缺點進行相關優(yōu)化后再進一步求解。Rivera等[10]建立了兩個混合整數(shù)線性模型，并且開發(fā)了一種基于資源約束的最短路徑公式來解決資源受限的最短路徑問題，實驗結果顯示此方法優(yōu)于商業(yè)MIP解算器，具有較高的效率。Lei等[11]針對人員調度和物資供應問題展開了研究，以總延誤時間最小化為目標定義了一個兩階段供應鏈網(wǎng)絡，對可再生資源和不可再生資源應用了不同的管理策略，并提出了一種基于數(shù)學規(guī)劃的啟發(fā)式算法，利用隨機產生的5 420個測試案例以及一個真實的城市醫(yī)院配送案例進行算法的性能對比分析，經(jīng)過實驗證明，文中所提出的模型和算法可以快速、有效地搜尋到最優(yōu)運輸策略，為快捷、高效地解決應急調度問題提供了理論基礎，具有較強的實用價值及現(xiàn)實意義。Wang等[12]提出了以時間最小化和成本最小化為目標的二維多目標優(yōu)化模型，并采用救援點分解的方法減小模型的維數(shù)，最后利用理想點算法進行求解，通過仿真實驗證明了模型的合理性和算法的有效性。Chakraborty等[13]為有效地處理應急車輛交通問題，提出了一種動態(tài)交通信號控制算法，通過無線傳感網(wǎng)絡技術對交通進行實時監(jiān)測，并判斷行駛車輛是否為緊急車輛，最后在考慮死鎖的情況下利用算法進行求解，仿真實驗顯示平均等待時間為34.492 s，證明了此算法的優(yōu)越性，為今后車輛應急調度問題的研究提供了一種新穎的優(yōu)化方案。Qi等[14]為解決最短資源調度時間前提下?lián)p耗最小化的多目標路徑優(yōu)化問題，將ACS[15]與PLS算法相結合，設計出了一種改進的多目標蟻群算法，在仿真實驗中通過與原始蟻群算法的對比證明了該方法有著獨特的優(yōu)勢，并且在實際應用方面有較強的適應性。Feng等[16]以總運輸距離最小化及成本最小化為目標建立了一個雙目標優(yōu)化模型，并利用可變加權算法將雙目標問題轉化成單目標問題，降低了多目標優(yōu)化問題的復雜性，最后通過實驗證明文中模型和算法的優(yōu)越性及可行性。Laksono等[17]為改善當前醫(yī)療服務水平，提出了利用層次分析法和動態(tài)最短路徑算法來快速、準確地解決救護車緊急調度問題，通過仿真實驗發(fā)現(xiàn)，采用這種算法所需的時間比人工解決調度問題所需的時間大大減少，為醫(yī)療水平的改善提供了理論基礎。Tlili等[18]將緊急醫(yī)療服務中的救護車路徑問題（ARP）建模為OVRP問題和VRPPD問題，并在花瓣算法（PA）[19]和粒子群優(yōu)化算法（PSO）[20]的基礎上，提出了一種新算法，其思路是利用花瓣算法將問題分成多個區(qū)域，再利用粒子群優(yōu)化算法對每個區(qū)域進行求解，最后通過仿真實驗對新算法與其他算法進行性能對比，發(fā)現(xiàn)PA-PSO算法與最優(yōu)解的誤差僅為5.52%，明顯優(yōu)于其他算法，充分證明了新算法的效率更高、精度更準。Ghosh等[21]提出了一種線性約束的精確優(yōu)化模型，并且為了提高可伸縮性，提出了兩種啟發(fā)式算法來解決緊急調度問題，最后通過兩個數(shù)據(jù)集進行仿真實驗，證明了提出的兩種啟發(fā)式算法比其他算法的性能更加優(yōu)越。Issam等[22]為高效解決救護車的緊急調度問題，建立了一種新的車輛路徑數(shù)學模型，并利用K-Means算法對數(shù)據(jù)進行分類，同時分析模擬退火算法[23]與禁忌搜索算法特點，將兩種算法進行結合，最后提出了利用模擬退火-禁忌搜索算法（SA-TS）搜索及優(yōu)化路徑的方案，通過仿真實驗與粒子群優(yōu)化算法和遺傳算法進行對比，充分證明了新算法在性能方面有較大的提升。

本文提出了一種結合遺傳算法和禁忌搜索算法的優(yōu)化煙花算法，以煙花算法為框架，以煙花個體中的數(shù)值大小順序表示求解結果，利用遺傳算法中的交叉變異策略代替?zhèn)鹘y(tǒng)煙花算法中的高斯變異算子，并引入禁忌表的概念，更有效地對模型進行精準求解。

2 醫(yī)療物資應急調度模型

2.1 問題描述

2.1.1 問題提出

在一般的調度問題中，通常優(yōu)先考慮其運輸成本，即以運輸成本最小化為目標展開研究[24]。但是由于應急調度問題具有弱經(jīng)濟性和時間緊迫性的特點，因此在實際應急調度問題中，成本最小化將不再是首要考慮因素，而是要將患者生命安全放在首位，最大限度地對患者進行有效醫(yī)療救助。應急調度的對象通常是需求點緊急缺少的生命救助藥物等時效性較強的物資，而此類物資能否在短時間內抵達需求點是挽救患者生命健康的關鍵因素，因此在滿意度最大化的前提下，運輸所消耗的最短時間才是應急調度最需要考慮的問題[25]。

大規(guī)模突發(fā)性疫情爆發(fā)后，需要大量的消耗類醫(yī)療物資來防止疫情擴散，然而一般情況下受災點日常儲備的醫(yī)療物資有限，僅能在短時間內維持平衡，因此需要迅速籌集各類醫(yī)療物資進行緊急援助，并且要根據(jù)需求情況動態(tài)調整醫(yī)療物資分配，做到精準供給對接，最大限度地降低患者的生命財產損失[26]。為此，需要構建一個多周期的醫(yī)療物資動態(tài)分配模型，根據(jù)疫情的發(fā)展狀況，并結合上一周期的醫(yī)療物資使用情況，實時調整下一周期醫(yī)療物資分配方式。考慮到醫(yī)療物資調度需要花費一定時間，若周期結束后再進行下一周期調度，可能會造成一段時間內物資緊缺，因此可以提前一段時間進行調度，或者設置需求點緊急度閾值，動態(tài)監(jiān)測需求點緊急度，若低于閾值則開始下一周期調度。用ηωjn,min表示第ω周期需求點對醫(yī)療物資n的需求緊急度閾值。用Ω={1,2,…,ω,…}表示醫(yī)療物資應急調度各周期集合，Tω表示第ω個周期所持續(xù)天數(shù)。

由于實際應急調度問題具有突發(fā)性的特點，在大規(guī)模的疫情突發(fā)后，可能會出現(xiàn)應急供應點運輸車輛不足的情況。而此次疫情政府對人員流動做出限制，造成大量運輸工具的閑置，因此可通過在社會范圍內進行車輛臨時征用來緩解車輛不足的情況，但也造成了車輛信息的不確定性，即每輛車的載重、速度可能會略有不同，這將會對車輛路徑規(guī)劃造成較為嚴重的影響。當車輛從應急供應點出發(fā)，會根據(jù)實際情況對各個需求點所需的醫(yī)療物資進行運輸，但各需求點對醫(yī)療物資的需求緊急度略有不同，因此如何合理地規(guī)劃車輛運輸路徑是優(yōu)化應急調度問題的研究重點[27]。用K={k1,k2,…,kn}表示不同種類車輛的集合。

2.1.2 基本假設

為了便于建模及求解，先對模型所需信息進行假設：

（1）假設各需求點的位置是已知的，并且每個需求點僅需要醫(yī)用口罩、防疫藥品兩種消耗類醫(yī)療物品。

（2）假設供應點有幾種不同的相服務車輛，各車輛的載重不同，但速度相同，且車輛勻速行駛。

（3）忽略裝貨卸貨時間的影響，只計算車輛行駛時間。

（4）運輸為閉合回路，即車輛完成運輸任務后需要返回供應點。

（5）假設各需求點與供應點之間直接互通，且忽略天氣、堵車、道路損壞等因素影響。

（6）假設需求點的醫(yī)療物資需求量與此需求點的感染人數(shù)成正比，且感染人數(shù)可以通過傳染病擴散規(guī)律進行預測。

（7）假設患者痊愈后不再受疫情影響

2.2 基于SEIR的應急物資預測模型

應急調度問題具有不確定性的特點，即在大規(guī)模疫情突然爆發(fā)的情況下，疫情的危害程度會隨時間的推移而產生變化，因此在不同時間段內各需求點所需醫(yī)療物資數(shù)量會有所不同[28]。為解決醫(yī)療物資數(shù)量不確定的情況，本文采用SEIR（Susceptible-Exposed-Infected-Removed）模型[29]對感染人數(shù)進行預測，從而間接預測各需求點所需的醫(yī)療物資數(shù)量。如圖1所示，SEIR模型將某一地區(qū)的人群劃分為四類：易感者(S)、暴露者(E)、患病者(I+I1)、康復者(R)。由于新型傳染病初期無具體針對措施，各年齡段人群都無明顯抵抗力，因此各年齡段人群被傳染的概率基本一致。但由于老年人的身體抵抗性較弱，且常常伴隨著較多的慢性疾病，因此當老年人與患者接觸后，其發(fā)病率明顯要高于其他人群，同時治愈率要低于其他人群，因此本模型添加I1變量用來表示60歲以上的老年患病者。

圖1 SEIR模型Fig.1 Schematic diagram of SEIR model

SEIR的動態(tài)模型可用式（1）表示：

其中，S(t)、E(t)、I1(t)、I(t)、R(t)分別表示在t時刻某一患病地區(qū)范圍內易感者、暴露者、老年患病者（60歲以上患病人群）、其他人群患病者及康復者的人數(shù)，λ表示患病者的傳播率（易感染人群被感染進入潛伏期狀態(tài)的概率）、λ1表示處在潛伏期人群的傳播率、β表示某一地區(qū)60歲以上老年人所占比例、σ1表示老年患者的發(fā)病率（暴露者發(fā)病進入患病狀態(tài)的概率）、σ表示其他人群的發(fā)病率、μ1表示老年患者的治愈率（患病者被治愈進入康復狀態(tài)的概率）、μ表示其他人群患者的治愈率。

總人口數(shù)量約束如下：

其中，N表示患病地區(qū)的總人口數(shù)，S、E、I1、I、R分別表示此地區(qū)的易感者、暴露者、老年患病者、其他人群患病者及康復者的人口數(shù)量。

假設各需求點醫(yī)療器械充足，僅缺少醫(yī)用口罩、防疫藥品兩種消耗類醫(yī)療物品，因此可采取如下模型[30]來預測所需要的醫(yī)療物資數(shù)量：

2.3 物資調度優(yōu)化模型

2.3.1 模型符號定義

為了方便描述，對以下符號進行定義：

K為應急供應點車輛的集合；D為需求點集合；a為應急供應點；A表示D?a，需求點與應急供應點的集合；N表示醫(yī)療物資的種類集合為第ω周期開始時需求點j醫(yī)療物資n的儲備量；Ck為車輛k的核定載重為第ω周期需求點j對醫(yī)療物資n的需求緊急度；tij為供應點i到達需求點j的行駛時間；為第ω周期需求點j對醫(yī)療物資n的滿意度；為第ω周期需求點j所需醫(yī)療物資n的總數(shù)量；為第ω周期車輛k在需求點j投放醫(yī)療物資n的數(shù)量；為0-1變量，若在ω周期內車輛k從需求點i（或應急供應點a）出發(fā)，到達需求點j（或應急供應點a）則為1，否則為0；為0-1變量，若在第ω周期內車輛k到達需求點j則為1，否則為0。

2.3.2 模型構建

目標函數(shù)：

目標函數(shù)（5）表示各需求點的滿足率最大化。

目標函數(shù)（6）表示各車輛行駛時間最小化。

約束（7）表示需求緊急度計算公式，在周期ω內需求點儲備量可以滿足需求時，緊急度為0，需求點無儲備量時緊急度最大，為1。

約束（8）表示滿意度計算公式，當供大于求時，滿意度最大值為1。

約束（9）表示車輛運輸?shù)尼t(yī)療物資不超過最大載重。

約束（10）表示車輛k為需求點j所投放的醫(yī)療物資n的數(shù)量不得超過需求點j所需要的醫(yī)療物資n的總量。

約束（11）表示每一需求點的醫(yī)療物資運輸僅由一輛車輛負責，避免出現(xiàn)因車輛多次訪問同一需求點而造成資源浪費的情況。

約束（12）和約束（13）表示車輛k到達需求點j后，仍從需求點j出發(fā)。

約束（14）表示從應急供應點出發(fā)的車輛數(shù)目等于回到應急供應點的車輛數(shù)目，且整個運輸過程中實際使用的車輛數(shù)目不得超過應急供應點可用的車輛數(shù)目。

約束（15）和約束（16）表示變量取值約束。

2.3.3 問題轉化

討論求解的醫(yī)療物資應急調度問題的是多目標優(yōu)化問題，即要求需求點滿意度(F1)最大、車輛行駛時間(F2)最短。為便于求解，本文采用理想點法將多目標優(yōu)化問題轉化為單目標優(yōu)化問題，并采用加權歐幾里德距離來求最優(yōu)解。根據(jù)理想點法的原理，要先找出正、負理想點，即目標函數(shù)的最優(yōu)值、最劣值。

首先將最大化目標函數(shù)轉化為最小化，如式（17）所示：

3 算法設計

3.1 煙花算法介紹

3.1.1 煙花算法原理

煙花算法是Tan等[31]受煙花爆炸的啟發(fā)，所提出的一種新穎智能優(yōu)化算法，其基本原理是將每個煙花都看作解空間中的一個可行解，利用爆炸操作對原始煙花進行鄰域搜索，并通過直接或間接的信息傳遞促使煙花的適應性逐漸提高，從而求出全局最優(yōu)解或最優(yōu)近似解。煙花算法步驟主要包括火花爆炸操作、火花變異操作及選擇策略，其中火花爆炸的半徑及數(shù)量會根據(jù)煙花適應度值動態(tài)變化，適應性較差的煙花爆炸半徑更大，但生成的火花數(shù)量較少；適應性較好的煙花爆炸半徑更小，但生成的火花數(shù)量較多。簡而言之，煙花算法會在火花較差位置進行大范圍少量搜索，較好位置進行小范圍大量搜索，因此煙花算法可以利用煙花適應度值來平衡全局搜索和局部搜索之間的關系，保證更快速地求出最優(yōu)解。此外，變異火花可以避免算法陷入局部最優(yōu)，提高算法的搜索效率，保證種群的多樣性[32]。目前煙花算法已被證實是一種高效的智能算法，并廣泛地應用在各大領域[33]，其具體運算步驟如下所示：

步驟1初始化，生成n個煙花，并設置參數(shù)。

步驟2根據(jù)煙花的適應度值計算煙花的爆炸半徑Er和爆炸數(shù)目En，并產生爆炸煙花。

步驟3根據(jù)爆炸半徑Er和爆炸數(shù)目En產生高斯變異火花。

步驟4判斷是否滿足終止條件，若滿足，停止迭代并輸出最優(yōu)解。

步驟5從原始煙花、爆炸煙花及變異煙花中，根據(jù)適應度值選取n個煙花作為下次迭代的初始煙花，進入步驟2。

3.1.2 煙花算法設計

由于煙花算法優(yōu)異的搜索機制，近些年被廣泛應用在各大領域，其主要包含爆炸操作、高斯變異操作及選擇策略。

（1）爆炸操作。煙花算法在進行爆炸操作之前需要計算每個煙花的爆炸半徑及爆炸數(shù)目，為保證煙花的多樣性，可根據(jù)每個煙花的適應度值，自適應地調整產生的火花數(shù)目，一般來說，煙花的適應性越好（即適應度值越?。谝欢ǚ秶鷥瓤梢援a生的火花數(shù)目就越多，反之，煙花的適應性越差，所產生的火花數(shù)目就越少。產生火花的公式如下：

其中，M是調整產生火花數(shù)量的一個常數(shù)，N是煙花總個數(shù)，fmax是所有煙花中最大適應度值，τ是一個無限小的常數(shù)，用來避免零操作，表示第i個煙花的適應度值，Si表示第i個煙花將要產生的火花數(shù)目。由于公式（20）求解的結果是一個實數(shù)，但煙花產生的火花數(shù)目應為一個整數(shù)，因此可以通過公式（21）將公式（20）中求得的實數(shù)轉化為一個整數(shù)。

為防止煙花算法過早收斂，引入了一種自適應性的爆炸半徑求解方法，其原理是利用最優(yōu)煙花與選定煙花對爆炸算子進行改進，從而使不同煙花自適應調整自身的爆炸半徑。爆炸半徑計算公式如式（22）：

Ri表示第i個煙花的爆炸半徑，R?是調整爆炸半徑的一個常數(shù)，fmin表示所有煙花中最佳適應度值，f(xi)表示第i個煙花的適應度值，τ是一個無限小的常數(shù)，用來避免零操作。

（2）高斯變異操作。煙花算法引入了高斯變異算子，從而提高算法的種群多樣性，增強算法的全局搜索能力。高斯變異算子的具體操作步驟為，首先在當前煙花種群中隨機選取一個煙花，設為xi，然后對該煙花隨機選擇的維度進行高斯變異操作，對于煙花xi的在維度k進行高斯變異運算的公式如下：

其中，e～N(1,1),N(1,1)表示均值、方差為1的高斯分布。

（3）選擇策略。煙花種群在經(jīng)過爆炸操作及高斯變異操作后，會產生一系列新的煙花組成候選解。為使解空間中的優(yōu)秀信息可以傳遞到下一代種群，算法會在候選解中選擇一定數(shù)量的個體作為下一代煙花，首先按照精英策略選取候選者中適應度值最小的一個煙花個體作為下一代的初始煙花種群，然后使用輪盤賭的方法在候選解中選取剩余的N-1個煙花。煙花被選擇的概率公式如下：

其中，p(xi)表示煙花xi被選中的概率表示煙花xi與煙花xj之間的距離。

3.2 TSFWA-GA算法設計

在傳統(tǒng)煙花算法中，爆炸及變異操作會對煙花中的信息進行整體變換，因此，在迭代過程中會丟失煙花個體中包含的部分優(yōu)秀可行解信息，進而導致算法陷入局部最優(yōu)、搜索效率慢等問題。

為進一步優(yōu)化算法，提高算法的搜索效率及精度，將遺傳算法中的交叉變異操作引入到傳統(tǒng)煙花算法中，利用交叉變異操作對爆炸火花進行調整，加強煙花個體之間的信息交流，從而增強算法在此模型中的搜索效率，提高算法的局部尋優(yōu)能力。此外，增加禁忌表，以防止算法陷入局部最優(yōu)。TSFWA-GA算法的具體運算步驟如圖2所示。

圖2 TSFWA-GA算法流程圖Fig.2 TSFWA-GA flow chart

3.2.1 煙花編碼

在求解應急調度問題時，煙花算法可以用一維向量來表示問題的解，每個煙花都是一個解向量。初始化煙花時，隨機生成0～1之間的數(shù)，并對隨機數(shù)進行排序，利用數(shù)值的大小來表示車輛行駛過需求點的先后順序。過程如圖3所示，假設某一應急供應點要向6個需求點進行物資運輸，此時煙花個體可表示為X，其中pi表示應急供應點i。圖3中煙花個體X的解即表示依次訪問節(jié)點6、3、5、1、2、4。

圖3 初始化過程Fig.3 Initialization process

3.2.2 爆炸操作

爆炸操作采用2.1.2小節(jié)中爆炸火花數(shù)、爆炸半徑的計算公式，設煙花個體為xi，根據(jù)公式計算煙花的爆炸半徑Ri、爆炸火花數(shù)Si，然后使煙花xi在半徑為Ri的解空間中進行爆炸操作，重復Si次，直到產生Si個爆炸火花。

3.2.3 變異操作

變異操作可以增加煙花種群的多樣性，然而傳統(tǒng)煙花算法中的高斯變異算子會替換整個煙花個體，從而導致新產生的變異煙花損失原本煙花中所包含的優(yōu)秀可行解信息，造成算法搜索效率低、搜索精度低等問題。為此，引入了遺傳算法[34]的思想，利用遺傳算法中的交叉變異操作生成變異煙花，促進煙花個體之間的內部信息交流，從而增強算法的局部尋優(yōu)能力。

交叉變異操作的主要目的是將選取的爆炸花火進行變異，然后與目前的最優(yōu)火花進行信息交換。為了能讓爆炸火花與最優(yōu)火花更好地進行信息交互，會隨機產生一個[0，1]之間的數(shù)字，再根據(jù)交叉率和變異率對候選火花進行挑選，并對選中的爆炸火花進行變異，其變異方式是將煙花個體中隨機兩個路徑進行交換。如圖4所示：將3.2.1小節(jié)煙花個體X中的X(2)與X(5)位置的變量進行交換，隨機變異操作后的結果為X′。

圖4 隨機變異過程Fig.4 Random mutation process

變異操作完成后，需要與目前最優(yōu)的煙花個體進行交叉，其交叉操作為提取選中的煙花個體部分信息，并與最優(yōu)煙花個體中相應位置信息進行交換。具體操作過程如圖5所示：選中煙花個體為X，設目前最優(yōu)煙花個體為P，對選中煙花個體X進行信息提取，設提取的信息為X，并對提取信息的位置進行置零操作，然后從最優(yōu)煙花個體P中去尋找C信息，C內的元素在P中的順序記為C′，最后將C′中的信息合并到X中，形成新的煙花個體X。

圖5 隨機交叉過程Fig.5 Random crossover process

3.2.4 適應度評估函數(shù)

煙花算法是以適應度值來衡量煙花個體的優(yōu)劣，在本文所涉及的應急調度問題是以需求點的滿足率最大化及車輛行駛時間最小化為目標，因此采用理想點法將多目標問題轉化為單目標問題，并將目標值與理想值的加權歐幾里德距離作為煙花的適應度值。最后判斷整個過程是否滿足車輛數(shù)目約束及需求點滿意度約束，若不滿足，則將一個遠大于一般適應度值的數(shù)賦予此煙花適應度值，從而淘汰該煙花。

3.2.5 禁忌表

設置禁忌表的目的是避免算法在循環(huán)過程中陷入局部最優(yōu)，它通常記錄前若干次迭代中選取的煙花，禁止這些煙花在短期內返回。在迭代固定次數(shù)后，禁忌表釋放煙花，重新參加運算。

禁忌表的大小在很大程度上影響著搜索速度和求解精度。若禁忌表長度過小，搜索會進入死循環(huán)，整個搜索將圍繞著相同的幾個解徘徊；相反，若禁忌表長度過大，會很大程度上限制搜索區(qū)域，跳過當前最優(yōu)解。因此一個好的禁忌表長度應該是盡可能小卻又能避免算法進入循環(huán)。

3.2.6 選擇策略

煙花算法的選擇策略是煙花種群中的優(yōu)秀個體能否傳遞到下一次迭代的關鍵，因此可以采用錦標賽選擇策略每次從候選解中隨機抽取出70%的個體，然后選擇其中最優(yōu)的一個煙花，判斷此煙花個體是否在禁忌表中，若在禁忌表中，則放棄此煙花，從候選解中重新選取煙花，否則，此煙花個體進入下一次迭代，并存入禁忌表中。重復該操作直到新的種群規(guī)模達到原來的種群規(guī)模。

4 案例分析

假設某一地區(qū)出現(xiàn)突發(fā)性傳染疾病，其中有30個需求點受到突發(fā)事件的影響，需要大量醫(yī)療物資援助（設僅需要醫(yī)用口罩及防疫藥品兩種物資），每個需求點所需要的醫(yī)療物資數(shù)量會根據(jù)此需求點的患病人數(shù)而上下波動，各需求點初始狀態(tài)的易感者、暴露者、老年患病者、其他人群患病者、康復者數(shù)量如表1所示。設應急供應點目前有7輛可行駛車輛，每輛車速度相同，最大載重如表2所示。各需求點醫(yī)療物資庫存數(shù)量如表3所示。供應點到各需求點之間的時間如表4所示。

表1 SEIR模型初始值Table 1 SEIR model initial value

表2 車輛最大載重Table 2 Load of vehicle

表3 節(jié)點j的醫(yī)療物資庫存量Table 3 Node’s medical supplies inventory

表4 節(jié)點i到節(jié)點j的行駛時間Table 4 Travel time from i to j

根據(jù)上文所述算法實驗數(shù)據(jù)，利用MATLAB軟件進行仿真實驗分析，控制TSFWA-GA算法的參數(shù)如下：煙花數(shù)為20，變異火花數(shù)為70，爆炸數(shù)目為250，爆炸半徑為1 500，交叉率為0.7，變異率為0.2，禁忌步長為20，迭代次數(shù)為100次。為形成對比，又引入相同參數(shù)變量的基本煙花算法及遺傳算法，三種算法對比結果如圖6所示。

根據(jù)圖6的對比結果發(fā)現(xiàn)，在此次仿真實驗的醫(yī)療物資運輸求解過程中，TSFWA-GA算法、GA算法FWA算法、分別在15、40、45次迭代后趨于穩(wěn)定，但TSFWA-GA的求解結果最精確，其最優(yōu)值明顯比GA算法和FWA算法都要低。因此可以看出在此仿真實驗中，TSFWA-GA算法精確度更高，效果更好。由此可見，優(yōu)化后的煙花算法在保證完成運輸任務的同時，縮短運輸時間，可以有效地節(jié)約資源，降低成本，從而提高應急醫(yī)療物資調度的效率，為實現(xiàn)黃金時間內完成需求點所需醫(yī)療物資的運輸提供了理論基礎。

圖6 三種算法求解趨勢對比Fig.6 Comparison of three algorithms to solve change trend

為確保實驗合理性，將三種算法分別進行10次算法求解，實驗結果如表5所示。從表5可以看出，TSFWA-GA的最優(yōu)值為0.995 11，比其他兩種算法的求解適應度更高。從10次結果的平均值來看，F(xiàn)WA和GA兩種算法差距不大，而TSFWA-GA的平均值為1.014 43，在精準度方面優(yōu)于其他兩種算法。

表5 三種算法實驗對比Table 5 Comparison of three algorithms

傳統(tǒng)煙花算法中的變異策略會對煙花個體進行整體替換，很難保留最優(yōu)解中的優(yōu)秀信息，而TSFWA-GA算法中的變異策略采用了遺傳算法中的變異和交叉操作，可以更好地保留最優(yōu)煙花中的部分優(yōu)秀信息傳遞給下一代煙花，增強了算法的局部搜索能力。同時，又利用禁忌表的特點進一步改進，避免算法陷入局部最優(yōu)，從而提高了算法的尋優(yōu)能力。上述仿真實驗充分證明了此算法在應對醫(yī)療物資調度模型問題時，有著較強的尋優(yōu)能力，它可以在保證完成醫(yī)療物資運輸?shù)那疤嵯?，盡可能地減少車輛行駛路程，對提高受災地區(qū)的救助效率，降低生命及財產損失有著重要的實際意義。

5 結束語

醫(yī)療物資應急調度是應急管理中的重要工作之一，而在此次新冠肺炎疫情防控工作中，醫(yī)療物資的及時供給更是重中之重，因此對應急醫(yī)療物資配送和調度的研究是及其必要的。為更精準地預測各需求點所需物資，本文引入了SEIR模型，并根據(jù)疫情特點進行優(yōu)化，通過確定患病者人數(shù)，從而預測各需求點所需的消耗類醫(yī)療物資數(shù)量。隨后分析探討了應急調度的特點，根據(jù)其特點構建雙目標應急調度過程模型，為便于計算，利用理想點法將雙目標問題轉化為單目標問題。然后根據(jù)GA算法和禁忌搜索算法的特性設計了一種TSFWA-GA算法，并根據(jù)上述模型進行優(yōu)化，最后通過兩種規(guī)模的仿真實驗及與FWA算法和GA算法的對比，突出了TSFWA-GA算法在求解此模型問題中的高效性及穩(wěn)定性。本文不足之處在于只分析了一個應急供應點對多個需求點進行運輸?shù)那闆r，在實際情況中會有多個應急供應點對多個需求點進行物資運輸?shù)那闆r，因此多對多的醫(yī)療物資調度問題將是今后的重點研究方向。