改進遺傳算法求解VRP問題

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

關鍵詞：改進遺傳算法 VRP 忳能

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

1 VRP數學模型的建立

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

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

由這些參數和變量可以求出VRP問題的數學模型表示為：

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

2 遺傳算法改進

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

fmax是種群中最大的適應度值，favg每一代種群的平均適應度值，fmin每代種群中最小的適應度值，f'要交叉的兩個個體種較大的適應度值，f要變異個體的適應度值。，取（0，1）區間的值，在優化過程中，根據需要不斷調整。

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

3 算法實例計算

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

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

參數初始化：

（1）車輛數

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

其中，[ ]表示對括號內的數字取整，0<

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

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

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

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

參考文獻

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

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