突發(fā)事件下多品種應(yīng)急物資調(diào)度優(yōu)化模型

李 然，葉曉飛，洪 鋼，楊 俊，鄭彭軍

（1.寧波大學(xué) 海運(yùn)學(xué)院，浙江 寧波 315211；2.寧波中通物流集團(tuán)有限公司，浙江 寧波 315000）

0 引言

近年來，各種自然災(zāi)害、重大事故以及公共衛(wèi)生事件在不同程度上影響著人們的生活，不僅造成了巨大的財(cái)產(chǎn)損失和人員傷害，也對(duì)人們的經(jīng)濟(jì)狀況和心理健康有一定的影響。尤其是2019年12月爆發(fā)的新冠病毒疫情，給人民身體健康和社會(huì)經(jīng)濟(jì)造成了很大的影響和損失，對(duì)突發(fā)情況下應(yīng)急物資的配送需求與日俱增。表1對(duì)近十年突發(fā)的重大疫情進(jìn)行了總結(jié)，圖1 分析了近十年我國重大災(zāi)害受災(zāi)人口和經(jīng)濟(jì)損失。

圖1 近十年我國重大災(zāi)害受災(zāi)人口和經(jīng)濟(jì)損失統(tǒng)計(jì)

表1 近十年突發(fā)的重大疫情情況

災(zāi)情突然出現(xiàn)時(shí)，在緊急物資數(shù)量有限的前提下，如何對(duì)各緊急物資需求中心及時(shí)做好物品的最優(yōu)配置，并使物流質(zhì)量最優(yōu)化，即災(zāi)區(qū)經(jīng)濟(jì)損失最少的同時(shí)物流配送質(zhì)量也最大，是當(dāng)前應(yīng)急配送面臨的重大難題。在資源有限的情況下，按需求程度快速合理的將應(yīng)急物資分發(fā)到受災(zāi)點(diǎn)至關(guān)重要。因此，國內(nèi)外專家針對(duì)應(yīng)急物資的配送問題展開了一系列研究。Zhou，等[1]建立了多周期動(dòng)態(tài)問題的多目標(biāo)優(yōu)化模型。Ding，等[2]考慮到應(yīng)急時(shí)間和信息不確定性等因素，引入灰色變量建立了應(yīng)急后勤調(diào)度問題的灰色多目標(biāo)規(guī)劃模型。Sun，等[3]運(yùn)用累積前景理論建立了多策略集進(jìn)化博弈模型。Huang，等[4]考慮到需求和事件的不確定性，在建立應(yīng)急物流配送路徑模型時(shí)引入了不確定性理論，采用專家估計(jì)的方法解決了優(yōu)化中的不確定問題。以上研究考慮了道路運(yùn)輸過程中的需求不確定性，但由于現(xiàn)實(shí)生活中的復(fù)雜路網(wǎng)以及突發(fā)狀況，需要將交通條件的不確定性以及應(yīng)急事件的緊迫性考慮在內(nèi)，針對(duì)這一考慮因素，Sakurab，等[5]在建立模型時(shí)，考慮了道路網(wǎng)絡(luò)的可達(dá)性和救災(zāi)人員調(diào)度問題；Zhang，等[6]對(duì)緊急糧食分配車輛進(jìn)行了研究和分析。Sun，等[7]考慮了車流量對(duì)調(diào)度的影響，使用云模型來處理不確定的交通狀況。閆森，等[8]建立雙目標(biāo)模型，旨在提高地震發(fā)生時(shí)的應(yīng)急物資配送效率，降低人員傷亡與經(jīng)濟(jì)損失?？紤]到應(yīng)急物資配送過程中時(shí)間的緊迫性，尤其是針對(duì)醫(yī)療和冷鏈物資，Guan，等[9]建立了針對(duì)多需求中心、軟時(shí)間窗下冷鏈應(yīng)急物資的配送路徑優(yōu)化問題。Qi，等[10]構(gòu)建了貨物配送過程中緊急冷鏈物流調(diào)度的數(shù)學(xué)模型；楊菊花，等[11]在建模過程中引入了時(shí)間緊迫系數(shù)。陳勇，等[12]對(duì)突發(fā)疫情下的疫苗冷鏈配送進(jìn)行研究，以此實(shí)現(xiàn)應(yīng)急配送系統(tǒng)的最優(yōu)化調(diào)度。除此之外，需要針對(duì)不同的災(zāi)害類型、不同的物資種類、不同的運(yùn)輸方式考慮不同的影響因素進(jìn)行應(yīng)急物資路徑優(yōu)化，針對(duì)不同的場景，設(shè)定合適的目標(biāo)函數(shù)建立模型，并選擇合適的求解方式。趙建有，等[13]對(duì)各受災(zāi)點(diǎn)物資需求緊迫度進(jìn)行量化，采用K-means聚類算法進(jìn)行應(yīng)急物資配送中心的選擇和需求點(diǎn)的應(yīng)急程度劃分。賀錦[14]在考慮需求緊迫度的基礎(chǔ)上，構(gòu)建了確定條件下的應(yīng)急醫(yī)療物資調(diào)配模型，模型考慮了多配送中心、多需求點(diǎn)、多種物資、多階段的應(yīng)急物資調(diào)配，并設(shè)計(jì)了求解算法，最后以武漢市新冠疫情應(yīng)急醫(yī)療物資調(diào)配為例，驗(yàn)證了模型的有效性。

