重大突發事件下應急物流車輛路徑優化模型與算法

王娟 譚康業

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

關鍵詞：應急物流;車輛路徑優化;軟時間窗;改進的粒子群優化算法;重大突發事件

中圖分類號：F252.8??? 文獻標識碼：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

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

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

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

1? 重大突發事件下應急物流車輛路徑優化模型

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

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

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

模型中的參數定義為：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輛車最大行駛里程數，單位：km;VC為第j輛車在單次運輸過程中的單位運輸成本，單位：元;TC為單位時間成本，T表示完成單次配送所耗費的時間，A表示車輛j到達需求點k的時間，ET表示時間窗最早允許時間，LT表示時間窗最晚時間，Z表示第k個需求點的懲罰成本。Z表示單位早到懲罰成本;Z表示單位遲到懲罰成本;C表示出車單位固定成本。

應急物流車輛路徑優化模型中的決策變量定義：

x=

y=

z=

構建的應急物流車輛路徑優化模型如下：

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

2? 重大突發事件下應急物流車輛路徑優化算法

2.1? 改進的PSO數學模型

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

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

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

粒子i的速度：

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

粒子i尋優位置：

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

種群尋優位置：

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維空間中，插入改進的粒子優化公式：

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

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

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

其中：ω為慣性權值，可以擴展粒子探索的空間，讓粒子保持慣性從而進行新的探索;c和c都為認知常數，其中c表示粒子自我認知能力，c表示粒子群體的認知能力，當認知常數設定值較高時，粒子可能會越過目標區域，且一般不為0;c和

c都為粒子優化系數，當粒子優化系數設定值較高時，粒子運動能力增強，擴大了解空間，且粒子與粒子群信息交流更密切;

r和r是兩個在0，1范圍內變化的隨機數。某一維粒子速度應滿足V

2.2? 改進的PSO實現步驟

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

算法基本實現步驟如下：

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

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

Step 2：適應度值計算模塊。計算粒子群個體的適應度值，即根據需求點到配送中心的坐標位置計算兩點之間的距離、車輛速度、車輛載重等計算相應的適應度。轉Step 3。

Step 3：根據目標函數計算適應度值，引入粒子優化策略，擴大粒子搜索范圍，找出粒子群的gbest和各粒子的pbest，如果當前適應度優于之前的最優值，則更新粒子最優值和全局最優值，即pbestX=X;pbestX=X，轉Step 4;反之，則不進行最優值更新，轉Step 4。

Step 4：將評估值進行存儲，用于下一狀態的評價，根據粒子適應度值更新個體最優粒子和群體最優粒子，更新各任務對應的車輛速度及車輛接受各任務序號的速度和位置并進行速度和位置校正，若此時粒子速度V∈V，V、粒子位置X

∈X，X且優于之前，則更新，轉Step 5;否則保持不變，轉Step 3;

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

[9] 胡忠君，劉艷秋，李佳. 基于實時交通信息的災后應急物流多源配送優化問題[J]. 工業工程，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] 曲沖沖，王晶，黃鈞，等. 考慮時效與公平性的震后應急物資動態配送優化研究[J]. 中國管理科學，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] 楊菊花，朱昌鋒，田志強. 引入時間緊迫系數的應急物資運輸路徑優化[J]. 鐵道科學與工程學報，2013，10（2）：103-107.

[22] 鄭斌，馬祖軍，周愉峰. 震后應急物流動態選址—聯運問題的雙層規劃模型[J]. 系統管理學報，2017，26（2）：326-337.

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