馬麗榮，尹耀杰

(蘭州石化職業(yè)技術(shù)大學(xué)國際商務(wù)學(xué)院，甘肅 蘭州 730060)

近年來，甘肅遭受了多種自然災(zāi)害，如地震、滑坡、山體崩塌、雪災(zāi)、風(fēng)雹、低溫冷凍、洪澇、干旱、泥石流等，特別是低溫冷凍、洪澇、風(fēng)雹災(zāi)害最為頻繁，也最為嚴(yán)重，各種自然災(zāi)害給全省群眾生活及農(nóng)牧業(yè)生產(chǎn)造成嚴(yán)重的影響。2020 年，自然災(zāi)害共造成全省485.47 萬人次受災(zāi)；因災(zāi)遇難32 人、失蹤3 人；緊急轉(zhuǎn)移安置9.06 萬人；房屋倒塌3131戶、1.16 萬間，嚴(yán)重?fù)p壞9838戶、4.71 萬間，一般損壞2.92 萬戶、15.55 萬間；農(nóng)作物受災(zāi)396.33 千hm2，其中成災(zāi)250.65 千hm2，絕收33.41 千hm2。直接經(jīng)濟損失約337.32 億元[1]。自然災(zāi)害發(fā)生以后，提高政府部門對突發(fā)事件調(diào)控和應(yīng)對能力，保證應(yīng)急物資供應(yīng)和市場價格基本穩(wěn)定帶來了巨大的挑戰(zhàn)，應(yīng)急救援物資需要在有效的時間內(nèi)輸送到災(zāi)區(qū)，應(yīng)急物資的快速供應(yīng)直接關(guān)系到救援的成效。那么，災(zāi)后應(yīng)急物資如何及時有效的供應(yīng)，應(yīng)急物流設(shè)施如何定位，應(yīng)急物流配送路徑如何規(guī)劃等等問題，是應(yīng)急救災(zāi)工作急需研究的課題。應(yīng)急物流是應(yīng)急管理系統(tǒng)的重要組成部分，主要承擔(dān)應(yīng)急物資的儲備、運輸、配送及回收廢棄物的職責(zé)。

如何以最短路徑、高滿意度、最低成本等為目標(biāo)在最短的時間內(nèi)完成突發(fā)事件下應(yīng)急物資的配送，已成為國內(nèi)外學(xué)者高度關(guān)注的問題。李志等[2]研究了以物資分配公平性和需求效用最大化為目標(biāo)，建立基于多目標(biāo)的混合整數(shù)規(guī)劃方法應(yīng)急物資供應(yīng)點定位-分配模型；楊恩緣等[3]提出了以運輸成本最小為目標(biāo)，結(jié)合容量限制及應(yīng)急配送的多樣性和多級性特點，構(gòu)建了應(yīng)急物資多級配送選址-路徑的混合整數(shù)規(guī)劃模型；陳湉等[4]提出基于離散蜂群的災(zāi)害應(yīng)急物流車輛調(diào)度優(yōu)化問題研究，以供應(yīng)過量、物資分配不足所造成的損失最小化、車輛調(diào)度成本最低為優(yōu)化目標(biāo)，以服務(wù)時間窗和車輛運載能力為約束條件，構(gòu)建了應(yīng)急需求下的車輛調(diào)度優(yōu)化模型，并采用離散蜂群算法求解；張偉等[5]以運輸距離最短化、運輸時間最小化和路徑復(fù)雜性為目標(biāo)，建立多目標(biāo)應(yīng)急物流路徑規(guī)劃模型；蔣杰輝[6]利用改進(jìn)智能水滴算法求解應(yīng)急物資配送中車輛路徑優(yōu)化問題；朱娜[7]采用“矢量投影－理想點法”以車輛運載能力等為限制條件，以應(yīng)急運輸成本、應(yīng)急時間及救災(zāi)點數(shù)量為優(yōu)化目標(biāo)構(gòu)建了應(yīng)急物資分配模型；朱佳翔[8]等以運輸時間最少、成本最優(yōu)以及用戶滿意度最大等為目標(biāo)，構(gòu)建多階段多目標(biāo)應(yīng)急物流配送的灰色動態(tài)規(guī)劃模型。

1 問題的描述

