基于改進單親遺傳算法的車輛路徑優(yōu)化問題研究

陳曉桐

摘 要：單親遺傳算法隨著種群的進化，單親遺傳算法的突變、逆序、變異使得算法在局部搜索的能力逐步減弱。為了克服該缺點，文中提出了一種基于貪心思想的重組算子。在進化過程中它不斷地對父代和子代的染色體進行篩選，保留最優(yōu)，加快了整體的收斂速度。

關鍵詞：VRP；PGA；貪心算法

DOI：10.16640/j.cnki.37-1222/t.2018.19.182

1 單親遺算法

單親遺算法（PGA）是通過選擇和變異算子繁衍后代，取消了傳統(tǒng)序號編碼GA的交叉算子，只在一條染色體上操作基因重組的遺傳算法，簡化了操作，提高了計算效率，并且不需要出示群體的多樣性，也不存在“早熟收斂”，是一種適合求解組合問題的新型遺傳算法[1]。

2 單親遺傳算法的改進

引入貪心算法，進行局部調整操作。即在進行變異操作后，對變異后的個體進行適應度值計算，如果適應度大于上一代的適應度值，變異后個體代替變異前個體，否則放棄變異后個體，保留原先個體。通過此種方法的局部尋優(yōu)，找到局部最優(yōu)。因此，在求VRP時，既利用單親遺傳算法的優(yōu)勢來確保全局搜索的能力，又利用了貪心算子來保證局部搜索能力。這種混合型算法，不僅使收斂速度得到提高，還能夠盡可能快的尋求到問題的最優(yōu)解。

3 基于改進PGA的VRP問題研究

3.1 問題描述及模型建立

本文研究對象是物流中心，n個零售商，m輛運輸車輛，每個零售需求量為Ci。假定每輛車容量為Q，零售商有優(yōu)先級，配送成本分為固定和可變成本。其優(yōu)化的目標是在滿足需求，求車輛的運貨路線，使得總運輸成本最低。根據(jù)約束條件和參數(shù)變量，數(shù)學表達式如下：

（1）

s.t

（2）

（3）

當時， （4）

3.2 關鍵算法的設計

3.2.1 適應度值計算

GA中最重要的數(shù)據(jù)是適應度值。是進化時優(yōu)勝劣汰的依據(jù)。計算過程如下：

（1） i=1，v=1；（2） 按照個體中零售商編號依次將第i次序的零售商加入到車v的配送路線中；（3）若車v運輸貨物量總和超過車輛運載量，至步驟4，否則轉至步驟2，且i=i+1；（4）將配送路線中的零售商按優(yōu)先級進行排序；（5）計算車v配送成本；（6） v=v+1；（7）若配送車輛已用完，或者所有零售商都已得到配送，則結束，輸出適應度，否則回到步驟2。

3.2.2 變異算子

本文中采用帶貪心算法的基因串逆轉算子，具體過程如下：（1）隨機選擇一段基因串片段；（2）將選擇的基因串片段逆序翻轉；（3）計算變異后的個體適應度，如果大于變異前個體適應度，則用變異后個體代替變異前個體，否則放棄編譯后個體。

3.2.3 改進后的單親遺傳算法的步驟

（1）初始種群的產生；（2）計算初始群體的個體的適應值；（3）保留最優(yōu)個體；（4）輪盤賭算法選擇子代個體；（5）采用貪心算法思想，利用基因串逆轉操作進行個體的變異，只將變異后適應度得到改進的染色體保留；（6）完成群體的更新，新群體由保留下來的最優(yōu)解個體和新的個體組成；（7）將初始設定的代數(shù)作為判斷運算是否終止的依據(jù)，滿足終止條件，則終止運算，并輸出結果，否則返回到步驟2。

四 實證分析

本文案例中，車輛數(shù)量為5，運載量為15，啟動成本為30。種群規(guī)模取m=30，最大迭代次數(shù)為300，零售商的需求量為[1 4 2 1 2 3 4 1 1 2 3 2 1 2 3 4 3 4 2 3 1 4 3 2 4 2 1 4 3 2]，配送優(yōu)先級為[1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 2 2 2 2]得出配送總成：758.36。

為了驗證改進單親遺傳算法在車輛路徑問題的優(yōu)勢，本文做了仿真比較。由圖2可以看出改進遺傳算法的收斂速性和解的精確度方面都高于基本的單親遺傳算。所以改進單親遺傳引入貪心算法，能提前獲得大量的優(yōu)良基因，所花時間、迭代次數(shù)和最優(yōu)結果等方面都優(yōu)于一般GA。

參考文獻：

[1]占焱發(fā).基于遺傳算法的物流配送車輛路徑問題研究[D].北京交通大學博士學位論文2010.

[2]傅成紅.多周期庫存路徑問題及其算法研究[D].中南大學博士學位論文，2010.