求解車輛路徑問題的協(xié)同進化遺傳算法

姚衛(wèi)粉

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

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

DOIDOI：10.11907/rjdk.143490

中圖分類號：TP312

文獻標識碼：A 文章編號文章編號：16727800（2015）001005702

0 引言

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

1 車輛路徑問題數(shù)學模型

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

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為運輸距離；i，j為客戶編號；n為客戶量，k為車輛的順序；Cij為從點i到點j的費用；xijk為1時，表示車輛從i出發(fā)到j(luò)，否則為0；需求點i的需求量為qi，yik為1時表示客戶i的任務(wù)由車輛k來完成，否則為0。

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

2 基于動態(tài)小生境的協(xié)同進化模型

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

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

圖1 基于動態(tài)小生境的協(xié)同進化模型

3 動態(tài)小生境協(xié)同進化遺傳算法

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

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

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

其中，cx，cy為任意的兩條染色體，k為個體索引，L為染色體長度。

個體cx相對于個體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ī)模大小。動態(tài)小生境的動態(tài)適應(yīng)度函數(shù)為：

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

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

（3）操作算子。①選擇算子——選擇算子采取線性排序選擇策略同時采取排擠機制的選擇策略，保留精英個體；②交叉算子——通過交叉算子可以調(diào)整車輛路徑，交叉操作是在兩個完全不同的個體之間進行的，具體的交叉操作如圖2：③變異算子——因為變異的可能性很小而且變異只起到輔助作用，所以對每代種群以變異概率pm進行變異，交換兩點基因值。

圖2 染色體交叉操作示例

4 實驗分析與結(jié)論

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

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