突發事件下多目標應急救援物資配送路徑規劃

康 斌， 劉 權， 黃 健， 龔建興

(國防科技大學智能科學學院，長沙 410073)

近年來，突發事件已經成為危害人類安全的主要因素。突發事件發生后，應急救援物資的指揮調度是救援工作的核心，即核心環節就是應急物資的配送[1]。面對突發事件中可能出現的各種不確定情況，例如交通路網結構的破壞、車輛運力不足、道路阻斷修復和車輛類型限制等情況，決策者需要決定如何快速、有效地對應急救援物資進行優化配置，使得配送時間最短、需求未滿足率最小、成本最低等。由于應急救援決策受救援時間和應急物資數量等因素約束，如何選擇合適的路徑提高物資配送的效率和效果是應急決策者面臨的重大問題。

針對應急救援物資的配送問題，中外研究學者做了許多相關的研究。呂游等[2]以最小成本花費為研究目標，建立基于硬時間窗的車輛配送優化模型，引入排隊策略思想優化實時路徑，通過實驗驗證其合理性。Cao等[3]以最小救援時間、最小成本和最大救援效果為目標，建立應急救援車輛路徑優化模型，提出一種基于蟻群算法的非支配解排序遺傳算法(non-dominated sorting in genetic algorithmsⅡ，NSGAⅡ)和一種基于隨機交叉和變異的NSGAⅡ混合遺傳算法。俞武揚[4]以配置總成本最小為目標，考慮阻斷道路數量和需求量兩個參數，建立兩階段應急救援物資魯棒配置模型，將二次規劃模型轉化為整數混合模型并提出Benders分解算法。段滿珍等[5]考慮在不確定通行能力限制條件下，分析公交疏散問題，研究了上層最優轉向策略和下層救援時間最短路徑。劉波等[6]以最小車輛調配時間和最小車輛成本為目標，在時間窗和道路通行可靠性限制情況下，建立雙層魯棒優化模型。王晶等[7]以最大配送效率為目標，充分考慮道路中斷和通行可靠性降低對應急救援配送路徑的影響，建立道路修復和道路可靠性選擇集成優化，并提出了多吸引子的粒子群算法對其求解。

目前，在應急救援物資配送優化目標的考慮上，多數文獻以時間和成本花費為研究目標，主要集中在提高配送的效率方面，在配送效果方面研究比較少。現以最小化最晚服務結束時間和最小化需求未滿足率為目標，在道路對車型限制、道路阻斷修復和道路可靠性約束條件下，建立多目標優化模型，既考慮配送效率又兼顧配送公平性效果，更為滿足實際救援情景下的應急資源配送路徑規劃需求，以期為突發事件下決策者快速選擇有效救援物資調度方案提供決策依據。

1 問題描述與模型構建

1.1 問題描述

突發事件下，面對時間緊迫，道路情況復雜等多種因素，如何安全高效地將應急救援物資配送到需求點成為決策者需要重要考慮的問題之一。為了符合實際救援物資配送要求，考慮實際災害情景對救援物資配送車輛路徑規劃的限制因素。①存在道路受突發事件影響而受損以及道路自身結構如橋梁、窄道等因素限制，為保證車輛能夠順利通行，需考慮道路路況對車型的限制；②災害發生后，部分道路損毀導致路段完全無法通行，為提高配送效率，需考慮對部分道路進行搶修；③道路受次生災害影響存在一定的安全風險，需考慮道路的可靠性因素，可依靠技術檢測或受災程度分析等手段得到道路可靠性等級信息。優化目標在考慮應急物資可用量和車載容量限制條件下，確定最佳配送方案使得最晚車輛服務時間最短和物資需求點的需求未滿足率最小。

1.2 問題假設

(1)配送過程中忽略配送車輛故障和最大行駛距離的影響。

(2)應急救援道路網絡情況已知。

(3)僅考慮車輛配送情況，需要飛機、輪船等其他運輸方式才能到達的需求點不做考慮。

(4)道路修復完成之后可靠性為1。

(5)需求點位置不變，且物資在需求點不能轉移。

(6)救援物資僅考慮一般生活物資并且可以混裝，不影響裝卸貨時間。

1.3 參數設置和變量說明

