一種基于蟻群算法的多物流配送中心選址策略

李文彬,王楊東,宋 亮

(1.湖南理工學(xué)院 信息與通信工程學(xué)院,湖南 岳陽 414006;2.湖南理工學(xué)院 復(fù)雜系統(tǒng)優(yōu)化與控制湖南省普通高等學(xué)校重點實驗室,湖南 岳陽 414006)

引言

物流配送中心是現(xiàn)代物流系統(tǒng)成本控制中的又一重要環(huán)節(jié),合理的配送中心能夠減少貨物的運輸成本,降低運營成本,促進(jìn)生產(chǎn)和消費的協(xié)調(diào)與配合,保證物流系統(tǒng)的平衡發(fā)展.鑒于配送中心及其位置的重要作用,大量科研人員對這一問題展開過研究,提出了許多選址模型和選址算法[1,3],例如重心法、數(shù)值分析法、線性規(guī)劃法以及傳統(tǒng)啟發(fā)式算法等等.但是這些算法都存在一些不足,重心法和數(shù)值分析法只能解決單一選址問題,對于多地址選擇則無能為力.線性規(guī)劃法和傳統(tǒng)啟發(fā)式算法雖然可以解決多目標(biāo)問題,但是線性規(guī)劃算法對目標(biāo)函數(shù)的“線性”要求嚴(yán)格,傳統(tǒng)啟發(fā)式算法克服了線性算法的不足,但是對于大規(guī)模的實際問題求解還是很困難.

近年來,生物學(xué)進(jìn)化理論[4]在計算機(jī)領(lǐng)域內(nèi)影響越來越大,人們受到生物學(xué)進(jìn)化機(jī)理的啟發(fā),研發(fā)出了一系列人工智能算法,如遺傳算法,蟻群算法等.這些算法通常用來解決一些較為復(fù)雜的優(yōu)化問題.本文提出一種基于蟻群覓食原理的匹配算法,將配送中心的選址過程映射成一種配送點和配送中心的匹配過程,利用蟻群系統(tǒng)中,螞蟻利用信息素尋找最優(yōu)解的機(jī)制,以物流配送總運輸成本和配送中心建造成本最低為標(biāo)準(zhǔn),結(jié)合螞蟻對于路徑選擇的行為模式來定義配送點在選擇配送中心時的轉(zhuǎn)移概率和信息素的更新方式,把配送點和配送中心的匹配,以及配送中心和工廠的匹配作為一種解,從而確定配送中心的位置、數(shù)目和規(guī)模等信息.

1 蟻群算法基本原理

蟻群算法的本質(zhì)是利用信息素作為引導(dǎo),同時又更新信息素的一個正反饋過程.由于是正反饋,因此可以使得問題的解向著全局最優(yōu)的方向不斷進(jìn)化,最終能有效的獲得相對較優(yōu)的解,解決全局最優(yōu)化的問題.下面簡單介紹一下基于路徑尋優(yōu)的蟻群算法[2].

這里以經(jīng)典的最短路徑問題來說明基于路徑尋優(yōu)的蟻群算法的基本原理.假設(shè)有 m只螞蟻,目標(biāo)是找到從A到B的最短路徑,m只螞蟻起始位置都在A上.剛開始時候,整個地圖上信息素濃度是一樣高的,設(shè) τij( t )為 t時刻路徑(i,j)上的信息素濃度.那么每只螞蟻都根據(jù)當(dāng)前位置上所能觸到的道路上的信息素按概率選擇下一步將要前往的點.其中第k只螞蟻在t時刻從i走到j(luò)的概率為

其中ηij表示螞蟻從點i選擇到j(luò)去的啟發(fā)因子,α表示信息素對當(dāng)前選擇的影響程度,β表示啟發(fā)因子對當(dāng)前選擇的影響程度,它們都是一個常數(shù),tabuk表示第k只螞蟻走過的點的列表.

設(shè)dij表示從i到j(luò)的距離,那么ηij的計算可以表示為:

如果 (i,j)的距離dij越大,那么螞蟻對走這條路的期望就越小.

當(dāng)螞蟻從A走到B,便得到一個解,接下來更新螞蟻走過的路徑上的信息素:

其中Δτij表示道路(i,j)上的信息素增量,ρ表示信息素的揮發(fā)速率,通常取值在(0,1)之間.如果某一條路徑上太長時間沒有螞蟻經(jīng)過的話,那么它上面的信息素將揮發(fā)接近于0.相反經(jīng)常有螞蟻走動的道路,信息素濃度會越來越高.

