基于改進(jìn)蟻群算法的CVRP問(wèn)題*

張海軍 ，徐廷學(xué) ，逯 程 ，韓 玉

（1.海軍航空大學(xué)，山東 煙臺(tái) 264001；2.海軍航空大學(xué)青島校區(qū)，山東 青島 266041）

0 引言

配送車(chē)輛的路徑問(wèn)題（Vehicle Routing Problem，VRP）是研究物流配送的關(guān)鍵，VRP一直是物流研究領(lǐng)域中的一個(gè)具有重要理論意義和現(xiàn)實(shí)意義的問(wèn)題［1-2］。因此，在物流保障過(guò)程中，需要制定合理有效的配送路徑，選擇省時(shí)省力的方法，在完成保障任務(wù)的前提下，盡最大努力滿足客戶對(duì)配送的需求。

配送車(chē)輛的路徑問(wèn)題（Vehicle Routing Problem，VRP）是 Dantzig 和 Ramser［3］在 1959 年提出來(lái)的。所謂VRP，一般指的是：調(diào)用多輛車(chē)輛，從車(chē)場(chǎng)出發(fā)，對(duì)客戶組織適當(dāng)?shù)男熊?chē)路線，有序地訪問(wèn)所有客戶并且只訪問(wèn)一次，在滿足所有設(shè)定的約束條件下，力爭(zhēng)實(shí)現(xiàn)所設(shè)定的目標(biāo)。帶容量約束的車(chē)輛路徑問(wèn)題（CVRP）是車(chē)輛路徑問(wèn)題（VRP）中的基本問(wèn)題之一，廣泛應(yīng)用于資源配置和物流運(yùn)輸?shù)确矫妗?/p>

求解CVRP的算法大致可以分為精確算法和啟發(fā)式算法兩類(lèi)［4-5］。精確算法（Accurately Arithmetic）在求解規(guī)模較小的路徑優(yōu)化問(wèn)題時(shí)能夠在可承受的空間與時(shí)間消耗下得到精確解。但是配送路徑優(yōu)化問(wèn)題屬于NP問(wèn)題，實(shí)際求解過(guò)程中問(wèn)題的規(guī)模較大，使用精確算法所消耗的空間和時(shí)間成本都是比較大的。而啟發(fā)式算法（Heuristics）不管是求解小規(guī)模的問(wèn)題還是大規(guī)模的問(wèn)題，都能夠在一定的范圍和較短的時(shí)間內(nèi)給出滿意解或最優(yōu)解。因此，目前相關(guān)領(lǐng)域的專(zhuān)家以及研究人員對(duì)于求解算法的主要研究方向是啟發(fā)式算法，特別是對(duì)現(xiàn)代啟發(fā)式算法的研究。蟻群算法作為現(xiàn)代啟發(fā)式算法之一，自從被提出之后就受到了廣泛的關(guān)注，該算法具有正反饋性、并行性和魯棒性等優(yōu)點(diǎn)，在解決任務(wù)分配、路徑優(yōu)化等問(wèn)題時(shí)表現(xiàn)出了良好的性能，但同時(shí)蟻群算法也存在一定的缺陷，如在解決大規(guī)模的問(wèn)題時(shí)，會(huì)出現(xiàn)運(yùn)算時(shí)間長(zhǎng)、收斂速度慢、容易陷入局部最優(yōu)解等問(wèn)題［6］。本文在基本的蟻群算法基礎(chǔ)上進(jìn)行合理改進(jìn)，提高了算法的性能，使算法的運(yùn)算結(jié)果更加準(zhǔn)確。首先，制定轉(zhuǎn)移規(guī)則，更加科學(xué)地初始化車(chē)輛的位置，使得車(chē)輛有更大概率地走出最佳的路徑；然后，在搜索的過(guò)程中與禁忌搜索算法結(jié)合，添加新的參數(shù)負(fù)信息素來(lái)記憶已經(jīng)訪問(wèn)過(guò)的客戶；同時(shí)，使用局部信息素更新和全局信息素更新相結(jié)合的信息素更新方式，并且，全局信息素更新添加了動(dòng)態(tài)更新的新模式；最后，使用2-opt搜索［7］對(duì)結(jié)果進(jìn)行進(jìn)一步的探索，擴(kuò)大搜索的范圍，增加了得到最優(yōu)解的概率。通過(guò)仿真實(shí)驗(yàn)，用不同的算法對(duì)已知案例進(jìn)行仿真，結(jié)果顯示本文算法相對(duì)于其他算法，無(wú)論是結(jié)果的準(zhǔn)確性還是運(yùn)算時(shí)間的長(zhǎng)短都表現(xiàn)出了更好的性能。

