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

高大利

（泉州師范學院數學與計算機科學學院，福建泉州362000）

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

高大利

（泉州師范學院數學與計算機科學學院，福建泉州362000）

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

物流配送；路徑優化；蟻群算法；混沌

1 引言

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

2 物流配送路徑問題的數學模型

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

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

（2）每個客戶點的需求必須且只能由一輛車來完成；

（3）配送線路遍歷所有客戶點.

上述符號的含義是：客戶點總數L，客戶點i的貨物需求量qi，從客戶點i到客戶點j的距離di,j，車輛總數K，車輛k的最大裝載量Qk，車輛k配送的客戶總數nk，車輛k配送的客戶點集合Rk.對于中小規模物流配送路徑問題，物流成本和運輸路程相關性較強，為簡化計算，選擇運輸路程Z最短為物流配送路徑問題的優化目標.

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

3.1 基本蟻群算法模型

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

在式（5）中，α，β兩個參數分別決定了信息素量和啟發信息量的相對影響力；Pkij表示螞蟻k由配送點i轉移到配送點j的概率.當所有螞蟻都構建好路徑后，各邊上的信息素將被更新，其規則如下：

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

上述模型被稱為基本蟻群算法模型[2]；參數α，β，ρ，Q等可通過實驗方法確定其最優組合，算法停止條件可以設定固定循環次數或者當解不明顯時便停止計算.

3.2 混沌與蟻群算法的融合

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

目前對混沌尚無嚴格的定義，一般地，由確定性方程得到的具有隨機性的運動狀態稱為混沌[5].本文采用Logistic映射作為混沌序列發生器，其迭代公式如下：

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

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

在式（9）中，Xij為混沌變量，可由式（8）迭代得到；λ為調節系數；Lbest為當前迭代的最優路徑長度；各條路徑上的信息素濃度被限制在[τmin，τmax]之間，超出這個范圍的值被強制設為τmin=τmax/5或τmax=1/(ρZ)[7].

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

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

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

Step2螞蟻k從配送中心的位置出發；

Step3對螞蟻k從1到m，重復下面的步驟，直到螞蟻k走完所有的配送點：

（1）按式（5）選擇下一步允許選擇的目標配送點；

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

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

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

Step5迭代計數器NC=NC+1,如果NC

4 實驗及分析

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

表1 EIL30問題各配送點坐標及需求量數據表

經過實驗，在下列參數組合下，采用MMAS算法求解EIL30問題的較好解如表2所示：

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

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

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

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

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

現將MMAS算法、混沌蟻群算法（MMAS算法中加入混沌）這兩種算法對EIL30問題求解的具體結果進行對比，如表4所示.

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

表4 不同算法求解EIL30問題的實驗結果

5 結論

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

〔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〕李士勇.蟻群算法及其應用[M].哈爾濱:哈爾濱工業大學出版社,2004.

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

〔4〕唐巍,郭鎮明,唐嘉亨，等.復雜函數優化的混沌遺傳算法[J].哈爾濱工程大學學報,2000,21(5):1-5.

〔5〕黃潤生,黃浩.混沌及其應用[M].武漢:武漢大學出版社,2005：12.

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

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

TP18

A

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