改進(jìn)蟻群算法求解帶容量限制的車輛路徑問(wèn)題*

徐澤峰 蔡延光

?

改進(jìn)蟻群算法求解帶容量限制的車輛路徑問(wèn)題*

徐澤峰 蔡延光

（廣東工業(yè)大學(xué)自動(dòng)化學(xué)院）

對(duì)蟻群算法進(jìn)行改進(jìn)以增加其在處理帶容量限制的車輛路徑問(wèn)題時(shí)的性能。改進(jìn)后的算法建立每一個(gè)點(diǎn)的臨近點(diǎn)序列以增加生成解的質(zhì)量并減少計(jì)算時(shí)間。設(shè)定一個(gè)信息素最小值，避免算法由于部分邊上信息素值過(guò)低而被忽略。在計(jì)算選擇概率時(shí)將所有邊全部減小一個(gè)相同的值，以增加邊長(zhǎng)在決定選擇時(shí)的作用。增加一只記憶螞蟻來(lái)增強(qiáng)算法的收斂能力，令螞蟻在前進(jìn)過(guò)程中有可能回到出發(fā)點(diǎn)，通過(guò)這種方法讓算法具有檢索所有解的可能。在算法的最后加入對(duì)解的調(diào)整操作，進(jìn)一步靠近全局最優(yōu)解。用該算法計(jì)算通用的VRP算例，驗(yàn)證了算法的有效性。

CVRP；蟻群算法；臨近點(diǎn)序列

0　引言

車輛路徑問(wèn)題（vehicle routing problem，VRP），Dantzig等人于1959年首先提出[1]，并成為組合優(yōu)化領(lǐng)域的熱點(diǎn)問(wèn)題。根據(jù)給出的限制條件不同VRP有很多種，其中一種稱為帶容量限制的車輛路徑問(wèn)題（capacitated vehicle routing problem，CVRP）。該問(wèn)題可描述為：有一個(gè)中心站和若干個(gè)客戶，中心站和客戶相互之間的距離均為已知。中心站有若干輛卡車。現(xiàn)在要從中心站使用這些卡車向各個(gè)客戶運(yùn)送貨物，每個(gè)客戶對(duì)貨物的需求量一定，同時(shí)所有卡車都有負(fù)載限制。每個(gè)客戶必須且只被一輛卡車送貨一次，每輛卡車最多送貨一次。要求給出合起來(lái)最短的所有卡車的送貨路徑。

旅行商問(wèn)題（traveler salesman problem，TSP），可認(rèn)為是VRP問(wèn)題的一個(gè)特例。TSP問(wèn)題可描述為：有若干個(gè)城市，它們相互之間的距離已知，一個(gè)旅行商人要從一個(gè)固定的起點(diǎn)前往所有城市，每個(gè)城市必須且僅經(jīng)過(guò)一次，并最終返回起點(diǎn)，要求給出一條最短的移動(dòng)路徑。

蟻群算法于1992年由Dorigo提出，被用于解決TSP問(wèn)題以及其他組合優(yōu)化問(wèn)題[2-4]。用蟻群算法處理TSP問(wèn)題時(shí)，一只螞蟻可以在所有還未前往的點(diǎn)中選擇下一個(gè)前往點(diǎn)。但在VRP問(wèn)題中，需要考慮卡車的容量，因此螞蟻每一次選擇時(shí)要考慮的并不是所有還未前往的點(diǎn)，這給構(gòu)成可行解帶來(lái)了困難，因此，蟻群算法很難直接用來(lái)解決VRP問(wèn)題[5-9]。

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

1.1蟻群算法

蟻群算法處理TSP問(wèn)題的流程：

1) 初始化所有邊上的信息素為某特定值（該值事先給出）；

2) 初始化螞蟻的位置為起始點(diǎn)；

