楊瑞琪，馬巧玲，連天嬌，郭丹陽，許曙博

（廣州城市理工學(xué)院,廣東廣州，510800）

0 引言

隨著經(jīng)濟(jì)的發(fā)展和社會生活水平的提高，各個城市出現(xiàn)交通擁堵現(xiàn)象，給生鮮產(chǎn)品配送帶來挑戰(zhàn)。生鮮配送的速度會影響到人們健康生活，然而當(dāng)前社會在生鮮配送上的發(fā)展水平較低，需要提高生鮮配送的技術(shù)。

對于生鮮配送路徑優(yōu)化問題的研究，許多國內(nèi)學(xué)者進(jìn)行了大量的研究，并取得一定的成果。文慧君[1]研究了上層為冷鏈物流優(yōu)化總成本，下層為優(yōu)化客戶滿意度的雙層規(guī)劃模型，使用遺傳算法對雙層規(guī)劃模型進(jìn)行求解。楊雅琪[2]在生鮮連鎖店配送路徑問題的研究中，考慮到各地區(qū)交通擁堵的因素，為有效減少生鮮配送成本，并且提高生鮮配送的準(zhǔn)時性。因此為M生鮮連鎖店構(gòu)建出，由蟻群算法和侵入雜草算法相結(jié)合的新混合蟻群算法—生鮮連鎖店配送促進(jìn)優(yōu)化模型。明小菊等[3]以最小化成本為目標(biāo)創(chuàng)建了冷鏈配送優(yōu)化模型，采用萊維飛行和反向?qū)W習(xí)優(yōu)化的粒子群算法對粒子群算法進(jìn)行優(yōu)化用于模型求解。王永鋒[4]針對生鮮產(chǎn)品易腐敗的特性，提出建立帶時間窗的配送車輛路徑優(yōu)化數(shù)學(xué)模型，選擇混沌遺傳算法對模型求解，縮短了運輸距離，降低了運輸成本。

我國對生鮮產(chǎn)品配送的需求不斷增加，為了降低生鮮產(chǎn)品的配送成本，解決路徑優(yōu)化問題，本文采用蟻群算法尋找最優(yōu)路徑，但該算法收斂速度慢、運行時間長、區(qū)域搜索能力差。為了彌補(bǔ)蟻群算法的缺點，引入貪心算法提高了蟻群算法的局部搜索能力。考慮到實際生鮮產(chǎn)品配送需求的特點和相關(guān)條件的制約，設(shè)計了貪心蟻群算法，實施了全球路徑規(guī)劃，達(dá)到了配送路徑的最佳目的。

1 算法

1.1 蟻群算法

蟻群算法是模仿螞蟻覓食的行為，是一種仿生算法。螞蟻在尋找食物的過程中，產(chǎn)生螞蟻和螞蟻之間交換信息的機(jī)制，即信息素，從而獲得食物和當(dāng)前位置的最佳路徑[5]。

傳統(tǒng)的蟻群算法是由1991 年由 Marco Dorigo等提出的。在研究過程中發(fā)現(xiàn)，螞蟻覓食的過程中，會在路上釋放信息素，而且信息素會隨著時間的流逝而揮發(fā)，螞蟻走過的路線越長，留下的信息素?fù)]發(fā)多濃度則低，相反越短的路徑上面的信息素發(fā)揮的時間越短，導(dǎo)致該路徑上的信息素濃度高，更容易引導(dǎo)后來的螞蟻來走這條最短的路徑[6]。蟻群算法就是模擬自然界蟻群尋找從蟻巢到食物源間最短路徑過程的一種隨機(jī)搜索算法[7]。但是蟻群算法存在收斂速度慢，容易陷入局部最優(yōu)解的問題。蟻群算法的執(zhí)行步驟如圖2所示。

圖1 螞蟻的覓食過程

圖2 蟻群算法流程

螞蟻在覓食過程中會在路徑上留下信息素，其他螞蟻則傾向于沿著不同路徑上信息素濃度較高的路徑走，如果距離相同，則傾向于走濃度較高的路徑，經(jīng)過一段時間后，可以以最短的路徑到達(dá)目的地。螞蟻k從選擇下一節(jié)點的概率公式如式（1）所示 ：

每個螞蟻個體在通過特定路徑時釋放信息素，通過所有路徑節(jié)點后，根據(jù)信息素的疊加和揮發(fā)機(jī)制更新路徑中的信息素，更新策略如公式（3）所示：

式中：ρ為信息素?fù)]發(fā)系數(shù)，（1-ρ）為信息素的殘留系數(shù)，如果ρ值過小，會導(dǎo)致殘留的信息素裹多，則會無法區(qū)別路徑的長短，?τij為節(jié)點i到節(jié)點j信息素的增量，其計算值如式（4）所示 ：

式中：Q為蟻群算法的信息素強(qiáng)度系數(shù)。

1.2 貪心算法

貪心算法是一種能夠得到某種度量意義下的最優(yōu)解的分級處理方法，它總是做出在當(dāng)前看來是最優(yōu)的選擇，也就是說貪心策略并不是從整體上加以考慮它所做出的選擇只是在某種意義上的局部最優(yōu)解算法[8]。貪心算法在路徑規(guī)劃方面，每次僅會選擇離當(dāng)前節(jié)點最近的節(jié)點，直到所有的節(jié)點都選取完畢，就完成路徑規(guī)劃。由于貪心策略總是采用從全局看來是最優(yōu)的選擇，因此并不從整體上加以考慮，不能保證求得的最后解是最佳的。

