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

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

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

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

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

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

1 問題描述與假設(shè)

1.1 問題描述

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

圖1 車輛路徑問題示意圖

1.2 問題假設(shè)

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

2 多目標(biāo)模型構(gòu)建

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

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

(1)

應(yīng)急救援所需總費(fèi)用影響到救援的經(jīng)濟(jì)成本，包括從物資供應(yīng)點(diǎn)到配送中心的運(yùn)輸費(fèi)用、從配送中心運(yùn)送至各個受災(zāi)點(diǎn)再返回配送中心的運(yùn)輸費(fèi)用、車輛固定運(yùn)營成本以及裝載物資和卸載物資花費(fèi)的費(fèi)用。應(yīng)急救援所需總費(fèi)用可表示為

(2)

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

(3)

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

(4)

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

約束條件為

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

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

3 算法設(shè)計

3.1 算法介紹

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

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

3.2 布谷鳥-蟻群組合算法設(shè)計

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

圖3 編碼形式示意圖

表1 快速排序法映射關(guān)系

4 案例分析

4.1 案例設(shè)計

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

表2 受災(zāi)點(diǎn)相關(guān)信息

4.2 參數(shù)設(shè)定

4.3 結(jié)果分析

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

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

圖4 算法收斂性對比

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

表3 應(yīng)急配送中心及受災(zāi)點(diǎn)劃分結(jié)果

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

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

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

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

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

5 結(jié) 論

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

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

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