應急道路網絡表示為G=(V,A,L),其中，V(i∈V)表示所有節點，其中i=0表示配送中心，i=1,2,…,n表示需求點，n為需求點的數量；A為可用鏈路集合；L為失效鏈路集合，l∈L。K為車輛集合，k∈K。Q為應急物資可用量。Qij為車輛從i點出發，到達j點后，配送給j點的物資量(i,j)∈A。QAi為配送前i點的應急物資可用量。QFi為配送后點i處應急物資持有量。Qk為在應急配送中心處車輛k的裝載量。wik為車輛k給需求點i處運送應急物資的數量。Di為需求點i處應急物資需求量。Sik為車輛k在點i處的服務時間。nh為工作效率，即每小時物資的裝載量或者卸載量。rij為鏈路(i,j)∈A的安全通過概率，rij∈[0,1]。rk表示車輛k的最大容量。M為車輛類型(M為整數，越大車輛越大型)。KMij為鏈路(i,j)∈A允許通過M及其以下類型的車輛,即車輛限定值。tl為道路l搶修完成時間。VAik為0-1整數變量，如果車輛k在需求點i處可用為1,否則為0。VFik為0-1整數變量,如果點i是車輛k所服務路線上的最后一個節點為1，否則為0。xijk為0-1整數變量，車輛k通過鏈路(i,j)∈A為1;否則為0。yik為0-1整數變量，車輛k經過需求點i為1，否則為0。

1.4 多目標車輛路徑優化模型

車輛在鏈路(i，j)的運行時間tijk取決于鏈路的距離dij以及車輛的最大限制速度vij和平均運行速度vk,即tijk=dij/min(vij,vk)。車輛k在需求點i的卸貨時間Sik=wik/nh由此，車輛k在需求點i的服務結束時間ti=tijkxijk+Sikyik。

應急救援物資配送優化模型如下：

minZ1

(1)

minZ2

(2)

(3)

s. t.

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

式(1)表示最小化車輛最晚服務結束時間；式(2)表示最小化需求未滿足率；式(3)表示安全通過概率不小于規定值；式(4)表示從配送中心運出的物資總量等于需求點的配送量；式(5)為在各節點處車流量均衡;式(6)表示車輛總數不變;式(7)表示服務結束時一個車輛可以且僅可以停留在一個節點上；式(8)表述車輛到達一個節點(除路線上最后一個節點外)后必須從同一個節點離開；式(9)表示車輛配送給需求點的物資量不超過其需求量且非負；式(10)表示配送到需求點的物資總量不超過應急物資可用量；式(11)表示車輛裝載量不超過車載容量；式(12)為子回路規避，同一輛車只能服務同一個需求點一次。

2 模型求解

2.1 數據獲取

地震等突發事件發生后，第一時間無法準確獲得環境信息具體的數值，使得面向數據決策的數據獲取具有較大的難度。利用谷歌地圖、高德地圖等軟件獲取相關路網信息，同時結合專家評估法[8]對路網進行評估。具體評估方法如下。

(1)請專家對震后路網結構中被破壞的路段進行評估，估計出每條路段搶修完成平均時間tl，物資消耗量暫不考慮在內。

(2)對所有路段的通行可靠性進行估計；根據車輛類型差異，給出路段對車輛的類型限制要求。

2.2 模型層次化求解

應急救援物資配送路徑規劃涉及兩層優化問題：①路網層問題，在道路對車型的限制條件下，通過車型對路網結構進行更新，每類車型對應一種路網結構，保證在滿足最優目標條件的同時又能夠成功完成配送任務；在道路搶修時間已知情況下，確定道路能否在車輛到達前搶修成功，保證車輛順利通行；②路徑層問題，在以上分析的基礎上，車輛分配給不同的需求點，配送路徑不同，同時分析配送路徑可靠性，確定所有車輛的最佳配送路徑，使得配送方案最優。

2.2.1 路網層優化問題

首先假定整個路網道路情況完好，根據車輛類型限定值KM，更新整個道路路網的結構，得出不同類型車輛所對應的路網。每條路段(i,j)存在安全通過概率rij，在滿足rij>θ的條件下，計算任意兩點之間最短路徑dij。采用Floyd算法[8]對路網層進行求解，得到邏輯層面的全連通路網結構。路網層優化結果作為路徑層的輸入，保證車輛順利完成配送任務。

2.2.2 路徑層優化問題

不確定路網情況下車輛路徑分配屬于典型的NP難問題[9]。理論證明，采用遺傳算法解決NP難問題能夠得到較好的可行解，因此采用非支配解排序的遺傳算法(NSGAⅡ)解決應急救援物資車輛配送路徑規劃的多目標優化問題，引入部分映射交叉(partial-mapped crossover,PMX)和優先鄰點混合交叉算子，提高局部搜索能力。NSGAⅡ將應急救援物資配送同受損道路修復，道路對車輛類型限制和道路安全系數進行綜合優化，使得最終輸出的應急救援物資配送路線達到最優。

2.3 NSGAⅡ設計

NSGAⅡ算法思想[10]：首先，采用隨機方式生成初始種群，通過交叉變異生成新一代的子種群，將父代種群和子代種群合并，經過快速支配排序并計算所有個體的擁擠度，最后由精英選擇策略選擇合適種群作為新一代父代種群，直到滿足結束條件。

2.3.1 染色體編碼

