面向車輛路徑問題的改進蟻群算法研究

劉紫玉 趙麗霞 薛建越 陳軍霞 宋偉

摘 要：為解決基礎蟻群算法在求解車輛路徑問題時出現收斂速度慢、易陷入局部最優解等問題，提出了一種改進蟻群算法。首先，引入節約矩陣更新選擇概率公式引導螞蟻搜索;其次，運用分段函數改進揮發因子，調整算法的收斂速度;再次，使用2-opt法，提高算法的局部搜索能力;最后，選取車輛路徑問題國際通用數據集進行仿真，運用控制變量法找到信息素因子和啟發函數因子的合適取值，以P類數據測試算法的改進效果，并與基礎蟻群算法、遺傳算法、模擬退火算法和粒子群算法進行對比。結果表明，相較于基礎蟻群算法，改進蟻群算法的最優路徑總長度平均減少了6.97%;與遺傳算法、模擬退火算法和粒子群算法相比，改進蟻群算法的尋優能力更強、收斂速度更快。因此，改進蟻群算法可以有效減少路徑長度，跳出局部最優，加快收斂速度，尤其是在單路線允許服務點較多且各點分布較離散的車輛路徑情況下，其優勢更為明顯，可為解決車輛路徑問題提供一定的參考。

關鍵詞：交通運輸工程其他學科;基礎蟻群算法;路徑規劃;揮發因子;2-opt法

中圖分類號：F570?? 文獻標識碼：A

DOI：10.7535/hbkd.2022yx01009

收稿日期：2021-05-17;修回日期：2021-12-10;責任編輯：張士瑩

基金項目：河北省社會科學基金（HB20GL011）

第一作者簡介：劉紫玉（1975—），女，河北趙縣人，教授，博士，主要從事物流與供應鏈、數據挖掘方面的研究。

E-mail：purpleyuliu@163.com

Research on vehicle routing problem based on improved ant colony algorithm

LIU Ziyu，ZHAO Lixia，XUE Jianyue，CHEN Junxia，SONG Wei

（School of Economics and Management，Hebei University of Science and Technology ，Shijiazhuang，Hebei 050018，China）

Abstract：In order to solve the problems of slow convergence and easiness to fall into local optimal solution in solving vehicle routing problem，an improved ant colony algorithm was proposed.Firstly，the saving matrix updating selection probability formula was introduced to guide ant search;Secondly，the piecewise function was used to improve the volatilization factor and adjust the convergence speed of the algorithm;Thirdly，the 2-opt method was used to improve the local search ability of the algorithm;Finally，the international general data set of vehicle routing problem was selected for simulation，and the control variable method was used to find the appropriate values of pheromone factor and heuristic function factor.The improvement effect of the algorithm was tested with class P data，and compared with basic ant colony algorithm，genetic algorithm，simulated annealing algorithm and particle swarm optimization algorithm.The results show that compared with the basic ant colony algorithm，the total length of the optimal path of the improved ant colony algorithm is reduced by 6.97%;Compared with genetic algorithm，simulated annealing algorithm and particle swarm optimization algorithm，the improved ant colony algorithm has stronger optimization ability and faster convergence speed.Therefore，the improved ant colony algorithm can effectively reduce the path length，jump out of the local optimization and accelerate the convergence speed.Especially in the case of a single route that allows more service points and discrete distribution of points，its advantages are more obvious，which provides a certain reference for solving the vehicle routing problem.

Keywords：

other disciplines of transportation engineering;basic ant colony algorithm;route planning;volatile factor;2-opt method

車輛路徑問題（vehicle routing problem，VRP）指的是配送中心按照不同配送點的要求，安排車輛有序配送，找到滿足約束的最優車輛調度方案。該問題屬于NP難題。在求解VRP時，研究人員經常會使用精確式算法和元啟發式算法。在求解小規模問題（節點數小于30）時，精確式算法獨具優勢，但當規模數量變大時，采用該算法會導致計算量過大，難以有效解決問題，適用面較窄。相比于精確式算法，元啟發式算法更適合解決大規模問題，搜索更全面，可提高解的優良性，適用面也更廣。蟻群算法具有魯棒性、正反饋、并行性的優點，廣泛用于解決車輛路徑問題[1]，但也會出現陷入局部最優解、收斂速度慢、效果不理想的情況。近年來，人們致力于改進蟻群算法的研究，提高其有效性和適用性，目前主要集中在流程改進和參數設置2個方面。

