基于遺傳算法的災后物資運輸選址與路徑優化

周雨晴 楊宇晴 陳曉陽 李曉倩 陳金志

摘? 要：本文以云南魯甸地震相關資料為依據，選取實際的地點作為研究個體，采用遺傳算法作為我們的求解方法，對個體的儲備物資應急配送進行研究和討論。在有限的時間、空間、資源等條件約束下，要使應急物資在最短的時間內到達災區，這就需要充分考慮救援物資的儲備地點和運輸路徑。本文主要考慮時間最短和成本最低兩個問題，基于數理建模和實際的限制條件構建雙路優化模型，從而選擇出最合適的物資儲存點和相對最短的運輸路徑。

關鍵詞：遺傳算法;選址;路徑優化;災后物資運輸;Matlab

地震是對人類造成最嚴重危害的自然災難之一，在我國西部地區（四川、云南等地）強震頻發，魯甸地震的發生給我國的人民帶來巨大災難。在2014年，我國大陸地區共發生5級以上地震22次，6級以上地震5次，集中發生在西部地區。其中，云南魯甸6.5級地震災害損失最為嚴重，是魯甸地區有歷史記載以來的最強地震，造成617人死亡，112人失蹤，大量城鄉房屋倒損，交通、通訊等基礎設施和學校、醫療衛生機構等公共服務設施遭受嚴重破壞，給當地群眾生產生活造成嚴重影響，直接經濟損失201.4億元（其中云南198.5億元、四川1.7億元、貴州1.2億元）。

儲備庫選址和路徑選優是實現災后快速救援的核心，而該問題也是近年來國內外學者研究的重點。本文的研究重點是選址—路徑兩步優化，即在選址優化的基礎上對其可能存在的路徑進行第二次優化。為此，我們研究了相關領域的優秀論文，探討其使用的方法和得到的結果。國內學者考慮到應急物資和遺傳算法的特點，限制條件的確定是否滿足實際情況和數學建模的要求，針對目標函數沒有明確的表達式或者在表達式極其復雜的情況，應用遺傳算法對變異算子和交換算子等的淘汰方式做了一定深度的研究。何勇指出災后的應急物資具有突然需要、復雜多變、時間緊迫、約束不一以及需求不確定等特點，很難一次性構建數學優化模型，所以采用了K-均值聚類算法和類子群算法來進行更優的計算。優化可以根據以下兩個方面進行：一、不同災情需求;二、不同約束條件，再進一步計算，分別與物資需求量較小和物資需求量較大兩種情況進行有效組合。李清等學者基于最短路問題，考慮到道路的可靠性，構建雙目標優化模型，一方面最小化道路起訖點間的長度，另一方面最大化道路的可靠性。采用NSGA-II多目標遺傳算法求解，在Matlab軟件下進行仿真實驗。分別得到三種情形下的解，開展2個目標的Pareto分析，剖析交叉概率和變異概率對結果的影響，有效地解決了最短和最可靠路徑的搜索問題。張成元根據選址理論研究的現狀和應急救援管理存在的問題，在結合應急物資儲備庫選址特征的基礎上，提出受災點需求權重問題、選址問題以及儲備庫分級問題，并分別構建相關模型，給出相應的求解方法。前人已經從震后儲存物資選址和救災路徑選優兩方面進行了研究分析，給我國的震后救援提供了極大的幫助和參考。

本文基于多個物資供應點的選擇和安全最短路徑兩個問題出發，進行縱向聯合研究。通過對我國西南地區災難頻發的地點進行應急資源的優化配置分析，驗證模型的可行性和可用性。

1選擇研究問題的工具

本文要解決的問題是最佳救災物資儲備庫選址及運輸路徑優化，煩瑣復雜的運算程序不利于對實際問題的解決，因此需要科學合理且簡單高效的工具輔助研究?？紤]到要將問題簡單化、運算清晰化、結果可視化，我們在多個應用軟件中通過比較界面舒適度、功能多樣性和運算精確度，選擇界面友好易懂、功能豐富強大、語言較為簡單的Matlab軟件作為本文研究問題的工具。

2選址-路徑優化模型

2.1問題描述

