胡 琳

(湖南工程學(xué)院 經(jīng)濟管理學(xué)院，湖南 湘潭 411104)

基于改進粒子群優(yōu)化算法的物流配送中心選址技術(shù)

胡 琳

(湖南工程學(xué)院 經(jīng)濟管理學(xué)院，湖南 湘潭 411104)

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

雙層規(guī)劃模型；粒子群優(yōu)化算法；選址；物流配送中心

0 引言

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

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

1 物流配送中心選址模型

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

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

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

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

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

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

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

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

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

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

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

2 改進粒子群優(yōu)化算法

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

2.1 位置與速度的加法運算

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

2.2 位置的減法運算

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

2.3 速度的數(shù)乘運算

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

2.4 速度的加法運算

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

2.5 改進的粒子運動方程

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

3 仿真實例

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

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

客戶需求w1=400，需求的反函數(shù)如下：

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

其中aij,bij,Eij和Vij都是參數(shù)。假設(shè)：

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。

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

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

反應(yīng)函數(shù)分別如下所示：

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

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

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

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

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

4 結(jié)束語

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

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

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

[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-），女，湖南湘鄉(xiāng)人，碩士，講師，研究方向：物流管理。

（責(zé)任編輯/亦 民）