基于蟻群算法考慮路線安排的單配送中心選址

林　雄

摘要:對(duì)一類要求考慮路線安排的單配送中心選址問題建立基于蟻群算法的選址模型,模型目標(biāo)以配送中心建設(shè)費(fèi)用與運(yùn)輸費(fèi)用之和最小;同時(shí)構(gòu)造模型的蟻群算法求解結(jié)構(gòu);最后初步應(yīng)用證明了該模型解決此類問題的有效性,為單配送選址提供又一種方法。

關(guān)鍵詞:蟻群算法;配送中心;路線安排;選址

中圖分類號(hào):F224文獻(xiàn)標(biāo)識(shí)碼:A

Abstract: Builds based-on ant colony algorithm's location model for a class of single distribution center location problem with consideration of the routing. Mimizing the cost of construction of distribution center and the transportation costs are the objectives of model. Construct the model's ant colony algorithm solving structure. Finally, using an example shows the effectiveness of the model, providing another method for single distribution center location.

Key words: ant colony algorithm; distribution center; routing; location

單配送中心選址模型目前主要采用連續(xù)模型,如重心法。這類方法在解決配送中心選址問題的局限性一方面在于模型要求區(qū)域內(nèi)任意點(diǎn)都可以建設(shè)配送中心,但在實(shí)際環(huán)境中往往做不到,經(jīng)常出現(xiàn)用這種方法求出的配送中心的位置在實(shí)際中不能建設(shè),如求得的建設(shè)地點(diǎn)位于湖泊中、江河中等;另一方面,目前的單配送中心模型選址時(shí),沒有考慮配送路線的安排[1-2]?；谙伻核惴紤]路線安排的單配送中心選址模型克服了以上局限,能夠解決這樣一類配送中心選址問題:要求在選址區(qū)域內(nèi)選擇一個(gè)需求點(diǎn)來建設(shè)一個(gè)配送中心,同時(shí)需要考慮配送路線安排,目標(biāo)是使得配送總費(fèi)用最低。

1選址模型研究

1.1問題描述與分析

現(xiàn)實(shí)中有這樣一類配送中心選址問題:已知某區(qū)域及區(qū)域內(nèi)需求點(diǎn)地址集合,該區(qū)域內(nèi)各需求點(diǎn)的需求特點(diǎn)是一次需求量少,且需求穩(wěn)定,具有周期性,各需求點(diǎn)的一次需求總量也相對(duì)較小,對(duì)各需求點(diǎn)的一次需求實(shí)行一次巡回配送完成,現(xiàn)在要在各需求點(diǎn)中選出一個(gè)來擴(kuò)建成配送中心為這個(gè)區(qū)域的需求服務(wù),使得配送中心建設(shè)費(fèi)用與運(yùn)輸費(fèi)用最小。因?yàn)椴捎靡淮窝不嘏渌?巡回路線的不同對(duì)運(yùn)輸費(fèi)用影響很大,考慮到各需求點(diǎn)需求穩(wěn)定且具有周期性,一旦獲得最優(yōu)的配送巡回路線,可以重復(fù)使用,而每個(gè)備選點(diǎn)都有其最優(yōu)的運(yùn)輸費(fèi)用與建設(shè)費(fèi)用組合,基于這樣的考慮,問題的目標(biāo)就是尋找基于最優(yōu)配送路線的一次運(yùn)輸費(fèi)用與一次分?jǐn)偨ㄔO(shè)費(fèi)用之和最小的備選點(diǎn)位置。

1.2模型假設(shè)

(1)區(qū)域內(nèi)僅建設(shè)一個(gè)配送中心;

(2)配送中心建立在某個(gè)需求點(diǎn)處;

(3)只考慮一級(jí)運(yùn)輸,即只考慮從配送中心到需求地的運(yùn)輸;

(4)配送中心的容量可以滿足所有需求地的需求;

(5)各需求地的需求量為已知;

(6)運(yùn)輸費(fèi)用與運(yùn)輸距離及運(yùn)輸量成正比;

(7)系統(tǒng)總費(fèi)用只考慮配送中心的建設(shè)費(fèi)用和運(yùn)輸費(fèi)用。

1.3模型的建立

根據(jù)以上問題描述與模型假設(shè),可以得出配送中心選址的一般模型表達(dá):

minz=cdx+cdx+cdx+…+cdx+fm(1)

Subject to(2)

目標(biāo)函數(shù)(1)表示配送中心選建在需求地i時(shí)的最小總費(fèi)用,包括配送中心建設(shè)費(fèi)用與配送費(fèi)用;同時(shí)表示當(dāng)配送中心建在需求地i時(shí),最優(yōu)配送為從i出發(fā),配送路線依次經(jīng)歷需求地1,2,3,…,n,最后回到配送中心i處,模型中路線i→1→2→3→…→n→i是一個(gè)未定的路線,表示從i出發(fā)所有巡回配送路線中的任意一種;c,c,…,

