求解帶容量約束車輛路徑問題的改進遺傳算法

徐偉華，邱龍龍，張根瑞，魏傳祥

(昆明理工大學 交通工程學院，云南 昆明 650000)

0 引 言

遺傳算法(genetic algorithm)自1975年提出以來，目前已被廣泛應用于路徑規(guī)劃[13]、參數(shù)尋優(yōu)[14]、車間調(diào)度[15]等實際工程領(lǐng)域。傳統(tǒng)遺傳算法求解CVRP時，存在收斂速度慢、求解精度不高、局部搜索能力差等問題，針對這些問題，本文提出了改進遺傳算法(improved genetic algorithm)。

1 問題描述及模型建立

1.1 問題描述

本文研究的帶有容量約束的車輛路徑問題由一個配送中心，若干臺可用車輛及多個分散客戶組成，求解該問題的目標是在滿足容量約束的情況下，為分散的客戶找到最短的配送路線，并安排好服務次序。

CVRP定義為一個有向圖G=(V，E)，頂點集V={0，1，2，…，N}，邊集E={(i，j)|i，j∈V}，其中0代表配送中心，節(jié)點 {1，2，…，N} 代表有特定需求qi的客戶，其中i={1，2，…，N}，節(jié)點i到j之間的距離用dij表示?？捎门渌蛙囕v集合M={1，2，…，k}，質(zhì)地相同，最大容量限制均為Q。如果車輛k直接從客戶i出發(fā)到達客戶j，則xijk=1，否則xijk=0；如果車輛k直接服務客戶i，則yik=1，否則yik=0。

1.2 模型建立

建立如下數(shù)學模型

(1)

約束條件

(2)

(3)

(4)

(5)

(6)

(7)

其中，式(1)為目標函數(shù)，即車輛配送總距離最短；式(2)表示每個客戶僅由一輛車服務式；式(3)為車載容量約束，即每條路徑上客戶需求量之和不超過配送車輛最大載重限制；式(4)保證每個客戶都被服務到；式(5)和式(6)表示車輛服務時一定有路徑連接；式(7)表示所有線路均從同一倉庫開始，服務結(jié)束后回到倉庫。

2 求解CVRP的改進遺傳算法

2.1 染色體編碼與解碼

本文采用自然數(shù)編碼，將所有節(jié)點(不含配送中心)編碼組成一條染色體。如1個配送中心，8個客戶點以及2臺可用車輛組成的編碼為{23486751}，解碼時先將第一個客戶點2加入到配送路徑中，再判斷下個客戶3加入路徑是否能滿足車載容量約束，若能滿足，則將該客戶加入當前配送路徑；若不能滿足，則取當前客戶點為下一條配送路徑的起點，并更新上一條路徑。以此規(guī)則，可獲得配送路線分別為{02340}、{0867510}，每條路線由一輛車服務。圖1(a)為染色體編碼，圖1(b)為染色體解碼。

圖1 染色體編碼與解碼

2.2 初始種群生成

對于CVRP的求解，本文采用貪婪算法生成初始種群，并引入車載容量限制。相比隨機生成策略，貪婪算法可以產(chǎn)生質(zhì)量更高的初始種群。生成初始解的步驟如下：

步驟1 隨機從所有客戶點中選出一個點作為染色體的首位基因；

步驟2 通過計算選出與當前點距離最近且滿足約束條件的客戶作為下一個基因，直到所有客戶加入染色體，且沒有重復；

步驟3 重復步驟1和步驟2N次，即可生成規(guī)模為N的初始種群。

2.3 啟發(fā)式交叉算子

交叉操作模擬了自然界生物種群交配的過程，對選中的兩個個體使用交叉算子來產(chǎn)生新的個體。隨機交叉算子雖然能夠增強算法的全局尋優(yōu)能力，但隨著客戶點的增多，可能會增加無效搜索，降低搜索效率，針對這一缺點，本文提出了基于貪婪策略的啟發(fā)式交叉算子(heuristic cros-sover operator)。其基本思想是：子代以繼承父代染色體的一個基因為基礎(chǔ)，并以距離為啟發(fā)函數(shù)，優(yōu)先搜索距離當前點最近的客戶作為下一個基因，再逐步搜索子代的其余基因?；谪澙凡呗缘膯l(fā)式交叉算子的具體操作如下：

隨機選取兩個父代染色體X1={x11，x12，…，x1N} 和X2={x21，x22，…，x2N}，則產(chǎn)生子代染色體的步驟為：

步驟1 隨機選擇父代的一個位置xi作為起點，并將該點作為子代的第一個基因；

