雷金羨，孫 宇，朱洪杰

(廣西大學(xué) 計算機(jī)與電子信息學(xué)院，廣西 南寧 530004)

0 引言

車輛路徑規(guī)劃問題(Vehicle Routing Problems,VRP)自1959年被提出后，引起了國內(nèi)外研究者們的關(guān)注，隨著經(jīng)濟(jì)和電子商務(wù)的快速發(fā)展，該問題已成為眾多學(xué)者研究的熱門問題之一[1]。VRP配送中心在滿足客戶需求和約束的限制下進(jìn)行路徑規(guī)劃，目的是找到成本最低的路線。經(jīng)過多年的研究，VRP已經(jīng)拓展出許多更具實際意義的研究問題[2]，帶時間窗的車輛路徑問題(VRP with Time Window, VRPTW)是其中之一。VRPTW在基本VPR問題上對客戶接收貨物的時間段進(jìn)行了約束，客戶只在某一段固定時間接受送達(dá)的貨物，超過這個時間段則拒絕接受貨物，在此約束下找到一條最優(yōu)路徑[3]。解決這一問題的方法一般分為精確式算法和啟發(fā)式算法兩大類。

精確式算法是一類能夠求出最優(yōu)解的算法，一般用于解決復(fù)雜度較低的組合優(yōu)化問題，常用的算法有線性規(guī)劃法、貪婪算法、動態(tài)規(guī)劃算法等[4]。然而，隨著問題研究的不斷深入，VRP也變得更加復(fù)雜，數(shù)據(jù)量更大，精確算法對于這類較為復(fù)雜的組合優(yōu)化問題的計算時間將呈指數(shù)增長[5]。因此，為了能夠在可接受時間內(nèi)得到可行解，通常采用啟發(fā)式算法。啟發(fā)式算法可以在一定的時間和范圍內(nèi)求解得到精度較高的近似解[6]，常用于解決VRP的啟發(fā)式算法包括：遺傳算法[7]、禁忌搜索算法[8]、模擬退火算法[9]、蟻群算法[10]、粒子群算法[11]等。

蟻群算法(Ant Colony Optimization,ACO)是一種通過模擬自然界螞蟻覓食行為來優(yōu)化實際問題的智能優(yōu)化算法，最早由意大利學(xué)者DORIGO等[12]在上個世紀(jì)九十年代提出。蟻群算法尋優(yōu)的基本思想是：以巢穴為出發(fā)點，食物源為目的地，螞蟻開始搜索行為時會沿路釋放一種蟻群之間能夠相互識別的化學(xué)物質(zhì)即信息素(pheromone)。一開始搜索時螞蟻的行為沒有信息素的指導(dǎo)，各個螞蟻隨機(jī)選擇路徑，同時沿路釋放信息素。隨著時間的推移，螞蟻們各自找到了食物，并在路徑上留下信息素。由此多次往返后，在單位時間內(nèi)，短路徑上留下的信息素濃度更高。而螞蟻會趨向于選擇走高濃度的路徑，在后續(xù)搜索中越來越多螞蟻選擇短路徑，最后得到一個最短路徑的解[13]。由算法思路可知，由于蟻群算法不需要初始解，在不同的環(huán)境下能夠自動地調(diào)整尋優(yōu)路線，體現(xiàn)了其具有正反饋機(jī)制、與其他算法結(jié)合的適應(yīng)性強(qiáng)、魯棒性強(qiáng)、自適應(yīng)能力強(qiáng)的特點[14]。

