螞蟻優(yōu)化算法在解決CVRP中的應(yīng)用

劉 瑛

（重慶理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶 400054）

運(yùn)力限制的車(chē)輛路徑問(wèn)題CVRP（Capacitated Vehicle Routing Problem）是最基本的車(chē)輛路徑問(wèn)題，它在VRP問(wèn)題的基礎(chǔ)上加了限制條件，即所有的車(chē)輛對(duì)同一商品具有相同的運(yùn)載能力，每條路線上客戶(hù)的配送總量要小于車(chē)輛的最大運(yùn)載量。具體描述如下:一個(gè)配送中心，對(duì)同一種貨物，使用具有相同最大運(yùn)載能力的車(chē)輛，完成對(duì)需要配送貨物數(shù)量已知的一組客戶(hù)（或城市）的配送。問(wèn)題的目標(biāo)是使行車(chē)路線的運(yùn)輸費(fèi)用最少。該問(wèn)題有以下的限制條件:每個(gè)客戶(hù)只能被一輛車(chē)服務(wù)且只能服務(wù)一次;所有的車(chē)輛必須從配送中心出席，最后回到配送中心;每條行車(chē)路線上的客戶(hù)的配送總量不能超過(guò)車(chē)輛的最大運(yùn)載量;每個(gè)客戶(hù)需要配送的數(shù)量必須小于車(chē)輛的最大運(yùn)載量。

簡(jiǎn)而言之，就是滿足上述限制條件，用相同運(yùn)載能力的車(chē)輛花最少的運(yùn)輸費(fèi)用完成對(duì)所有客戶(hù)點(diǎn)單一貨物的配送。國(guó)外對(duì)物流配送車(chē)輛優(yōu)化調(diào)度問(wèn)題作了大量而深入的研究，該領(lǐng)域的代表人物有Bodin，Christofides，Golden等。在國(guó)內(nèi)，有關(guān)車(chē)輛調(diào)度問(wèn)題的研究是在20世紀(jì)90年代以后才逐漸興起，比國(guó)外相對(duì)落后。國(guó)內(nèi)研究對(duì)象主要是旅行商問(wèn)題（Traveling Salesman Problem，簡(jiǎn)稱(chēng)TSP）、中國(guó)郵遞員問(wèn)題（Chinese Postman Problem，簡(jiǎn)稱(chēng)CPP）、有向中國(guó)郵遞員問(wèn)題（Directed Chinese Postman Problem，簡(jiǎn)稱(chēng)DCPP）等，系統(tǒng)性研究還很少見(jiàn)到。西南交通大學(xué)的李軍教授和郭耀煌教授對(duì)車(chē)輛優(yōu)化調(diào)度的基礎(chǔ)理論及各類(lèi)問(wèn)題進(jìn)行了系統(tǒng)的研究。李大為等以TSP的最近距離啟發(fā)式為基礎(chǔ)，通過(guò)設(shè)置評(píng)價(jià)函數(shù)來(lái)處理時(shí)間窗約束，求解了簡(jiǎn)單的VRP。另外在利用亞啟發(fā)式優(yōu)化算法（如遺傳算法、神經(jīng)網(wǎng)絡(luò)方法、模擬退火等）對(duì)簡(jiǎn)單TSP的求解取得了一定成果。蔡延光等應(yīng)用模擬退火法針對(duì)滿載問(wèn)題進(jìn)行了求解。總體來(lái)說(shuō)，目前我國(guó)對(duì)車(chē)輛調(diào)度問(wèn)題的理論研究仍相對(duì)薄弱，需要進(jìn)一步研究。

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

式（1）為問(wèn)題的目標(biāo)函數(shù)，表示完成所有客戶(hù)配送，所用車(chē)輛行駛路線長(zhǎng)度總和的最小值;式（2）表示第k輛車(chē)的配送客戶(hù)的貨物總量不能超過(guò)車(chē)輛的最大運(yùn)載量q;式（3）表示每個(gè)客戶(hù)i只能讓一輛車(chē)進(jìn)行配送服務(wù)，并且只能被服務(wù)一次;式（4）表示每輛車(chē)k，最多只能開(kāi)往客戶(hù)j一次;式（5）表示每輛車(chē)k最多只能離開(kāi)客戶(hù)i一次式（4）和式（5）結(jié)合在一起說(shuō)明每輛車(chē)k對(duì)每個(gè)客戶(hù)點(diǎn)進(jìn)入一次，就必須離開(kāi)一次，并且最多只能訪問(wèn)一次。

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

