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

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

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

中圖分類(lèi)號(hào)：F570?? 文獻(xiàn)標(biāo)識(shí)碼：A

DOI：10.7535/hbkd.2022yx01009

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

基金項(xiàng)目：河北省社會(huì)科學(xué)基金（HB20GL011）

第一作者簡(jiǎn)介：劉紫玉（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

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

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

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

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

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

VRP可以描述為配送中心按照不同配送點(diǎn)的要求，從配送中心出發(fā)，對(duì)所有配送點(diǎn)進(jìn)行配送。每條配送路徑的總載貨量不可以超過(guò)車(chē)的最大承載能力，以確保每個(gè)配送點(diǎn)都能得到服務(wù)，一個(gè)配送點(diǎn)只能由一輛配送車(chē)提供服務(wù)。服務(wù)完配送路徑最后一個(gè)配送點(diǎn)后，配送車(chē)要返回配送中心。為了找到滿足約束的最小配送成本配送方案，做以下假設(shè)：（1）無(wú)缺貨假設(shè);（2）配送貨物包裝規(guī)則，無(wú)異型包裝，配送貨物按質(zhì)量計(jì)算;（3）配送點(diǎn)需求量不會(huì)超過(guò)配送車(chē)的最大載重量。符號(hào)定義如表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）表示目標(biāo)函數(shù)，目標(biāo)為總配送距離最短;式（2）表示配送車(chē)輛不可以超載;式（3）表示配送車(chē)輛出發(fā)后需要返回出發(fā)點(diǎn);式（4）和式（5）表示每個(gè)配送點(diǎn)只能由一輛配送車(chē)配送。

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

2.1 基礎(chǔ)蟻群算法

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

蟻群算法步驟如下。

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

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

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

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

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

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

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

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

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

8）輸出結(jié)果。

2.2 改進(jìn)蟻群算法

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

2.2.1 構(gòu)建路徑

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

采用節(jié)約矩陣思想優(yōu)化后，把原路線合并成一個(gè)路線，即從1點(diǎn)出發(fā)向i點(diǎn)運(yùn)送，服務(wù)完i點(diǎn)后再向j點(diǎn)運(yùn)送，服務(wù)完j點(diǎn)后返回1點(diǎn)，具體路線由虛線線段標(biāo)出?？偩嚯xD1=d1i+dij+dj1，且只需要1臺(tái)車(chē)輛就可以完成配送任務(wù)。這樣一來(lái)節(jié)約的里程數(shù)A=D0-D1=di1+dj1-dij。A越大，表明越應(yīng)該把i點(diǎn)和j點(diǎn)合并到一條配送路徑上來(lái)。在基本蟻群算法運(yùn)算后期，螞蟻搜索主要依賴(lài)信息素，對(duì)能見(jiàn)度的依賴(lài)變少，可能會(huì)出現(xiàn)陷入局部最優(yōu)解的情況。為了解決該問(wèn)題，需要引入節(jié)約矩陣U，增強(qiáng)先驗(yàn)信息對(duì)螞蟻的吸引力：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è)置過(guò)大，信息素?fù)]發(fā)較快，每條路徑上的信息素含量差別較大，加大了螞蟻搜索范圍，雖會(huì)加快算法的收斂速度，但也增加了陷入局部最優(yōu)解的可能性;揮發(fā)因子設(shè)置過(guò)小，信息素?fù)]發(fā)較慢，每條路徑上的信息素含量差別較小，有利于找到全局最優(yōu)解，但會(huì)使算法的收斂速度減緩。

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

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

2.2.3 運(yùn)用2-opt法

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

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

2.2.4 更新信息素

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

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

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

2.2.5 改進(jìn)流程

改進(jìn)蟻群算法（improved ant colony optimization，IACO）流程如下。

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

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

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

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

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

6）求當(dāng)前路徑費(fèi)用;

7）運(yùn)用2-opt法對(duì)路徑節(jié)點(diǎn)進(jìn)行調(diào)節(jié);

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

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

10）輸出結(jié)果。

改進(jìn)后的蟻群算法流程圖如圖3所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 與其他算法的比較

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

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

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

4 結(jié) 語(yǔ)

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

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

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

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

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

參考文獻(xiàn)/References：

[1] 龐燕，羅華麗，邢立寧，等.車(chē)輛路徑優(yōu)化問(wèn)題及求解方法研究綜述[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] 潘穎，阮文惠.基于改進(jìn)蟻群算法的嵌入式系統(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] 田鴿，薛冬娟，梁斌，等.基于改進(jìn)蟻群算法的冰鮮水產(chǎn)品配送路徑優(yōu)化方法研究[J].大連海洋大學(xué)學(xué)報(bào)，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ìn)雙層蟻群算法的移動(dòng)機(jī)器人路徑規(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]李廣明，付劍鋒.基于用戶(hù)搜索狀態(tài)的動(dòng)態(tài)推薦模型研究[J].情報(bào)理論與實(shí)踐，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ā)蟻群算法的無(wú)人機(jī)路徑規(guī)劃[J].河北科技大學(xué)學(xué)報(bào)，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)國(guó).名優(yōu)茶采摘機(jī)器人路徑規(guī)劃[J].安徽農(nóng)業(yè)大學(xué)學(xué)報(bào)，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áng)，等.基于蟻群算法的最優(yōu)路徑規(guī)劃及參數(shù)研究[J].中國(guó)科技論文，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]萬(wàn)杰，耿麗，田喆.基于改進(jìn)的蟻群算法求解多目標(biāo)生鮮農(nóng)產(chǎn)品車(chē)輛路徑[J].山東農(nóng)業(yè)大學(xué)學(xué)報(bào)（自然科學(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ù)機(jī)器人路徑導(dǎo)航系統(tǒng)設(shè)計(jì)及算法[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)蟻群算法的高速列車(chē)行車(chē)調(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]史恩秀，陳敏敏，李俊，等.基于蟻群算法的移動(dòng)機(jī)器人全局路徑規(guī)劃方法研究[J].農(nóng)業(yè)機(jī)械學(xué)報(bào)，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)化蟻群算法的機(jī)器人路徑規(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)改進(jìn)蟻群算法及應(yīng)用[J].計(jì)算機(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