但是傳統(tǒng)蟻群算法因為過于依賴信息素的引導(dǎo)，所以存在容易陷入局部最優(yōu)，收斂速度慢、參數(shù)難以精確設(shè)置等缺點。針對這一缺陷，ZHANG等[15]改進(jìn)了蟻群算法中的狀態(tài)轉(zhuǎn)移概率計算方法，降低信息素對螞蟻選擇路徑的影響，將局部搜索能力較強(qiáng)的2-optimization(2-opt)算法加入到現(xiàn)有解的優(yōu)化中，彌補(bǔ)了蟻群算法在局部尋優(yōu)方面的不足；LU等[16]使用最大最小策略更新信息素，目標(biāo)是實現(xiàn)最小—最大或勞動平衡的目標(biāo)，通過面向任務(wù)的方法將螞蟻分配到團(tuán)隊中，最終達(dá)到優(yōu)化算法的目的；YAO等[17]也針對容易陷入局部最優(yōu)的問題提出改進(jìn)的蟻群算法(Improved Ant Colony Optimization,IACO)算法，加入了一種掃描策略，并使用交叉操作來擴(kuò)大算法的搜索空間；方文婷[18]等針對蟻群算法在前期的搜索階段，因信息素不足而導(dǎo)致收斂速度慢的問題，結(jié)合A*算法的全局收斂性對蟻群算法進(jìn)行改進(jìn)，提出一種混合算法，并證明了其有效性；何美玲等[19]在傳統(tǒng)蟻群算法中加入變鄰域搜索算法來加強(qiáng)局部搜索的能力，并設(shè)置了進(jìn)入局部搜索階段的條件，當(dāng)連續(xù)兩次迭代結(jié)果相同且信息素?fù)]發(fā)系數(shù)在設(shè)定的范圍內(nèi)時，就進(jìn)入局部搜索階段等。因此，本文針對其容易陷入局部最優(yōu)的缺點，在信息素更新方式上借鑒最大最小蟻群(MAX-MIN Ant System, MMAS)方法[20]進(jìn)行了改進(jìn)，同時在迭代過程中動態(tài)調(diào)整信息素?fù)]發(fā)因子的大小，并加入2-opt(2-optimization)算法、順序交換策略、順序插入策略優(yōu)化其每次迭代得到的最優(yōu)路徑。將改進(jìn)算法應(yīng)用在VRPTW上，并通過實驗證明了改進(jìn)算法的有效性。

1 VRPTW數(shù)學(xué)模型

VRPTW是VRP的一個拓展，在VRP的基礎(chǔ)上增加了一個最主要的時間窗約束，使問題的研究更具現(xiàn)實意義。

1.1 問題描述

配送中心通過配送車輛完成向客戶配送貨物的任務(wù)，已知客戶點的位置、客戶接受服務(wù)的時間區(qū)間、服務(wù)時長、車輛容量、客戶的貨物重量等信息，車輛在進(jìn)行貨物配送時，有以下約束[21]：

(1)車輛只能在客戶接受的時間區(qū)間內(nèi)對客戶進(jìn)行配送服務(wù)，否則客戶會拒絕接受服務(wù)；

(2)每個客戶只能被走訪一次；

(3)車輛的載重不能超過車輛容量；

(4)車輛只能從配送中心出發(fā)，最后返回配送中心。

本問題的目標(biāo)是在滿足上述約束的情況下，找到一條成本最低的路線[22]。

1.2 建立模型

根據(jù)以上問題描述建立的相應(yīng)的VRPTW模型中[23]，可將配送中心和客戶點視為一個無向圖G(V,A)，其中頂點集V={v0，v1，v2,…,vN}表示1個配送中心和N個客戶點的集合，其中v0表示配送中心，{v1，v2,…,vN}表示N個客戶點，配送中心要為N個客戶點進(jìn)行配送服務(wù)；邊集A={(vi，vj)|vi，vj∈V,i≠j}表示每個點之間都存在可行路徑；K表示車輛集合；dij表示車輛從i點到j(luò)點花費(fèi)的距離；tij表示車輛從i點到j(luò)點已花費(fèi)的時間；ci表示客戶點i的貨物重量，即服務(wù)量。

目標(biāo)函數(shù)：

(1)

約束條件：

xijk∈{0,1}，

(2)

ai+si+tij>bi，

(3)

(4)

(5)