1 問(wèn)題描述及數(shù)學(xué)建模

CVRP是從同一車(chē)場(chǎng)出發(fā)的多輛車(chē)輛訪問(wèn)多個(gè)客戶進(jìn)行運(yùn)送貨物的問(wèn)題。已知出發(fā)車(chē)場(chǎng)的位置以及需要訪問(wèn)的客戶的位置，客戶的數(shù)量以及需求數(shù)量，車(chē)輛的數(shù)量以及負(fù)載數(shù)量，對(duì)客戶組織適當(dāng)?shù)男熊?chē)路線，有序地訪問(wèn)所有客戶并且只訪問(wèn)一次，在滿足所有設(shè)定的約束條件下，力爭(zhēng)實(shí)現(xiàn)所設(shè)定的目標(biāo)（車(chē)輛所走的路徑最短或者花費(fèi)最少）。

將現(xiàn)實(shí)問(wèn)題轉(zhuǎn)化為數(shù)學(xué)模型，可以將CVRP描述為m輛車(chē)從車(chē)場(chǎng)0出發(fā)訪問(wèn)n位客戶進(jìn)行運(yùn)送貨物的問(wèn)題。設(shè)di為客戶i的需求數(shù)量，cij為車(chē)輛從客戶i到客戶j的運(yùn)輸花費(fèi)，bk為車(chē)輛k的負(fù)載數(shù)量，而

求解CVRP是為了使車(chē)輛走出的總的路徑最短［8-9］，從而令運(yùn)輸?shù)某杀綣最小，即

且應(yīng)滿足以下約束條件：

式（3）表示所有車(chē)輛都從同一個(gè)車(chē)場(chǎng)出發(fā)，完成所擔(dān)負(fù)的任務(wù)之后全部返回車(chē)場(chǎng)，每一輛車(chē)走出的路徑都形成一個(gè)哈密爾頓巡回；式（4）和式（5）表示車(chē)輛要對(duì)所有客戶進(jìn)行服務(wù)，并且只能服務(wù)一次；式（6）表示每輛車(chē)服務(wù)客戶時(shí)，自身的負(fù)載量不能低于被服務(wù)客戶的總的需求量。

2 算法設(shè)計(jì)

2.1 蟻群算法求解CVRP

使用蟻群算法對(duì)CVRP進(jìn)行求解時(shí)，螞蟻會(huì)在各路徑上產(chǎn)生信息素，信息素ij表示車(chē)輛k在對(duì)客戶i服務(wù)完成之后，下一個(gè)客戶j對(duì)車(chē)輛k產(chǎn)生的吸引程度。當(dāng)車(chē)輛的負(fù)載量能夠滿足客戶的需求時(shí)，車(chē)輛按照設(shè)定好的轉(zhuǎn)移規(guī)則來(lái)選定客戶。在選好所有客戶形成回路之后，對(duì)各路徑上的信息素實(shí)行更新策略，進(jìn)而實(shí)現(xiàn)一次迭代。在迭代達(dá)到最大次數(shù)時(shí)，可以獲得一個(gè)Pareto解集。跟其他的啟發(fā)式算法相比，蟻群算法具有更高的機(jī)能，但在對(duì)CVRP的求解過(guò)程中還是會(huì)有一些不可避免的缺陷。

