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

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

0 引 言

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

1 問題描述及模型建立

1.1 問題描述

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

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

1.2 模型建立

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

(1)

約束條件

(2)

(3)

(4)

(5)

(6)

(7)

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

2 求解CVRP的改進(jìn)遺傳算法

2.1 染色體編碼與解碼

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

圖1 染色體編碼與解碼

2.2 初始種群生成

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

步驟1 隨機(jī)從所有客戶點(diǎn)中選出一個(gè)點(diǎn)作為染色體的首位基因；

步驟2 通過計(jì)算選出與當(dāng)前點(diǎn)距離最近且滿足約束條件的客戶作為下一個(gè)基因，直到所有客戶加入染色體，且沒有重復(fù)；

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

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

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

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

步驟1 隨機(jī)選擇父代的一個(gè)位置xi作為起點(diǎn)，并將該點(diǎn)作為子代的第一個(gè)基因；

步驟2 分別找出xi在父代X1和X2的位置x1i和x2i。若xi在父代的最后一位，則其下一位是父代的第一位。更新子代Child1：選取父代X1和X2，找出x1，i+1和x2，i+1所在父代中對應(yīng)的基因，計(jì)算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所對應(yīng)的基因，計(jì)算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中得到的基因作為新的起點(diǎn)。

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

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

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

2.4 變異算子

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

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

(8)

(9)

(10)

選取兩個(gè)變異點(diǎn)Cm和Cn的步驟如下：

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

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

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

2.5 適應(yīng)度評價(jià)

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

(11)

2.6 選擇策略

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

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

步驟2 將剩余個(gè)體按照適應(yīng)度值大小降序排列；

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

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

(12)

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

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

2.7 局部優(yōu)化

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

圖3 單點(diǎn)局部插入算子

2.8 改進(jìn)遺傳算法偽代碼

輸入：算例數(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)計(jì)算初始種群中個(gè)體的適應(yīng)度值f(Xi)，i=1，2，…，n；

(3)While

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

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

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

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

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

(4)End while.

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

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

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

3.2 實(shí)驗(yàn)與結(jié)果分析

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

(13)

(14)

(1)實(shí)驗(yàn)1

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

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

(2)實(shí)驗(yàn)2

選取CVRP算例集中SetA的27個(gè)算例，對比已發(fā)表文獻(xiàn)中的算法LNS-ACO[4]、ALNS[7]、AGGWOA[8]、EFFA[9]，對本文IGA的優(yōu)化效果進(jìn)行分析，表中下劃線加粗體表示最優(yōu)解，NA表示該文獻(xiàn)未對算例進(jìn)行求解，計(jì)算結(jié)果見表2。求解結(jié)果中，本文IGA在27個(gè)算例中能求得其中的15個(gè)最優(yōu)解，優(yōu)于AGGWOA算法的13個(gè)以及ALNS算法的9個(gè)最優(yōu)解，略差于LNS-ACO的17個(gè)最優(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%。在求解時(shí)間上，文獻(xiàn)[5-7]未給出求解時(shí)間，本文IGA平均求解時(shí)間為86.07 s，LNS-ACO為2336 s。

(3)實(shí)驗(yàn)3

選取CVRP算例集中SetP中的20個(gè)算例，測試結(jié)果見表3。實(shí)驗(yàn)結(jié)果顯示：本文IGA在20個(gè)算例中能求得13個(gè)最優(yōu)解，優(yōu)于所對比算法ALNS的8個(gè)、AGGWOA和LNS-ACO的12個(gè)最優(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%。在求解時(shí)間上，LNS-ACO平均耗時(shí)2078 s，本文IGA平均耗時(shí)為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種算法的求解平均偏差都逐漸增大，但I(xiàn)GA增加的最慢。由此可知：IGA求解性能穩(wěn)定性強(qiáng)于所對比的兩種算法。

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

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

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

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

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

4 結(jié)束語

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

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

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