式(2)中的xijk表示車輛k是否經(jīng)過點i和點j之間的路徑，若經(jīng)過，則xijk=1，否則xijk=0。由此，式(1)中用xijk的取值來判斷車輛是否經(jīng)過i和點j之間的路徑，將車輛k經(jīng)過的所有客戶點進(jìn)行累加，然后從K輛車的路線中取距離最短的路線作為目標(biāo)函數(shù)值z。客戶i接受服務(wù)的時間區(qū)間為[ai,bi]，si表示在客戶點i的服務(wù)時間，則式(3)保證車輛服務(wù)客戶點的時間必須在客戶指定的時間內(nèi)進(jìn)行；式(4)表示每個客戶點只能進(jìn)行一次服務(wù)；式(5)表示每輛車的載重不能超過車本身的容量。

2 蟻群算法

自蟻群算法提出后，許多學(xué)者將蟻群算法改進(jìn)后應(yīng)用于更多的組合優(yōu)化問題中，且都在不同程度上展現(xiàn)出了較為良好的成果[24]。

(6)

其中ηij(t)為根據(jù)自身自適應(yīng)定義的啟發(fā)函數(shù)，

(7)

城市i與j之間的距離用dij來表示，dij和ηij(t)成反比關(guān)系，dij越小，ηij(t)越大，則狀態(tài)轉(zhuǎn)移概率p也越大，由此ηij(t)代表螞蟻由城市i轉(zhuǎn)移到下一個城市j的期望量值。

所有螞蟻在一次迭代中完成走訪全部城市的任務(wù)后，為避免信息素積累過多導(dǎo)致覆蓋了還未探索的路徑啟發(fā)信息，需對信息素進(jìn)行及時的更新處理。

τij(t+1)=(1-ρ)·τij(t)+Δτij。

(8)

其中ρ表示信息素?fù)]發(fā)系數(shù)，會直接影響到整個蟻群算法的全局搜索能力和收斂速度，(1-ρ)則是信息素的殘留因子，體現(xiàn)了螞蟻個體之間相互影響的強(qiáng)弱程度，ρ的取值范圍：{ρ|0<ρ<1}，初始τij(0)=0。Δτij為本次迭代中的信息素增量，可表示為：

(9)

式中：Q是一個常量，表示螞蟻本身攜帶的信息素的固定值；Lk代表本次迭代螞蟻k走過的路徑。

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

本文對蟻群算法的改進(jìn)主要在3個方面：①改進(jìn)更新信息素的方式;②對信息素?fù)]發(fā)因子ρ進(jìn)行階梯式調(diào)整;③加入了2-opt算法、順序插入策略、順序交換策略進(jìn)行改進(jìn)。

3.1 改進(jìn)信息素更新方式

在信息素更新方式上作了3個方面的調(diào)整：

(1)在每次迭代結(jié)束更新信息素時只更新最優(yōu)路徑的信息素；

(2)在更新信息素時增加一個獎勵值；

(3)對信息素的值設(shè)置動態(tài)的限制區(qū)間。

下面對以上3個方面的調(diào)整進(jìn)行詳細(xì)說明。

3.1.1 更新最優(yōu)路徑的信息素

由信息素增量式(8)可知，基本蟻群算法更新信息素時在每只螞蟻走過的路徑上都增加了信息素，這樣的更新方式使得信息素的累積較快，迭代一段時間后會導(dǎo)致最優(yōu)路徑和其他路徑的信息素形成一個較大的差值，螞蟻們在后續(xù)迭代中更傾向于選擇這條最優(yōu)路徑，從而喪失了尋找其他更優(yōu)路徑的能力，最終使整個算法陷入局部最優(yōu)。針對該問題，本次改進(jìn)將在每次迭代結(jié)束之后只更新最優(yōu)路徑bestroute上的信息素值，并加上一個獎勵值award，信息素更新方式為:

(10)

式中，bestroute已經(jīng)更新為本次迭代中的最優(yōu)路線，只更新最優(yōu)路徑上的信息素值能夠相應(yīng)地降低路徑上積累信息素的速度，使信息素在早期的時候的引導(dǎo)作用較小，從而提高全局搜索能力。