本文針對(duì)疫情下多種物資的配送問題展開研究，考慮了多種物資配送以及時(shí)間緊迫性，以總時(shí)間最短和總成本最低為目標(biāo)函數(shù)建立了路徑優(yōu)化模型，解決了應(yīng)急配送中多種物資的配送問題，運(yùn)用NSGA-Ⅱ算法進(jìn)行求解，與傳統(tǒng)的遺傳算法進(jìn)行比較，驗(yàn)證了該算法的優(yōu)越性。并以2020年寧波市北侖區(qū)疫情下的物資配送為例進(jìn)行案例分析，驗(yàn)證了算法和模型的可行性。

1 問題描述及假設(shè)

1.1 問題描述

在應(yīng)急物資的配送過程中，由于實(shí)際過程中的影響因素和不確定因素較多，在路徑優(yōu)化過程中很難考慮周到，所以要根據(jù)不同的災(zāi)害，找到最合適的影響因素。本文主要針對(duì)多個(gè)配送中心和多個(gè)受災(zāi)點(diǎn)的物流網(wǎng)絡(luò)進(jìn)行研究。當(dāng)重大災(zāi)害發(fā)生后，形成多供應(yīng)點(diǎn)和多需求點(diǎn)的應(yīng)急物流網(wǎng)絡(luò)，配送車輛需要在規(guī)定時(shí)間內(nèi)將應(yīng)急物資從配送中心i送到需求點(diǎn)j。應(yīng)急物流網(wǎng)絡(luò)為G=(M,L)，如圖2所示，M表示物流網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)子集的集合，包含I個(gè)配送中心與J個(gè)受災(zāi)點(diǎn)共W個(gè)節(jié)點(diǎn)，L表示應(yīng)急物流網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間的可選路徑，cij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離，xijv表示車輛v將物資從點(diǎn)i運(yùn)送到點(diǎn)j，根據(jù)三角定理，對(duì)于任意的i,j,v,xijv≤xiav+xajv，其中a為其他節(jié)點(diǎn)，因此這個(gè)不等式表示在物流網(wǎng)絡(luò)中任意兩點(diǎn)的距離小于從一點(diǎn)繞行另一點(diǎn)再到目的地的距離。

圖2 應(yīng)急物流網(wǎng)絡(luò)

