基于改進(jìn)蟻群算法的物流配送路徑優(yōu)化研究

夏鵬+張瑋

摘要：本文首先通過(guò)對(duì)傳統(tǒng)蟻群算法在物流配送路徑優(yōu)化問(wèn)題中的研究，得出蟻群算法存在如收斂速度較慢、算法易陷于局部最優(yōu)等缺點(diǎn)，進(jìn)而對(duì)蟻群算法進(jìn)行優(yōu)化改進(jìn)，使物流配送路徑優(yōu)化研究得到更好的解決。

關(guān)鍵詞：蟻群算法 物流配送路徑 優(yōu)化

一、引言

互聯(lián)網(wǎng)在不斷地發(fā)展，這一時(shí)代慢慢興起，網(wǎng)購(gòu)逐漸走進(jìn)我們的生活大當(dāng)中。伴隨著網(wǎng)購(gòu)而不斷興盛的就是物流行業(yè)。物流行業(yè)越來(lái)越繁榮，對(duì)物流配送路徑進(jìn)行優(yōu)化也顯得尤為重要，因?yàn)檫@直接關(guān)系到物流行業(yè)的成本控制、盈利水平及配送效率。調(diào)查顯示，目前在我們國(guó)家物流行業(yè)的總成本一半以上花費(fèi)在運(yùn)輸當(dāng)中，這一項(xiàng)花費(fèi)遠(yuǎn)遠(yuǎn)高于西方的一些發(fā)達(dá)國(guó)家。

在研究物流配送路徑的時(shí)候，我們常將其歸屬于組合優(yōu)化，即是一個(gè)NP完全問(wèn)題。研究過(guò)程中，針對(duì)路徑優(yōu)化人們經(jīng)常會(huì)用到諸如方案評(píng)價(jià)法、動(dòng)態(tài)規(guī)劃法、遺傳算法等各類方法。不過(guò)就目前的一些研究而言，這些算法都存在著一定程度的缺點(diǎn)，并不是特別完美，比如遺傳算法局部搜索能力不強(qiáng)，蟻群算法容易呈現(xiàn)停滯征象，等等?，F(xiàn)在的研究中，針對(duì)以往在物流配送路徑優(yōu)化方面的一些算法進(jìn)行改進(jìn)完善，以便于原有算法的所存在的缺點(diǎn)和不足之處能夠得到彌補(bǔ)。

近些年來(lái)，受到生物進(jìn)化展現(xiàn)出來(lái)的先進(jìn)特點(diǎn)的啟發(fā)，部分學(xué)者研究發(fā)現(xiàn)了一些像遺傳算法、蟻群算法等的智能算法，并常常將這些算法運(yùn)用到一些復(fù)雜優(yōu)化問(wèn)題中去。在進(jìn)行物流配送路徑問(wèn)題研究的時(shí)候，遺傳算法具有收斂到全局最優(yōu)的優(yōu)點(diǎn)，不過(guò)在描述所求問(wèn)題的約束條件時(shí)，這一算法往往表現(xiàn)的不盡如人意，而物流配送路徑優(yōu)化又是一種多約束問(wèn)題。和遺傳算法一樣，蟻群算法也是一種隨機(jī)搜索算法，不過(guò)蟻群算法有其自身的優(yōu)點(diǎn)，比如其能同時(shí)兼顧解的局部構(gòu)造和整體性能， 適合用來(lái)求解具有復(fù)雜約束條件以及解的組成元素之間關(guān)聯(lián)性較強(qiáng)的優(yōu)化問(wèn)題。

二、蟻群算法與物流配送路徑問(wèn)題

2.1 蟻群算法描述

蟻群算法（ant colony optimization， ACO）是由意大利的著名學(xué)者M(jìn)arco Dorigo最先提出來(lái)的，它是一種隨機(jī)搜索算法。這種算法是受到螞蟻群體在尋找食物時(shí)探索路徑行為的啟發(fā)，它是對(duì)日常螞蟻群體進(jìn)行較優(yōu)路徑搜尋這一過(guò)程的模擬，蟻群中的每一只螞蟻分別獨(dú)自地在候選解空間中去搜索一個(gè)解，螞蟻會(huì)在每次搜索完成之后留下一些信息量在相應(yīng)的解上面在。根據(jù)所選擇的解的性能的差異，螞蟻會(huì)有選擇的留下信息量，當(dāng)解的性能較好的時(shí)候，螞蟻會(huì)留下較多的信息量，反之留下的信息量則會(huì)比較少，其中留下較多信息量的解也相應(yīng)的更加容易被再次選擇。在剛開(kāi)始執(zhí)行算法的時(shí)候，每個(gè)解上面的信息量都是相同的，當(dāng)算法不斷地往前推進(jìn)，就相當(dāng)于螞蟻不斷地尋找路徑，較優(yōu)解上面留下來(lái)的信息量就會(huì)漸漸變多，這樣不同解上的信息量就逐漸被拉開(kāi)，進(jìn)而收斂得到最優(yōu)解或者近似的最優(yōu)解。

