改進蟻群算法在快遞配送路徑中的應用

陸緣緣，高華成，崔 衍

(南京郵電大學 物聯網學院，江蘇 南京 210023)

0 引 言

隨著快遞業的飛速發展，快遞單量也在飛速增加，如何能夠準時地進行快遞配送已經成為現在快遞行業的一個重要評價標準。在史曉原[1]的研究中發現，近年來快遞投訴有效率高達95%，且其最突出的問題就是快遞晚點問題。如何提高末端快遞配送速度成為重中之重。對于這一問題，近年來國內外學者提出了多種優化算法對快遞配送路徑進行優化，包括蟻群算法、遺傳算法、粒子群算法等。楊從平[2]將信息素釋放量與各個節點的螞蟻數量聯系在一起，采用動態的釋放函數進行各個節點的信息素釋放。胡春陽等[3]對兩點之間的搜索進行優化，對蟻群算法進行改進，提出雙向搜索機制并引入懲戒因子，可以提高蟻群的搜索能力。李桃迎等[4]對外賣配送問題改進遺傳算法，引入聚類算法根據配送點的屬性進行聚類分析，并在其后的遺傳算法計算中對編碼形式進行改進，加速優化速度。趙靜等[5]對啟發函數和信息素揮發因子進行改進以提高蟻群算法的搜索能力，采用連接目標方式改進啟發函數使搜索更具有目的性，并使信息素揮發因子自適應變化，保證在找到最優解時可以快速收斂。Jiao Z等[6]對蟻群算法進行改進，提出多態蟻群優化算法。對路徑上的信息素進行自動變化原則，使得蟻群在進行路徑搜索時更容易找到最優路徑。黃國銳等[7]通過對蟻群算法路徑選擇進行研究，認為可以通過相互合作進行路徑偏好選擇，相鄰螞蟻可以相互影響其信息素釋放。Deng W等[8]針對蟻群算法前期信息素匱乏的問題，提出可以通過粗略搜索獲得初始化信息素，然后再通過蟻群算法進行最優路徑的搜索。馬貴平等[9]對蟻群算法各個節點之間的道路上信息素的最大最小值進行限制，從而可以改變路徑選擇的概率，加快迭代速度。

以上文獻中都對現代啟發算法進行改進，但考慮得還不夠全面。如蟻群算法在改進的過程中有的只考慮局部最優解問題[10]，或是只考慮優化速度問題，并沒有同時解決這兩個問題。對于平均最優路徑都沒有進行改變，說明最終在搜索方面，螞蟻的搜索路徑仍較為分散。

如何對快遞末端配送進行優化，都雪靜等[11]提出了一種快遞自提柜放置在地鐵口的設計理念，通過這種辦法降低運輸成本、減少貨物到達客戶手中的時間等。但是將快遞放在地鐵口會讓用戶從家出來拿快遞花費的時間更長，并不會減少用戶所等待的時間，沒有方便用戶。李玲玉等[12]則提出在快遞末端配送的類TSP問題上采用C-W節約算法對快遞配送路徑進行優化，所找出的最佳路徑平均縮短了7.8%的里程，但是在搜索速度上還有進一步的優化空間。李鳳坤等[13]對蟻群算法多目標搜索問題，選擇將多目標變為單目標進行搜索遍歷，最后利用遺傳算法對目標路徑進行優化，找出最優解。但此算法中由于多目標合成單目標是避免了極值的影響，也失去了路徑優化過程中的多樣性，容易在遺傳算法后期陷入局部最優解，冗余過大。葉威惠等[14]對快遞配送過程中的旅行商問題進行研究，對遺傳算法染色體的產生進行改進。采用當前節點最近點作為染色體中的一個染色體進行初始化，從而在搜索過程中可以快速找到最優解。Qi Chengming等[15]在使用蟻群算法計算路徑優化問題時，結合PLS(pareto local search)算法對蟻群算法找到的路徑做進一步優化。但是PLS是一個針對單目標問題的本地搜索算法的拓展，在多目標搜索處理上并不能有效且快速地找到最優路徑。