本文對(duì)突發(fā)事件下醫(yī)療物資和民用物資兩種物資進(jìn)行有效配送，因此，需要在已知受災(zāi)點(diǎn)需求量或需求區(qū)間的基礎(chǔ)上，選擇合適的車輛，將兩種物資從配送中心運(yùn)送到需求區(qū)，并使配送過程中的運(yùn)輸時(shí)間和成本達(dá)到最小。配送結(jié)束后，車輛需要返回配送中心進(jìn)行新的配送任務(wù)，因此在設(shè)計(jì)配送路線時(shí)，盡可能調(diào)整車輛的載貨量，使之接近所經(jīng)過受災(zāi)點(diǎn)的物資需求量總和，減少運(yùn)輸過程中的車輛成本。

1.2 模型假設(shè)

對(duì)于重大災(zāi)害，車輛調(diào)度優(yōu)化模型的建立還需要考慮從多個(gè)車場調(diào)用車輛，從多個(gè)儲(chǔ)備庫調(diào)用救助物資等因素。本文集中考慮多個(gè)物資配送中心、多個(gè)受災(zāi)物資需求點(diǎn)的情況，歸結(jié)為將物資從配送站點(diǎn)送達(dá)受災(zāi)需求點(diǎn)，并使總運(yùn)輸費(fèi)用和時(shí)間最小的車輛路徑優(yōu)化決策問題。為了簡化和準(zhǔn)確建立數(shù)學(xué)模型，做出如下幾項(xiàng)假設(shè)：

（1）車輛配送路網(wǎng)為完全網(wǎng)絡(luò)且無方向性；

（2）已知各受災(zāi)地點(diǎn)的位置信息和救災(zāi)物資種類，同時(shí)也知道配送中心的物資儲(chǔ)備量；

（3）受災(zāi)地點(diǎn)車輛的型號(hào)相同，且從供應(yīng)點(diǎn)到災(zāi)害點(diǎn)的所有運(yùn)輸車輛的平均速度為常數(shù)；

（4）調(diào)度中，道路持續(xù)可用，交通擁堵不變；

（5）每個(gè)需求點(diǎn)都能且智能被一輛車服務(wù)一次；

（6）配送中心目前無需考慮車輛的維護(hù)保養(yǎng)問題；

（7）受災(zāi)點(diǎn)及其配送路徑集合已知；

（8）除本文考慮的因素外，暫不受其他因素影響。

2 模型建立

應(yīng)急物流車輛路徑優(yōu)化模型主要由四部分組成，包括應(yīng)急物流車輛調(diào)度模型的符號(hào)定義、目標(biāo)函數(shù)、約束條件，以及對(duì)于該模型的說明。

2.1 多品種物資的分解

在救災(zāi)應(yīng)急物流中，一個(gè)受災(zāi)點(diǎn)需要多種救災(zāi)物資，且不同種類物資的時(shí)限要求不同，為了簡化模型結(jié)構(gòu)，將一個(gè)受災(zāi)點(diǎn)的多品種需求虛擬成多個(gè)受災(zāi)點(diǎn)的單品種需求，將其構(gòu)造成標(biāo)準(zhǔn)的問題，簡化模型結(jié)構(gòu)，便于求解。比如受災(zāi)點(diǎn)A,B,C有P種物資需求，見表2，則每個(gè)受災(zāi)點(diǎn)添加P-1 個(gè)虛擬點(diǎn)后擴(kuò)展為A1,A2,...,Ap;B1,B2,...,Bp;C1,C2,...,Cp，每個(gè)點(diǎn)僅有一種物資需求，而每個(gè)受災(zāi)點(diǎn)擴(kuò)展的虛擬點(diǎn)之間的距離為0。經(jīng)過虛擬擴(kuò)張?zhí)幚砗螅瓉硇枰渌偷膎個(gè)受災(zāi)點(diǎn)就變成了n·p個(gè)受災(zāi)點(diǎn)，從而將多品種物資的配送問題轉(zhuǎn)化為單一品種物資的配送問題。表3 顯示，3個(gè)受災(zāi)點(diǎn)對(duì)民用和醫(yī)療兩種物資的需求經(jīng)分解后轉(zhuǎn)換為6個(gè)虛擬受災(zāi)點(diǎn)對(duì)單種物資的需求。