3.1.2 增加獎勵值

在更新信息素增加一個獎勵值award，目的是加強(qiáng)信息素的引導(dǎo)，保證算法早期的搜索質(zhì)量，award具體計算方法為：

(11)

式中bestroute是還未更新的最優(yōu)路線長度，而nowbestroute是當(dāng)前迭代得到的更好的最優(yōu)路線長度，則nowbestroute的值越小，award值也越大，通過award值達(dá)到了獎勵最優(yōu)解目的。award值獎勵了找最優(yōu)路徑的螞蟻，在削弱信息素早期引導(dǎo)能力的同時，也通過獎勵機(jī)制保證了螞蟻在前期搜索的質(zhì)量，對后期的搜索起到一個指導(dǎo)作用。

3.1.3 設(shè)置信息素的限制區(qū)間

(12)

(13)

3.2 改進(jìn)信息素?fù)]發(fā)因子

信息素?fù)]發(fā)因子ρ決定著信息素存留在路徑上的持久程度，若ρ過小，信息素存留在路徑上的時間長，雖然具有較強(qiáng)的引導(dǎo)能力，但是隨著時間的累積，很有可能限制整體的全局搜索能力，陷入到局部最優(yōu)的情況中；若ρ過大，路徑上存留的信息素較少，雖然可能在早期能夠提高全局搜索能力，但是在一定程度上會減弱信息素的引導(dǎo)能力，整體進(jìn)入盲目的搜索狀態(tài)，從而得到不穩(wěn)定的結(jié)果。因此，ρ的取值會影響整體算法的搜索能力和效率，根據(jù)這一特點，本文對ρ值的設(shè)置進(jìn)行了改進(jìn)。隨著迭代次數(shù)的增加，信息素?fù)]發(fā)因子ρ也逐步增大，以適應(yīng)蟻群搜索過程中信息素濃度的變化。

(14)

其中：n表示當(dāng)前迭代次數(shù)，N表示總迭代次數(shù)。一開始ρ設(shè)置為一個較小的值，目的是保持蟻群算法搜索的特點，在前期通過信息素的引導(dǎo)，找到一些較好的路徑；進(jìn)入迭代的第二階段，也就是0.25N之后，路徑上的信息素積累到較大的值，開始加大揮發(fā)力度，以防止一些路徑信息素濃度累積過高，存在陷入局部最優(yōu)的風(fēng)險；三階段的調(diào)整在迭代次數(shù)為0.75N時進(jìn)行，路徑上的信息素濃度都已達(dá)到一個較大的值，相應(yīng)地增大ρ值。

3.3 多策略改進(jìn)

(1)2-opt算法 2-opt是一種局部搜索算法，原理是隨機(jī)獲取路線上的兩個點，將這兩個點之間的點都進(jìn)行逆序翻轉(zhuǎn)，兩點外的其他點順序不變[26]。圖1a可以表示為一個VRP的路線圖，0為配送中心，其他點為客戶點。路線3的原路徑為：(0，10，6，8，7，3，0)，假設(shè)隨機(jī)獲得了點7和點6，經(jīng)過翻轉(zhuǎn)后，得到的路徑為：(0，10，7，8，6，3，0)。

(2)順序交換策略 順序遍歷每一客戶點，將當(dāng)前客戶點與同一路線內(nèi)和不同路線之間的客戶點位置進(jìn)行交換，如圖2所示。圖2舉例說明了路線間的客戶點交換，假設(shè)圖2a遍歷到了路線2中的點3和路線3中的點2，這兩個點進(jìn)行交換，即得到圖2b中的結(jié)果。

(3)順序插入策略 順序遍歷每一客戶點，將當(dāng)前客戶點插入到同一路線或不同路線中的客戶點位置，如圖3所示。圖3舉例說明了在路線間插入客戶點的情況，假設(shè)圖3a遍歷到了路線2中的點3，將點3插入到路線3中，即得到圖3b中的結(jié)果。

