改進的粒子群優(yōu)化算法在物流配送中的應用

李 君，梁昔明，張 克

(北京建筑大學 理學院，北京 100044)

改進的粒子群優(yōu)化算法在物流配送中的應用

李 君，梁昔明，張 克

(北京建筑大學 理學院，北京 100044)

選址問題的優(yōu)化模型一般是多目標約束優(yōu)化模型，綜合考慮物流成本和物流服務能力，以物流成本最小化和物流服務能力最大化為目標，構建一個多目標優(yōu)化選址模型，通過添加參數(shù)和運用約束處理方法，將選址問題化為單目標約束優(yōu)化問題，并利用嵌入最速下降法的改進粒子群優(yōu)化算法ZK_PSO_SD算法進行求解，所得數(shù)值分析和對比的結果表明，所建立的選址模型具有很好的實用性.

粒子群優(yōu)化算法； 最速下降法； 物流服務能力； 成本最小化

隨著全球經(jīng)濟的發(fā)展，以及信息技術的更新變革，物流行業(yè)得到了極大地發(fā)展，加之電子商務的推動，我國的物流業(yè)一直保持高速增長. 配送系統(tǒng)在物流系統(tǒng)中的地位重中之重，選擇一個好的物流配送中心，對于整個物流配送系統(tǒng)至關重要. 在選擇物流配送中心時，我們要選擇一種優(yōu)良的方案，使節(jié)儉花銷、降低成本且保證質(zhì)量的基礎上服務水平最高. 近些年以來，選址優(yōu)化問題已經(jīng)成為科學研究的一個重要分支.

經(jīng)典配送中心選址問題一般有以下3種類型：連續(xù)模型選址問題、離散模型選址問題和德爾菲專家咨詢法選址方法[1]. 對于選點無約束、不考慮實際情況的選址問題，一般采用連續(xù)模型選址方法來求解，常見的幾種連續(xù)模型選址方法是重心法、改進遺傳算法、粒子群優(yōu)化算法等. 離散模型選址問題[2]是備選的地點是有限的幾個場地，而最佳的地址只能從這幾個中選取，這類問題的求解主要借助庫恩- 漢姆布里爾法、鮑摩- 瓦爾福法、反町氏法、整數(shù)或混合整數(shù)規(guī)劃法等算法. 國內(nèi)諸多學者也就相關問題進行了深入研究，取得了較大進展. 王戰(zhàn)權[3]提出了采用遺傳算法對混合整數(shù)規(guī)劃模型進行分析求解，可以有效地提高算法的效率，提高選址問題的精確度. 劉海燕等[4]通過分析物流系統(tǒng)各要素間的邏輯關聯(lián)，以物流配送中心選址作為對象構建了混合整數(shù)規(guī)劃模型. 德爾菲專家咨詢法選址的思路是將定性分析和定量計算相結合，將專家的判斷以數(shù)值形式表現(xiàn)出來的方法.

隨著研究的深入，針對經(jīng)典配送中心選址問題的求解已經(jīng)無法滿足時代的發(fā)展. 除了經(jīng)典配送中心選址問題以外，近年來國內(nèi)外學者主要對帶有距離限制的配送中心選址問題[5]、帶容量限制的配送中心選址問題[6]、帶道路容量限制的配送中心選址問題[7]等進行研究. 還有一些應急設施選址問題[8]、競爭設施選址問題[9]等也得到了很多專家和學者的關注. 上述的選址問題的情況比較復雜，因此需要對模型進行必要的簡化，并且提出一些假設條件，才滿足算法的需要. 因此，這些年專家和學者研究的重點主要在對各種經(jīng)典問題的擴展研究上，即在考慮各種現(xiàn)實條件的前提下，提出的帶有限制條件的路徑優(yōu)化問題，如最短時限運輸問題[10]、帶時間窗的路徑優(yōu)化問題[11]、帶車容量限制的路徑優(yōu)化問題等. 雖然經(jīng)典的物流配送選址問題相關的研究成果已經(jīng)很豐富，但是與復雜多變的實際情況相比，這些研究還是不夠，這就需要相關領域的學者和專家共同努力. 本文綜合考慮物流成本和物流服務能力，以物流成本最小化和物流服務能力最大化為目標，構建一個多目標優(yōu)化選址模型，通過添加參數(shù)和運用約束處理方法，將問題化為單目標約束選址優(yōu)化問題來解決，利用嵌入最速下降法的改進的粒子群優(yōu)化算法來進行求解，這樣就為多目標選址優(yōu)化模型的求解提供了一個新的思路.