表2 原始受災(zāi)點(diǎn)的物資需求

表3 分解后虛擬受災(zāi)點(diǎn)的物資需求

2.2 符號(hào)定義

應(yīng)急物流車輛調(diào)度模型主要包括兩種符號(hào)的定義，即集合和相關(guān)參數(shù)集合，

（1）集合定義。具體見表4。

表4 集合定義說明

（2）參數(shù)定義。具體見表5。

表5 參數(shù)定義說明

2.3 模型建立

本文研究的是多種應(yīng)急物資配送問題，以物資配送時(shí)間和成本最小化為最終目的，能否在第一時(shí)間到達(dá)災(zāi)區(qū)是檢驗(yàn)應(yīng)急物流運(yùn)作成功的關(guān)鍵。因此，模型重在實(shí)現(xiàn)應(yīng)急物流的效率，目標(biāo)函數(shù)為最小化車輛配送總時(shí)間和總成本?？偝杀景ㄜ囕v將物資從配送點(diǎn)運(yùn)送到需求點(diǎn)的運(yùn)輸成本和車輛使用發(fā)生的固定成本。

目標(biāo)函數(shù)（1）旨在使車輛配送總時(shí)間最小，目標(biāo)函數(shù)（2）旨在使車輛配送總成本最小，約束條件（3）-（5）表示應(yīng)急車輛的路徑約束，即確保每個(gè)需求點(diǎn)的每種物資僅由一臺(tái)車輛負(fù)責(zé)配送且車輛最后需返回配送中心；約束條件（6）表示車輛的裝載量約束，約束條件（7）和（8）表示二進(jìn)制決策變量的0-1約束。

3 算法求解

3.1 NSGA-Ⅱ算法

采用非支配排序遺傳算法（NSGA-Ⅱ）進(jìn)行求解，在傳統(tǒng)遺傳算法的基礎(chǔ)上加入了擁擠度計(jì)算、非支配排序等步驟，可以求解多目標(biāo)規(guī)劃問題。該算法收斂性好，運(yùn)行速度快，降低了計(jì)算的復(fù)雜度[18]。

3.2 算法步驟

算法的流程圖如圖3所示，具體步驟為：

圖3 NSGA-Ⅱ算法流程圖

第一步：初始種群并設(shè)置進(jìn)化代數(shù)Gen=1。

第二步：判斷是否生成了第一代子種群，若已生成則令進(jìn)化代數(shù)Gen=2，否則對(duì)初始種群進(jìn)行非支配排序和選擇、交叉、變異，從而生成第一代子種群并使進(jìn)化代數(shù)Gen=2。

第三步：將父代種群與子代種群合并為新種群。

第四步：判斷是否已生成新的父代種群，若沒有則計(jì)算新種群中個(gè)體的目標(biāo)函數(shù)，并執(zhí)行快速非支配排序、計(jì)算擁擠度等操作，生成新的父代個(gè)體；否則進(jìn)入第五步。

第五步：對(duì)生成的父代種群執(zhí)行選擇、交叉、變異操作，生成子代種群。

第六步：判斷Gen 是否大于等于最大的進(jìn)化代數(shù)，若沒有則進(jìn)化代數(shù)Gen=Gen+1并返回第三步；否則算法運(yùn)行結(jié)束。

4 算例分析

4.1 算例描述

