震后多時段應急物資聯合配送路徑優化研究

杜茂康,楊 單,陸 聰

(重慶郵電大學經濟管理學院,重慶 400065)

地震災害救援一直是中國應急救援的重中之重。中國共有23條地震帶,地震活動頻度高、強度大、震源淺、分布廣,是一個震災嚴重的國家。強度較大的地震如2008年汶川地震、2011年玉樹地震、2017年九寨溝地震和2022年瀘定地震等[1],都給人民生命安全和財產造成重大損失。完備的震后應急救援系統能夠極大限度地將災害造成的損失降至最低。地震救援具有時效性強的特點,越早投入救援力量和救援物資震后損失越小。因此,震后應急救援物資的及時合理配送一直是學者們研究的重要課題。

通常情況下,自然災害往往會伴隨一些破壞性較大的活動,災區內的交通設施可能會面臨癱瘓。在突發災害情景下,還需要從多方面對應急救災進行多種考慮。FIKAR等[2]提出了一個模擬優化的決策分析系統來滿足不同受災點的動態需求。閆森等[3]研究道路受損對應急物資配送的影響,考慮多種類物資和多中心配送。狄衛民等[4]綜合對災后道路損毀狀況、道路復雜程度及物資拆分等因素進行了研究。文獻[5-7]分別對災民心理影響、手機數據測算及次生災害等其他方面構建模型進行研究。趙建有等[8]將受災點進行區域劃分,以救援過程總時間最短和總費用最小為目標,在汶川地震背景下構建算例進行模型驗證。上述研究考慮了災后受災區域內道路受損情況,構建多目標模型以滿足不同的災民物資需求,但并未考慮特殊點位的特殊需求,如震中區域的時間窗要求。

在考慮受災區域內道路損毀狀況的同時,除了上述學者的研究,有部分學者嘗試通過設計劃分多個階段,根據損毀程度或多種目標劃分兩階段或是三階段進行問題求解。AHMADI等[9]在考慮道路損壞的情況下,設計一種隨機行程時間的兩階段隨機線性規劃。曲沖沖等[10]考慮時效性和物資分配的公平性,建立了多階段的應急配送中心選址-配送模型。張立等[11]將應急物資配送任務劃分多個周期進行求解考慮。上述文獻集中研究劃分多個階段的方式進行物資配送,能夠使物資配送流程更加合理規范,但由于涉及較廣,因而不能很好地突出受災道路損毀等重要影響因素。文獻[12-16]的研究主要解決了受災區域交通狀況受限情況下的物資高效配送問題,包括研究道路通行難易程度、道路修復及道路修復結合設施選址等有針對性的方法解決道路受限問題,但在交通運輸工具的選擇上過于單一,往往不能滿足災民需求。

本文在災后初期受災區道路受損程度不一情況下,結合實際中應急救援物資源源不斷從各地運至應急分配中心,且各受災點由于受災程度和次生災害影響會產生持續的物資需求的情況,研究物資規劃和及時配送問題。通過搶修力度及道路修復情況劃分時段進行物資配送,且考慮不同時段下受損道路的恢復狀況以滿足及時配送的需要。采用“車輛+直升機”的聯合配送方式,根據受災點受災道路嚴重程度使用不同的配送工具。在震中附近道路損壞嚴重區域使用直升機進行配送,其他道路受損但不影響通行的區域及道路修復區域采用車輛進行配送。為了及時更新配送路線以節省救援時間,本文構建多目標規劃模型,以救援物資需求配送總成本最小和總配送時間最短為目標,利用遺傳算法結合模擬退火算法對該模型進行求解。本研究可為災后初期應急救援物資的配送提供決策思路,以減少因突發災害造成的人員傷亡和經濟損失。

1 問題描述與模型構建

1.1 問題描述

