基于鯰魚效應(yīng)粒子群算法的物流配送中心選址

黎 華

（西昌學(xué)院 汽車與電子工程學(xué)院，四川 西昌 615000）

1 引言

隨著我國經(jīng)濟(jì)的迅速發(fā)展，物流配送業(yè)務(wù)日益增多，配送中心在物流系統(tǒng)中起著樞紐作用，其目標(biāo)主要根據(jù)區(qū)域內(nèi)不同客戶要求，將商品貨物及時(shí)、準(zhǔn)確和有效地送到客戶手中，因此物流配送中心選址是物流系統(tǒng)研究中的核心，對于選擇最佳物流配送中心具有十分重要的實(shí)用價(jià)值[1]。

針對物流配送中心選址問題，國內(nèi)外學(xué)者進(jìn)行了大量的研究，提出了許多選址模型[2]。大量研究表明，物流配送中心選址問題是一個(gè)帶有復(fù)雜約束的目標(biāo)優(yōu)化問題，屬于NP-hard問題[3]。為此，學(xué)者們提出了禁忌搜索算法、遺傳算法、蟻群算法等，這些算法都取得了一定的成效[4-6]。由于這些算法都屬于啟發(fā)式搜索算法，當(dāng)所求問題的規(guī)模較大時(shí)，尋優(yōu)速度慢，難以獲得全局最優(yōu)的物流配送中心選址方案，選址效果不夠理想[7]。粒子群優(yōu)化算法（PSO)模擬鳥群覓食行為，具有收斂速度快、尋優(yōu)能力強(qiáng)、參數(shù)設(shè)置簡單等優(yōu)點(diǎn)，成為物流配送中心選址問題求解的主流算法[4,8]。在實(shí)際應(yīng)用中，標(biāo)準(zhǔn)PSO算法存在一些缺陷，如易出現(xiàn)“早熟”現(xiàn)象，當(dāng)物流配送點(diǎn)多時(shí)，PSO算法易獲得物流配送中心選址的局部最優(yōu)解，尋優(yōu)效果差[9]。

為了解決標(biāo)準(zhǔn)PSO算法在物流配送中心選址問題求解過程存在的缺陷，引入自然界的“鯰魚效應(yīng)”（catfish effect），提出了一種基于鯰魚效應(yīng)粒子群算法的物流配送中心選址策略（CFPSO），并通過對實(shí)際物流配送中心選址問題進(jìn)行仿真實(shí)驗(yàn)，與標(biāo)準(zhǔn)PSO算法、遺傳算法進(jìn)行對比，驗(yàn)證CFPSO用于物流配送中心選址問題求解的有效性。仿真結(jié)果表明，CPSO算法較好地克服了其它算法存在的缺點(diǎn)，可以獲得全局最優(yōu)的物流配送中心選址方案，具有對比算法無法比擬的優(yōu)勢。

2 物流配送中心選址問題描述

物流配送中心選址模型可表示為：

式（1）中，Wij表示需求點(diǎn)i對配送中心j的需求量；l表示需求點(diǎn)與配送中心的距離上限；M為被選為配送中心的需求點(diǎn)的集合；N表示所有需求點(diǎn)的序號(hào)集合；Cj為配送中心的建設(shè)費(fèi)用；gj表示配送中心物資流轉(zhuǎn)的單位管理費(fèi)用；hj∈{0,1}，當(dāng)其為1時(shí)表示點(diǎn)j被選為配送中心；dij表示需求點(diǎn)i離它最近的配送中心j的距離；Zij∈{0,1}表示需求點(diǎn)與配送中心的服務(wù)分配關(guān)系，當(dāng)其為1時(shí)，表示需求點(diǎn)i的需求量由配送中心j供應(yīng)，否則Zij＝0[10]；Bj表示配送中心j的供應(yīng)上限。

式（1）相應(yīng)的限制條件為：

約束條件中，式（2）表示需求點(diǎn)i對配送中心j的需求量應(yīng)小于配送中心j的總供應(yīng)量；式（3）表示每個(gè)需求點(diǎn)由離它最近配送中心服務(wù)；式（4）表示沒有配送中心的地點(diǎn)不會(huì)有客戶；式（5）表示有p個(gè)需求點(diǎn)被選為配送中心；式（6）表示配送中心只對附近的需求點(diǎn)進(jìn)行服務(wù)。

3 鯰魚效應(yīng)的粒子算法