3) 螞蟻在當(dāng)前點(diǎn)形成選擇輪盤，輪盤中包含所有還未前往的點(diǎn)，每一點(diǎn)具有一定的被選擇概率，這個(gè)概率由該點(diǎn)與螞蟻當(dāng)前點(diǎn)的距離和該條邊上的信息素值決定，選擇數(shù)為距離倒數(shù)的次方和信息素的次方的乘積，該點(diǎn)的選擇數(shù)在所有可選點(diǎn)選擇數(shù)之和中所占比例即為該點(diǎn)被選擇的概率，其中，和為事先給定的常數(shù)，分別稱為距離因子和信息素因子，重復(fù)進(jìn)行3)直到所有點(diǎn)被選擇，之后螞蟻返回初始點(diǎn)，構(gòu)成一個(gè)解，螞蟻的數(shù)量事先給定，當(dāng)每一只螞蟻各自獲得一個(gè)解之后，轉(zhuǎn)入4)；

4) 計(jì)算所有螞蟻獲得的解路徑長(zhǎng)，取最短的一條，在該條路徑包含的所有邊上增加信息素值，增加量一般為路徑長(zhǎng)的倒數(shù)乘以一個(gè)事先給定的常數(shù)；

5) 令所有邊上的信息素減小一定的比例，一般設(shè)定為10%，這樣可在之后的循環(huán)中找到更好的解時(shí)消除之前循環(huán)找到的解的影響。

至此，算法一輪循環(huán)結(jié)束，轉(zhuǎn)入2)開始新的循環(huán)。

1.2 回歸概率

使用蟻群算法處理VRP問(wèn)題時(shí)，首先需要解決解的構(gòu)成方式問(wèn)題。構(gòu)成解最大的困難在于卡車的容量有限，當(dāng)一輛車服務(wù)過(guò)多的客戶點(diǎn)時(shí)，它會(huì)超載。算法在解的構(gòu)成方面有2種設(shè)計(jì)思路。第一種思路，一只螞蟻從中心站出發(fā)，依次選擇下一個(gè)前往的點(diǎn)，如果所選擇的下一個(gè)點(diǎn)會(huì)讓已經(jīng)前往的所有點(diǎn)的需求之和大于卡車的最大容量，即這只螞蟻超載，則不前往該點(diǎn)，并返回中心站，從而構(gòu)成一條回路。例如，螞蟻已選擇的點(diǎn)的需求量和為98，卡車最大容量為100，這時(shí)若選擇一個(gè)需求為8的點(diǎn)，由于選擇該點(diǎn)之后容量將超過(guò)100，所以不選這個(gè)點(diǎn)，并返回起點(diǎn)，構(gòu)成一條回路。此后，繼續(xù)構(gòu)成其他各條回路，從而生成一個(gè)解。第二種思路，等于卡車數(shù)目的螞蟻同時(shí)從中心站出發(fā)，每一次其中隨機(jī)一只螞蟻從目前還沒有被任何螞蟻選擇的點(diǎn)中選擇一個(gè)點(diǎn)。如果一次選擇將讓一只螞蟻超載，則該次選擇無(wú)效。第二種思路比第一種思路的優(yōu)勢(shì)在于，它有檢索所有解的可能。然而實(shí)驗(yàn)表明，使用第二種思路時(shí)算法獲得的結(jié)果不如第一種思路，獲得可行解更加困難，算法運(yùn)行時(shí)間顯著增加，并且對(duì)提升解的質(zhì)量沒有幫助。因此，使用第一種思路來(lái)設(shè)計(jì)算法。與此同時(shí)，設(shè)置一個(gè)回歸概率，使算法具有檢索所有解的可能。如果剩余的車輛可用次數(shù)能夠承載剩余的所有點(diǎn)的需求，則螞蟻以該回歸概率立刻回到中心站。例如，車的總數(shù)為5，所有車的最大載重為100，螞蟻正在進(jìn)行第二條回路的生成，因此剩余車輛使用次數(shù)3，剩余的所有點(diǎn)的總需求為280，小于3輛車可以承載的300，此時(shí)生成0到1的隨機(jī)數(shù)，若該數(shù)小于回歸概率，則螞蟻回到中心站，結(jié)束該條回路的生成，開始生成下一條回路。