2.1.1 選取初始客戶過(guò)程中的局限

在CVRP中，因?yàn)檐?chē)輛都有一定的負(fù)載，訪問(wèn)多個(gè)客戶要滿足客戶需求，而每輛車(chē)在訪問(wèn)客戶時(shí)都會(huì)有貨物量限制和訪問(wèn)先后的問(wèn)題，所以求解CVRP受到選取初始客戶的極大影響。運(yùn)用蟻群算法求解CVRP時(shí)，初始化螞蟻位置的方式有兩種：1）全部放置方式。將所有螞蟻全部放置于每個(gè)節(jié)點(diǎn)，這樣搜索的范圍會(huì)很大，更容易得到全局最優(yōu)的解，但同時(shí)也將造成大量時(shí)間的消耗，在處理較大規(guī)模的CVRP時(shí)，會(huì)令問(wèn)題更加復(fù)雜。2）隨機(jī)放置方式。將部分螞蟻隨機(jī)放置到部分節(jié)點(diǎn)，這樣做可以節(jié)省時(shí)間，降低問(wèn)題的復(fù)雜程度，但是也容易造成得到的結(jié)果只是局部最優(yōu)的，令每次迭代得到的Pareto解差距過(guò)大。

2.1.2 信息素更新過(guò)程的局限性。

隨著算法的不斷運(yùn)算，尋找著最優(yōu)路徑，而信息素在路徑上不停地累積，當(dāng)前已尋找到的最優(yōu)路徑上的信息素越來(lái)越多，這或許會(huì)造成以下的不良后果：1）在當(dāng)前已尋找到的最優(yōu)路徑上的信息素過(guò)多，造成算法的停滯。2）即便尋找到新的最優(yōu)路徑，這條路徑上的信息素也遠(yuǎn)遠(yuǎn)沒(méi)有之前得到的最優(yōu)路徑上的信息素多，幾次迭代之后，這種現(xiàn)象也可能沒(méi)有得到緩解?？傊?，在基本蟻群算法中，原有的信息素更新方式會(huì)導(dǎo)致信息素的分布不能很好地體現(xiàn)當(dāng)前最優(yōu)路徑的變化，這會(huì)對(duì)算法的求解過(guò)程造成很大的影響。

2.2 算法改進(jìn)

針對(duì)在求解CVRP時(shí)蟻群算法存在的缺陷，本文改進(jìn)蟻群算法將提高其求解CVRP的性能。

2.2.1 轉(zhuǎn)移概率的改進(jìn)

為了降低算法的復(fù)雜程度，同時(shí)加強(qiáng)算法的精確程度，在算法選擇初始客戶的過(guò)程中，本文將蟻群算法和禁忌搜索進(jìn)行融合，修正轉(zhuǎn)移概率，以改進(jìn)蟻群算法。將禁忌搜索融入蟻群算法主要是利用禁忌搜索長(zhǎng)久的記憶能力來(lái)加強(qiáng)蟻群算法搜索的開(kāi)拓性［10-12］。本文結(jié)合禁忌搜索記憶之前訪問(wèn)過(guò)的節(jié)點(diǎn)，加入了負(fù)信息素的概念：

當(dāng)螞蟻k處于節(jié)點(diǎn)i的位置時(shí)，根據(jù)以下規(guī)則選擇下一節(jié)點(diǎn)：

2.2.2 信息素更新方式

針對(duì)蟻群算法在信息素更新過(guò)程中存在的問(wèn)題，本文使用局部信息素更新和全局信息素更新相結(jié)合的信息素更新方式，并且，全局信息素更新添加了動(dòng)態(tài)更新的新模式。

