基于混沌蟻群算法的物流配送路徑問題仿真研究

高大利

（泉州師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建泉州362000）

基于混沌蟻群算法的物流配送路徑問題仿真研究

高大利

（泉州師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建泉州362000）

將混沌與最大最小螞蟻算法相融合，在蟻群算法的信息素更新規(guī)則中加入混沌擾動(dòng)量避免了在搜索過程中陷入局部極值.測(cè)試結(jié)果表明混沌蟻群算法能夠有效地提高算法的全局尋優(yōu)能力，對(duì)于物流配送路徑問題的求解能夠獲得滿意的結(jié)果.

物流配送；路徑優(yōu)化；蟻群算法；混沌

1 引言

在物流配送過程中，配送線路安排的合理與否對(duì)配送速度、物流成本影響很大；由于配送線路安排涉及多個(gè)配送點(diǎn)和復(fù)雜的道路網(wǎng)絡(luò)結(jié)構(gòu)等情況，這就使物流配送路徑問題的求解更加困難.隨著人工智能技術(shù)的不斷發(fā)展，蟻群算法等新技術(shù)被用于解決路徑優(yōu)化及其他一系列組合優(yōu)化問題；針對(duì)蟻群算法求解物流配送路徑問題易陷入早熟、停滯、局部最優(yōu)的缺限.本文將混沌引入蟻群算法，通過仿真實(shí)驗(yàn)驗(yàn)證了混沌蟻群算法對(duì)于物流配送路徑問題的求解是有效的.

2 物流配送路徑問題的數(shù)學(xué)模型

物流配送路徑問題是指有L個(gè)客戶點(diǎn)，已知每個(gè)客戶點(diǎn)的需求量及位置，至多用K輛車從配送中心到達(dá)這批客戶點(diǎn)，并且在完成配送任務(wù)后，返回物流中心.每輛車載重量一定，要求安排車輛行駛線路使得總成本（如距離、時(shí)間等）為最小，且滿足以下約束條件：

（1）每條線路上的客戶點(diǎn)需求量之和不超過車輛載重量；

（2）每個(gè)客戶點(diǎn)的需求必須且只能由一輛車來完成；

（3）配送線路遍歷所有客戶點(diǎn).

上述符號(hào)的含義是：客戶點(diǎn)總數(shù)L，客戶點(diǎn)i的貨物需求量qi，從客戶點(diǎn)i到客戶點(diǎn)j的距離di,j，車輛總數(shù)K，車輛k的最大裝載量Qk，車輛k配送的客戶總數(shù)nk，車輛k配送的客戶點(diǎn)集合Rk.對(duì)于中小規(guī)模物流配送路徑問題，物流成本和運(yùn)輸路程相關(guān)性較強(qiáng)，為簡(jiǎn)化計(jì)算，選擇運(yùn)輸路程Z最短為物流配送路徑問題的優(yōu)化目標(biāo).

3 物流配送路徑問題的混沌蟻群算法

3.1 基本蟻群算法模型

20世紀(jì)90年代，Marco Dorigo等人[1]受到自然界中蟻群覓食行為的啟發(fā)，提出了一種用于求解組合優(yōu)化問題的新型仿生進(jìn)化算法——蟻群算法.使用蟻群算法求解物流配送路徑問題引入符號(hào)定義：t時(shí)刻在邊(i,j)上的信息素量τij；t時(shí)刻在邊(i,j)上的啟發(fā)信息量ηij，可取配送點(diǎn)間距離的倒數(shù)，即ηij=1/dij；allowedk表示螞蟻k下一步允許選擇的配送點(diǎn)集合；位于i配送點(diǎn)的螞蟻k選擇j配送點(diǎn)作為下一位置的概率按下式計(jì)算：

在式（5）中，α，β兩個(gè)參數(shù)分別決定了信息素量和啟發(fā)信息量的相對(duì)影響力；Pkij表示螞蟻k由配送點(diǎn)i轉(zhuǎn)移到配送點(diǎn)j的概率.當(dāng)所有螞蟻都構(gòu)建好路徑后，各邊上的信息素將被更新，其規(guī)則如下：

在式（6）中，ρ為信息素?fù)]發(fā)系數(shù)，其作用是避免信息素的無限積累，0＜ρ＜1；△τkij表示第k只螞蟻在本次循環(huán)中留在邊(i,j)的信息素量.Lk表示第k只螞蟻在本次循環(huán)中的所走的路徑長(zhǎng)度；Q為信息素強(qiáng)度.