在解決物流配送路徑優(yōu)化問(wèn)題上，蟻群算法憑借其自身的優(yōu)點(diǎn)表現(xiàn)出極其強(qiáng)大的作用。不過(guò)這種算法仍然在一定程度上存在著一些不足之處，例如收斂速度較慢、算法易陷于局部最優(yōu)、各個(gè)參數(shù)的設(shè)置還建立在實(shí)驗(yàn)和經(jīng)驗(yàn)的基礎(chǔ)上、理論支持不是特別的嚴(yán)謹(jǐn)?shù)取?/p>

與神經(jīng)網(wǎng)絡(luò)、遺傳算法等一些其他的優(yōu)化算法相比，蟻群算法的優(yōu)點(diǎn)體現(xiàn)在它具有正反饋、分布式計(jì)算、較強(qiáng)的魯棒性以及富于建設(shè)性的貪婪啟發(fā)式搜索等特點(diǎn)。蟻群算法的這些不同于其他算法的特點(diǎn)，使得一些更加復(fù)雜的問(wèn)題在求解方面難度有所降低。

2.2 物流配送路徑問(wèn)題描述

2.2.1 問(wèn)題描述

針對(duì)物流配送問(wèn)題，我們一般可以進(jìn)行如下描述：為滿足某一配送目標(biāo)，從物流配送中心發(fā)出若干車輛，選擇一條比較合適的的運(yùn)輸路線，在滿足送貨量、時(shí)間窗、車輛數(shù)量、載重量、行駛里程等條件下，完成配送目標(biāo)，要求對(duì)形式路線作出合理安排，使運(yùn)輸總成本最小，并且還需要滿足下列各項(xiàng)約束條件：

（1）當(dāng)配送中心為完成一次配送任務(wù)后從該中心發(fā)出一輛運(yùn)輸車輛，運(yùn)輸車輛在完成配送中心布置的任務(wù)之后重新返回到配送中心；

（2）各條線路上的運(yùn)輸車輛的最大運(yùn)輸量應(yīng)該大于或等于該路徑上面各站點(diǎn)的一次配送需求量；

（3）每條配送路徑的長(zhǎng)度需控制在運(yùn)輸車輛單次配送的最大行駛距離以內(nèi)；

（4）有且僅能有一輛運(yùn)輸車給每一位客戶送貨。

2.2.2 數(shù)學(xué)模型

在建立蟻群算法數(shù)學(xué)模型之初，我們要考慮設(shè)計(jì)出一條最優(yōu)的配送路線，該線路要滿足總的配送距離最短。現(xiàn)作出如下假設(shè)：某一區(qū)域有一個(gè)配送中心，該配送中心服務(wù)N個(gè)目標(biāo)客戶，每個(gè)目標(biāo)客戶的需求量為，從配送中心發(fā)出的運(yùn)輸車輛的最大運(yùn)輸量為G，定義二值函數(shù)如下：

根據(jù)假設(shè)作出如下數(shù)學(xué)模型：

（1）

（2）

2.3 蟻群算法在配送路徑問(wèn)題中的應(yīng)用描述

根據(jù)以上建立起來(lái)的蟻群算法，我們用車輛去替代螞蟻，從配送中心發(fā)出一輛車，為配送區(qū)域中的一個(gè)配送節(jié)點(diǎn)配送貨物，如果從配送中心發(fā)出的車輛的貨運(yùn)量能夠達(dá)到需配送的配送節(jié)點(diǎn)的需求量，就對(duì)貨物進(jìn)行配送，如否則返回配送中心重新裝貨，表示完成一次配送。從配送中心發(fā)出的一輛運(yùn)輸車輛在一個(gè)配送過(guò)程中完成了相應(yīng)的配送任務(wù)之后，對(duì)每一條配送路徑上的信息素進(jìn)行更新。一趟任務(wù)接著一趟任務(wù)去完成，當(dāng)每一輛從配送中心發(fā)出的車輛完成了各目標(biāo)客戶的配送任務(wù)之后，表示一次迭代成功的完成了，比較其便利的路徑長(zhǎng)度并保存最短路徑，然后進(jìn)行下一次迭代。

三、蟻群算法的改進(jìn)與優(yōu)化

3.1 改進(jìn)算法數(shù)學(xué)模型

在2.2節(jié)建立的數(shù)學(xué)模型的基礎(chǔ)上，結(jié)合實(shí)際的物流配送情況，對(duì)蟻群算法的數(shù)學(xué)模型進(jìn)行改進(jìn)與優(yōu)化。優(yōu)化之后的算法具體描述如下：

全局信息素更新規(guī)則：

基于增強(qiáng)螞蟻全局搜索能力的目的，使得收斂這一現(xiàn)象不要發(fā)生的太快，每一只螞蟻在相同的一條路徑上通過(guò)的時(shí)候會(huì)留下相應(yīng)的信息素，這些信息素對(duì)其他螞蟻訪問(wèn)該路徑有抑制作用。所以可以按照下述規(guī)則對(duì)t時(shí)刻在路徑（i，j） 上的信息素進(jìn)行相應(yīng)調(diào)整：