1）局部更新。在構(gòu)建最優(yōu)路徑的過(guò)程中，螞蟻每經(jīng)過(guò)邊（i，j）都會(huì)依照下面的信息素更新公式來(lái)更新這條邊上的信息素：

其中，ρ1表示局部更新的揮發(fā)系數(shù)，表示信息素的初始值，是一個(gè)較小的正常量，可以設(shè)表示節(jié)點(diǎn)數(shù)，L表示生成的路徑長(zhǎng)度。引入信息素局部更新的目的，是為了使螞蟻在經(jīng)過(guò)邊（i，j）時(shí)，會(huì)揮發(fā)這條邊上一部分的信息素，降低其他的螞蟻同樣選擇這條邊的幾率，可以更多地去探索其他的邊，從而令算法的開(kāi)拓性大大加強(qiáng)。

2）全局動(dòng)態(tài)更新。當(dāng)?shù)淮瓮瓿珊?，按下式?duì)此次迭代得到的最優(yōu)路徑上的信息素實(shí)行全局更新：

式（11）和式（12）可以依照每次迭代得到的最優(yōu)路徑的情況，對(duì)當(dāng)前迭代所得的最優(yōu)路徑上的全局信息素進(jìn)行動(dòng)態(tài)調(diào)整。在x次迭代后，得到了一個(gè)最優(yōu)路徑，相比x-1次迭代，這條路徑要短，L2和L1的差值就為正，說(shuō)明當(dāng)前迭代找到的最優(yōu)路徑比之前尋找到的要好，但此時(shí)該路徑上的信息素濃度并不高，而根據(jù)式（12），L2和L1的差值越大，就會(huì)越大，在之后的迭代中，信息素濃度的積累就會(huì)越快；L2和L1的差值越小就會(huì)越小，在之后的迭代中，信息素濃度的積累就會(huì)越慢；如果在x次迭代后，得到的最優(yōu)路徑比L2要長(zhǎng)，L2和L1的差值就為負(fù)，說(shuō)明當(dāng)前迭代找到的最優(yōu)路徑不如之前尋找到的好，而根據(jù)式（12），L2和L1的差值越大，就會(huì)越大，在之后的迭代中，信息素濃度就會(huì)加快揮發(fā)；L2和L1的差值越小，就會(huì)越小，在之后的迭代中，信息素濃度揮發(fā)的就會(huì)越慢。這種動(dòng)態(tài)調(diào)整是為了讓算法能夠及時(shí)修正迭代得到的結(jié)果，引導(dǎo)算法可以更快地找到最優(yōu)的路徑。

2.2.3 局部搜索策略

為了能夠增加算法的開(kāi)拓性，本文在所有車(chē)輛對(duì)路徑選擇完成之后選用2-opt搜索作為局部搜索的策略，而2-opt搜索只用于一輛車(chē)所選擇的路徑之中。

2.3 算法步驟

根據(jù)以上描述的改進(jìn)策略，改進(jìn)后的算法步驟如下：

2）初始化車(chē)輛的位置。車(chē)輛按照式（8）選擇客戶，將所選擇的客戶添加到中，并更新的值。

3）路徑選擇。在滿足車(chē)輛負(fù)載條件的前提下，車(chē)輛按照式（9）進(jìn)行客戶的選擇；否則車(chē)輛返回車(chē)場(chǎng)。將所選擇的客戶或車(chē)場(chǎng)添加到中，更的值。

4）信息素的局部更新。每當(dāng)車(chē)輛作出一次選擇，便根據(jù)式（10）對(duì)剛剛走過(guò)的路徑（i，j）進(jìn)行信息素的局部更新。

5）2-opt局部搜索。當(dāng)所有車(chē)輛服務(wù)客戶完成之后，尋找路徑完畢時(shí)，對(duì)每輛車(chē)所尋找到的路徑進(jìn)行2-opt搜索，并更新和；否則返回 3）。

3 仿真實(shí)例

