考慮優先級和時間窗約束的應急物資調配模型

王慧麗, 喬詠藝

(西安財經大學統計學院, 西安 710100)

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

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

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

綜上可知,應急物資配送選址-路徑規劃問題已有大量研究,但現有研究主要集中于應急物資大型儲備點選址的研究,小型物資配送站點的選址問題研究較少;配送路徑規劃方面未從物資的需求程度以及公共衛生事件的特殊性方面計算優先級系數,并且僅考慮固定的時間窗約束。為此,在現有研究的基礎上,研究突發性公共衛生事件中小型物資配送中轉站的選址問題;計算優先級系數時考慮物資需求量及特殊事件的發生;將優先級系數和配送時間窗結合,構建更精確的物資配送時間窗約束,為政府或相關應急管理部門在制定應急處置方案時提供借鑒和參考。

1 構建生活物資配送中轉站的選址模型

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

(1)

(2)

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

2 構建生活物資配送路徑規劃模型

突發公共衛生事件爆發初期,應急物資分配在追求效率的同時要兼顧“精準防控”的公平性。因此研究從配送中心到需求站點的最佳物資配送方案,計算優先級系數時考慮物資需求量和特殊事件的發生,并將優先級系數與配送中心設定的時間窗結合,求得更公平的時間窗約束,構建兼顧效率和公平的生活物資配送路徑規劃模型。

2.1 時間窗約束和優先級計算

2.1.1 時間窗約束

時間窗指一個時間段,時間窗約束指在路徑規劃時配送車輛應在時間窗范圍內將物資送達,未按時送達則根據違反時間窗的長短接受相應的懲罰函數。將配送中心設置的時間窗與各需求站點的優先級系數結合,優先級系數越大,配送時間窗越短,反之則越長,即高優先級的需求站點得到最佳的配送時間,由此可求得更精確的時間窗[Ej,Lj]為

Ej=E′j(1-Uj)

(3)

Lj=L′j(1-Uj)

(4)

式中:E′j、L′j分別為配送中心指定的配送左時間窗與右時間窗;Uj為各需求站點的優先級系數。

2.1.2 優先級系數計算

突發性公共衛生事件爆發初期,生活物資的配送中往往有供應不足、服務人員少等問題,而生活物資配送具有緊急性,在運輸上具有更高的要求。因此,在物資有限的約束下,計算每個需求站點的優先級系數,保證物資配送的公平性,有利于提高生活物資的配送效率。

優先級系數計算有多種方法,熵權法具有指標權重不受主觀因素影響的優點,使結果更客觀、準確和科學,因此采用熵權法計算各需求站點生活物資配送的優先級系數。考慮在突發性公共衛生事件背景下特殊事件的發生,構建小區戶數(單位:戶)、小區人口數(單位:人)、物資需求量(單位:kg)、特殊事件個數(指定隨機數)作為生活物資優先級綜合評價指標體系。設指標體系中有a個評價對象,有b個評價指標,則第j個評價對象的優先級系數為

(5)

(6)

式(6)中:Xij為第j個評價對象的第i個評價指標的值;maxXij、minXij分別為指標原始數據的最大值和最小值。

2.2 配送路徑規劃模型

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

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

設Sjj′為車輛從需求站點j行駛到j′的距離,V為車輛的平均行駛速度,Tj為車輛到達需求站點j的時間,Tjj′為車輛從需求站點j行駛到j′的時間,Q為運載車輛的最大載重量,Qj為需求站點j的物資需求量,Ej為需求站點的左時間窗,Lj為需求站點的右時間窗。路徑規劃模型的表達式為

(7)

(8)

(9)

目標函數為

minZ=Z1+Z2+Z3

(10)

約束條件:

(11)

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

(12)

(13)

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

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

3 實證分析

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

在選址模型中,選取(35,25)為中心,建立二維坐標系,指定(50,40)為配送中心。將長春市朝陽區的200 個小區劃分為k個需求站點,目的是使同一類的需求站點的地理位置相似程度高,不同類間的相似程度低,進而加強物資運輸的效率。根據選址模型及參數設置利用K-means聚類算法求解選址模型得到60 個需求站點,如圖2所示。

0為物資配送中心;1～60為60個需求站點的位置

分別計算60個需求站點的優先級系數,利用熵權法計算各指標權重,具體結果為:小區戶數0.128、小區人口數0.105、物資需求量0.104、特殊事件個數0.662。

在權重的基礎上,根據式(5)、式(6)計算各需求站點的優先級系數,得到結果如表1所示。可以看出,各需求站點的優先級系數因其指標特點不同差別較大。例如站點48的人口數量多,所需物資數量大,并且有特殊事件的發生,所以其配送的優先級系數最大,為0.904,而站點59人口數量少,且沒有特殊事件發生,所以其優先級系數僅為0.014。

表1 各需求站點的優先級系數Table 1 Priority factor for each demand site

為求得更精確的配送時間窗,將配送中心設置的時間窗[0,500]與優先級系數Uj結合,各需求站點的配送時間窗為[Ej,Lj]=[0,500×(1-Uj)]。

在路徑規劃模型建立基礎上,利用混合遺傳算法求解路徑規劃模型,在MATLAB軟件迭代100次,最終得到26 個最優解,3個目標最后趨于平穩,說明收斂完成。最優配送結果為:使用26 輛車對60 個需求站點配送生活物資,未違反時間窗與車輛容量約束。計算得到的最優配送路線如表2所示。

表2 最優配送路線Table 2 Optimal delivery routes

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

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

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

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

(4)類型4。配送路徑中包括4個需求站點的路線,路徑3、7、11,此類路徑包含的人口數量少,需要的生活物資少,并且需求站點的優先級系數低,也沒有嚴格的時間窗約束,車輛在一條路徑中可為多個需求站點配送物資。

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

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

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

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

4 結論

從效率和公平兩個視角,考慮優先級和時間窗約束,建立物資配送的選址和路徑規劃模型,得出如下結論。

(1)建立物資配送選址模型,采用K-means聚類算法,對長春市朝陽區200個小區進行劃分,計算所得的60個需求站點以物資配送中心呈空間網狀分布。

(2)結合優先級和時間窗的約束,構建了綜合評價指標體系,不同需求站點優先級的計算結果表明,人口數量越大,所需物資量越大,優先級越高。

(3)考慮優先級與時間窗約束,建立物資配送路徑規劃模型,根據配送路徑中所包含的需求站點數量不同,將其分成4類不同的配送路徑,使用26輛車可實現對長春市朝陽區60個需求站點的物資配送。

在構建物資配送模型時,改進了優先級和時間窗的計算,為應急物資的配送提供新思路。未來在對應急物資的配送路徑進行規劃時,也可考慮優先級與時間窗約束,在本文方法上進一步拓展。此外,在物資需求量有限的假設下建立模型,若需求點的物資需求量大于運輸車輛的容量約束,則要考慮多階段的物資分配模型,進一步深入研究。