改進(jìn)蟻群算法在快遞配送路徑中的應(yīng)用

陸緣緣，高華成，崔 衍

(南京郵電大學(xué) 物聯(lián)網(wǎng)學(xué)院，江蘇 南京 210023)

0 引 言

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

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

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

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

1 相關(guān)算法分析

1.1 傳統(tǒng)遺傳算法

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

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

1.2 傳統(tǒng)蟻群算法

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

(1)

ηij(t)=1/dij

(2)

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

(3)

蟻周系統(tǒng)：

(4)

蟻密系統(tǒng)：

(5)

蟻量系統(tǒng)：

(6)

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

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

(1)當(dāng)節(jié)點(diǎn)過多時，計(jì)算時間較長。

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

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

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

2.1 信息素初始矩陣更改

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

Tau(i.j)=

(7)

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

aviDistances公式為：

(8)

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

(9)

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

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

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

整個過程重復(fù)m次，這樣最終用經(jīng)過交叉、變異的路徑替代原有的路徑，避免陷入局部最優(yōu)解的問題。

2.3 信息素更新規(guī)則更改

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

(10)

(11)

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

aviDistances=

(12)

其中，D為各個節(jié)點(diǎn)之間的距離，Table為當(dāng)前蟻群所走的路徑。對信息素更新公式進(jìn)行自適應(yīng)計(jì)算，有助于蟻群快速找到最優(yōu)解。在多節(jié)點(diǎn)計(jì)算時，可以更快地得到最優(yōu)解，減少迭代次數(shù)和迭代時間。

2.4 改進(jìn)蟻群算法實(shí)現(xiàn)步驟

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

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

(3)尋找路徑，將起點(diǎn)加入到禁忌表中，根據(jù)狀態(tài)轉(zhuǎn)移概率公式計(jì)算下一可達(dá)節(jié)點(diǎn)的概率，根據(jù)輪盤賭方法選擇下一到達(dá)節(jié)點(diǎn)，直到節(jié)點(diǎn)全部加入禁忌表。

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

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

(6)判斷當(dāng)前迭代次數(shù)是否大于最大迭代次數(shù)，如果大于則輸出最優(yōu)路徑，否則繼續(xù)進(jìn)行迭代搜索。

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

改進(jìn)蟻群算法具體流程如圖1所示。

圖1 改進(jìn)ACO算法流程

3 實(shí)驗(yàn)仿真與結(jié)果分析

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

圖2 地點(diǎn)分布

圖中黑色實(shí)心點(diǎn)是快遞公司物流轉(zhuǎn)運(yùn)站，其他點(diǎn)是30個小區(qū)快遞柜坐標(biāo)。使用蟻群算法以快遞站為起點(diǎn)進(jìn)行TSP搜索遍歷，對改進(jìn)蟻群算法和傳統(tǒng)蟻群算法的搜索效率進(jìn)行對比。

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

圖3 傳統(tǒng)蟻群算法最優(yōu)路徑

圖4 改進(jìn)蟻群算法最優(yōu)路徑

對兩種算法的實(shí)驗(yàn)結(jié)果進(jìn)行比較，最優(yōu)路徑對比如圖5所示。從圖中可以看出，改進(jìn)蟻群算法比傳統(tǒng)蟻群算法更早地找到了最優(yōu)解，且突破了傳統(tǒng)蟻群算法的局部最優(yōu)解問題。通過計(jì)算得知，改進(jìn)蟻群算法比傳統(tǒng)蟻群算法的效率提高64%。

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

圖5 最優(yōu)路徑對比

圖6 平均路徑對比

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

圖7 傳統(tǒng)蟻群算法最后迭代禁忌表

圖8 改進(jìn)蟻群算法最后迭代禁忌表

文中提出的改進(jìn)蟻群算法對傳統(tǒng)蟻群算法存在的前期信息素匱乏導(dǎo)致搜索速度過慢、節(jié)點(diǎn)過多導(dǎo)致迭代次數(shù)較多和平均路徑較為分散導(dǎo)致不完全滿足最優(yōu)路徑的問題都有所改善。

表1 兩種算法迭代數(shù)據(jù)對比

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

4 結(jié)束語

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