步驟2 分別找出xi在父代X1和X2的位置x1i和x2i。若xi在父代的最后一位，則其下一位是父代的第一位。更新子代Child1：選取父代X1和X2，找出x1，i+1和x2，i+1所在父代中對應的基因，計算x1i與x1，i+1及x2i和x2，i+1間的距離，若d(x1ix1，i+1)≥d(x2ix2，i+1)，則將x2，i+1作為子代Child1中xi的后一位基因，否則將x1，i+1作為xi的后一位基因。更新子代Child2：選取父代X1和X2中找出x1，i-1和x2，i-1所對應的基因，計算x1i與x1，i-1及x2i和x2，i+1間的距離，若d(x1ix1，i-1)≥d(x2ix2，i-1)，則將x2，i-1作為xi的后一位基因，否則將x1，i-1作為子代Child2中xi的后一位基因。

步驟3 將xi從父代X1和X2中刪除，得到X′1和X′2。

步驟4 將步驟2中得到的基因作為新的起點。

步驟5 循環(huán)步驟2～步驟4，當子代Child1和Child2中的基因個數(shù)均為N，則循環(huán)結(jié)束，得到最終的Child1和Child2。

如圖2所示，對于有8個客戶點的CVRP，隨機選取圖2(a)所示兩個個體X1和X2，以5為起點，作為染色體Child1和Child2的第一位。圖2(b)和圖2(e)分別是父代X1和X2經(jīng)過步驟2～步驟4一次更新得到的個體，并確定1和3作為Child1和Child2的下一位基因。當子代中基因個數(shù)都為8時，循環(huán)結(jié)束得到圖2(c)和圖2(f)所示的Child1和Child2。

圖2 基于貪婪策略的啟發(fā)式交叉算子交叉過程

2.4 變異算子

由于隨機變異算子變異范圍較大，不利于算法的局部尋優(yōu)，于是本文在兩點隨機交換變異的基礎(chǔ)上引入最近鄰搜索算子，將變異的范圍縮小，以提高局部搜索能力。

最近鄰定義為：對于包含n個客戶點V={v1，v2，…，vn} 的CVRP而言，任意一個客戶點vi(i=1，2，…，n) 的最近鄰就是距離該客戶最近的k個客戶點的集合，記為U={c1，c2，…，ck}，k=1，2，…，n。為了衡量vi與近鄰點的遠近程度，引入近鄰度λ，定義式(8)，其中d代表vi與集合U中點集的歐式距離，d值越大，則近鄰度λ越小，表示距離越遠；反之越近

(8)

(9)

(10)

選取兩個變異點Cm和Cn的步驟如下：

步驟1 使用式(9)和式(10)分別計算出U中每個點被選擇的概率以及前j個點被選擇的累計概率；

步驟2 分別生成兩個0到1之間不重復的隨機數(shù)r1和r2，若r1≤p1，則近鄰點Cm為c1，若pj-1

步驟3 將染色體中近鄰點Cm和Cn對應的客戶位置互換，得到新的染色體，即完成變異操作。

2.5 適應度評價

個體的適應度值大小決定了個體能否被保留和繼續(xù)進化，個體適應度值越大，被保留下來的概率越大。本文以個體所對應的配送距離的倒數(shù)作為個體的適應度，配送距離越長則適應度值越小。適應度計算公式為

(11)

2.6 選擇策略

選擇策略決定了個體是否能保留下來繼續(xù)進化。常用的輪盤賭選擇法是比例選擇的一種，個體被選擇的概率與其適應度值大小成正比。但由于該方法是基于概率的選擇，往往會產(chǎn)生較大誤差，有時適應度值大的個體也無法被選中。相比于輪盤賭法，精英選擇策略能把當代適應度值最好的個體保留下來繼續(xù)進化，也能很好地保留種群的多樣性，缺點是局部最優(yōu)個體不易被淘汰。鑒于兩種方法的優(yōu)缺點，本文采用精英選擇策略和輪盤賭法結(jié)合的方式進行個體的選擇，具體操作步驟如下：

步驟1 將交叉和變異操作產(chǎn)生的新個體與父代種群合并，并刪除重復個體，得到種群M；

步驟2 將剩余個體按照適應度值大小降序排列；

步驟3 從排列中選取數(shù)量為N/2個適應度值最大的個體；

步驟4 根據(jù)公式計算 (M-N/2) 個剩余個體被選中的概率

(12)

步驟5 使用輪盤賭法選取N/2個個體；

