王海軍

(鄂爾多斯應(yīng)用技術(shù)學(xué)院,內(nèi)蒙古 鄂爾多斯 017000)

PSO-GA-ACO算法在冷鏈物流配送路徑優(yōu)化中的應(yīng)用*

王海軍

(鄂爾多斯應(yīng)用技術(shù)學(xué)院,內(nèi)蒙古 鄂爾多斯 017000)

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

蟻群算法；遺傳算法；粒子群算法；物流；路徑優(yōu)化

0 引言

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

1 路徑配送模型的構(gòu)建[5]

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

S=min(∑∑(xijdij))P,i,j∈{0,1,2,…,M}

(1)

其中xij需要滿足如下幾個條件：

(2)

(3)

(4)

∑∑xij≤M+1,i,j∈{0,1,2,…,M}

(5)

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

2 PSO-GA-ACO冷鏈物流配送算法設(shè)計

2.1 蟻群算法基本原理

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

2.2 基本ACO執(zhí)行步驟

j∈allowedk

(6)

(3)濃度計算：根據(jù)tabu表按式(7)[9]計算每只螞蟻在每條路徑上所遺留的信息濃度增量：

(7)

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

(4)濃度更新：當(dāng)所有螞蟻完成一次對所有城市遍歷的循環(huán)后，用式(8)[9]對信息濃度進行一次更新。

(8)其中，ρ表示信息素?fù)]發(fā)系數(shù)，1-ρ則表示信息素殘留因子。

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

2.3 PSO-GA-ACO設(shè)計思想

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

2.4 PSO-GA-ACO算法實現(xiàn)

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

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

(2)隨機交叉：在當(dāng)前螞蟻完成一次對所有客戶的遍歷后對其走過路徑進行順序交叉，選取2個隨機交叉點j1與j2，設(shè)j1

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

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

當(dāng)運行到步驟(8)時，判斷是否達到最大運行次數(shù)，如果是則結(jié)束運算，否則重復(fù)步驟(3)～步驟(8)，直到滿足停止條件為止。當(dāng)算法最終運行結(jié)束后，所求出的解即為冷鏈物流最優(yōu)配送路徑。

3 仿真實驗

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

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

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

3.2 實驗結(jié)果

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

表1 各種算法運行結(jié)果

圖1 基于GA-PSO-ACO算法配送路徑

圖2 基于ACO算法的配送路徑

圖3 基于PSO算法配送路徑

圖4 基于GA算法配送路徑

4 結(jié)論

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

[1] 王文銘,鄭薇.果蔬配送中心物流作業(yè)建模與仿真研究[J]物流工程與管理,2010,32(4):115-117.

[2] 鄧汝春.我國的冷鏈物流市場及其發(fā)展策略[J].商場現(xiàn)代化,2008,17(2): 8-14．[3] 繆小紅,周新年,林森.第3方冷鏈物流配送路徑優(yōu)化研究[J].運籌與管理,2011,20(4):32-38.

[4] 吳天羿,許繼恒,劉建永.基于改進蟻群算法的越野路徑規(guī)劃[J].計算機應(yīng)用,2013,33(4):1157-1160.

[5] 蘇濤,王慶斌,孫聰，等.蟻群算法的軍事物流配送路徑優(yōu)化[J].海軍航空工程學(xué)院學(xué)報,2012,27(3):342-346.

[6] 林娜,劉二超.基于改進蟻群算法的無人機動態(tài)航路規(guī)劃[J].計算機測量與控制,2016,24(3):149-153.

[7] 戴天虹,李昊.基于改進蟻群算法的無線傳感器網(wǎng)絡(luò)路由的優(yōu)化[J].計算機測量與控制, 2016,24(2):321-324.

[8] 談曉勇,林鷹.基于改進遺傳蟻群算法的災(zāi)后救援路徑規(guī)劃[J].計算機工程與設(shè)計,2014,35(7):2626-2531.

[9] 劉道偉,關(guān)昕.蟻群算法在林火撲救路徑選擇中的應(yīng)用[J].計算機工程,2011,37(14):214-217.

[10] 馮興杰,岳鵬濤.基于動態(tài)優(yōu)先級的機場滑行道調(diào)度優(yōu)化算法[J].計算機工程與設(shè)計,2016,37(4):999-1003.

[11] 高尚, 張曉如.蟻群遺傳混合算法[J].數(shù)學(xué)的實踐與認(rèn)識,2009,39(24):93-98.

[12] 徐江樂,肖志濤,趙京華.基于遺傳算法的改進智能優(yōu)化蟻群算法[J].微電子學(xué)與計算機,2011,28(8):47-50.

PSO-GA-ACO algorithm used in cold chain logistics distribution route optimization

Wang Haijun

(College of Ordos Applied Technology, Ordos 017000， China)

With the rapid development of modern logistics industry, cold chain logistics industry also has developed rapidly. In cold chain logistics research, distribution routing optimization problem plays a crucial role for the development of cold logistics chain. In view of the suceessful application of ant colony algorithm in the path optimization, it applies the ant colony algorithm to cold chain logistics distribution routing problem.Taking into account the problems of ant colony algorithm when running, it introduces genetic algorithm and particle swarm algorithm into the ant colony algorithm, forming PSO-GA-ACO algorithm based cold chain logistics distribution routing optimization algorithm. The experimental results show that this idea is feasible, and can effectively improve the algorithm efficiency, shorten delivery distances, and increase economic efficiency.

ant colony algorithm; genetic algorithm; particle swarm optimization; supply chain; path optimization

內(nèi)蒙古自治區(qū)高等學(xué)?？茖W(xué)研究項目(NJZY16382)

TP301.6, TP15

A

10.19358/j.issn.1674- 7720.2016.24.026

王海軍. PSO-GA-ACO算法在冷鏈物流配送路徑優(yōu)化中的應(yīng)用[J].微型機與應(yīng)用，2016,35(24)：91-93，100.

2016-07-25)

王海軍(1982-)，通信作者，男，工學(xué)碩士，高級工程師,主要研究方向：人工智能算法應(yīng)用。E-mail:wanghaijun11249@126.com。