考慮優(yōu)先級(jí)和時(shí)間窗約束的應(yīng)急物資調(diào)配模型

王慧麗, 喬詠藝

(西安財(cái)經(jīng)大學(xué)統(tǒng)計(jì)學(xué)院, 西安 710100)

近年來(lái),中外突發(fā)公共衛(wèi)生事件頻發(fā),2009年的H1N1流感全球確診約6×107例,死亡病例約3×105例;2014年的埃博拉疫情全球確診近19 031例,死亡病例超7 373例;2019年的新冠肺炎疫情,全球死亡病例超6.5×106例,全球經(jīng)濟(jì)和人民的健康受到很大威脅。突發(fā)公共衛(wèi)生事件爆發(fā)快、預(yù)測(cè)難,因此疫情大規(guī)模爆發(fā)時(shí),各國(guó)常采取切斷傳染源的方法,對(duì)中高風(fēng)險(xiǎn)區(qū)采取封閉式管理,應(yīng)急物資的儲(chǔ)備和調(diào)運(yùn)成為關(guān)系民生的首要問(wèn)題。統(tǒng)計(jì)數(shù)據(jù)[1]表明,生活物資配送選址以及路徑規(guī)劃的研究是應(yīng)對(duì)突發(fā)公共衛(wèi)生事件的關(guān)鍵。

目前,針對(duì)應(yīng)急選址模型的構(gòu)建,學(xué)者們從經(jīng)濟(jì)、環(huán)境、距離等方面考慮。席月等[2]構(gòu)建考慮自然因素、環(huán)境因素、風(fēng)險(xiǎn)因素、社會(huì)因素和經(jīng)濟(jì)因素的準(zhǔn)則層確定南京市應(yīng)急物資儲(chǔ)備庫(kù)建設(shè)區(qū)域。鄭夏等[3]以物資儲(chǔ)備中心與需求點(diǎn)距離最短、物資損失量最小作為目標(biāo)構(gòu)建選址優(yōu)化模型。馮瑛杰等[4]構(gòu)建考慮時(shí)間、成本和需求滿意度的應(yīng)急物流設(shè)施選址模型。針對(duì)物資配送路徑模型的構(gòu)建,普通物流考慮的首要目標(biāo)是配送成本,而配送時(shí)間則是應(yīng)急物資配送路徑規(guī)劃首要考慮的問(wèn)題之一。此外,結(jié)合公平性,要根據(jù)需求程度確定配送的優(yōu)先等級(jí)和時(shí)間窗約束。韓孟宜等[5]針對(duì)公共衛(wèi)生事件應(yīng)急物流所體現(xiàn)的弱經(jīng)濟(jì)性、時(shí)間約束的緊迫性等特點(diǎn)構(gòu)建路徑規(guī)劃模型,獲得最優(yōu)物資配送方案。曲沖沖等[6]考慮時(shí)效性和分配公平性建立應(yīng)急物資配送模型。陳剛等[7]以需求滿足率最小、送達(dá)時(shí)間最短體現(xiàn)物資配送的公平與效率。Ahmad等[8]構(gòu)造考慮優(yōu)先級(jí)的醫(yī)療物資配送單目標(biāo)混合整數(shù)規(guī)劃模型?，F(xiàn)有研究多從時(shí)間、公平、成本等方面考慮構(gòu)建模型的因素,但未考慮其中特殊事件的突發(fā)性特征。