上述模型被稱為基本蟻群算法模型[2]；參數(shù)α，β，ρ，Q等可通過實(shí)驗(yàn)方法確定其最優(yōu)組合，算法停止條件可以設(shè)定固定循環(huán)次數(shù)或者當(dāng)解不明顯時(shí)便停止計(jì)算.

3.2 混沌與蟻群算法的融合

混沌是自然界廣泛存在的一種非線性現(xiàn)象，混沌具有隨機(jī)性、遍歷性、對(duì)初始條件的敏感性，能在一定范圍內(nèi)按其自身規(guī)律不重復(fù)地遍歷所有狀態(tài)，利用混沌的這些性質(zhì)可以進(jìn)行優(yōu)化搜索[3]，并且可以將混沌同其他算法融合，如混沌遺傳算法[4]等.

目前對(duì)混沌尚無嚴(yán)格的定義，一般地，由確定性方程得到的具有隨機(jī)性的運(yùn)動(dòng)狀態(tài)稱為混沌[5].本文采用Logistic映射作為混沌序列發(fā)生器，其迭代公式如下：

式（8）中，μ為控制參數(shù)，μ∈（2，4]；Xi為混沌變量，i=0，1，2，…；盡管式（8）是確定性的，但當(dāng)μ=4并且X0埸{0，0.25，0.5，0.75，1}時(shí)，Logistic映射產(chǎn)生的序列完全呈混沌狀態(tài).

為了提高解的多樣性和蟻群算法的全局尋優(yōu)能力，在基本蟻群算法的基礎(chǔ)上，采用最大最小螞蟻系統(tǒng)[6]（MAX-MIN Ant System，MMAS）與混沌融合，具體來說就是在蟻群算法的信息素更新規(guī)則中加入混沌擾動(dòng)量，使解跳出局部極值區(qū)間，從而有效地避免搜索過程陷入局部最優(yōu).將混沌加入MMAS算法后，各邊上的信息素將按式（9）進(jìn)行更新：

在式（9）中，Xij為混沌變量，可由式（8）迭代得到；λ為調(diào)節(jié)系數(shù)；Lbest為當(dāng)前迭代的最優(yōu)路徑長(zhǎng)度；各條路徑上的信息素濃度被限制在[τmin，τmax]之間，超出這個(gè)范圍的值被強(qiáng)制設(shè)為τmin=τmax/5或τmax=1/(ρZ)[7].

3.3 物流配送路徑問題的混沌蟻群算法描述

根據(jù)混沌蟻群算法模型，使用該算法求解物流配送路徑問題的步驟如下：

Step1初始化參數(shù)α、β、ρ、λ，X0，最大迭代次數(shù)NCmax、迭代計(jì)數(shù)器NC=0等；

Step2螞蟻k從配送中心的位置出發(fā)；

Step3對(duì)螞蟻k從1到m，重復(fù)下面的步驟，直到螞蟻k走完所有的配送點(diǎn)：

（1）按式（5）選擇下一步允許選擇的目標(biāo)配送點(diǎn)；

（2）若配送點(diǎn)j滿足式（1）～（3）的約束條件，則將第k只螞蟻轉(zhuǎn)移到配送點(diǎn)j；

（3）把配送點(diǎn)j加入到已訪問過的配送點(diǎn)集合中；

Step4由式（8）生成混沌變量Xij，根據(jù)式（9）更新信息素；

Step5迭代計(jì)數(shù)器NC=NC+1,如果NC

4 實(shí)驗(yàn)及分析

由于蟻群算法中信息啟發(fā)式因子α、期望值啟發(fā)式因子β、信息素?fù)]發(fā)參數(shù)ρ等都是影響物流配送路徑問題求解的重要參數(shù)，故先通過仿真實(shí)驗(yàn)來確定MMAS算法求解物流配送路徑問題的最佳參數(shù)組合，然后再驗(yàn)證MMAS算法中加入混沌的有效性.實(shí)驗(yàn)所用的物流配送路徑問題數(shù)據(jù)來源于VRP測(cè)試庫，所有實(shí)驗(yàn)均在Visual C++6.0環(huán)境下進(jìn)行50次取最優(yōu)解，算法的最大迭代次數(shù)NCmax=1000.在不同參數(shù)組合下，采用MMAS算法對(duì)VRP測(cè)試庫中EIL30問題進(jìn)行求解；已知車輛最大載重量為4500kg，客戶數(shù)為30個(gè)，編號(hào)1對(duì)應(yīng)的位置為配送中心，各配送點(diǎn)坐標(biāo)及需求量如表1.

