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

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

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

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

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

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

1選擇研究問題的工具

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

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

2.1問題描述

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

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

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

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

（4）運輸過程中不損耗救災(zāi)物資;

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

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

2.2模型構(gòu)建

目標(biāo)函數(shù)的確定

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

約束條件分析

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

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

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

（3）個數(shù)限制

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

（4）算法過程

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

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

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

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

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

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

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

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

2.3求解結(jié)果

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

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

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

3結(jié)語

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

參考文獻(xiàn)

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

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

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