在對(duì)選址模型的求解過(guò)程中,李帥等[9]利用層次分析法,使層次總排序最高的方案作為應(yīng)急預(yù)案?jìng)溥x目標(biāo)地。但層次分析法計(jì)算繁瑣、主觀性較強(qiáng),于是諸多學(xué)者利用相關(guān)數(shù)學(xué)算法和啟發(fā)式算法對(duì)選址問(wèn)題研究,朱莉等[10]應(yīng)用遺傳算法求解考慮區(qū)域異質(zhì)性的應(yīng)急物資選址模型。魯玲嵐等[11]利用改進(jìn)的K-means三維聚類算法優(yōu)化配送站點(diǎn)的選址方案。此外,引力模型[12]、粒子群算法[13]等也用來(lái)求解選址問(wèn)題。在對(duì)路徑規(guī)劃模型的求解中,求解方法主要集中于數(shù)學(xué)算法、啟發(fā)式算法,并不斷實(shí)驗(yàn)得到最優(yōu)解的過(guò)程。Zhu等[14]設(shè)計(jì)蟻群優(yōu)化算法求解最優(yōu)配送路徑。張凱月等[15]利用頭腦風(fēng)暴算法求解應(yīng)急物資車輛調(diào)度模型。劉長(zhǎng)石等[16]設(shè)計(jì)一種自適應(yīng)遺傳算法求解符合目標(biāo)的路徑規(guī)劃方案。王英輝等[17]通過(guò)具有君主方案的遺傳算法對(duì)應(yīng)急物流路徑進(jìn)行優(yōu)化。此外,求解物資配送選址-路徑規(guī)劃模型時(shí),通常利用混合算法提高精確度。

綜上可知,應(yīng)急物資配送選址-路徑規(guī)劃問(wèn)題已有大量研究,但現(xiàn)有研究主要集中于應(yīng)急物資大型儲(chǔ)備點(diǎn)選址的研究,小型物資配送站點(diǎn)的選址問(wèn)題研究較少;配送路徑規(guī)劃方面未從物資的需求程度以及公共衛(wèi)生事件的特殊性方面計(jì)算優(yōu)先級(jí)系數(shù),并且僅考慮固定的時(shí)間窗約束。為此,在現(xiàn)有研究的基礎(chǔ)上,研究突發(fā)性公共衛(wèi)生事件中小型物資配送中轉(zhuǎn)站的選址問(wèn)題;計(jì)算優(yōu)先級(jí)系數(shù)時(shí)考慮物資需求量及特殊事件的發(fā)生;將優(yōu)先級(jí)系數(shù)和配送時(shí)間窗結(jié)合,構(gòu)建更精確的物資配送時(shí)間窗約束,為政府或相關(guān)應(yīng)急管理部門在制定應(yīng)急處置方案時(shí)提供借鑒和參考。

1 構(gòu)建生活物資配送中轉(zhuǎn)站的選址模型

考慮城市居民小區(qū)的居家隔離人員,由于小區(qū)分布具有聚集性,將位置在一定范圍內(nèi)的小區(qū)規(guī)劃為一個(gè)需求站點(diǎn),以達(dá)到物資調(diào)運(yùn)的高速運(yùn)轉(zhuǎn)。利用K-means聚類算法計(jì)算配送中轉(zhuǎn)站的選址地點(diǎn),K-means聚類算法是一種通過(guò)比較相似性來(lái)進(jìn)行聚類的無(wú)監(jiān)督方法,常用于選址中對(duì)區(qū)域的劃分。利用K-means聚類算法的最小距離分配原則,首先假設(shè)k個(gè)初始聚類中心W1,W2,…,Wk;然后逐個(gè)將各個(gè)樣本按最小距離原則分配給k個(gè)聚類中心的某個(gè)Wl(l=1,2,…,k);此時(shí)計(jì)算新的聚類中心W′l,若W′l≠Wl,則不停迭代直到聚類中心不再發(fā)生變化;否則算法收斂,計(jì)算結(jié)束;最后通過(guò)平均輪廓系數(shù)比較不同聚類方案的效果,選擇聚類效果較好且符合模型假設(shè)的方案作為最終選址結(jié)果,輪廓系數(shù)的計(jì)算公式為

(1)

(2)

式中:Pi為樣本i的輪廓系數(shù),Pi∈[-1,1],越趨近于1代表聚類效果越好;ai為樣本i到同一簇內(nèi)其他點(diǎn)的平均距離;bi為樣本i到其他簇內(nèi)點(diǎn)平均距離的最小值;Pk為各方案的平均輪廓系數(shù)。

2 構(gòu)建生活物資配送路徑規(guī)劃模型

突發(fā)公共衛(wèi)生事件爆發(fā)初期,應(yīng)急物資分配在追求效率的同時(shí)要兼顧“精準(zhǔn)防控”的公平性。因此研究從配送中心到需求站點(diǎn)的最佳物資配送方案,計(jì)算優(yōu)先級(jí)系數(shù)時(shí)考慮物資需求量和特殊事件的發(fā)生,并將優(yōu)先級(jí)系數(shù)與配送中心設(shè)定的時(shí)間窗結(jié)合,求得更公平的時(shí)間窗約束,構(gòu)建兼顧效率和公平的生活物資配送路徑規(guī)劃模型。