當(dāng)貪心算法經(jīng)常被用于解決優(yōu)化問題時，為了獲得目標(biāo)函數(shù)最優(yōu)解，將會不斷地進(jìn)行搜索選擇。采用循環(huán)的動態(tài)方式縮小問題、解決問題，不斷得出子問題的最優(yōu)解。例如，在活動選擇問題中，我們總是根據(jù)一個問題選擇結(jié)束時間最早的活動，然后根據(jù)其余活動選擇結(jié)束時間最早的活動，直到?jīng)]有活動以這種方式選擇為止。綜上所述，將總問題劃分成子問題，依次求解子問題的最優(yōu)解，最后將子問題的最優(yōu)解整合成總問題的解[9]。

1.3 貪心蟻群算法

針對貪心算法和蟻群算法各自的缺點，把兩種算法結(jié)合起來，在傳統(tǒng)蟻群算法的操作步驟中接入貪心策略，提高算法的局部搜索能力和收斂速度。算法步驟如下：首先進(jìn)行初始化參數(shù)，包括蟻群初始化數(shù)量、最迭代次數(shù)、啟發(fā)函數(shù)因子、揮發(fā)因子、信息素等，其中開始的時候每條邊的信息素量都相等。將各只螞蟻分別放在各個的頂點，禁忌表為對應(yīng)的頂點。其次選取一只螞蟻，引入貪心策略修改初始路線。傳統(tǒng)的蟻群算法，螞蟻的初始路線是隨機(jī)生成的，當(dāng)遇見帶有信息素的路線時，根據(jù)概率決絕是否要更改路線。蟻群即使當(dāng)下時刻選擇了走帶有信息素的路線，下一時刻也不一定會繼續(xù)走帶有信息素的路線，反而是繼續(xù)走隨機(jī)路線。由于隨機(jī)路線是隨機(jī)生成的，當(dāng)參數(shù)設(shè)置不當(dāng)時，算法搜索路徑的時候會延長，收斂速度極慢，因此引入貪心策略，設(shè)置蟻群的初始路線，減少算法迭代的時間。計算一只螞蟻額的轉(zhuǎn)移概率，選擇下一個頂點，更新禁忌表，再計算概率，再選取頂點，循環(huán)往復(fù)，直至這只螞蟻遍歷了所有頂點。計算當(dāng)前這只螞蟻留在各條邊上的信息素增量，然后該螞蟻完成使命死去。所有螞蟻都重復(fù)一樣的步驟。直到所有螞蟻都完成使命。計算各條邊的信息素增量 ?τij和信息素量τij(t+n)。最后，記錄本次迭代的路徑，更新當(dāng)前的最優(yōu)路徑，清空禁忌表。判斷是否達(dá)到預(yù)定的迭代步數(shù)，若是則輸出當(dāng)前的最優(yōu)路徑，結(jié)束程序，若為否，則繼續(xù)迭代。

2 實驗

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

蟻群作為一種啟發(fā)式搜索算法，蟻群算法具有良好的魯棒性，且易于融合其他算法應(yīng)用到實際問題中[5]。貪心蟻群算法的實驗參數(shù)設(shè)置如下表所示，參數(shù)的設(shè)置都是在經(jīng)驗值的基礎(chǔ)上，結(jié)合實驗效果進(jìn)行修改的，具有一定的適用性。

表1 相關(guān)參數(shù)設(shè)置

2.2 實驗數(shù)據(jù)介紹

為了驗證算法改進(jìn)的有效性，使用32個信息節(jié)點來模擬一位生鮮配送員的配送情況，并利用Matlab軟件編寫算法實現(xiàn)。節(jié)點的部分信息如下所示。其中節(jié)點1表示起點，節(jié)點2-32表示顧客，如表2所示。假定生鮮配送員以勻速行駛，沒有突發(fā)狀況發(fā)生。

表2 部分節(jié)點信息

2.3 結(jié)果分析

分別對貪心算法、傳統(tǒng)的蟻群算法和改進(jìn)后的貪心蟻群算法進(jìn)行10次實驗，得到的結(jié)果如下表所示。從尋優(yōu)的結(jié)果可以看出，在求解該問題的最優(yōu)路線時，貪心算法只基于當(dāng)前節(jié)點考慮下一個最優(yōu)節(jié)點，導(dǎo)致前期的路線為最優(yōu)路線，后期的路線為剩余節(jié)點的湊合，路線很長，達(dá)不到全局優(yōu)化的目的。而蟻群算法和貪心蟻群算法從圖中可以看出，規(guī)劃的路線節(jié)點之間的長度較均勻合理。但是貪心蟻群算法所求得的路徑的距離是三種中最短的、算法運行的時間也較傳統(tǒng)的蟻群算法少得多。如圖可知，貪心蟻群最優(yōu)解的配送路線為：1-15-9-8-4-25-21-32-16-6-12-22-11-10-13-19-5-7-14-27-2-23-28-17- 29-24-3-18-31-30-20-26，計算得到總距離約114.9294km。

表3 算法運行結(jié)果

圖3 貪心算法路徑規(guī)劃圖

圖4 蟻群算法路徑規(guī)劃圖

圖5 貪心蟻群路徑規(guī)劃圖

螞蟻種群算法和貪心蟻群算法的最佳距離和算法迭代次數(shù)如下圖所示，通過貪心算法改善局部搜索能力后，可以用較少的迭代次數(shù)找到最佳路徑，算法的改進(jìn)具有良好的效果。

圖6 蟻群算法適應(yīng)度曲線

圖7 貪心蟻群算法適應(yīng)度曲線

3 結(jié)論

本文基于生鮮配送問題，使用貪心算法、蟻群算法和改進(jìn)后的貪心蟻群算法進(jìn)行求解，通過對比實驗可知，貪心蟻群算法能加快算法的收斂，并進(jìn)行路徑的優(yōu)化。