李 君，梁昔明，張 克

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

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

李 君，梁昔明，張 克

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

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

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

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

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

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

1 嵌入最速下降法的基于增廣Lagrange乘子法的改進(jìn)粒子群優(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乘子法中加一個(gè)能反映等式約束hi(x)和不等式約束cj(x)是否滿足約束的懲罰項(xiàng)，在求解上述形式約束優(yōu)化問題中，如果沒有限制條件l≤x≤u，則將約束優(yōu)化問題(1)就轉(zhuǎn)化為了一系列如下無約束優(yōu)化問題：

minP(x,λk,σk)

(2)

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

(3)

(4)

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

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

(5)

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

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

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

(6)

(7)

σk+1=γσk

(8)

(9)

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

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

(12)

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

xk+1=αdk+xk

(13)

(14)

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

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

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

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

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

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

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

(k) 令α=1；

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

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

2 配送中心選址問題

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

2.1 配送中心的成本組成及假設(shè)

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

1) 每個(gè)需求點(diǎn)的需求量是已知的年需求量；

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

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

4) 一個(gè)需求點(diǎn)僅由一個(gè)配送中心供應(yīng)；

5) 運(yùn)輸費(fèi)用與運(yùn)量和距離成正比；

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

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

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

n： 需求點(diǎn)個(gè)數(shù)；

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

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

Dj： 第j個(gè)需求點(diǎn)的年需求量；

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

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

xij： 配送中心i為需求點(diǎn)j供應(yīng)的貨物量；

hij： 從配送中心i到需求點(diǎn)j供應(yīng)的單位運(yùn)費(fèi)(包括裝卸、運(yùn)輸花銷)；

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

(15)

2.2 物流配送中心服務(wù)能力模型

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

設(shè)Tij是需求點(diǎn)i接受配送中心j等候的最短時(shí)長(zhǎng)，Li為需求點(diǎn)i的顧客評(píng)價(jià)級(jí)別達(dá)到“非常滿意”時(shí)最長(zhǎng)等待貨物時(shí)間，Ui是需求點(diǎn)i的顧客評(píng)價(jià)級(jí)別為“非常不滿意”時(shí)等候的最短時(shí)長(zhǎng)，其中Li≤Ui；Tij為需求點(diǎn)i的顧客對(duì)配送中心j的反應(yīng)時(shí)間的滿意度水平.

(16)

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

(17)

2.3 配送中心選址模型

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

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

(18)

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

(19)

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

3 舉例分析

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

(20)

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

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

(21)

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

(22)

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

在同等條件下，Nash均衡求解算法[13]得到的4個(gè)優(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算法的改進(jìn)結(jié)果如下表1所示，通過Nash算法和ZK_PSO_SD算法結(jié)果對(duì)比，可以看到在服務(wù)水平差距不大的情況下，ZK_PSO_SD算法相比于Nash算法可以更好地降低運(yùn)輸成本，因此，ZK_PSO_SD算法在選址問題上的運(yùn)用是有效果的，是一種實(shí)用的算法.

表1 Nash算法與ZK_PSO_SD優(yōu)化算法計(jì)算結(jié)果對(duì)比

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

4 結(jié)論

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

表2 需求點(diǎn)與配送中心對(duì)應(yīng)關(guān)系圖

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

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

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

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

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

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

[7] 李珍萍，李婷婷，梁志新.帶道路容量限制的多配送中心選址問題的數(shù)學(xué)模型與算法[J].統(tǒng)計(jì)與決策，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] 楊豐梅，華國(guó)偉，黎建強(qiáng).一個(gè)競(jìng)爭(zhēng)選址問題的新模型及其算法[J].系統(tǒng)工程理論與實(shí)踐，2006(7)：18-24

[10] 李珍萍.最短時(shí)限運(yùn)輸問題及解法[J].中國(guó)管理科學(xué)，2001，9(1)：50-56

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

[12] 龔延成.物流配送點(diǎn)選址模型及其算法研究[J].中國(guó)公路學(xué)報(bào)，2003，16(2)：123-126

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

[責(zé)任編輯：佟啟巾]

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

國(guó)家自然科學(xué)基金項(xiàng)目(61463009)； 北京市自然科學(xué)基金項(xiàng)目(4122022)； 中央支持地方科研創(chuàng)新團(tuán)隊(duì)(PXM2013_014210_000173)

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

1004-6011(2016)04-0058-07

TP301.6

A