重大突發(fā)事件下應(yīng)急物流車輛路徑優(yōu)化模型與算法

王娟 譚康業(yè)

摘? 要：重大突發(fā)事件如新冠疫情、地質(zhì)災(zāi)害等的爆發(fā)對我國應(yīng)急物流的及時響應(yīng)性與運轉(zhuǎn)穩(wěn)定性提出嚴(yán)峻挑戰(zhàn)與要求。針對重大突發(fā)事件下應(yīng)急物流配送時效性不足、系統(tǒng)總成本過高等問題，以車輛配送走行成本、時間成本、早到/遲到懲罰成本和出車固定成本最小化為目標(biāo)，考慮各需求點收貨軟時間窗、車輛額定載重量、容積、車輛單次配送最大行駛里程等約束條件，構(gòu)建面向重大突發(fā)事件的應(yīng)急物流車輛路徑優(yōu)化模型;引入收斂速度改進(jìn)策略、粒子搜索改進(jìn)策略、精英保留改進(jìn)策略，設(shè)計了一種適于求解全局優(yōu)化問題的改進(jìn)粒子群優(yōu)化算法。仿真結(jié)果表明，利用改進(jìn)的粒子群優(yōu)化算法求解面向重大突發(fā)事件的應(yīng)急物流車輛路徑問題時，能夠得到更加優(yōu)化的結(jié)果。

關(guān)鍵詞：應(yīng)急物流;車輛路徑優(yōu)化;軟時間窗;改進(jìn)的粒子群優(yōu)化算法;重大突發(fā)事件

中圖分類號：F252.8??? 文獻(xiàn)標(biāo)識碼：A

Abstract： A major epidemic situation such as COVID-19 or geological disaster brings severe challenges and requirements for the timely response and operational stability of emergency logistics. Basing on the problems of insufficient timeliness and high total system cost of emergency logistics distribution in major epidemic situations， taking the minimum of vehicle distribution travel cost， time cost， early/late punishment cost， and fixed cost of vehicle as the target， the soft time window for receiving goods at each demand point， the rated load of the vehicle， the volume， the maximum travel of the vehicle in a single delivery as constraints， the emergency logistics vehicle routing problem optimization model for major epidemics was constructed. The convergence speed improvement strategy， particle search improvement strategy， and elite retention improvement strategy were introduced to improve particle swarm optimization algorithm suitable for solving global optimization problems. The simulation results show that， the improved particle swarm optimization algorithm designed to solve the emergency logistics vehicle routing problem for major epidemic situation can reach optimal results.

Key words： emergency logistics; vehicle routing problem optimization; soft time window; improved particle swarm optimization algorithm; major epidemic situation

應(yīng)急物流通常指的是為應(yīng)對自然災(zāi)害或災(zāi)難性的突發(fā)事件，對生活用品、救援物資和人員的緊急調(diào)運安排的一類特殊的物流管理活動[1]。應(yīng)急物流是應(yīng)急事件反應(yīng)體系中至關(guān)重要的一環(huán)，而應(yīng)急車輛路徑優(yōu)化又是應(yīng)急物流活動能否快速、準(zhǔn)確、穩(wěn)定運行的關(guān)鍵，是應(yīng)急物流的重要組成部分。國家重大應(yīng)急事件包括公共衛(wèi)生事件、地質(zhì)災(zāi)害、重大自然災(zāi)害等，如新冠病毒疫情期間武漢采取封城策略，對城市應(yīng)急物流提出了極大挑戰(zhàn)。SARS期間造成的損失總額約176億美元，其中應(yīng)急物流的損失高達(dá)30億美元[2];據(jù)人民日報報道，新冠疫情爆發(fā)初期武漢出現(xiàn)了因物資配送中心管理不善導(dǎo)致應(yīng)急物資發(fā)放出現(xiàn)諸如分配不當(dāng)、分配時間過長等問題，集中體現(xiàn)了我國應(yīng)急物流發(fā)展的短板。

