基于蟻群算法的電子商務(wù)物流配送路徑優(yōu)化研究

王海軍 ，喬 燁

（1.內(nèi)蒙古大學(xué) 鄂爾多斯學(xué)院，內(nèi)蒙古 鄂爾多斯 017000；2.鄂爾多斯市人大，內(nèi)蒙古 鄂爾多斯 017000）

電子商務(wù)是在 Internet上基于瀏覽器/服務(wù)器（C/S）模式實現(xiàn)消費者網(wǎng)上消費的一種新型的商業(yè)運營模式。電子商務(wù)中的任何一筆交易，都包含著基本的信息流、商流、資金流和物流[1]。其中物流作為有形商品實現(xiàn)網(wǎng)絡(luò)交易的重要支持環(huán)節(jié)，對企業(yè)起著舉足輕重的作用。物流配送的效率已經(jīng)成為制約我國電子商務(wù)快速發(fā)展的一個重要瓶頸，因而如何優(yōu)化和完善物流配送線路，提高企業(yè)市場競爭力是電子商務(wù)企業(yè)成功的關(guān)鍵之所在。本文以蟻群算法為基礎(chǔ)，采用Matlab實現(xiàn)的模型來研究蟻群算法在電子商務(wù)物流配送線路優(yōu)化方面應(yīng)用的可行性，并將結(jié)果與其他算法進(jìn)行比較。

1 問題分析

電子商務(wù)企業(yè)的貨物配送路徑問題實際上就是求最小配送成本問題，但由于要考慮人力、物力等問題的模擬過于復(fù)雜，因此為了能從最簡單的方面考慮，本研究只考慮路程和運費組成的最小成本問題。由于目前運費成本是一定的，從而可轉(zhuǎn)化為求最短路徑問題。在二維空間可描述如下[2]：在配送圖 G（V，A）中，V表示所有要收貨的客戶集合，V=（v1，v2，…，vM），對 G 中的某一邊（vi，vj）， 相 應(yīng) 的有 一 個距 離 d（vi，vj），如果 G 中不存在 邊（vi，vj），則令 d（vi，vj）無窮大，實際上是這兩個客戶所在的地點之間不存在通路。因此只要能在最短通路狀態(tài)下把每個客戶都走一遍，也就達(dá)到了費用最低的效果。可將這種配送最小成本的問題轉(zhuǎn)化為求解一個相對復(fù)雜的旅行商問題（TSP）的最短路徑。物流配送的數(shù)學(xué)模型就轉(zhuǎn)變?yōu)閇3]：

其中 d（vi，vj）表示客戶 i和客戶 j之間的距離。

2 優(yōu)化模型的設(shè)計

2.1 模型設(shè)計原理

蟻群算法是對螞蟻覓食行為的模擬。現(xiàn)實螞蟻存在于三維空間中，而優(yōu)化問題位于二維平面中，因此首先將三維空間抽象為一個二維平面圖。螞蟻在連續(xù)平面運動，其運動軌跡總是離散點，計算機可以通過對離散點的處理組成連續(xù)的平面。現(xiàn)實螞蟻在覓食過程中的前進(jìn)方向主要由所處環(huán)境的信息素量來決定，在算法構(gòu)造過程中，信息素被抽象為圖的邊上的軌跡，螞蟻到達(dá)每一節(jié)點處根據(jù)邊上的信息素濃度選擇下一節(jié)點。螞蟻從初始節(jié)點（巢穴）按照一定轉(zhuǎn)移概率選擇下一節(jié)點，最終選擇行走到目標(biāo)節(jié)點（食物源），這樣便得到了TSP問題的一個可行解[4]。

2.2 模型設(shè)計步驟

（2）螞蟻啟動：螞蟻開始運行，并根據(jù)每條路徑上的信息素量及路徑的啟發(fā)信息來計算轉(zhuǎn)移概率pij。啟發(fā)函數(shù) ηij=1/dij，表示螞蟻從客戶 i轉(zhuǎn)移到客戶 j的期望程度。客戶i到客戶j的轉(zhuǎn)移概率定義為[5]：

其中，allowedk={CDT-tabuk}表示螞蟻k下一步允許選擇的城市即下一個要配送的客戶。α和β分別是螞蟻在運動過程中的信息啟發(fā)因子及期望啟發(fā)因子。