c分別表示車輛經(jīng)歷分段路徑i,1,1,2,…,n,i的運(yùn)輸費(fèi)率,(單位為元·km-1·kg-1);d,d,…,d表示分段路徑i,1,1,2,…,n,i的距離;x,x,…,x分別表示車輛經(jīng)歷分段路徑i,1,1,2,…,n,i時(shí)的載重量;f表示配送中心建設(shè)在i點(diǎn)的建設(shè)費(fèi)用,m表示配送中心服務(wù)年限內(nèi),所執(zhí)行的配送次數(shù),m=tp,t表示配送中心設(shè)計(jì)服務(wù)年限,p為每年執(zhí)行配送的次數(shù),fm表示建設(shè)費(fèi)用分?jǐn)偟矫看闻渌偷馁M(fèi)用;Dj=1,2,…,n為各需求地的需求量。

2模型求解的蟻群算法

模型求解涉及巡回路線尋優(yōu),不僅要考慮各需求點(diǎn)間的距離,還要考慮各需求點(diǎn)的需求量不同,采用一般搜索方法難以解決,這里利用蟻群算法在路徑尋優(yōu)方面的優(yōu)勢(shì)設(shè)計(jì)求解模型的蟻群算法。

2.1基本的蟻群算法模型

定義如下參數(shù):

m——蟻群中螞蟻數(shù)量,d——路徑i,j的距離,η——路徑i,j的能見度,τt——t時(shí)刻路徑i,j上的信息量,△τ——螞蟻k在本次循環(huán)中留在路徑i,j上的信息量,Pt——螞蟻k在t時(shí)刻由位置i轉(zhuǎn)移到位置j的概率,α——軌跡的相對(duì)重要性α≥0,β——能見度的相對(duì)重要性β≥0,ρ——信息素的持久性0≤ρ<1,1

-ρ——信息素的衰減度。初始時(shí)刻,設(shè)所有路徑上的信息素都相等,τ0=0c是一個(gè)常數(shù)。螞蟻kk=1,2,…,n在運(yùn)動(dòng)過程中,根據(jù)各條路徑上的信息素的大小以一定的概率Pt決定轉(zhuǎn)移方向,Pt表示為[3]:

Pt=(3)

其中,allowed=0,1,…,n表示t時(shí)刻螞蟻k下一步允許選擇的點(diǎn)。在螞蟻算法中,假設(shè)人工蟻群系統(tǒng)有記憶功能,用tabukk=1,2,…,m記錄螞蟻k已經(jīng)走過的節(jié)點(diǎn)。當(dāng)一個(gè)周期結(jié)束,進(jìn)入t+1時(shí)刻,對(duì)各路徑上的信息素進(jìn)行調(diào)整,即[3]:

τt+1=ρτt+Δτt,t+1 (4)

Δτt,t+1=Δτt,t+1 (5)

其中,△τt,t+1表示第k只螞蟻在時(shí)刻t,t+1留在路徑i,j上的信息素量,其值視螞蟻表現(xiàn)的優(yōu)劣程度而定。路徑越短,信息素釋放的就越多;△τt,t+1表示本次循環(huán)中路徑i,j的信息素量的增量;1-ρ為信息素軌跡的衰減系數(shù),通常設(shè)置系數(shù)ρ<1來避免路徑上軌跡量的無限累加。根據(jù)具體算法的不同,△τ、△τ及Pt的表達(dá)形式可以不同,要根據(jù)具體問題而定。M.Dorigo曾給出三種不同模型[4]分別是蟻周系統(tǒng)(antcycle system)、蟻量系統(tǒng)(ant-quantity system),蟻密系統(tǒng)(ant-density system)[5]。

2.2基于蟻群算法的模型求解

2.2.1模型的求解步驟

模型求解思路:

當(dāng)配送中心選建在任意點(diǎn)i,如果待配送的需求點(diǎn)有n個(gè),那么可能的配送路線將有n!種,需要先從這n!種找出最小運(yùn)輸費(fèi)用的一種配送方案,當(dāng)n取值很大時(shí),同時(shí)考慮距離和各需求點(diǎn)的需求量時(shí)常規(guī)算法將無法勝任,因而,引入蟻群算法進(jìn)行路徑尋優(yōu)(這里的最優(yōu)指經(jīng)歷路線的運(yùn)輸費(fèi)用最小),得到配送中心建設(shè)在i點(diǎn)時(shí)的最優(yōu)配送路線,根據(jù)此路線計(jì)算配送中心建設(shè)在需求地i且考慮配送路線安排的最小費(fèi)用,重復(fù)計(jì)算,得到配送中心獨(dú)立建設(shè)在各個(gè)需求點(diǎn)的最小費(fèi)用,對(duì)這一系列費(fèi)用進(jìn)行排序,最小者即為選址方案。

