改進蟻群算法求解帶容量限制的車輛路徑問題*

徐澤峰 蔡延光

?

改進蟻群算法求解帶容量限制的車輛路徑問題*

徐澤峰 蔡延光

（廣東工業大學自動化學院）

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

CVRP；蟻群算法；臨近點序列

0　引言

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

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

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

1　算法設計

1.1蟻群算法

蟻群算法處理TSP問題的流程：

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

2) 初始化螞蟻的位置為起始點；

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

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

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

至此，算法一輪循環結束，轉入2)開始新的循環。

1.2 回歸概率

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

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

1.3臨近點序列

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

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

1.4 信息素最小值

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

1.5 產生選擇輪盤時改變所有邊的長度

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

1.6 記憶螞蟻

算法中可能出現這樣情況：之前獲得的一個解改變了信息素，下一輪循環中獲得的解劣于已經獲得的解。由于信息素衰減的緣故，較優解對信息素的影響有所衰減，而新獲得的較劣解的影響還沒有衰減，導致后續生成的解對之前較優解的參考很弱。這在實驗中的體現，就是每一輪循環獲得的最優解都有很大可能劣于上一輪循環獲得的最優解。

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

1.7 優化解

在算法的最后可以對獲得的解進行進一步處理來繼續優化。所采用的方法類似于2-opt[10]，但有所不同。區別在于，2-opt隨機決定互換的兩點，而本文是對所有的互換進行搜索。

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

2　實驗結果及分析

采用通用CVRP的19個算例測試算法，這些算例在文獻[10-12]中使用，具體結果如表1所示。

表1　實驗結果

表1中列出所得最優解、已經發表的最優解和所得最優解與已知最優解的相對差距，算得所得最優解時花費的時間。

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

表2　計算時的部分參數

算例名稱中n后的數字代表包含中心站在內的點的數目，如n33表示客戶32個，中心站1個。k后數字為卡車數目。

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

算例本身的特性對結果有很大影響，如對n55-k9這個算例獲得了1%以內的結果，說明該算法在處理這個算例時容易獲得好的結果。

計算花費的時間并不隨著問題規模的增大而明顯增加，這是因為該算法計算花費的時間極大地取決于是否生成可行解。就算例本身的特性來說，一些算例較難生成可行解。例如n45-k6和n61-k9，前者的總需求為597，與車的總承載量600僅僅相差3；后者的總需求為885，與900僅相差15。在計算這2個算例時，都較大地增加了臨近點載重，同時減小了回歸概率，以增加找到可行解的概率。

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

3　結論

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

[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] 劉志碩,申金升,柴躍廷.基于自適應蟻群算法的車輛路徑問題研究[J].控制與決策,2005,20(5):562-566.

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

[8] 何文玲,倪郁東,汪婷婷.基于混合行為蟻群算法的車輛路徑問題[J].合肥工業大學學報(自然科學版),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] 孫晶,白艷萍.改進的混合型蟻群算法在VRP問題中的應用[J].黑龍江大學自然科學學報,2014,31(3):328-334.

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

[13] 王志剛,夏慧明.求解車輛路徑問題的人工蜂群算法[J].計算機工程與科學,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] 鐘石泉,馬壽峰.車輛路徑問題的改進分支切割法[J].系統工程理論與實踐,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

國家自然科學基金（61074147）；廣東省自然科學基金（S2011010005059）；廣東省教育部產學研結合項目（2012B091000171，2011B090400460）；廣東省科技計劃項目（2012B050600028，2014B010118004，2016A050502060）；廣州市花都區科技計劃項目（HD14ZD001）。

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

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