考慮通行約束和運力限制的災后應急物資聯合調度優化研究

薛星群，王旭坪,2，韓 濤，阮俊虎

(1.大連理工大學商學院，遼寧 盤錦 124221；2.大連理工大學系統工程研究所，遼寧 大連 116024； 3.西北農林科技大學經濟管理學院，陜西 楊凌 712100)

1 引言

近年來環境問題日益嚴峻，自然災害頻發，比如2005年南亞大地震、2008年艾奧瓦洪災、2010年智利地震以及由地震引發的海嘯等，這些自然災害不僅使人們的財產受到損失，還危及人們的生命安全。在災后救援實施工作中，及時有效地向受災地區運輸救援物資有利于降低災區的受損程度。但是通常情況下，災害發生會使道路呈現出不同程度的損害致使救援工具無法到達被救援地區，這不利于應急工作的開展。而救援任務時間緊急，在此背景下，相對于之前單一救援工具，運用車輛-直升機聯合運輸救援物資逐漸成為對受災地點救助的主要應急方式[1-2]。

目前已有部分學者從單一救援工具的角度出發研究應急物資的運送問題。代穎等[3]考慮到車輛運載量的限制，為實現運送救援物資至各受災點的總時間最少，構建物資運輸點選址和車輛路徑安排集成優化模型，設計一種兩階段啟發式算法予以解決；詹沙磊和劉南[4]在研究多車型、多受災點應急物資的運送問題中，將貝葉斯分析和最優停止決策規則納入同一研究框架，通過建立貝葉斯風險函數解決實際問題；Mete和Zabinsky[5]根據地震后受災地區實況建立一種隨機優化方法來解決救援工具配送救援的醫療物資問題；Garrido等[6]為了在災澇后幫助決策者合理調度救援物資而設計出一種量化應急物資的庫存水平以及車輛可利用性的優化模型；Moreno等[7]研究出一種混合整數規劃啟發式方法來解決階段災害救援中車輛運力的重復使用問題；朱建明等[8]針對應急醫療物資的運輸問題，考慮到醫療物資到達醫院時間最小以及最大限度的滿足醫療物資所需，構造出改進的隨機算法進行模型求解。以上研究在應急物資運送模型構建的過程中，大部分只是針對車輛等陸地救援工具進行研究，關于多類型救援工具的研究相對較少。現實生活中，考慮到地震、海嘯等大規模自然災害實況，道路的流通性較差且余災時有發生，僅靠車輛無法對災區實施救援工作。因此，從多種類型救援工具的角度出發，Fikar等[9]研究了如何選取陸運和空運協調運輸中轉點等問題，根據仿真和優化方法設計出一種決策支持系統以應對最后一公里的救援物資的運輸問題；Zhou Chao等[10]針對突發情況設計出多智能體方法來予以應對。但是上述多類型救援工具下的決策系統和方法仍不能解決大規模受災的問題。為此，祁明亮等[11]以及阮俊虎等[12]分別采用直升機或者建立救援中轉點方式，分兩階段運輸救援物資以此處理道路受損情況下對難以進入救援區配送救援物資的問題，但是兩階段運輸物資會對救災時間產生影響，而且直升機在協同車輛幫助普通受災地區運輸物資的過程中剩余運力的使用率也不高。

多種運輸工具的聯合運輸物資在應對大規模災害的過程中發揮重要的作用。李雙琳等[13]設計出一種NSGAII來解決模糊需求條件下救援物資配送選址及多式聯運問題；Hu Zhihua[14]構建整數線性規劃模型進而改進了免疫算法,優化了救援網絡下的集裝箱多式聯運問題；鄭斌等[15]基于上下層的雙層規劃構建模型并設計出混合遺傳算法來解決物流選址及聯運問題。以上文獻大部分針對多種運輸工具能夠同時使用條件下的救援物資配送，但由于災后情況的多變性，應急救援決策也需要適時調整，此時運輸方式的選擇受到限制，上述多種運輸工具同時使用的條件也不能滿足。王旭坪等[16]在運力受限的條件下通過混合整數規劃模型并改進編碼方式來配置運力；Yi和?zdamar[17]通過設計的集成位置分布模型來解決撤離人員問題和應急物資的運輸問題。然而以有限運力為基礎的緊急決策是分階段的，而且運力的多次利用也具備約束性特點。Erdemir等[18]為了解決空運工具同陸地車輛聯合實施救助等問題，設計出一種位置覆蓋模型和貪婪啟發式算法；Ruan等[19]基于模糊C-均值聚類方法，考慮醫療救助點數量和容量限制約束，構建平衡的車輛聯運網絡和直升機來解決大型自然災害中的醫療物資多式聯運問題。但是上述研究沒有考慮運力的可重復利用，因此尚有可優化空間。

