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

2024-03-21 01:59:16徐偉華邱龍龍張根瑞魏傳祥

計算機工程與設計 2024年3期

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

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

0 引言

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

1 問題描述及模型建立

1.1 問題描述

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

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

1.2 模型建立

建立如下數學模型

(1)

約束條件

(2)

(3)

(4)

(5)

(6)

(7)

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

2 求解CVRP的改進遺傳算法

2.1 染色體編碼與解碼

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

圖1 染色體編碼與解碼

2.2 初始種群生成

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

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

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

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

2.3 啟發式交叉算子

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

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

步驟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 循環步驟2～步驟4，當子代Child1和Child2中的基因個數均為N，則循環結束，得到最終的Child1和Child2。

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

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

2.4 變異算子

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

最近鄰定義為：對于包含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之間不重復的隨機數r1和r2，若r1≤p1，則近鄰點Cm為c1，若pj-1

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

2.5 適應度評價

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

(11)

2.6 選擇策略

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

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

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

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

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

(12)

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

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

2.7 局部優化

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

圖3 單點局部插入算子

2.8 改進遺傳算法偽代碼

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

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

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

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

(3)While

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

根據2.3節使用基于貪婪策略的啟發式交叉算子進行交叉操作；

再按照變異概率選出n個個體根據2.4節進行變異操作；

將交叉和變異產生的個體與父代個體合并，根據2.6節的選擇策略選出N個個體；

根據2.7節對算法進行局部優化；

(4)End while.

3 算例驗證和結果分析

3.1 實驗環境及參數設置

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

3.2 實驗與結果分析

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

(13)

(14)

(1)實驗1

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

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

(2)實驗2

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

(3)實驗3

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

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

圖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求解平均偏差回歸曲線的斜率最小，表明隨著客戶數量的增多，3種算法的求解平均偏差都逐漸增大，但IGA增加的最慢。由此可知：IGA求解性能穩定性強于所對比的兩種算法。