在PSO算法中，每一個(gè)粒子代表待求解問題的一個(gè)潛在解，由適應(yīng)度函數(shù)確定粒子的優(yōu)劣程度。首先隨機(jī)產(chǎn)生一群粒子，然后計(jì)算粒子的適應(yīng)度值，最后粒子在解空間不斷飛行，最終找到問題的解。設(shè)粒子個(gè)體和整個(gè)群體的最優(yōu)位置分別為pbest和gbest，粒子的速度與位置更新公為：

其中，ω 為慣性權(quán)重；c1和c2為學(xué)習(xí)因子；rand()為（0,1）之間的隨機(jī)數(shù)；vi,dk和xi,dk分別為粒子i在第k次迭代中第d維的速度和位置；pbesti,dk是粒子i在第d維的個(gè)體極值的位置；gbestdk是群體在第d維的全局極值的位置。

由式（7）和式（8）可知，粒子群算法出現(xiàn)早熟收斂現(xiàn)象，那么pg一定是局部最優(yōu)解，通過改變pg或pi，讓粒子逃出局部最優(yōu)解區(qū)域。

CFPSO采用偏差閾值作為觸發(fā)條件，通過鯰魚算子對全局極值或個(gè)體極值進(jìn)行擾動(dòng)，粒子速度更新變?nèi)缦拢?/p>

式（9）中，c3表示鯰魚對個(gè)體最優(yōu)的沖撞強(qiáng)度;c4表示鯰魚對全局最優(yōu)的沖撞強(qiáng)度；c3·rand()和c4·rand()稱為鯰魚算子，其定義如下：

式中，ep表示當(dāng)前值與當(dāng)前個(gè)體最優(yōu)值的偏差；eg表示當(dāng)前值與當(dāng)前全局最優(yōu)值的偏差；e0p表示當(dāng)前值與當(dāng)前局部最優(yōu)值之偏差的閾值；e0g表示當(dāng)前值與當(dāng)前全局最優(yōu)值之偏差的閾值。

由式（10）、式（11）可知，若當(dāng)前值的偏差大于偏差閾值，鯰魚算子取為1，此時(shí)CFPSO算法為標(biāo)準(zhǔn)PSO算法；反之，認(rèn)為此時(shí)粒子發(fā)生聚集，引入鯰魚算子去沖撞個(gè)體最優(yōu)值或局部最優(yōu)值，以跳出局部最優(yōu)。

4 基于CFPSO的物流配送中心選址問題求解

4.1 粒子的編碼方式

采用CFPSO算法對物流配送中心選址問題進(jìn)行求解時(shí)，首先也是最為關(guān)鍵的一步就是粒子編碼。粒子的具體編碼方式為：X=(x1,x2,...,xN)，其中粒子的長度N為物流中心備選點(diǎn)的個(gè)數(shù)，若最后求出的最優(yōu)粒子X=(1,0,0,1,1,0,0)，則表示在7個(gè)物流備選點(diǎn)中，第1、第4和第5個(gè)備選點(diǎn)將作為物流配送中心。

4.2 求解的具體步驟

Step 1:設(shè)置CFPSO算法的參數(shù)。主要包括粒子數(shù)目、ω、c1、c2、粒子速度以及粒子位置。

Step 2:初始化粒子群。傳統(tǒng)PSO算法采用隨機(jī)方式產(chǎn)生初始粒子群，易使粒子集中于某一局部，可行解分布不均勻，本文采用均勻方法產(chǎn)生初始粒子群，保證初始粒子群分布的均勻性。

Step 3:計(jì)算每個(gè)粒子的適應(yīng)度值，根據(jù)適應(yīng)度值確定個(gè)體最優(yōu)值和群體最優(yōu)值。

Step 4:根據(jù)式（10）和式（11）確定鯰魚算子，并更新粒子的速度和位置。

Step 5:計(jì)算每個(gè)粒子在新位置上的適應(yīng)度值，如果粒子的適應(yīng)度值優(yōu)于個(gè)體的適應(yīng)度值，則個(gè)體更新為新位置；如果粒子的適應(yīng)度值優(yōu)于群最優(yōu)值，則群體最優(yōu)值更新為新位置。

Step 6:如果達(dá)到最大迭代次數(shù)，輸出最優(yōu)物流配送中心選址方案，否則轉(zhuǎn)到Step 2，繼續(xù)進(jìn)行尋優(yōu)。

具體流程如圖1所示。

圖1 CFPSO的物流配送中心選址問題求解流程

5 仿真實(shí)驗(yàn)

5.1 仿真環(huán)境

