趙建有， 肖 宇， 朱欣媛， 趙 陽,4

(1.長安大學 汽車學院，西安710064；2.長安大學 運輸工程學院，西安710064；3.比亞迪汽車有限公司，西安710119;4.長安大學 基建處，西安 710064)

近年來，各種大型突發(fā)自然災害在世界各地頻頻爆發(fā)，2008年發(fā)生在中國大范圍地區(qū)的低溫、雨雪、冰凍等自然災害，直接經濟損失達到537.9億元。據文獻[1]數(shù)據報道，同年的汶川大地震，受災總人口達4 625.6萬人，造成8 451.4億元的重大經濟損失；2013年雅安蘆山地震累計造成231余萬人受災，受災面積達12 500 km2。2021年7月，河南省中北部出現(xiàn)大暴雨，致使1 366.43萬人受災，直接經濟損失885.34億元。這些突發(fā)災害通常都伴有極大的破壞性和重大的人員傷亡，帶來了巨大的經濟損失，因此必須及時采取有效的救援措施，做好應急救援物資配送工作，才能幫助災區(qū)人民盡快恢復正常的秩序和生產生活。

應急車輛路徑優(yōu)化問題是應急物資配送的核心，是提高應急能力與提升災后救援工作水平的重要保障，在有限的時間和資源下，實現(xiàn)應急車輛合理的路徑規(guī)劃成為了國內外學者致力于研究的問題。在應急路徑優(yōu)化模型目標函數(shù)構建方面，文獻[2]研究了災害應急處置中協(xié)調物流供應和疏散行動的選址分配集成問題，指出突發(fā)事件情況下的物流計劃需要包括應急資源的調運方案以及傷員的疏散和轉移方案。文獻[3]量化了洪水影響和所需物資數(shù)量，建立了一個以庫存容量、物資需求時間等為約束的多目標應急物流規(guī)劃模型。文獻[4]將時間滿意度最大作為目標，建立了應急物流配送車輛調度模型。文獻[5]提出了一種考慮應急救援車輛的調度費用成本和應急救援車輛的路徑在途行程時間的雙層規(guī)劃的集成優(yōu)化模型?？梢钥闯觯⒍嗄繕说膽蔽锪饕?guī)劃模型可以更加準確地描述應急救援過程中的實際問題。

在求解算法方面，主要求解方法有蟻群算法[6]、布谷鳥算法[7-8]、遺傳算法[9]以及模擬退火算法[10]等啟發(fā)式算法。文獻[11]對信息素蒸發(fā)系數(shù)進行改進，提高了蟻群算法的收斂性，能夠快速找到從待救援點到多個目標點的優(yōu)化路徑。文獻[12]使用路徑內搜索和路徑間搜索提出了一種離散布谷鳥算法，求解帶時間窗和同時取送貨的車輛路徑問題。文獻[13]結合了兩種類型的局部搜索和遺傳算子，提出了一種混合螢火蟲算法，提高了車輛路徑問題解的質量。因此通過改進算法或進行不同算法的組合，可以明顯地提高解的質量以及收斂速度。文獻[14]針對重大疫情初期各地區(qū)對醫(yī)用防護物資需求緊迫性的差異，總結了醫(yī)用防護物資需求特征，對醫(yī)用防護物資需求緊迫度相關指標進行了量化。

上述研究主要考慮救援的時效性和配送成本，較少考慮到各受災點的受災情況以及物資需求差異性，因此在突發(fā)災害情況下，針對應急車輛路徑優(yōu)化問題進行研究，本文引入受災點緊迫度量化及分級，盡可能優(yōu)先配送受災點需求緊迫度高的地區(qū)，尋找在約束條件內最優(yōu)的路徑規(guī)劃方案，并設計相應的求解算法，可以為決策者提供決策依據，達到應急救援的快速響應、高效合理的目標，減少突發(fā)事件造成的損失。

1 問題描述與假設

1.1 問題描述

突發(fā)災害的發(fā)生對受災地區(qū)資源環(huán)境和人員安全與生活造成嚴重危害，具有影響范圍廣、影響程度深的特點，由于區(qū)域內各受災點的地理位置和需求情況存在一定的無規(guī)律性，需要制定合理高效的應急車輛路徑方案，才能及時地為各受災點運送救援物資。本文所研究的問題可以描述為：物資保障部門在對應急物資進行匯總整理后，利用不同編隊數(shù)量的車隊將應急物資由集中供應點配送到各物資配送中心，再運送至配送中心所轄的各受災點。其中，各車隊由物資配送中心出發(fā)，沿不同的規(guī)劃路徑，按照一定的運送順序為不同區(qū)域的若干受災點運送物資，并最終返回配送中心，形成一條完整的配送路徑，在配送過程中考慮受災點需求緊迫度、車輛隨機行駛時間等條件，使得整個救援過程中的總時間最少、總費用最低、緊迫度排序指數(shù)最大，其示意圖如圖1所示。

