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

林　雄

摘要:對一類要求考慮路線安排的單配送中心選址問題建立基于蟻群算法的選址模型,模型目標以配送中心建設費用與運輸費用之和最小;同時構造模型的蟻群算法求解結構;最后初步應用證明了該模型解決此類問題的有效性,為單配送選址提供又一種方法。

關鍵詞:蟻群算法;配送中心;路線安排;選址

中圖分類號:F224文獻標識碼: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

單配送中心選址模型目前主要采用連續模型,如重心法。這類方法在解決配送中心選址問題的局限性一方面在于模型要求區域內任意點都可以建設配送中心,但在實際環境中往往做不到,經常出現用這種方法求出的配送中心的位置在實際中不能建設,如求得的建設地點位于湖泊中、江河中等;另一方面,目前的單配送中心模型選址時,沒有考慮配送路線的安排[1-2]。基于蟻群算法考慮路線安排的單配送中心選址模型克服了以上局限,能夠解決這樣一類配送中心選址問題:要求在選址區域內選擇一個需求點來建設一個配送中心,同時需要考慮配送路線安排,目標是使得配送總費用最低。

1選址模型研究

1.1問題描述與分析

現實中有這樣一類配送中心選址問題:已知某區域及區域內需求點地址集合,該區域內各需求點的需求特點是一次需求量少,且需求穩定,具有周期性,各需求點的一次需求總量也相對較小,對各需求點的一次需求實行一次巡回配送完成,現在要在各需求點中選出一個來擴建成配送中心為這個區域的需求服務,使得配送中心建設費用與運輸費用最小。因為采用一次巡回配送,巡回路線的不同對運輸費用影響很大,考慮到各需求點需求穩定且具有周期性,一旦獲得最優的配送巡回路線,可以重復使用,而每個備選點都有其最優的運輸費用與建設費用組合,基于這樣的考慮,問題的目標就是尋找基于最優配送路線的一次運輸費用與一次分攤建設費用之和最小的備選點位置。

1.2模型假設

(1)區域內僅建設一個配送中心;

(2)配送中心建立在某個需求點處;

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

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

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

(6)運輸費用與運輸距離及運輸量成正比;

(7)系統總費用只考慮配送中心的建設費用和運輸費用。

1.3模型的建立

根據以上問題描述與模型假設,可以得出配送中心選址的一般模型表達:

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

Subject to(2)

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

c分別表示車輛經歷分段路徑i,1,1,2,…,n,i的運輸費率,(單位為元·km-1·kg-1);d,d,…,d表示分段路徑i,1,1,2,…,n,i的距離;x,x,…,x分別表示車輛經歷分段路徑i,1,1,2,…,n,i時的載重量;f表示配送中心建設在i點的建設費用,m表示配送中心服務年限內,所執行的配送次數,m=tp,t表示配送中心設計服務年限,p為每年執行配送的次數,fm表示建設費用分攤到每次配送的費用;Dj=1,2,…,n為各需求地的需求量。

2模型求解的蟻群算法

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

2.1基本的蟻群算法模型

定義如下參數:

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

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

Pt=(3)

其中,allowed=0,1,…,n表示t時刻螞蟻k下一步允許選擇的點。在螞蟻算法中,假設人工蟻群系統有記憶功能,用tabukk=1,2,…,m記錄螞蟻k已經走過的節點。當一個周期結束,進入t+1時刻,對各路徑上的信息素進行調整,即[3]:

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

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

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

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

2.2.1模型的求解步驟

模型求解思路:

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

求解步驟為:

步驟1:以任意一個需求地i為配送中心建設地,計算配送中心建設在該地點考慮配送路線安排的最小費用。即假設配送中心建設在i點,構造蟻群搜索規則搜索以i為起點的配送費用最小的配送路線,依據這一最優配送路線,依據公式(1)計算得到配送中心建設在該點的最小費用;

步驟2:重復步驟1,直到獲得配送中心獨立建設在每個需求地的最小費用及相應配送路線安排;

步驟3:對求得的一系列費用進行排序,其中費用最小的方案即為選址解決方案,如得到的結果為:配送中心建設在需求點j,配送路線安排為j→x→x→x→x→…→x→j,其中,x,x,x,…,x為區域內的需求點。

2.2.2模型求解蟻群算法的設計與實現

(1)初始化

設定時間計數器t,循環次數計數器N,螞蟻數m,初始化關鍵參數α、β、ρ、τt的設置:信息素軌跡強度初始值采用最大最小螞蟻系統(MMAS)的設置,即為經歷兩需求地間的每段路徑i,j設置一個最大信息素軌跡強度的初始值τ=τ。△τ的設置:信息素軌跡增量的初始值設為0,隨后計算的增量為一常數。η的設置:這里路徑最優不一定指配送路線最短,路線最短不一定配送成本最低,因為配送費用還與各需求點的需求量有關,因而兩點間的能見度在這里設為η=ξDd,0<ξ<1。禁忌表初始化為空集,把m只螞蟻全都置于起始點i,同時將螞蟻的初始位置這里即起始點i置于當前禁忌表中。

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

位于需求點i的螞蟻選擇下一需求點j的狀態轉移規則如下:

j=(6)

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

(3)利用最大最小螞蟻系統信息軌跡更新規則,對信息素軌跡進行全局更新

當m只螞蟻都建立完一次路徑解決方案,根據公式(1)找出尋到本次最優路徑的螞蟻,最優的螞蟻就是搜索到的配送路線使得配送總費用最小的那只螞蟻,只對這只螞蟻經歷的路徑進行信息素更新,更新規則如下:

τt+1= (7)

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

(4)清空禁忌表,重復(1)、(2)、(3),直至達到設置的循環次數N,得到從需求點i出發的最后的最優配送路線。

(5)根據得到的最優路線安排,依據式(1)計算配送中心建在需求點i的總成本z。

(6)對每個需求點重復(1)～(5),得到把配送中心建在各需求點的總費用,z,z,…,z。

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

3初步應用

某企業為一個區域提供機械零件的配送服務,為控制費用并能有效地提供配送服務,決定在其中一個需求點建設一個配送中心,使得建設費用與配送費用最小。區域內共有10個需求點,各需求點的機械零件一次需求量較少,需求量及需求周期穩定,每個月定期執行4次配送,配送計劃采用一次巡回配送。各需求點間的距離見表1;各需求點的定期一次需求量見表2;在各需求點建設配送中心的費用見表3。

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

4結論與討論

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

參考文獻:

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

[2] 馬麗娟. 物流中心選址模型比較[J]. 商場現代化,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] 李士勇. 蟻群算法及其應用[M]. 哈爾濱:哈爾濱工業大學出版社,2004:22-40.