突發(fā)事件下應(yīng)急物資多目標(biāo)優(yōu)化調(diào)度模型與算法研究:以新冠肺炎疫情為例

單子丹, 盛晨輝, 王曉燕, 韓 姣

(1.哈爾濱理工大學(xué) 經(jīng)濟(jì)與管理學(xué)院,黑龍江 哈爾濱 150040; 2.哈爾濱理工大學(xué) 高新技術(shù)產(chǎn)業(yè)發(fā)展研究中心,黑龍江 哈爾濱 150040)

0 引言

2020年初，新冠肺炎在全國蔓延，徹底打亂了國民社會生活秩序和經(jīng)濟(jì)發(fā)展進(jìn)程。突發(fā)事件應(yīng)對過程中所需要的各類生命救助、防護(hù)用品等合稱為應(yīng)急物資，是成功應(yīng)對突發(fā)事件的基本保障[1]。二月上旬武漢各大醫(yī)院陸續(xù)向社會發(fā)布接受抗疫物資捐贈公告，急需進(jìn)行醫(yī)療物資的緊急調(diào)度。如何以最合理、高效的運(yùn)輸方式將物資在所需時間內(nèi)送達(dá)是此次疫情期間物資跨區(qū)域調(diào)度亟待解決的突出問題。

目前國內(nèi)外學(xué)者從不同視角出發(fā)，對應(yīng)急物資調(diào)度問題進(jìn)行了較為廣泛的研究。在應(yīng)急物資調(diào)度過程中，救援時間能夠?qū)崿F(xiàn)最短是大多數(shù)學(xué)者考慮的首要因素[2-3]。考慮到災(zāi)后路網(wǎng)受損等特殊情況，學(xué)者們結(jié)合多種運(yùn)輸方式探索物資調(diào)度方式[4-5]。同時也考慮到了災(zāi)后物資需求存在著高度不確定性[6-7]。根據(jù)配送網(wǎng)絡(luò)級數(shù)不同常常分為二級和三級調(diào)度網(wǎng)絡(luò)，現(xiàn)有研究大多數(shù)為二級配送網(wǎng)絡(luò)[9]。學(xué)者們多以成本與時間作為模型構(gòu)建目標(biāo)[3-4]。為了有效求解應(yīng)急物資調(diào)度問題，近年來國內(nèi)外學(xué)者將研究熱點(diǎn)轉(zhuǎn)向了進(jìn)化算法[9-10]。粒子群算法相對于其他智能算法具有實(shí)現(xiàn)容易、收斂速度快、求解質(zhì)量高等優(yōu)勢，在應(yīng)急管理領(lǐng)域已經(jīng)得到了廣泛的應(yīng)用，但易產(chǎn)生早熟收斂，針對這一問題對粒子群算法進(jìn)行了改進(jìn)用于模型的求解。

可以發(fā)現(xiàn)，大多數(shù)學(xué)者對于三級配送網(wǎng)絡(luò)研究較少。事實(shí)上，新冠肺炎應(yīng)急物資調(diào)度具有區(qū)域波及范圍廣、跨區(qū)域協(xié)調(diào)強(qiáng)度大等特點(diǎn)，在模型構(gòu)建目標(biāo)、擇優(yōu)方式及約束設(shè)計上有別于以往研究，且現(xiàn)有研究提出的多方式運(yùn)輸大多基于路網(wǎng)損毀情況下，路網(wǎng)尚好情況下大多是單一車輛運(yùn)輸方式。因此提出了包含多周期、多集散點(diǎn)、配送中心、需求點(diǎn)和運(yùn)輸方式的多目標(biāo)優(yōu)化調(diào)度復(fù)雜網(wǎng)絡(luò)模型。

1 問題描述與模型假設(shè)

1.1 問題描述

基于上述分析，疫情發(fā)生后，構(gòu)建集散-送中心-需求點(diǎn)三級調(diào)度網(wǎng)絡(luò)。考慮物資需求的緊迫性、物資送達(dá)時間要求的特殊性、運(yùn)輸成本的經(jīng)濟(jì)性，本文采用航空和公路運(yùn)輸相結(jié)合的運(yùn)輸方式來柔性選擇運(yùn)輸方式。結(jié)合在不同周期應(yīng)急物資需求和供給存在動態(tài)變化角度，建立如下物資調(diào)度網(wǎng)絡(luò)，示意圖如下圖1:

圖1 兩階段多周期應(yīng)急物資動態(tài)調(diào)配示意圖

