改進的遺傳算法在物流管理中的應用

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

[關鍵詞] 物流管理 車輛路徑問題 遺傳算法

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

一、問題的描述及數學模型

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

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

(1)

(2)

(3)

(4)

(5)

(6)

其中，(7)

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

二、改進的雙種群遺傳算法

傳統的雙種群遺傳算法，交叉概率、變異概率固定不變，容易出現過早收斂而僅得到局部最優解的現象。我們采用自適應遺傳算法中交叉概率和變異概率能自適應調節的特點，將雙種群遺傳算法中交叉概率Pc和變異概率Pm按如下公式進行自適應調整，使算法尋優速度加快而且不易陷入局部最優解。

(8)

(9)

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

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

三、求解車輛路徑問題

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

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

實驗符號表示：GA：傳統的雙種群遺傳算法。

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

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

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