1 嵌入最速下降法的基于增廣Lagrange乘子法的改進粒子群優(yōu)化算法

1.1 增廣Lagrange乘子法

非線性約束優(yōu)化問題的形式如下：

minf(x)x∈Rn
s.t.hi(x)=0,i=1,2,…,l
cj(x)≥0,j=1,2,…,m
l≤x≤u

(1)

增廣Lagrange乘子法是一種較為常見的約束問題處理方法，其基本思想是在Lagrange乘子法中加一個能反映等式約束hi(x)和不等式約束cj(x)是否滿足約束的懲罰項，在求解上述形式約束優(yōu)化問題中，如果沒有限制條件l≤x≤u，則將約束優(yōu)化問題(1)就轉化為了一系列如下無約束優(yōu)化問題：

minP(x,λk,σk)

(2)

其中是P(x,λk,σk)代表的是在給定的λk和σk下，增廣Lagrange乘子法第k步所求的無約束優(yōu)化子問題. 而P(x,λ,σ)是增廣Lagrange罰函數(shù)：

(3)

(4)

對于形如式(1)所示的約束優(yōu)化問題，保留界約束條件l≤x≤u，在使用增廣Lagrange乘子法的基礎上得到如下形式的界約束優(yōu)化問題：

minP(x,λk,σk)
s.t.l≤x≤u

(5)

其中P(x,λk,σk)表達式和式(2)中表述一致.

我們需要借助增廣Lagrange乘子法的思想來求解式(1)的約束優(yōu)化問題，然后將其化為一系列如式(5)所示的式子來求解. 求解過程分為兩個步驟，并且是以內(nèi)外兩層結構的形式，在內(nèi)層結構中主要是對問題(5)進行求解，得到一組最優(yōu)解；外層迭代主要是修改λk和σk以及檢查算法何時終止.

乘子向量λ和σ初始化時，為了方便計算，取λ0=(1,1,…,1)，σ0=(10,10,…,10)，在迭代過程中，Lagrange乘子向量λ的修正方法為：

(6)

(7)

σk+1=γσk

(8)

(9)

1.2 嵌入最速下降法的改進粒子群優(yōu)化算法

在基本粒子群優(yōu)化算法中，每個粒子j的位置和速度更新如下：

vj(t+1)=wvj(t)+c1r1(pj(t)-
xj(t))+c2r2(pg(t)-xj(t))

(10)

xj(t+1)=vj(t+1)+xj(t)

(11)

其中vj(t)為粒子j在第t代的速度，w表示慣性權重，是調(diào)整算法全局搜索能力和局部搜索能力的平衡因子，較大的慣性權重能增強算法的全局搜索能力，而較小的慣性權重則可以增強算法的局部搜索能力；c1為認知系數(shù)，c2為社會系數(shù)；r1,r2為服從均勻分布在區(qū)間(0，1)上的隨機數(shù)，Pj為粒子j的個體歷史最優(yōu)位置，Pg為群體的歷史最優(yōu)位置. 最速下降法的最大特點就是沿著目標函數(shù)的負梯度方向獲得下一個點，這樣尋找的點必然比原來的點更加接近最優(yōu)點. 因此可將最速下降法引入到基本粒子群優(yōu)化算法中.

(12)

為搜索方向，根據(jù)：

xk+1=αdk+xk

(13)

(14)

1.3 改進粒子群優(yōu)化算法的具體流程

(a) 初始化Lagrange乘子法中乘子向量λ0和罰參數(shù)向量σ0；

(b) 借助Lagrange函數(shù)，將約束優(yōu)化問題(1)轉化為界約束優(yōu)化子問題(5)；

