基于混合蟻群算法的物流配送路徑優(yōu)化研究

王慕抽 （溫州大學(xué)，浙江 溫州 325035）

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

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

1 蟻群算法原理和模型

1.1 蟻群算法原理

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

1.2 蟻群算法模型

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

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

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

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

3 物流配送路徑優(yōu)化問題的混合蟻群算法

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

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

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

fori=1tocustomsdo//customs為客戶數(shù)量

（2） fork=1tomdo//m為螞蟻的數(shù)量

{if滿足約束條件

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

else返回配送中心。}

fork=1tomdo

計算lengthk；

//lengthk為第k只螞蟻的尋優(yōu)路徑長度

尋找階段最優(yōu)解。

（3）對階段最優(yōu)解實施變異操作

用線路改進算法優(yōu)化階段最優(yōu)解的子路徑；

評價并更新階段最優(yōu)解。

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

對τij設(shè)置相對應(yīng)的上界及下界。

（5） NC=NC+1

動態(tài)調(diào)整信息素的揮發(fā)因子ρ；

評價并更新當前最優(yōu)解。

（6） if NC＞nc

算法結(jié)束，輸出最優(yōu)路徑及路徑長度；

否則轉(zhuǎn)Step2。

4 實例仿真

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

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

表1 距離與需求量表

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

表2 混合蟻群算法的計算結(jié)果

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

5 結(jié)束語

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

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

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

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

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

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

[6] 張瀟，王江晴.混合蟻群算法在車輛路徑問題中的應(yīng)用[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.