1.2 模型假設(shè)

結(jié)合應(yīng)急物資的調(diào)度特征，做出如下假設(shè):

(1)每個周期集散中心的供給量和需求點(diǎn)的需求量已知，且供給量不會超過需求量。

(2)集散中心至配送中心至需求點(diǎn)間道路相通可以進(jìn)行長期的物資調(diào)配。

(3)不同類別的應(yīng)急物資在不超載的前提下可由同一運(yùn)輸工具進(jìn)行裝載。

(4)以一天(24h)為一個決策周期，所有周期的物資起運(yùn)時間均為0時刻。

2 動態(tài)多階段應(yīng)急物資調(diào)度模型構(gòu)建

2.1 符號說明

(1)集合符號

集合符號含義集合符號含義I物資集散中心集合(i∈I)J應(yīng)急物資配送中心集合(j∈J)M疫情需求點(diǎn)集合(m∈M)K應(yīng)急物資種類集合(k∈K)N物資配送周期集合(n∈N)H集散中心至配送中心的運(yùn)輸方式集合,H={α,β}

(2)參數(shù)符號

參數(shù)符號符號含義Snikn周期應(yīng)急物資集散中心i對物資k的供給量Rnikn周期末應(yīng)急物資集散中心i對物資k的庫存量Rnjkn周期末應(yīng)急物資配送中心j對物資k的庫存量Dnmkn周期疫情需求點(diǎn)m對應(yīng)急物資k產(chǎn)生的當(dāng)周期需求量Lnmkn周期疫情需求點(diǎn)m對應(yīng)急物資k產(chǎn)生的短缺量Snijn周期應(yīng)急物資集散中心i向配送中心j運(yùn)輸?shù)淖畲蠊?yīng)量Snimn周期應(yīng)急物資配送中心j向疫情需求點(diǎn)m運(yùn)輸?shù)淖畲蠊?yīng)量Cnhijn周期使用運(yùn)輸方式h從集散中心i向配送中心j的單位運(yùn)輸成本Cnjmn周期配送中心j向疫情需求點(diǎn)m運(yùn)輸?shù)墓愤\(yùn)輸單位成本dij應(yīng)急物資集散中心i和應(yīng)急物資配送中心j之間的距離djm應(yīng)急物資配送中心j與疫情需求點(diǎn)m之間的距離Qkk物資的單位重量,gVnhijn周期使用運(yùn)輸方式h從應(yīng)急物資集散中心i至配送中心j的速度Vjm應(yīng)急物資配送中心j至需求點(diǎn)m的公路運(yùn)輸行駛速度tnikn周期從i地開始運(yùn)送物資k的時刻tnijn周期從應(yīng)急物資集散中心i至物資配送中心j的道路通行時間tnjmn周期從應(yīng)急物資配送中心j至疫情需求點(diǎn)m的道路通行時間tnjkn周期應(yīng)急物資到達(dá)配送中心j后必要的裝卸搬運(yùn)作業(yè)時間tnmkn周期應(yīng)急物資k送達(dá)疫情需求點(diǎn)m的時間

(3)決策變量符號

決策變量符號含義xnijkn周期從應(yīng)急物資集散中心i至配送中心j運(yùn)輸應(yīng)急物資k的數(shù)量xnjmkn周期從物資配送中心j至疫情需求點(diǎn)m運(yùn)輸應(yīng)急物資k的數(shù)量

2.2 時間窗下的物資調(diào)度懲罰函數(shù)

①硬時間窗約束[ET,LT]。ET和LT分別為最早和最晚送達(dá)時間。物資只有在此時間段內(nèi)送達(dá)才能被接受。

②軟時間窗約束[EET,ET)。EET為適當(dāng)放寬的早送達(dá)時間上限，同時需要根據(jù)早送到的時間長短接受懲罰。

③軟時間窗約束(LT,ELT]。ELT為適當(dāng)放寬的晚送達(dá)時間上限，同時需要根據(jù)晚送到的時間長短接受懲罰。

④[0,EET),(ELT,-)，在這兩個時間窗內(nèi)送達(dá)的物資均違反了軟硬時間窗約束。

考慮疫情期間對物資需求的緊迫性，物資送達(dá)時間應(yīng)越早越好，晚送達(dá)會產(chǎn)生相應(yīng)懲罰成本，因此疫情下物資送達(dá)時間窗的約束如圖3。不同需求點(diǎn)相應(yīng)非線性懲罰函數(shù)如式(1)。

