姚衛(wèi)粉

摘要：通過(guò)對(duì)車(chē)輛路徑問(wèn)題的分析，建立車(chē)輛路徑問(wèn)題數(shù)學(xué)模型。針對(duì)遺傳算法優(yōu)化車(chē)輛路徑問(wèn)題易陷入局部最優(yōu)解以及收斂速度慢等問(wèn)題，引入基于動(dòng)態(tài)小生境的協(xié)同進(jìn)化模型。最后，將動(dòng)態(tài)小生境協(xié)同進(jìn)化算法應(yīng)用于所建立的模型中。實(shí)驗(yàn)結(jié)果表明：動(dòng)態(tài)小生境協(xié)同進(jìn)化遺傳算法可有效避免遺傳算法的早熟現(xiàn)象，并在一定程度上提高優(yōu)化車(chē)輛路徑問(wèn)題的求解效率。

關(guān)鍵詞：車(chē)輛路徑問(wèn)題；協(xié)同進(jìn)化遺傳算法；動(dòng)態(tài)小生境；早熟

DOIDOI：10.11907/rjdk.143490

中圖分類(lèi)號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)文章編號(hào)：16727800（2015）001005702

0 引言

車(chē)輛路徑問(wèn)題（Vehicle Routing Problem，VRP）由Dantzig 和Ramser[1]于1959年第一次提出。該問(wèn)題是指在客戶(hù)需求位置已知的情況下，確定車(chē)輛在各客戶(hù)間的行程路線，然后使得車(chē)輛路線最短或運(yùn)輸成本最低。車(chē)輛路徑問(wèn)題是個(gè)NP難題，在尋找滿足約束條件最優(yōu)解的過(guò)程中，需要很大的設(shè)計(jì)空間。設(shè)計(jì)空間是多維而非連續(xù)的，所以用來(lái)系統(tǒng)的搜索整個(gè)空間的規(guī)范搜索集很難找到，導(dǎo)致很難得到全局最優(yōu)解。關(guān)于車(chē)輛路徑問(wèn)題的優(yōu)化算法大致可以分為兩類(lèi)，一類(lèi)是精確算法，另一類(lèi)是啟發(fā)式算法。目前，針對(duì)車(chē)輛路徑問(wèn)題，主要采用啟發(fā)式算法。比如，樹(shù)狀搜尋法[2]、節(jié)省法[3]、掃描法[4]、遺傳算法[5]等。由于精確算法難以用于求解復(fù)雜的車(chē)輛路徑問(wèn)題，而啟發(fā)式算法也只是基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，所以只能求出問(wèn)題的某一特殊類(lèi)型或者是規(guī)模較小時(shí)的近似最優(yōu)解。由于這些問(wèn)題的存在，本文將基于動(dòng)態(tài)小生境的協(xié)同進(jìn)化遺傳算法引入到車(chē)輛路徑問(wèn)題中，從而更好地解決車(chē)輛路徑優(yōu)化問(wèn)題。

1 車(chē)輛路徑問(wèn)題數(shù)學(xué)模型

對(duì)于單配送中心問(wèn)題，設(shè)配送中心共有N個(gè)客戶(hù)，1個(gè)中心倉(cāng)庫(kù)，K輛車(chē)。每個(gè)客戶(hù)的需求量和時(shí)間窗都有固定的限制，且均只被某輛車(chē)服務(wù)一次，每輛車(chē)只服務(wù)于一條路徑。每輛車(chē)載重為Q且從配送中心出發(fā)，服務(wù)所有客戶(hù)后回到配送中心。建立數(shù)學(xué)模型如下：

minZ=∑ni=0∑nj=0∑kk=1CijXijk（1）

∑ni=1qiyik≤Q；k=1，…，K（2）

∑Kk=1y0k=K（3）

∑Kk=1yik=1；i=1，…，n（4）

∑ni=1xi0k=1；k=1，…，K（5）

∑ni=0xijk=yjk；j=1，…n；k=1，…，K（6）

∑nj=0xijk=yik； i=1，…，n；k=1，…，K（7）

上述模型中，Z為運(yùn)輸距離；i，j為客戶(hù)編號(hào)；n為客戶(hù)量，k為車(chē)輛的順序；Cij為從點(diǎn)i到點(diǎn)j的費(fèi)用；xijk為1時(shí)，表示車(chē)輛從i出發(fā)到j(luò)，否則為0；需求點(diǎn)i的需求量為qi，yik為1時(shí)表示客戶(hù)i的任務(wù)由車(chē)輛k來(lái)完成，否則為0。

