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

劉祥坤, 李萬龍, 李東升, 牛家冰

(長春工業大學 計算機科學與工程學院, 吉林 長春 130102)

0 引 言

車輛路徑問題(VRP)最早由Dantzig G B等[1]于1959年提出,該問題也被證明屬于NP-hard問題,隨著研究的深入,該問題的研究范圍也不僅僅局限在簡單的車輛路徑問題,如容量限制車輛路徑問題、有時間窗口限制的車輛路徑問題等。

文中主要研究了容量約束車輛路徑問題(CVRP),CVRP是在傳統CRP問題的基礎上,加入了車輛容量約束,主要解決多輛有容量約束的配送車輛向多個服務點進行服務,如何設計配送車輛的行駛路徑,使得服務成本最低的問題。由于該問題屬于NP-hard問題,精確算法并不能在合理的時間內得到滿意的結果,人們的研究也從精確算法轉向了啟發式算法。Wu Y F等[2]提出一種基于蟻群優化的改進混合ACO-VNS算法和可變鄰域搜索算法,該方法在更短的時間內取得了更好的性能;Asma M等[3]通過螢火蟲算法與兩種類型的局部搜索和遺傳算子結合,提高了解的質量,并加快了收斂速度;蔡延光等[4]提出一種帶分裂機制的帝國競爭算法求解,結合2-opt局部搜索算法,有效求解CVRP問題;王丹等[5]采用新染色體表示和不同交叉操作、變異操作策略,依據基準數據集和測試數據驗證了NGA算法,有效解決了問題;曹炳汝等[6]提出在多車型動態需求車輛配送模型,采用遺傳算法求解一條最優路線;韓孟宜等[7]根據實際條件構建了有時間限制的應急物資配送模型,遺傳算法通過結合節約算法、大規模鄰域搜索算法,設計了一種混合遺傳算法。

目前對該模型的求解主要用到的啟發式算法為蟻群算法[8-10]、遺傳算法和粒子群算法[11-12]等。文中在傳統遺傳算法的基礎上對種群初始化和選擇操作、交叉操作、變異操作進行了改進,同時結合鄰域搜索算法進行改進,以達到最短時間內求出最優解或次最優解。

1 CVRP數學模型

CVRP問題描述:設某倉庫有m輛配送車,該倉庫需要向N個客戶運輸物資,每個客戶的物資需求量為Qi(i=1,2,…,N),每輛車的最大載貨重量為Qmax,dij為節點i和節點j之間的距離。如何使所有車輛行駛的總距離最短是本問題研究目標,對該問題進行如下假設:

1)倉庫以及各個客戶位置已知,且所有客戶與倉庫之間互通,配送車輛從倉庫出發,最后返回到倉庫;

2)每個客戶只能由一輛配送車輛進行配送,不能由多輛車進行多次配送;

3)單個客戶的需求量小于等于車輛的最大配送量;

4)所有車輛規格相同,每輛車只安排一次配送任務。

本問題目標函數為配送過程中所有配送車行駛的總路徑長度,則問題模型如下:

目標函數為

(1)

約束條件為

(2)

s=1,2,…,N,

(3)

(4)

j=1,2,…,N;s=1,2,…,m,

(5)

i=1,2,…,N;s=1,2,…m,

其中,式(2)是保證每輛車的配送物資不超過配送車輛的最大載貨重量,式(3)～式(5)是保證每個客戶只能由一輛車提供配送。

2 求解過程

傳統遺傳算法隨著迭代次數的增加,種群多樣性下降迅速,導致算法搜索能力降低,文中通過對基本遺傳算法的操作進行改進,增加搜索范圍,避免陷入局部最優,提高解的質量。

2.1 染色體編碼

文中選用實數編碼進行染色體的構造,將客戶點和車輛分別進行編碼,客戶編碼為(1,2,…,N),車輛編碼為(1,2,1,3,…,k),其中N為客戶數量,K為該次運輸所需要的車輛數。如客戶染色體為“1,2,3,4,5,6,7”,車輛染色體為“1,3,1,2,3,1,2”表示的路線為:

子路線1:倉庫0-客戶1-客戶3-客戶6-倉庫0;