應急救援物資車輛配送路徑規劃問題是車輛從配送中心出發經歷不同的需求點，得到車輛行駛路線。考慮到車輛編號和需求點編號為整數序列，因此在NSGAⅡ中采用整數編碼方式。每條染色體由兩個字串組成，即X=[X1,X2]。因為車輛總數為k,需求點總數為n,所以X1包含k個元素，X2包含n個元素，兩個字串產生方式為隨機產生,所有車輛都從一個配送中心出發，忽略配送中心在染色體中所占位置,染色體的總長度為k+n。染色體結構如圖1所示。

圖1 染色體結構Fig.1 Chromosome structure

2.3.2 種群初始化

(1)染色體中X1的一個基因位代表一輛車，檢測該基因位車輛所屬類型，輸入對應的路網結構。

(2)X1中的第一個基因位表示所對應的車輛首先會到達X2的第一個基因位所代表的需求點，由該輛車為該點進行配送，并檢驗是否滿足道路可通行性，即若到達該點時間大于搶修路段搶修完成時間和到達該點的安全通過概率大于規定值，則道路可通行；反之，舍棄該染色體。

(3)若該需求點的需求量小于車輛載貨量，則配送X2中的下一基因位代表的需求點。如果該需求點的需求大于車輛載貨量，則該車輛停在該需求點等待下次分配，然后X1中的第二基因位所代表車輛為X2中當前基因位的下一基因位開始配送物資，以此類推。

(4)若所有需求點都有車輛配送后，車輛和救援物資還有剩余，并且還有需求點的需求未被全部滿足，則從X1的第一個基因位重復以上過程。

2.3.3 交叉、變異算子

為提高解的多樣性和Pareto解集質量，對染色體中的兩個字串進行獨立交叉，算法中具體采用PMX交叉和優先鄰點交叉相結合的混合交叉方式，即能提高種群多樣性，又能保證優秀基因片段被保留，提高解的質量。

以9輛車配送9個需求點為例，說明混合交叉過程。從同代種群中隨機選擇兩條染色體A、B。

(1)對X1進行PMX交叉。

(13)

隨機選擇兩個交叉點，將X1進一步分為三段：

(14)

交換兩個交叉點之間的基因段，得到：

(15)

得到交叉片段中的映射關系：2對應4，4對應5，9對應2，通過消除交叉基因段中相同數字得到9對應5，替換交叉基因段之外重復的數字得到新字串:

(16)

(2)對X2進行優先鄰點交叉。

(17)

隨機選擇兩個相鄰交叉點a、b，將X2進一步分為三段，將前一位基因記錄為ea，后一位基因記錄為eb。

(18)

(19)

采用倒置變異的方法進行變異操作。在不同的字串隨機生成兩點，將兩點之間的待變異片段倒置處理得到新的染色體。

2.3.4 快速非支配解排序

所建模型為雙目標模型，即車輛最遲服務結束時間和需求點未滿足率。假設種群種中有p條染色體，每一條染色體都需要和其他剩下的p-1條染色體就這兩個目標進行比較，最終得出Pareto的前沿等級，即非支配解排序。np是在可行解空間中可以支配個體p的所有個體的數量，Sp為可行解空間中所有被個體p支配的個體組成的集合。主要步驟如下：

(1)初始化np=0，Sp=?，找到np=0所有的個體，并將它們保存到當前集合Fl中(l為迭代次數)。

(2)對于集合Fl中每個個體k所支配個體集合為Sk，歷遍集合Sk中所有個體j，并執行nj=nj-1，若nj=0，將個體j存入另一個集合H。

(3)將Fl作為非支配解集合，并給予集合中的個體相同的非支配序irank,并以集合H作為當前集合，重復以上過程，直到整個種群分級。

2.3.5 確定擁擠度

擁擠度是指種群中給定個體的周圍個體的密度,直觀上可表示為個體周圍僅僅包含自身但并不包含其他個體的最小長方形，用nd表示[11]，如圖2所示。

圖2 個體n擁擠度Fig.2 Individual n-crowding

種群中每個個體在經歷排序和擁擠度計算之后，得到其非支配前沿等級irank和擁擠度nd，定義擁擠度比較算子為≥n，個體優劣的比較依據為

i≥nj,即個體i優于個體j，當且僅當irankjnd。

圖3 NSGAⅡ 流程圖Fig.3 NSGAⅡ flow chart

2.4 NSGAⅡ 步驟

本文采用的NSGAⅡ流程圖如圖3所示，具體步驟如下：

Stpe1隨機生成第一代種群Pt，種群大小為N。

Stpe2對種群Pt進行交叉和變異操作，生成新種群Qt。

Stpe3將種群Pt和種群Qt合并生成新種群Rt。

Stpe4計算種群Rt所有染色體的目標函數值。