地震災害發生后,需要及時向災區運送生活物資和醫療物資,緊緊把握救援“黃金72小時”。通常情況下,在地震災害發生后,交通運輸路網會因災害或次生災害遭到破壞,無法完成物資運送任務。因此,考慮采用“車輛+直升機”對災區進行聯合配送。對震中區域道路損毀嚴重、短時間內道路無法通行地區采用直升機進行配送;同時,在其他道路暢通區域采用卡車進行受災點的物資配送。隨著搶險力量的介入,道路修復通暢程度會加快。據此,提出時段劃分情景下考慮道路修復程度的應急物資配送方案。災后72 h將被平均劃分為3個時段,根據不同時段會出現不同的道路通暢情況,進行受災點的物資配送路徑優化。由于災害發生需要在最短時間內完成救援配送任務,因此首要約束目標考慮滿足所有受災點物資需求配送的總時間最小化,其次考慮應急物資配送方式的成本最小化,在聯合配送情況下達到高效合理運輸應急物資至受災點的目標。

根據道路通暢情況進行配送任務的分配,道路為L1通暢度時代表不影響車輛通行,道路為L2通暢度時代表此道路需要在災后t1時段才可恢復通行。據此,如圖1中L1區域中的點均可由救援車輛進行物資配送,其余點要由直升機配送;圖2表示多時段,原L2的點將被吸收至配送L1區域的后續點,另外點將延續使用直升機進行配送。

圖1 “救援車輛+直升機”聯合配送示意圖

圖2 多時段下聯合配送示意圖

1.2 問題假設

1)由于災害發生第一時間就會實施應急響應機制,信息會逐步完善,因此應急分撥中心位置和容量、受災點位置和需求已知。

2)根據衛星地圖等信息分析可知道路通暢程度。

3)假設應急救援所使用的供應商所提供的救援設備型號為同一型號。

4)雖然救援過程中道路損毀度不同所導致的救援設備行駛速度并非全程保持一致,但整個過程救援設備的平均行駛速度一定,載重容量已知。

5)救援設備完成配送后必須返回應急分撥中心。

6)由于應急救援初期以滿足主要的食品、藥品和醫療器材為主,因此不考慮其他多樣化物資種類,救援設備所配送的主要為應急物資包。

1.3 符號定義

參數和決策變量如表1所示。

表1 符號定義

1.4 數學模型

通過對現有相關文獻的研究發現,由于地震災害時效性較強,災后應急救援物資及其他應急設施越早抵達災區,災區受災群眾的生命健康就能越早得到保障,因災害遭受的損失就會越小。因此,第1個目標總配送時間f1為

(1)

其中:t1,t2,…,tn為不同時段(t1,t2,…,tn∈T),具體規定為在不同的時段,道路通暢度不同,每一時段代表24 h。t1表示震后24 h;t2表示震后48 h;t3表示震后72 h,tn表示震后24nh;其中,考慮救援車輛和直升機在不同時段配送方案中具有不同的卸貨時間tpk和tpz,如在第一時段配送方案下,救援車輛卸貨時間為tpk1,直升機卸貨時間為tpz1。即在時段背景下,救援車輛從分撥中心出發,首先到達所負責的車輛需求點i,完成卸貨任務后轉向下一個車輛需求點j,最后返回;同時救援直升機從分撥中心出發,到達救援需求急迫但道路損毀的直升機需求點i,完成卸貨任務后轉向下一個點j,最終返回分撥中心。

第2個目標考慮因應急配送而產生的成本f2,包括應急分撥中心的成本、救援車輛的成本及救援直升機的成本,即f2=C1+C2+C3。應急分撥中心的成本包括使用成本和人員工資費用等,設定F5Mh為決策變量,表示應急分撥中心h是否啟用。故應急分撥中心的成本C1為

(2)

救援設備的固定成本C2包括車輛的固定成本F1(租賃費、維護費等)以及直升機的固定成本(租賃費、駕駛員工資、維護費等)F3,故救援設備固定成本C2為

(3)

救援設備的運行成本C3包括救援卡車每公里運行成本F2及救援直升機每公里的飛行成本F4,故救援設備運行成本C3為

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