在車(chē)輛路由公共數(shù)據(jù)集［13］中選擇標(biāo)準(zhǔn)算例進(jìn)行測(cè)試，使用Matlab進(jìn)行編程，并在CPU為Intel（R）Core（TM）i5-4460 CPU@3.20 GHz 3.20 GHz，內(nèi)存 8G的計(jì)算機(jī)上運(yùn)行。實(shí)驗(yàn)參數(shù)設(shè)置為：ρ1=0.1，ρ=0.1，α=1，β=2，γ=1，e=15～30，r0=0.8～0.95，NC=40。

表1 求解各案例結(jié)果

表1顯示出運(yùn)用本文算法求解選擇出來(lái)的這部分算例的結(jié)果，求解每個(gè)算例都運(yùn)行10次。這里設(shè)B為數(shù)據(jù)集中目前已知的算例最優(yōu)解，R為運(yùn)用本文算法求解該案例得到的最優(yōu)解，P為運(yùn)用本文算法求解案例得到的最優(yōu)解對(duì)比數(shù)據(jù)集中已知最優(yōu)解B的偏移率。從表1可以看出，運(yùn)用給本文算法求解從數(shù)據(jù)集中隨機(jī)抽選的12個(gè)算例中，有7個(gè)案例的求解結(jié)果和數(shù)據(jù)集中已知最優(yōu)解相同，而在剩下5個(gè)結(jié)果有所偏差的案例中，案例N200K17的偏移率最大，但是偏移率僅為2.67%。以上說(shuō)明本文算法的性能是值得肯定的。

此外，從數(shù)據(jù)集中選擇5個(gè)案例，運(yùn)用本文算法與其他算法分別對(duì)案例進(jìn)行求解，得出結(jié)果進(jìn)行比較，表2顯示了對(duì)比的結(jié)果。從表2可以看出，本文算法求解案例得到的最優(yōu)解對(duì)比數(shù)據(jù)集中已知最優(yōu)解的偏移率平均值為0.88%，與其他3種算法相比，僅高于HGA 0.03%。運(yùn)用給本文算法求解從數(shù)據(jù)集中隨機(jī)抽選的5個(gè)算例，有2個(gè)案例的求解結(jié)果和數(shù)據(jù)集中已知最優(yōu)解相同。在求解運(yùn)算的消耗時(shí)間方面，運(yùn)用本文算法求解N51K5、N76K10所消耗的時(shí)間比SA要多一些，而求解另外3個(gè)案例的時(shí)間都是最短的，而且求解這5個(gè)案例所消耗的總時(shí)間最短，平均消耗時(shí)間也最短。

選擇的5個(gè)案例，服務(wù)的車(chē)輛和被服務(wù)的客戶數(shù)量都比較多，問(wèn)題的規(guī)模都很大，在這幾個(gè)大規(guī)模問(wèn)題中，相對(duì)于其他3種算法，本文算法無(wú)論是運(yùn)算結(jié)果還是花費(fèi)的時(shí)間都體現(xiàn)出了更佳的性能，而且問(wèn)題的規(guī)模越大，本文算法體現(xiàn)出的性能越好。

表2 各算法對(duì)案例求解對(duì)比

4 結(jié)論

本文首先對(duì)VRP問(wèn)題的理論進(jìn)行了研究，引出CVRP問(wèn)題，并且對(duì)其進(jìn)行了數(shù)學(xué)模型的建立，然后在基本蟻群算法的基礎(chǔ)上，改進(jìn)算法使其能更好地對(duì)所建模型進(jìn)行求解，最后從數(shù)據(jù)集中抽取案例，運(yùn)用改進(jìn)后的算法進(jìn)行求解，并與其他的算法進(jìn)行比較，得出本文算法無(wú)論是運(yùn)算結(jié)果還是花費(fèi)的時(shí)間都體現(xiàn)出了更佳的性能和結(jié)論。