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

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

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

1 蟻群算法原理和模型

1.1 蟻群算法原理

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

1.2 蟻群算法模型

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

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

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

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

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

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

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

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

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

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

{if滿足約束條件

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

else返回配送中心。}

fork=1tomdo

計(jì)算lengthk；

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

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

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

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

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

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

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

（5） NC=NC+1

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

評價(jià)并更新當(dāng)前最優(yōu)解。

（6） if NC＞nc

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

否則轉(zhuǎn)Step2。

4 實(shí)例仿真

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

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

表1 距離與需求量表

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

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

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

5 結(jié)束語

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

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

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

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

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

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

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