步驟6 將步驟3和步驟5中得到的個體合并組成新的種群。

2.7 局部優(yōu)化

為提高算法的局部搜索能力，本文使用單點局部插入算子，在鄰域搜索的基礎(chǔ)上尋找更好的可行解。對于x1、x2和x3這3個點，若d(x1，x2)≤d(x2，x3)，則以點x2為圓心，d(x2，x3) 為半徑畫圓，將在圓內(nèi)但不包含點x2和點x3的所有點組成集合W。優(yōu)化時將點x2依次插入集合W中的所有點的下一位，得到一組新的可行路徑，將可行路徑的適應度值與初始路徑適應度值進行對比，將適應度值優(yōu)者更新為當前路徑。如圖3(a)所示為一個配送中心以及2輛車構(gòu)成的初始配送路徑，vehicle1和vehicle2對應的兩條配送路線存在交叉，以d(x2，x3) 為半徑的圓包括3個點，使用單點局部插入策略后得到圖3(b)～圖3(f)所示的5組可行路徑，將5組可行路徑進行對比，圖3(c)的路徑長度最短，則使用該路徑為當前路徑。

圖3 單點局部插入算子

2.8 改進遺傳算法偽代碼

輸入：算例數(shù)據(jù)集、種群規(guī)模N、變異概率Pm、交叉概率Pc、最大迭代次數(shù)Gmax、最近鄰搜索范圍K。

輸出：最優(yōu)解f(x*)。

(1)根據(jù)2.2節(jié)初始化種群X={X1，X2，…，XN}，Xi={xi1，xi2，…，xin}，i=1，2，…，n；

(2)計算初始種群中個體的適應度值f(Xi)，i=1，2，…，n；

(3)While

判斷算法是否滿足終止條件，滿足則解碼后輸出最優(yōu)解f(x*)，否則執(zhí)行下一步操作；

根據(jù)2.3節(jié)使用基于貪婪策略的啟發(fā)式交叉算子進行交叉操作；

再按照變異概率選出n個個體根據(jù)2.4節(jié)進行變異操作；

將交叉和變異產(chǎn)生的個體與父代個體合并，根據(jù)2.6節(jié)的選擇策略選出N個個體；

根據(jù)2.7節(jié)對算法進行局部優(yōu)化；

(4)End while.

3 算例驗證和結(jié)果分析

3.1 實驗環(huán)境及參數(shù)設置

本文選取CVRP標準算例庫中SetE、SetA和SetP的部分算例對本文算法進行測試，算例源自于http：//vrp.atd-lab.inf.puc-rio.br/index.php/en/，算法程序在Matlab r2018a中編寫，計算機操作系統(tǒng)為Windows7，運行內(nèi)存大小為8.0 GB，處理器為四核酷睿i5-3470@3.2 GHz.經(jīng)過反復測試，本文實驗參數(shù)選取如下：初始種群規(guī)模N=100，最大迭代次數(shù)Gmax=300，變異概率為Pm=0.1，最近鄰搜索范圍K=10，啟發(fā)式交叉算子的交叉概率為Pc=0.8。

3.2 實驗與結(jié)果分析

對比實驗中所有算例結(jié)果皆由算法獨立運行20次，表中下劃線加粗字體表示算法求得最優(yōu)解，NA表示文獻未對該算例進行求解，其中Opt為目前已文獻最優(yōu)解，Best表示最優(yōu)解，Worst表示最差解，Er表示最優(yōu)解偏差，Mr表示平均偏差，Time為運算時間，單位s，Average為平均值，最優(yōu)解偏差和平均偏差分別可用式(13)和式(14)計算

(13)

(14)

(1)實驗1

選取CVRP算例集中SetE的9個算例，將本文的IGA與GA作比較，GA實驗參數(shù)設置為N=100、Gmax=300、Pm=0.1、Pc=0.8。計算結(jié)果對比見表1。實驗結(jié)果顯示，本文IGA能在9個算例中找到其中的5個最優(yōu)解，最優(yōu)值偏差僅為0.36%，GA為1.96%，求解最優(yōu)值偏差降低了81.63%；在求解精度上，IGA的平均值偏差在1%以內(nèi)，而GA為3.16%，求解平均偏差降低了70.25%；在求解時間上，IGA對9個算例的平均求解時間為73.20 s，而GA的平均求解時間為581.42 s，求解時間減少了87.41%，表明改進遺傳算法求解CVRP的效率明顯高于傳統(tǒng)遺傳算法。

表1 GA和IGA求解CVRP SetE類算例結(jié)果比較

