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

王海軍

(鄂爾多斯應(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)化問(wèn)題對(duì)冷鏈物流的發(fā)展起到至關(guān)重要的作用，鑒于蟻群算法在路徑優(yōu)化問(wèn)題中的成功應(yīng)用，因此將蟻群算法應(yīng)用到冷鏈物流配送路徑優(yōu)化問(wèn)題中?？紤]到蟻群算法運(yùn)行中存在的問(wèn)題，將遺傳算法與粒子群算法引入到蟻群算法中，構(gòu)成基于PSO-GA-ACO算法的冷鏈物流配送路徑優(yōu)化算法。實(shí)驗(yàn)結(jié)果表明，這種構(gòu)想是可行的，可以有效提高算法運(yùn)行效率，縮短配送距離，提高經(jīng)濟(jì)效益。

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

0 引言

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

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

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

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

(1)

其中xij需要滿足如下幾個(gè)條件：

(2)

(3)

(4)

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

(5)

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

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

2.1 蟻群算法基本原理

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

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

j∈allowedk

(6)

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

(7)

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

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

(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è)計(jì)思想

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

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

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

(1)螞蟻粒化：在path表中，產(chǎn)生2m條隨機(jī)路徑，并對(duì)這2m條路徑的長(zhǎng)度進(jìn)行排序，取其中的m條長(zhǎng)度最短的路徑作為m只螞蟻的初始個(gè)體最優(yōu)路徑pcbest，取其路徑長(zhǎng)度為個(gè)體極值plbest。將m只螞蟻中的最小的plbest作為螞蟻群體的全局極值glbest，其路徑為全局最優(yōu)路徑gcbest。

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

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

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

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

3 仿真實(shí)驗(yàn)

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

考慮到在實(shí)際配送中，一般一個(gè)冷庫(kù)的配送點(diǎn)數(shù)不會(huì)特別多，因此，在文中采用30個(gè)城市的TSP問(wèn)題數(shù)據(jù)作為研究對(duì)象進(jìn)行比較研究。為了驗(yàn)證本文算法的有效性，將算法運(yùn)行結(jié)果分別與GA、PSO與ACO算法運(yùn)行結(jié)果進(jìn)行比較，基本參數(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算法： 粒子個(gè)數(shù)num=30, 最大迭代次數(shù)NcMax=200。

3.2 實(shí)驗(yàn)結(jié)果

采用MATLAB語(yǔ)言實(shí)現(xiàn)如表所示算法模型對(duì)30個(gè)城市的TSP問(wèn)題分別運(yùn)行10次，表1給出算法運(yùn)行結(jié)果，從表中可以看出在算法運(yùn)行200次的情況下， GA-PSO-ACO與ACO算法的運(yùn)行穩(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元計(jì)算，則每配送一趟比其他算法給出的路徑可以分別節(jié)省5.77元、55.19元及38.96元，這樣長(zhǎng)期配送節(jié)約的費(fèi)用將是一個(gè)巨大的數(shù)字。圖1～圖4給出了4種算法某次運(yùn)行結(jié)果，從結(jié)果中可以看出GA-PSO-ACO算法對(duì)配送拐點(diǎn)的處理好于其他算法, 因此在局部尋優(yōu)方面效果明顯好于其他三種。

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

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

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

圖3 基于PSO算法配送路徑

圖4 基于GA算法配送路徑

4 結(jié)論

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

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

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

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

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

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

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

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

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

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

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

[12] 徐江樂(lè),肖志濤,趙京華.基于遺傳算法的改進(jìn)智能優(yōu)化蟻群算法[J].微電子學(xué)與計(jì)算機(jī),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é)研究項(xiàng)目(NJZY16382)

TP301.6, TP15

A

10.19358/j.issn.1674- 7720.2016.24.026

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

2016-07-25)

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