王海軍

　　(鄂爾多斯應(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ì)效益。

　　關(guān)鍵詞：蟻群算法；遺傳算法；粒子群算法；物流；路徑優(yōu)化

　　中圖分類號(hào)：TP301.6, TP15文獻(xiàn)標(biāo)識(shí)碼：ADOI： 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.

0引言

　　隨著經(jīng)濟(jì)的發(fā)展，現(xiàn)代物流觀念不僅在工業(yè)、商業(yè)、制造業(yè)有了成功的應(yīng)用，而且開(kāi)始逐步深入應(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ù)為：

　　-

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

2PSO-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í)行步驟

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

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

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

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

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

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

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

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

　　2.3PSO-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.4PSO-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<j2，將群體當(dāng)前最優(yōu)路徑gcbest中的第j1到第j2步之間走過(guò)的區(qū)間（j1，…，j2）作為交叉區(qū)域安排到第 k只螞蟻第i次行走路徑pathk(i)中的對(duì)應(yīng)的位置，刪除路徑pathk(i)中已經(jīng)在（j1，…，j2）交叉區(qū)域中出現(xiàn)過(guò)的客戶，這樣就得到新的路徑path1，隨后將path1再與螞蟻個(gè)體最優(yōu)路徑pcbest以如上方式再次交叉得到路徑path2。

　　(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)方面效果明顯好于其他三種。　

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ì)效益。

　　參考文獻(xiàn)

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

　　［2］ 鄧汝春.我國(guó)的冷鏈物流市場(chǎng)及其發(fā)展策略［J］.商場(chǎng)現(xiàn)代化,2008,17(2): 814．