趙銀婷，徐曉敏，周 行

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

0 引言

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

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

1 模型構(gòu)建

1.1 研究背景

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

1.2 模型假設(shè)

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

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

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

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

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

1.3 模型建立

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

(1)

約束條件1 應(yīng)急儲(chǔ)備中心醫(yī)療物資供應(yīng)量和各疫災(zāi)點(diǎn)需求量之間的約束。考慮疫情初期醫(yī)療物資供不應(yīng)求的實(shí)際情況，則各疫災(zāi)點(diǎn)的總需求量應(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為車輛在實(shí)際配送中，第w類車輛所裝第r類醫(yī)療物資的量。

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

(4)

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

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

(5)

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

(6)

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

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

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

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

(7)

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

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

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

(8)

ηij=1/dij，

(9)

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

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

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

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

(2)建立禁忌表，根據(jù)狀態(tài)轉(zhuǎn)移式(8)，確定下一個(gè)配送的疫災(zāi)點(diǎn)(通過蟻群算法確定的概率由輪盤算法選擇1個(gè)疫災(zāi)點(diǎn))，并將這個(gè)疫災(zāi)點(diǎn)列入禁忌表。直到螞蟻?zhàn)咄耆康囊邽?zāi)點(diǎn)，終結(jié)螞蟻的循環(huán)活動(dòng)。

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

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

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

3 模型應(yīng)用

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

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

假定某地有8個(gè)疫災(zāi)點(diǎn)，N=8，1個(gè)應(yīng)急醫(yī)療物資儲(chǔ)備中心0點(diǎn)，待配送應(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ī)療物資儲(chǔ)備中心0點(diǎn)出發(fā)，向8個(gè)疫災(zāi)點(diǎn)配送應(yīng)急物資，其中各疫災(zāi)點(diǎn)對(duì)各種醫(yī)療物資的需求量信息如表3所示。

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

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

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

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

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

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

3.2 應(yīng)用過程

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

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

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

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

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

圖3 車輛路線匹配圖

3.4 結(jié)果對(duì)比

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

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

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

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

4 結(jié)論

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