疫情暴發(fā)初期應(yīng)急醫(yī)療物資配送優(yōu)化研究

趙銀婷，徐曉敏，周 行

(1.北京信息科技大學(xué) 信息管理學(xué)院，北京 100085；2. 中國科學(xué)院大學(xué) 電子與電氣工程學(xué)院，北京 100190)

0 引言

2019年末暴發(fā)的新冠肺炎疫情對國民經(jīng)濟和人民的安全造成了極大沖擊。重大疫情事件往往具有在短時間內(nèi)傳染速度快、傳播不確定性強等特點。當(dāng)疫情發(fā)生時，患者救治、醫(yī)護人員安全、疫災(zāi)點衛(wèi)生防疫等問題需要在第一時間得到處理，會對應(yīng)急醫(yī)療物資產(chǎn)生很大的需求。因此醫(yī)療物資的及時配送就成為應(yīng)對疫情重大公共衛(wèi)生事件的關(guān)鍵問題。近年來，國內(nèi)外學(xué)者對應(yīng)急醫(yī)療物資配送問題的探索主要集中于以下幾個方面。在單目標(biāo)建模優(yōu)化進行應(yīng)急物資配送的研究中主要有盧安文[1]，羅平[2]等學(xué)者，這些學(xué)者基于成本因素視角考慮運輸費用及多車型低耗車路徑問題進行了應(yīng)急物資配送的研究。Bouchra[3]，徐衛(wèi)[4]，Hu等[5]側(cè)重考慮時間的影響，基于最短運達(dá)時間建立模型對應(yīng)急物資的配送展開了探究。還有一些學(xué)者[6-9]則考慮公平原則，基于公平視角構(gòu)建了應(yīng)急醫(yī)療物資模型。在多目標(biāo)、多模型建模優(yōu)化進行應(yīng)急物資配送的研究中，一些學(xué)者[10-11]結(jié)合效率與公平及未滿足需求量和總物資延誤時間因素等建立了多目標(biāo)模型，且考慮物資的分類分批不同周期等來構(gòu)建多模型進行研究。

綜合以上研究成果可以看出，目前專門針對疫情應(yīng)急醫(yī)療物資配送優(yōu)化問題的研究相對較少，多數(shù)研究著眼于通用應(yīng)急物資的配送優(yōu)化，而沒有考慮突發(fā)公共衛(wèi)生事件所具有的特殊場景[12-14]。僅僅局限在單一應(yīng)急物資或單一車型的配送研究，沒有集成性考慮多種物資、多類車型的綜合性優(yōu)化。疫情應(yīng)急物流具有比較鮮明的特點，如疫情初期對醫(yī)療物資供不應(yīng)求、配送時間緊急性、物資需求點的變動性等不確定性因素更多，情況十分復(fù)雜[15-16]，因此需要針對疫情應(yīng)急事件物資配送的特點進行專門研究。鑒于此，本研究以我國應(yīng)對新冠肺炎重大疫情事件為背景，深入分析疫情中應(yīng)急醫(yī)療物資配送中存在的問題，結(jié)合我國國情，考慮疫情發(fā)生時疫災(zāi)地應(yīng)急物資儲備中心與當(dāng)?shù)蒯t(yī)療物資需求點之間，以需求點等待時間最短為目標(biāo)、構(gòu)建車輛-路徑的綜合優(yōu)化模型，并應(yīng)用改進蟻群算法實現(xiàn)對模型的求解，得出最佳配送方案。

1 模型構(gòu)建

1.1 研究背景