本文使用這3種策略對蟻群算法每次迭代后得到的最優(yōu)路徑進(jìn)行優(yōu)化。根據(jù)VRPTW約束，最優(yōu)解中會出現(xiàn)多條回路，因此多策略將會對每一條回路進(jìn)行調(diào)整優(yōu)化，調(diào)整次數(shù)設(shè)置為每條路徑的節(jié)點數(shù)，以此來適應(yīng)數(shù)據(jù)的變化。每一次調(diào)整后都會判斷是否能夠得到比初始解更好的路徑，若調(diào)整后出現(xiàn)更短的路徑則替代原路徑。

4 改進(jìn)蟻群算法在VRPTW問題上的應(yīng)用

本章采用Java語言編寫了改進(jìn)算法，主要進(jìn)行了兩個實驗：第一個實驗將本文的改進(jìn)算法應(yīng)用在Solomon Benchmark problem的算例 C101上，并調(diào)整迭代次數(shù)，與官網(wǎng)結(jié)果進(jìn)行對比；第二個實驗將本文改進(jìn)算法與基本蟻群算法同樣應(yīng)用在算例C101上進(jìn)行對比。兩個實驗均得到了較好的結(jié)果，本章將對實驗及結(jié)果進(jìn)行分析比對。實驗環(huán)境為：Windows 10系統(tǒng)，Intel(R)Core(TM)i5-7300HQ CPU @ 2.50 GHz。

4.1 參數(shù)設(shè)置

蟻群算法沒有設(shè)置參數(shù)的規(guī)范，需要通過大量反復(fù)的實驗得到一個較好的參數(shù)設(shè)置范圍。本文通過反復(fù)實驗之后，得到了讓實驗結(jié)果呈現(xiàn)最好效果的參數(shù)，參數(shù)設(shè)置如下：種群規(guī)模(螞蟻數(shù)量)為100；螞蟻載重上限(容量)為200；迭代次數(shù)為1 000；α=1；β=2；pbest=0.05。

4.2 算法設(shè)計

算法的具體流程如下：

(1)對信息素、客戶以及車輛信息等相關(guān)參數(shù)進(jìn)行初始化，設(shè)車輛數(shù)量為m，且共有n個城市，候選客戶數(shù)組為allowk[n]。將蟻群算法應(yīng)用在VRPTW時，算法中的蟻群相當(dāng)于車輛集合。

在互聯(lián)網(wǎng)時代條件下，物聯(lián)網(wǎng)技術(shù)的應(yīng)用為農(nóng)業(yè)產(chǎn)生帶來了極大的便利，同時也促進(jìn)著農(nóng)業(yè)生產(chǎn)技術(shù)的發(fā)展。智慧農(nóng)業(yè)作為一種新型農(nóng)業(yè)形態(tài)，其融合了多項現(xiàn)代信息技術(shù)，有效解決了農(nóng)業(yè)生產(chǎn)中遇到的問題，是未來農(nóng)業(yè)發(fā)展的必然趨勢。要想促進(jìn)農(nóng)業(yè)的高效、可持續(xù)發(fā)展，就必須加大物聯(lián)網(wǎng)技術(shù)在農(nóng)業(yè)生產(chǎn)中的應(yīng)用，不斷創(chuàng)新農(nóng)業(yè)生產(chǎn)模式，以提高生產(chǎn)效率。

(3)判斷車輛載重是否超過車輛最大容量C或服務(wù)時間超過客戶點接受服務(wù)時間范圍[ai,bi]，若判斷為真，則讓其返回配送中心，記錄下本次途經(jīng)的路徑，再重新創(chuàng)建一條從配送中心出發(fā)的新路徑，更新當(dāng)前位置信息；反之，車輛k將準(zhǔn)備移動到客戶點j并更新局部信息素。

(4)接著根據(jù)allowk[k]中所剩的個數(shù)判斷是否遍歷完所有城市，若車輛k已完成全部走訪任務(wù)，則車輛k回到配送中心，k=k+1；反之，車輛k繼續(xù)計算狀態(tài)轉(zhuǎn)移尋找下一客戶點，即重復(fù)步驟(2)。