為此，文中提出一種改進蟻群算法來解決快遞配送問題中的TSP問題，采用遺傳-蟻群相結合的方式，對遺傳算法的啟發函數進行改進。首先，針對蟻群算法前期搜索較慢的問題引入啟發函數來進行信息素更新。其次，對蟻群算法易于陷入局部最優解的問題，對螞蟻搜尋的路徑進行交叉、變異操作。最后，對蟻群算法的信息素揮發因子進行改進，利用遺傳算法的啟發函數使信息素揮發函數自適應變化，從而快速找到最優解。

1 相關算法分析

1.1 傳統遺傳算法

傳統的遺傳算法(GA)[16]是對生物界所存在的生物進化過程進行模擬而提出的一種搜索最優解的方法。最早于1975年提出，其本質是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型。在計算機仿真時，對求解的問題進行轉換，轉換成為類似生物體內染色體基因的形式，每一個節點就是一個染色體。并根據“物競天擇、適者生存”原則對染色體進行進化，引入選擇、交叉、編譯三個基本操作算子，加快其搜索能力。

遺傳算法將需要進行搜索的問題進行演化變為一個種群，再將這個種群經過基因編碼成為一條染色體。在每一次進行演化時，引入適應度函數對染色體個體進行計算，引入選擇、交叉、編譯操作算子，產出代表新的種群。這樣，經過一系列操作所產生的種群會更有競爭力，其最優個體可以認為是最優解。但是遺傳算法也存在一些問題，如搜索速度慢、易陷入“早熟”，導致后期冗余過大。因此常對啟發函數進行改進以提高搜索能力，避免過早陷入“早熟”。所以，目前對于遺傳算法的改進一直在進行，如：Mei和Wang等[17]提出了一種稱為蜂王演化遺傳算法，實現了使用運算符序列來進行迭代執行以尋找最優路徑。

1.2 傳統蟻群算法

蟻群算法(ACO)[2-3]是對自然界中螞蟻群體覓食行為進行模擬而提出的一種啟發式搜索算法，于20世紀90年代首先提出。算法因可進行并行計算，魯棒性好和正反饋機制被廣泛地應用在車輛調度、路徑優化、網絡路由等問題上。生物界中螞蟻進行覓食，剛開始會隨機進行路徑的選擇。但是螞蟻在路徑中進行爬行時會分泌一種物質，這種物質會影響其他螞蟻在覓食時對路徑的選擇。路徑上存在的信息素越多，那么螞蟻選擇這條路徑的概率就越大，這樣最終可以找到最優的覓食路徑。在蟻群算法中，首先設置初始螞蟻種群，通過輪盤賭方法將其分布在各個點，并根據其狀態轉移函數對螞蟻下一步移動節點進行計算。其公式如下：

(1)

ηij(t)=1/dij

(2)

其中，dij表示節點i到節點j的距離。allowk表示螞蟻k還未訪問的節點集合，在螞蟻k進行搜索的過程中，已訪問的節點會放到禁忌表tabuk中，未訪問的放到allowk中。由狀態轉移概率公式可以看出，距離當前節點信息素越高的節點下次被訪問到的概率就越大。所以在蟻群算法中需要對路徑上的信息素進行更新，信息素會進行揮發，常設ρ來代表揮發因子。在信息素進行揮發的同時還需要再將在該時刻上其他螞蟻所釋放的信息素進行累加。其公式如下:

(3)

蟻周系統：

(4)

蟻密系統：

(5)

蟻量系統：

(6)

其中，Q為信息素總量，Lk表示螞蟻k在一次迭代中所通過路徑的總長度，dij表示節點i到節點j之間的距離。

蟻群算法較其他啟發算法，搜索能力更強，所以在路徑搜索方面使用蟻群算法較好。但是，在TSP問題的搜索上，雖然可以取得良好的效果，能夠找到一條可以遍歷所有節點的最短路徑，卻仍存在一些缺點:

(1)當節點過多時，計算時間較長。

(2)前期由于信息素缺乏，搜索速度較慢。

(3)本質上要求所有螞蟻選擇同一條路，該線路即為最優線路。但是在實際的使用中，給定迭代次數，很難達到這個條件，使找到最優路徑在某種情況下可能只是局部最優解。

2 改進蟻群算法

2.1 信息素初始矩陣更改