在流程改進方面，MOHAMED等[2]為解決帶裝載能力約束的車輛路徑問題，提出一種結合局部搜索和蟻群算法的解決方法;KALAYCI等[3]為解決同時取送貨車輛的路徑問題，提出一種基于蟻群算法和可變鄰域搜索的混合算法;ASGHARI等[4]為了找到社交網絡中目標用戶與客戶端之間的可靠路徑，設計了反向蟻群算法，更新后的信息素對螞蟻選擇的路徑具有反向作用;潘穎等[5]將改進蟻群算法應用于解決系統軟硬件劃分問題，引入逆反饋機制提高蟻群算法的搜索性能;JOVANOVIC等[6]提出一種求解區域重定位問題的蟻群優化算法，將基本貪婪算法擴展到蟻群算法，給出定義信息素矩陣，提高了算法性能;BOUAMAMA等[7]將變鄰域搜索作為子例程改進蟻群算法，求解最小連通支配集問題，該方法還可應用于加權和非加權問題變量;田鴿等[8]提出一種改進蟻群算法，對信息素更新方式加以擴大至最優解尋覓范圍，并將啟發因子的函數定義范圍擴展至初始節點，利用2-opt（2-optimization）法進行局部優化;DECERLE等[9]提出一種將模因理論與蟻群算法相結合的混合算法，解決工作時間均衡的家庭醫療保健問題;MARTIN等[10]為解決家庭護理調度問題，提出一種動態鄰域函數改進蟻群算法，提高了搜索能力;張恒等[11]提出一種改進雙層蟻群算法，將蟻群劃分為引導層蟻群和普通層蟻群;李廣明等[12]為實現系統自適應動態推薦，改進了蟻群算法，針對不同搜索狀態變更路徑搜索策略，根據狀態變化動態調整信息啟發函數和期望函數，逐步完善了推薦策略;尹雅楠等[13]在規劃無人機路徑時改進了蟻群算法，對揮發因子以及信息素進行了上下設限。

在參數設置方面，原艷芳等[14]研究了采茶機器人路徑問題，改進了蟻群算法，通過改變自適應調節信息素濃度值和迭代終止條件，提高全局搜索能力和計算效率;李根等[15]為解決室外移動機器人路徑規劃問題，優化了蟻群算法，運用單因素法對蟻群算法中的螞蟻數目、信息素啟發因子、期望啟發因子、信息素揮發因子等參數進行分析研究，尋找到最優參數組合;萬杰等[16]在研究VRP時設計了一種改進的蟻群算法，在啟發因子中加入需求量和時間窗跨度因素;劉冠一等[17]在設計室內服務機器人路徑導航系統時提出了自適應信息素濃度和動態信息素揮發因子，改進后的蟻群算法具有較高的全局搜索能力;劉輝等[18]提出采用改進蟻群算法實現高速列車的行車調度優化。

綜合以上可以看出，在求解VRP改進蟻群算法時，人們只單方面關注流程的改進或是參數設置。由于基礎蟻群算法在一開始搜索時具有盲目性，因而在實際操作中容易出現陷入局部最優解、收斂速度慢的情況。針對該情況，本文引入節約矩陣提高算法的全局搜索能力，運用分段函數改進揮發因子調整收斂速度，運用2-opt法提高算法的局部搜索能力。通過對蟻群算法流程和參數的綜合改進，更好地求解車輛路徑問題。

1 VRP數學模型的構建

VRP可以描述為配送中心按照不同配送點的要求，從配送中心出發，對所有配送點進行配送。每條配送路徑的總載貨量不可以超過車的最大承載能力，以確保每個配送點都能得到服務，一個配送點只能由一輛配送車提供服務。服務完配送路徑最后一個配送點后，配送車要返回配送中心。為了找到滿足約束的最小配送成本配送方案，做以下假設：（1）無缺貨假設;（2）配送貨物包裝規則，無異型包裝，配送貨物按質量計算;（3）配送點需求量不會超過配送車的最大載重量。符號定義如表1所示。

