基于貪心蟻群算法的生鮮配送全局路徑規劃

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

（廣州城市理工學院,廣東廣州，510800）

0 引言

隨著經濟的發展和社會生活水平的提高，各個城市出現交通擁堵現象，給生鮮產品配送帶來挑戰。生鮮配送的速度會影響到人們健康生活，然而當前社會在生鮮配送上的發展水平較低，需要提高生鮮配送的技術。

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

我國對生鮮產品配送的需求不斷增加，為了降低生鮮產品的配送成本，解決路徑優化問題，本文采用蟻群算法尋找最優路徑，但該算法收斂速度慢、運行時間長、區域搜索能力差。為了彌補蟻群算法的缺點，引入貪心算法提高了蟻群算法的局部搜索能力?？紤]到實際生鮮產品配送需求的特點和相關條件的制約，設計了貪心蟻群算法，實施了全球路徑規劃，達到了配送路徑的最佳目的。

1 算法

1.1 蟻群算法

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

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

圖1 螞蟻的覓食過程

圖2 蟻群算法流程

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

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

式中：ρ為信息素揮發系數，（1-ρ）為信息素的殘留系數，如果ρ值過小，會導致殘留的信息素裹多，則會無法區別路徑的長短，?τij為節點i到節點j信息素的增量，其計算值如式（4）所示 ：

式中：Q為蟻群算法的信息素強度系數。

1.2 貪心算法

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

當貪心算法經常被用于解決優化問題時，為了獲得目標函數最優解，將會不斷地進行搜索選擇。采用循環的動態方式縮小問題、解決問題，不斷得出子問題的最優解。例如，在活動選擇問題中，我們總是根據一個問題選擇結束時間最早的活動，然后根據其余活動選擇結束時間最早的活動，直到沒有活動以這種方式選擇為止。綜上所述，將總問題劃分成子問題，依次求解子問題的最優解，最后將子問題的最優解整合成總問題的解[9]。

1.3 貪心蟻群算法

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

2 實驗

2.1 參數設置

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

表1 相關參數設置

2.2 實驗數據介紹

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

表2 部分節點信息

2.3 結果分析

分別對貪心算法、傳統的蟻群算法和改進后的貪心蟻群算法進行10次實驗，得到的結果如下表所示。從尋優的結果可以看出，在求解該問題的最優路線時，貪心算法只基于當前節點考慮下一個最優節點，導致前期的路線為最優路線，后期的路線為剩余節點的湊合，路線很長，達不到全局優化的目的。而蟻群算法和貪心蟻群算法從圖中可以看出，規劃的路線節點之間的長度較均勻合理。但是貪心蟻群算法所求得的路徑的距離是三種中最短的、算法運行的時間也較傳統的蟻群算法少得多。如圖可知，貪心蟻群最優解的配送路線為：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 算法運行結果

圖3 貪心算法路徑規劃圖

圖4 蟻群算法路徑規劃圖

圖5 貪心蟻群路徑規劃圖

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

圖6 蟻群算法適應度曲線

圖7 貪心蟻群算法適應度曲線

3 結論

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