基于改進(jìn)遺傳算法求解容量約束車輛路徑問(wèn)題

劉祥坤, 李萬(wàn)龍, 李東升, 牛家冰

(長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 吉林 長(zhǎng)春 130102)

0 引 言

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

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

目前對(duì)該模型的求解主要用到的啟發(fā)式算法為蟻群算法[8-10]、遺傳算法和粒子群算法[11-12]等。文中在傳統(tǒng)遺傳算法的基礎(chǔ)上對(duì)種群初始化和選擇操作、交叉操作、變異操作進(jìn)行了改進(jìn),同時(shí)結(jié)合鄰域搜索算法進(jìn)行改進(jìn),以達(dá)到最短時(shí)間內(nèi)求出最優(yōu)解或次最優(yōu)解。

1 CVRP數(shù)學(xué)模型

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

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

2)每個(gè)客戶只能由一輛配送車輛進(jìn)行配送,不能由多輛車進(jìn)行多次配送;

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

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

本問(wèn)題目標(biāo)函數(shù)為配送過(guò)程中所有配送車行駛的總路徑長(zhǎng)度,則問(wèn)題模型如下:

目標(biāo)函數(shù)為

(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)是保證每輛車的配送物資不超過(guò)配送車輛的最大載貨重量,式(3)～式(5)是保證每個(gè)客戶只能由一輛車提供配送。

2 求解過(guò)程

傳統(tǒng)遺傳算法隨著迭代次數(shù)的增加,種群多樣性下降迅速,導(dǎo)致算法搜索能力降低,文中通過(guò)對(duì)基本遺傳算法的操作進(jìn)行改進(jìn),增加搜索范圍,避免陷入局部最優(yōu),提高解的質(zhì)量。

2.1 染色體編碼

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

子路線1:倉(cāng)庫(kù)0-客戶1-客戶3-客戶6-倉(cāng)庫(kù)0;

子路線2:倉(cāng)庫(kù)0-客戶4-客戶7-倉(cāng)庫(kù)0;

子路線3:倉(cāng)庫(kù)0-客戶2-客戶5-倉(cāng)庫(kù)0。

2.2 種群初始化

先采用隨機(jī)生成法生成一條合理的路徑,然后通過(guò)變鄰域搜索算法對(duì)該路徑進(jìn)行不斷交換、替代、倒置等優(yōu)化操作,直至所有客戶點(diǎn)遍歷完成,形成一條更加合理的路徑,將該個(gè)體加入到種群中,循環(huán)重復(fù)該過(guò)程直到達(dá)到種群數(shù)量。通過(guò)該方法構(gòu)建種群,提高了初始種群的質(zhì)量,從而加快了算法的求解速度。

2.3 計(jì)算適應(yīng)度值

個(gè)體的好壞由個(gè)體的適應(yīng)度值決定,個(gè)體在種群的適應(yīng)度值越大,則代表該個(gè)體在種群中越優(yōu)秀,被保留下來(lái)的概率也越大,由于CVRP的目標(biāo)是使總的運(yùn)輸距離最小,所以需要將目標(biāo)函數(shù)進(jìn)行轉(zhuǎn)換,適應(yīng)度函數(shù)為:

(6)

(7)

式中:Zi----該個(gè)體對(duì)應(yīng)的目標(biāo)函數(shù)值(該個(gè)體的運(yùn)輸距離);

N----客戶的個(gè)數(shù)。

2.4 選擇操作

通過(guò)精英保留策略和輪盤賭對(duì)個(gè)體進(jìn)行選擇,算法初期由于種群個(gè)體較差,不宜保留過(guò)多精英個(gè)體,通過(guò)動(dòng)態(tài)調(diào)整精英個(gè)體數(shù)量來(lái)加快算法的求解速度,其基本步驟為:

1)計(jì)算種群所有個(gè)體適應(yīng)度值,并按照從大到小依次排序;

2)根據(jù)式(8)確定當(dāng)前保留優(yōu)秀個(gè)體數(shù)量,剩余個(gè)體則按照輪盤賭的方式進(jìn)行選擇。

(8)

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

N----種群個(gè)體數(shù)量;

P----優(yōu)秀個(gè)體占總個(gè)體的比例;

x----當(dāng)前迭代次數(shù)。

由于算法迭代初期不存在優(yōu)良個(gè)體或優(yōu)良個(gè)體較少,若使用固定數(shù)量的保留策略,則會(huì)影響種群的多樣性,從而造成搜索范圍的減少,而動(dòng)態(tài)精英保留策略在算法迭代初期,保留數(shù)量較少,不會(huì)對(duì)種群多樣性造成破壞。到了算法后期,個(gè)體達(dá)到最優(yōu)或接近最優(yōu),此時(shí)保留數(shù)量增加,又可以避免個(gè)體被破壞。

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

2.5 交叉操作

交叉操作是種群新個(gè)體產(chǎn)生的主要來(lái)源,遺傳算法在開(kāi)始時(shí)由于種群種類豐富,但是解的質(zhì)量并不高,適當(dāng)提高種群的交叉概率以提高尋優(yōu)速度,而到了算法后期,個(gè)體解的質(zhì)量都接近最優(yōu)解,此時(shí)適當(dāng)減小種群的交叉概率可以避免交叉對(duì)優(yōu)質(zhì)解的破壞。

文中對(duì)交叉概率進(jìn)行改進(jìn),改進(jìn)的交叉概率為

(9)

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

fa----當(dāng)前種群的平均適應(yīng)度值;

f′a----種群初始平均適應(yīng)度值。

