宋樹洋

（北京航空航天大學(xué)經(jīng)濟(jì)管理學(xué)院，中國(guó) 北京100000）

應(yīng)急物資的運(yùn)輸與配送問題是應(yīng)急物流主要研究的問題之一，它也是應(yīng)急物流中最為關(guān)鍵的一個(gè)環(huán)節(jié)，而在一般情況下，應(yīng)急物資調(diào)運(yùn)問題就會(huì)轉(zhuǎn)化成一般的車輛路徑問題。車輛路徑問題是一個(gè)典型的組合優(yōu)化問題，求解十分困難，截至當(dāng)下，僅有一些相對(duì)較小規(guī)模的問題能夠保證被求解到精確的最優(yōu)解。各國(guó)的學(xué)者通過大量的實(shí)踐和理論證明得出結(jié)論，精確算法在求解大規(guī)模VRP問題時(shí)非常不適合，而啟發(fā)式算法在求解這類問題時(shí)顯示出非常大的優(yōu)勢(shì)，并成為近年來此領(lǐng)域應(yīng)用最多的方法。其中遺傳算法以其優(yōu)秀的尋優(yōu)能力為眾多學(xué)者所青睞。

1 遺傳算法

遺傳算法(Genetic Algorithm，簡(jiǎn)稱GA)是由Holland教授首先提出的，它是一種建立在群體遺傳學(xué)基礎(chǔ)和自然選擇上的隨機(jī)、并行搜索算法。求解車輛調(diào)度問題，使用GA搜索算法十分理想，但使用GA算法時(shí)面臨的一個(gè)難以解決的問題就是如何防止其“早熟”收斂。

在遺傳算法提出以來，來自世界各地的眾多學(xué)者提出了多種方法提高GA的性能：Rudolhp G提出為保證算法的收斂性，使用精英選擇策略保持群體中最好個(gè)體的方法[1]；馬欣等提出了PEGA算法，即使用單親進(jìn)化的遺傳算法，它提高算法收斂速度的方法，是利用來自父體有效邊的信息，保留使用最小邊，這樣來進(jìn)行個(gè)體的進(jìn)化[2]；馬均水等提出大變異策略，這個(gè)策略可以表述為，如果某一代里的大多數(shù)個(gè)體集中在了一起，此時(shí)使用一個(gè)較大的變異概率（遠(yuǎn)大于通常）執(zhí)行一次變異操作，這樣使之獨(dú)立產(chǎn)生多個(gè)新個(gè)體，可以讓整個(gè)群體脫離早熟[3]；以上方法只解決了算法部分問題，而且采取的改進(jìn)方式比較復(fù)雜，一般以高運(yùn)算量并降低算法效率為代價(jià)解決遺傳算法過早收斂的問題。

遺傳算法優(yōu)化分析：

早熟收斂一直是遺傳算法中存在的主要問題，算法一旦出現(xiàn)早熟收斂，將無法得到問題的最優(yōu)解，這個(gè)問題主要原因是遺傳算法自身的優(yōu)化能力有限，不得不需要多次迭代才能夠找到最優(yōu)解，迭代過程中發(fā)生早熟將很難跳出。本文主要研究如何避免早熟收斂問題，下面將在交叉概率一定的(pc=0.8)的前提下進(jìn)行研究討論。

1）變異算子的改進(jìn)

對(duì)于遺傳算法易“早熟”的問題，其中主要原因之一是遺傳算法中最重要的遺傳算子——交叉算子使群體中的染色體具有局部相似性，從而會(huì)導(dǎo)致搜索停滯不前，因此變異算子的存在就變成克服算法早熟的最有效手段。

2）傳統(tǒng)變異算子的缺陷

定義1 在優(yōu)化問題求解過程中得到的最優(yōu)解，其對(duì)應(yīng)染色體上的每個(gè)基因稱為這個(gè)染色體基因位上的有效基因。

定義2 種群中，染色體同一個(gè)基因位上的等位基因具有多樣性，即染色體相同的基因位上既有“1”又有“0”，或者說在某一個(gè)基因位上，基因全為“1”(或“0”)的概率P(“1”)(或P(“0”))為：

P（“0”）或P（“1”）＝0 （1）