為了彌補上述研究的不足，我們將通行約束以及運力受限這兩個條件考慮在內，在災害造成通行受約束和救援工具數量有限的場景下，采用“車輛+直升機”的聯合運送方式，其中孤立的受災區只允許直升機到達，其他受災區車輛和直升機均能到達，考慮救援的經濟成本，對完成運送任務的運力重新進行救災任務分配，構建滿足災后救援物資聯合運送平均等待時間最短及決策體系總成本最低的優化模型，且基于帶精英策略的非支配排序遺傳算法(NSGA-II)改進了隨機鄰域搜索以及分級交叉，從而提出新的智能求解算法(NSHEA-II)，通過算例實驗表明，本文設計的算法在有限的時間內得到更優的Pareto前沿，能夠為不同偏好情況下的決策者提供更有效的調度方案。

2 模型構建

2.1 問題界定與模型假設

一般而言，災后救助使用直升機和車輛運輸救援物資。但是通常發生大規模災害時，通向受災地點的主要路徑受到阻礙或是中斷無法通行，由于道路疏通具有一定的時滯性或者短期內無法疏通，從而使一部分受困災點的救援物資運輸僅依賴高性能、運輸路線靈活的直升機來完成，即特殊受災點由直升機完成物資運輸，一般受災點依靠直升機的剩余運力和陸面救援車輛的的聯合運輸完成，具體運送路徑如圖1所示。同已有研究中直升機只進行孤立受災區救援物資運送不同的是，本文考慮了直升機可以利用其剩余運力來幫助地面車輛運輸救援物資至普通受災區，減少了救援時間，提高了所有運力的利用率。本文綜合考慮受災地區獲得救援的平均時間及應急決策體系下整體費用最小化這兩個決策目標，合理安排直升機和地面救援車輛運力以實現運輸應急物資至受災點的高效化。

圖1 “直升機+車輛”聯合運送示意圖

考慮到能及時調動的應急救助交通工具數量的限制性特點，一些直升機或是車輛救援工具可能會被反復派出進行多次物資的運送，假定一條子路徑代表救援時一次任務，那么一個救援工具的所有運輸路徑是由其全部運輸子路徑構成。災后，以集散中心作為起點，直升機以及救援車在完成一條子路徑的物資運輸后重返集散中心，然后進行下一次的物資配送直至任務完成。主要假設如下所述：

(1)假定決策系統中包含待通行約束的多個受災點，受災點的位置和兩兩受災點之間的距離已知；還包含一個物資集散中心。

(2)本文對物資分配和多樣化資源的配送不作細致性研究，所以認為物資集散中心的物資量充足而且種類單一，故救援工具僅運輸一種物資；

(3)遙感飛機能夠觀測到受災以后運輸物資的路徑狀態，因此受災點的種類以及所需救援資源的數量已知，并且各受災點僅能被訪問一次；

(4)假定能夠應急調度救援的直升機、車輛的裝載量和數量均已知，平均速度不變，運行時長不受限制，不考慮救援工具維護時間的限制。

2.2 符號定義

Di：節點i對救援物資的需求量；

dij：節點i到節點j的距離，且滿足dij=dji，i,j∈V；

Nk：配送工具k的子路徑集合；

Ck：配送工具k的單位距離運送成本；

Qk：配送工具k的容量上限；