即使不設(shè)置回歸概率，螞蟻依然有可能在走完所有點(diǎn)之后不能形成可行解。設(shè)置回歸概率后，這種可能性會(huì)增加。如果螞蟻形成的不是可行解，則放棄該解，重新生成一個(gè)解。增加不能生成可行解的概率之后，算法消耗的時(shí)間將會(huì)增加。

1.3臨近點(diǎn)序列

在螞蟻每一次的選擇中，很多時(shí)候需要考慮讓相對(duì)較長(zhǎng)的邊參與解的構(gòu)成。由于蟻群算法本身的特性，如果一條較長(zhǎng)的邊在算法的某一輪循環(huán)后，包含在最后增加的信息素路徑中，這條邊很可能在之后的計(jì)算中不被舍棄，導(dǎo)致算法最終無(wú)法收斂到一個(gè)較好的解。因此，如果在螞蟻選擇時(shí)不考慮這些邊，不僅能夠增加生成解的質(zhì)量，還能夠減少計(jì)算時(shí)間。

具體做法是，除了中心站外，對(duì)每個(gè)點(diǎn)生成其臨近點(diǎn)序列，即將除中心站之外的所有其他點(diǎn)按照到該點(diǎn)的距離，從近到遠(yuǎn)進(jìn)行排序產(chǎn)生序列。從該點(diǎn)開始，依次將點(diǎn)的需求相加，直到需求和大于某個(gè)事先給定的值為止，這個(gè)值稱為臨近點(diǎn)載重，一般與卡車最大載重相同。但對(duì)某些算例，臨近點(diǎn)載重過(guò)小可能導(dǎo)致形成可行解的難度過(guò)大，此時(shí)可以考慮適當(dāng)增大該值。

1.4 信息素最小值

為讓之前獲得的解產(chǎn)生信息素的影響消失，在一輪循環(huán)的最后按照給定比例減少所有邊上的信息素。這樣會(huì)導(dǎo)致部分對(duì)生成好的結(jié)果有幫助的邊因在最初的幾輪循環(huán)中沒有被選中，其信息素不斷衰減，之后的循環(huán)中也很難被選中。通過(guò)設(shè)定信息素最小值，能夠避免出現(xiàn)這樣的情況。還可增加算法在后期檢索更多解的能力，避免陷入局部最優(yōu)解。具體做法是，在每一輪循環(huán)的最后降低所有邊的信息素時(shí)，如果降低后一條邊的信息素少于設(shè)定的信息素最小值，則令其回到該最小值。

1.5 產(chǎn)生選擇輪盤時(shí)改變所有邊的長(zhǎng)度

一般蟻群算法通過(guò)調(diào)整距離因子和信息素因子使其具有理想的性能，但由于2個(gè)因子都是指數(shù)，算法設(shè)計(jì)者難以對(duì)實(shí)際計(jì)算中各個(gè)概率有直觀的認(rèn)識(shí)，對(duì)2個(gè)因子的調(diào)整非常困難。生成解的總路徑長(zhǎng)取倒數(shù)后波動(dòng)不大，從而對(duì)每輪循環(huán)信息素的增加值的影響波動(dòng)不大。信息素是以固定的比例衰減，因此一條邊上的信息素永遠(yuǎn)不可能超過(guò)某個(gè)值。例如，初始信息素為0.5，衰減比例為10%，每次增加信息素都在0.1左右波動(dòng)，則一條邊上的信息素永遠(yuǎn)不會(huì)超過(guò)1.2。又因?yàn)樵O(shè)定了最小的信息素值，信息素對(duì)選擇概率的影響非常明顯。在距離因子固定的情況下，在計(jì)算選擇概率時(shí)將邊長(zhǎng)增加或減小一定的值來(lái)調(diào)整邊長(zhǎng)對(duì)選擇概率的影響。例如，所有邊中最大的邊長(zhǎng)為100，最小的邊長(zhǎng)為2。為了增加邊的影響，可以將所有邊長(zhǎng)減小1，此時(shí)最大邊與最小邊長(zhǎng)度的比值從50增加到100。而如果將所有邊長(zhǎng)增加2，則該比值從50減小到了25。當(dāng)距離因子和信息素因子都設(shè)為1時(shí)，上述邊比值的變化就是實(shí)際選擇時(shí)選擇概率的變化。