J.Craig Potts等人的研究得出結(jié)論，在GA搜索中，在遺傳算法運(yùn)行過程中發(fā)生早熟收斂的原因主要是有效等位基因缺失[4]。選擇策略的目的是在于加快基因的收斂過程，但是交叉算子作用于個(gè)體卻不可能產(chǎn)出新的基因，所以這無法避免地會(huì)使得在特定基因位上的某一類基因比例下降，最終會(huì)導(dǎo)致這個(gè)基因位上可能的有效基因的缺損。因此，為了預(yù)防早熟收斂，在不知道有效基因位的情形下，如果變異算子可以讓染色體統(tǒng)一基因位上保持等位基因的高多樣性，那么將極大地防止有效基因的缺失，進(jìn)而在最大程度上避免遺傳算法運(yùn)行過程中的早熟收斂。

定理1 一般方法使用的變異算子沒有辦法保證保持染色體同一基因位上等位基因的多樣性。

證明：在一個(gè)種群規(guī)模為N的種群中，如果假設(shè)在染色體的第j個(gè)基因位上有n1個(gè)“0”和n2(n2=N-n1)個(gè)“1”，那么這個(gè)基因位上的全部基因經(jīng)過變異操作（取反操作）后變?yōu)橥粋€(gè)基因的概率為：

此式與式（1）矛盾。

3）二元變異算子

一般來說，一般的變異算子作用是進(jìn)行的是一元操作（取反操作），即是操作數(shù)需要且僅需要一個(gè)基因。如果染色體是由二進(jìn)制字符串組成的，對(duì)于此類染色體，我們可以在遺傳算法搜索中引入數(shù)字技術(shù)里的二元邏輯算子，優(yōu)化傳統(tǒng)的變異方式，即產(chǎn)生了二元的變異算子：同或/異或。

此種變異操作與傳統(tǒng)的取反變異有所不同，這種變異操作中需要兩個(gè)個(gè)體（染色體）參與，例如：

從邏輯上容易知道，在這個(gè)運(yùn)算之后得到的兩種邏輯狀態(tài)是互補(bǔ)關(guān)系，即如果一個(gè)為“0”，另一個(gè)一定為“1”。換句話說在一個(gè)基因位上的基因經(jīng)過變異操作之后，這個(gè)基因位上至少有一個(gè)“0”和一個(gè)“1”同時(shí)存在，但是并不會(huì)出現(xiàn)都是“0”或者都是“1”的情況。

基于二元變異算子的遺傳算法流程與原遺傳算法流程相同，只在變異操作時(shí)有所區(qū)別。

2 應(yīng)急物資調(diào)度模型

2.1 問題的提出

應(yīng)急資源的調(diào)度需要考慮的問題有很多，其中包括運(yùn)輸工具的調(diào)度、運(yùn)輸路線的設(shè)計(jì)，還有資源調(diào)度的速度和效率。突發(fā)事件發(fā)生后，如果造成了大面積的受災(zāi)，救災(zāi)物資需求點(diǎn)的數(shù)量很多，那么在短時(shí)間內(nèi)制定出合理的物資配送計(jì)劃將會(huì)十分困難。

應(yīng)急資源調(diào)度問題可以抽象為圖1所示：

圖1 震后應(yīng)急資源調(diào)度問題抽象模型

2.2 問題情景描述

假設(shè)中國(guó)西南部某地發(fā)生了一定強(qiáng)度的地震，地震地帶處于山地丘陵地形內(nèi)，震后造成交通線路阻斷，圍繞震中形成了幾個(gè)受災(zāi)較為嚴(yán)重的區(qū)域，區(qū)域內(nèi)交通能力恢復(fù)迅速，區(qū)域與區(qū)域之間處于半隔離狀態(tài)。處于各受災(zāi)區(qū)域的政府救助力量迅速組織人員和工具分別進(jìn)行難民的搜尋和治療，并以最快的速度恢復(fù)通信能力，與上一級(jí)政府組織取得聯(lián)系并發(fā)出求救信息。上級(jí)地震災(zāi)害救助領(lǐng)導(dǎo)組織匯集各區(qū)域需求，利用空中設(shè)備(直升機(jī))將救災(zāi)物資空投至各區(qū)域，其中包括醫(yī)藥、食物、飲用水、救災(zāi)車輛及工具等具體物資，另各救災(zāi)區(qū)域內(nèi)的救災(zāi)應(yīng)急小組抓緊組織收集可利用的機(jī)動(dòng)性運(yùn)輸工具，在各區(qū)域內(nèi)形成配送中心，根據(jù)各需求點(diǎn)需求進(jìn)行救災(zāi)物資配送和傷員運(yùn)輸。