模型構建如下：

min Z=∑mi=0∑mj=0∑nk=1dijxijk ，（1）

∑mi=0∑mj=0∑nk=1qixijk≤qmax ，（2）

∑mj=0xijk=∑mj=0xjik≤1 ，（3）

∑mi=0∑kk=1xijk=1，i∈M，i≠j，k∈K，（4）

∑mj=0∑kk=1xjik=1。（5）

式（1）表示目標函數，目標為總配送距離最短;式（2）表示配送車輛不可以超載;式（3）表示配送車輛出發后需要返回出發點;式（4）和式（5）表示每個配送點只能由一輛配送車配送。

2 改進蟻群算法的構建

2.1 基礎蟻群算法

蟻群算法（ant colony optimization，ACO）是由意大利學者DORIGO等于20世紀90年代首先提出來的[19]。DORIGO等通過觀察螞蟻覓食發現，無論在任何情況下，蟻群最終都可以找到一條距離食物和洞穴最短的路徑。看似簡單的自然現象背后一定蘊含著科學原因。經過認真研究發現，“信息素”起著至關重要的作用。信息素是螞蟻在爬行時分泌的一種特殊物質，正是這種特殊物質讓螞蟻在覓食時可以相互傳遞信息，實現交流。每只螞蟻都會在爬行過的路徑上分泌出“信息素”，信息素會有一定程度的揮發，其他螞蟻在爬行時會感知到信息素的存在，也能分辨出信息素的濃度。螞蟻在爬行時都會偏愛最短路徑，這樣一來螞蟻就會在最短路徑上分泌出信息素，別的螞蟻感知到高濃度信息素的存在，會以更高的概率選擇該路徑，同時也會分泌出信息素。那些不是最短距離的路徑也可能會被螞蟻爬行，同樣也留下信息素。隨著時間的推移，較短路徑上的信息素會越來越多，非較短路徑上的信息素會越來越少。其他螞蟻在覓食時也會選擇最短路徑進行爬行。不斷循環往復后，最短路徑上會有高濃度的信息素，所有的螞蟻都會選擇最短路徑，至此蟻群找到了最短路徑。

蟻群算法步驟如下。

1）初始化參數。

2）迭代次數NC=NC+1。

3）m只螞蟻從起點出發。

4）選擇下一個配送點。根據選擇概率公式（6）和輪盤賭法選擇下一個要到達的點：

pkijt=ταijtηβij∑j∈Nkjταijtηβij， j∈allowed，0， otherwise。（6）

式中：τij（t）為t時刻i，j兩點間的信息素濃度，信息素濃度越高，螞蟻選擇該路徑的概率越大;η為啟發函數，η=1/dij，為i和j兩點距離的倒數，兩點距離越短，螞蟻選擇該路徑的概率越大;allowed表示未訪問點的集合。

5）判斷是否歷遍所有點，沒有歷遍返回步驟4），反之轉到步驟6）。

6）更新信息素。每只螞蟻歷遍所有配送點后需要更新信息素，按τij（t+1）=τij（t）*（1-ρ）+Δτij進行更新，其中Δτij為新增信息素含量，Δτij=∑mk=1Δτkij。這里采用的是蟻周模型，即歷遍后螞蟻才會釋放信息素，即Δτkij=QLk，如果螞蟻k經過路徑i j，0，否則。其中，Lk為螞蟻k所經路徑之和。

7）判斷當前迭代是否達到最大迭代次數，若沒達到返回步驟2），反之轉到步驟8）。

8）輸出結果。

2.2 改進蟻群算法

對于基礎蟻群算法而言，一開始螞蟻的搜索具有盲目性，實際操作中容易出現陷入局部最優解、收斂速度慢等情況。為此引入節約矩陣引導螞蟻搜索，采用改進的揮發因子調整收斂速度，運用2-opt法改善算法效果。

2.2.1 構建路徑

如圖1所示，1點想要給i點和j點運送貨物，原路線是從1點出發分別向i點和j點運送并原路返回，具體路線由實線線段標出。總距離D0=d1i+di1+d1j+dj1，需要2臺車輛完成配送任務。