文中對(duì)染色體的交叉采用單點(diǎn)交叉與兩點(diǎn)交叉結(jié)合方式,其基本步驟如下:

1)以一定的概率Pc隨機(jī)選擇單點(diǎn)交叉或兩點(diǎn)交叉。

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

圖1 單點(diǎn)交叉示意圖

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

圖2 兩點(diǎn)交叉示意圖

L=N-X,

(10)

式中:N----客戶數(shù)量;

X----第一個(gè)切點(diǎn)的位置。

2.6 變異操作

變異操作是種群產(chǎn)生新個(gè)體的另一種方法,若變異概率恒定,則可能造成優(yōu)秀個(gè)體的丟失,為了保存種群的優(yōu)秀個(gè)體,文中采用動(dòng)態(tài)調(diào)整變異概率的方式來(lái)實(shí)現(xiàn)優(yōu)秀個(gè)體的保留。每個(gè)個(gè)體的變異概率為

(11)

式中:fi----當(dāng)前個(gè)體的適應(yīng)度值。

采用兩點(diǎn)互換的操作進(jìn)行染色體的變異操作,即在個(gè)體中隨機(jī)選擇兩個(gè)不同的基因位置進(jìn)行交換,如圖3所示。

圖3 變異操作示意圖

2.7 變鄰域搜索算法

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

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

ab+cd

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

圖4 2-opt示意圖

2)兩點(diǎn)交換法是從路徑間或路徑內(nèi)隨機(jī)選擇兩個(gè)客戶點(diǎn),如果交換有效,則交換兩個(gè)客戶點(diǎn)在路徑中的位置,即

db+bc+ca

如圖5所示。

圖5 交換法示意圖

3)單點(diǎn)插入法是從路徑間或路徑內(nèi)隨機(jī)一個(gè)客戶點(diǎn)插入到最佳位置。即

da+ab+bc

如圖6所示。

圖6 單點(diǎn)插入法示意圖

2.8 算法流程

1)初始化參數(shù),種群規(guī)模為M,最大迭代次數(shù)Tmax,交叉概率Ps和變異概率Pmu,交叉點(diǎn)選擇概率Pc,當(dāng)前迭代次數(shù)0。

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

3)計(jì)算個(gè)體適應(yīng)度值大小,進(jìn)行從大到小排序。

4)根據(jù)動(dòng)態(tài)精英保留策略和輪盤賭的方式選擇個(gè)體。

5)根據(jù)交叉概率公式?jīng)Q定被選擇個(gè)體是否進(jìn)行交叉操作,并根據(jù)概率選擇交叉方式。

6)若Prand_mu

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

8)當(dāng)前迭代次數(shù)加1,判斷是否達(dá)到最大迭代次數(shù),若沒(méi)有達(dá)到,繼續(xù)從3)開(kāi)始執(zhí)行,否則輸出最優(yōu)結(jié)果。

3 實(shí)驗(yàn)結(jié)果

3.1 測(cè)試用例與環(huán)境

為了驗(yàn)證該算法在求解有容量車輛路徑問(wèn)題的準(zhǔn)確性,文中選用20個(gè)CVRP的算例進(jìn)行測(cè)試。實(shí)驗(yàn)環(huán)境:CPU為AMD Ryzen 7 4800H with Radeon Graphics 2.90 GHz,內(nèi)存選取為8 GB,操作系統(tǒng)為64位Windows10,采用整數(shù)運(yùn)算,實(shí)驗(yàn)誤差定義為

已知最優(yōu)解為測(cè)試數(shù)據(jù)集提供的最優(yōu)解。

3.2 數(shù)據(jù)分析

實(shí)驗(yàn)過(guò)程對(duì)算法參數(shù)進(jìn)行初始化,最大迭代次數(shù)Tmax為100,初始種群數(shù)量M為10,交叉概率Pcro為0.6,變異概率Pmu為0.1,交叉點(diǎn)個(gè)數(shù)選擇概率Pcro_num為0.7,當(dāng)前迭代次數(shù)0。選取了CVRPLIB數(shù)據(jù)集中部分算例運(yùn)行結(jié)果如圖7所示。

圖7 部分實(shí)例結(jié)果圖

由圖7可知,改進(jìn)后的遺傳算法無(wú)論是在求解準(zhǔn)確率,還是在求解速度上都有明顯提高。

對(duì)每個(gè)實(shí)例統(tǒng)計(jì)20次,CVRP實(shí)驗(yàn)結(jié)果見(jiàn)表1。

表1 改進(jìn)遺傳算法求解CVRP實(shí)驗(yàn)結(jié)果

由表1可以看出,當(dāng)客戶節(jié)點(diǎn)在50個(gè)以內(nèi)時(shí),可以求出最優(yōu)解,且平均誤差也能保證在1%以內(nèi),隨著客戶節(jié)點(diǎn)個(gè)數(shù)的增加,該算法也能夠得到最優(yōu)解或者接近最優(yōu)解,且平均誤差可以保證在1.8%以內(nèi)。

在實(shí)驗(yàn)環(huán)境相同的情況下,為進(jìn)一步驗(yàn)證算法的準(zhǔn)確性,文中與AGGWOA[13]、ISA[14]、VNSS[15]算法進(jìn)行比較,結(jié)果見(jiàn)表2。

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

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

隨著客戶節(jié)點(diǎn)個(gè)數(shù)的增加,所有算法的求解能力都有所下降,文中算法的下降速度要低于其他算法。

4 結(jié) 語(yǔ)

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