當(dāng)重大應(yīng)急事件發(fā)生時，應(yīng)急物流需要及時響應(yīng)，向需求點運送應(yīng)急物資，盡快滿足需求點的各類需求，其中重點和難點之一就是車輛的路徑優(yōu)化，如何在指定時間內(nèi)運送需求物資到達(dá)指定地點，是應(yīng)急物流車輛路徑優(yōu)化要解決的主要問題。與傳統(tǒng)車輛路徑優(yōu)化明顯不同的一點是，應(yīng)急車輛路徑優(yōu)化更注重時效性和準(zhǔn)確性等特點。車輛路徑問題（Vehicle Routing Problem， VRP）最早由Dantzig和Ramser[3]提出，描述的問題可概括為一定的需求點和一個起點，已知各需求點需求量和位置坐標(biāo)，如何在約束條件下，選擇一條最合適的最后返回起點的路徑。應(yīng)用到實際場景中，衍生了許多類型的VRP問題，包括含有時間窗的VRP、開放式VRP，綠色VRP、應(yīng)急VRP等。國內(nèi)關(guān)于應(yīng)急VRP的研究最早是由歐忠文等[4]明確開始的，其首次提出了“應(yīng)急物流”的概念，并清晰闡述了其內(nèi)涵與研究內(nèi)容等，為應(yīng)急物流發(fā)展奠定了基礎(chǔ)。陳瑩珍等[5]從地區(qū)物資平衡性方面加以考慮，提出了改進(jìn)的差分進(jìn)化算法求解應(yīng)急物資分配問題。龐海云等[6]建立了三級應(yīng)急物資運輸網(wǎng)絡(luò)并提出一種改進(jìn)粒子群算法，進(jìn)一步完善了應(yīng)急配送網(wǎng)絡(luò)。劉長石等[7]從系統(tǒng)集成化的角度來完善應(yīng)急物流配送問題，構(gòu)建了一個多目標(biāo)模糊LRP模型，旨在協(xié)同解決定位—路徑優(yōu)化問題。Sheu等[8]強調(diào)了應(yīng)急物流的目的性、信息化和有效性。胡忠君等[9]針對城市應(yīng)急物流配送問題，考慮救災(zāi)需求點物資配送可由配送中心和轉(zhuǎn)運中心多源滿足的情況，在實時交通信息下，以救災(zāi)時間最小和資源分配公平性最大為目標(biāo)建立模型。Gutjahr等[10]第一次在應(yīng)急物流中強調(diào)了物資配送與應(yīng)急災(zāi)害管理間的關(guān)系優(yōu)化。Jacobson等[11]在考慮時間窗、緊要程度等的情況下建立數(shù)學(xué)模型，進(jìn)一步提出了應(yīng)急物流的多目標(biāo)優(yōu)化策略。Huang等[12]建立了物流資源應(yīng)急分配模型來應(yīng)對災(zāi)害發(fā)生后的場景，其中考慮了生存性、延時性、公平性等三個目標(biāo)。Talarico等[13]求解了災(zāi)后傷員如何分配救護(hù)車的路徑優(yōu)化問題模型。Wilson等[14-15]建立了同時多個災(zāi)后傷員救治目標(biāo)的數(shù)學(xué)模型，對應(yīng)急物流問題進(jìn)行了拓展。Xian[16]根據(jù)應(yīng)急物流的特性建立了相應(yīng)的體系結(jié)構(gòu)，對車輛路徑進(jìn)行合理優(yōu)化。曲沖沖等[17]建立了一種應(yīng)急配送中心選址與車輛路徑共同優(yōu)化模型。Edrissi等[18]提出一種用于評估物流網(wǎng)絡(luò)運作性能的方法，更系統(tǒng)地完善了應(yīng)急物流運作網(wǎng)絡(luò)。Meysam等[19]提出了一個多目標(biāo)優(yōu)化模型，用于地震響應(yīng)時的車輛路徑優(yōu)化問題。Nikoo等[20]提出了一種用于尋找最優(yōu)應(yīng)急車輛路線的優(yōu)化模型。楊菊花等[21]針對應(yīng)急物資全程調(diào)撥時路徑選擇問題設(shè)計了一種改進(jìn)蟻群算法。對于這類問題和模型多數(shù)學(xué)者采用的主要求解方法有遺傳算法[22]、模擬退火算法[23]等啟發(fā)式算法及其拓展算法。

以上文獻(xiàn)主要研究了地震后快速響應(yīng)、應(yīng)急物流車輛運輸、人員救援轉(zhuǎn)移等問題，現(xiàn)有應(yīng)急物流相關(guān)研究為本研究提供了基礎(chǔ)，但重大突發(fā)事件下應(yīng)急物流車輛路徑優(yōu)化方面，需進(jìn)一步研究優(yōu)化。在重大突發(fā)事件下應(yīng)急物流車輛路徑優(yōu)化的各項影響因素的基礎(chǔ)上，建立含有軟時間窗的應(yīng)急車輛路徑優(yōu)化模型，引入收斂速度改進(jìn)策略、粒子搜索改進(jìn)策略、精英保留改進(jìn)策略，提出一種改進(jìn)的粒子群優(yōu)化算法（PSO），最后通過實例驗證了該算法的有效性。