采用節約矩陣思想優化后，把原路線合并成一個路線，即從1點出發向i點運送，服務完i點后再向j點運送，服務完j點后返回1點，具體路線由虛線線段標出。總距離D1=d1i+dij+dj1，且只需要1臺車輛就可以完成配送任務。這樣一來節約的里程數A=D0-D1=di1+dj1-dij。A越大，表明越應該把i點和j點合并到一條配送路徑上來。在基本蟻群算法運算后期，螞蟻搜索主要依賴信息素，對能見度的依賴變少，可能會出現陷入局部最優解的情況。為了解決該問題，需要引入節約矩陣U，增強先驗信息對螞蟻的吸引力：U（i，j）=D（i，1）+D（j，1）-D（i，j）。引入節約矩陣后，概率公式更新如式（7）所示，其中θ是可以調節節約矩陣的權重系數。

pkijt=ταijtηβijUθij∑j∈NkjταijtηβijUθij， j∈allowed，0， otherwise。（7）

2.2.2 設置揮發因子

揮發因子ρ反映信息素的消失水平，（1-ρ）反映信息素的保留水平，ρ取值范圍為0～1。揮發因子設置過大，信息素揮發較快，每條路徑上的信息素含量差別較大，加大了螞蟻搜索范圍，雖會加快算法的收斂速度，但也增加了陷入局部最優解的可能性;揮發因子設置過小，信息素揮發較慢，每條路徑上的信息素含量差別較小，有利于找到全局最優解，但會使算法的收斂速度減緩。

為了控制算法的收斂速度且避免算法陷入局部最優解，應合理設置揮發因子值，在不同迭代時段設置不同的值。迭代初期，為了能擴大螞蟻的搜索范圍，讓螞蟻歷遍全局找到全局最優解，揮發因子應該定一個比較大的值;迭代一定程度后，為了不讓算法陷入局部最優解，應適當調小揮發因子值，提高算法局部搜索能力，讓螞蟻在當前情況下找到最優解，避免算法急劇收斂而陷入局部最優解;迭代后期，需要提高算法收斂速度，把揮發因子降到最低，讓當前較優路徑中的信息素含量較大，加快收斂速度找到最優解。揮發因子的設置改進如式（8）所示。

ρ=0.8， NC<NCmax3，0.3， NCmax3≤NC<2NCmax3，0.1， NC≥2NCmax3。（8）

2.2.3 運用2-opt法

2-opt就是兩元素優化，亦可稱作2-exchange，核心在于隨機選擇路徑上一個區間段進行優化，這個優化只是對當前一個狀態的優化，并不是對全局的優化，所以是局部搜索算法。蟻群算法在迭代后期，有些路徑上會因為距離短留下大量信息素，引導螞蟻繼續選擇該路徑，容易陷入局部最優解。

2-opt法基本思想如下。首先，通過迭代當前產生一條最短路徑，如圖2 a）中的a-b-c-d-e-f-g-h-a，圖中箭頭只表示方向，與距離無關。然后，隨機選擇2個不同的配送點，反轉這2個配送點在內的中間路線，比如隨機選擇配送點c和配送點f，此時原路徑被分割成3段：（a-b）-（c-d-e-f）-（g-h-a），反轉后，新路徑為（a-b）-（f-e-d-c）-（g-h-a），新路徑如圖2 b）所示。最后，如果新路徑的總距離小于原路徑的總距離，那么最短路徑變為新路徑，此時NC要歸零，繼續迭代;如果新路徑的總距離大于原路徑總距離，那么原路徑還是當前的最短路徑，此時NC=NC+1;如果NC≥NCmax，算法結束，當前的路徑就是最短路徑（局部最優的最短路徑）。運用2-opt法調整配送點的順序增強局部搜索能力，再對局部進行優化，有助于找到全局最優解。

2.2.4 更新信息素

每只螞蟻歷遍所有配送點后需要更新信息素，按τij（t+1）=τij（t）×（1-ρ）+Δτij進行更新，其中Δτij為新增信息素含量，Δτij=∑mk=1Δτkij。這里采用的是蟻周模型，即歷遍后螞蟻才會釋放信息素，即

Δτkij=QLk， 如果螞蟻k經過路徑ij，0， 否則。（9）