傳統蟻群算法信息素初始矩陣一般設置為0或者1，這樣會造成前期蟻群算法信息素匱乏的問題，導致前期搜索過慢，因此本算法對信息素初始矩陣進行改進。由于遺傳算法因其啟發函數的存在，導致前期搜索速度較快，設計信息素初始化啟發函數對蟻群算法信息素初始矩陣進行設值。對遺傳算法啟發函數公式的改進如下：

Tau(i.j)=

(7)

其中，n為節點的個數，aviDistances為每個節點到給定點之間的距離占總路徑長度的概率，maxval為aviDistances中的最大值，minval為aviDistances中的最小值，min則為彌補精度采用的一個極小值。

aviDistances公式為：

(8)

其中，D為各個節點之間的距離，st為給定起始點，sumDistances為總路徑長度，公式如下：

(9)

通過計算出起始點到其他各個節點的概率，其距離越近，概率越大，符合蟻群系統中螞蟻根據信息素尋找路徑的規則。所以將此結果Tau作為蟻群算法信息素初始矩陣有助于蟻群算法避免前期搜索較慢的問題。

2.2 迭代中引入變異、交叉操作

在蟻群算法進行最優路徑的搜索時，螞蟻會根據路徑上信息素的大小來進行路徑的選擇。但是，可能存在所選的最優路徑只是某局部的最優路徑。這時，如果問題本身屬于凸優化問題，則可認為這個解是整體最優解。如果問題是非凸優化問題，則無法保證這個解是整體最優解。所以，引入交叉、變異操作，對迭代中的路徑盡可能多樣化，突破局部最優解的問題。交叉操作會隨機選擇將兩條路徑進行一定的交叉形成一條新的路徑，變異操作會對路徑中的某一個節點進行替換操作，突破當前的搜索限制，更容易找到最優解。為此，在本算法中設置輪盤賭大小tournamentSize的值。然后進行tournamentSize次的輪盤賭選擇，選擇出隨機的tournamentSize個路徑，選擇其中距離最小的路徑。重復兩次，這樣將兩個最小路徑進行交叉操作。交叉的結果進行變異，將變異后的結果存儲。

整個過程重復m次，這樣最終用經過交叉、變異的路徑替代原有的路徑，避免陷入局部最優解的問題。

2.3 信息素更新規則更改

傳統蟻群算法當節點過多時迭代次數較多，計算時間較長且其計算結果的平均路徑較為分散。所以，對蟻群算法的信息素更新公式進行改進，解決所存在的問題。傳統的蟻量、蟻密和蟻周系統局限性太大，信息素的更新容易陷入局部最優解，且在一定的迭代次數中，螞蟻難以找到一條最優路徑進行共同遍歷，平均距離較大，說明螞蟻尋找的路徑波動較大。對這一問題，文中對蟻群算法的信息素更新公式進行改進，公式如下：

(10)

(11)

其中，aviDistances(i,j)計算的是起點到每個點的概率，其公式為：

aviDistances=

(12)

其中，D為各個節點之間的距離，Table為當前蟻群所走的路徑。對信息素更新公式進行自適應計算，有助于蟻群快速找到最優解。在多節點計算時，可以更快地得到最優解，減少迭代次數和迭代時間。

2.4 改進蟻群算法實現步驟

(1)利用公式(9)計算每條路徑上的總路徑長度，之后利用公式(8)計算每兩個節點之間的距離所占總路徑的比例，計算出其選中的概率。再之后利用公式(7)計算出初始信息素矩陣τ(i,j)的值。

(2)設置蟻群算法的初始種群螞蟻數量m,迭代次數iter初始值及最高迭代次數iter_max。設置信息素啟發函數系數α，期望啟發函數β以及信息素揮發系數ρ。設置常系數Q，起點位置，初始化禁忌表，設置交叉和變異概率的值。

(3)尋找路徑，將起點加入到禁忌表中，根據狀態轉移概率公式計算下一可達節點的概率，根據輪盤賭方法選擇下一到達節點，直到節點全部加入禁忌表。

(4)利用交叉、變異對禁忌表進行操作。

(5)利用改進信息素更新公式更新信息素矩陣。