1.6 記憶螞蟻

算法中可能出現(xiàn)這樣情況：之前獲得的一個(gè)解改變了信息素，下一輪循環(huán)中獲得的解劣于已經(jīng)獲得的解。由于信息素衰減的緣故，較優(yōu)解對(duì)信息素的影響有所衰減，而新獲得的較劣解的影響還沒有衰減，導(dǎo)致后續(xù)生成的解對(duì)之前較優(yōu)解的參考很弱。這在實(shí)驗(yàn)中的體現(xiàn)，就是每一輪循環(huán)獲得的最優(yōu)解都有很大可能劣于上一輪循環(huán)獲得的最優(yōu)解。

通過(guò)增加一只記憶螞蟻可以改變這一狀況。有一只特殊的螞蟻并不參與形成解，而是記錄之前所有循環(huán)中獲得的最優(yōu)解。如果一輪循環(huán)之后得到的最優(yōu)解比記憶螞蟻記錄的解好，則記憶螞蟻記下新的解。每一輪循環(huán)結(jié)束之后，由記憶螞蟻和該輪循環(huán)的最優(yōu)解共同增加信息素。

1.7 優(yōu)化解

在算法的最后可以對(duì)獲得的解進(jìn)行進(jìn)一步處理來(lái)繼續(xù)優(yōu)化。所采用的方法類似于2-opt[10]，但有所不同。區(qū)別在于，2-opt隨機(jī)決定互換的兩點(diǎn)，而本文是對(duì)所有的互換進(jìn)行搜索。

具體做法是，對(duì)每一條回路的所有客戶點(diǎn)之間的所有兩點(diǎn)互換進(jìn)行檢索。如果互換后該條回路的長(zhǎng)度減小則應(yīng)用這一互換，并重新對(duì)該條回路進(jìn)行檢索。檢索完所有的回路之后，所得到的解就是算法最終解。

2　實(shí)驗(yàn)結(jié)果及分析

采用通用CVRP的19個(gè)算例測(cè)試算法，這些算例在文獻(xiàn)[10-12]中使用，具體結(jié)果如表1所示。

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

表1中列出所得最優(yōu)解、已經(jīng)發(fā)表的最優(yōu)解和所得最優(yōu)解與已知最優(yōu)解的相對(duì)差距，算得所得最優(yōu)解時(shí)花費(fèi)的時(shí)間。

表2列出了程序運(yùn)行時(shí)的部分參數(shù)。沒有列出的參數(shù)統(tǒng)一如下：距離因子和信息素因子均設(shè)定為1；初始信息素為0.5；螞蟻數(shù)量為34；信息素最小值為0.01；增加信息素時(shí)的相乘常數(shù)為100；信息素衰減幅度為10%；循環(huán)次數(shù)為500次。表2中的距離減小值即計(jì)算選擇概率時(shí)距離的減小值。獲得的最優(yōu)解均為程序運(yùn)行5次中最好的一次解，花費(fèi)的時(shí)間均為獲得最優(yōu)解時(shí)運(yùn)行花費(fèi)的時(shí)間。使用CPU主頻2G Hz的微機(jī)，程序編寫采用C++。

表2　計(jì)算時(shí)的部分參數(shù)