(5)判斷當(dāng)前k是否等于車輛數(shù)量上限m，若k=m，則結(jié)束本次迭代，得到本次迭代最優(yōu)解，使用改進(jìn)的信息素全局更新公式進(jìn)行更新；反之，開始第k輛車的走訪任務(wù)。

(6)本次判斷迭代次數(shù)是否大于最大迭代次數(shù)，若成立，則結(jié)束本次迭代，輸出最優(yōu)解X；反之，則迭代次數(shù)增加一次，開始新一輪迭代。

改進(jìn)算法流程圖如圖4。

4.3 實驗過程

4.3.1 實例1

數(shù)據(jù)集選用Solomon Benchmark，該數(shù)據(jù)集包括6類算例：C1、C2、R1、R2、RC1、RC2，其中C1、R1、RC1的算例的時間窗口比較小，設(shè)定的車輛負(fù)載較??；C2、R2、RC2則相反，其中的算例時間窗口較大，車輛負(fù)載也較大。本次實驗將改進(jìn)的算法應(yīng)用在Solomon Benchmark的算例C101中不同數(shù)量的客戶點中，分別為：25，50，100。

輸入實例如表1所示(選取前10個客戶點作為展示)，序號0為配送中心。

表1中算例C101給出的信息有：使用橫縱坐標(biāo)來表示客戶點的位置信息、貨物量ci、時間窗起始時間ai、時間窗結(jié)束時間bi，以及服務(wù)時間si。

表1 Solomon Benchmark problems中算例C101前10個客戶點信息

Solomon Benchmark 的網(wǎng)站給出了各個算例歷來使用啟發(fā)式算法求解得到的最優(yōu)路徑，將其與本次改進(jìn)后得到的最優(yōu)解對比，如表2。

從表2中可以看到，改進(jìn)后的算法結(jié)果雖然與精確解有一定的差值，但是官網(wǎng)同時給出了C101.100啟發(fā)式求解方法的最優(yōu)解為828.94，即與表2中改進(jìn)后的最優(yōu)解是相同的，由此可知本次改進(jìn)后的結(jié)果有著較為良好的效果。

表2 歷來啟發(fā)式最優(yōu)路徑和本次改進(jìn)最優(yōu)解對比

通過實驗，當(dāng)客戶點數(shù)量為25時，改進(jìn)蟻群算法算法得到的最短路徑X=191.81對應(yīng)的路線如表3所示。

表3 客戶點數(shù)量為25的最優(yōu)路徑

當(dāng)客戶點數(shù)量為50時，改進(jìn)蟻群算法算法得到的最短路徑X=363.24對應(yīng)的路線如表4所示。

表4 客戶點數(shù)量為50的最優(yōu)路徑

當(dāng)客戶點數(shù)量為100時，改進(jìn)蟻群算法得到的最短路徑X=828.94對應(yīng)的最優(yōu)徑路如表5所示。

表5 客戶點數(shù)量為100的最優(yōu)路徑

4.3.2 實例2

本次實驗將基本蟻群算法和改進(jìn)蟻群算法進(jìn)行對比，選取了C1型、R1型和RC1型的實例，每種類型選取4個算例，分別為：C101、C102、C103、C104、R101、R102、R103、R104、RC101、RC102、RC103、RC104，共12個實例。每個算例測試10次，將得到的最優(yōu)路徑長度取平均值進(jìn)行對比，得到結(jié)果如表6所示。

表6 最優(yōu)路徑長度均值對比

由表6的最長路徑長度均值對比可知，基本蟻群算法通過改進(jìn)后解的質(zhì)量得到了顯著提升。接下來對兩個算法得到的最短路徑長度平均值進(jìn)行比較，如圖5所示。