式中：Q為信息素常量;Lk為螞蟻k所經路徑之和。

2.2.5 改進流程

改進蟻群算法（improved ant colony optimization，IACO）流程如下。

1）初始化參數;

2）迭代次數NC=NC+1;

3）m只螞蟻從配送中心出發;

4）螞蟻依據概率公式（7）選擇下一個配送點;

5）判斷是否歷遍所有配送點，沒有歷遍返回步驟4），反之轉到步驟6）;

6）求當前路徑費用;

7）運用2-opt法對路徑節點進行調節;

8）更新信息素，揮發因子按式（8）取值;

9）判斷當前迭代是否達到最大迭代次數，沒達到則返回步驟2），反之轉到步驟10）;

10）輸出結果。

改進后的蟻群算法流程圖如圖3所示。

3 參數設置結果及與其他算法的比較

3.1 參數設置結果

蟻群算法參數設置很重要，合適的參數設置能凸顯出蟻群算法的優勢。信息素因子α反映的是先前螞蟻在前期搜索中釋放出來的信息素對未來螞蟻搜索路徑時的指導程度。α設置過大，信息素的指導程度也越大，意味后期螞蟻極容易受先前螞蟻的影響，在搜索中會選擇和先前螞蟻同樣的路徑。這樣一來可能會出現沒有走過的路徑不會被探索的情況，造成隨機搜索能力下降，解空間變小，容易陷入局部最優解。α設置過小，信息素的指導程度也越小，意味著先前螞蟻的貢獻重要程度變小，算法正反饋機制減弱，也容易陷入局部最優解。α的取值范圍一般為[1，5][20]。

啟發函數因子β反映的是啟發函數在螞蟻搜索路徑時的指導程度。在基本蟻群算法中，將β設置為2點距離的倒數。β設置過大，螞蟻在搜索時受到2點距離的影響越大，螞蟻越容易選擇局部最短路徑，局部最短不意味著全局最短，從而會導致算法過早收斂，容易陷入局部最優解。相反，β設置過小，螞蟻在搜索時不容易受啟發函數的影響，出現完全隨機搜索的情況，算法收斂會變慢，不容易找到最優解。β的取值范圍一般為[1，5][20]。

本文采用針對VRP國際通用的數據集進行試驗。該數據集有74個數據，名稱有統一標準，即X-nY-kZ。X代表A，B，P不同類型，A類代表數據中各個配送點分布是半聚集半分散的，B代表聚集型，P代表分散型;Y代表點數（配送中心和配送點總和）;Z為最大車輛使用數。例如：A-n32-k5，代表的是A類型32個點，允許最大使用車輛數為5的數據。數據集特點見表2。

本文只針對P類數據進行討論。隨機選擇P-n22-k8對信息素因子α、啟發函數因子β的取值進行試驗，α和β在[1，5]區間內取整數兩兩組合，共有25種情況，對不同組合都進行10次運算，測試出合適的參數組合，運行結果如表3所示。

在表3可以看出，當α取值保持不變時，β取值越小，螞蟻越不受2點距離的影響，陷入隨機搜索，算法不易收斂;相反，隨著β取值的不斷變大，螞蟻在搜索時幾乎只考慮兩點距離，很容易選擇局部最短路徑，導致算法過早收斂。當β取值保持不變時，α取值越大，螞蟻在搜索時幾乎只考慮先前螞蟻留下的信息素，使得隨機搜索能力下降，容易陷入局部最優解，運行出來的結果越來越差;相反，隨著α取值的不斷變小，前期螞蟻做出的貢獻重要程度也變小，不利于找到全局最優解。

由表3還可以看出，序號為17時算法效果較好。雖然平均迭代次數不是最小值，但迭代次數居中，最優路徑距離總長度和最差路徑距離總長度的和均為最短。因此，將α設置為4，β設置為2。調試參數組合的最優情況路徑圖如圖4所示。

從圖4 P-n22-k8最優路徑圖可以看出，物流中心服務的客戶距離都較近，車輛路徑鮮少出現交叉與迂回等現象，因此改進蟻群算法給車輛路徑規劃提供了更大的組合優化空間，能有效避免出現交叉配送與迂回運輸不合理等現象，縮短車輛行駛距離，減少車輛使用數量，降低物流成本。