1? 重大突發(fā)事件下應(yīng)急物流車輛路徑優(yōu)化模型

在疫情發(fā)生初期，通常由省市紅十字會負(fù)責(zé)應(yīng)急物資的調(diào)配與發(fā)放。應(yīng)急物資在配送中心集中以后，需按照各需求點的具體需求品種和數(shù)量，在指定時間范圍內(nèi)及時、準(zhǔn)確送達(dá)至需求地點，因此，如何快速制定出車輛裝載和配送路徑，是重大突發(fā)事件下應(yīng)急物流需要解決的關(guān)鍵問題。以車輛走行成本、時間成本、早到/遲到懲罰成本、出車固定成本等最低為目標(biāo)函數(shù)，考慮收貨軟時間窗、車輛額定載重量、容積、車輛單次配送最大行駛里程、每個需求點的貨物只能由一輛車進(jìn)行配送等約束條件，構(gòu)建重大突發(fā)事件下應(yīng)急物流車輛路徑優(yōu)化模型。模型假設(shè)如下：

（1）需求點早到/遲到懲罰函數(shù)呈線性變化;

（2）需求點的貨物需求量均未超過單車額定載重量和容積。

模型中的參數(shù)定義為：i為貨物編號i=1，2，…，I;j為車輛編號j=1，2，…，J;p、q為需求點編號，p，q=0，1，2，…，K，d表示需求點p到q距離;k為需求點編號，k=1，2，…，K;V表示貨物i的體積，單位：m3;VV為j輛車額定容積：m3;CW為p需求點第i件貨物的重量;VW為j輛車額定載重，單位：kg;M為第j輛車最大行駛里程數(shù)，單位：km;VC為第j輛車在單次運輸過程中的單位運輸成本，單位：元;TC為單位時間成本，T表示完成單次配送所耗費的時間，A表示車輛j到達(dá)需求點k的時間，ET表示時間窗最早允許時間，LT表示時間窗最晚時間，Z表示第k個需求點的懲罰成本。Z表示單位早到懲罰成本;Z表示單位遲到懲罰成本;C表示出車單位固定成本。

應(yīng)急物流車輛路徑優(yōu)化模型中的決策變量定義：

x=

y=

z=

構(gòu)建的應(yīng)急物流車輛路徑優(yōu)化模型如下：

minf=xdVC+TC*T+Penaltyp+yC?????????????????????? （1）

s.t.

zyCW≤VW， ？坌j=1，2，3，…，J??????????????????????????????????????? （2）

xd≤M， ？坌j=1，2，3，…，J???????????????????????????????????????????? （3）

zV≤VV， ？坌j=1，2，3，…，J? ??????????????????????????????????????????（4）

y=1， ？坌k=1，2，3，…，K??????????????????????????????????????????????????? （5）

x=x， ？坌j=1，2，3，…，J??????????????????????????????????????????? ???（6）

Penaltyp=?????????????????????????????????? （7）

x∈0，1??? p，q=0，1，2，…，K; j=1，2，3，…，J?????????????????????????????????? （8）

y∈0，1??? k=0，1，2，…，K; j=1，2，3，…，J???????????????????????????????????? （9）

z∈0，1??? i=1，2，3，…，I; j=1，2，3，…，J; k=0，1，2，…，K????????????????????????? （10）

公式（1）表示模型的目標(biāo)函數(shù)為車輛配送走行成本、時間成本、早到/遲到懲罰成本和出車固定成本最小化;公式（2）表示每輛車裝載貨物總重量不超過車輛額定載重量;公式（3）表示每輛車每次配送總距離不超過車輛單次配送最大行駛里程;公式（4）表示每輛車裝載貨物總體積不超過車輛容量;公式（5）表示每個需求點的貨物只能由一輛車完成配送;公式（6）表示車輛在完成配送任務(wù)后返回配送中心;公式（7）表示送貨時間早于或晚于需求點收貨時間窗的懲罰函數(shù);公式（8）、公式（9）、公式（10）為0～1決策變量。

2? 重大突發(fā)事件下應(yīng)急物流車輛路徑優(yōu)化算法

2.1? 改進(jìn)的PSO數(shù)學(xué)模型