在（6）式中，我們用ρ表示信息素的持久化系數(shù)，其取值范圍為0到1；用 （t，n）表示螞蟻在第n次迭代后留在路徑（i，j）上的信息素增量；

∈[0，1]為一個(gè)系數(shù)； 的含義是完成一次迭代后，螞蟻

在前面n-1次迭代中在路徑（i，j）上留下的信息素增量之和；這樣

表示屬于前面迭代中螞蟻釋放信息素加權(quán)抑制因子。

式（7）中： 表示所有的螞蟻第 n 次迭代后在路徑（i，j） 上留下

的信息量的總和， 的取值采用蟻周系統(tǒng)模型，值為：

式（8）中：Lk表示的是第k只螞蟻完成一次循環(huán)過(guò)程經(jīng)歷的總的路徑長(zhǎng)度；Q表示信息素強(qiáng)度。

局部信息素更新規(guī)則：和蟻群算法相類似。在改進(jìn)的蟻群算法當(dāng)中，局部信息素更新的設(shè)置主要是為了根據(jù)路徑爬行次數(shù)與總次數(shù)的比值來(lái)對(duì)該路徑上信息素的大小進(jìn)行進(jìn)一步的控制，然后來(lái)對(duì)螞蟻選擇該路徑的概率進(jìn)行影響。所以，當(dāng)螞蟻從由區(qū)域i行駛到區(qū)域j時(shí)，

式（9）中：η表示的是前n-1次迭代所有螞蟻經(jīng)過(guò)路徑（i，j）的次數(shù)比上前 n-1迭代參與搜尋的螞蟻總數(shù)得到的數(shù)值大小，（1-ξ）反應(yīng)了路徑（i，j）的重要程度。ξ2（0<ξ2<1）是一個(gè)參數(shù)，而 路徑上信息素最初始的濃度。

3.2 改進(jìn)后的算法流程

以TSP為例，采用蟻周系統(tǒng)模型。改進(jìn)蟻群算法的主要步驟如下：

（1）對(duì)參數(shù)進(jìn)行初始化設(shè)置。在剛開(kāi)始運(yùn)行算法的時(shí)候，給每一個(gè)參數(shù)設(shè)置一個(gè)初始值：迭代的次數(shù)為NC=0，最大的迭代次數(shù)是Ncmax，螞蟻數(shù)量為m，信息素強(qiáng)度初始值為Q，最小信息素強(qiáng)度為 ，最大信息素強(qiáng)度為 和 、 的參數(shù)值；

（2）把禁忌表清空，且NC=NC+1；

（3）根據(jù)式（1）的路徑選擇概率，將螞蟻從原始位置運(yùn)輸?shù)较乱粋€(gè)城市，再對(duì)禁忌表進(jìn)行修改，在該螞蟻的禁忌表中增加該城市；

（4）如果算法中的螞蟻是在第一次迭代中，就按照步驟（3）與（4）循環(huán)執(zhí)行，如果不是，那么根據(jù)式（7）進(jìn)行局部信息素更新，一直到該算法中每一只螞蟻都生成一條路徑為止。

（5）對(duì)第 k 只螞蟻通過(guò)的總路徑LK進(jìn)行計(jì)算，當(dāng)螞蟻是第一次迭代時(shí)，根據(jù)（2）式更新全局信息素，否則螞蟻根據(jù)式（ 8） 進(jìn)行所有路徑上的全局信息素更新。

（6）當(dāng)循環(huán)次數(shù) 時(shí)，結(jié)束該循環(huán)，輸出螞蟻?zhàn)哌^(guò)的路徑，此時(shí)的路徑為最優(yōu)路徑，若不滿足 ，則轉(zhuǎn)至步驟（2）。

參考文獻(xiàn)：

[1]王訓(xùn)斌，陸慧娟，陳伍濤，張火明.改進(jìn)蟻群算法在物流配送路徑中的應(yīng)用[J].中國(guó)計(jì)量學(xué)院學(xué)報(bào)，2008，19（4）：342-346.

[2]段愛(ài)民，陳澤琳，陳海波.基于改進(jìn)蟻群算法的物流配送路徑優(yōu)化[J].計(jì)算機(jī)技術(shù)與發(fā)展，2011，21（12）：178-181.

[3]王睿.物流智能配送系統(tǒng)集成一體化探討[J].電子測(cè)試，2014，23（4）：72-74.

[4]袁亞博，劉羿，吳斌.改進(jìn)蟻群算法求解最短路徑問(wèn)題[J].計(jì)算機(jī)工程與應(yīng)用，2016，6：8-12.

[5]張建民，恰汗·合孜爾，高大利.基于改進(jìn)蟻群算法的物流配送路徑問(wèn)題研究[J].計(jì)算機(jī)工程與科學(xué)，2010，7（1）：117-119.

安徽財(cái)經(jīng)大學(xué)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃資助項(xiàng)目編號(hào)201610378141