約束(6)表示救援設備r在到達某個物流網絡節點后必須從該物流網絡節點離開;約束(7)表示每個受災點僅獲得救援設備的一次配送,即要么救援車輛配送該點,要么救援直升機配送該點;約束(8)表示每個災區受限點僅被救援直升機配送1次;約束(9)確保救援設備從應急分撥中心出發,經過所負責的需求點完成配送任務后最終返回應急分撥中心;約束(10)表示應急分撥中心負責的受災點總需求不超過該中心的可用容量;約束(11)表示每條路線的受災點物資總需求量不超過該救援設備的最大容量。

2 遺傳模擬退火算法設計

對于多目標優化問題,傳統的求解方法已難以解決日漸復雜的多目標規劃問題。遺傳算法等啟發式算法逐漸成熟并被廣泛應用,但由于遺傳算法易早熟、早期個體差異較大,容易導致種群進化停滯。救援設備的聯合配送問題涉及路線更新和路線規劃等多個復雜方面,因此考慮將遺傳算法和模擬退火算法進行結合,充分發揮模擬退火算法的局部搜索能力和遺傳算法的全局搜索能力,克服遺傳算法的易早熟現象和模擬退火算法效率不高的問題。算法流程圖如圖3所示。具體操作步驟如下:

圖3 遺傳模擬退火算法流程圖

1)設置初始參數:群體個數n、交叉概率Pc、變異概率Pm、最大迭代次數i、初始溫度T和降溫系數α;

2)隨機生成初始救援設備路線方案,并計算每條路線;

3)經過輪盤賭選擇、交叉變異操作產生新的救援設備路徑方案;

4)計算新方案中某一片段的適應度值并與舊片段的適應度進行比較,若新片段適應度fe1>fe,則用新片段替換舊片段;否則,以min{1,exp(-ΔE/T)}>rand[0,1]的概率接收新片段或舍棄;

5)設置救援設備容量約束和路線片段約束條件,若不滿足約束條件則返回,繼續優化迭代;

6)設定算法終止條件,滿足一定迭代次數后算法終止,輸出最優解。

2.1 編碼方式

采用二維矩陣實數編碼方式進行染色體編碼,假設有3輛卡車和2架直升機進行配送任務,共需配送19個受災點,且染色體在初始化種群和變異交叉的過程中必須確保道路不暢的受災點只能分配給直升機來配送。道路不暢的受災點編號為2,3,5,7,8,編號為1,4,6,…等的為卡車配送點,可能的編碼方式如圖4所示。由于救援設備有相應的容量限制,因此,在子路徑劃分上必須按照容量限制進行譯碼。如卡車3的路徑可能是0-12-16-19-0和0-18-13-2-7-0。

圖4 時段對比方案

2.2 適應度函數

種群個體的適應度是由模型部分的目標函數通過計算得出,本文最優值函數為考慮時間和成本標準化處理后的加權,所以最優值越小適應度值越大。針對種群中的個體x,適應度函數應為

2.3 遺傳算子設計

1)選擇算子采用輪盤賭算法,通過個體被選擇的概率與其適應度成比例來確定選擇的幾率大小,輪盤賭算法是一種有放回的隨機抽樣選擇法,一般來說,適應度越大,選擇概率也越大。

2)交叉操作采用2點交叉的方式進行。如圖5所示,首先隨機配對種群中的個體,然后在所選擇的個體中隨機設置2個交叉點位,將所配對個體2個隨機交叉點位中的基因進行互換,所生成的即為新個體。但由于交叉點位隨機產生,因此互換后的2個個體中可能會存在相同的基因片段,對此采取映射的方法對相同基因進行消除。

圖5 交叉操作

3)變異方式采用兩點互易方法,包含2種變異策略。

策略a:首先對救援工具負責的點組進行變異操作,假設卡車1負責5個點,卡車2負責6個點,卡車3負責3個點,此時選擇卡車2和卡車3進行點組變異,即卡車1負責5個點,卡車2負責3個點,卡車3負責6個點,如圖6所示。

圖6 策略a示意

策略b:除了對救援工具所負責點組進行變異操作外,對點組內部也進行相應的變異操作。采用2點互易方式,隨機產生2個自然數并交換其對應的點值,如圖7所示。