(c) 初始化粒子群優(yōu)化算法各參數(shù)，隨機產(chǎn)生初始粒子及速度，并設定速度和位置的范圍為[vmin,vmax],[Ld,Ud]，令當前迭代次數(shù)t=0；

(f) 根據(jù)式(10)計算微粒下一代的速度vj(t+1)，如果新計算出的速度值超出[vmin,vmax]，則取邊界值；

(g) 根據(jù)式(11)計算微粒下一代的位置xj(t+1)，如果新計算出的位置值超出[Ld,Ud]，則取邊界值；

(j) 如果‖dk‖≤eps或k>4則轉(o)；否則，轉(k)；

(k) 令α=1；

(l) xk+1=xk+αdk；

(p) 根據(jù)式(6)～式(8)修正Lagrange乘子法參數(shù)λk和σk，轉(b).

2 配送中心選址問題

配送中心選址和配送路徑優(yōu)化問題在物流配送關系鏈中起著至關重要的作用，一個合理的配送中心選址方案不僅要考慮成本的因素，而且要考慮客戶的滿意度水平，只有兼顧這兩種因素，這樣的配送中心才是我們需要的，才能滿足現(xiàn)代物流配送中心的要求.

2.1 配送中心的成本組成及假設

優(yōu)化計算離不開數(shù)學模型，但建模過程是極為復雜的，為了簡化過程，需要做一些假設：

1) 每個需求點的需求量是已知的年需求量；

2) 不同單位的產(chǎn)品的運輸費用一樣；

3) 在配送過程中的速度是已知的，為一常數(shù)值，不考慮不同路段的差異問題；

4) 一個需求點僅由一個配送中心供應；

5) 運輸費用與運量和距離成正比；

6) 系統(tǒng)總費用只考慮運輸過程中的固定費用、運輸費用以及流通配送中心產(chǎn)品的流通加工費用；

7) 配送中心沒有囤貨現(xiàn)象.

以方便建模和計算為目的，我們需要引用以下參數(shù)：

n： 需求點個數(shù)；

m： 配送中心備選地個數(shù)；

t： 擬建配送中心個數(shù)；

Dj： 第j個需求點的年需求量；

Fi： 在第i個候選作為配送中心的每年固定花銷；

Ci： 每件物品在第i個配送中心的存放花銷；

xij： 配送中心i為需求點j供應的貨物量；

hij： 從配送中心i到需求點j供應的單位運費(包括裝卸、運輸花銷)；

物流配送中心的選址成本優(yōu)化模型如下所示：

(15)

2.2 物流配送中心服務能力模型

物流配送中點的服務水平和能力與很多因素有關，為了使其得到提升，首要的任務是定性到定量因素的轉變. 一般的處理方法是用時間來量度，并且考慮貨物的受損程度等因素. 一般用“時間滿意度函數(shù)”來表示顧客對產(chǎn)品或者服務的時間滿意度與顧客等待時長的對應關系. 接下來分析連續(xù)條件下的線性的“時間滿意度函數(shù)”. 如圖1所示.

設Tij是需求點i接受配送中心j等候的最短時長，Li為需求點i的顧客評價級別達到“非常滿意”時最長等待貨物時間，Ui是需求點i的顧客評價級別為“非常不滿意”時等候的最短時長，其中Li≤Ui；Tij為需求點i的顧客對配送中心j的反應時間的滿意度水平.

(16)

則配送中心系統(tǒng)的時間滿意度可以按照以下計算：

(17)

2.3 配送中心選址模型

本文研究的配送中心選址問題是一個多目標優(yōu)化問題，目標是在保障高服務水平的同時力求運輸成本最小. 該問題將路面信息抽象為方形的區(qū)域，每個地點的信息都是一個二維的點，坐標信息即表示其具體位置，本文問題的研究是在給定顧客需求量和具體位置的基礎上展開的.

配送中心連續(xù)性選址的物流成本模型可表示為：

(18)

配送中心選址問題的目標函數(shù)是在二維空間中選取一個或多個點作為配送中心，在保障高服務水平的同時力求運輸成本最小. 配送中心選址的多目標優(yōu)化模型如下：

(19)