為了驗(yàn)證所構(gòu)建的應(yīng)急物資調(diào)度優(yōu)化模型的可行性與有效性，本文以2020年1月1日寧波市北侖區(qū)疫情下應(yīng)急物資配送數(shù)據(jù)為樣本進(jìn)行實(shí)例分析。在此次抗疫中，設(shè)計(jì)配送中心兩個(gè)，分別為寧波農(nóng)副產(chǎn)品物流中心和海曙區(qū)石碶街道，調(diào)配物資種類分別為民用和醫(yī)療物資，數(shù)量為160t和6 000套。為了便于計(jì)算，假設(shè)一醫(yī)療物資所占體積為1 單位，假設(shè)20kg民用物資和一套醫(yī)療物資所占體積相同，因此，本文民用和醫(yī)療物資數(shù)量分別為8 000 單位和6 000 單位。假設(shè)寧波農(nóng)副產(chǎn)品物流中心有可分配車輛4 輛，海曙區(qū)石碶街道有可分配車輛5 輛，單車裝載能力為2 500 單位。隨機(jī)選取北侖區(qū)內(nèi)的10 個(gè)小區(qū)作為物資需求點(diǎn)，分別為四明家園住宅區(qū)、里仁花園住宅區(qū)、華盛小區(qū)住宅區(qū)、學(xué)府茗苑住宅區(qū)、惠金佳園住宅區(qū)、甬江家園住宅區(qū)、高塘和苑住宅區(qū)、東城華園住宅區(qū)、東方花園住宅區(qū)、永新景園住宅區(qū)。每個(gè)小區(qū)需配送600 單位民用和500 單位醫(yī)療物資。

4.2 算例求解

由上述案例可知，路網(wǎng)中一共存在12個(gè)節(jié)點(diǎn)，包括2 個(gè)配送中心和10 個(gè)需求點(diǎn)，進(jìn)行兩種物資的配送。為了保持算法的公平性，兩種算法均通過MATLAB 2022a 在配置為Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz2.70 GHz，運(yùn)行內(nèi)存為8 GB，操作系統(tǒng)為WIN10的計(jì)算機(jī)上運(yùn)行。

NSGA-Ⅱ算法和遺傳算法的實(shí)驗(yàn)均設(shè)置種群規(guī)模為100，交叉概率為0.8，迭代次數(shù)1 000，并均以迭代次數(shù)作為終止條件。實(shí)驗(yàn)中其他參數(shù)見表6。物資需求點(diǎn)和物資配送中心的距離選擇現(xiàn)實(shí)路網(wǎng)中的最短路徑，具體距離見表7，物資需求點(diǎn)和物資配送中心的具體信息見表8。

表6 實(shí)驗(yàn)參數(shù)

表7 物資需求點(diǎn)和物資配送中心距離 （單位：km）

表8 配送中心和需求點(diǎn)信息

4.3 算例結(jié)果

NSGA-Ⅱ算法和遺傳算法得出的配送方案和計(jì)算結(jié)果見表9、表10，兩種算法的配送路線如圖4、圖5所示，NSGA-Ⅱ算法下兩種物資的配送路徑如圖6所示。

圖4 遺傳算法配送路線

圖5 NSGA-Ⅱ算法配送路線

圖6 NSGA-Ⅱ算法下兩種物資配送路線

表9 車輛配送方案

表10 計(jì)算結(jié)果

由配送路線和計(jì)算結(jié)果可知，NSGA-Ⅱ算法的配送路徑總長度為486.2km，遺傳算法為657.4km，車輛配送路徑縮減了26.04%，總時(shí)間減少了26.04%，總成本節(jié)省了27.76%，因此，NSGA-Ⅱ算法的計(jì)算結(jié)果優(yōu)于遺傳算法。

5 結(jié)語

本文建立了考慮多品種的應(yīng)急物資車輛路徑優(yōu)化模型，并設(shè)計(jì)非支配排序遺傳算法（NSGA-Ⅱ）進(jìn)行求解，使得車輛配送總時(shí)間和總成本達(dá)到最優(yōu)，以2022年1月1日寧波市北侖區(qū)抗疫進(jìn)行應(yīng)急物資配送實(shí)例分析，驗(yàn)證了模型和算法的有效性。

結(jié)果表明：（1）NSGA-Ⅱ算法的車輛配送路徑總長度為486.2km，總時(shí)間為291.72，總成本為743.1；（2）將NSGA-Ⅱ算法與傳統(tǒng)遺傳算法進(jìn)行對(duì)比，車輛配送總時(shí)間縮短了26.04%，總成本節(jié)省了27.76%，因此NSGA-Ⅱ算法的計(jì)算結(jié)果優(yōu)于遺傳算法。