si：配送工具在受災點i工作的時間，s0=0；

ck：配送工具k的固定成本費用

vk：配送工具k的平均速度；

其中(i,j)∈A,k∈K,n∈Nk；

2.3 數學模型

通過對已有的應急救援進行研究，我們發現災后救援物資的及時運輸以及救災的效果會受到救援效率的影響。救援物資(如醫療救護物資、電力物資等)的長時間匱乏不僅會錯失搶救傷亡人員的最佳時間，而且會給災民造成一定的心理恐慌，不利于應急救援工作的開展，所以本文將最小化受災地區等待物資運送的平均時間設定為第一個目標。

(1)

(2)

救援物資協同調度優化模型如下：

Minf1

(3)

Minf2

(4)

(5)

(6)

(7)

(8)

(9)

?i,j∈V,k∈K,n∈Nk

(10)

(11)

(12)

(13)

3 算法設計

割平面法和分支定界法是解決小規模整數規劃問題的主流方法，然而由于實際情況越來越復雜，一定的時間限制下難以求出精準算法的解，通常利用遺傳算法、模擬退火、粒子群算法等解決大規模調度問題以此提升運算效率。對于多目標優化問題，基于將多目標問題轉變為單目標問題的思路，通常采用極小極大法、約束法等方法，然而權重值以及所給目標的次序會對其產生影響。對此，根據上述設立的模型的復雜度，我們運用帶精英策略的非支配排序遺傳算法(NSGA-II)計算其解，另外對隨機鄰域搜索和分級交叉進行改進，構造出帶精英策略的非支配排序混合進化算法(NSHEA-II)，算法流程圖如下所示。

圖2 NSHEA-II算法流程圖

3.1 染色體編碼

我們采用二維矩陣實數編碼方式，行表示救援工具，列表示受災點的編號，為了滿足式(7)的條件，染色體在初始化以及鄰域操作的過程中始終確保帶通行約束的受災點僅分配給直升機的規則進行。假設有2架直升機，3輛卡車，20個受災點，且編號為1、2、3的受災點帶通行約束(矩陣中0在編碼和解碼時忽略)，則其可能的編碼方式如圖3所示。由于每個救援工具有裝載量限制，解碼時按照應急工具的載容上限劃分子路徑，如卡車2的子路徑可以是0-4-6-0和0-6-10-0。

圖3 染色體編碼圖

3.2 遺傳算子

這部分運用錦標賽選擇法，從種群中選取50%的染色體作為父代種群進行交叉和變異。

通過對模型分析，我們不但要對救援工具的種類進行確定，還要對救援路徑予以確定，以此獲得應急物資的聯合調度優化。而傳統帶精英策略的非支配排序遺傳算法中變異算子形式單一，對當前解易產生較大的不穩定性，對解的局部優化產生了負面影響，為了彌補傳統算法的不足，我們設立如下的鄰域結構：

變換1：將某一應急工具路徑中的一個節點插入到另一個應急工具路徑中。具體做法：首先在一個應急工具的路線中任意抽一個節點a，然后在該路徑中將節點a去除，接著查看該節點是否為帶通行約束，如果滿足條件那么將其放入直升機路徑，如果不滿足條件，隨意將其插入某個路徑。

變換2：交換某兩個應急工具路徑的節點。如果應急方式選擇的是一架直升機、一輛車，并且從直升機路徑中選帶通行約束的受災點，那么需要從直升機路徑中剩余點中選擇另外一個互換點，如果該直升機路經節點都是帶通行約束的節點，那么需要重新選擇路經。

變換3：優化某應急工具路徑內的兩路徑。在滿足總節點數大于3的應急工具路徑中任意選擇兩個節點a和b，a之前和b之后的路徑不做任何改變地加入至新路線，將a到b兩節點間的路線翻轉編號后加入至新的路線，從而優化現有路徑[20]。

變換4：交換一條應急路徑中的任意兩個受災點。在受災點數多于3的應急路徑中任意抽取兩點a和b，將a與b互換。

3.3 非支配排序

第一步：將種群內全部ni=0染色體存到集合z1中；

