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

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

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

關(guān)鍵詞：交通運輸工程其他學(xué)科;基礎(chǔ)蟻群算法;路徑規(guī)劃;揮發(fā)因子;2-opt法

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

DOI：10.7535/hbkd.2022yx01009

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

基金項目：河北省社會科學(xué)基金（HB20GL011）

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

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

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

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

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

1 VRP數(shù)學(xué)模型的構(gòu)建

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

模型構(gòu)建如下：

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）表示目標函數(shù)，目標為總配送距離最短;式（2）表示配送車輛不可以超載;式（3）表示配送車輛出發(fā)后需要返回出發(fā)點;式（4）和式（5）表示每個配送點只能由一輛配送車配送。

2 改進蟻群算法的構(gòu)建

2.1 基礎(chǔ)蟻群算法

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

蟻群算法步驟如下。

1）初始化參數(shù)。

2）迭代次數(shù)NC=NC+1。

3）m只螞蟻從起點出發(fā)。

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

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

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

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

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

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

8）輸出結(jié)果。

2.2 改進蟻群算法

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

2.2.1 構(gòu)建路徑

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

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

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

2.2.2 設(shè)置揮發(fā)因子

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

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

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

2.2.3 運用2-opt法

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

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

2.2.4 更新信息素

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

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

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

2.2.5 改進流程

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

1）初始化參數(shù);

2）迭代次數(shù)NC=NC+1;

3）m只螞蟻從配送中心出發(fā);

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

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

6）求當前路徑費用;

7）運用2-opt法對路徑節(jié)點進行調(diào)節(jié);

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

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

10）輸出結(jié)果。

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

3 參數(shù)設(shè)置結(jié)果及與其他算法的比較

3.1 參數(shù)設(shè)置結(jié)果

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

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

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

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

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

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

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

3.2 與基礎(chǔ)蟻群算法的比較

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

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

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

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

3.3 與其他算法的比較

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

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

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

4 結(jié) 語

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

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

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

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

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

參考文獻/References：

[1] 龐燕，羅華麗，邢立寧，等.車輛路徑優(yōu)化問題及求解方法研究綜述[J].控制理論與應(yīng)用，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] 潘穎，阮文惠.基于改進蟻群算法的嵌入式系統(tǒng)軟硬件劃分[J].現(xiàn)代電子技術(shù)，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，F(xiàn)AGES 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] 田鴿，薛冬娟，梁斌，等.基于改進蟻群算法的冰鮮水產(chǎn)品配送路徑優(yōu)化方法研究[J].大連海洋大學(xué)學(xué)報，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]張恒，何麗，袁亮，等.基于改進雙層蟻群算法的移動機器人路徑規(guī)劃[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]李廣明，付劍鋒.基于用戶搜索狀態(tài)的動態(tài)推薦模型研究[J].情報理論與實踐，2021，44（7）：166-172.

LI Guangming，F(xiàn)U Jianfeng.Research on dynamic recommendation model based on user search state[J].Information Studies Theory & Application，2021，44（7）：166-172.

[13]尹雅楠，甄然，武曉晶，等.自適應(yīng)多啟發(fā)蟻群算法的無人機路徑規(guī)劃[J].河北科技大學(xué)學(xué)報，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]原艷芳，鄭相周，林衛(wèi)國.名優(yōu)茶采摘機器人路徑規(guī)劃[J].安徽農(nóng)業(yè)大學(xué)學(xué)報，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]李根，李航，張帥陽，等.基于蟻群算法的最優(yōu)路徑規(guī)劃及參數(shù)研究[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]萬杰，耿麗，田喆.基于改進的蟻群算法求解多目標生鮮農(nóng)產(chǎn)品車輛路徑[J].山東農(nóng)業(yè)大學(xué)學(xué)報（自然科學(xué)版），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]劉冠一，竇水海，杜艷平，等.室內(nèi)服務(wù)機器人路徑導(dǎo)航系統(tǒng)設(shè)計及算法[J].科學(xué)技術(shù)與工程，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]劉輝，代學(xué)武，崔東亮，等.基于參數(shù)自適應(yīng)蟻群算法的高速列車行車調(diào)度優(yōu)化[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]史恩秀，陳敏敏，李俊，等.基于蟻群算法的移動機器人全局路徑規(guī)劃方法研究[J].農(nóng)業(yè)機械學(xué)報，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]杜玉紅，張巖，趙煥峰.基于參數(shù)優(yōu)化蟻群算法的機器人路徑規(guī)劃研究[J].現(xiàn)代制造工程，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]張松燦，普杰信，司彥娜，等.基于種群相似度的自適應(yīng)改進蟻群算法及應(yīng)用[J].計算機工程與應(yīng)用，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