圖7 策略b示意

4)將模擬退火算子引入遺傳算法中,設置算法終止條件。通過模擬退火算法中的降溫操作尋找全局最優解,并根據模擬退火算法中的Metropolis準則進行新解e1和原解e的適應度值比較,ΔE=fe1-fe,若ΔE>0,則新解將被接收,用新的解e1替換當前解e,若ΔE<0則按照min{1,exp(-ΔE/T)}>rand[0,1]的概率選擇接收或舍棄該解。

3 案例分析

3.1 算例設置

表3 配送中心與各受災點間的相對距離

表4 救援設備參數

圖8 震中區域需求點位置

3.2 算例結果與分析

將遺傳模擬退火算法的參數設置如下:群體個數N= 200,交叉概率= 0.8,變異概率= 0.06,最大迭代次數Gen = 300,初始溫度T0= 1 000,降溫系數= 0.99。由于地震災害具有很強的時效性,因此將最小配送總時間設置較高的權重,最優值為最小配送時間和最小成本經過標準化處理后進行加權的綜合考量。使用Python軟件進行傳統遺傳算法與本文遺傳-模擬退火算法(GA-SA算法)的對比求解,最優值的變化收斂情況如圖9所示。

圖9 算法迭代對比

由圖9可以看出,本文GA-SA算法相對于傳統遺傳算法收斂效果更好。圖10為第三時段下的結果路徑對比圖,通過表5與遺傳算法相比較,總配送成本降低了9.53%,配送總時間減少了7.03%,表明在考慮道路損毀修復的震后多時段應急物資配送背景下,本文算法具有更好的求解效果,所得出的路徑圖比傳統遺傳算法路徑圖更加合理,車輛分區規劃更加明確,配送時間更短。

表5 算法結果對比

圖10 第三時段下路徑對比

以第三時段下不同算法具體路徑方案為例,對表5中的路徑結果相關含義進行簡要闡述。第三時段下,表示有5輛車和1架直升飛機所各自負責的點,如第1輛車負責點為[9,2,1,3,19,15,…,12,6,5,4]中的[9,2,1],第2輛車負責點為[3,19,15,14,13],其他救援設備負責路徑與上述規劃相應,不再過多贅述。具體路徑方案如表6所示。

表6 第3時段下具體路徑方案

3.3 考慮時段情景分析

由于地震災害應急救援是一項時效性較強的工作,越短時間內完成配送任務越能夠救治更多的傷員,因此,對震后“黃金72小時”采取劃時段安排救援方案尤有必要。劃分時段的方法能夠及時獲取道路的通暢程度變化,及時對配送方案的路線進行更新,以更短的時間完成配送任務,提高應急救援物資配送的效率。為了驗證考慮時段因素情景下應急物資配送更有效率與否,本文對比了考慮時段和不考慮時段情景的結果,如表7所示。

表7 考慮時段和不考慮時段情景結果對比

通過對比發現,考慮時段情景下的應急物資配送任務在配送總時間上比不考慮時段情景下減少了6.33%;在配送總成本上比不考慮時段情景降低了18.9%。

本文方法將災后救援物資配送階段進行了時段劃分,考慮了道路通暢程度與震中位置關系,對震后一定時段及配送路徑方案進行設計,結合地震實例相關數據進行對比分析,驗證了本文算法及模型的有效性。

4 結 論

在震后應急物資配送情景下,本文以應急物資總配送時間最小為主,將最小化配送成本考慮在內,采取劃分多時段的方法對配送方案進行更新和優化。由于地震災害的強時效性,通過劃分時段的方法構建模型能夠提高救援物資配送效率,及時將抵達災區的救援物資送至需求點,避免資源的停滯浪費。將遺傳算法與模擬退火算法相結合對所構建模型進行求解,使用地震實例相關數據進行算例驗證和對比分析,得到以下結論。

1)考慮劃分時段的方式構建模型,更具有解決震害后物資配送問題的針對性,結合道路損毀條件,能夠為特定情景提供物資配送方案。