第二步：考慮目前集合z1中的任意染色體i所支配的染色體集合si，然后將si中的每條染色體k的nk變成nk=nk-1(處于支配地位的染色體i已經存到集合z1中)，如果更新后的nk=0，那么把k保存在另一個集合z2。

第三步：集合z1中的染色體處于支配地位不受其他染色體支配，把它們認定為第一級最優的非支配染色體集合，給集合z1中的染色體一個相等的非支配序ranki=1，接著對z2重復以上分級操作并給予相應的非支配序，直至全部個體都被分級。

3.4 擁擠度比較

為了得到均勻的Pareto最優解集，需要計算染色體的擁擠度。在非支配排序和擁擠度計算之后，每條染色體i都擁有兩個屬性：擁擠度disi和非支配序ranki。因此可得到擁擠度比較算子：任選兩條染色體i和j，如果染色體i所處的非支配層相對于染色體j所處的非支配層是占優的，即rankidisj，那么染色體i占優。染色體擁擠度的計算步驟如下：

第一步：初始化每條染色體的擁擠度disi=0；

第二步：將染色體按照f1和f2值排序，取最大的目標函數值fmax和最小的目標函數值fmin，把f1和f2的擁擠度設成無窮大；

第三步：運用式(13)計算其它染色體的擁擠度：

(14)

4 算例分析

我們將物資集散地的坐標設定成(50,50)，救災點的坐標信息在100100的平面內隨機生成，我們用歐氏距離描繪任意兩受災點間的距離。考慮通行以及運力受約束的情況，我們任選三個受災點作為帶通行約束的受災點，并設定存在2架直升機、3輛卡車，表1為應援工具參數，表2 為受災點信息。測試環境為Windows7操作系統，4GB內存，intel四核2.5GHz處理器，采用MATLAB 2015b編程算法。

4.1 算例測試結果

將NSHEA-II算法的參數設置為：染色體數目N=100，最大迭代次數Gmax=1000，最大鄰域搜索次數Cmax=10，交叉概率Pc=0.8，變異概率Pm=0.2。圖4和圖5描繪了算法的收斂效果，由圖4可知，初始種群的解分布有多個等級，具有許多可支配解，最少的平均等待時間是62分鐘，最低的經濟成本2719萬元。當達到最大迭代次數后，全部解均為非支配解，從而形成Pareto最優前沿。而圖5中平均等待時間最小值是39分鐘，最小的經濟成本是1770萬元，優化比例分別達到37.1%和34.9%。

表1 應援工具參數

表2 受災點信息

圖4 初始解分布圖

圖5 最終解分布圖

表3和表4為兩種目標下的Pareto最優方案。表3為決策者偏好系統的總經濟成本最小的最優方案，表4為受災點平均等待時間最短的最優方案。其中，路徑中的數字0代表初始點，括號內的數字表示從0時刻開始直至救援工具到達該受災點的等待時間，數值均向上取整。以表3為例，我們對調度路徑方案的含義進行簡要說明，在決策者偏好系統總經濟成本最小時，直升機1在第2分鐘到達受災點17完成運送任務，直升機2在第18分鐘到達受災點9，在第22分鐘到達受災點15，第35分鐘到達受災點2完成運送任務。卡車1有兩條運送路徑，第一條為0-16-12-5-1-6-0，第二條為0-3-0，卡車1完成第一條子路徑的運輸任務后才能向受災點3運輸救援物資，卡車1從0時刻開始直至到達受災點3需要242分鐘。剩余救援工具的具體調度方案解釋同上，不再贅述。帶通行約束的受災點2、9、17都由直升機負責運輸，符合式(7)。

表3 總成本最小

表4 平均等待時間最短

由圖5中Pareto前沿的兩端可以觀察到，兩個目標函數值并非呈等比例的反比關系，當犧牲很小一部分目標函數2時，可以大幅度優化目標函數1，反之亦然。當耗費的總經濟成本由1770萬元提高到1792萬元時，提升比例為1.24%，但受災點平均等待時間由86分鐘降低為58分鐘，下降比例為32.56%。由此可見，利用多目標進化算法得到Pareto最優解集是有效的，能夠為決策者提供科學的應急物資調度方案。

