王海軍

　　(鄂爾多斯應用技術學院,內蒙古 鄂爾多斯 017000)

       摘要：伴隨著現代物流的快速發展，冷鏈物流也得到快速發展。在冷鏈物流研究中配送路徑優化問題對冷鏈物流的發展起到至關重要的作用，鑒于蟻群算法在路徑優化問題中的成功應用，因此將蟻群算法應用到冷鏈物流配送路徑優化問題中?？紤]到蟻群算法運行中存在的問題，將遺傳算法與粒子群算法引入到蟻群算法中，構成基于PSOGAACO算法的冷鏈物流配送路徑優化算法。實驗結果表明，這種構想是可行的，可以有效提高算法運行效率，縮短配送距離，提高經濟效益。

　　關鍵詞：蟻群算法；遺傳算法；粒子群算法；物流；路徑優化

　　中圖分類號：TP301.6, TP15文獻標識碼：ADOI： 10.19358/j.issn.1674-7720.2016.24.026

　　引用格式：王海軍. PSO-GA-ACO算法在冷鏈物流配送路徑優化中的應用［J］.微型機與應用，2016,35（24）：91-93，100.

0引言

　　隨著經濟的發展，現代物流觀念不僅在工業、商業、制造業有了成功的應用，而且開始逐步深入應用到生鮮類農產品的發展中［1］。由于生鮮類農產品具有易腐敗變質的特點，因此就產生了專門針對生鮮類農產品產運銷的冷鏈物流 ［2］。配送路徑優化問題是物流研究的一個核心，在冷鏈物流中也同樣如此，生鮮易腐食品從生產者到最終消費者的過程中，有80%以上的時間花在配送運輸上［3］。因此本文主要研究智能算法在冷鏈物流配送路徑優化上的應用，目前常用的路徑優化算法主要集中在遺傳算法(GA）、粒子群算法(PSO)和蟻群算法(ACO)等一些算法上，本文主要研究ACO算法在冷鏈物流配送路徑中的應用。已有研究成果［4］表明，ACO算法存在易過早陷入局部最優，從而造成算法停滯現象等一系列問題，因此本文將GA、PSO算法引入到ACO算法的優化中，研究PSO-GA-ACO算法在冷鏈物流配送路徑優化中的應用。

1路徑配送模型的構建［5］

　　在本研究中，設所在城市有一個冷庫儲存生鮮產品，當所有客戶均收到貨物后貨車回到冷庫。設總的接受配送的客戶數為M，客戶i 和j 之間的距離為dij，因為每兩個客戶間的配送距離不相同，所以計算配送費用時單位配送距離費用相同。設單位配送費用為P，總的配送費用為S,符號變量xij表示客戶i與客戶j之間是否存在前后配送關系。則該配送模型可以建立目標函數為：

　　-

　　約束條件(3)表示配送車輛到達每個客戶一次且只到達一次，約束條件(4)表示配送車輛到達用戶p 且必須離開用戶p，約束條件(5)保證配送車輛起、止于配送中心。

2PSO-GA-ACO冷鏈物流配送算法設計

　　2.1蟻群算法基本原理

　　蟻群算法(Ant Colony Optimization, ACO)是一種用來在圖中尋找優化路徑的機率型算法。它是DORIGO M博士于1992年提出的，其靈感來源于螞蟻在尋找食物過程中發現最佳路徑的行為。ACO是通過模擬自然界中蟻群的覓食行為而發展起來的一種智能算法。在該算法中，螞蟻在覓食過程中會在其走過的路徑上釋放生物信息素，感知到信息素的螞蟻會沿著同樣路徑同時也會釋放信息素從而強化路徑上已經存在的信息素，如此反復進行［6］，到最后就會形成一條高濃度信息素的路徑，所有螞蟻都會選擇這條路徑去覓食，這樣就形成了一條洞穴到食物的最佳路徑［7］。

　　2.2基本ACO執行步驟

　　（1）參數設定：在算法運行前，設定最大運行次數NC，算法運行計算器nc=0。初始化任意邊(i,j)的信息濃度τij(0)=c為常量，初始時刻信息濃度增量Δτkij(0)=0。設dij為客戶i和客戶j之間的距離，當i≠j時，dij=［(xi-xj)2 + (yi-yj)2］0.5，當i=j時，dij=K為常量。初始化禁忌表tabu及路線表path，將m只螞蟻隨機地放到 n 個客戶位置，同時，將每只螞蟻的禁忌表的第一個元素設置為它當前所在的客戶位置。

　　(2)啟動螞蟻：螞蟻從tabu中的第一個位置按照轉移概率pij尋找下一步要轉移到的客戶位置，則客戶i到客戶j的pkij(t)定義為［8］:

　　其中，啟發函數ηij=d-bij，allowedk={0,1,…,n}-tabuk表示螞蟻k下一步允許選擇的客戶，α與β分別為軌跡相對重要性和能見度相對重要性。

　?。?）濃度計算：根據tabu表按式(7)［9］計算每只螞蟻在每條路徑上所遺留的信息濃度增量：

　　式中，Q表示信息素強度，Lk表示螞蟻k在本次循環中所走路徑的總長度。

　?。?）濃度更新：當所有螞蟻完成一次對所有城市遍歷的循環后，用式（8）［9］對信息濃度進行一次更新。

　　其中，ρ表示信息素揮發系數，1-ρ則表示信息素殘留因子。

　?。?）終止判斷：判斷循環次數nc是否小于最大循環次數NC，如果是，則停止循環，輸出gcbest和gtbest，否則，將所有禁忌表清空，并且重復步驟(2)~步驟(5)，直到滿足停止條件為止。

　　2.3PSO-GA-ACO設計思想

　　GA與PSO算法在運算初期能夠快速逼近最優解，有效優化系統參數，但中后期運行效率低，易早熟收斂，局部尋優能力差。而ACO算法運行初期由于信息素少，計算時間長、收斂速度慢、易陷入局部最優，但是后期局部尋優能力較強。因此在本算法中將GA、PSO算法融入到ACO算法求解中，使新算法能夠盡可能避免過早陷入局部極小值，提高算法整體尋優能力。算法設計思路:(1)螞蟻群粒子化;(2)按照信息素大小進行遍歷;(3)對螞蟻得到的路徑進行遺傳交叉、變異，從而產生新解;(4)利用PSO算法對得到的新路徑根據粒子群優化算法中的局部極值和全局極值進行調整;(5)調整結束后，根據結果判定算法是否繼續。

　　2.4PSO-GA-ACO算法實現

　　為了提高ACO算法的運行效率，減少其過早陷入局部最優、易出現停滯等現象，本文將以下三步［10 12］融合到蟻群算法中，構建出基于PSO-GA-ACO算法的冷鏈物流最優配送路徑算法。

　　(1)螞蟻?；涸趐ath表中，產生2m條隨機路徑，并對這2m條路徑的長度進行排序，取其中的m條長度最短的路徑作為m只螞蟻的初始個體最優路徑pcbest，取其路徑長度為個體極值plbest。將m只螞蟻中的最小的plbest作為螞蟻群體的全局極值glbest，其路徑為全局最優路徑gcbest。

　　(2)隨機交叉：在當前螞蟻完成一次對所有客戶的遍歷后對其走過路徑進行順序交叉，選取2個隨機交叉點j1與j2，設j1<j2，將群體當前最優路徑gcbest中的第j1到第j2步之間走過的區間（j1，…，j2）作為交叉區域安排到第 k只螞蟻第i次行走路徑pathk(i)中的對應的位置，刪除路徑pathk(i)中已經在（j1，…，j2）交叉區域中出現過的客戶，這樣就得到新的路徑path1，隨后將path1再與螞蟻個體最優路徑pcbest以如上方式再次交叉得到路徑path2。

　　(3)變異更新：在交叉操作后，對路徑path2進行逆轉變異，在路徑path2中交換第p次和第q次訪問的城市，其余順序不變，從而得到新路徑path3；根據path3計算路徑長度，若新路徑長度小于交叉變異前的路徑長度則接受新值，更新path表中相應螞蟻的個體極值ptbest和位置極值pcbest，并更新全局極值gtbest和gcbest，否則拒絕。

　　將以上三個改進步驟與基本ACO執行步驟結合起來就構成了新的PSOGAACO算法，具體執行步驟為：(1)參數設定;(2)螞蟻?；唬?）啟動螞蟻；（4）隨機交叉;(5)變異更新;(6)濃度計算;(7)濃度更新;(8)終止判斷。

　　當運行到步驟（8）時，判斷是否達到最大運行次數，如果是則結束運算，否則重復步驟（3）~步驟（8），直到滿足停止條件為止。當算法最終運行結束后，所求出的解即為冷鏈物流最優配送路徑。

3仿真實驗

　　3.1參數設置

　　考慮到在實際配送中，一般一個冷庫的配送點數不會特別多，因此，在文中采用30個城市的TSP問題數據作為研究對象進行比較研究。為了驗證本文算法的有效性，將算法運行結果分別與GA、PSO與ACO算法運行結果進行比較，基本參數設置如下。

　　GA-PSO-ACO算法參數:α=1，β=5，ρ=0.95，Q=100，NcMax=200，m=30；ACO算法參數:α=1，β=5，ρ=0.95，Q=100，NcMax=200，m=30;GA算法：初始種群inn=100，交叉概率0.8，變異概率0.8，最大迭代次數gnmax=200；PSO算法： 粒子個數num=30, 最大迭代次數NcMax=200。

　　3.2實驗結果

　　采用MATLAB語言實現如表所示算法模型對30個城市的TSP問題分別運行10次，表1給出算法運行結果，從表中可以看出在算法運行200次的情況下， GA-PSO-ACO與ACO算法的運行穩定性要明顯好于PSO算法與GA算法，其中GA-PSO-ACO算法的穩定性最好，它的平均配送距離比ACO、PSO及GA算法分別減少了4.811 8 km、45.995 3 km及32.468 6 km。按照現在城市道路貨車每公里1.2元計算，則每配送一趟比其他算法給出的路徑可以分別節省5.77元、55.19元及38.96元，這樣長期配送節約的費用將是一個巨大的數字。圖1~圖4給出了4種算法某次運行結果，從結果中可以看出GA-PSO-ACO算法對配送拐點的處理好于其他算法, 因此在局部尋優方面效果明顯好于其他三種。　

4結論

　　冷鮮食品屬于易變質的食品，對冷鮮食品的配送一般要求在最短的時間、最短路徑、最低成本下完成配送?？紤]到實際配送過程的復雜性，本文主要研究冷鏈物流的最短配送路徑，鑒于ACO算法在冷鏈物流配送路徑優化中的應用，考慮到采用ACO算法進行冷鏈物流配送，但是ACO算法在路徑優化中存在易過早陷入局部最優、算法易出現停滯現象等一系列問題，因此將另外兩種智能算法GA與PSO算法引入到ACO算法的優化中，給出了基于PSO、GA和ACO融合算法的冷鏈物流配送路徑設計思想和算法運行步驟。實驗結果表明，本文的構想是可行的，可以有效提高配送路徑優化效率，提高經濟效益。

　　參考文獻

　?。?］ 王文銘,鄭薇.果蔬配送中心物流作業建模與仿真研究［J］物流工程與管理,2010,32(4):115117.

　?。?］ 鄧汝春.我國的冷鏈物流市場及其發展策略［J］.商場現代化,2008,17(2): 814．