2)采用聯合配送的方式,不但能夠滿足一般受災點的物資需求,還能夠應對特殊情景下的需求,當僅依靠車輛無法到達時,聯合配送能夠提供一種更有效的解決方法。

3)混合算法優于傳統遺傳算法,具有更好的收斂性,在特定情景下能夠減少配送時間和降低配送成本,具有更強的實效性。

本文主要對震害后應急物資聯合配送進行研究,但未考慮次生災害造成的二次道路損害及需求量的動態變化等方面,這些方面還具有較大的研究空間,將成為后續研究的工作重點。

參考文獻/References：

[1] 馬亞偉,臧陽,韓顏顏,等.2022年震情述評[J].中國地震,2023,39(1):213-218.

MA Yawei,ZANG Yang,HAN Yanyan,et al.A review of seismicity in 2022[J].Earthquake Research in China,2023,39(1):213-218.

[2] FIKAR C,GRONALT M,HIRSCH P.A decision support system for coordinated disaster relief distribution[J].Expert Systems with Applications,2016,57:104-116.

[3] 閆森,齊金平,張儒.考慮道路受損的震后應急物資運輸路徑優化[J].科學技術與工程,2022,22(28):12598-12604.

YAN Sen,QI Jinping,ZHANG Ru.Optimization of the transportation route of emergency supplies after the earthquake considering the road damage[J].Science Technology and Engineering,2022,22(28):12598-12604.

[4] 狄衛民,張鵬閣,杜慧莉.考慮道路狀況的應急配發站啟用以及配送優化問題[J].中國安全生產科學技術,2020,16(9):12-17.

DI Weimin,ZHANG Pengge,DU Huili.Opening of emergency distribution stations and optimization of distribution considering road conditions[J].Journal of Safety Science and Technology,2020,16(9):12-17.

[5] 孟燕萍,申慢慢.考慮災后道路恢復情況下動態應急物資選址問題[J].重慶交通大學學報(自然科學版),2019,38(1):89-96.

MENG Yanping,SHEN Manman.Location of dynamic emergency materials in the case of road rehabilitation after disaster[J].Journal of Chongqing Jiaotong University(Natural Science),2019,38(1):89-96.

[6] 張夢玲,王晶,黃鈞,等.基于手機定位數據的突發事件下道路修復和物資配送集成優化研究[J].中國管理科學,2021,29(3):133-142.

ZHANG Mengling,WANG Jing,HUANG Jun,et al.Research on the integrated optimization of road repair and relief distribution based on mobile phone location data[J].Chinese Journal of Management Science,2021,29(3):133-142.

[7] 譚潔,李文莉,劉康康.考慮二次災害的開放式應急物流車輛路徑問題[J].系統工程,2021,39(2):61-71.

TAN Jie,LI Wenli,LIU Kangkang.The open vehicle routing problem of emergency logistics considering secondary disasters[J].Systems Engineering,2021,39(2):61-71.

[8] 趙建有,肖宇,朱欣媛,等.考慮需求緊迫度的應急車輛路徑優化方法[J].哈爾濱工業大學學報,2022,54(9):27-34.

ZHAO Jianyou,XIAO Yu,ZHU Xinyuan,et al.Route optimization method for emergency vehicles considering demand urgency[J].Journal of Harbin Institute of Technology,2022,54(9):27-34.

[9] AHMADI M,SEIFI A,TOOTOONI B.A humanitarian logistics model for disaster relief operation considering network failure and standard relief time:A case study on San Francisco district[J].Transportation Research Part E:Logistics and Transportation Review,2015,75:145-163.

[10] 曲沖沖,王晶,黃鈞,等.考慮時效與公平性的震后應急物資動態配送優化研究[J].中國管理科學,2018,26(6):178-187.

QU Chongchong,WANG Jing,HUANG Jun,et al.Dynamic emergency materials distribution optimization with timeliness and fairness objective for post-earthquake emergency rescue[J].Chinese Journal of Management Science,2018,26(6):178-187.

[11] 張立,賀明玲,尹秋霜,等.不確定條件下多周期應急物資配送優化研究[J].系統仿真學報,2023,35(8):1669-1680.

