基于參數(shù)動(dòng)態(tài)調(diào)整策略的蟻群算法優(yōu)化及應(yīng)用研究

王兵+劉佩+周亦鵬

摘 要：物流配送路徑問(wèn)題已成為現(xiàn)在關(guān)注的熱點(diǎn)，尋找一種有效全局優(yōu)化的算法對(duì)研究該問(wèn)題起著至關(guān)重要的作用。本文提出了一種改進(jìn)的蟻群算法，通過(guò)適當(dāng)調(diào)整相關(guān)參數(shù)和信息素規(guī)則，試圖提高算法的運(yùn)算性能。并結(jié)合Matlab7.0編寫(xiě)程序進(jìn)行仿真，基于實(shí)驗(yàn)結(jié)果驗(yàn)證了改進(jìn)后的蟻群算法的高效性，為研究物流配送路徑算法提供了一種新思路。

關(guān)鍵詞：配送路徑；蟻群算法；信息素

中圖分類號(hào)：TP301 文獻(xiàn)識(shí)別碼：A

蟻群算法是20世紀(jì)末意大利學(xué)者Dorigo提出的一種仿生計(jì)算方法。在解決路徑優(yōu)化問(wèn)題上具有很好的適用性，特別是解決TSP問(wèn)題和路徑分配問(wèn)題。但如何能提高收斂速度和全局搜索能力原則，一直是研究的重點(diǎn)。本文提出一種改進(jìn)的蟻群算法優(yōu)化方法，通過(guò)適當(dāng)調(diào)整相關(guān)參數(shù)和信息素規(guī)則，以求在物流配送路徑選擇方面獲得更好的效果。

1.物流配送路徑數(shù)學(xué)模型

已知一個(gè)物流中心有k輛車，車載量是qk，要完成N個(gè)目客戶點(diǎn)的配送任務(wù)?？蛻酎c(diǎn)為i，該點(diǎn)需求量為gi，maxgi≤maxqk，求符合要求的車輛最短路徑。設(shè)客戶點(diǎn)i到j(luò)總運(yùn)輸成本cij、車輛一次運(yùn)送成本c0、車輛路程c1、其他成本c2，p1p2為行駛路程和額外成本費(fèi)用系數(shù)。xxjk，yki取0或1分別代表k車從點(diǎn)i到點(diǎn)j，客戶i需求由k車完成，否則均為0配送中心等待。數(shù)學(xué)模型如下：

2.蟻群算法及其改進(jìn)

2.1 蟻群算法

其中，Q表示信息素強(qiáng)度，即：某只螞蟻在走過(guò)所有的城市后，留在線路上的信息量的總和，該值通常取為正常數(shù)即可。Lk描述的是在該次迭代過(guò)程中，螞蟻k路過(guò)的線路的總距離。

2.2 基于參數(shù)動(dòng)態(tài)調(diào)整策略的蟻群算法優(yōu)化

蟻群算法在求解配送問(wèn)題時(shí)，需要提高收斂速度的同時(shí)也要保證全局搜索能力。本文提出一種算法參數(shù)的動(dòng)態(tài)調(diào)整策略來(lái)實(shí)現(xiàn)算法的優(yōu)化。影響蟻群算法的計(jì)算效率和效果的參數(shù)包括：信息啟發(fā)因子α、期望值啟發(fā)因子β、信息素殘留系數(shù)ρ和信息素強(qiáng)度Q等。根據(jù)以上影響因素，因?yàn)棣僚cβ兩個(gè)因子具有相似的特性，本文的α，β值采用隨循環(huán)次數(shù)的增大而逐漸變小的策略來(lái)使算法的性能得到增強(qiáng)。將α值取大一點(diǎn)，隨后逐漸降低α值。方法如下：

根據(jù)實(shí)驗(yàn)結(jié)果，平均最優(yōu)費(fèi)用為6573，平均迭代次數(shù)為46。而文獻(xiàn)[2]中研究的最好結(jié)果是平均最優(yōu)費(fèi)用為7258，平均迭代次數(shù)為56。因此，本文算法參數(shù)動(dòng)態(tài)調(diào)整策略和信息素更新策略，能夠在物流配送路徑優(yōu)化問(wèn)題上獲得更好的性能優(yōu)化效果。

結(jié)論

面向物流配送路徑問(wèn)題，建立了配送路徑選擇的數(shù)學(xué)模型，并分析了影響蟻群算法計(jì)算效率的因素。針對(duì)蟻群算法的性能優(yōu)化問(wèn)題，對(duì)蟻群算法進(jìn)行改進(jìn)，并引用物流實(shí)例數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)表明本文提出的動(dòng)態(tài)調(diào)整算法參數(shù)的策略和信息素更新策略較為明顯地提高了算法的性能，從而為蟻群算法，解決物流配送路徑問(wèn)題提供幫助。

參考文獻(xiàn)

[1]林博.改進(jìn)遺傳算法在物流配送中的應(yīng)用研究[D].遼寧科技大學(xué)，2016.

[2]張欣鈺.半開(kāi)放式多配送中心車輛路徑優(yōu)化問(wèn)題研究[D].大連：大連海事大學(xué)，2014.

[3]石華瑀.改進(jìn)的蟻群算法在實(shí)際VRP中的應(yīng)用研究[D].山東大學(xué)，2012.

[4]王進(jìn).蟻群算法在物流系統(tǒng)中的應(yīng)用研究[D].南昌大學(xué)，2008.

[5]沈彬.改進(jìn)蟻群算法在物流配送中的應(yīng)用研究[D].浙江大學(xué)，2004.