圖2 混合時間窗懲罰函數(shù)示意圖

圖3 疫情下需求點(diǎn)時間窗示意圖

(1)

2.3 三級跨區(qū)域動態(tài)調(diào)度模型建立

疫情爆發(fā)初期患者人數(shù)激增，醫(yī)療物資產(chǎn)生了大量缺口，長時間短缺不僅會錯失治療患者的最佳機(jī)會，還會帶來巨大的心理恐慌，因此盡可能降低物資短缺是模型建立的首要目標(biāo)。

(2)

其中，f1即n周期所有疫情需求點(diǎn)的各種物資需求短缺程度值的總和。βm為m地的應(yīng)急物資需求緊急程度。

需求點(diǎn)根據(jù)疫情情況確定物資送達(dá)時間窗口，應(yīng)急物資應(yīng)盡可能實(shí)現(xiàn)在所需時間內(nèi)送達(dá)，由此建立時間窗約束下懲罰函數(shù)如下式(3):

(3)

其中，f2為n周期所有需求點(diǎn)在軟-硬混合時間窗約束下的總懲罰成本。

大批量多批次長距離運(yùn)輸會產(chǎn)生較高的運(yùn)輸費(fèi)用，出于經(jīng)濟(jì)性考慮，將運(yùn)輸成本作為目標(biāo)函數(shù)的評價依據(jù)，表達(dá)式如下式(4):

(4)

其中，f3為n周期物資的總運(yùn)輸成本，α表示航空運(yùn)輸，β表示公路運(yùn)輸。

由上述分析，應(yīng)急物資調(diào)度模型構(gòu)建如下:

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

3 模型求解與啟發(fā)性算法

3.1 多目標(biāo)函數(shù)的轉(zhuǎn)化

上述模型三個目標(biāo)函數(shù)分屬不同量綱。蔣杰輝等在論文中引入時間成本系數(shù)，將多目標(biāo)函數(shù)轉(zhuǎn)化為單目標(biāo)函數(shù)[12]。借鑒此思想，引入短缺時間成本系數(shù)μ，將多目標(biāo)函數(shù)轉(zhuǎn)化為單目標(biāo)函數(shù)并將三個權(quán)重系數(shù)分別設(shè)置為μ1、μ2和μ3。從而轉(zhuǎn)化為如下單目標(biāo)函數(shù):

minF=μ1·F1+μ2·F2+μ3·F3

(22)

3.2 改進(jìn)粒子群算法的應(yīng)用

3.2.1 粒子群優(yōu)化算法

粒子群優(yōu)化算法由兩位學(xué)者受鳥群捕食現(xiàn)象啟發(fā)提出的智能算法[13]。粒子通過跟蹤個體和群體極值來更新自身位置和速度即:

(23)

(24)

3.2.2 改進(jìn)DCWPSO算法

為解決粒子群算法早熟收斂問題，有學(xué)者對慣性權(quán)重ω進(jìn)行了深入研究。Shi Y提出了線性遞減慣性權(quán)重策略[14]:

(25)

其中iter為當(dāng)前迭代次數(shù)，ω變化只與迭代次數(shù)線性相關(guān)。文獻(xiàn)[15]通過實(shí)驗(yàn)證明動態(tài)變慣性權(quán)重自適應(yīng)粒子群(DCWPSO)算法性能明顯優(yōu)于LDW算法，引入聚焦距離變化率概念。

(26)

(27)

(28)

(29)

其中，MaxDist和MeanDist分別為最大和平均聚焦距離。本文在此基礎(chǔ)上，引入變異算子，使得收斂速度和精度進(jìn)一步優(yōu)化，簡稱此算法為VDCWPSO算法。具體流程圖如下：

圖4 VDCWPSO算法流程圖

3.3 實(shí)例計算與分析

3.3.1 問題實(shí)例