圖1 車輛路徑問題示意圖

1.2 問題假設

為方便進行后續(xù)研究工作的展開，對車輛路徑問題作出以下相關假設：1)已知應急救援中應急車輛的額定裝載量和平均速度，且保持不變，不考慮在救援過程中車輛的維護成本和維護時間；2)各受災點的需求量小于應急車輛的額定裝載量，且供應點的物資儲備量可以滿足所有受災點的需求，且有足夠的應急車輛來完成救援任務；3)應急車輛在一個閉環(huán)行程中不能多次訪問同一受災點，每個受災點至少被應急車輛訪問一次；4)從某一應急物資配送中心出發(fā)的車輛，完成運輸任務后，仍需返回至起點。

2 多目標模型構建

應急車輛路徑優(yōu)化問題受多種因素共同影響，由于應急物資來自多方途徑，需要運送的受災點較為分散，因此應急車輛路徑優(yōu)化模型的主要解決目標是盡可能地縮小救援過程耗費的時間和資金，并需要考慮受災點受災情況的差異，及時有力地保障受災群眾的物資供應。

應急救援所需總時間的長短直接影響到救援的時效性，將應急救援所需總時間按照救援過程進行劃分，總時間包括應急車輛從物資供應點到配送中心的時間、從配送中心運送至各個受災點再返回配送中心的時間以及裝載物資和卸載物資花費的時間。參考文獻[15]關于應急救援時間的定義，可將應急救援所需總時間表示為

(1)

應急救援所需總費用影響到救援的經濟成本，包括從物資供應點到配送中心的運輸費用、從配送中心運送至各個受災點再返回配送中心的運輸費用、車輛固定運營成本以及裝載物資和卸載物資花費的費用。應急救援所需總費用可表示為

(2)

各受災點的需求緊迫度綜合排序指數(shù)是指受災點的需求緊迫度與配送序列值的比值，當某受災點需求緊迫度越大，配送序列值越小時，該受災點越能接受優(yōu)先配送。因而模型最優(yōu)目標之一是各受災點緊迫度綜合排序指數(shù)之和最大，緊迫度綜合排序指數(shù)為

(3)

車輛路徑優(yōu)化模型為多目標優(yōu)化模型，考慮到目標函數(shù)包括3個優(yōu)化對象f1、f2和f3，且目標函數(shù)之間存在相互制約，因此模型求解的最終方案需要滿足多目標優(yōu)化效果整體最優(yōu)，而非每個目標個體最優(yōu)，選用線性加權的方法能夠很好地解決此類多目標優(yōu)化問題。對各個目標函數(shù)進行無量綱操作后，為每個目標函數(shù)分別添加權重系數(shù)，最終轉化為易于求解的單目標函數(shù)優(yōu)化問題，進而目標函數(shù)可改寫為

(4)

式(4)中θ1,θ2,θ3∈[0,1],θ1+θ2+θ3=1，權重系數(shù)的取值應由應急管理決策者依據應急救援的實際情況分析確定。

約束條件為

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

式(5)表示應急車輛在節(jié)點之間的實際行駛時間，dae為受災點a到震源e的距離，b為受災點所在位置的震級，α、β、γ為不同路況下的折損系數(shù)；式(6)表示應急車輛從供應點運往各個應急物資配送中心的需求量之和，不超過其本身的最大裝載量，Qk為應急車輛k的額定裝載量，hb為物資配送中心b的物資儲備量；式(7)表示應急車輛從應急物資配送中心運往各個受災點的需求之和，不超過其本身的最大裝載量，qa為受災點a的需求量；式(8)表示應急物資配送中心之間不存在物資的流動；式(9)表示應急車輛在從供應點到應急物資配送中心道路上的行駛總時間，不超過車輛本身在勻速狀態(tài)下的最長運行時間，MaxDk為應急車輛k的最大行駛距離，v為應急車輛k的平均行駛速度；式(10)表示應急車輛在從應急物資配送中心到各個受災點的行駛總時間不超過車輛本身在勻速狀態(tài)下的最長運行時間；式(11)表示到達受災點a的應急車輛仍從受災點a出發(fā)，保證路徑的連續(xù)性；式(12)表示各個受災點物資需求量之和，等于所有應急物資配送中心總物資儲備量，hg為供應點g的應急物資儲備量；式(13)表示在一次交付過程中，每個受災點不能被同一應急車輛訪問兩次；式(14)表示從應急物資配送中心出發(fā)的所有應急車輛最終都返回至起點；式(15)表示每個受災點有且僅被應急車輛訪問一次；式(16)規(guī)定了變量的范圍。