求解步驟為:

步驟1:以任意一個(gè)需求地i為配送中心建設(shè)地,計(jì)算配送中心建設(shè)在該地點(diǎn)考慮配送路線安排的最小費(fèi)用。即假設(shè)配送中心建設(shè)在i點(diǎn),構(gòu)造蟻群搜索規(guī)則搜索以i為起點(diǎn)的配送費(fèi)用最小的配送路線,依據(jù)這一最優(yōu)配送路線,依據(jù)公式(1)計(jì)算得到配送中心建設(shè)在該點(diǎn)的最小費(fèi)用;

步驟2:重復(fù)步驟1,直到獲得配送中心獨(dú)立建設(shè)在每個(gè)需求地的最小費(fèi)用及相應(yīng)配送路線安排;

步驟3:對(duì)求得的一系列費(fèi)用進(jìn)行排序,其中費(fèi)用最小的方案即為選址解決方案,如得到的結(jié)果為:配送中心建設(shè)在需求點(diǎn)j,配送路線安排為j→x→x→x→x→…→x→j,其中,x,x,x,…,x為區(qū)域內(nèi)的需求點(diǎn)。

2.2.2模型求解蟻群算法的設(shè)計(jì)與實(shí)現(xiàn)

(1)初始化

設(shè)定時(shí)間計(jì)數(shù)器t,循環(huán)次數(shù)計(jì)數(shù)器N,螞蟻數(shù)m,初始化關(guān)鍵參數(shù)α、β、ρ、τt的設(shè)置:信息素軌跡強(qiáng)度初始值采用最大最小螞蟻系統(tǒng)(MMAS)的設(shè)置,即為經(jīng)歷兩需求地間的每段路徑i,j設(shè)置一個(gè)最大信息素軌跡強(qiáng)度的初始值τ=τ?！鳓拥脑O(shè)置:信息素軌跡增量的初始值設(shè)為0,隨后計(jì)算的增量為一常數(shù)。η的設(shè)置:這里路徑最優(yōu)不一定指配送路線最短,路線最短不一定配送成本最低,因?yàn)榕渌唾M(fèi)用還與各需求點(diǎn)的需求量有關(guān),因而兩點(diǎn)間的能見度在這里設(shè)為η=ξDd,0<ξ<1。禁忌表初始化為空集,把m只螞蟻全都置于起始點(diǎn)i,同時(shí)將螞蟻的初始位置這里即起始點(diǎn)i置于當(dāng)前禁忌表中。

(2)螞蟻開始搜索路徑,建立路徑解決方案

位于需求點(diǎn)i的螞蟻選擇下一需求點(diǎn)j的狀態(tài)轉(zhuǎn)移規(guī)則如下:

j=(6)

其中,q是在0,1區(qū)間均勻分布的隨機(jī)數(shù),q是一個(gè)參數(shù)0≤q≤1,由表達(dá)式(6)產(chǎn)生的狀態(tài)轉(zhuǎn)移規(guī)則,被稱為偽隨機(jī)比例規(guī)則[6]。參數(shù)q的大小決定了利用先驗(yàn)知識(shí)與探索新路徑之間的相對(duì)重要性:每當(dāng)一只位于需求點(diǎn)i的螞蟻選擇下一個(gè)將要到達(dá)的需求點(diǎn)j時(shí),它選取一個(gè)隨機(jī)數(shù)0≤q≤1。如果q≤q,則根據(jù)先驗(yàn)知識(shí)(根據(jù)式(6))第一式選擇最好的邊,否則按(3)概率地選擇一條邊,將剛剛選擇的需求點(diǎn)j加到tabu中。根據(jù)這種規(guī)則每只螞蟻建立各自的路徑解決方案,完成一次循環(huán)。

(3)利用最大最小螞蟻系統(tǒng)信息軌跡更新規(guī)則,對(duì)信息素軌跡進(jìn)行全局更新

當(dāng)m只螞蟻都建立完一次路徑解決方案,根據(jù)公式(1)找出尋到本次最優(yōu)路徑的螞蟻,最優(yōu)的螞蟻就是搜索到的配送路線使得配送總費(fèi)用最小的那只螞蟻,只對(duì)這只螞蟻經(jīng)歷的路徑進(jìn)行信息素更新,更新規(guī)則如下:

τt+1= (7)