本研究主要針對重大疫情應(yīng)急醫(yī)療物資配送優(yōu)化問題專門進行。應(yīng)急醫(yī)療物資是指突發(fā)性自然災(zāi)害、公共衛(wèi)生事件等發(fā)生后，用于救治傷員、患者及保護醫(yī)護人員生命安全所需的一類專用物資，該類物資一般包括：各類醫(yī)療設(shè)備、醫(yī)療藥品及醫(yī)用防護用品等。應(yīng)急醫(yī)療物資具有不確定性、不可替代性、時效性及滯后性等特點。應(yīng)急醫(yī)療物資的及時保障對人民生命安全極為重要，因此應(yīng)急醫(yī)療物資的配送問題成為突發(fā)事件應(yīng)急管理的重中之重。應(yīng)急醫(yī)療物資保障一般包括物資籌措、物資調(diào)度、物資配送等環(huán)節(jié)，不同的突發(fā)事件其物資保障方式有所不同，其中尤以疫情醫(yī)療物資具有較大的特殊性，如：疫情發(fā)生時現(xiàn)有交通網(wǎng)絡(luò)、道路設(shè)置完好，但疫災(zāi)點位置、數(shù)量及疫災(zāi)點對醫(yī)療物資需求量和需求類型隨著時間呈現(xiàn)動態(tài)變化?；诖?，本研究針對疫區(qū)應(yīng)急醫(yī)療物資配送優(yōu)化問題進行深入探究。具體地，通過收集各疫災(zāi)點所需各類醫(yī)療物資信息，構(gòu)建從疫情地應(yīng)急物資儲備中心到各疫災(zāi)點的總等待時間最短的數(shù)學(xué)模型，對模型進行求解得出優(yōu)化配送方案，將應(yīng)急儲備中心內(nèi)有限的醫(yī)療物資在最短的時間內(nèi)快速、精準(zhǔn)送達(dá)至各個疫災(zāi)點。

1.2 模型假設(shè)

假設(shè)1：疫情發(fā)生地建有1個應(yīng)急醫(yī)療物資儲備中心，記為0點，有n個疫災(zāi)醫(yī)療物資需求點。

假設(shè)2：應(yīng)急醫(yī)療物資儲備中心的位置及醫(yī)療物資類型、供應(yīng)量、疫災(zāi)點位置、醫(yī)療物資類型和需求量已知，儲備中心與各疫災(zāi)點及疫災(zāi)點與疫災(zāi)點之間的線路連通且距離已知。

假設(shè)3：疫情發(fā)生時，當(dāng)?shù)貞?yīng)急管理部門政府臨時征用各類社會車輛(如公交車、出租車、私家車等)進行統(tǒng)一調(diào)度。車輛類型各異，運輸能力差別較大。配送車輛有其不同的核定載重及不同的運載體積限制，所有車輛從應(yīng)急物資儲備中心裝載醫(yī)療物資出發(fā)按照優(yōu)化方案將指定物資運送至指定的疫災(zāi)點。

疫情應(yīng)急醫(yī)療物資配送網(wǎng)絡(luò)模型見圖1。

圖1 應(yīng)急醫(yī)療物資配送網(wǎng)絡(luò)模型

1.3 模型建立

目標(biāo)函數(shù)：以各疫災(zāi)點總的等待時間最短來構(gòu)建數(shù)學(xué)模型，尋求出最優(yōu)的配送路徑方案，同時找到各疫災(zāi)點的總的最短等待時間，即：

(1)

約束條件1 應(yīng)急儲備中心醫(yī)療物資供應(yīng)量和各疫災(zāi)點需求量之間的約束?？紤]疫情初期醫(yī)療物資供不應(yīng)求的實際情況，則各疫災(zāi)點的總需求量應(yīng)大于應(yīng)急醫(yī)療物資的總供應(yīng)量，即：

(2)

式中，r為醫(yī)療物資的類型；p為醫(yī)療物資的類型總數(shù)；Fr為第r種醫(yī)療物資的供應(yīng)量；Qr為第r種醫(yī)療物資的需求量。

約束條件2 各車型的可載醫(yī)療物資總體積不能超過各車型的核定載容量，即：

(3)

式中，w為配送車輛的類型；u為車輛的類型總數(shù)；ar為第r種醫(yī)療物資的單位體積；λw為第w種類型車的載容量；Gw為第w種類型車的數(shù)量；Ywr為車輛在實際配送中，第w類車輛所裝第r類醫(yī)療物資的量。