表1 EIL30問題各配送點(diǎn)坐標(biāo)及需求量數(shù)據(jù)表

經(jīng)過實(shí)驗(yàn)，在下列參數(shù)組合下，采用MMAS算法求解EIL30問題的較好解如表2所示：

表2 MMAS算法求解EIL30問題的較好解

由表2可知：采用MMAS算法求解EIL30問題的最佳參數(shù)組合為：α=1，β=3，ρ=0.3（配送距離為646km，配送路線數(shù)為3條）.

為驗(yàn)證MMAS算法中加入混沌的有效性，仍對(duì)VRP測(cè)試庫中的EIL30問題進(jìn)行求解.參數(shù)設(shè)置為：α=1，β=3，ρ=0.3；調(diào)節(jié)系數(shù)λ分別取1，10，100；混沌初始值X0分別取隨機(jī)生成，0.1，0.2，0.3，0.4；經(jīng)過大量實(shí)驗(yàn)，在下列參數(shù)組合下，采用混沌蟻群算法求解EIL30問題的較好解如表3所示：

表3 混沌蟻群算法求解EIL30問題的較好解

由表3可知：在以上參數(shù)組合下，采用混沌蟻群算法求解的配送距離都小于MMAS算法得出的全局最優(yōu)解（配送距離為646km，配送路線數(shù)為3）；采用混沌蟻群算法求解EIL30問題的最佳參數(shù)組合為：α=1，β=3，ρ=0.3，X0=0.1，λ=1（配送距離為622km，配送路線數(shù)為3）.

現(xiàn)將MMAS算法、混沌蟻群算法（MMAS算法中加入混沌）這兩種算法對(duì)EIL30問題求解的具體結(jié)果進(jìn)行對(duì)比，如表4所示.

由表4可知：在MMAS算法中加入混沌后，求解的配送距離小于MMAS算法得出的結(jié)果，由此說明混沌蟻群算法對(duì)物流配送路徑問題的求解是有效的.

表4 不同算法求解EIL30問題的實(shí)驗(yàn)結(jié)果

5 結(jié)論

本文利用混沌的隨機(jī)性遍歷性及規(guī)律性等特點(diǎn)，將混沌與蟻群算法融合.實(shí)驗(yàn)表明：混沌蟻群算法能夠有效提高蟻群算法的全局尋優(yōu)能力，混沌蟻群算法對(duì)于物流配送路徑問題的求解能夠獲得滿意的結(jié)果.此外，本文中MMAS算法及混沌蟻群算法的參數(shù)選擇，是在大量仿真實(shí)驗(yàn)基礎(chǔ)上得出的，這些參數(shù)組合對(duì)于其他組合優(yōu)化問題的求解具有一定的參考價(jià)值.

〔1〕DorigoM,VittorioManiezzo,AlbertoColorni.TheAnt system:optimization by a colony of cooperating agents.IEEE Transactions on systems,Man and Cybernetics,PartB,1996,26(1):29-41.

〔2〕李士勇.蟻群算法及其應(yīng)用[M].哈爾濱:哈爾濱工業(yè)大學(xué)出版社,2004.

〔3〕李兵,蔣慰孫.混沌優(yōu)化方法及其應(yīng)用[J].控制理論與應(yīng)用,1997,14(4):613-615.

〔4〕唐巍,郭鎮(zhèn)明,唐嘉亨，等.復(fù)雜函數(shù)優(yōu)化的混沌遺傳算法[J].哈爾濱工程大學(xué)學(xué)報(bào),2000,21(5):1-5.

〔5〕黃潤(rùn)生,黃浩.混沌及其應(yīng)用[M].武漢:武漢大學(xué)出版社,2005：12.

〔6〕T.Stutzle,H.Hoos.MAX-MIN Ant System.Future Generation Computer Systems,16(8):889-914,2000.

〔7〕馬良,朱剛,寧愛兵.蟻群優(yōu)化算法[M].北京:科學(xué)出版社,2008.

TP18

A

1673-260X（2011）01-0025-03