車輛運輸路徑問題（VRPTW）是應(yīng)急物流研究的基本問題，也是實現(xiàn)在有限時間內(nèi)實現(xiàn)物資的及時送達(dá)，提高救援效率，將災(zāi)害降到最小化的有效途徑。文章針對甘肅應(yīng)急物流運輸與配送問題，構(gòu)建了以車輛數(shù)最少和路徑最短為目標(biāo)的車輛配送模型，設(shè)計遺傳算法對應(yīng)急物流配送路徑模型求解，兼顧考慮多個制約條件，如車輛載重量的限制，受災(zāi)點對物資需求時間窗的限制等。假設(shè)有多個配送中心對多個受災(zāi)點進(jìn)行應(yīng)急物資配送，配送中心有容量不同的車輛，受災(zāi)點對物資需求的時間各不相同，要求在規(guī)定的時間內(nèi)完成配送任務(wù)，規(guī)劃配送路線并要求每條路線上只有一輛車配送，規(guī)定車輛從配送中心出發(fā)完成配送任務(wù)后再返回配送中心，利用MATLAB 軟件編程求解，求出應(yīng)急物流低成本高效率的配送路徑最優(yōu)解。

2 構(gòu)建應(yīng)急物流配送路徑模型

2.1 模型參數(shù)與變量定義

N={0，1，…，n，n+1}是節(jié)點集合，0,n+1 表示配送中心，需求點編號為{1，…，n}；

di：需求點i 的需求量；

K={1，2，…，k}是車輛集合；

A：弧的集合；

xijk={0，1}，表示車輛k 是否從i 點出發(fā)前往j點，如果車輛k 是從i 點出發(fā)前往j 點，則xijk=1，否則xijk=0；

Cij：表示i 點和j 點之間的距離；

wik：表示車輛k 對i 點的開始服務(wù)時間；

si：表示受災(zāi)點i 的服務(wù)時間；

tij：表示從i 點到j(luò) 點的行駛時間；

Mij：一個足夠大的數(shù)，可以取10 的7 次方；

ai：受災(zāi)點i 的左時間窗；

bi：受災(zāi)點i 的右時間窗；

E：配送中心的左時間窗；

L：配送中心的右時間窗；

Ck：車輛k 最大裝載量；

s+(i)：表示從i 點出發(fā)的弧的集合；

s-(j)：表示回到j(luò) 點的弧的集合。

2.2 模型設(shè)計[9]

其中目標(biāo)函數(shù)（1）表示車輛使用數(shù)目最少和車輛行駛總距離最短，將這兩個目標(biāo)合為一個目標(biāo)表示配送成本最低；（2）～（10）是約束條件，（2）表示每個需求點只能被分配到一條配送路徑上；（3）表示每條配送線路上從配送中心出發(fā)只能前往一個需求點；（4）表示車輛k 在路徑上的流量限制；（5）表示車輛配送完畢都必須返回配送中心；（6）表示配送時間連續(xù)性；（7）表示需求點時間窗約束；（8）表示配送中心時間窗約束；（9）表示載重量約束；（10）表示變量取值的約束。

3 基于遺傳算法（GA）的應(yīng)急物流配送路徑模型求解

3.1 算法設(shè)計

3.1.1 編碼

在使用GA 求解VRPTW 問題時，可以采用整數(shù)編碼的形式對染色體進(jìn)行編碼，當(dāng)配送車輛數(shù)最多為K，且節(jié)點數(shù)目為N 時，染色體長度為N+K-1，那么表達(dá)該染色體的基本形式為（1，2，3，…，N，N+1，…，N+K-1）。

3.1.2 遺傳適應(yīng)度函數(shù)

當(dāng)編碼的解碼不能保證都滿足每條配送路線上對時間窗的約束和載重量的約束條件時，為了解決違反約束問題，那進(jìn)行求解時采用懲罰函數(shù)。構(gòu)建的懲罰函數(shù)如下：f(s)=c(s)+αq(s)+βw(s)，c(s)表示車輛總行駛距離，q(s)表示各條路徑違反的容量約束之和，w(s)表示所有顧客違反的時間窗約束之和。因為，違反容量約束相對來說不太容易，所以，將α 設(shè)為10，而較容易違反時間窗約束，所以，將β 設(shè)為100。

目標(biāo)函數(shù)值越小越優(yōu)越，因此，在選擇環(huán)節(jié)，將懲罰函數(shù)的倒數(shù)設(shè)置為適應(yīng)度函數(shù)，即為1/f(s)。

3.1.3 初始化種群

先構(gòu)建帶時間窗車輛路徑問題的初始解，再進(jìn)行初始化種群。

設(shè)節(jié)點數(shù)目為m。

第一步：任意選擇某一節(jié)點i∈{1，2，3，…，m}；

第二步：使用車輛數(shù)的初始化k=1；

第三步：遍歷節(jié)點生成序列Sq=[i，i+1，…，m，1，2，…，i-1]

第四步：遍歷節(jié)點j 至節(jié)點m，形成初始解。按序列Sq 遍歷節(jié)點Sq(j)，將節(jié)點Sq(j)添加到第q 條路徑中，在添加到對應(yīng)線路中時要考慮車輛的載重量和左時間窗的約束條件。