Stpe5對種群Rt所有染色體進行非支配解排序和擁擠度計算，得出Pareto前沿等級。

Stpe6通過精英選擇策略，篩選出種群大小為N的下一代父種群Pt+1。

Stpe7若當前運行種群代數t>T(T為最大運行種群代數)，則輸出最優解集;否則t=t+1,并轉向Stpe 2。

3 算例分析

參考雅安地震[12]應急資源配送示例，配送中心和需求點的交通網絡參數如表1所示。表1中i0表示配送中心，i1,i2,…,i8表示受災需求點，(a,b,c)表示兩相鄰節點之間鏈路的距離 (km)、最大允許行駛速度(km/h)以及道路可靠性(可靠性為0表示道路損壞，待修復;修復完成可靠性為1)。

表1 交通網絡參數 Table 1 Taffic network parameters

注：道 路i5-i6搶修完成時間tl=1 h。

救援物資配送車輛有大型卡車有6輛,中型卡車4輛和小型卡車6輛，具體車輛類型參數如表2所示。

需求點需求量如表3所示。

表2 車輛類型參數Table 2 Vehicle type parameters

表3 各需求點的應急救援物資需求量Table 3 Demand of emergency relief materials at various demand points

3.1 計算結果

在CPU為Intel(R) 3.3 GHz,內存8 GB的計算機上用MATLAB R2016a對算法進行仿真實驗。

算法設置參數如下：種群大小N=100，最大迭代次數T=500，交叉概率Pc=0.8，變異概率Pm=0.5。仿真試驗設置以配送時間優先和以配送需求未滿足率優先兩種方案，得到不同方案下雙目標模型的Pareto最優目標值，如表4所示。

表4 兩種方案下雙目標 Pareto最優值Table 4 Bi-objiective Pareto optimal solution under two schemes

由表4可知，方案一最晚服務時間為6.92 h，方案二最晚服務時間為8.62 h，相比方案一在配送效率上提高了7.8%。但是，方案一最大未滿足率為0.253，方案二最大未滿足率為0.222，相比方案一，最大未滿足率卻下降13%，結果驗證了本文所提算法和模型的有效性。

3.2 算法比較

采用基于改進的混合交叉算子NSGAⅡ(簡稱改進NSGAⅡ)與基于兩點交叉PMX算子NSGAⅡ(簡稱一般NSGAⅡ)兩種算法對實例進行仿真實驗。得出的Pareto最優解集如圖4所示。從圖4中可以看出，改進NSGAⅡ對應4個解，一般NSGAⅡ對應3個解，并且前者支配后者，因此改進的NSGAⅡ能夠提高局部搜索能力，增加解的多樣性。

圖4 改進NSGAⅡ和一般NSGAⅡ Pareto最優解集Fig.4 Improved NSGAⅡand General NSGAⅡ Pareto optimal solution set

兩種算法運行100次之后，得到平均運行時間和最優目標值如表5、表6所示，同時得到兩種算法不同目標函數的收斂圖，如圖5、圖6所示。

由表5可知，改進NSGAⅡ的平均時間用時更少，并且兩種算法都在5 min內完成，符合現實條件。由表6可知改進算法在時間開銷上還能夠降低5.9%，配送時間更短。

表5 平均運行時間Table 5 Average running time

表6 最優值對比 Table 6 Optimal value contrast

圖5 最晚服務結束時間收斂圖Fig.5 Convergence graph of latest service end time

圖6 需求未滿足率收斂圖 Fig.6 Convergence graph of unsatisfactory rate of demand

由圖5可知改進NSGA Ⅱ相比一般NSGA Ⅱ，雖然在收斂速度不占優，卻能夠進一步縮短最晚服務結束時間，提高救援物資配送效率。由圖6可知改進NSGA Ⅱ得到的需求未滿足率雖然與一般NSGA Ⅱ相同，但是迭代收斂速度更快。實驗證明兩種算法均有效，改進NSGAⅡ能夠提供比一般NSGAⅡ時間更少，選擇更多的應急救援物資配送路徑。

4 結論

突發事件發生后，選擇最優應急救援物資配送路徑提高物資配送的效率和效果，是應急決策者面臨的主要問題。將最遲服務結束時間和需求未滿足率作為目標，考慮實際情況下道路對車型的限制，如道路因受損或道路本身結構如橋梁、窄道等，僅允許某特定類型車輛通過。災害發生后，部分道路損毀導致路段完全無法通行，需要對部分道路進行搶修，提高配送的效率。災害發生后，通行路段存在一定的安全風險，在實際情況中需要考慮道路的可靠性。據此建立多目標應急救援物資配送優化模型。設計優先鄰點交叉算子對 NSGA-Ⅱ算法提高全局搜索能力和減少運行時間，通過仿真對比試驗驗證模型和算法的有效性，為決策者選擇最優路徑提供決策依據。