2014年云南魯甸6.5級地震發生后，根據災區急需，民政部協調北京、廣東、福建3?。ㄊ校┟裾d（局）向災區支援5萬條毛巾被、5000條毛毯、2.28萬套衣服、2500件短袖襯衣、2.4萬個手電簡和2000件雨衣。截至8月6日16時，云南省共接收社會救災捐贈款物合計人民幣23754.17萬元，其中資金14464萬元，物資折價9290.17萬元。（以上資料來自國家減災網http：//www.ndrcc.org.cn/）。在應急情況下的物資運輸是一項十分艱巨的任務，它考驗財力、物力以及人力等多方面的協同工作能力，災后的物資運輸更是需要與時間賽跑。本論文主要研究的是在災害發生后，如何快速準確的確定從哪個物資儲備庫最先發送救援物資以及應該在哪一條路徑上進行運輸，尤其是當一些路徑因為自然災害而不能及時通行時，同時需要做到成本最少，運輸最及時。為了實現科學的應急物資運輸規劃，將選址與路徑優化分為兩個步驟進行。第一步為選址，第二步為路徑優化。應急運輸對時效性有一定的要求，在建立模型時應有相應考慮和表達。整個過程有如下假設：

（1）為了避免過多不相關因素的干擾，起點與中轉點、中轉點與中轉點、中轉點與終點間的運輸距離用兩點之間的距離替代;

（2）災區需求量僅考慮最大化狀態，即一個合理固定值;

（3）運輸是單向的，即僅由儲備庫向受災點運輸物資;

（4）運輸過程中不損耗救災物資;

（5）時效性約束用最大允許運輸次數來表示;

（6）每一次物資的運輸量都等于儲備庫的最大供給量。

2.2模型構建

目標函數的確定

i為儲備庫地點編號，s為點編號，n為點的個數。Fi表示第i個儲備庫建設及運輸的固定成本，Vi表示第i個儲備庫的單位可變成本系數，D表示災區物資需求量，Si表示第i個儲備庫的最大供給量，Xs和Xs+1表示相鄰兩點的x坐標，Ys+1和Ys表示相鄰兩點的y坐標。minZ表示函數目標是使運輸成本最低，運輸時間最短。

約束條件分析

（1）編號規則限制

（2）運輸次數限制

A為最大允許運輸次數，運輸次數限制為時效性約束。

（3）個數限制

B為一個固定值，根據實際資料來給定。

（4）算法過程

根據實際資料數據建立一個匹配度較高的坐標圖，運用遺傳算法解決選址及路徑優化問題，使用Matlab軟件編寫程序進行求解運算。

第一，確定編碼。采用四位二進制數的編碼方式，將15個點從1到15依次編碼為0001—1111，把一條路徑用二進制數值來表示，位數長度L=28，表示時不足28位二進制數的，在路徑編碼中插入合適數量的虛擬點，編碼用0000填充，由于虛擬點在實際中并不存在，在計算距離時不予考慮;二進制數超過28位的路徑很顯然不滿足運輸時間最短的目標，直接予以剔除。

第二，產生初始種群。根據上述編碼，一條路徑就是一條染色體，路徑上的一個點即為一個基因，利用染色體編碼原理生成初始種群。種群規模不宜過大，取M=20～40即可。

第三，用適應度函數對種群個體進行評估。一代種群中的一個染色體即為一個個體，也就是一個可行解，本問題的適應度函數為：

minZ的值越小說明個體的適應性越好，對應的可行解越接近最優解。

第四，選擇。選擇的原則是優勝劣汰，優秀的個體獲得生存機會將基因遺傳給下一代。

第五，交叉。指定交換率Pc=0.43。

第六，變異。指定變異率Pm=0.05。

2.3求解結果

為便于理解和總結用如下表的方式來表達結果：

參考值為考慮問題中多方面因素結合目標函數得出的用于判斷結果優劣的數值，路徑的參考值越小表明此條路徑越優。

由以上圖表我們可以得出最佳選址點為圖1中的點3，優化后的路徑為3→9→11→13→15。通過相關資料可以找到對應的現實地址及運輸路徑，對應的最佳選址為廣州，路徑為廣州→桂林→貴陽→畢節→魯甸，此結果具有一定的實際意義。

3結語

本文利用遺傳算法對三個儲備庫（北京、廣東、福建）到達災區路徑的橫向對比，在已選定的三個運輸方案中選出了最佳解決方案，若其他條件滿足，可以利用此方案更快地將物資運送到災區并將受災人員快速的送到安全位置。

參考文獻

[1]何勇.應急救援物資配送模型及算法研究[D].廣東工業大學，2016.

[2]李清，胡志華.基于多目標遺傳算法的災后可靠路徑選擇[J].浙江大學學報（工學版），2016，50（01）：33—47.

[3]張成元.基于免疫算法和蟻群算法的應急物資儲備庫選址研究[D].吉林大學，2017.