得到的初始解就是一個配送方案，通過將個體賦值的方式轉(zhuǎn)換為種群初始化。

3.1.4 選擇

從群體中選擇優(yōu)良個體來繁殖子代的過程，并進(jìn)行優(yōu)勝劣汰操作，通過基于適應(yīng)度的過程選擇個體解決方案，即從群體中選擇多個適應(yīng)度值大的個體進(jìn)行交叉、變異以及局部搜索過程。

3.1.5 交叉

交叉是指新的個體由兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成的。

3.1.6 變異變異過程是指子代染色體由父代染色體的這兩個位置上的基因互換形成的。

3.1.7 終止條件

遺傳算法具有隨機搜索特性，需要設(shè)置終止條件，以在可接受時間內(nèi)獲得最優(yōu)解。比如設(shè)置最大進(jìn)化次數(shù)為終止條件，或達(dá)到最大迭代數(shù)時終止算法運算，再如判斷種群適應(yīng)度值的收斂性，種群適應(yīng)度值不被繼續(xù)優(yōu)化時終止算法運算。

3.2 遺傳算法的運算流程

遺傳算法（GA）是借鑒生物界的進(jìn)化論，適者生存，優(yōu)勝劣汰的遺傳機制演化而來，是一種隨機化搜索全局尋優(yōu)的生物進(jìn)化過程算法，具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力，采用概率化的尋優(yōu)方法，能自動獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，使群體不斷進(jìn)化，逐漸接近最優(yōu)。GA 是解決VRPTW 問題的有效方法之一，在求解應(yīng)急物流配送模型中得到了廣泛的應(yīng)用[10]，如圖1所示。

圖1 遺傳算法流程圖

4 算例分析——以甘肅省定西漳縣和岷縣為例

甘肅省定西市漳縣和岷縣自古有“西控青海，南通巴蜀，東去三秦”之說，地處黃土梁峁地帶，山巒環(huán)抱，溝壑縱橫，是地震等自然災(zāi)害高發(fā)地區(qū)，自然災(zāi)害發(fā)生以后，災(zāi)區(qū)需求大量的應(yīng)急物資，由于災(zāi)區(qū)地形地貌的特殊性，嚴(yán)重影響了對應(yīng)急物資的配送，有必要在災(zāi)區(qū)附件設(shè)置臨時的應(yīng)急配送中心點，臨時應(yīng)急配送中心負(fù)責(zé)為附近的鄉(xiāng)鎮(zhèn)配送應(yīng)急物資。本文以定西市漳縣和岷縣為研究對象，兩縣共有31 個鄉(xiāng)鎮(zhèn)，利用奧維互動地圖查找到31 個鄉(xiāng)鎮(zhèn)的二維坐標(biāo)經(jīng)度和維度，在模型計算中受災(zāi)點的需求量是按照各鄉(xiāng)鎮(zhèn)人口數(shù)量、受災(zāi)程度等信息估計得到，在考慮配送距離和受災(zāi)點需求量的情況下構(gòu)建應(yīng)急物流選址模型，利用免疫算法優(yōu)化求解，采用MATLAB 軟件對設(shè)計進(jìn)行編程實現(xiàn)，見表1。

表1 甘肅省漳縣和岷縣各鄉(xiāng)鎮(zhèn)的數(shù)據(jù)資料

案例中，采用免疫算法確定了5 個鄉(xiāng)鎮(zhèn)為配送中心點，結(jié)果如圖2 所示。以這5 個配送中心點為出發(fā)點完成鄰近鄉(xiāng)鎮(zhèn)的配送路線規(guī)劃，采用MATLAB 軟件對設(shè)計的GA 算法進(jìn)行編程實現(xiàn)，程序運行時間短，計算效率較高，有效實現(xiàn)了在規(guī)定的時間內(nèi)應(yīng)急物流配送路徑規(guī)劃。軟件求解結(jié)果如圖3 所示，最優(yōu)配送路徑見表2。

圖2 應(yīng)急物流中心圖

圖3 配送路徑優(yōu)化圖

表2 多配送中心的配送路徑優(yōu)化結(jié)果

5 結(jié)語

文章針對配送中心如何向災(zāi)區(qū)配送應(yīng)急物資這一問題，提出了基于遺傳算法的應(yīng)急物流車輛配送路徑優(yōu)化方案，構(gòu)建了以車輛數(shù)最少和配送路徑最短為目標(biāo)，綜合目標(biāo)是以應(yīng)急物流成本最低為目標(biāo)，滿足多個約束條件下優(yōu)化問題模型，結(jié)合模型特點使用遺傳算法進(jìn)行求解。研究結(jié)果表明，遺傳算法能有效的解決應(yīng)急物流配送路徑問題，大大縮短應(yīng)急配送時間，節(jié)約成本，提升滿意度，提高配送效率。