相較于傳統(tǒng)粒子群算法收斂速度過快、粒子運動能力過差，解空間過小等特點，引入收斂速度改進(jìn)策略、粒子搜索改進(jìn)策略、精英保留改進(jìn)策略，設(shè)計了一種適于求解全局優(yōu)化問題的改進(jìn)粒子群優(yōu)化算法。通過將粒子及粒子群智能化處理，主動且快速地尋找解空間內(nèi)最優(yōu)解的地點，核心在于獨特的粒子更新策略以及速度變化。改進(jìn)的PSO數(shù)學(xué)模型如公式（11）至公式（18）所示。

粒子i的位置如公式（11）所示，作為優(yōu)化問題潛在解：

X=x，x，…，x， i=1，2，3，…，m???????????????????????????????????? （11）

粒子i的速度：

V=v，v，…，v， i=1，2，3，…，m???????????????????????????????????? （12）

粒子i尋優(yōu)位置：

P=p，p，…，p， i=1，2，3，…，m???????????????????????????????????? （13）

種群尋優(yōu)位置：

G=g，g，…，g， i=1，2，3，…，m????????????????????????????????????? （14）

在d維空間中，粒子i的速度更新公式為：

v=ω*v+c*r*p-x+c*r*p-x??????????????????????????????? （15）

在d維空間中，粒子i的位置更新公式為：

x=x+v?????????????????????????????????????????????? （16）

在d維空間中，插入改進(jìn)的粒子優(yōu)化公式：

x=c*x+c*v??????????????????????????????????????????? （17）

在此過程中對于每個粒子i，有：

X∈X，X， V∈V，V???????????????????????????????????? （18）

其中：ω為慣性權(quán)值，可以擴(kuò)展粒子探索的空間，讓粒子保持慣性從而進(jìn)行新的探索;c和c都為認(rèn)知常數(shù)，其中c表示粒子自我認(rèn)知能力，c表示粒子群體的認(rèn)知能力，當(dāng)認(rèn)知常數(shù)設(shè)定值較高時，粒子可能會越過目標(biāo)區(qū)域，且一般不為0;c和

c都為粒子優(yōu)化系數(shù)，當(dāng)粒子優(yōu)化系數(shù)設(shè)定值較高時，粒子運動能力增強，擴(kuò)大了解空間，且粒子與粒子群信息交流更密切;

r和r是兩個在0，1范圍內(nèi)變化的隨機(jī)數(shù)。某一維粒子速度應(yīng)滿足V

2.2? 改進(jìn)的PSO實現(xiàn)步驟

改進(jìn)的粒子群優(yōu)化策略：（1）收斂速度改進(jìn)策略。主要是調(diào)整算法的基本參數(shù)，即慣性權(quán)重ω和認(rèn)知常數(shù)c和c，慣性權(quán)重對搜索范圍和搜索精度會有一定程度的影響。（2）粒子搜索改進(jìn)策略。引入了粒子優(yōu)化公式，通過粒子同個體極值和群體極值的交叉、粒子自身變異、優(yōu)化的方式來搜索最優(yōu)解。（3）精英保留改進(jìn)策略。概率接受粒子交叉中不滿足約束的粒子作為惡劣解，協(xié)助粒子跳出局部最優(yōu)。

算法基本實現(xiàn)步驟如下：

Step 1：種群初始化模塊。初始化粒子群種群，設(shè)置改進(jìn)粒子群算法的參數(shù)，假設(shè)粒子群個數(shù)為m，車輛數(shù)目是n，需求點數(shù)目為k，迭代次數(shù)為T，認(rèn)知常數(shù)為c和c，粒子潛在解空間為X，X，粒子速度變化為V，V，初始化粒子的位置和速度V，粒子最優(yōu)位置為P，種群最優(yōu)位置為G。根據(jù)需求點生成相應(yīng)的任務(wù)編號D，X為各任務(wù)對應(yīng)的車輛編號，X=roundrandm，n*n-1+1，X為各車輛進(jìn)行各項任務(wù)的排序，X=randm，n*k-1+1。V為車輛編號的生成速度，V

=roundrandm，n*n-3+1，V為任務(wù)排序的速度，V=randm，n*k-1+1，生成各粒子和粒子群初始解pbestX、pbestX、gbestX、gbestX，轉(zhuǎn)Step 2。

Step 2：適應(yīng)度值計算模塊。計算粒子群個體的適應(yīng)度值，即根據(jù)需求點到配送中心的坐標(biāo)位置計算兩點之間的距離、車輛速度、車輛載重等計算相應(yīng)的適應(yīng)度。轉(zhuǎn)Step 3。