(2)實驗2

選取CVRP算例集中SetA的27個算例，對比已發(fā)表文獻中的算法LNS-ACO[4]、ALNS[7]、AGGWOA[8]、EFFA[9]，對本文IGA的優(yōu)化效果進行分析，表中下劃線加粗體表示最優(yōu)解，NA表示該文獻未對算例進行求解，計算結(jié)果見表2。求解結(jié)果中，本文IGA在27個算例中能求得其中的15個最優(yōu)解，優(yōu)于AGGWOA算法的13個以及ALNS算法的9個最優(yōu)解，略差于LNS-ACO的17個最優(yōu)解。5種算法求解結(jié)果的最優(yōu)解偏差都在1%以內(nèi)，本文IGA的最優(yōu)解偏差僅為0.17%，優(yōu)于其它4種算法；在求解精度方面，本文IGA求解的平均偏差為0.62%，優(yōu)于ALNS的1.81%和AGGWOA的1.57%。在求解時間上，文獻[5-7]未給出求解時間，本文IGA平均求解時間為86.07 s，LNS-ACO為2336 s。

(3)實驗3

選取CVRP算例集中SetP中的20個算例，測試結(jié)果見表3。實驗結(jié)果顯示：本文IGA在20個算例中能求得13個最優(yōu)解，優(yōu)于所對比算法ALNS的8個、AGGWOA和LNS-ACO的12個最優(yōu)解。在求解精度方面，本文IGA的最優(yōu)解偏差為0.11%，優(yōu)于ALNS的1.15%、AGGWOA的0.22%，EFFA的0.52%以及LNS-ACO的0.32%；本文IGA求解結(jié)果的平均偏差為0.67%，優(yōu)于ALNS的1.81%和AGGWOA的1.27%。在求解時間上，LNS-ACO平均耗時2078 s，本文IGA平均耗時為77.42 s。

表3 ALNS、AGGWOA、EFFA、LNS-ACO和IGA求解CVRP SetP類算例結(jié)果比較

圖4和圖5展示了ALNS、AGGWOA和IGA求解SetA類算例的平均偏差回歸曲線，圖4中3種算法的平均偏差斜率分別為kALNS=0.0735，kAGGWOA=0.0665，kIGA=0.0265，圖5中kALNS=0.0428，kAGGWOA=0.0527，kIGA=0.0305。和其它兩種算法對比，IGA求解平均偏差回歸曲線的斜率最小，表明隨著客戶數(shù)量的增多，3種算法的求解平均偏差都逐漸增大，但IGA增加的最慢。由此可知：IGA求解性能穩(wěn)定性強于所對比的兩種算法。

圖4 SetA類算例求解平均誤差回歸曲線

圖5 SetP類算例求解平均誤差回歸曲線

圖6分別是算例En22k4、Pn51k10和An80k10的最優(yōu)路徑圖和迭代圖，由迭代圖可以看出，本文所提算法的求解速度較快，求解性能較好，能使用較少的迭代次數(shù)找到最優(yōu)解。

圖6 最優(yōu)路徑及算法迭代

綜合以上實驗，在求解CVRP時，本文提出的IGA對比傳統(tǒng)遺傳算法具有求解速度快，精度高的優(yōu)勢，對比算法ALNS、AGGWOA、EFFA、LNS-ACO這4種算法，也具有較好的優(yōu)化效果，說明該IGA是求解CVRP的有效算法。

4 結(jié)束語

遺傳算法求解CVRP的效率和精度受多種因素的影響，如初始種群生成、種群數(shù)量、交叉和變異算子、選擇算子、評價方法等，本文主要研究了交叉算子和變異算子對算法求解CVRP性能的影響，并針對傳統(tǒng)遺傳算法的不足提出了改進策略。

(1)隨機交叉算子雖有利于全局尋優(yōu)，但也增大了無效搜索的概率，基于貪婪策略的交叉算子不僅能加快算法尋優(yōu)速度，在全局尋優(yōu)上也有較好表現(xiàn)。變異操作能使種群產(chǎn)生新的個體，但隨機變異范圍過大，會降低算法的搜索效率，引入最近鄰搜索算子，能有效縮小變異范圍，提高算法局部搜索能力。

(2)通過實例驗證分析，本文提出的改進遺傳算法能有效克服傳統(tǒng)遺傳算法的缺點，求解CVRP時具有求解速度快，精度高，穩(wěn)定性好的優(yōu)點，說明本文算法能有效求解CVRP，對解決此類組合優(yōu)化的問題具有一定的參考價值。