基于改進粒子群優化算法的物流配送中心選址技術

胡 琳

(湖南工程學院 經濟管理學院，湖南 湘潭 411104)

基于改進粒子群優化算法的物流配送中心選址技術

胡 琳

(湖南工程學院 經濟管理學院，湖南 湘潭 411104)

文章同時考慮客戶和物流規劃部門的利益，構建了物流配送中心地址優化的雙層規劃模型。提出了一種改進的粒子群優化算法，分別求解雙層規劃模型的上層模型和下層模型。仿真實例表明了本文方法的可行性和有效性。

雙層規劃模型；粒子群優化算法；選址；物流配送中心

0 引言

物流配送中心選址是諸多管理決策問題之一。無論是分配系統的成本還是客戶服務水平都顯著地取決于配送中心的數量、規模和位置以及每個中心所服務的客戶。因此，大量研究一直致力于物流配送中心選址的數學模型。

物流配送中心選址問題能作為領導者-跟隨者模型或斯塔克爾貝格游戲的一個代表，決策管理者是領導者，客戶就是那些可自由選擇配送中心的跟隨者。因此，用雙層規劃模型來表現選址問題是恰當的。然而，盡管已經廣泛地研究了設施選址問題，仍然只有極少數關注使用雙層規劃模型。谷口未央[1]發展了一種雙層模型來決定公共物流終端的最佳規模和地點。模型上層描述了規劃者最大化降低整體成本的行為，成本包括了運輸成本(長途運輸與提取運送費用)和設施投資成本。模型的下層則用來決定在任意公共物流終端的卡車和客車的平衡分配。該模型直接采取遺傳算法進行求解。盡管如此，客戶需求分配(響應功能形式)地點位置的影響并沒有分析得很精準。雙層模型精確的響應功能(上層模型變量與下層模型變量的變動關系)是至關重要的。鑒于此，本文同時考慮客戶和物流規劃部門的利益，構建了物流配送中心地址優化的雙層規劃模型。提出了一種改進的粒子群優化算法，分別求解雙層規劃模型的上層模型和下層模型。仿真實例表明了本文方法的可行性和有效性。

1 物流配送中心選址模型

與傳統單層規劃模型相比，雙層規劃模型具備更多優點：(1)雙層規劃模型能在決策過程中同時分析兩種不同甚至是沖突的客觀事物；(2)雙層規劃模型的多重準則可更好地反映出實際問題；(3)雙層規劃模型能明確地代表系統管理者與客戶的共同行為。由于物流配送中心的選址問題涉及到系統管理者和客戶這兩種類型的決策者，有著不同的目標函數，顯然，采用雙層規劃模型來描述選址問題是恰如其分的。

1.1 物流配送中心選址的上層模型

物流配送中心選址的上層模型主要用來決定配送中心的最優場所從而使得整體成本(固定和變動費用)最小，在決策者制定的固定投資范圍內來滿足位于不同位置的客戶需求。假定在建新配送中心之前沒有任何配送中心，即不需要考慮新舊配送中心之間的競爭。物流配送中心選址的上層規劃模型描述如下：

這里，Cij(Xij)表示配送中心j滿足客戶需求的整體成本，通常是一個非線性函數；Xij表示由配送中心j提供給客戶的物資；fj表示與建造配送中心相關聯的固定投資；zj表示0～1變量，如果配送中心j已建好，那么zj就是1，反之為0。

從決策者的角度來看，上層模型目標函數的第一部分表示了滿足客戶需求的整體變動成本，第二部分表示了與建造配送中心相關聯的固定成本。固定投資成本包括土地征用費用和設施建造費用。第1個約束確保了至少建造一個配送中心，第2個約束表示了決定變動的雙重限制。物流配送中心選址的上層模型是非線性的0～1整數規劃問題。

1.2 物流配送中心選址的下層模型

在物流配送系統中，某個客戶的需求分配受到其他客戶需求分配的影響。假如所有客戶都去一個配送中心(根據交通費用這可能是最近的)，由于整體需求費用的獨立性，可能將發展為擁擠。因此，該地點的成本增加到一定程度可能不再是費用最小的那個。一些客戶可能將選擇別的配送中心，這個配送中心也有可能擁擠。這個過程就需要重復分配直到達到一種平衡狀態。在這種狀態下，所有使用的配送中心費用將持平，并且也小于或等于到任意非配送中心的費用，這種平衡稱為用戶均衡狀態。為了反映這種現象，采用需求函數來描述客戶和客戶j的最低成本與客戶分配的關系。