子路線2:倉庫0-客戶4-客戶7-倉庫0;

子路線3:倉庫0-客戶2-客戶5-倉庫0。

2.2 種群初始化

先采用隨機生成法生成一條合理的路徑,然后通過變鄰域搜索算法對該路徑進行不斷交換、替代、倒置等優化操作,直至所有客戶點遍歷完成,形成一條更加合理的路徑,將該個體加入到種群中,循環重復該過程直到達到種群數量。通過該方法構建種群,提高了初始種群的質量,從而加快了算法的求解速度。

2.3 計算適應度值

個體的好壞由個體的適應度值決定,個體在種群的適應度值越大,則代表該個體在種群中越優秀,被保留下來的概率也越大,由于CVRP的目標是使總的運輸距離最小,所以需要將目標函數進行轉換,適應度函數為:

(6)

(7)

式中:Zi----該個體對應的目標函數值(該個體的運輸距離);

N----客戶的個數。

2.4 選擇操作

通過精英保留策略和輪盤賭對個體進行選擇,算法初期由于種群個體較差,不宜保留過多精英個體,通過動態調整精英個體數量來加快算法的求解速度,其基本步驟為:

1)計算種群所有個體適應度值,并按照從大到小依次排序;

2)根據式(8)確定當前保留優秀個體數量,剩余個體則按照輪盤賭的方式進行選擇。

(8)

式中:ceil----向上取整;

N----種群個體數量;

P----優秀個體占總個體的比例;

x----當前迭代次數。

由于算法迭代初期不存在優良個體或優良個體較少,若使用固定數量的保留策略,則會影響種群的多樣性,從而造成搜索范圍的減少,而動態精英保留策略在算法迭代初期,保留數量較少,不會對種群多樣性造成破壞。到了算法后期,個體達到最優或接近最優,此時保留數量增加,又可以避免個體被破壞。

通過該選擇策略,既避免了輪盤賭導致的隨機誤差,又提高了種群的多樣性,保證了算法的收斂速度。

2.5 交叉操作

交叉操作是種群新個體產生的主要來源,遺傳算法在開始時由于種群種類豐富,但是解的質量并不高,適當提高種群的交叉概率以提高尋優速度,而到了算法后期,個體解的質量都接近最優解,此時適當減小種群的交叉概率可以避免交叉對優質解的破壞。

文中對交叉概率進行改進,改進的交叉概率為

(9)

式中:Ps----初始交叉概率;

fa----當前種群的平均適應度值;

f′a----種群初始平均適應度值。

文中對染色體的交叉采用單點交叉與兩點交叉結合方式,其基本步驟如下:

1)以一定的概率Pc隨機選擇單點交叉或兩點交叉。

2)若選取單點交叉,以父親染色體起點到切點之間的基因作為孩子染色體的初始狀態。依次遍歷母親染色體,若當前孩子染色體長度小于L,將孩子不存在的基因在孩子初始染色體頭部依次加入,否則在當前孩子染色體的末尾加入,如圖1所示。

圖1 單點交叉示意圖

3)若兩點交叉,以父親染色體切點X與Y之間的基因作為孩子染色體的初始狀態。依次遍歷母親染色體,若當前孩子染色體長度小于L,則在切點X前依次加入,否則在當前孩子染色體末尾加入,如圖2所示。

圖2 兩點交叉示意圖

L=N-X,

(10)

式中:N----客戶數量;

X----第一個切點的位置。

2.6 變異操作

變異操作是種群產生新個體的另一種方法,若變異概率恒定,則可能造成優秀個體的丟失,為了保存種群的優秀個體,文中采用動態調整變異概率的方式來實現優秀個體的保留。每個個體的變異概率為

(11)

式中:fi----當前個體的適應度值。

采用兩點互換的操作進行染色體的變異操作,即在個體中隨機選擇兩個不同的基因位置進行交換,如圖3所示。

圖3 變異操作示意圖

2.7 變鄰域搜索算法