2.1 基本螞蟻算法求解CVRP問(wèn)題的模型

螞蟻算法解決CVRP問(wèn)題，關(guān)鍵在于單只螞蟻一次迭代如何構(gòu)建整個(gè)問(wèn)題的一個(gè)可行解。在一次迭代中，螞蟻通過(guò)正確選擇下一個(gè)可以訪問(wèn)的客戶(hù)來(lái)進(jìn)行移動(dòng)，在選擇下一個(gè)客戶(hù)時(shí)，由于車(chē)輛運(yùn)載能力限制，沒(méi)有客戶(hù)可選擇時(shí)，就選擇配送中心，然后開(kāi)始下輪的螞蟻循環(huán)，直到所有客戶(hù)都被訪問(wèn)，尋找到問(wèn)題的一個(gè)解，然后更新殘留信息素完成一次迭代。螞蟻在選擇下一個(gè)可訪問(wèn)的客戶(hù)時(shí)受到以下兩個(gè)因素影響，一個(gè)是與連接當(dāng)前客戶(hù)i到選擇客戶(hù)j這條邊相關(guān)的殘留信息素τij，另一個(gè)就是啟發(fā)信息ηij，一般的，啟發(fā)信息ηij=1/cij，cij為兩點(diǎn)的距離。在可訪問(wèn)的客戶(hù)節(jié)點(diǎn)集allowed={j∈V，j滿足限制條件}∪{0}，依據(jù)隨機(jī)性原則選擇客戶(hù)j，螞蟻k從客戶(hù)i出發(fā)下一站選擇客戶(hù)j的概率的計(jì)算方法如式（6）:

α為殘留信息素的相對(duì)重要程度，β為啟發(fā)信息（也叫可見(jiàn)性）的重要程度，通過(guò)調(diào)整α，β來(lái)決定殘留信息素和啟發(fā)信息在選擇概率的相對(duì)作用大小。

螞蟻算法首先進(jìn)行初始化，螞蟻數(shù)量m設(shè)成和客戶(hù)的數(shù)量n相等，每只螞蟻在不同的客戶(hù)點(diǎn)，算法初始化后，將上面兩個(gè)步驟構(gòu)造解路徑和更新信息素循環(huán)執(zhí)行指定的次數(shù)Imax就是基本的螞蟻算法模型。

2.2 局部搜索優(yōu)化

2－opt啟發(fā)式搜索是通過(guò)對(duì)邊的交換產(chǎn)生一個(gè)2－opt解路徑，所謂的2－opt解路徑就是通過(guò)交換任意不相鄰的兩邊來(lái)縮短解路徑的長(zhǎng)度，直到以這種方式不能再縮短解路徑為止。人工螞蟻可以將2－opt搜索優(yōu)化用到構(gòu)造解的過(guò)程中。在每次迭代過(guò)程的最后，用2－opt對(duì)每只螞蟻找到車(chē)輛路徑進(jìn)行局部搜索優(yōu)化，然后再計(jì)算所有路徑的長(zhǎng)度，對(duì)優(yōu)化后路徑進(jìn)行信息素更新。在螞蟻算法中引入2－opt搜索優(yōu)化過(guò)程，可以大大提高局部解路徑的質(zhì)量，加快螞蟻算法的收斂速度。

2.3 問(wèn)題相關(guān)的算法

CVRP有一些特點(diǎn)能夠用到螞蟻算法中幫助改進(jìn)螞蟻算解路徑的質(zhì)量。在CVRP問(wèn)題，不僅兩個(gè)客戶(hù)的相對(duì)路徑對(duì)螞蟻搜索路徑很重要，而且這兩個(gè)客戶(hù)與配送中心的相對(duì)位置也很重要。利用節(jié)約量μij可以判斷連接客戶(hù)i和客戶(hù)j的可行性，μij=cio+coj－cij，節(jié)約量越大，表示在客戶(hù)i選擇客戶(hù)j越好，將節(jié)約量與螞蟻算法的轉(zhuǎn)移概率聯(lián)系起來(lái)，節(jié)約量越大，選擇的概率就越大，即pij～，這樣就能提高螞蟻系統(tǒng)可行解的質(zhì)量。

