疫情暴發初期應急醫療物資配送優化研究

趙銀婷，徐曉敏，周 行

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

0 引言

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

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

1 模型構建

1.1 研究背景

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

1.2 模型假設

假設1：疫情發生地建有1個應急醫療物資儲備中心，記為0點，有n個疫災醫療物資需求點。

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

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

疫情應急醫療物資配送網絡模型見圖1。

圖1 應急醫療物資配送網絡模型

1.3 模型建立

目標函數：以各疫災點總的等待時間最短來構建數學模型，尋求出最優的配送路徑方案，同時找到各疫災點的總的最短等待時間，即：

(1)

約束條件1 應急儲備中心醫療物資供應量和各疫災點需求量之間的約束。考慮疫情初期醫療物資供不應求的實際情況，則各疫災點的總需求量應大于應急醫療物資的總供應量，即：

(2)

式中，r為醫療物資的類型；p為醫療物資的類型總數；Fr為第r種醫療物資的供應量；Qr為第r種醫療物資的需求量。

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

(3)

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

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

(4)

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

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

(5)

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

(6)

2 優化實現

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

2.1 信息素更新規則

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

(7)

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

2.2 狀態轉移規則

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

(8)

ηij=1/dij，

(9)

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

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

基于改進蟻群算法的疫情應急物資配送優化求解步驟為：

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

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

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

(4)記錄各疫災點總的最短等待時間，并多次執行(2)～(4)，使之達到最大迭代次數。

(5)結果輸出。

3 模型應用

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

3.1 應用數據

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

表1 車輛基本信息

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

表2 應急醫療物資基本信息

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

表3 應急醫療物資需求信息

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

應急醫療物資的實際供應情況如表4所示。

表4 應急醫療物資供應信息

由表4可見各類物資對應的可供應系數和實際供應量等信息。其中，應急物資儲備中心與各疫災點之間及疫災點和疫災點之間的距離如表5所示，表5即為配送網絡距離矩陣。

表5 節點之間的距離

3.2 應用過程

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

圖2 改進ACO算法優化實現過程

3.3 優化結果

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

表6 應急醫療物資具體配送方案

圖3 車輛路線匹配圖

3.4 結果對比

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

圖4 改進遺傳算法優化實現過程

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

表7 算法運行結果比較

4 結論

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