算例名稱中n后的數(shù)字代表包含中心站在內(nèi)的點(diǎn)的數(shù)目，如n33表示客戶32個(gè)，中心站1個(gè)。k后數(shù)字為卡車數(shù)目。

本文算法對(duì)n32-k5，n33-k5，n33-k6，n37-k5，n38-k5，n55-k9這6個(gè)算例獲得的最優(yōu)解與已知最優(yōu)解的差距在1%以內(nèi)，對(duì)其他算例差距最大為n45-k6的4.41%，說(shuō)明該算法處理CVRP問(wèn)題比較有效。普通的蟻群算法在修改解的獲得方式后用于VRP問(wèn)題，對(duì)上述所有算例的結(jié)果與已知最優(yōu)解的差距均在10%以上，說(shuō)明蟻群算法的改進(jìn)是有效的。

算例本身的特性對(duì)結(jié)果有很大影響，如對(duì)n55-k9這個(gè)算例獲得了1%以內(nèi)的結(jié)果，說(shuō)明該算法在處理這個(gè)算例時(shí)容易獲得好的結(jié)果。

計(jì)算花費(fèi)的時(shí)間并不隨著問(wèn)題規(guī)模的增大而明顯增加，這是因?yàn)樵撍惴ㄓ?jì)算花費(fèi)的時(shí)間極大地取決于是否生成可行解。就算例本身的特性來(lái)說(shuō)，一些算例較難生成可行解。例如n45-k6和n61-k9，前者的總需求為597，與車的總承載量600僅僅相差3；后者的總需求為885，與900僅相差15。在計(jì)算這2個(gè)算例時(shí)，都較大地增加了臨近點(diǎn)載重，同時(shí)減小了回歸概率，以增加找到可行解的概率。

所有距離減小值的取法均為：計(jì)算所有邊的長(zhǎng)度后，得到最短邊，適當(dāng)取邊長(zhǎng)減小值以使最短邊的邊長(zhǎng)減小到1以下。例如n32-k5的最短邊為2.236，最長(zhǎng)邊為128.004，將所有邊在計(jì)算選擇概率時(shí)減小了2之后，邊長(zhǎng)起到的作用增加了。

3　結(jié)論

本文對(duì)蟻群算法進(jìn)行多方面的改進(jìn)以增加其性能，取得較好的效果。不足之處有：1) 找到可行解的概率與原來(lái)相比顯著下降，導(dǎo)致計(jì)算時(shí)間延長(zhǎng)，可以通過(guò)繼續(xù)的改進(jìn)來(lái)增加找到可行解的概率；2) 通過(guò)蟻群算法找到了一個(gè)相對(duì)較好的解，最后對(duì)解的調(diào)整步驟過(guò)于簡(jiǎn)單，如果使用更好的解的調(diào)整方法可以讓解更加靠近全局最優(yōu)解[14-15]。例如，本文最后僅使用了回路內(nèi)的調(diào)整，而未使用回路間的調(diào)整，因此在回路內(nèi)調(diào)整之前增加一步回路間的調(diào)整將會(huì)增加解的收斂幅度。另外，遺傳算法在最后對(duì)解的調(diào)整中可以起到非常好的效果。

[1] Dantzig G, Ramser J. The truck dispatching problem[J]. Management Scence, 1959, 6(1): 81-91.

[2] Gambardella L M, Dorigo M. Solving symmetric and asymmetric TSPs by ant colonies[C]//IEEE Conference on Evolutionary Computation, ICEC, 1996: 622-627.

[3] Song Y H, Chou C S V, Min Y. Large-scare economic dispatch by artificial ant colony search algorithms[J].Electric Machines and Power System, 1999, 27(7): 679-690.

[4] Bland J A. Space-planning by ant colony optimization[J]. International Journal of Computer Applications in Technology, 1999, 12(6): 320-328.