（3）信息素計算：根據(jù)禁忌表計算每只螞蟻所走的路線長度，并且記錄到目前為止所走的最短路徑，然后根據(jù)式（3）計算每只螞蟻在每條路徑上所遺留的信息素[6]。

式中，Q表示信息素強度，在一定程度上影響算法的收斂速度。Lk表示螞蟻k在本次循環(huán)中所走路徑的總長度。

（4）信息素更新：根據(jù)式（4）、（5）當(dāng)螞蟻完成一次對CityNum個城市遍歷的循環(huán)后對信息素含量進(jìn)行一次更新[7]。

其中，ρ表示信息素?fù)]發(fā)系數(shù)，1-ρ則表示信息素殘留因子。 Δτijk（t）表示第 k只螞蟻在本次循環(huán)中留在路徑（i，j）上的信息素量。

（5）終止判斷：判斷循環(huán)次數(shù)Nc是否小于最大循環(huán)次數(shù)NcMax，如果尚未到達(dá)停止條件，則將所有禁忌表清空，并且重復(fù)步驟（2）～步驟（5），直到滿足停止條件為止。

3 仿真實驗

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

本文分別采用蟻群算法、遺傳算法以及禁忌搜索算法對30個城市的TSP問題進(jìn)行比較研究。各算法的參數(shù)設(shè)置如下：

（1）蟻群算法：信息啟發(fā)因子 α=1，期望啟發(fā)因子β=5，信息素?fù)]發(fā)系數(shù) ρ=0.5，信息素強度 Q=100，最大迭代次數(shù)NcMax=200，螞蟻數(shù) m=30；

（2）遺傳算法：初始種群 inn=100，交叉概率為 0.8，變異概率為0.8，最大迭代次數(shù)gnmax=1 000；

（3）禁忌搜索算法：禁忌長度 t1=50，候選解 l1=200，終止步數(shù) stop=1 000。

3.2 結(jié)果分析

采用Matlab語言實現(xiàn)三種算法模型對30個城市的TSP問題分別運行20次，表1給出了三種算法的運行結(jié)果，從表中可以看出，蟻群算法模型的運算結(jié)果最好、最穩(wěn)定，運行時間也最短；遺傳算法模型次之，它的穩(wěn)定性和平均值要小于禁忌搜索算法；最禁忌搜索算法的最短路徑長度最短，但整體穩(wěn)定性最差。如圖1～圖6所示。

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

針對電子商務(wù)中的物流配送路徑優(yōu)化問題，將其抽象化為TSP問題，并采用蟻群算法為基礎(chǔ)建立優(yōu)化模型。隨后介紹了優(yōu)化模型的實現(xiàn)過程，通過實驗，與遺傳算法模型和禁忌搜索算法模型運行結(jié)果進(jìn)行比較，結(jié)果表明，蟻群算法模型不但運行速度快，而且運行效果最好、最穩(wěn)定，從而為電子商務(wù)中的物流配送路徑優(yōu)化提供了一種新的、可行的思路。

[1]朱立偉.現(xiàn)代化物流管理技術(shù)在電子商務(wù)中的作用[J].企業(yè)經(jīng)濟，2006（1）：20-21.

[2]溫清芳.遺傳算法求解 TSP問題的 MATLAB實現(xiàn)[J].韶關(guān)學(xué)院學(xué)報·自然科學(xué)，2007，28（6）：18-22.

[3]田貴超，黎明，韋雪潔.旅行商問題（TSP）的幾種求解方法[J].計算機仿真，2006，23（8）：153-157.

[4]高陽.基于蟻群算法的集合覆蓋問題求解及其應(yīng)用研究[D].無錫：江南大學(xué)，2007

[5]野瑩瑩，付麗君，程立英.基于 MATLAB的蟻群算法仿真研究[J].裝備制造技術(shù)，2008，（11）：13-14.

[6]熊芳敏，岑宇森，曾碧卿.運用蟻群算法解決物流中心揀貨路徑問題[J].華南師范大學(xué)學(xué)報（自然科學(xué)版），2010（2）：50-54.

[7]王軍.蟻群算法求解TSP時參數(shù)設(shè)置的研究[J].科學(xué)技術(shù)與工程，2007，7（17）：4501-4504.