李文彬,王楊東,宋 亮

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

引言

物流配送中心是現(xiàn)代物流系統(tǒng)成本控制中的又一重要環(huán)節(jié),合理的配送中心能夠減少貨物的運(yùn)輸成本,降低運(yùn)營成本,促進(jìn)生產(chǎn)和消費(fèi)的協(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ī)模的實(shí)際問題求解還是很困難.

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

1 蟻群算法基本原理

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

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

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

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

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

當(dāng)螞蟻從A走到B,便得到一個(gè)解,接下來更新螞蟻?zhàn)哌^的路徑上的信息素:

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

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

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

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

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

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

那么此時(shí)費(fèi)用為:

假設(shè)配送點(diǎn)到配送點(diǎn)運(yùn)費(fèi)為1,工廠到配送中心運(yùn)費(fèi)為0.5.

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

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

3.1 算法思路

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

3.2 算法流程

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

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

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

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

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

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

Step6 更新信息素,

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

4 算法仿真

根據(jù)上述算法描述設(shè)計(jì)實(shí)驗(yàn).

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

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

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

圖1 實(shí)驗(yàn)一結(jié)果

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

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

仿真結(jié)果如圖2所示,此時(shí)因?yàn)榕渌椭行牡慕ㄔO(shè)成本增加,配送中心由實(shí)驗(yàn)一中的兩個(gè),縮減為了一個(gè),配送中心只剩下3,其余的都是配送點(diǎn).顯然,實(shí)驗(yàn)結(jié)果和實(shí)際情況很吻合.

圖2 實(shí)驗(yàn)二結(jié)果

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

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

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

圖3 實(shí)驗(yàn)三結(jié)果

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

5 結(jié)論

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

[1] 周根貴,沈雁飛.基于時(shí)間滿意度的物流配送中心選址問題研究[J].浙江工業(yè)大學(xué)學(xué)報(bào),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é)報(bào)(自然科學(xué)版),2009,30(5)

[4] 吳 堅(jiān),史忠科.基于遺傳算法的配送中心選址問題[J].華南理工大學(xué)學(xué)報(bào)(自然科學(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é)報(bào)(自然科學(xué)版),2009,39 (2)