3.2 與基礎蟻群算法的比較

選擇P類數據，運用基礎蟻群算法和改進蟻群算法分別進行計算，基礎蟻群算法中ρ=0.2[21]，改進蟻群算法中θ=2。其他參數設置如下：m=節點數×1.5[22]，Q=1 000，NCmax=200。使用MATLAB R2018a軟件進行仿真，小規模問題、中規模問題和大規模問題的迭代曲線如圖5—圖7所示，不同案例最優路徑總長度和比較如表4所示。

由圖5—圖7可以看出，在小規模問題下，基礎蟻群算法和改進蟻群算法都在迭代初期找到最優解，但改進蟻群算法在搜索初期路徑長度就小于基礎蟻群算法，且收斂速度更快，更早跳出局部最優解;在中規模問題下，迭代初期改進算法的初始解優于基礎蟻群算法，2種算法在迭代中期收斂，但改進蟻群算法更早跳出局部最優解，且收斂速度也要快于基礎蟻群算法;在大規模問題下，2種算法在迭代初期相差較大，明顯體現出改進算法的優勢，且改進算法能夠不斷跳出局部最優，尋找更優解，2種算法雖都在迭代中后期收斂，但改進蟻群算法稍快于基礎蟻群算法，尋優能力更強。

由表4可以看出，所有案例使用改進蟻群算法后都有不同程度的改善。與基礎蟻群算法相比，改進蟻群算法平均距離減少了6.97%，大部分案例都減少6%以上，最多減少了22%。提升較少的案例原因有2點：一是因為單路線允許服務配送點較少（如案例1、案例6）;二是各點分布較密集（如案例20，各點分布如圖8所示），可優化的空間較小，所以改進蟻群算法的優勢體現不出來。由此可以得出，本文提出的算法較適合于單路線允許服務點較多且各點分布較離散的VRP（如案例5，分布如圖9所示）。

總體來看，改進蟻群算法明顯優于基礎蟻群算法。結合迭代圖可以看出，改進后的蟻群算法仿真結果均優于基本蟻群算法，且在迭代初期改進蟻群算法的尋優能力就強于基礎蟻群算法;此外，改進蟻群算法的收斂速度也快于基本蟻群算法。

3.3 與其他算法的比較

選擇P類數據，運用基礎蟻群算法和改進蟻群算法分別進行計算，基礎蟻群算法中ρ=0.2[21]，改進蟻群算法中θ=2。其他參數設置如下：m=節點數×1.5[22]，Q=1 000，NCmax=200。使用MATLAB R2018a軟件，運用遺傳算法、模擬退火算法和粒子群算法分別進行仿真比較，結果如表5所示。

由表5可以看出，與遺傳算法相比，改進蟻群算法共有17個案例最優路徑總長度和減少。剩余案例中只有案例22、案例23遺傳算法結果明顯優于改進蟻群算法，其余相差不多。與模擬退火算法相比，共有15個案例最優路徑總長度和減少，比較而言，改進蟻群算法對于小規模問題的改善程度較低。與粒子群算法相比，改進蟻群算法的仿真結果絕大部分都有改善，只有大規模問題提升效果不佳，共有18個案例的總路徑長度減少。以案例6為例，不同算法的迭代圖如圖10所示。

由圖10可以看出，在迭代初期幾種方法相差較大，初始解明顯體現出了改進算法的優勢，且改進算法能夠跳出局部最優尋找更優解;從解的質量來看，不論是初始解還是最優解，改進蟻群算法的尋優能力更強;從收斂速度來看，改進蟻群算法與粒子群算法都比較快，遺傳算法較慢，模擬退火算法居中，但綜合解的質量來說，還是改進蟻群算法的效果更好。因此，與其他算法相比，改進蟻群算法的尋優能力更強，收斂速度更快，最優路徑距離總長度最短。

4 結 語

1）本文綜合算法流程和參數設置對蟻群算法進行了改進：引入節約矩陣更新選擇概率公式，提高了算法的全局搜索能力;運用分段函數改進揮發因子，合理加快了算法的收斂速度;引入2-opt法，提高了算法的局部搜索能力。