以新冠肺炎為背景，數(shù)據(jù)來源于武漢市部分區(qū)新冠肺炎真實(shí)數(shù)據(jù)和部分仿真數(shù)據(jù)，本文選取2月24日至29日疫情數(shù)據(jù)，選如下部分區(qū)作為需求點(diǎn)：江岸區(qū)、江漢區(qū)、漢陽區(qū)、武昌區(qū)、青山區(qū)、江夏區(qū)。將天河機(jī)場和漢南機(jī)場作為配送點(diǎn)；合肥、西安作為集散點(diǎn)；選取醫(yī)用防護(hù)口罩、醫(yī)用防護(hù)服、84消毒液作為調(diào)配物資。其中合肥和西安距離天河機(jī)場分別為447和762km,合肥和西安距離漢南機(jī)場分別為437和769km。天河機(jī)場距離江岸、江漢、漢陽、武昌、青山、江夏區(qū)分別為28，24，32，32，36，59km，漢南機(jī)場距離六區(qū)距離分別為51，50，42，52，65，43km。六區(qū)物資送達(dá)時間窗要求為LT:14，5，13，4，14，15時，ELT：16，6，15，6，15，16時。航空和公路運(yùn)輸單價分別為1700和20元/t/h，平均速度分別為500和80km/h，其中航空運(yùn)輸單價參考上海機(jī)場貨運(yùn)公司上海至武漢航線500kg以上貨物2.6元/kg價格，公路運(yùn)輸速度取高速公路運(yùn)輸最高與最低限速平均值。

表1 六個疫情需求點(diǎn)的基本情況(單位：例)

表2 集散中心各階段應(yīng)急物資供給量

表3 疫情需求點(diǎn)各階段應(yīng)急物資需求量

3.3.2 算例結(jié)果分析

通過MATLAB編程實(shí)現(xiàn)，對比DCWPSO算法和遺傳算法驗(yàn)證本算法有效性，μ1、μ2、μ3設(shè)置為0.4,0.4,0.2,此權(quán)重考慮了弱經(jīng)濟(jì)性。由于篇幅有限，各周期集散點(diǎn)至配送點(diǎn)和配送點(diǎn)至需求點(diǎn)運(yùn)送物資數(shù)量不做詳細(xì)陳述，僅選取第五周期物資最優(yōu)調(diào)配方案如表4,表5。

表4 第五周期物資最優(yōu)調(diào)配方案(第一階段)

表5 第五周期物資最優(yōu)調(diào)配方案(第二階段)

圖5 [0.4,0.4,0.2]權(quán)重下適應(yīng)度函數(shù)曲線圖

圖6 [0.6,0.3,0.1]權(quán)重下適應(yīng)度函數(shù)曲線圖

圖7 [0.2,0.6,0.2]權(quán)重下適應(yīng)度函數(shù)曲線圖

圖8 [0.2,0.2,0.6]權(quán)重下適應(yīng)度函數(shù)曲線圖

上四圖為不同權(quán)重組合下三種算法適應(yīng)度函數(shù)曲線對比圖。從圖中可看出運(yùn)輸成本占函數(shù)值比重較大，函數(shù)曲線在迭代初期波動較大，隨著迭代次數(shù)增大，曲線趨于平緩。從圖中可看出本文所提算法適應(yīng)度函數(shù)值最低，可見本文提出的算法更能有效求解所提出的問題。在本算法迭代過程中，從曲線傾斜程度可看出，初期函數(shù)值變化幅度較大，算法收斂效率較高。

4 結(jié)論

在新冠肺炎疫情這一突發(fā)事件背景下，本文構(gòu)建包含多集散、配送、需求中心，多周期、物資品種、運(yùn)輸方式的動態(tài)兩階段多目標(biāo)應(yīng)急物資調(diào)度網(wǎng)絡(luò)模型并設(shè)計VDCWPSO算法來求解模型。通過求解分析，可得到以下結(jié)論：

(1)應(yīng)急物資跨區(qū)域調(diào)度過程中，運(yùn)輸成本占成本比例較大，采用多式聯(lián)運(yùn)方式既可以柔性滿足時間窗要求又有效減少運(yùn)輸成本。

(2)本文在DCWPSO算法基礎(chǔ)上對每代最優(yōu)粒子引入三種變異操作，并將本算法與GA、DCWPSO算法以四組不同權(quán)重值組合為參照進(jìn)行實(shí)驗(yàn)，驗(yàn)證所提算法的有效性與實(shí)用性，可為此類應(yīng)急物資調(diào)度問題提供實(shí)際決策支持。

(3)經(jīng)濟(jì)、時效、公平作為三個具有悖反關(guān)系的指標(biāo)，難以兼顧且均需考慮完全，決策者可根據(jù)目標(biāo)側(cè)重關(guān)系決定權(quán)重，實(shí)驗(yàn)驗(yàn)證不同權(quán)重組合均不影響本算法相對更優(yōu)的計算結(jié)果。

本文所構(gòu)建的模型尚未考慮實(shí)際交通流、供需量不確定因素，因此帶有不確定因素的多元應(yīng)急物資調(diào)度問題有待未來進(jìn)一步深入研究。