2.1 時(shí)間窗約束和優(yōu)先級(jí)計(jì)算

2.1.1 時(shí)間窗約束

時(shí)間窗指一個(gè)時(shí)間段,時(shí)間窗約束指在路徑規(guī)劃時(shí)配送車輛應(yīng)在時(shí)間窗范圍內(nèi)將物資送達(dá),未按時(shí)送達(dá)則根據(jù)違反時(shí)間窗的長(zhǎng)短接受相應(yīng)的懲罰函數(shù)。將配送中心設(shè)置的時(shí)間窗與各需求站點(diǎn)的優(yōu)先級(jí)系數(shù)結(jié)合,優(yōu)先級(jí)系數(shù)越大,配送時(shí)間窗越短,反之則越長(zhǎng),即高優(yōu)先級(jí)的需求站點(diǎn)得到最佳的配送時(shí)間,由此可求得更精確的時(shí)間窗[Ej,Lj]為

Ej=E′j(1-Uj)

(3)

Lj=L′j(1-Uj)

(4)

式中:E′j、L′j分別為配送中心指定的配送左時(shí)間窗與右時(shí)間窗;Uj為各需求站點(diǎn)的優(yōu)先級(jí)系數(shù)。

2.1.2 優(yōu)先級(jí)系數(shù)計(jì)算

突發(fā)性公共衛(wèi)生事件爆發(fā)初期,生活物資的配送中往往有供應(yīng)不足、服務(wù)人員少等問(wèn)題,而生活物資配送具有緊急性,在運(yùn)輸上具有更高的要求。因此,在物資有限的約束下,計(jì)算每個(gè)需求站點(diǎn)的優(yōu)先級(jí)系數(shù),保證物資配送的公平性,有利于提高生活物資的配送效率。

優(yōu)先級(jí)系數(shù)計(jì)算有多種方法,熵權(quán)法具有指標(biāo)權(quán)重不受主觀因素影響的優(yōu)點(diǎn),使結(jié)果更客觀、準(zhǔn)確和科學(xué),因此采用熵權(quán)法計(jì)算各需求站點(diǎn)生活物資配送的優(yōu)先級(jí)系數(shù)?？紤]在突發(fā)性公共衛(wèi)生事件背景下特殊事件的發(fā)生,構(gòu)建小區(qū)戶數(shù)(單位:戶)、小區(qū)人口數(shù)(單位:人)、物資需求量(單位:kg)、特殊事件個(gè)數(shù)(指定隨機(jī)數(shù))作為生活物資優(yōu)先級(jí)綜合評(píng)價(jià)指標(biāo)體系。設(shè)指標(biāo)體系中有a個(gè)評(píng)價(jià)對(duì)象,有b個(gè)評(píng)價(jià)指標(biāo),則第j個(gè)評(píng)價(jià)對(duì)象的優(yōu)先級(jí)系數(shù)為

(5)

(6)

式(6)中:Xij為第j個(gè)評(píng)價(jià)對(duì)象的第i個(gè)評(píng)價(jià)指標(biāo)的值;maxXij、minXij分別為指標(biāo)原始數(shù)據(jù)的最大值和最小值。

2.2 配送路徑規(guī)劃模型

在構(gòu)建生活物資配送路徑規(guī)劃模型時(shí),首先考慮如下假設(shè):①假設(shè)配送中心的生活物資數(shù)量足以滿足各需求站點(diǎn)的需求;②假設(shè)所有配送車輛的性能完全相同,只考慮容量約束,不考慮其他特殊情況的發(fā)生;③假設(shè)每個(gè)需求站點(diǎn)的物資需求量不大于運(yùn)輸車輛的容量約束,每個(gè)需求站點(diǎn)只能被一輛車服務(wù);④假設(shè)所有配送車輛以配送中心為起點(diǎn),且完成配送任務(wù)后需返回配送點(diǎn)。

