[摘 要] 本文針對傳統(tǒng)的雙種群遺傳算法用于求解最優(yōu)化問題時常采用固定染色體交叉概率和染色體變異概率，容易出現(xiàn)早熟、收斂速度較慢的問題，提出新的雙種群遺傳算法，并成功地運(yùn)用到車輛路徑問題的研究。

[關(guān)鍵詞] 物流管理 車輛路徑問題 遺傳算法

求解物流管理中車輛路徑問題，遺傳算法是被研究得最多的一種。但標(biāo)準(zhǔn)遺傳算法(Genetic Algorithm，簡稱GA)易陷入局部極值解，出現(xiàn)“早熟收斂”現(xiàn)象。

一、問題的描述及數(shù)學(xué)模型

物流配送路徑優(yōu)化問題一般可以這樣描述：從某物流配送中心最多用K輛配送車向L個客戶送貨。每輛車載重為bk(k=1，2，3，…，K），每個客戶貨物需求量為di(i＝1，2，…，L），客戶i到客戶j之間的距離為Cij。假設(shè)忽略體積因素，在滿足各客戶配送需求且不超載的情況下，確定合適的車輛數(shù)，以及如何安排行車路線，使得總的運(yùn)輸成本最低。

設(shè)nk為第k輛車所包含的客戶數(shù)（若nk＝0表示未啟用第k輛車），用集合Rk表示第k條路徑，其中的元素rki表示客戶rki在路徑k中的順序?yàn)閕（不包含物流中心）。令rk0=rk(nk+1)=0表示物流中心，則有如下的車輛路徑問題的數(shù)學(xué)模型。

(1)

(2)

(3)

(4)

(5)

(6)

其中，(7)

上式中不等式(2)保證每條路徑上的各客戶的總需求量不超過此條路徑配送車容量，不等式(3)表明每條路徑服務(wù)的客戶數(shù)不超過總客戶數(shù)，等式(4)要求每個客戶都得到車輛的配送服務(wù)，等式(5)表示每條路徑的客戶組成，等式(6)則限制每個客戶的需求僅能由一車輛來完成．

二、改進(jìn)的雙種群遺傳算法

傳統(tǒng)的雙種群遺傳算法，交叉概率、變異概率固定不變，容易出現(xiàn)過早收斂而僅得到局部最優(yōu)解的現(xiàn)象。我們采用自適應(yīng)遺傳算法中交叉概率和變異概率能自適應(yīng)調(diào)節(jié)的特點(diǎn)，將雙種群遺傳算法中交叉概率Pc和變異概率Pm按如下公式進(jìn)行自適應(yīng)調(diào)整，使算法尋優(yōu)速度加快而且不易陷入局部最優(yōu)解。

(8)

(9)

其中，fmax代表群體中最大適應(yīng)度；favg代表每代群體的平均適應(yīng)度；f’代表要交叉的兩個個體中較大適應(yīng)度；f代表要變異個體的適應(yīng)度。Pc1＝0.9，Pc2＝0.6，Pm1=0.1，Pm2=0.01。

這樣就相應(yīng)地提高了群體中表現(xiàn)優(yōu)良的個體的Pc和Pm，使得他們不會處于一種近乎停滯不前的狀態(tài)。因此，自適應(yīng)的Pc和Pm能夠提供相對某個解的最佳Pc和Pm。改進(jìn)后的染色體交叉算子和變異算子在保證群體多樣性的同時，保證遺傳算法的收斂性。

三、求解車輛路徑問題

為便于比較，本實(shí)驗(yàn)仍采用的經(jīng)典測試集。用上述改進(jìn)的雙種群遺傳算法，對一個有8個客戶和1個配送中心，兩輛車（容量均為8噸）的配送系統(tǒng)的車輛路徑問題進(jìn)行求解．已知各客戶的需求和各客戶之間的距離如表1(其中0表示配送中心)，要求合理安排車輛的行駛路線，使總的運(yùn)距最短。

用2×8個互不重復(fù)的1到16的自然數(shù)構(gòu)成一條染色體，表示一種車輛路徑安排方案。隨機(jī)產(chǎn)生10個這樣的染色體構(gòu)成初始種群。利用自適應(yīng)染色體交叉算子和變異算子，采用不同的初始種群，經(jīng)過上機(jī)運(yùn)行10次，進(jìn)化50代和100代得到路徑長度與傳統(tǒng)的雙種群遺傳算法的結(jié)果對比如表2所示。表3是得到最優(yōu)解67.5所需的進(jìn)化代數(shù)對比。

實(shí)驗(yàn)符號表示：GA：傳統(tǒng)的雙種群遺傳算法。

New GA：本文提出的新雙種群遺傳算法

從表2和表3可以看出，改進(jìn)后的雙種群遺傳算法搜索到全局最優(yōu)解的效率要比傳統(tǒng)的雙種群遺傳算法高，能夠快速的求得最優(yōu)解，是求解車輛路徑問題的一種有效算法。

物流配送系統(tǒng)中的車輛路徑問題具有減少運(yùn)輸成本、提高經(jīng)濟(jì)效益的重要作用，對該問題的研究有多種解決方法。本文提出一種改進(jìn)的雙種群遺傳算法求解VRP，通過自適應(yīng)調(diào)整染色體交叉概率和染色體變異概率，保證染色體的多樣性，能夠有效避免早熟收斂現(xiàn)象，并通過實(shí)例驗(yàn)證了該算法的性能，是求解車輛路徑問題的一種有效方法。