3 算法設計

3.1 算法介紹

應急車輛路徑模型建立后，需要采取合適的算法求得最優(yōu)方案。布谷鳥算法由于參數(shù)較少因此結構簡單，全局尋優(yōu)能力較強，但萊維隨機飛行策略會造成全局更新的位置過于隨機，在迭代過程中不能滿足所有鳥巢位置都向當前最優(yōu)解的方向靠攏，導致收斂速度下降，收斂精度不足。同時，針對車輛路徑這類組合優(yōu)化問題，蟻群算法在魯棒性和求解速度方面具有較大優(yōu)勢，但存在結果為局部最優(yōu)而非全局最優(yōu)的問題。所以本文結合布谷鳥算法與蟻群算法的各自優(yōu)勢，將布谷鳥算法得到的最優(yōu)解作為蟻群算法的信息素初始分布，進而獲得最優(yōu)路徑，能夠避免蟻群算法在初期進行盲目搜索，縮短了求解時間，布谷鳥-蟻群組合算法的流程如圖2所示。

圖2 布谷鳥-蟻群組合算法流程圖

3.2 布谷鳥-蟻群組合算法設計

本文將布谷鳥算法和蟻群算法組合求解路徑優(yōu)化問題，具體改進措施為：1)因為求解的應急車輛路徑問題具有離散性，因此采用非負整數(shù)編碼，即將實數(shù)編碼個體的每一維元素映射成受災點的編號；2)合理運用布谷鳥算法中的萊維飛行策略，利用快速排序法，將更新后鳥巢位置中的各維度數(shù)據進行排序，把每個鳥巢各維度數(shù)據的索引位置映射成每個受災點的編號，編碼形式如圖3所示,將數(shù)據的連續(xù)性特征進行離散化處理，經過萊維策略更新后的鳥巢位置和受災點的映射關系見表1；3)根據文獻[16]的啟發(fā)，對在布谷鳥算法中對信息素啟發(fā)式因子α進行自適應更新，從而改進萊維飛行位置公式；4)在傳統(tǒng)蟻群算法中，啟發(fā)函數(shù)通常取為兩點間距離的倒數(shù)，但本文的優(yōu)化目標不僅與距離相關，還與下一節(jié)點的緊迫度系數(shù)相關，因此將啟發(fā)式函數(shù)改進為需求緊迫度與節(jié)點之間距離的比值，文獻[17]表明兩點間距離越短，可選擇的下一節(jié)點的需求緊迫度系數(shù)越高，蟻群選擇該路徑的概率就越大。

圖3 編碼形式示意圖

表1 快速排序法映射關系

4 案例分析

4.1 案例設計

本文以汶川地震為背景進行分析，參考文獻[18]的民政部救助標準，從環(huán)境因素、人口因素和物資需求3個方面確定需求緊迫度影響指標，采用基于灰色關聯(lián)-TOPSIS法的組合方法進行賦權，并使用SPSSAU軟件進行計算，得出10個受災較重地區(qū)的需求緊迫度，結果見表2。其余29個受災較輕地區(qū)數(shù)據不能完全獲得，因此通過文獻[19]中的地區(qū)人口、地理等客觀數(shù)據進行估算，需求緊迫度系數(shù)均取0.3。

表2 受災點相關信息

4.2 參數(shù)設定

4.3 結果分析

本文模型求解的運行環(huán)境是在英特爾i5 2.11 GHz, 四核八線程CPU，8 GB RAM Windows 10系統(tǒng)的計算機操作系統(tǒng)的計算機進行。按照上述數(shù)據以及相關參數(shù)，采用線性加權和的方法對模型中的多個目標進行處理，并與不考慮需求緊迫度的車輛路徑優(yōu)化模型求解結果進行對比。