約束條件3 各車型所裝載各種物資的總重不能超過其核定載重，即：

(4)

式中，br為第r種醫(yī)療物資的單位質(zhì)量；βw為第w種類型車的載重量。

約束條件4 可供應(yīng)的所有應(yīng)急醫(yī)療物資總體積不得超過所有運載車輛總的載容量，即：

(5)

約束條件5 可供應(yīng)的所有應(yīng)急醫(yī)療物資總質(zhì)量不得超過所有運載車輛總的載重，即：

(6)

2 優(yōu)化實現(xiàn)

上述應(yīng)急醫(yī)療物資配送優(yōu)化問題因其包括車輛-路徑的集成優(yōu)化，模型變量及約束條件較多，求解比較復(fù)雜。針對該模型的這些特點，選擇具有較強魯棒性、并行性、穩(wěn)定性及能夠快速求解的蟻群算法比較合適。蟻群算法(Ant Colony Optimization，ACO)是由意大利學(xué)者Dorigo等[17]在1991 年創(chuàng)造的一種隨機搜索算法。該算法的理念來自于自然界中蟻群尋找食物的現(xiàn)象[18]。許多研究表明蟻群算法在解決物資分配、路徑優(yōu)化等問題時表現(xiàn)出良好性能[19-20]。

2.1 信息素更新規(guī)則

在每次尋找路線的迭代中，每只螞蟻代表的車輛都從應(yīng)急物資儲備中心出發(fā)開始訪問，在訪問任意1個疫災(zāi)點后都有一定的概率決定是否繼續(xù)配送后面的疫災(zāi)點，而一旦這只螞蟻決定配送下一個疫災(zāi)點，則當(dāng)前疫災(zāi)點完成配送，并將之放到禁忌表的點集中。經(jīng)過1次迭代，可以得到各車輛所配送分路徑，而螞蟻代表的車輛在每次運動過程中都會釋放信息素到所走的路徑上。到疫災(zāi)點各路線上信息素的更新規(guī)則為:

(7)

式中，信息素濃度τij為當(dāng)前配送車輛在對疫災(zāi)點i配送完成后，下一個疫災(zāi)點j對該車輛產(chǎn)生的吸引程度；Q為信息素強度(此處Q=800)；T為本次迭代中各疫災(zāi)點總的等待時間。疫災(zāi)點總的等待時間對信息素濃度的增量有很大的影響，總等待時間越短，則信息素濃度的增量則會越大。

2.2 狀態(tài)轉(zhuǎn)移規(guī)則

車輛在選擇配送疫災(zāi)點的過程中，各分路徑線上的信息素濃度同時會影響車輛下一步的轉(zhuǎn)移方向。隨著路徑上不斷積累新的信息素，車輛在配送的過程中會根據(jù)各路徑上信息素的強度及各路徑的啟發(fā)式信息決定下一步行動方向，即狀態(tài)轉(zhuǎn)移概率。上面對信息素改進中增加了提升信息素濃度系數(shù)k1，因此在螞蟻由疫災(zāi)點向另一個疫災(zāi)點的轉(zhuǎn)移概率也會隨之變化。其中，螞蟻k由當(dāng)前疫災(zāi)點i到可訪問的疫災(zāi)點集合j中的狀態(tài)轉(zhuǎn)移概率為：

(8)

ηij=1/dij，

(9)

式中allowedk=(N-V)，為螞蟻k當(dāng)前可選擇配送的所有疫災(zāi)點集合；τij為疫災(zāi)點i到j(luò)上的信息素濃度；α為信息素重要程度因子；β為啟發(fā)函數(shù)重要程度因子；dij為待配送疫災(zāi)點i到j(luò)的距離；ηij為螞蟻從疫災(zāi)點i到j(luò)的期望程度。當(dāng)螞蟻在某疫災(zāi)點完成配送，則該疫災(zāi)點以后將不能被訪問。