由于遺傳算法本身存在局部搜索能力不足的缺點,雖然也能夠以一定的概率找到最優解,但是要花費很大的時間代價,為了擴大搜索算法的搜索空間,文中在遺傳操作之后加入了變鄰域搜索算法,通過將遺傳算法與鄰域搜索算法進行結合,更好地提高解的質量與求解速度。文中設計了2-opt法、兩點交換法和單點插入法,這些算法不僅無需復雜的參數設置、設計簡單,而且加快了遺傳算法尋優的速度。

1)2-opt是求解路徑最常用的局部搜索算法,即

ab+cd

則刪除邊ac與bd,連接ab與cd,并把頂點b與c之間的邊反向,如圖4所示。

圖4 2-opt示意圖

2)兩點交換法是從路徑間或路徑內隨機選擇兩個客戶點,如果交換有效,則交換兩個客戶點在路徑中的位置,即

db+bc+ca

如圖5所示。

圖5 交換法示意圖

3)單點插入法是從路徑間或路徑內隨機一個客戶點插入到最佳位置。即

da+ab+bc

如圖6所示。

圖6 單點插入法示意圖

2.8 算法流程

1)初始化參數,種群規模為M,最大迭代次數Tmax,交叉概率Ps和變異概率Pmu,交叉點選擇概率Pc,當前迭代次數0。

2)采用變鄰域搜索算法對種群進行初始化。

3)計算個體適應度值大小,進行從大到小排序。

4)根據動態精英保留策略和輪盤賭的方式選擇個體。

5)根據交叉概率公式決定被選擇個體是否進行交叉操作,并根據概率選擇交叉方式。

6)若Prand_mu

7)遺傳操作完成后,對新生成的染色體進行變鄰域搜索,選擇合適的調整方法對新染色體進行調整。

8)當前迭代次數加1,判斷是否達到最大迭代次數,若沒有達到,繼續從3)開始執行,否則輸出最優結果。

3 實驗結果

3.1 測試用例與環境

為了驗證該算法在求解有容量車輛路徑問題的準確性,文中選用20個CVRP的算例進行測試。實驗環境:CPU為AMD Ryzen 7 4800H with Radeon Graphics 2.90 GHz,內存選取為8 GB,操作系統為64位Windows10,采用整數運算,實驗誤差定義為

已知最優解為測試數據集提供的最優解。

3.2 數據分析

實驗過程對算法參數進行初始化,最大迭代次數Tmax為100,初始種群數量M為10,交叉概率Pcro為0.6,變異概率Pmu為0.1,交叉點個數選擇概率Pcro_num為0.7,當前迭代次數0。選取了CVRPLIB數據集中部分算例運行結果如圖7所示。

圖7 部分實例結果圖

由圖7可知,改進后的遺傳算法無論是在求解準確率,還是在求解速度上都有明顯提高。

對每個實例統計20次,CVRP實驗結果見表1。

表1 改進遺傳算法求解CVRP實驗結果

由表1可以看出,當客戶節點在50個以內時,可以求出最優解,且平均誤差也能保證在1%以內,隨著客戶節點個數的增加,該算法也能夠得到最優解或者接近最優解,且平均誤差可以保證在1.8%以內。

在實驗環境相同的情況下,為進一步驗證算法的準確性,文中與AGGWOA[13]、ISA[14]、VNSS[15]算法進行比較,結果見表2。

表2 混合遺傳算法同其他算法比較

由表2可以看出,文中提出的混合遺傳算法在求解A類數據集時,無論是在求解最優解還是平均值,都要優于遺傳算法與灰狼算法結合的算法AGGWOA和改進后的模擬退火算法ISA,但要弱于改進后的鄰域搜索算法。

隨著客戶節點個數的增加,所有算法的求解能力都有所下降,文中算法的下降速度要低于其他算法。

4 結 語

在傳統遺傳算法的基礎上進行了改進,通過采用變鄰域搜索算法完成對種群的初始化,并將分組策略和輪盤賭相結合進行染色體的選擇,避免了算法陷入局部最優。將單點交叉和兩點交叉結合的交叉方式在算法后期仍然能夠保證種群的多樣性,文中通過CVRP的案例,與其他啟發式算法進行比較,無論是在求解效率和求解質量上都有明顯提高,對今后車輛調度問題的研究有很大幫助。