其中,△τ是事先給定的一個(gè)合理常數(shù),ρ是信息素?fù)]發(fā)系數(shù),0<ρ<1。為避免搜索過早停滯,對(duì)信息素軌跡的最大值和最小值分別施加了τ和τ限制,從而使對(duì)所有信息素軌跡τ≤τt≤τ;在每次循環(huán)后,確保軌跡量遵從這一限制。若有τt>τ,則設(shè)置τt=τ;若有τt<τ,則設(shè)置τt=τ。

(4)清空禁忌表,重復(fù)(1)、(2)、(3),直至達(dá)到設(shè)置的循環(huán)次數(shù)N,得到從需求點(diǎn)i出發(fā)的最后的最優(yōu)配送路線。

(5)根據(jù)得到的最優(yōu)路線安排,依據(jù)式(1)計(jì)算配送中心建在需求點(diǎn)i的總成本z。

(6)對(duì)每個(gè)需求點(diǎn)重復(fù)(1)～(5),得到把配送中心建在各需求點(diǎn)的總費(fèi)用,z,z,…,z。

(7)對(duì)z,z,…,z進(jìn)行排序,值最小對(duì)應(yīng)的方案即為考慮路線安排的配送中心選址方案。

3初步應(yīng)用

某企業(yè)為一個(gè)區(qū)域提供機(jī)械零件的配送服務(wù),為控制費(fèi)用并能有效地提供配送服務(wù),決定在其中一個(gè)需求點(diǎn)建設(shè)一個(gè)配送中心,使得建設(shè)費(fèi)用與配送費(fèi)用最小。區(qū)域內(nèi)共有10個(gè)需求點(diǎn),各需求點(diǎn)的機(jī)械零件一次需求量較少,需求量及需求周期穩(wěn)定,每個(gè)月定期執(zhí)行4次配送,配送計(jì)劃采用一次巡回配送。各需求點(diǎn)間的距離見表1;各需求點(diǎn)的定期一次需求量見表2;在各需求點(diǎn)建設(shè)配送中心的費(fèi)用見表3。

根據(jù)式(1)建立配送中心選址模型,配送中心的設(shè)計(jì)服務(wù)年限為5年,利用上述提供的蟻群算法求解,編程計(jì)算,初始參數(shù)設(shè)置為:α=0.6;β=0.8;ρ=0.7。取運(yùn)輸費(fèi)率為0.005元·km-1·kg-1。運(yùn)算得到的最優(yōu)選址方案為,配送中心P建立在需求點(diǎn)j處,配送路線為:Pj→h→g→b→f→e→c→i→a→d→Pj。執(zhí)行一次配送的運(yùn)輸費(fèi)用為367.2元,執(zhí)行一次配送的建設(shè)費(fèi)用的分?jǐn)倿?35.4元,執(zhí)行一次配送總費(fèi)用為1 102.6元。

4結(jié)論與討論

現(xiàn)實(shí)商業(yè)中,廣泛存在這樣的一類配送中心選址問題,這類問題的特點(diǎn)可以總結(jié)為服務(wù)區(qū)域內(nèi)的各需求點(diǎn)的一次需求量較少且較穩(wěn)定,需求表現(xiàn)為明顯的周期性特點(diǎn),為提高配送車輛的利用率,降低車輛空載率從而降低配送費(fèi)用,一般采用巡回配送,在這樣的區(qū)域內(nèi)確定一個(gè)配送中心的選址。對(duì)于這類問題,可以用式(1)建立的模型進(jìn)行描述,利用蟻群算法容易得到滿意解,初步應(yīng)用證明了模型與算法的有效性,可以為這類問題提供一種解決方法。模型還存在一些局限性,模型的建立,沒有考慮未來需求的變化,把未來的需求簡(jiǎn)化為是不變的,還有模型沒有考慮需求點(diǎn)的緊急需求。

參考文獻(xiàn):

[1] 蔣利軍,蔣明,趙正佳. 配送中心選址問題研究文獻(xiàn)綜述[J]. 物流科技,2008,31(4):31-33.

[2] 馬麗娟. 物流中心選址模型比較[J]. 商場(chǎng)現(xiàn)代化,2008(5):138-139.

[3] Marco D. Ant colonies for the traveling salesman problem[J]. Biosystems, 1997(43):73-81.

[4] M Dorigo, V Maniezzo, A Colorni. Positive Feedback as a Search Strategy[J]. Technical Report, 2002(3):91-96.

[5] Yuvraj Gajpal, Prakash Abad. An ant colony system(ACS)for vehicle routing problem with simultaneous delivery and pickup[J]. Computers & Operations Research, 2009,36(12):15-23.

[6] 李士勇. 蟻群算法及其應(yīng)用[M]. 哈爾濱:哈爾濱工業(yè)大學(xué)出版社,2004:22-40.