CVRP有運(yùn)力限制的約束條件，因此，高的運(yùn)力利用率有利于找到問(wèn)題的滿意解。設(shè)qi是車(chē)輛在客戶(hù)i的總運(yùn)載量，包括客戶(hù)i的需要運(yùn)輸?shù)呢浳锪浚瑥目蛻?hù)i到客戶(hù)j的運(yùn)力利用率kij=（qi+gj）/q，將運(yùn)力利用率和選擇概率聯(lián)系起來(lái)，運(yùn)力利用率越大，選擇概率越大，即pij～，將節(jié)約量和運(yùn)力利用率加入大選擇概率的求解過(guò)程中來(lái)對(duì)螞蟻算法進(jìn)行優(yōu)化，這樣在客戶(hù)i選擇客戶(hù)j的選擇概率公式（8）如下:

3 實(shí)例求解與分析

3.1 標(biāo)準(zhǔn)數(shù)據(jù)集測(cè)試

采用關(guān)于CVRP問(wèn)題的標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集E－n22－k4來(lái)測(cè)試算法，對(duì)基本螞蟻算法求解車(chē)輛路徑問(wèn)題的性能進(jìn)行分析。E－22－k4問(wèn)題為22階CVRP，包括一個(gè)配送中心，21個(gè)客戶(hù)，至少要用4輛車(chē)進(jìn)行配送，每輛車(chē)的最大運(yùn)載量為6 000，目前的最優(yōu)解為375。對(duì)基本螞蟻算法（AS），進(jìn)行局部搜索優(yōu)化的螞蟻算法（AS+LS），加入精英螞蟻的螞蟻算法（AS+E），加入與問(wèn)題相關(guān)參數(shù)的算法（AS+P），以及融入所有改進(jìn)的綜合螞蟻算法（AS+ALL）進(jìn)行數(shù)據(jù)測(cè)試分析，分析各自的特點(diǎn)。AS+LS，AS+E，AS+P都是在基本螞蟻算法基礎(chǔ)上進(jìn)行某一方面的改進(jìn)。最后，將AS+ALL用來(lái)解決幾個(gè)標(biāo)準(zhǔn)的CVRP數(shù)據(jù)模型來(lái)驗(yàn)證算法的可行性。再對(duì)基本參數(shù) α，β，ρ，σ，m等進(jìn)行初步性能測(cè)試之后，最終確定Imax=5 000，α =1，β =1，ρ=0.99，γ =1，σ =8，m=10。

表1 幾種蟻群算法的比較