Xij=Dij(uij),坌i=1,2,…，m，j=1,2,…，n

這里，uij表示從配送中心j滿足客戶i需求的最低成本，D(·)表示最低成本uij的單調遞減函數，它反映了配送規模、服務等級和成本信息等。物流配送中心選址的下層模型如下所示：

這里，D-1（·）表示需求函數的反函數，需求函數的反函數的常見形式是冪函數和對數函數；wi是客戶i的整體需求，sj是配送中心j的容量；M是一種任意的大的正常數。

物流配送中心選址的下層模型代表了客戶選擇行為和分配在各配送中心的需要，也就是說，每個客戶把他的需求分配到各配送中心以最大化降低他的總費用。在物流配送中心選址的下層模型中，第一個約束確保每位客戶的總需求由一些配送中心來提供滿足；第二個約束是容量約束，確保所有分配到每個配送中心的需求不會超過它的容量；第三個約束禁止在實際上并未修建的配送中心提供需求，M是一種任意的大的正常數，如果zj=0，那么Xij不可能是正數；如果zj=1，那么Xij可盡可能地大；第四個約束代表決策變量的非負限制。

2 改進粒子群優化算法

粒子群優化算法(Particle swarm optimization，PSO)以鳥群的集體協作為尋優目的，主要模擬鳥群飛行覓食行為。在PSO算法中，自身、歷史最優位置和整個粒子群的全局最優位置給每個粒子提供信息，單個粒子在方案空間內不斷飛行，從而達到實現尋找最優解的目的。盡管有關離散域，尤其是路由規劃和組合優化問題研究得較少，但是粒子群優化算法已成功地應用于求解連續問題。就TSP問題而言，Clere等提出了一個具體的DPSO算法。雖然未考慮到離散量運算規律的不同，跟其他算法存在著不小的差距，但其定義速度為交換列表，也定義了其他量及運算法則。同樣，利用交換列表的規律，黃嵐等也定義了不同的離散量運算規則，算法僅僅針對小維數TSP問題進行了仿真。盡管如此，他的算法證明了PSO在求解離散優化問題是可行的，仍然顯現了其極強的進化特征。

2.1 位置與速度的加法運算

粒子位置的變化由位置與速度加法運算來體現，可由以下公式來確定新位置。其中交換位置x中的xi和vi由函數來定義。如新位置(5,2,3,1,4)由=(0,2,3,0,4)和=(2,4,5,1,3)得到。

2.2 位置的減法運算

1個速度由兩位置相減所得，下式可用來表示v=x2-x1位置減法運算的含義。

2.3 速度的數乘運算

我們定義v=c1vc2(1≤c1,c2≤N)，把1到N的循環列表看成是維，從位置開始進行左乘的操作，右乘c2表示至c2-1位置結束。維的速度在這之間取原有值，其余位置值都為0。隨機產生的數值即c1和c2(c2>c1)。c2=c2-length(v)時意味著c1為速度的最后一維數據。從而得到較為均衡的粒子速度，并且它向最佳方向的飛行也很均衡。同時，參數c選取所帶來的問題也隨即消失了，下列公式也可表示速度的數乘運算規則。

2.4 速度的加法運算

1個新的速度由2個速度相加獲得，v=v1+v2，其中分量定義為：

2.5 改進的粒子運動方程

站在社會心理學的角度，個體學習自身成功行為的能力由學習因子C1來表示，這個同時也稱為認知因子，而C2即為社會因子，代表了學習社會成功行為的能力。以Pgt和Plt為中心的領域所有范圍都能由C1和C2搜索到。在本文中，搜索效果再次受到每次迭代過程中每代的最優值PCT的影響。C3定義為時代因子，表示學習本次迭代成功行為的能力。實現這一方法主要在于進一步改進的粒子運動方程，并且將1個當前代粒子最優位置Pct重新定義，這樣不僅能使粒子向個體最優和全局最優靠攏，而且還能向當前代的最優值靠近。鑒于DPSO的特殊性，采用分段計算方式將達到更好的效果，原因在于對位置上各維數據的作用是相互的。

3 仿真實例

本部分通過一個簡單的數值例子來描述模型以及驗證本文方法的正確性。雖然數值例子的說服力有點微弱，應該從客戶的實際行為觀察證實，但這個例子重點用來驗證本文方法的正確性。假定系統中有一個客戶，有四個候選的配送中心位置(B1,B2,B3,B4,B5,B6,B7,B8,B9)，整體成本函數為：