通過上述改進，克服了標(biāo)準(zhǔn)蟻群算法在搜索空間和時間性能上的不協(xié)調(diào)，較好地實現(xiàn)了每只螞蟻(所代表相應(yīng)的車輛)找到所負(fù)責(zé)的1個或多個疫災(zāi)點的1條路徑。將所有螞蟻找到的路徑組合在一起得到完整疫災(zāi)點的配送路線，繼而得到各個疫災(zāi)點總的最短等待時間。

基于改進蟻群算法的疫情應(yīng)急物資配送優(yōu)化求解步驟為：

(1)初始化各參數(shù)，將Nc設(shè)定為迭代次數(shù)，開始時間t=0，Nc=0，設(shè)定最大的迭代次數(shù)Nmax。將m只螞蟻放在應(yīng)急物資儲備中心，初始時刻 Δτij(0)=0。

(2)建立禁忌表，根據(jù)狀態(tài)轉(zhuǎn)移式(8)，確定下一個配送的疫災(zāi)點(通過蟻群算法確定的概率由輪盤算法選擇1個疫災(zāi)點)，并將這個疫災(zāi)點列入禁忌表。直到螞蟻走完全部的疫災(zāi)點，終結(jié)螞蟻的循環(huán)活動。

(3)記錄本次迭代各疫災(zāi)點總的最短等待時間，當(dāng)前迭代次數(shù)中的最短等待時間即是所求的各車輛運行最佳路線上對應(yīng)各疫災(zāi)點最短等待時間的和，按信息素更新式(7)進行信息素全局更新。

(4)記錄各疫災(zāi)點總的最短等待時間，并多次執(zhí)行(2)～(4)，使之達(dá)到最大迭代次數(shù)。

(5)結(jié)果輸出。

3 模型應(yīng)用

以下通過實際算例對疫情應(yīng)急醫(yī)療物資配送模型及優(yōu)化算法的有效性進行驗證。

3.1 應(yīng)用數(shù)據(jù)

假定某地有8個疫災(zāi)點，N=8，1個應(yīng)急醫(yī)療物資儲備中心0點，待配送應(yīng)急醫(yī)療物資的種類總數(shù)p=4，車輛的類型總數(shù)u=4，用A～D表示，且共有車15 veh。等待裝配車輛基本信息如表1所示。

表1 車輛基本信息

待配送應(yīng)急醫(yī)療物資的單位重量和單位體積信息如表2所示。

表2 應(yīng)急醫(yī)療物資基本信息

其中，各類車型均從應(yīng)急醫(yī)療物資儲備中心0點出發(fā)，向8個疫災(zāi)點配送應(yīng)急物資，其中各疫災(zāi)點對各種醫(yī)療物資的需求量信息如表3所示。

表3 應(yīng)急醫(yī)療物資需求信息

本研究背景主要針對疫情初期，多數(shù)疫災(zāi)點對應(yīng)急醫(yī)療物資的需求量大于當(dāng)前的可供應(yīng)量。其中可供應(yīng)系數(shù)為可供應(yīng)量和需求量的比值，若各類應(yīng)急醫(yī)療物資的可供應(yīng)量小于需求量，則該類醫(yī)療物資的實際供應(yīng)量為可供應(yīng)量；若此類醫(yī)療物資的可供應(yīng)量大于需求量，則取需求量為其實際供應(yīng)量。

應(yīng)急醫(yī)療物資的實際供應(yīng)情況如表4所示。

表4 應(yīng)急醫(yī)療物資供應(yīng)信息

由表4可見各類物資對應(yīng)的可供應(yīng)系數(shù)和實際供應(yīng)量等信息。其中，應(yīng)急物資儲備中心與各疫災(zāi)點之間及疫災(zāi)點和疫災(zāi)點之間的距離如表5所示，表5即為配送網(wǎng)絡(luò)距離矩陣。