2）與基礎蟻群算法、遺傳算法、模擬退火算法和粒子群算法的仿真結果表明，不論小規模、中規模還是大規模問題，改進后的蟻群算法仿真結果均優于基本蟻群算法，尤其是在解決單路線允許服務點較多且各點分布較離散的VRP時，改進蟻群算法的優勢更加凸顯。

3）改進后的蟻群算法迭代初期解就優于基礎蟻群算法，且改進蟻群算法的收斂速度快于基礎蟻群算法，最優路徑總長度的和也小于基礎蟻群算法。

4）與遺傳算法、模擬退火算法和粒子群算法相比，改進蟻群算法最優路徑總長度的和絕大部分都有改善，迭代圖也表明改進蟻群算法比其他3種算法的尋優能力更強，收斂速度更快。

改進蟻群算法不論在尋優能力方面還是在收斂速度方面都明顯優于基本蟻群算法、遺傳算法、模擬退火算法和粒子群算法，為解決VRP提供了新思路。本文提出的算法針對VRP雖有普遍適用性，但是細分VRP有很多類型，比如動態VRP、同時取送貨VRP等。為了提高算法的適用性，本文并沒有對每一種類型的VRP進行針對性的改進，未來可就此進行深入探討，還可以進一步改進蟻群算法，使其應用于更多領域。

參考文獻/References：

[1] 龐燕，羅華麗，邢立寧，等.車輛路徑優化問題及求解方法研究綜述[J].控制理論與應用，2019，36（10）：1573-1584.

PANG Yan，LUO Huali，XING Lining，et al.A survey of vehicle routing optimization problems and solution methods[J].Control Theory & Applications，2019，36（10）：1573-1584.

[2] MOHAMED M M S，GAJPALB Y，ELMEKKAWYC T Y，et al.Hybridized ant colony algorithm for the multi compartment vehicle routing problem[J].Applied Soft Computing，2015，37：196-203.

[3] KALAYCI C B，KAYA C.An ant colony system empowered variable neighborhood search algorithm for the vehicle routing problem with simultaneous pickup and delivery[J].Expert Systems with Applications，2016，66：163-175.

[4] ASGHARI S，AZADI K.A reliable path between target users and clients in social networks using an inverted ant colony optimization algorithm[J].Karbala International Journal of Modern Science，2017，3（3）：143-152.

[5] 潘穎，阮文惠.基于改進蟻群算法的嵌入式系統軟硬件劃分[J].現代電子技術，2017，40（3）：164-166.

PAN Ying，RUAN Wenhui.Embedded system hardware and software partition based on improved ant colony algorithm[J].Modern Electronics Technique，2017，40（3）：164-166.

[6] JOVANOVIC R，TUBA M，VO S.An efficient ant colony optimization algorithm for the blocks relocation problem[J].European Journal of Operational Research，2019，274（1）：78-90.

[7] BOUAMAMA S，BLUM C，FAGES J G.An algorithm based on ant colony optimization for the minimum connected dominating set problem[J].Applied Soft Computing，2019，80：672-686.

[8] 田鴿，薛冬娟，梁斌，等.基于改進蟻群算法的冰鮮水產品配送路徑優化方法研究[J].大連海洋大學學報，2019，34（5）：746-751.

TIAN Ge，XUE Dongjuan，LIANG Bin，et al.Distribution route and its optimization of chilled fishery products[J].Journal of Dalian Fisheries University，2019，34（5）：746-751.

[9] DECERLE J，GRUNDER O，HASSANI A H E，et al.A hybrid memetic-ant colony optimization algorithm for the home health care problem with time window，synchronization and working time balancing[J].Swarm and Evolutionary Computation，2019，46：171-183.

[10]MARTIN E，CERVANTES A，SAEZ Y，et al.IACS-HCSP：Improved ant colony optimization for large-scale home care scheduling problems[J].Expert Systems with Applications，2020，142.DOI.10.1016/j.eswa.2019.112994.

[11]張恒，何麗，袁亮，等.基于改進雙層蟻群算法的移動機器人路徑規劃[J/OL].控制與決策.[2021-01-05].https：//kns.cnki.net/kcms/detail/detail.aspx？FileName=KZYC20210104002&DbName=CAPJ2021.