式（1）表示以運(yùn)行總成本最低的目標(biāo)函數(shù)；式（2）保證車(chē)輛裝載貨物的總重量不超過(guò)車(chē)輛的載重；式（3）為每輛車(chē)都從配送中心出發(fā)；式（4）為每個(gè)客戶(hù)指被一輛車(chē)服務(wù)并且所有的車(chē)都得到服務(wù)；式（5）為車(chē)輛完成任務(wù)后回到配送中心。

2 基于動(dòng)態(tài)小生境的協(xié)同進(jìn)化模型

協(xié)同進(jìn)化是指生物與生物、生物與環(huán)境之間在進(jìn)化過(guò)程中的相互依賴(lài)、相互協(xié)調(diào)的依存關(guān)系。動(dòng)態(tài)小生境集具有共享和協(xié)同進(jìn)化的優(yōu)點(diǎn)，通過(guò)進(jìn)化過(guò)程形成峰值就是小生境，對(duì)于所有個(gè)體利用動(dòng)態(tài)來(lái)分類(lèi)這個(gè)峰值就是動(dòng)態(tài)小生境。動(dòng)態(tài)小生境集的動(dòng)態(tài)性體現(xiàn)在種群被動(dòng)態(tài)地分為若干個(gè)子種群，小生境的動(dòng)態(tài)性由小生境的核心部分決定。協(xié)同進(jìn)化模型能夠自動(dòng)的實(shí)現(xiàn)小生境的定位，這個(gè)動(dòng)態(tài)模型能夠消除分布不均勻的優(yōu)化解，所以能夠加快計(jì)算的速度，進(jìn)而加快了各子種群的進(jìn)化速度。

動(dòng)態(tài)小生境的協(xié)同進(jìn)化模型如圖1所示。

圖1 基于動(dòng)態(tài)小生境的協(xié)同進(jìn)化模型

3 動(dòng)態(tài)小生境協(xié)同進(jìn)化遺傳算法

（1）編碼設(shè)計(jì)，生成初始種群。此問(wèn)題采用自然數(shù)編碼，這種編碼比較直觀，能夠保證算法的性能，減小了編碼后的計(jì)算量。

（2）適應(yīng)度計(jì)算。染色體編碼的歐式距離為：

d（cx，cy）=∑Lk=1（cx-cy）2（8）

其中，cx，cy為任意的兩條染色體，k為個(gè)體索引，L為染色體長(zhǎng)度。

個(gè)體cx相對(duì)于個(gè)體cy的共享函數(shù)為

sh（d（cx，cy））=1-d（cx，cy）ασ0，0

其中，σ0為定義的小生境峰半徑，α為共享函數(shù)的形狀參數(shù)，α>0。

小生境數(shù)為：

mdsh，j=∑Nyshdcx，cy，x=1，…，N.（10）

N為種群規(guī)模大小。動(dòng)態(tài)小生境的動(dòng)態(tài)適應(yīng)度函數(shù)為：

fdsh，i=fimdsh，i，其中，fdsh，i和fi為共享適應(yīng)度和初始適應(yīng)度。

染色體交叉操作示例如圖2所示。

（3）操作算子。①選擇算子——選擇算子采取線性排序選擇策略同時(shí)采取排擠機(jī)制的選擇策略，保留精英個(gè)體；②交叉算子——通過(guò)交叉算子可以調(diào)整車(chē)輛路徑，交叉操作是在兩個(gè)完全不同的個(gè)體之間進(jìn)行的，具體的交叉操作如圖2：③變異算子——因?yàn)樽儺惖目赡苄院苄《易儺愔黄鸬捷o助作用，所以對(duì)每代種群以變異概率pm進(jìn)行變異，交換兩點(diǎn)基因值。

圖2 染色體交叉操作示例

4 實(shí)驗(yàn)分析與結(jié)論

為了檢驗(yàn)動(dòng)態(tài)小生境協(xié)同進(jìn)化遺傳算法的性能，下面用該方法對(duì)車(chē)輛路徑優(yōu)化問(wèn)題中的典型測(cè)試問(wèn)題F系列：F-70， F-120和C系列：C-50， C-140等4個(gè)問(wèn)題進(jìn)行仿真實(shí)驗(yàn)。結(jié)果見(jiàn)表1和表2。

根據(jù)基于動(dòng)態(tài)小生境的協(xié)同進(jìn)化遺傳算法對(duì)車(chē)輛路徑優(yōu)化測(cè)試問(wèn)題的仿真實(shí)驗(yàn)結(jié)果及其與其它優(yōu)化方法的對(duì)比結(jié)果表明，這種改進(jìn)算法對(duì)車(chē)輛路徑優(yōu)化顯現(xiàn)出了良好的優(yōu)化性能，優(yōu)化結(jié)果明顯優(yōu)于常規(guī)遺傳算法，為車(chē)輛路徑優(yōu)化問(wèn)題的解決提供了一條可供借鑒的新思路。