2.3 模型的建立

2.3.1 模型的假設(shè)條件

假設(shè)一：應(yīng)急資源調(diào)度中心與各物資需求點(diǎn)、各物資需求點(diǎn)之間的運(yùn)輸距離已知，可以作為常數(shù)。

假設(shè)二：受災(zāi)地點(diǎn)及各應(yīng)急資源調(diào)度中心根據(jù)其地理位置及交通便利情況完成最優(yōu)區(qū)域劃分，形成局部地震救災(zāi)單元，單元區(qū)域內(nèi)可以以最快速度進(jìn)行物資分配及救災(zāi)響應(yīng)。各單元地震災(zāi)區(qū)資源運(yùn)輸費(fèi)用有限可加，總和為地震總災(zāi)區(qū)資源調(diào)度費(fèi)用。

假設(shè)三：救災(zāi)物資運(yùn)送車輛所在停車場(chǎng)與應(yīng)急物資調(diào)度中心之間的距離可以忽略不計(jì)。

假設(shè)四：所有的需求點(diǎn)之間都可以相互通行，即此路徑網(wǎng)絡(luò)是完全路網(wǎng)。

假設(shè)五：所有的受災(zāi)地點(diǎn)的資源需求，在時(shí)間和數(shù)量方面都能夠得到滿足。

假設(shè)六：物資從調(diào)運(yùn)車輛上卸載的時(shí)間忽略，不予計(jì)算。

2.3.2 問題的數(shù)學(xué)模型描述

應(yīng)急資源車輛調(diào)度問題的數(shù)學(xué)模型可以概述如下：對(duì)于單一地震災(zāi)害救助單元，把各物資需求節(jié)點(diǎn)和應(yīng)急資源調(diào)度中心組成一個(gè)圖G(V,E)，其中V是圖中所有節(jié)點(diǎn)的集合，Vo∈V是應(yīng)急資源調(diào)度中心，其余節(jié)點(diǎn)為物資需求節(jié)點(diǎn)；E為圖中所有邊的集合，eij∈E為節(jié)點(diǎn)i，j之間的邊，圖G為無向圖，即邊eij是無方向的。有n個(gè)受災(zāi)地向救災(zāi)指揮中心請(qǐng)求物資配送，物資儲(chǔ)備中心與受災(zāi)節(jié)點(diǎn)、受災(zāi)節(jié)點(diǎn)之間的廣義運(yùn)輸費(fèi)用(距離)為Cij(i，j=0，1，2，…，n)，物資儲(chǔ)備中心編號(hào)為0，受災(zāi)節(jié)點(diǎn)編號(hào)為1到n，要求為各地震應(yīng)急救助區(qū)域指派運(yùn)輸車輛k，并確定車輛運(yùn)輸路線，使得總運(yùn)輸費(fèi)用最低。

對(duì)于模型圖中的每條弧(i，j)(i≠j)和車輛k定義變量Xijk：

應(yīng)急資源調(diào)度模型如下：

目標(biāo)函數(shù)：

以上數(shù)學(xué)模型中各表達(dá)式含義如下：

式（3）此式為目標(biāo)函數(shù)，其表示總的路徑代價(jià)(運(yùn)輸費(fèi)用、距離或時(shí)間)最低；

式（4）保證了有且僅有一輛物資配給車輛從物資配送中心出發(fā)；

式（5）保證了每個(gè)物資需求點(diǎn)凈流量為0；

式（6）保證了有且只有一輛物資配給車輛最終回到調(diào)度中心。

2.4 模型求解

根據(jù)前面已經(jīng)建立的應(yīng)急物流車輛調(diào)度數(shù)學(xué)模型，可將此問題進(jìn)一步描述如下：在各地震救災(zāi)單元區(qū)域內(nèi)，從配送中心派出車輛進(jìn)行救災(zāi)，每一輛車可為若干受災(zāi)點(diǎn)載送物資，車輛行駛路徑應(yīng)保證是距離最短的那條，最終要求出總消耗最低的路徑線路和最低費(fèi)用(距離)。

2.4.1 求解步驟描述

遺傳算法優(yōu)化算法(GA-plus)在求解應(yīng)急資源調(diào)度問題時(shí)的基本步驟如下：

Step1：設(shè)定初始參數(shù)。主要是遺傳迭代次數(shù)、初始種群大小、交叉和變異概率；

