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

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

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

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

地震是對人類造成最嚴重危害的自然災難之一，在我國西部地區(qū)（四川、云南等地）強震頻發(fā)，魯?shù)榈卣鸬陌l(fā)生給我國的人民帶來巨大災難。在2014年，我國大陸地區(qū)共發(fā)生5級以上地震22次，6級以上地震5次，集中發(fā)生在西部地區(qū)。其中，云南魯?shù)?.5級地震災害損失最為嚴重，是魯?shù)榈貐^(qū)有歷史記載以來的最強地震，造成617人死亡，112人失蹤，大量城鄉(xiāng)房屋倒損，交通、通訊等基礎設施和學校、醫(yī)療衛(wèi)生機構(gòu)等公共服務設施遭受嚴重破壞，給當?shù)厝罕娚a(chǎn)生活造成嚴重影響，直接經(jīng)濟損失201.4億元（其中云南198.5億元、四川1.7億元、貴州1.2億元）。

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

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

1選擇研究問題的工具

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

2選址-路徑優(yōu)化模型

2.1問題描述

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

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

（2）災區(qū)需求量僅考慮最大化狀態(tài)，即一個合理固定值;

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

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

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

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

2.2模型構(gòu)建

目標函數(shù)的確定

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

約束條件分析

（1）編號規(guī)則限制

（2）運輸次數(shù)限制

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

（3）個數(shù)限制

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

（4）算法過程

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

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

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

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

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

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

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

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

2.3求解結(jié)果

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

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

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

3結(jié)語

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

參考文獻

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

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

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