ZHANG Li,HE Mingling,YIN Qiushuang,et al.Research on period emergency supply distribution optimization under uncertainty[J].Journal of System Simulation,2023,35(8):1669-1680.

[12] 韓孟宜,丁俊武,陳夢覃,等.基于混合遺傳算法的應急物資配送路徑優化[J].科學技術與工程,2021,21(22):9432-9439.

HAN Mengyi,DING Junwu,CHEN Mengqin,et al.Optimization of emergency material distribution path based on hybrid genetic algorithm[J].Science Technology and Engineering,2021,21(22):9432-9439.

[13] 譚印,朱蕓蕓,蘇雯潔,等.多目標應急物流雙向配送的關聯反饋模型仿真[J].計算機仿真,2023,40(4):134-138.

TAN Yin,ZHU Yunyun,SU Wenjie,et al.Simulation of correlation feedback model of multi-objective emergency logistics[J].Computer Simulation,2023,40(4):134-138.

[14] 李卓,李引珍,李文霞.應急物資運輸路徑多目標優化模型及求解算法[J].計算機應用,2019,39(9):2765-2771.

LI Zhuo,LI Yinzhen,LI Wenxia.Multi-objective optimization model and solution algorithm for emergency material transportation path[J].Journal of Computer Applications,2019,39(9):2765-2771.

[16] 孫華麗,李澤平,馬騰.道路修復聯合應急設施選址-路徑魯棒優化研究[J].系統工程理論與實踐,2023,43(9):2701-2713.

SUN Huali,LI Zeping,MA Teng.Robust optimization of joint road restoration and emergency location-routing[J].Systems Engineering-Theory &Practice,2023,43(9):2701-2713.

[18] 沈曉冰,楊保華.基于雙層混合聯運的震后應急物資配送模糊多目標優化[J].工業工程,2017,20(3):113-117.

SHEN Xiaobing,YANG Baohua.A fuzzy multi-objective optimization of post-earthquake emergency logistics systems based on bi-level programming and mixed transportation[J].Industrial Engineering Journal,2017,20(3):113-117.

[19] HU Shaolong,HAN Chuanfeng,DONG Z S,et al.A multi-stage stochastic programming model for relief distribution considering the state of road network[J].Transportation Research Part B:Methodological,2019,123:64-87.

[20] 薛星群,王旭坪,韓濤,等.考慮通行約束和運力限制的災后應急物資聯合調度優化研究[J].中國管理科學,2020,28(3):21-30.

XUE Xingqun,WANG Xuping,HAN Tao,et al.Study on joint dispatch optimization of emergency materials considering traffic constraints and capacity limits[J].Chinese Journal of Management Science,2020,28(3):21-30.

[21] 祁明亮,秦凱杰,趙琰.雪災救援物資車輛-直升機聯合運送的調度問題研究[J].中國管理科學,2014,22(3):59-67.

QI Mingliang,QIN Kaijie,ZHAO Yan.Research on problem of scheduling of helicopter coordinated with vehicle for resources distribution in snowstorm[J].Chinese Journal of Management Science,2014,22(3):59-67.

[22] 李雙琳,馬祖軍,鄭斌,等.震后初期應急物資配送的模糊多目標選址-多式聯運問題[J].中國管理科學,2013,21(2):144-151.

LI Shuanglin,MA Zujun,ZHENG Bin,et al.Fuzzy multi-objective location-multimodal transportation problem for relief delivery during the initial post-earthquake period[J].Chinese Journal of Management Science,2013,21(2):144-151.

[23] 唐悅琳.考慮道路損毀度的地震應急物流選址-路徑優化研究[D].重慶:重慶大學,2021.

TANG Yuelin.Research on Earthquake Emergency Logistics Location Routing Problem Considering Road Damage Degree[D].Chongqing:Chongqing University,2021.

[24] LIU Hongbin,SONG Guopeng,LIU Tianyu,et al.Multitask emergency logistics planning under multimodal transportation[J].Mathematics,2022,10(19).DOI:10.3390/math10193624.