[5] Jabbarpour M R, Noor R M, Anuar N B, et al. Ant colony optimization for vehicle traffic systems: applications and challenges[J]. International Journal of Bio-Inspired Computation, 2014, 6(1): 32-56.

[6] 劉志碩,申金升,柴躍廷.基于自適應(yīng)蟻群算法的車輛路徑問(wèn)題研究[J].控制與決策,2005,20(5):562-566.

[7] 裴振兵,陳雪波.改進(jìn)蟻群算法及在車輛運(yùn)輸調(diào)度中的應(yīng)用[J].信息與控制,2015,44(6):753-758.

[8] 何文玲,倪郁東,汪婷婷.基于混合行為蟻群算法的車輛路徑問(wèn)題[J].合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,37(7): 883-887.

[9] Liu Y, Wang S, Dong F, et al. A two stage method for VRP based on the improved ant colony algorithm[J]. International Journal of Modeling, identification and Control, 2013, 18(2): 174-181.

[10] Verhoeven M G A, Aarts E H L, Swinkels P C J. A parallel 2-opt algorithm for the travelling salesman problem[J]. Future Generation Computer Systems, 1995, 11(2): 175-182.

[11] 孫晶,白艷萍.改進(jìn)的混合型蟻群算法在VRP問(wèn)題中的應(yīng)用[J].黑龍江大學(xué)自然科學(xué)學(xué)報(bào),2014,31(3):328-334.

[12] 步立新,羅文鈺,馮允成.隨機(jī)遞歸算法求解車輛路徑問(wèn)題[J].系統(tǒng)工程理論與實(shí)踐,2008,28(11):142-148.

[13] 王志剛,夏慧明.求解車輛路徑問(wèn)題的人工蜂群算法[J].計(jì)算機(jī)工程與科學(xué),2014,36(6):1088-1094.

[14] Homaifar A, Guan S, Liepins G E. A new approach on the traveling salesman problem by genetic algorithms[C]//Fifth International Conference on Genetic Algorithms.San Mateo CA USA: Morgan Kaufmann, 1993:460-466.

[15] 鐘石泉,馬壽峰.車輛路徑問(wèn)題的改進(jìn)分支切割法[J].系統(tǒng)工程理論與實(shí)踐,2009,29(10):152-158.

Improved Ant Colony Algorithm for Capacitated Vehicle Routing ProblemComputer Engineering and Applications

Xu Zefeng Cai Yanguang

(School of Automation, Guangdong University of Technology)

Improvements were made to enhance the performance of the ant colony algorithm when used to solve vehicle routing problem. The improved algorithm establishes the near point sequence to improve the quality of solutions and reduce the calculating time. Set a minimum value of pheromone, to avoid that the algorithm ignored edges with low pheromone. Reduced the value of all edges when calculating the selective possibility to enhance the effect of the length of edges when calculating selective possibility. Added a memory ant to enhance the convergence ability. Gave the ants a possibility to return when going forward, this method gives the algorithm the possibility to search all solutions. Added a procedure of modifying the solution at the last of the algorithm to make the solution approach the global optimal solution. Used the universal examples for VRP to test the effectiveness of algorithm, which proved that the algorithm is effective.

CVRP; Ant Colony Algorithm; Near Point Sequence

國(guó)家自然科學(xué)基金（61074147）；廣東省自然科學(xué)基金（S2011010005059）；廣東省教育部產(chǎn)學(xué)研結(jié)合項(xiàng)目（2012B091000171，2011B090400460）；廣東省科技計(jì)劃項(xiàng)目（2012B050600028，2014B010118004，2016A050502060）；廣州市花都區(qū)科技計(jì)劃項(xiàng)目（HD14ZD001）。

徐澤峰，男，1994年生，碩士研究生，主要研究方向：組合優(yōu)化。

蔡延光，男，1963年生，博士，教授，主要研究方向：組合優(yōu)化、人工智能、決策支持系統(tǒng)等。