改進(jìn)遺傳算法求解VRP問(wèn)題

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

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

中圖分類(lèi)號(hào)：U491.2 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2012）12（c）-0-01

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

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

貨車(chē)s由i駛向j；點(diǎn)i的貨運(yùn)任務(wù)由s貨車(chē)完成

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

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

2 遺傳算法改進(jìn)

改進(jìn)交叉概率pc和變異概率

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

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

3 算法實(shí)例計(jì)算

采用matlab 6.0進(jìn)行程序仿真，以9個(gè)客戶為例進(jìn)行求解。

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

參數(shù)初始化：

（1）車(chē)輛數(shù)

按照參考文獻(xiàn)對(duì)m進(jìn)行評(píng)估。

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

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

（3）車(chē)輛載重限制=12 t

改進(jìn)遺傳算法運(yùn)行總距離746 km，普通遺傳算法運(yùn)行總距離830 km。

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

參考文獻(xiàn)

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

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