ZHANG Heng，HE Li，YUAN Liang，et al.Mobile robot path planning using improved double-layer ant colony algorithm[J/OL].Control and Decision.[2021-01-05].https：//kns.cnki.net/kcms/detail/detail.aspx？FileName=KZYC20210104002&DbName=CAPJ2021.

[12]李廣明，付劍鋒.基于用戶搜索狀態的動態推薦模型研究[J].情報理論與實踐，2021，44（7）：166-172.

LI Guangming，FU Jianfeng.Research on dynamic recommendation model based on user search state[J].Information Studies Theory & Application，2021，44（7）：166-172.

[13]尹雅楠，甄然，武曉晶，等.自適應多啟發蟻群算法的無人機路徑規劃[J].河北科技大學學報，2021，42（1）：38-47.

YIN Yanan，ZHEN Ran，WU Xiaojing，et al.Research on UAV route planning based on adaptive multi heuristic ant colony algorithm[J].Journal of Hebei University of Science and Technology，2021，42（1）：38-47.

[14]原艷芳，鄭相周，林衛國.名優茶采摘機器人路徑規劃[J].安徽農業大學學報，2017，44（3）：530-535.

YUAN Yanfang，ZHENG Xiangzhou，LIN Weiguo.Path planning of picking robot for famous tea[J].Journal of Anhui Agricultural University，2017，44（3）：530-535.

[15]李根，李航，張帥陽，等.基于蟻群算法的最優路徑規劃及參數研究[J].中國科技論文，2018，13（16）：1909-1914.

LI Gen，LI Hang，ZHANG Shuaiyang，et al.Optimal path planning and parameter analysis based on ant colony algorithm[J].China Science Paper，2018，13（16）：1909-1914.

[16]萬杰，耿麗，田喆.基于改進的蟻群算法求解多目標生鮮農產品車輛路徑[J].山東農業大學學報（自然科學版），2019，50（6）：1080-1086.

WAN Jie，GENG Li，TIAN Zhe.Solution for the vehicle route of multi-objective fresh agricultural products based on the improved ant colony algorithm[J].Journal of Shandong Agricultural University（Natural Science Edition），2019，50（6）：1080-1086.

[17]劉冠一，竇水海，杜艷平，等.室內服務機器人路徑導航系統設計及算法[J].科學技術與工程，2020，20（34）：14114-14119.

LIU Guanyi，DOU Shuihai，DU Yanping，et al.Algorithm and design of path navigation system of indoor service mobile robot[J].Science Technology and Engineering，2020，20（34）：14114-14119.

[18]劉輝，代學武，崔東亮，等.基于參數自適應蟻群算法的高速列車行車調度優化[J].控制與決策，2021，36（7）：1581-1591.

LIU Hui，DAI Xuewu，CUI Dongliang，et al.Optimization of high-speed train operation scheduling based on parameter adaptive improved ant colony algorithm[J].Control and Decision，2021，36（7）：1581-1591.

[19]DORIGO M.Optimization，Learning and Natural Algorithms[D].Milan：Politecnicodi Milano，1992.

[20]史恩秀，陳敏敏，李俊，等.基于蟻群算法的移動機器人全局路徑規劃方法研究[J].農業機械學報，2014，45（6）：53-57.

SHI Enxiu，CHEN Minmin，LI Jun，et al.Research on method of global path-planning for mobile robot based on ant-colony algorithm[J].Transactions of the Chinese Society for Agricultural Machinery，2014，45（6）：53-57.

[21]杜玉紅，張巖，趙煥峰.基于參數優化蟻群算法的機器人路徑規劃研究[J].現代制造工程，2020（9）：7-14.

DU Yuhong，ZHANG Yan，ZHAO Huanfeng.Research on robot path planning based on parameters optimized ant colony optimization[J].Modern Manufacturing Engineering，2020（9）：7-14.

[22]張松燦，普杰信，司彥娜，等.基于種群相似度的自適應改進蟻群算法及應用[J].計算機工程與應用，2021，57（8）：70-77.

ZHANG Songcan，PU Jiexin，SI Yanna，et al.Adaptive improved ant colony algorithm based on population similarity and its application[J].Computer Engineering and Applications，2021，57（8）：70-77.

3493500338284