表5 節(jié)點之間的距離

3.2 應(yīng)用過程

參數(shù)初始化：設(shè)螞蟻數(shù)等于可配送疫災(zāi)點的數(shù)(可合并配送的疫災(zāi)點記為1個疫災(zāi)點)，將所有的螞蟻分布在應(yīng)急醫(yī)療物資儲備點0，假設(shè)各類型車輛的速度均為V=0.6 km/min，α=1，β=5，ρ=0.1，迭代1 000次后，可以得到1個比較滿意的優(yōu)化結(jié)果，各疫災(zāi)點總的等待時間最短為1 108.33 min。改進蟻群算法的迭代情況如圖2所示。

圖2 改進ACO算法優(yōu)化實現(xiàn)過程

3.3 優(yōu)化結(jié)果

對模型進行優(yōu)化求解，可得到關(guān)于車輛-路徑綜合優(yōu)化結(jié)果。表6為滿足各疫災(zāi)點醫(yī)療物資需求下所走路徑、各疫災(zāi)點分配的配送車輛及各類醫(yī)療物資實際配送的數(shù)量。其中，1 veh A型車和1 veh D型車依次經(jīng)過疫災(zāi)點2和疫災(zāi)點7，裝載醫(yī)療物資1有2 387件，醫(yī)療物資2有440件，醫(yī)療物資3有861件，醫(yī)療物資4有2 310件，滿足疫災(zāi)點2和疫災(zāi)點7所需的各種醫(yī)療物資。圖3為將疫情地應(yīng)急醫(yī)療物資儲備中心、各類醫(yī)療物資、各種車型各個疫災(zāi)點聯(lián)系而構(gòu)建的疫情地應(yīng)急醫(yī)療物資優(yōu)化匹配圖。

表6 應(yīng)急醫(yī)療物資具體配送方案

圖3 車輛路線匹配圖

3.4 結(jié)果對比

為進一步研究改進蟻群算法的性能, 利用改進遺傳算法對本研究的算例進行求解, 設(shè)置遺傳算法的交叉概率為 0.9, 變異概率為 0.1,迭代1 000次后找到最優(yōu)的結(jié)果。用改進遺傳算法求出的最短等待時間及路徑方案與改進蟻群算法的求解結(jié)果進行了觀察對比。圖4為改進遺傳算法迭代過程，表7對比了改進蟻群算法和改進遺傳算法運行效果。

圖4 改進遺傳算法優(yōu)化實現(xiàn)過程

由表7可以看到，改進后的蟻群算法在求解應(yīng)急醫(yī)療物資配送路徑優(yōu)化問題的過程中，改變算法的編碼和解碼規(guī)則, 使之適用于求解離散問題、良好的協(xié)調(diào)全局搜索能力和局部搜索能力。本研究對比使用改進的蟻群算法和改進的遺傳算法對所建的模型進行了求解，最終表明改進蟻群算法的優(yōu)化結(jié)果要優(yōu)于改進遺傳算法，且在求解過程中加快了算法的收斂速度，提高了算法的穩(wěn)定性。

表7 算法運行結(jié)果比較

4 結(jié)論

本研究以疫情應(yīng)急醫(yī)療物資配送為背景，結(jié)合我國國情，考慮疫情發(fā)生時疫災(zāi)地應(yīng)急儲備中心與當(dāng)?shù)蒯t(yī)療物資需求點之間的聯(lián)系，以疫災(zāi)點等待時間最短為目標(biāo)、構(gòu)建了車輛-路徑的集成優(yōu)化模型。通過使用改進蟻群算法實現(xiàn)了對優(yōu)化模型的求解，得出最優(yōu)路線選擇和車輛調(diào)配方案，解決了多車型、多物資、多疫災(zāi)點應(yīng)急醫(yī)療物資在需求緊急狀態(tài)下快速、高效配送問題，對其他突發(fā)事件應(yīng)急物資配送研究與實踐均具有一定的參考和借鑒價值。