為了檢驗算法的優越性，我們將用NSGA-II算法對算例求出的結果同用本文提出的算法求出的結果進行比較，圖6顯示了采用兩種算法迭代到最大次數后得出的Pareto最優解集。根據圖6顯示的結果，我們可以看出，NSHEA-II的對應解集支配了NSGA-II的對應解集，NSHEA-II的尋優效果較大。運用NSGA-II求出的平均等待時間的最小值為46分鐘，經濟費用的最小值為1851萬元，而用NSHEA-II求出的最短平均等待時間為39分鐘，最小經濟成本為1770萬元，后者相對于前者的優化比例分別是15.2%、4.4%，因此，我們可以通過使用NSHEA-II制定更優的應急決策。

圖6 NSGA-II與NSHEA-II尋優效果對比

本文分別以受災點的平均等待時間最小化和應急體系下總經濟成本最小化為目標，將實驗重復進行10次，NSHEA-II和NSGA-II迭代到一定次數后得到的結果如圖7 所示。根據圖7顯示，在一定時間約束的情況下運用NSGA-II得出的兩個目標解不穩定，而運用NSHEA-II獲得的目標解的相對來說較穩定，主要因為改進后的算法確保了染色體的多樣性，并且多種鄰域搜索算子使NSHEA-II規避了算法容易收斂到局部最優的風險。

圖7 NSGA-II與NSHEA-II穩定性對比

本文構造出15組不同參數的算例以此檢驗算法的可行性，其中，num表示受災點數量、p表示帶通行約束的受災點數量、k1表示直升機數量、k2表示車輛數量。由表5可以看出，通過結果對比我們發現，相對于NSGA-II，NSHEA-II取得的結果較好。通過對15組算例的目標一和目標二變量的計算，我們發現相對于比NSGA-II，NSHEA-II提高了3.83%和4.41%的優化。另外，我們還得到如下結果：通過對比只有受災點量不同的算例我們發現，受災點的個數與最小平均等待時間和最低總成本費用存在正比關系；通過對比結果中滿足只有帶約束受災點數量不同的算例可以發現，在兩種算法的結果中，帶通行約束的受災點數量同應急網絡中的最小總成本成正相關，而與最短平均等待時間無明確的關系；通過對比結果中僅直升機數量不同的算例可知，直升機的數量同受災點最短平均等待時間成負向關，同最低成本費用呈正向關系；根據僅車輛數量不同的算例，我們認為車輛的數量與最短平均等待時間呈現微弱的負向關系，而與最低成本不具有明確的關系。

表5 NSGA-II與NSHEA-II計算結果對比

5 結語

基于多目標的大規模災害場景，我們分析了空運和陸運兩種救援方式聯合運輸的調度問題。由于救援工具運力受限，在帶通行約束的受災地區僅準許直升機運送物資，在這樣的條件下，本文將受災點平均等待時間最短以及工具調度總成本最小作為主要目標，制訂了決策者不同偏好情況下每架直升機和每輛卡車的救援路線，能夠在較短時間內生成“直升機+車輛”聯合調度方案，為特定災害應對情景提供物資運送方案。本文在構建模型求解的過程中，按照參考分級交叉構造出新的交叉算子，然后綜合使用多種鄰域算子設計出隨機鄰域搜索的變異算子，構造新的多目標求解算法。通過實驗檢驗，我們發現相對NSGA-II算法，NSHEA-II算法的結果更好，這對決策者制定相關應急決策具有一定的借鑒意義。

在后續的工作中，我們會考慮將受災點服務的公平性這一條件納入研究之中，也就是說，以平均等待時間最短為條件，在此基礎上考慮滿足各受災點等待服務的時間差異性最小條件，以此規避受災點等待物質運送的時間過長等風險，從而滿足實際要求。此外，隨著迭代次數的增多，本文設計的變異方法會減弱算法運行的速度，需要將算法的自適應性考慮在內。