基于上述假設(shè),構(gòu)建生活物資路徑規(guī)劃模型,根據(jù)公平和效率原則,要求配送車輛的行駛距離最小、違反車輛容量約束的懲罰成本最小、違反時(shí)間窗約束的懲罰成本最小。為使此模型成立,還需要滿足以下約束條件:①每個(gè)需求站點(diǎn)都只被一輛車配送且只配送一次,每輛車從配送中心發(fā)出且完成任務(wù)后返回配送中心;②車輛到達(dá)需求站點(diǎn)j′的時(shí)間為到達(dá)上一個(gè)需求站點(diǎn)j的時(shí)間與車輛在站點(diǎn)j與j′路徑上行駛時(shí)間之和;③車輛從需求站點(diǎn)j行駛到j(luò)′的時(shí)間為站點(diǎn)之間的距離除以車輛的平均速度;④xjj′q、yjq為0-1變量。

設(shè)Sjj′為車輛從需求站點(diǎn)j行駛到j(luò)′的距離,V為車輛的平均行駛速度,Tj為車輛到達(dá)需求站點(diǎn)j的時(shí)間,Tjj′為車輛從需求站點(diǎn)j行駛到j(luò)′的時(shí)間,Q為運(yùn)載車輛的最大載重量,Qj為需求站點(diǎn)j的物資需求量,Ej為需求站點(diǎn)的左時(shí)間窗,Lj為需求站點(diǎn)的右時(shí)間窗。路徑規(guī)劃模型的表達(dá)式為

(7)

(8)

(9)

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

minZ=Z1+Z2+Z3

(10)

約束條件:

(11)

式中:α和β為常數(shù),分別表示違反車輛容量約束和時(shí)間窗約束的懲罰函數(shù)系數(shù);x0j′q為車輛q從配送中心行駛到需求站點(diǎn)j′;xj0q為車輛q從需求站點(diǎn)j行駛到配送中心;xjj′q、yjq為決策變量,可分別表示為

(12)

(13)

遺傳算法通過(guò)模擬生物進(jìn)化過(guò)程來(lái)隨機(jī)搜尋最優(yōu)解,充分利用了自然界優(yōu)勝略汰、適者生存的規(guī)律,遺傳算法與大鄰域搜索算法相結(jié)合,可以提高算法的局部搜索能力,優(yōu)化求解過(guò)程。采用混合遺傳算法求解配送路徑規(guī)劃模型,操作流程如圖1所示。

圖1 混合遺傳算法流程圖Fig.1 Flowchart of hybrid genetic algorithm

3 實(shí)證分析

選取長(zhǎng)春市朝陽(yáng)區(qū)2022年4月1日的突發(fā)公共衛(wèi)生情況作為案例背景,設(shè)置一處配送中心為長(zhǎng)春市朝陽(yáng)區(qū)200 個(gè)小區(qū)配送應(yīng)急物資,蔬菜為相應(yīng)的供應(yīng)物資。在該統(tǒng)計(jì)數(shù)據(jù)中,該市共有30 輛同規(guī)格的大卡車,車的最大載重量為10 t,平均車速為60 km/h,按每人每日對(duì)蔬菜的需求量為400 g計(jì)算各小區(qū)的蔬菜需求量,違反車輛容量約束的懲罰函數(shù)系數(shù)α=10,違反時(shí)間窗約束的懲罰函數(shù)系數(shù)β=100,配送中心設(shè)置的配送時(shí)間窗為[0,500]。相關(guān)實(shí)際數(shù)據(jù)來(lái)源于2022年中國(guó)研究生數(shù)學(xué)建模競(jìng)賽數(shù)據(jù)集、長(zhǎng)春市衛(wèi)生健康委員會(huì)網(wǎng)站、百度地圖等。

在選址模型中,選取(35,25)為中心,建立二維坐標(biāo)系,指定(50,40)為配送中心。將長(zhǎng)春市朝陽(yáng)區(qū)的200 個(gè)小區(qū)劃分為k個(gè)需求站點(diǎn),目的是使同一類的需求站點(diǎn)的地理位置相似程度高,不同類間的相似程度低,進(jìn)而加強(qiáng)物資運(yùn)輸?shù)男省８鶕?jù)選址模型及參數(shù)設(shè)置利用K-means聚類算法求解選址模型得到60 個(gè)需求站點(diǎn),如圖2所示。

