基于混合蟻群算法的物流配送路徑優化研究

王慕抽 （溫州大學，浙江 溫州 325035）

中國2001年4月頒布的《物流術語》國家標準定義：物流是“物品從供應地向接收地的實體流動過程。根據實際需要，將運輸、存儲、搬運、包裝、流通加工、配送、信息處理等基本功能實施有機結合”。配送是現代化物流系統的重要環節，配送路徑選擇是物流配送中最關鍵的問題，它的合理與否關乎配送速度、服務質量、配送成本等。

美國J.Holland教授及團隊在1970年代建立發展了遺傳算法，它是通過潛在解種群進行搜索，采用概率轉移來選擇個體，創造新后代，適合數值求解有些帶有多數、多變量的NP難題，但過早收斂和搜索效率低等問題。根據蟻群覓食的群體行為，意大利學者Dorigo M等于1991年在法國巴黎召開的第一屆歐洲人工生命會議上最早提出了蟻群算法的基本模型；1992年Dorigo M在其博士學位論文中進一步闡述了蟻群算法的核心思想。由于具有較強的群體搜索能力，蟻群算法被運用于求解各種組合優化問題。但研究結果表明在計算過程中有時會陷入局部最小，使整個系統呈現出早熟現象。于是我們構造了遺傳算法和蟻群算法相結合的混合蟻群算法為求解物流配送路徑優化問題提供了有效的工具。

1 蟻群算法原理和模型

1.1 蟻群算法原理

螞蟻尋覓食物的過程中，從螞蟻巢窩啟程尋覓食物源，剛開始的時候其路徑選擇是隨機的，但后來路徑選擇會隨著尋覓食物過程的繼續而適應性地搜索新的路徑。原因主要是螞蟻在運動過程中，在途徑的路徑上釋放信息素的物質，路徑上的信息量隨著時間流逝而逐漸消減，信息素物質與路徑長度有關，路徑越短分泌的信息素越大；如若某一條路徑上經過螞蟻越多，其留下的信息素濃度越強，信息素濃度越強就會吸引更多的螞蟻從此路徑過，這樣形成正反饋效應。如此螞蟻在尋覓食物的過程中就形成一個較優的尋覓食物路徑。受螞蟻尋覓食物路徑發現行為的啟發，1992年Marco Dorigo在其博士論文中闡述了蟻群算法，并且對其數學模型做了分析、解釋。

1.2 蟻群算法模型

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

各個顧客點需求量和位置及各車輛的裝載量已知，按要求用多個車輛對多個顧客需求進行配給貨物，尋求好的配送方案，使得總代價最小即我們說的物流配送路徑優化。它需要滿足：物流配送中心車型、位置唯一且已經；每輛車出發點和任務終止點都是配送中心；每條配送路徑上各需求點的總需求量不得超過該車輛的載重量；每條配送路徑的長度不得超過配送車輛一次配送的最大行駛距離；每個需求點需求被滿足且只能由一輛車送貨。

假設有n個客戶需配送中心送貨，每個客戶需求貨物量是gi，每輛車載重量為q，數學模型為：

上述模型，m代表所需車輛數；Cij為從點i到點j的運輸成本，它包括距離、時間、費用等，可以根據情況，并同時考慮車輛數及運行費用，式（1）是目標函數；式（2）是汽車容量約束；式（3）確保每客戶的運輸任務由僅有一輛車完成；式（4）和式（5）為到達和離開某一客戶的車僅為一輛。

3 物流配送路徑優化問題的混合蟻群算法

混合蟻群算法主要思想是將蟻群算法和遺傳算法結合起來。因為蟻群算法和遺傳算法具有很多類似的特性，蟻群算法和遺傳算法都是模擬生物進化的方法，蟻群算法是利用群體智能來搜尋最優解，而遺傳算法是利用種群進化來搜尋最優解。蟻群算法具有正反饋和建設性的“貪婪”啟發式特性，而遺傳算法具有全局收斂性。

物流配送路徑中選擇混合蟻群算法，省去了蟻群算法一開始尋找最優解的過程，而且遺傳算法尋找較優解的速度快，這兩種算法的融合，在時間效率上得到了提高。

（1） 初始化參數t=0、NC=0、WK=0、m、q等

fori=1tocustomsdo//customs為客戶數量

（2） fork=1tomdo//m為螞蟻的數量

{if滿足約束條件

選擇下一個客戶；更新tabuk表和車輛載重量。

else返回配送中心。}

fork=1tomdo

計算lengthk；

//lengthk為第k只螞蟻的尋優路徑長度

尋找階段最優解。

（3）對階段最優解實施變異操作

用線路改進算法優化階段最優解的子路徑；

評價并更新階段最優解。

do {更新路徑上信息素}；

對τij設置相對應的上界及下界。

（5） NC=NC+1

動態調整信息素的揮發因子ρ；

評價并更新當前最優解。

（6） if NC＞nc

算法結束，輸出最優路徑及路徑長度；

否則轉Step2。

4 實例仿真

根據物流配送路徑優化問題的混合蟻群算法，本人利用Matlab2012進行編程，計算實例結果進行分析比較。

實例：某配送中心有載容量8t的2輛配送車，各客戶的需求量為（單位為t），各客戶與配送中心距離如表1所示：

表1 距離與需求量表

運用本文提供的混合蟻群算法對其問題求解，參數設置α＝2，β＝4，ρ＝0.85。利用編程工具Matlab2012獲得的物流路徑為：0→4→7→6→0,0→1→3→5→8→2→0，隨機求解8次，得到結果如表2所示。

表2 混合蟻群算法的計算結果

利用蟻群算法得運輸總距離為159km，線路為0→6→5→7→3→0，0→4→8→2→1→0；遺傳算法可得總運輸距離143km；然而從表2可得其運輸總距離為135km，可見利用混合蟻群算法求得的距離較優，此方案滿足所規定的約束條件，是所陳述的車輛路徑問題的可行解。

5 結束語

本文用混合蟻群算法完成了物流配送車輛路徑問題方面的求解。本課題的研究對物流配送路徑具有優化作用，節約物流運送成本，提升企業競爭力。從仿真實例來看，該算法的優化質量和效率都優于遺傳算法和蟻群算法，增強尋優能力，提高了運算速度，避免算法造成停滯現象，具有較好搜尋全局最優解的能力。

[1] 郎茂祥.用單親遺傳算法求解配送車輛調度問題的研究[J].交通與計算機，2006(1):119-121.

[2] 于文莉.基于混合蟻群算法的物流配送路徑優化問題的研究[J].商場現代化，2007(10):137-138.

[3] 陳衛東，王佳.基于混合蟻群算法的物流配送路徑優化[J].計算機工程與設計，2009(14):3383-3385.

[4] 李卓君.混合蟻群算法求解物流配送路徑問題[J].武漢理工大學學報（交通科學與工程版），2006(2):306-309.

[5] 雷德明，吳智銘.基于粒子群優化的多目標作業車間調度[J].上海交通大學學報，2007,41(11):1796-1800.

[6] 張瀟，王江晴.混合蟻群算法在車輛路徑問題中的應用[J].計算機工程，2011(12):190-192.

[7] Colorni A.,Dorigo M.,Maniezzo V.,et al.Distributed optimization by ant colonies[C]//Proceedings of the 1st European Conference on Artificial Life,Paris,1991:134-142.

[8] Dorigo M..Optimization learning and natural algorithms[D].Department of Electronics,Politecnico Dimilano,Italy,1992.