從圖5更直觀地看到了改進(jìn)蟻群算法得到的最優(yōu)路徑明顯比基本蟻群算法得到的最優(yōu)路徑更好。本次研究選取了改進(jìn)蟻群算法和基本蟻群算法在c101算例上得到的最優(yōu)路徑解，根據(jù)算例中的橫縱坐標(biāo)畫出其最優(yōu)解的路徑圖，如圖6和圖7所示。

從圖6和圖7中能夠看到路徑的選擇方式，基本蟻群算法得到的路徑中存在一些交叉路徑，使得到的結(jié)果路徑更長，路徑質(zhì)量降低，相較之下，改進(jìn)蟻群算法的路徑更為簡潔。

本次實驗將兩個算法的收斂情況進(jìn)行了對比，如圖8所示。

本次實驗最大迭代次數(shù)設(shè)置為 1 000，圖8顯示了在這1 000次迭代中兩個算法收斂的情況。蟻群算法存在著容易過早收斂，陷入局部最優(yōu)的問題，這個現(xiàn)象可以從圖8中看到。在改進(jìn)蟻群算法還在搜索最優(yōu)路徑解時，基本蟻群算法已經(jīng)早早地停滯在當(dāng)前搜索結(jié)果上，沒有再繼續(xù)進(jìn)行搜索；而改進(jìn)蟻群算法能夠不斷地進(jìn)行搜索，直到找到最優(yōu)路徑解，這說明改進(jìn)算法擴(kuò)大了蟻群算法的搜索范圍，增強(qiáng)了路徑的搜索能力，達(dá)到了改進(jìn)目的。

5 結(jié)束語

VRPTW是經(jīng)典NP難問題，隨著問題規(guī)模的不斷增大，啟發(fā)式算法更適用于解決這類問題。蟻群算法則是經(jīng)典的群智能啟發(fā)式算法，其最初就是為了解決TSP而提出的，因此蟻群算法對解決路徑問題有著天然的適應(yīng)性。算法本身具有正反饋、適應(yīng)性強(qiáng)、魯棒性強(qiáng)等優(yōu)點，在解決VRP上也具有較為良好的表現(xiàn)，但同時也存在許多缺點。本次改進(jìn)針對蟻群算法容易陷入局部最優(yōu)的缺點，從3個方面對算法進(jìn)行改進(jìn)，目的是增強(qiáng)算法的路徑搜索能力，擴(kuò)大搜索范圍。本文改進(jìn)內(nèi)容如下:

(1)改進(jìn)信息素更新方式，每次迭代只更新最優(yōu)路徑上的信息素值，同時增加一個獎勵值獎勵，且對信息素值設(shè)置了動態(tài)區(qū)間，為找到最優(yōu)路徑的螞蟻保證后續(xù)搜索的解質(zhì)量。

(2)改進(jìn)信息素?fù)]發(fā)因子，隨著迭代次數(shù)的增加動態(tài)地調(diào)整信息素?fù)]發(fā)因子的大小以適應(yīng)蟻群搜尋路徑的情況。

(3)加入2-opt算法、順序交換策略、順序插入策略對每次迭代得到的最優(yōu)解進(jìn)行優(yōu)化，調(diào)整最優(yōu)解中每一條回路中任意兩條邊，重新計算路徑長度，若得到更短的路徑長度則替代原路徑，循環(huán)迭代最終得到最優(yōu)解。

在實驗部分，利用Java編程實現(xiàn)了改進(jìn)方案的全部代碼，然后在Solomon Benchmark中的算例上進(jìn)行測試，最后通過兩個部分的實驗，證明了改進(jìn)蟻群算法具有較為優(yōu)良的效果的結(jié)論，并達(dá)到了增強(qiáng)路徑搜索能力，防止蟻群算法陷入局部最優(yōu)的目的。蟻群算法本身還存在參數(shù)較多且難以設(shè)定的問題，在未來的研究方向中可以更多的考慮對參數(shù)的優(yōu)化，同時，可以嘗試在路徑優(yōu)化方向上找到更高效的策略，從而提高最優(yōu)解的質(zhì)量。