分析實(shí)驗(yàn)結(jié)果（表1），AS算法能夠接近模型的最優(yōu)解835，但是解的質(zhì)量還是有些不夠理想，平均解只有856.8，穩(wěn)定性較差，最優(yōu)和最差相差17，收斂速度差，平均需迭代1 737次。AS+LS算法將局部解進(jìn)行交換優(yōu)化，使得算法有了很大改進(jìn)，平均解達(dá)到843，算法比較穩(wěn)定，最差的解為843，迭代的次數(shù)降低，實(shí)際上，通過(guò)局部?jī)?yōu)化將局部解優(yōu)化，在優(yōu)化后的路徑上釋放信息素，使得整個(gè)螞蟻的搜索的過(guò)程向著更接近最優(yōu)解的搜索空間進(jìn)行搜索，而且當(dāng)螞蟻迭代到一定的次數(shù)后，結(jié)果變的穩(wěn)定，很難再找到更優(yōu)解，這時(shí)只能通過(guò)局部搜索優(yōu)化來(lái)改進(jìn)解。AS+E算法使得算法是當(dāng)前螞蟻的搜索空間向著當(dāng)前最好解的方向收斂，加快了螞蟻算法的收斂速度，因此，平均解達(dá)到846.7，解的質(zhì)量相對(duì)AS有所提高，數(shù)據(jù)中的平均迭代次數(shù)為2 047，相對(duì)AS有所提高，因?yàn)樗惴ㄋ阉鬏^好解是一個(gè)收斂過(guò)程，在聚集信息素，數(shù)據(jù)中最好解為846，而最差解為847，由于算法快速向著目前最好解進(jìn)行收斂，導(dǎo)致算法在局部最優(yōu)解的停滯。AS+P算法的解結(jié)果也比AS有了大的提高，平均解為847.9，這說(shuō)明在加入了與問(wèn)題相關(guān)的信息后，這里主要是指車(chē)輛路徑問(wèn)題中加入了節(jié)約量，使得搜索過(guò)程向著滿足問(wèn)題限制得最短路徑收斂，和AS+E一樣，AS+P也會(huì)陷入停滯。將上述得改進(jìn)措施都加入基本螞蟻算法中，螞蟻算法在穩(wěn)定性和最優(yōu)性都得到了提高，達(dá)到了較接近問(wèn)題最優(yōu)解的837，并且比較穩(wěn)定，平均解也是837，收斂速度也比AS有了明顯的改進(jìn)，迭代次數(shù)為1 097次。

3.2 實(shí)例演示

配送中心向上海靜安一中心小學(xué)新海隴小學(xué)、曹行、凌家里、朱家宅、車(chē)溝、西蔡六個(gè)配送點(diǎn)配送商品，一輛車(chē)能配送16件，靜安一中心小學(xué)新海隴小學(xué)庫(kù)需要10件，曹行需要3件，凌家里需要2件，、朱家宅需要8件，車(chē)溝需要3件，西蔡需要3件。初始信息如圖1所示。

圖1 初始信息界面

參數(shù)的設(shè)置，螞蟻所留軌跡數(shù)量常數(shù)Q=10，軌跡強(qiáng)度重要性=1，能見(jiàn)度相對(duì)重要性=3.1，揮發(fā)系數(shù)常數(shù)=0.7，計(jì)算結(jié)果如圖2所示。

圖2 計(jì)算結(jié)果

4 結(jié)語(yǔ)

針對(duì)螞蟻算法收斂性差，易停滯的特點(diǎn)，對(duì)螞蟻算法進(jìn)行了改進(jìn)，獲得了較好的效果。本文采用的是最基本的蟻群優(yōu)化算法，算法雖然經(jīng)過(guò)改進(jìn)，但是穩(wěn)定性不是很好，逼進(jìn)精確解的程度在規(guī)模很大的情況下不很理想，這就要求對(duì)算法進(jìn)行進(jìn)一步改進(jìn)。

［1］BODIN L，GOLDEN B，ASSAD A，et al.Routing and Scheduling of Vehicles and Crews［J］.The State of Art，Computers＆Operations Research，1983（10）:101-103

［2］CHRISTOFIDES N.Vehicle Routing in The Traveling Salesman Problem［J］.A Guide Tour of Combinatorial Optimization，1985（5）:7-9

［3］GOLDEN B L，ASSAD A.Vehicle Routing，Methods and Studies［J］.Elsevier Science Publishers B，1988（10）:57-60

［4］李軍，郭耀煌.物流配送車(chē)輛優(yōu)化調(diào)度理論與方法［M］.北京:中國(guó) 物資出版社，2001

［5］李大衛(wèi).遺傳算法在有時(shí)間窗車(chē)輛路徑問(wèn)題上的應(yīng)用［J］.系統(tǒng)工程理論與實(shí)踐，1999，19（8）:101-103

［6］蔡延光，錢(qián)積新，孫優(yōu)賢.多重運(yùn)輸調(diào)度的模擬退火算法［J］.系統(tǒng)工程理論與實(shí)踐，1998，10:11

［7］張波，葉家瑋，胡郁蔥.模擬退火算法在路徑優(yōu)化問(wèn)題中的應(yīng)用［J］.中國(guó)公路學(xué)報(bào)，2004（1）:79-81

［8］嚴(yán)彬.多種群蟻群算法的研究［D］.寧波大學(xué)，2009