為了驗(yàn)證CFPSO算法對物流配送中心選址問題求解的有效性，在P4雙核2.8G CPU、1G內(nèi)存，操作系統(tǒng)為Windows XP的計(jì)算機(jī)上，在Matlab2009環(huán)境下進(jìn)行了實(shí)驗(yàn)。客戶地址和物流需求量見表1，為使CFPSO算法的選址結(jié)果具有可比性，采用遺傳算法、標(biāo)準(zhǔn)粒子群算法進(jìn)行對比仿真實(shí)驗(yàn)。

表1 需求點(diǎn)位置和物資需求量

5.2 CFPSO的結(jié)果分析

采用CFPSO算法對表1的物流配送中心選址問題進(jìn)行求解，從26個(gè)客戶點(diǎn)中選擇5個(gè)位置作為配送中心。c1＝c2=2，w為0.55，最大迭代次數(shù)為100，粒子數(shù)目為20，那么CFPSO算法的收斂曲線如圖2所示。

圖2 CFPSO的收斂曲線

物流配送中心選址方案如圖3所示。從圖3可知，采用CFPSO算法可以獲得較優(yōu)的物流配送中心選址方案，其圓點(diǎn)表示需求點(diǎn)，方框表示配送中心。

5.3 與其它算法的性能對比

遺傳算法、標(biāo)準(zhǔn)粒子群算法和CFPSO算法的物流配送中心選址問題求解性能對比結(jié)果見表2。從表2可知，相對于遺傳算法、標(biāo)準(zhǔn)粒子群算法，CFPSO算法對物流配送中心選址問題進(jìn)行求解時(shí)，求解速度明顯加快，求解效率更高。對比結(jié)果表明，CFPSO較好地克服了傳統(tǒng)算法求解過程存在的不足，是一種有效的物流配送中心選址問題求解算法，尤其對于大規(guī)模物流配送中心選址問題的優(yōu)勢更加明顯。

圖3 基于CFPSO的物流配送中心選址方案

表2 不同算法的總體性能比較

6 結(jié)語

針對標(biāo)準(zhǔn)粒子群算法存在早熟收斂、易出現(xiàn)局部最優(yōu)等缺陷，引入自然界的“鯰魚效應(yīng)”，提出了一種基于鯰魚效應(yīng)粒子群算法的物流配送中心選址策略。由于引入“鯰魚效應(yīng)”，可以較好地保持粒子的活性，更加真實(shí)地反映了粒子的運(yùn)動(dòng)規(guī)律。仿真實(shí)驗(yàn)結(jié)果表明，相比于遺傳算法、標(biāo)準(zhǔn)粒子群算法，CFPSO算法可以獲得更優(yōu)的物流配送中心選址方案，可以快速、準(zhǔn)確地找到最優(yōu)的物流配送中心。

[1]李軍,郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法[M].北京:中國物資出版社,2001.

[2]Ming-Shin Kuo.Optimal location selection for an international distribution center by using a new hybrid method[J].Expert Systems with Applications,2011,38(6):7 208-7 221.

[3]Xu Jiuping,Yao LM,Zhao XD.A multi-objective chance-constrained network optimal model with random fuzzy coefficients and its application to logistics distribution center location problem[J].Fuzzy Optimization and Decision Making,2011,10(3):255-285.

[4]Yang Lixing,Ji Xiaoyu,Gao Ziyou.Logistics distribution centers location problem and algorithm under fuzzy environment[J].Journal of Computational and Applied Mathematics,2007,208(2):303-315.

[5]Ye Lia,Xiaodong Liua,Yan Chen.Selection of logistics center location using Axiomatic Fuzzy Set and TOPSISmethodology in logistics management[J].Expert Systems with Applications,2011,38(6):7 901-7 908.

[6]Huijun Sun,Ziyou Gao,Jianjun Wu.A bi-level programming model and solution algorithm for the location of logistics distribution centers[J].Applied Mathematical Modelling,2008,32(4):610-616.

[7]Sen Liua,Felix T S Chanb,S H Chungb.A study of distributioncenter location based on the rough sets and interactive multi-objective fuzzy decision theory[J].Robotics and Computer-Integrated Manufacturing,2011,27(2):426-433.

[8]Yasanur Kayikci.A conceptualmodel for intermodal freight logistics centre location decisions[J].Procedia-Social and Behavioral Sciences,2010,2(3):6 297-6 311.

[9]程明輝,齊名軍.基于粒子群算法的物流配送路徑優(yōu)化問題研究[J].中國外資,2008,(8):254-256.

[10]易文周.混沌鯰魚粒子群優(yōu)化和差分進(jìn)化混合算法[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(15):54-58.

[11]Chuang L Y,Wei T S,Yhong Y C.Chaotic catfish particle swarm optimization for solving global numerical optimization problems[J].Applied Mathematics and Computation,2011,217:6 900-6 916.