Cij(Xij)=aij(Xij)bij-Eij

客戶需求w1=400，需求的反函數如下：

D-1(Xij)=aij(Xij)bij-Vij

其中aij,bij,Eij和Vij都是參數。假設：

a11=0.15，a12=0.08,a13=0.1,a14=0.07,a15=0.08,a16=0.1,a17=0.07,a18=0.08,a19=0.1,

b11=0.33，b12=0.33,b13=0.33,b14=0.33,b15=0.33,b16=0.33,b17=0.33,

b18=0.33,b19=0.33,

E11=0.8z，E12=1.7z2,E13=1.5,E14=1.2z4,E15=1.7z5,E16=0.51z6,E17=1.2z7,E18=1.7z8,E19=0.51z9,

f1=1,f2=0.7,f3=1.5,f4=0.9,f5=0.7,f6=1.5,f7=0.9,f8=0.7,f9=1.5

再假定配送容量是無窮大的，M=500，e=0.05。

根據第三部分的改進粒子群優化算法，求得的物流配送中心選址的下層模型的最優方案為：

X*=(0,0,0,0,0,0,0,0,400)

反應函數分別如下所示：

X11=400z1-400

X12=400z2-400

X13=400z3-400

X14=400z4-400

X15=400z5-400

X16=400z6-400

X17=400z7-400

X18=400z8-400

X19=400z9

再根據第三部分的改進粒子群優化算法，求得的物流配送中心選址的上層模型的最優方案為：

z1=0,z2=0,z3=0,z4=0,z5=0,z6=0,z7=0,z8=0,z9=1

即最后的配送中心應該建造，其他的不應該建造。配送中心的客戶需求分布為：

X11=0,X12=0,X13=0,X14=0,X15=0,X16=0,X17=0,X18=0,X19=400

4 結束語

物流配送中心選址是諸多管理決策問題之一。無論是分配系統的成本還是客戶服務水平都顯著地取決于配送中心的數量、規模和位置以及每個中心所服務的客戶。

本文同時考慮客戶和物流規劃部門的利益，構建了物流配送中心地址優化的雙層規劃模型。物流配送中心選址的上層模型主要用來決定配送中心的最優場所從而使得整體成本(固定和變動費用)最小，在決策者制定的固定投資范圍內來滿足位于不同位置的客戶需求。物流配送中心選址的下層模型代表了客戶選擇行為和分配在各配送中心的需要，也就是說，每個客戶把他的需求分配到各配送中心以最大化降低他的總費用。

粒子群優化算法(Particle swarm optimization，PSO)以鳥群的集體協作為尋優目的，主要模擬鳥群飛行覓食行為。提出了一種改進的粒子群優化算法，分別求解雙層規劃模型的上層模型和下層模型。仿真實例表明了本文方法的可行性和有效性。

[1]E.Taniguchi.Optimal Size and Location Planning of Public Logistics Terminals[J].Transport.Res.,1999,35(3).

[2]C.H.Aikens.Facility Location Models for Distribution Planning[J].Eur.J.Oper.Res,1985,(22).

[3]K.Holmberg.Exact Solution Methods for Uncapacitated Location Problem with Convex Transportation Costs[J].Eur.J.Oper.Res,1999,(114).

[4]F.Barahona,D.Jensen.Plant Location with Minimum Inventory[J].Math.Program,1998,(83).

[5]S.H.Owen,M.S.Daskin.Strategic Facility Location:a Review[J].Eur.J.Oper.Res.,1998,(111).

[6]A.Klose,A.Drexl.Facility Location Models for Distribution System Design[J].Eur.J.Oper.Res.,2005,(162).

[7]G.Zhou,H.Min,M.Gen.The Balanced Allocation of Customers to Multiple Distribution Centers in the Supply Chain Network:a Genetic Algorithm Approach,Comput.Ind.Eng.,2002,(43).

[8]S.S.Syam.A Model and Methodologies for the Location Problem with Logistical Components[J].Comput.Oper.Res.,2002,(29).

[9]Z.Q.Lu,N.Bostel.A Facility Location Model for Logistics Systems Including Reverse Flows:the Case of Remanufacturing Activities[J].Comput.Oper.Res.,2007,(34).

F252

A

1002－6487（2011）04－0057-03

胡 琳（1969-），女，湖南湘鄉人，碩士，講師，研究方向：物流管理。

（責任編輯/亦 民）