其中，F(xiàn)1,F2均為目標函數(shù)，分別代表運輸成本和配送中心系統(tǒng)的服務能力. 模型中的符號說明如下：(xi,yi)表示用戶i的位置信息；(Xj,Yj)表示j的位置信息；Dij表示j到i的距離；H表示單位運費率；M表示需求點顧客數(shù)；N表示j的個數(shù)；Wi表示i的物品需求量；(xQ0,yQ0)、(xQ1,yQ1)分別代表方形配送區(qū)域的起始點、終止點坐標.

3 舉例分析

本文采取的思路就是將多目標約束優(yōu)化問題轉變?yōu)閱文繕思s束優(yōu)化問題，就可以得到形如式(1)的約束優(yōu)化問題，其形式如下：

(20)

其中0<α<1，K1,K2分別代表F1和F2的最大值. 這樣處理的目的是讓F1和F2處在對等的位置上，因為F1的數(shù)值相對于F2比較大，因此需要引進K1,K2來平衡兩個數(shù)的大小. 如此就得到一個單目標約束優(yōu)化問題式(20)，針對式(20)的求解，可利用ZK_PSO_SD算法來求解. 現(xiàn)給定物流配送區(qū)域，范圍是(0，0)到(100，100). 40個需求點[12]在此區(qū)域內(nèi)隨機分布，如圖2所示. 要求在上述區(qū)域的需求點中找到四個地址作為配送中心j，分別標記為P1,P2,P3,P4. 已知運費率H和需求點的需求量均為一個單位. 所有配送中心運輸派件的速度是50，需求點i的Li=2,Ui=3. 約定算法中終止迭代次數(shù)為200，種群數(shù)量為30，取K1=1 000,K2=160.

因此該物流配送中心選址的多目標優(yōu)化模型如下：

(21)

接下來采取的措施就是將如式(21)所示的有兩個目標函數(shù)的有約束問題轉變?yōu)橹挥袉蝹€目標函數(shù)的約束優(yōu)化問題，對于不同的α值，會有不同的結果. 公司根據(jù)自己的實際情況確定α值，若公司較看中成本，則選取較小的α值；否則，反之. 就本章而言，選擇α=0.7. 這就將多目標約束優(yōu)化問題轉變?yōu)閱文繕思s束優(yōu)化問題，就可以得到形如式(1)的約束優(yōu)化問題，其形式如下：

(22)

針對式(22)的求解，可以借助嵌入最速下降法的改進粒子群優(yōu)化算法的ZK_PSO_SD算法，利用MATLAB2014b實驗平臺，借助ZK_PSO_SD算法對問題(22)進行30次獨立試驗得到的配送中心的位置坐標為P1(73.62，64.8)、P2(21.54，33.87)、P3(44.39，62.04)、P4(47.59，0.54)，如圖3所示.

在同等條件下，Nash均衡求解算法[13]得到的4個優(yōu)化物流配送中心的地址，它們分別是P1(73.74,65.2)，P2(21.23,34.92)，P3(44.61,61.72)，P4(47.64,0.00). 如圖4所示.

Nash算法和ZK_PSO_SD算法的改進結果如下表1所示，通過Nash算法和ZK_PSO_SD算法結果對比，可以看到在服務水平差距不大的情況下，ZK_PSO_SD算法相比于Nash算法可以更好地降低運輸成本，因此，ZK_PSO_SD算法在選址問題上的運用是有效果的，是一種實用的算法.

表1 Nash算法與ZK_PSO_SD優(yōu)化算法計算結果對比

接下來可以思考，能否得到需求點對應的配送中心？一般來說，一個需求點對應一個配送中心，可以參考其中的一個量度作為衡量的標準得到每個需求點對應的配送中心. 如選擇利用距離的大小作為衡量的標準，可以很清晰地得到每個需求點對應的配送中心. 如表2所示，X值對應的是每一個需求點的橫坐標，Y值對應的是每一個需求點的縱坐標. 例如(1，0)而言，它到配送中心P1的距離為97.683 916 79，到配送中心P2的距離為40.356 651 25，到配送中心P3的距離為75.572 418 91，到配送中心P4的距離為46.64，故而可得需求點(1，0)到配送中心P2的距離最短，因而由配送中心P2向需求點(1，0)運貨. 每一個需求點對應的配送中心均可得到，表2中已標出，這樣就達到了我們處理問題的目的.