可見基于路徑尋優(yōu)的蟻群算法是利用m只螞蟻間的信息交流與相互協(xié)作,也就是說,每只螞蟻在自己行走的路上留下信息素,后來的螞蟻根據(jù)前進(jìn)道路上信息素量的多少選擇前進(jìn)方向,在經(jīng)過一個長的過程后,在較短路徑上螞蟻留下的信息素量將變得更多,最終找到最短路徑.

2 多物流配送中心模型的建立

物流系統(tǒng)中的多物流配送中心選址問題,本質(zhì)上其實是一個多目標(biāo)的最優(yōu)化問題.從現(xiàn)代物流發(fā)展的趨勢看,多物流配送中心的研究具有長遠(yuǎn)意義.因此在本文中以對多物流配送中心選址為目標(biāo),以系統(tǒng)花費最小為標(biāo)準(zhǔn),建立模型.物流配送總成本包括配送運營成本(含配送中心到配送點的運輸成本和工廠到配送中心運輸成本)和配送中心建造成本.

配送中心選址問題描述為在m個配送點中選則p個配送點作為配送中心,以合理的方案為每個配送中心指定配送點,為這m個配送點配送物品,使得在選出點建立的配送中心在滿足配送需求的前提下,成本(包括建造成本和運營成本)最低.

設(shè)第i個配送點的坐標(biāo)為( Xi,Yi),需求量為Ai,如果將它建成配送中心費用為Bi.工廠的坐標(biāo)為(Zx,Zy).假設(shè)有配送點j需要通過配送中心i來運送貨物,并設(shè) Di表示工廠到配送點i的距離、Sij表示配送點i到配送點 j的距離.

那么此時費用為:

假設(shè)配送點到配送點運費為1,工廠到配送中心運費為0.5.

多物流配送中心選址的目標(biāo)就是在這m個配送點中選出一些作為配送中心,并且為這些配送中心指定一些配送點,使得所有費用最低.

3 多物流配送中心選址算法

3.1 算法思路

算法的設(shè)計思路主要源自于基于路徑尋優(yōu)的蟻群算法和基于聚類的蟻群算法,讓每個螞蟻對每一個配送點分別進(jìn)行一次匹配,當(dāng)所有配送點都進(jìn)行完了一次匹配之后,便會得到一個解,同時,螞蟻為它的這個解留下信息素,用以引導(dǎo)后來的螞蟻.新增信息素的值為1/tatolcost,所以,越好的方案留下的信息素濃度會越大,也會吸引越來越多的螞蟻來,從而留下更多的信息素,這樣不斷的進(jìn)行正反饋,從而將最終解不斷逼近并最終確定,這和螞蟻覓食時候?qū)ふ易疃搪窂綍r的原理是一樣的:利用信息素進(jìn)行正反饋.

3.2 算法流程

Step1 維護(hù)信息素表τij,τij表示第t只螞蟻在配送點i選擇和配送點j進(jìn)行匹配時的信息素.設(shè)有M只螞蟻,初始化蟻群算法中的幾個關(guān)鍵參數(shù)α、β和ρ,本文對α、β和ρ取值分別是1.3、1.0和0.95,并初始化能見函數(shù):

其中dij表示配送點i和配送點j的距離加上將配送點j建設(shè)成配送中心的花費.請?zhí)貏e注意,還要加上花費.ηij表示i和j匹配為一對,并且將j建設(shè)成配送中心的期望程度.

Step2 設(shè)置禁忌匹配表tabuk(t),用于記錄第k只螞蟻在第t個配送點上不允許的匹配點.

Step3 螞蟻以每個配送點為起點 (i = 0,1,2,…),在允許匹配的配送點中按概率將配送點i和配送點j匹配為一對,并將配送點j建設(shè)成一個配送中心.其中概率為:

其中Ek表示第k只螞蟻的方案的總花費,若Ek為0,則為0.

Step5 若M只螞蟻都完成了一次循環(huán),則轉(zhuǎn)向步驟Step6 ,否則轉(zhuǎn)向步驟Step2 .

Step6 更新信息素,

并重新回到步驟Step1 ,直到完成了一定次數(shù)的迭代.

4 算法仿真

根據(jù)上述算法描述設(shè)計實驗.

實驗一的數(shù)據(jù)如表1所示:

表1 配送網(wǎng)絡(luò)的配送點情況