Step2：隨機(jī)產(chǎn)生初始種群，利用適應(yīng)度函數(shù)計(jì)算種群適應(yīng)度；

Step3：根據(jù)適應(yīng)度按輪盤賭方法和最佳個(gè)體復(fù)制選擇下一代染色體；

Step4：根據(jù)交叉概率，對(duì)染色體（候選解）進(jìn)行順序交叉操作；

Step5：根據(jù)變異概率，對(duì)染色體（候選解）進(jìn)行變異操作(二元變異)；

Step6：產(chǎn)生新的種群，利用適應(yīng)度函數(shù)計(jì)算種群適應(yīng)度，記錄新種群中的最佳個(gè)體；

Step7：判斷是否滿足遺傳算法迭代次數(shù)，若滿足則停止并輸出優(yōu)化結(jié)果，否則轉(zhuǎn)Step2對(duì)新種群繼續(xù)操作。

2.4.2 案例分析

本文采用Matlab編程，對(duì)有30個(gè)節(jié)點(diǎn)、50個(gè)節(jié)點(diǎn)和75個(gè)節(jié)點(diǎn)三種情況進(jìn)行試驗(yàn)分析。

（1）30節(jié)點(diǎn)時(shí)

各算法參數(shù)設(shè)置為：

GA迭代步數(shù)為2000，種群規(guī)模為100，交叉概率為0.8，變異概率為0.2；

GA-plus迭代步數(shù)為2000，種群規(guī)模為100，交叉概率為0.8，變異概率為0.2。

（2）50節(jié)點(diǎn)時(shí)

各算法參數(shù)設(shè)置為：

GA迭代步數(shù)為3000，種群規(guī)模為150，交叉概率為0.8，變異概率為0.2；

GA-plus迭代步數(shù)為3000，種群規(guī)模為150，交叉概率為0.8，變異概率為0.2。

（3）75節(jié)點(diǎn)時(shí)

各算法參數(shù)設(shè)置為：

GA迭代步數(shù)為7000，種群規(guī)模為200，交叉概率為0.8，變異概率為0.2；

GA-plus迭代步數(shù)為7000，種群規(guī)模為200，交叉概率為0.8，變異概率為0.2。

圖2 GA搜索結(jié)果

圖3 GA-plus搜索結(jié)果

圖4 GA搜索結(jié)果

圖5 GA-plus搜索結(jié)果

圖6 GA搜索結(jié)果

圖7 GA-plus搜索結(jié)果

3 結(jié)束語(yǔ)

通過實(shí)驗(yàn)過程以及以上圖示結(jié)果，可以對(duì)GA-plus優(yōu)化方法得出以下結(jié)論：

（1）GA-plus的全局優(yōu)化度相對(duì)較高，最終解顯示出更優(yōu)水平，并且平均優(yōu)化度也比較高；

（2）GA-plus的魯棒性強(qiáng)，趨于優(yōu)化解的概率較高；

（3）GA-plus的計(jì)算時(shí)間較長(zhǎng)，在算法效率上有待提高，但在一定程度上克服了過早收斂的早熟問題。

本文針對(duì)應(yīng)急物資調(diào)運(yùn)問題建立了數(shù)學(xué)模型，對(duì)模型求解過程中使用的啟發(fā)式算法進(jìn)行了優(yōu)化和改進(jìn)，實(shí)驗(yàn)結(jié)果表明改進(jìn)后的算法增強(qiáng)了對(duì)問題的求解能力，一定程度上克服了算法過早收斂的問題。本文對(duì)于應(yīng)急物資調(diào)運(yùn)問題的研究對(duì)于實(shí)際問題也具有借鑒意義

［1］Rudolph G. Convergence analysis of canonical genetic algorithms [J]. Neural Networks, IEEE Transactions on, 1994,5(1):96-101.

［2］馬欣,朱雙東,楊斐.旅行商問題(TSP)的一種改進(jìn)遺傳算法[J].計(jì)算機(jī)仿真,2003,4:36-37.

［3］馬鈞水,劉貴忠.改進(jìn)遺傳算法搜索性能的大變異操作[J].控制理論與應(yīng)用,1998,15(3):404-408.

［4］Potts J C, Giddens T D, Yadav S B. The development and evaluation of an improved genetic algorithm based on migration and artificial selection [J]. Systems,Man and Cybernetics, IEEE Transactions on, 1994,24(1):73-86.