摘 要：用遺傳算法（GA）求解車輛路徑問題，但總體上他們所得解的質(zhì)量都不高，這是由GA本身局部搜索能力不強所致.針對GA這一缺陷，該文對標(biāo)準(zhǔn)遺傳算法改進，用于求解VRP問題，并通過實驗計算證明了該算法具有良好的尋優(yōu)性能。

關(guān)鍵詞：改進遺傳算法 VRP 忳能

中圖分類號：U491.2 文獻標(biāo)識碼：A 文章編號：1674-098X（2012）12（c）-0-01

1 VRP數(shù)學(xué)模型的建立

問題描述如下：1個物流中心和個客戶，第k個客戶需運輸?shù)呢浳锪繛?，物流中心派出多輛貨車，從物流中心將個客戶的所有貨物運出，求滿足貨運需求的最短距離車輛運輸行程路線。設(shè)物流中心派出m輛貨車，每輛貨車的載重量為q，且q>gi，表示點i到點j的運輸成本，物流中心的編號為0，各客戶的編號為，另外幾個變量定義如下：

貨車s由i駛向j；點i的貨運任務(wù)由s貨車完成

由這些參數(shù)和變量可以求出VRP問題的數(shù)學(xué)模型表示為：

每輛貨車的載貨量不超過車輛載重量；保證通過每一個客戶有且僅有一輛車，所有車從物流中心出發(fā)，最后回到物流中心；確保每個客戶的運輸任務(wù)僅由1輛貨車來完成，所有的運輸任務(wù)則由m輛貨車協(xié)同完成。

2 遺傳算法改進

改進交叉概率pc和變異概率

fmax是種群中最大的適應(yīng)度值，favg每一代種群的平均適應(yīng)度值，fmin每代種群中最小的適應(yīng)度值，f'要交叉的兩個個體種較大的適應(yīng)度值，f要變異個體的適應(yīng)度值。，?。?，1）區(qū)間的值，在優(yōu)化過程中，根據(jù)需要不斷調(diào)整。

改進后的交叉概率和變異概率能夠隨適應(yīng)度自動改變，夠較高的概率產(chǎn)生出較大多樣性的子代，即能夠高概率產(chǎn)生適應(yīng)度更高的新個體，使得它們不會處于一種近似停滯不前的狀態(tài)，從而使算法跳出局部最優(yōu)解。

3 算法實例計算

采用matlab 6.0進行程序仿真，以9個客戶為例進行求解。

9家客戶（依次用1，2，…，9來表示）之間的距離（km）如表1所示，各客戶的需求量（kg）如表2所示。每輛貨車的容量為12 t，在保證車輛不超載，并且保證每家客戶的送貨量的前提下，找出對這9家客戶進行配貨的最短路徑。

參數(shù)初始化：

（1）車輛數(shù)

按照參考文獻對m進行評估。

其中，[ ]表示對括號內(nèi)的數(shù)字取整，0<

（2）進化代數(shù)G=50，初始群體p=50，pw=1000.

（3）車輛載重限制=12 t

改進遺傳算法運行總距離746 km，普通遺傳算法運行總距離830 km。

由以上的試驗結(jié)果可以看出，采用改進的遺傳算法與普通遺傳算法分別求解上面應(yīng)用實例，改進遺傳算法優(yōu)化結(jié)果明顯優(yōu)于普通遺傳算法。這說明標(biāo)準(zhǔn)遺傳算法中標(biāo)準(zhǔn)選擇，交叉，變異算子在求解VRP問題時搜索能力較差。將整數(shù)編碼、改進交叉算子引入改進標(biāo)準(zhǔn)遺傳算法后，算法的搜尋能力明顯加強，收斂性顯著提高，仿真試驗結(jié)果證明改進后算法的可行性和有效性。

參考文獻

[1]李軍，郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法[M].中國物資出版社，2001.

[2]歐陽森，王建華，耿英三，等.一種新的改進遺傳算法[J].計算機工程與應(yīng)用，2003，39（11）.