結(jié)果如圖1,很理想.事實上,我們直觀的就可以得到與實驗結(jié)果相同的答案,其中1、2、5、6為配送點,3、4為選定的配送中心.

圖1 實驗一結(jié)果

為了確定中心建設(shè)成本與中心個數(shù)的關(guān)系,我們將建設(shè)成本提高至30,進(jìn)行實驗二,實驗數(shù)據(jù)見表2:

表2 配送網(wǎng)絡(luò)的配送點情況

仿真結(jié)果如圖2所示,此時因為配送中心的建設(shè)成本增加,配送中心由實驗一中的兩個,縮減為了一個,配送中心只剩下3,其余的都是配送點.顯然,實驗結(jié)果和實際情況很吻合.

圖2 實驗二結(jié)果

為了進(jìn)一步驗證算法的正確性和靈活性,設(shè)計實驗三進(jìn)行實驗,數(shù)據(jù)見表3:

表3 配送網(wǎng)絡(luò)的配送點情況

實驗三中,設(shè)計點由原來的6個增加為10個,且每個配送點的需求量是不一致的,這是符合現(xiàn)實物流配送情況的.實驗結(jié)果表明,此時的最優(yōu)策略是,建立4個配送中心,為點4、5、8和9.結(jié)果如圖3所示,其中配送中心4個,配送中心5負(fù)責(zé)配送點3和自己,配送中心4負(fù)責(zé)配送點6和自己,配送中心8負(fù)責(zé)配送點1、10和自己,配送中心9負(fù)責(zé)配送點2、7和自己.實驗的結(jié)果符合預(yù)期.

圖3 實驗三結(jié)果

在設(shè)計的三個仿真實驗的過程中,算法規(guī)定工廠只能向配送中心運送貨物.經(jīng)過以上三個仿真實驗,可以證明算法的模型是正確的,算法不僅確定了配送中心的位置、數(shù)量,同時還將與配送中心相關(guān)的配送點信息也求出來了.該算法具有很強(qiáng)的靈活性,例如將來可能需要考慮建設(shè)中心的管理成本,那么只需要對能見函數(shù)ijη以及信息素增量做出相應(yīng)調(diào)整即可,無需改變整體算法架構(gòu),能夠適應(yīng)于現(xiàn)今多樣的物流配送模型.

5 結(jié)論

物流配送中心選址是整個物流系統(tǒng)的關(guān)鍵環(huán)節(jié),本文算法將物流配送中心的選址過程映射成一個特殊的匹配過程,以物流配送總成本最低為匹配原則,結(jié)合螞蟻的覓食原理,將蟻群算法的精華運用到物流配送中心選址問題.由于蟻群算法本身所具有的魯棒性和較高的計算效率,適合進(jìn)行并行計算,對于解決大規(guī)模、復(fù)雜的物流配送網(wǎng)絡(luò)具有很大的實際價值.而且該算法具有很強(qiáng)的靈活性,只需要根據(jù)不同的物流模型修相應(yīng)的信息素更新函數(shù),就能適用于現(xiàn)今多樣的物流配送問題.

[1] 周根貴,沈雁飛.基于時間滿意度的物流配送中心選址問題研究[J].浙江工業(yè)大學(xué)學(xué)報,2008,36(4)

[2] Deneubourg JL,Gross S,Franks N.The dynamics of collective sorting robot-like ants and ant-like robots[A].Proceedings of the 1st Conference on Simulation of Adaptive Behavior[C].1990:356～363

[3] 田立新,崔曉紅,唐煥超.均差排序法在配送中心選址中的應(yīng)用[J].江蘇大學(xué)學(xué)報(自然科學(xué)版),2009,30(5)

[4] 吳 堅,史忠科.基于遺傳算法的配送中心選址問題[J].華南理工大學(xué)學(xué)報(自然科學(xué)版),2004,32(6)

[5] Arhur E.Carter,Cliff T.Ragsdale.A new approach to solving the multiple traveling salesperson problem using genetic algorithms[J].European Journal of Operational Research,2005,(167)

[6] 董 亮.物流配送中心選址問題綜述[J].科技信息,2013(7)

[7] 隋崴崴,宋現(xiàn)允,付 蕾.物流配送中心選址數(shù)學(xué)模型和算法問題研究[J].物流技術(shù),2013,32(11)

[8] 湯希峰,毛海軍,李旭宏.物流配送中心選址的多目標(biāo)優(yōu)化模型[J].東南大學(xué)學(xué)報(自然科學(xué)版),2009,39 (2)