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

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

2.中國(guó)華能集團(tuán)有限公司 信息中心，北京100031

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

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

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

1 國(guó)內(nèi)外文獻(xiàn)綜述

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

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

2 醫(yī)療物資應(yīng)急調(diào)度模型

2.1 問(wèn)題描述

2.1.1 問(wèn)題提出

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

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

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

2.1.2 基本假設(shè)

為了便于建模及求解，先對(duì)模型所需信息進(jìn)行假設(shè)：

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

（2）假設(shè)供應(yīng)點(diǎn)有幾種不同的相服務(wù)車輛，各車輛的載重不同，但速度相同，且車輛勻速行駛。

（3）忽略裝貨卸貨時(shí)間的影響，只計(jì)算車輛行駛時(shí)間。

（4）運(yùn)輸為閉合回路，即車輛完成運(yùn)輸任務(wù)后需要返回供應(yīng)點(diǎn)。

（5）假設(shè)各需求點(diǎn)與供應(yīng)點(diǎn)之間直接互通，且忽略天氣、堵車、道路損壞等因素影響。

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

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

2.2 基于SEIR的應(yīng)急物資預(yù)測(cè)模型

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

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

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

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

總?cè)丝跀?shù)量約束如下：

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

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

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

2.3.1 模型符號(hào)定義

為了方便描述，對(duì)以下符號(hào)進(jìn)行定義：

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

2.3.2 模型構(gòu)建

目標(biāo)函數(shù)：

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

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

約束（7）表示需求緊急度計(jì)算公式，在周期ω內(nèi)需求點(diǎn)儲(chǔ)備量可以滿足需求時(shí)，緊急度為0，需求點(diǎn)無(wú)儲(chǔ)備量時(shí)緊急度最大，為1。

約束（8）表示滿意度計(jì)算公式，當(dāng)供大于求時(shí)，滿意度最大值為1。

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

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

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

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

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

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

2.3.3 問(wèn)題轉(zhuǎn)化

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

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

3 算法設(shè)計(jì)

3.1 煙花算法介紹

3.1.1 煙花算法原理

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

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

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

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

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

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

3.1.2 煙花算法設(shè)計(jì)

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

（1）爆炸操作。煙花算法在進(jìn)行爆炸操作之前需要計(jì)算每個(gè)煙花的爆炸半徑及爆炸數(shù)目，為保證煙花的多樣性，可根據(jù)每個(gè)煙花的適應(yīng)度值，自適應(yīng)地調(diào)整產(chǎn)生的火花數(shù)目，一般來(lái)說(shuō)，煙花的適應(yīng)性越好（即適應(yīng)度值越?。谝欢ǚ秶鷥?nèi)可以產(chǎn)生的火花數(shù)目就越多，反之，煙花的適應(yīng)性越差，所產(chǎn)生的火花數(shù)目就越少。產(chǎn)生火花的公式如下：

其中，M是調(diào)整產(chǎn)生火花數(shù)量的一個(gè)常數(shù)，N是煙花總個(gè)數(shù)，fmax是所有煙花中最大適應(yīng)度值，τ是一個(gè)無(wú)限小的常數(shù)，用來(lái)避免零操作，表示第i個(gè)煙花的適應(yīng)度值，Si表示第i個(gè)煙花將要產(chǎn)生的火花數(shù)目。由于公式（20）求解的結(jié)果是一個(gè)實(shí)數(shù)，但煙花產(chǎn)生的火花數(shù)目應(yīng)為一個(gè)整數(shù)，因此可以通過(guò)公式（21）將公式（20）中求得的實(shí)數(shù)轉(zhuǎn)化為一個(gè)整數(shù)。

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

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

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

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

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

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

3.2 TSFWA-GA算法設(shè)計(jì)

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

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

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

3.2.1 煙花編碼

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

圖3 初始化過(guò)程Fig.3 Initialization process

3.2.2 爆炸操作

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

3.2.3 變異操作

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

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

圖4 隨機(jī)變異過(guò)程Fig.4 Random mutation process

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

圖5 隨機(jī)交叉過(guò)程Fig.5 Random crossover process

3.2.4 適應(yīng)度評(píng)估函數(shù)

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

3.2.5 禁忌表

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

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

3.2.6 選擇策略

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

4 案例分析

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

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

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

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

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

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

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

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

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

表5 三種算法實(shí)驗(yàn)對(duì)比Table 5 Comparison of three algorithms

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

5 結(jié)束語(yǔ)

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