依據論文設計的改進的布谷鳥-蟻群組合算法的步驟，基于MATLAB R2018a平臺，對應急車輛路徑優(yōu)化模型進行求解，根據以往文獻和經驗方法比較選取參數(shù)，得到最優(yōu)參數(shù)組合，其中最大迭代次數(shù)T取500，種群數(shù)目N取30，發(fā)現(xiàn)概率pa取0.3，信息素啟發(fā)式因子α取1，期望啟發(fā)因子β取2，信息素揮發(fā)系數(shù)ρ取0.3。在參數(shù)設置相同的條件下，分別運行布谷鳥算法、蟻群算法和改進后的組合算法，得到3種算法的收斂情況如圖4所示。盡管蟻群算法最先收斂，但是后期易陷入局部最優(yōu)，布谷鳥算法隨著迭代次數(shù)的增加，逐步得到全局最優(yōu)解，但收斂速度較為緩慢。改進后的布谷鳥-蟻群組合算法可以在保證收斂速度較快的前提下，較好地實現(xiàn)搜索全局最優(yōu)的目標，能夠彌補其他兩種算法的不足，驗證了模型的有效性。

圖4 算法收斂性對比

由于本文通過經緯度距離公式計算兩個受災點之間的距離，并將其作為相似性度量的公式。通過K-means算法得到的受災點聚類結果顯示，共需構建4個臨時應急物資配送中心，應急物資配送中心的位置以及受災點的劃分結果見表3。

表3 應急配送中心及受災點劃分結果

表4為突發(fā)事件下考慮緊迫度分級的應急車輛路徑優(yōu)化方案，其中，應急物資配送中心Ⅰ共需要兩輛應急車輛，均按照受災點緊迫程度進行配送；應急物資配送中心Ⅱ共需要3輛應急車輛，均優(yōu)先對需求緊迫度高的受災點進行了配送，既滿足了較少的運輸時間和運輸費用，也使得嚴重災區(qū)優(yōu)先得到應急物資；應急物資配送中心Ⅲ處于受到地震災害影響最嚴重的區(qū)域，物資需求量最大，應急救援任務最繁重，共需要7輛應急車輛，所有車輛全部遵守需求緊迫度大小進行配送，極大地保障了需求緊迫度高的受災點優(yōu)先獲取物資的現(xiàn)實要求；應急物資配送中心Ⅳ被劃分到的受災點數(shù)目較多，但由于各受災點受到地震的損害程度普遍較小，相應地對物資的需求量較小，在滿足緊迫度需求的前提下，共需要兩輛應急車輛進行物資的配送?？紤]需求緊迫度的應急車輛路徑規(guī)劃圖如圖5所示。

表4 考慮緊迫度的應急車輛路徑優(yōu)化結果

通過與不考慮需求緊迫度的應急車輛路徑方案相比，在加入需求緊迫度因子優(yōu)化后的應急車輛路徑模型在整個配送過程中，共需要運輸總時間為111.6 h，實際救援時間為42.7 h，花費4 028 559元，考慮需求緊迫度前后的各指標變化比例結果見表5。相較于不考慮需求緊迫度的方案，優(yōu)化方案的運輸總時間與成本分別增加1.92%和3.43%，同時緊迫度排序指數(shù)增加11.2%，表明考慮需求緊迫度的優(yōu)化方案能夠更加合理地按照受災點的緊迫程度運輸應急物資，驗證了模型的合理性，有助于滿足應急救援物資保障的現(xiàn)實要求，實現(xiàn)了物資配送過程中應急車輛路徑方案的合理優(yōu)化。

圖5 考慮緊迫度的應急車輛路徑規(guī)劃圖

表5 考慮需求緊迫度與不考慮緊迫度的方案結果對比

5 結 論

1)采用了K-means聚類算法確定了應急物資配送中心的選擇及受災點的劃分，引入需求緊迫度構建了多目標車輛路徑優(yōu)化模型，設計了布谷鳥-蟻群組合算法對模型進行優(yōu)化求解，能夠滿足突發(fā)災害下應急物資配送的時效性、經濟性與公平性。

2)算例結果表明所提出的優(yōu)化模型在物資運送的總時間和物資運送成本變化比例較小的同時，考慮了各受災點物資需求程度的差異性，極大提高了受災點需求緊迫度排序指數(shù)，實現(xiàn)了優(yōu)先配送需求緊迫度較高的受災點的目標需求。

3)由于受災點需求緊迫度受多種因素影響，因此需要進一步提取需求點特征，采用更為精確的量化方法計算受災點需求緊迫度，進而提升路徑優(yōu)化模型的實際應用效果將是今后的研究任務。