0為物資配送中心;1～60為60個(gè)需求站點(diǎn)的位置

分別計(jì)算60個(gè)需求站點(diǎn)的優(yōu)先級(jí)系數(shù),利用熵權(quán)法計(jì)算各指標(biāo)權(quán)重,具體結(jié)果為:小區(qū)戶數(shù)0.128、小區(qū)人口數(shù)0.105、物資需求量0.104、特殊事件個(gè)數(shù)0.662。

在權(quán)重的基礎(chǔ)上,根據(jù)式(5)、式(6)計(jì)算各需求站點(diǎn)的優(yōu)先級(jí)系數(shù),得到結(jié)果如表1所示?？梢钥闯?各需求站點(diǎn)的優(yōu)先級(jí)系數(shù)因其指標(biāo)特點(diǎn)不同差別較大。例如站點(diǎn)48的人口數(shù)量多,所需物資數(shù)量大,并且有特殊事件的發(fā)生,所以其配送的優(yōu)先級(jí)系數(shù)最大,為0.904,而站點(diǎn)59人口數(shù)量少,且沒(méi)有特殊事件發(fā)生,所以其優(yōu)先級(jí)系數(shù)僅為0.014。

表1 各需求站點(diǎn)的優(yōu)先級(jí)系數(shù)Table 1 Priority factor for each demand site

為求得更精確的配送時(shí)間窗,將配送中心設(shè)置的時(shí)間窗[0,500]與優(yōu)先級(jí)系數(shù)Uj結(jié)合,各需求站點(diǎn)的配送時(shí)間窗為[Ej,Lj]=[0,500×(1-Uj)]。

在路徑規(guī)劃模型建立基礎(chǔ)上,利用混合遺傳算法求解路徑規(guī)劃模型,在MATLAB軟件迭代100次,最終得到26 個(gè)最優(yōu)解,3個(gè)目標(biāo)最后趨于平穩(wěn),說(shuō)明收斂完成。最優(yōu)配送結(jié)果為:使用26 輛車對(duì)60 個(gè)需求站點(diǎn)配送生活物資,未違反時(shí)間窗與車輛容量約束。計(jì)算得到的最優(yōu)配送路線如表2所示。

表2 最優(yōu)配送路線Table 2 Optimal delivery routes

從表2可以看出,每個(gè)需求站點(diǎn)只被一輛車服務(wù),且車輛從配送中心出發(fā),完成任務(wù)后再返回配送中心。將上述配送路徑按照所配送的需求站點(diǎn)數(shù)量分為4類,具體如下。

(1)類型1。配送路徑中包括1個(gè)需求站點(diǎn)的路線,路徑2、19、20、22、23、25、26,此類配送路徑中需求站點(diǎn)的人口基數(shù)大、生活物資需求量大,并且站點(diǎn)可能有特殊事件發(fā)生,優(yōu)先級(jí)系數(shù)高,導(dǎo)致配送時(shí)間窗短,在不違反載容量和時(shí)間窗約束的條件下只能選取一輛車配送物資。

(2)類型2。配送路徑中包括2個(gè)需求站點(diǎn)的路線,路徑1、8、9、12、17、18、21,此類配送路徑中需求站點(diǎn)的人口基數(shù)大或配送時(shí)間窗短,由于約束條件,車輛不能對(duì)多個(gè)站點(diǎn)配送物資。

(3)類型3。配送路徑中包括3個(gè)需求站點(diǎn)的路線,路徑4、5、6、10、13、14、15、16、24,此類路徑中需求站點(diǎn)人口數(shù)量少,但優(yōu)先級(jí)系數(shù)差別較大,車輛首先對(duì)優(yōu)先級(jí)系數(shù)大的站點(diǎn)配送物資,之后再滿足其他站點(diǎn)的物資需求。

(4)類型4。配送路徑中包括4個(gè)需求站點(diǎn)的路線,路徑3、7、11,此類路徑包含的人口數(shù)量少,需要的生活物資少,并且需求站點(diǎn)的優(yōu)先級(jí)系數(shù)低,也沒(méi)有嚴(yán)格的時(shí)間窗約束,車輛在一條路徑中可為多個(gè)需求站點(diǎn)配送物資。