(6)判斷當前迭代次數是否大于最大迭代次數，如果大于則輸出最優路徑，否則繼續進行迭代搜索。

(7)得到最優路徑，算法終止。

改進蟻群算法具體流程如圖1所示。

圖1 改進ACO算法流程

3 實驗仿真與結果分析

針對快遞末端配送問題，對提出的算法進行仿真實驗。仿真使用Matlab工具進行仿真，隨機設置31個點的坐標，其中一個坐標為快遞物流轉運站，其他點是各個小區快遞柜。設置蟻群算法各變量值，其中螞蟻數量50，最大迭代次數為100。信息素重要因子α經過測試設置為1，當值為1時搜索性能最好。啟發函數重要程度因子β值過小，會導致局部最優解，經過測試β取值5其搜索性能最好。信息素揮發因子ρ=0.1，交叉概率為0.8，變異概率為0.1。建立的模型如圖2所示。

圖2 地點分布

圖中黑色實心點是快遞公司物流轉運站，其他點是30個小區快遞柜坐標。使用蟻群算法以快遞站為起點進行TSP搜索遍歷，對改進蟻群算法和傳統蟻群算法的搜索效率進行對比。

圖3是傳統蟻群算法迭代100次搜索的最短路徑，其最短路徑路程長度是229.94 km。圖4為改進蟻群算法迭代100次搜索的最優路徑，其最短路徑路程長度為224.88 km，通過計算可知，改進算法比傳統算法在搜索總長度上優化了2.2%。

圖3 傳統蟻群算法最優路徑

圖4 改進蟻群算法最優路徑

對兩種算法的實驗結果進行比較，最優路徑對比如圖5所示。從圖中可以看出，改進蟻群算法比傳統蟻群算法更早地找到了最優解，且突破了傳統蟻群算法的局部最優解問題。通過計算得知，改進蟻群算法比傳統蟻群算法的效率提高64%。

在圖6中可以看出，在平均路徑方面改進蟻群算法比傳統蟻群算法性能更好。改進蟻群算法從第15>次開始，其平均路徑在230左右波動，而傳統蟻群算法在第50次才趨于穩定波動，其波動值在260左右。改進蟻群算法比傳統蟻群算法在波動時間方面優化了70%，在波動值穩定性方面優化了11.5%。

圖5 最優路徑對比

圖6 平均路徑對比

在最終迭代結果中查看最后一次禁忌表，查看其50只螞蟻搜索路徑，將兩種算法進行對比。圖7是傳統蟻群算法最后迭代禁忌表，可以看出其螞蟻搜索仍較為分散，不符合最優解的規定。圖8是改進蟻群算法最后迭代禁忌表，可以看出其螞蟻搜索已經趨于一致，符合最優解的規定，解決了2.2節提出的傳統蟻群算法在一定迭代次數中無法解決蟻群搜索路徑一致性的問題。

圖7 傳統蟻群算法最后迭代禁忌表

圖8 改進蟻群算法最后迭代禁忌表

文中提出的改進蟻群算法對傳統蟻群算法存在的前期信息素匱乏導致搜索速度過慢、節點過多導致迭代次數較多和平均路徑較為分散導致不完全滿足最優路徑的問題都有所改善。

表1 兩種算法迭代數據對比

由表1中的數據可看出，改進蟻群算法對傳統蟻群算法前期搜索過慢的問題進行了改進，在前期搜索效率和迭代次數方面都優于傳統算法。在查找最優路徑方面，其最優解的值和平均路徑值都更符合最優解。

4 結束語

從實際情況出發，對快遞末端配送問題進行分析，提出了一種改進蟻群算法。引入啟發公式對信息素初始矩陣進行初始化，避免了蟻群算法前期因信息素匱乏導致搜索緩慢的問題。針對蟻群算法所存在的問題，對蟻群算法搜索的路徑進行交叉、變異。對于信息素的變化問題，通過引入動態更新信息素，加快蟻群對最優路徑的搜索速度，減少迭代次數。通過Matlab工具進行仿真，定點出發進行TSP搜索。從實驗結果可看出，改進的蟻群算法在前期搜索能力、尋找最優解所需時間和平均路徑收斂的控制問題上都優于傳統蟻群算法，具有十分廣泛的應用前景。