4 結論

通過介紹多目標優(yōu)化模型，然后簡單的描述了選址問題的背景、物流成本模型和物流配送中心服務能力模型. 將連續(xù)的有約束條件的具有多個目標函數(shù)的選址問題轉變?yōu)橹挥袉蝹€目標函數(shù)的連續(xù)約束優(yōu)化問題，之后再使用基于增廣拉格朗日乘子法的改進粒子群優(yōu)化算法ZK_PSO_SD算法，對一個不僅要考慮成本的因素，而且要考慮客戶的滿意度水平的配送中心選址方案進行試驗. 在給定α值的前提下，相比于Nash優(yōu)化算法，在客戶滿意度水平相差不多的情況下，ZK_PSO_SD算法選取的配送中心的物流成本最低，這就說明ZK_PSO_SD算法在處理選址問題上是行之有效的.

表2 需求點與配送中心對應關系圖

[1] 蔡林寧.物流系統(tǒng)規(guī)劃——及實例分析[M].北京：機械工業(yè)出版社，2008：1-58, 182-229

[2] 王非，徐渝，李毅學.離散設施選址問題研究綜述[J].運籌與管理，2006(10)：64-69

[3] 王占權，楊東援.配送中心選址的遺傳算法研究[J].實用物流技術，2001(3)：11-14

[4] 劉海燕，李宗平，葉懷珍.物流配送中心選址模型[J].西南交通大學學報，2000，35(3)：311-314

[5] 趙斌，王媛，李珍萍.帶距離限制的雙配送中心選址模型[J].物流技術，2011，30(1)：69-71

[6] 魯曉雪，李珍萍.帶容量限制的多配送中心選址問題[J].物流技術，2011，30(1)：67-70

[7] 李珍萍，李婷婷，梁志新.帶道路容量限制的多配送中心選址問題的數(shù)學模型與算法[J].統(tǒng)計與決策，2013,378：37-40

[8] Jaramillo J H, Bhadury J, Batta R. On the use of genetic algorithems to solve location problems[J]. Location Analysis,2002,29(6):761-779

[9] 楊豐梅，華國偉，黎建強.一個競爭選址問題的新模型及其算法[J].系統(tǒng)工程理論與實踐，2006(7)：18-24

[10] 李珍萍.最短時限運輸問題及解法[J].中國管理科學，2001，9(1)：50-56

[11] 馬華偉，左春榮，楊善林.多時間窗車輛調(diào)度問題的建模與求解[J].系統(tǒng)工程學報，2009(5)：607-613

[12] 龔延成.物流配送點選址模型及其算法研究[J].中國公路學報，2003，16(2)：123-126

[13] 李艷，謝能剛，王付宇，等.物流配送中心多目標優(yōu)化選址的仿真設計[J].計算機仿真，2012，29(7)：234-237

[責任編輯：佟啟巾]

Appliction of Improved Particle Swarm Optimization Algorithm in Logistics Distribution

Li Jun, Liang Ximing, Zhang Ke

(School of Science, Beijing University of Civil Engineering and Architecture, Beijing 100044)

Location problem of the optimization model is generally a multi-objective constrained optimization model, which is considered of the goal that has the logistics cost minimization and logistics service capability maximization, and then building a multi-objective optimal location model. By adding parameters and using the constraint handling method, the location problem is changed into a single objective constrained optimization problem, and the improved particle optimization algorithm based on the steepest method is used to solve the problem of ZK-PSO-SD algorithm. The results of numerical analysis and comparison show that the established location model has good practicability.

particle swarm optimization (PSO); steepest descent method; logistics service capability; cost minimization

2016-07-09

國家自然科學基金項目(61463009)； 北京市自然科學基金項目(4122022)； 中央支持地方科研創(chuàng)新團隊(PXM2013_014210_000173)

李 君(1989—), 男, 碩士研究生, 研究方向： 最優(yōu)化智能算法及其應用.

1004-6011(2016)04-0058-07

TP301.6

A