總之,不同需求站點(diǎn)的特點(diǎn)不同,所需要的配送時(shí)間窗也不同,此物資配送路徑模型在不違反車輛容量約束的同時(shí),既提升了配送效率,又考慮到個(gè)別需求站點(diǎn)的需求緊急性。

為了進(jìn)一步明確配送方案,具體的配送路徑如圖3所示。

不同顏色線條表示不同類型的配送路徑,紅色路徑表示類型1; 紫色路徑表示類型2;綠色路徑表示類型3;黑色路徑表示類型4

圖3中不同顏色表示不同類型的配送路徑。紅色路徑表示類型1,如0→48→0,需求站點(diǎn)48的人口數(shù)量大,相應(yīng)生活物資需求量也很大,并且此點(diǎn)有特殊事件發(fā)生,對(duì)應(yīng)的優(yōu)先級(jí)系數(shù)為0.904,非常高,即配送時(shí)間窗很短,需要一輛車單獨(dú)配送物資;紫色路徑表示類型2,如0→44→51→0,需求站點(diǎn)44、51的人口數(shù)量較大,其優(yōu)先級(jí)系數(shù)分別為0.211、0.163,配送時(shí)間窗較短,車輛只能為兩個(gè)站點(diǎn)配送物資;綠色路徑表示類型3,如0→8→56→21→0,此3個(gè)需求站點(diǎn)的人口數(shù)量較少,優(yōu)先級(jí)系數(shù)分別為0.766、0.739、0.168,差別較大,車輛先為站點(diǎn)8、56配送,最后為站點(diǎn)21配送物資;黑色路徑表示類型4,如0→5→10→18→59→0,此4個(gè)需求站點(diǎn)的人口數(shù)量少,優(yōu)先級(jí)系數(shù)為0.339、0.163、0.074、0.014,都較低,配送時(shí)間窗長(zhǎng),此路徑中的車輛可對(duì)多個(gè)需求站點(diǎn)配送物資。由此,該模型在實(shí)際應(yīng)用中不違反車輛容量約束,同時(shí)考慮效率與公平目標(biāo),模型是有效的。

4 結(jié)論

從效率和公平兩個(gè)視角,考慮優(yōu)先級(jí)和時(shí)間窗約束,建立物資配送的選址和路徑規(guī)劃模型,得出如下結(jié)論。

(1)建立物資配送選址模型,采用K-means聚類算法,對(duì)長(zhǎng)春市朝陽(yáng)區(qū)200個(gè)小區(qū)進(jìn)行劃分,計(jì)算所得的60個(gè)需求站點(diǎn)以物資配送中心呈空間網(wǎng)狀分布。

(2)結(jié)合優(yōu)先級(jí)和時(shí)間窗的約束,構(gòu)建了綜合評(píng)價(jià)指標(biāo)體系,不同需求站點(diǎn)優(yōu)先級(jí)的計(jì)算結(jié)果表明,人口數(shù)量越大,所需物資量越大,優(yōu)先級(jí)越高。

(3)考慮優(yōu)先級(jí)與時(shí)間窗約束,建立物資配送路徑規(guī)劃模型,根據(jù)配送路徑中所包含的需求站點(diǎn)數(shù)量不同,將其分成4類不同的配送路徑,使用26輛車可實(shí)現(xiàn)對(duì)長(zhǎng)春市朝陽(yáng)區(qū)60個(gè)需求站點(diǎn)的物資配送。

在構(gòu)建物資配送模型時(shí),改進(jìn)了優(yōu)先級(jí)和時(shí)間窗的計(jì)算,為應(yīng)急物資的配送提供新思路。未來(lái)在對(duì)應(yīng)急物資的配送路徑進(jìn)行規(guī)劃時(shí),也可考慮優(yōu)先級(jí)與時(shí)間窗約束,在本文方法上進(jìn)一步拓展。此外,在物資需求量有限的假設(shè)下建立模型,若需求點(diǎn)的物資需求量大于運(yùn)輸車輛的容量約束,則要考慮多階段的物資分配模型,進(jìn)一步深入研究。