Step 3：根據(jù)目標(biāo)函數(shù)計算適應(yīng)度值，引入粒子優(yōu)化策略，擴(kuò)大粒子搜索范圍，找出粒子群的gbest和各粒子的pbest，如果當(dāng)前適應(yīng)度優(yōu)于之前的最優(yōu)值，則更新粒子最優(yōu)值和全局最優(yōu)值，即pbestX=X;pbestX=X，轉(zhuǎn)Step 4;反之，則不進(jìn)行最優(yōu)值更新，轉(zhuǎn)Step 4。

Step 4：將評估值進(jìn)行存儲，用于下一狀態(tài)的評價，根據(jù)粒子適應(yīng)度值更新個體最優(yōu)粒子和群體最優(yōu)粒子，更新各任務(wù)對應(yīng)的車輛速度及車輛接受各任務(wù)序號的速度和位置并進(jìn)行速度和位置校正，若此時粒子速度V∈V，V、粒子位置X

∈X，X且優(yōu)于之前，則更新，轉(zhuǎn)Step 5;否則保持不變，轉(zhuǎn)Step 3;

Step 5：獲取任務(wù)對應(yīng)車輛編號的粒子和車輛對應(yīng)任務(wù)的順序，存儲每輛車運送的貨物和時間懲罰成本，對每個粒子的X和X解碼后進(jìn)行約束條件判斷，依據(jù)各車輛的額定載重量及容量限制，評估是否可作為可行解，通過群體最優(yōu)交叉，更新粒子群速度和位置，并進(jìn)行目標(biāo)函數(shù)的計算，轉(zhuǎn)Step 6。

[9] 胡忠君，劉艷秋，李佳. 基于實時交通信息的災(zāi)后應(yīng)急物流多源配送優(yōu)化問題[J]. 工業(yè)工程，2018，21（1）：83-88.

[10]? Walter J Gutjahr， Pamela C Nolz. Multicriteria optimization in humanitarian aid[J]. European Journal of Operational Research， 2016，252（2）：351-366.

[11]? Jacobson E U， Argon N T， Ziya S. Priority assignment in emergency response[J]. Operations Research， 2012，60（4）：813-832.

[12]? Kai Huang， Yiping Jiang， Yufei Yuan， et al. Modeling multiple humanitarian objectives in emergency response to large-scale disasters[J]. Transportation Research Part E， 2015，75（3）：1-17.

[13]? Talarico L， Meisel F， S Rensen K. Ambulance routing for disaster response with patient groups[J]. Computers & Operations Research， 2015，56（4）：120-133.

[14]? Wilson D T， Hawe G I， Coates G， et al. A multi-objective combinatorial model of casualty processing in major incident response[J]. European Journal of Operational Research， 2013，230（3）：643-655.

[15]? Wilson D T， Hawe G I， Coates G， et al. Online optimization of casualty processing in major incident response： An experimental analysis[J]. European Journal of Operational Research， 2016，252（1）：334-348.

[16]? Xian Qiang. Vehicle scheduling model for emergency logistics distribution with improved genetic algorithm[J]. International Journal of Advancements in Computing Technology， 2012，4（18）：315-323.

[17] 曲沖沖，王晶，黃鈞，等. 考慮時效與公平性的震后應(yīng)急物資動態(tài)配送優(yōu)化研究[J]. 中國管理科學(xué)，2018，26（6）：178-187.

[18]? Ali Edrissi， Mehdi Nourinejad， Matthew J Roorda. Transportation network reliability in emergency response[J]. Transportation Research Part E， 2015，80（5）：56-73.

[19]? Meysam Fereiduni， Marzieh Hamzehee， Kamran Shahanaghi. A robust optimization model for logistics planning in the earthquake response phase[J]. Decision Science Letters， 2016，5（4）：519-534.

[20]? Babaei M， Mohaymany A S， Nikoo N. Emergency transportation network design problem： identification and evaluation of disaster response routes[J]. International Journal of Disaster Risk Reduction， 2018，27（7）：7-20.

[21] 楊菊花，朱昌鋒，田志強. 引入時間緊迫系數(shù)的應(yīng)急物資運輸路徑優(yōu)化[J]. 鐵道科學(xué)與工程學(xué)報，2013，10（2）：103-107.

[22] 鄭斌，馬祖軍，周愉峰. 震后應(yīng)急物流動態(tài)選址—聯(lián)運問題的雙層規(guī)劃模型[J]. 系統(tǒng)管理學(xué)報，2017，26（2）：326-337.

[23] 樓振凱. 應(yīng)急物流系統(tǒng)LRP的雙層規(guī)劃模型及算法[J]. 中國管理科學(xué)，2017，25（11）：151-157.