龍圣杰 劉衍民 曾慶雨

(遵義師范學院數學學院 遵義 563002)

改進粒子群算法在多目標物流選址中的應用*

龍圣杰 劉衍民 曾慶雨

(遵義師范學院數學學院 遵義 563002)

考慮到物流選址規(guī)劃對系統(tǒng)運營的影響，以物流運營成本最小及服務滿意度最大為目標，構建工廠-物流中心-分銷商三級物流選址規(guī)劃模型.為了避免粒子群算法容易早熟和容易落入局部最優(yōu)的缺陷，引入合作學習思想，針對多目標選址規(guī)劃問題，用多目標合作粒子群算法(MCPSO)求多目標離散型物流選址規(guī)劃模型的Pareto解.通過對實例進行仿真模擬，求解模型的選址-分派方案，并結合靈敏度分析，證明所提出算法的有效性.

物流選址規(guī)劃；多目標；合作學習；粒子群算法；仿真

0 引 言

全球化市場競爭環(huán)境下，整個價值鏈的競爭能力替代了以往強調企業(yè)個體競爭能力，實現成本最低與服務最大化一直是產品價值鏈的核心問題[1].物流規(guī)劃中的選址與其分派計劃的制定密切相關，因此物流中心研究的核心在于選址規(guī)劃問題[2].國內外很多學者建立了一系列的模型與算法針對這一問題進行了定性與定量的研究[3-4].對于選址規(guī)劃問題，按照模型與優(yōu)化算法的不同可分為連續(xù)型與離散型[5-6].物流規(guī)劃涉及的多目標問題，大多數研究以權重法將多目標優(yōu)化模型轉化為單目標優(yōu)化，或是采用目標規(guī)劃法將主要目標以外的目標函數轉化為約束條件[7].物流中心選址規(guī)劃這類涉及的成本與服務等存在背反效應的多個目標，以上提到的方法依賴于主觀性或是犧牲其他目標函數的方法對于多目標尋優(yōu)具有很大限制[8]，因此，提出構建離散型多目標物流規(guī)劃模型尋求Pareto解.

對于物流規(guī)劃問題研究涉及的多目標、多維度解的問題，采用常規(guī)方法運算量大、計算復雜程度高，而當前的一些啟發(fā)式方法容易陷入局部最優(yōu)[9].針對多目標物流規(guī)劃的NP-hard問題，為克服傳統(tǒng)的粒子群算法容易陷入局部最優(yōu)的情況，學者們提出了對粒子群的改進：①對粒子群算法慣性參數進行調整，包括動態(tài)策略和自適應方法，學習因子和社會因子的調整[10]；②提出鄰域搜索策略，加強當前種群鄰域的勘探[11]；③粒子群采用信息共享機制，增強種群多樣性而避免算法早熟；④與其他算法相融合，如粒子群優(yōu)化算法與免疫算法、遺傳算法、人工蜂群算法的結合[12].離散型問題中，解的每一個維度都對應一個尋優(yōu)方案，向單一gbest粒子學習的策略容易忽略解空間的一些優(yōu)秀‘單元’，同時也容易喪失粒子多樣性而迅速陷入局部最優(yōu).針對離散型物流規(guī)劃模型解空間存在多目標、多維度的特點，采用粒子不同維度向解空間其他優(yōu)秀粒子合作學習的方式，構建合作學習粒子群算法對多目標離散型物流規(guī)劃問題進行尋優(yōu)求解.

1 多目標物流規(guī)劃模型構建

1.1 基于客戶滿意度與服務成的物流中心選址模型描述

選擇由I個工廠、J個物流中心和K個客戶組成的典型三級物流網絡進行選址研究.該物流網絡服務于單一產品，其物流方式是工廠先將各自生產的貨品運輸到物流中心，再經過物流中心集中配貨后運送給不同客戶.工廠Fi(i=1,2,…,I)產量充足，客戶Ck(k=1,2,…,K)的需求確定，備選物流中心Dj(j=1,2,…,J)為聯系工廠與客戶的中間節(jié)點.假設為了便于管理，在該物流網絡中一個工廠只向一個物流中心供貨，一個客戶也只接受一個物流中心的服務.此時，物流網絡的規(guī)劃就涉及兩個問題:

1) 物流中心的選址 在J個備選物流中心中選擇若干個建設并使用.

2) 物流分派的制定 分別確定為每個工廠Fi與客戶Ck服務的物流中心Dj.

1.2 客戶滿意度函數

時效性是衡量物流系統(tǒng)的一個重要指標，它反映了物流系統(tǒng)為客戶提供物流服務的能力，也體現了該物流系統(tǒng)的市場競爭力.物流中心Dj在客戶Ck要求的時間內滿足其物流服務的概率表達式為

Pij=P(tij≤ti)=

(1)

式中：Tij為產品由物流中心i到客戶j的運輸時間；dij為產品由物流中心i到客戶j的運輸距離；vij為產品由物流中心i到客戶j的運輸速度；ti為客戶要求的最大運輸時間；Fvij(*)為運輸車輛由物流中心i到客戶j的速度分布函數.

定義Pij為客戶j對物流中心i提供的物流服務滿意度，由若干個物流中心與若干個客戶組成的物流系統(tǒng)的總體物流服務滿意度為

(2)

式中：Ps為物流系統(tǒng)總體服務滿意度；qi為客戶i的產品需求量.

1.3 多目標物流選址模型數學表達式

物流選址-分派模型的目的是實現總成本最小及服務滿意度最高.建立的多目標物流選址模型為

maxTs(φij,φjk)=

(3)

(4)

s.t.

(5)

(6)

(7)

(8)

φj=0,1,j∈J

(9)

φij=0,1,i∈I,j∈J

(10)

φjk=0,1,j∈J,k∈K

(11)

式中：Fvijk(*)為車輛從工廠i經過物流中心j到達客戶k的速度分布函數，服從正態(tài)分布；Qj為備選物流中心j的物流容量；Qk為客戶k的產品需求量；φi為0-1變量，選擇物流中心j則為1，否則為0；φij為0-1變量，產品由工廠i經過物流中心j為1，否則為0；φjk為0-1變量，產品由物流中心j送達客戶k則為1，否則為0；cij為工廠i到物流中心j單位運輸費用；cjk為物流中心j到客戶k單位運輸費用；dij為工廠i到物流中心j的距離；djk為物流中心j到客戶k的距離；tk為客戶k要求的物流時間；xij為由工廠i送達物流中心j的產品量；xjk為物流中心j送達客戶k的產品量.

Ts(φij，φjk)為物流系統(tǒng)服務滿意度目標函數，運用到1.2中介紹到的計算方式；Tc(φi，φij，φjk)為物流系統(tǒng)成本目標函數，包括物流中心建設成本、工廠到物流中心的運輸成本和物流中心到客戶的運輸成本；約束條件表示每個客戶只由一個物流中心提供服務.

當存在一組解間不存在Pareto支配時，講其稱為多目標規(guī)劃的Pareto解.多目標函數處于沖突狀態(tài)時，不存在使得所有目標函數同時達到最大或者最小值的最優(yōu)解，此時我們只能尋求Pareto解.

2 粒子群算法編碼及改進

粒子群算法(PSO)是1995年由Kennedy和Eberhart提出的一種進化計算技術，源于對鳥群和魚群捕食等行為的模擬.目前，PSO及其改進算法已廣泛應用于函數優(yōu)化、神經網絡訓練、模糊系統(tǒng)控制、模式識別及工程應用等諸多領域，并被證明能夠以較小的計算代價獲得良好的優(yōu)化解.其核心內容為參數編碼、初始群體設計、適應度函數設計、進化操作設計與參數控制五部分.

2.1 粒子群優(yōu)化算法

算法中粒子有n個參數，種群包括m個粒子，第i個粒子演化到k代為xik={xi1k，xi2k,…,ximk}，i=1,2,…,m.根據算法適應度函數，計算出粒子當前最優(yōu)位置為pik={pi1k，pi2k,…,pimk}，以及群體最優(yōu)適應值，第i粒子下一步迭代速度與位置計算公式為

(12)

(13)

式中：i=1,2,…,m；j=1,2,…,n；s1為粒子自我認知學習系數；s2為粒子社會認知學習系數；r1，r2為(0,1)分布的隨機數;w為粒子變化慣性權重，它決定了粒子先前速度對當前速度的影響程度.

2.2 粒子群編碼設計

選址規(guī)劃模型中，有兩種粒子：位置粒子A與B、速度粒子VA與VB，其中粒子A與VA為J維，粒子B與VB為K維的浮點數(以典型三級物流網絡為例，假設模型中有I個工廠、J個備選物流中心和K個客戶).采用整數編碼形式，物流中心粒子的位數與備選物流中心的位數相對應.將J個備選物流中心按照I～J依次編號，物流中心粒子群第i個粒子演化到第t代時為Ai(t)={Ai1(t)，Ai2(t),…,Aiφ(t),…,AiJ(t)}.若粒子中Aiφ(t)位數值為n，則該位置為第n個被選中的物流中心，若該位置為0，則表示該位置的物流中心未被選中.

客戶粒子B按照I～K依次編號，第i個粒子演化到第t代為Bi(t)={Bi1(t)，Bi2(t),…,Biφ(t),…,BiK(t)}.

若Biφ(t)為n,則該客戶由選擇建立的第n號物流中心提供服務.

例如，在4個備選物流中心中選擇2個為4個分銷商進行服務時，物流中心選址、分派粒子A，B離散化后分別為

A={1，0，3,0}，B={1,3,1,3}

表示1號與3號備選物流中心被選中.其中1號物流中心為1,3號客戶服務，3號物流中心為2,4號客戶服務.此時A，B粒子對應的物流配送網絡結構圖見圖1.

圖1 物流選址規(guī)劃結構圖

2.3 算法改進及設計

經典粒子群算法中粒子分別向代表“認知部分”的pi(t)與“社會部分”pg(t)學習，由于組合優(yōu)化問題解空間中每個維度都是的一個解中的元素，“社會部分”單純向一個pg(t)學習很有可能錯過粒子某一維度的最優(yōu)解，導致“two steps forward,one step back”的現象.

提出的合作學習的方式對粒子群算法進行改進，該算法粒子“社會部分”不是向g(t)學習，而是粒子每一個維度d以一定的概率向粒子群中具有優(yōu)秀適應度值的粒子學習.在該算法中，速度更新公式為

(14)

式中：pdf(i)(t)為i粒子d維度學習的對象，為了保證粒子的多樣性學習對象也包括自身的pdi(t).對于粒子i的任意維度d，產生一個隨機數，如果該隨機數大于Pc則粒子i的d維度向自身的pdi(t)學習，如該隨機數小于Pc則粒子i的d維度則向pdf(i)(t)學習.在合作學習的多目標粒子群算法(CLMPSO)選擇學習粒子的方法為：①在粒子群中隨機選擇n個粒子；②以(Tc(i)>Tc(j))&&(Ts(i)Tc(j))&&(abs(Ts(i)-Ts(j))

與經典的PSO比較，提出的MCPOS采用粒子的不同維度分別向非劣解對應粒子的學習的策略，該方法操作簡單，計算復雜度小.采用向非劣解粒子學習的方式可以避免PSO算法存在的向gbest快速收斂的趨勢，擴展粒子的多樣性而避免收斂到局部最優(yōu)解,見圖2.針對不同維度的學習方式，尤其適合于存在眾多局部最優(yōu)的離散型問題求解.

圖2 PSO與MCPSO搜尋范圍圖

在傳統(tǒng)的PSO中，全局最優(yōu)gbest粒子與粒子歷史最優(yōu)pbest粒子決定了粒子的速度與搜索范圍.當gbest粒子與pbest粒子同時陷入局部最優(yōu)區(qū)域時，粒子很容易收斂到局部最優(yōu)解，見圖2b).然而文中提出的MCPOS中，粒子的各個維度分別向整個解空間中非劣解粒子學習，能夠擴展了粒子搜尋范圍，增加跳出局部最優(yōu)的可能性.

具體算法為：①初始化粒子的位置與速度，并設定粒子學習概率；②Whilei≤pSize，確定i粒子的維度d學習對象；③Whiled≤D，隨機選擇種群中的n個粒子，計算出對應粒子的物流成本與服務滿意度，并篩選出多目標非劣解；④隨機選擇非劣解粒子作為i粒子的維度d學習對象，更新粒子i各個維度的速度；⑤更新粒子群的位置；⑥判斷是否達到結束條件，如果沒有轉到步驟②，否則結束.

3 仿真實驗與算例分析

3.1 收斂特性仿真實驗

文中為了評估MCPOS運行效率，設計了一個類比實驗，比較本文的MCPOS算法與標準PSO算法、加入收縮因子的PSO算法(SPSO)，鄰域學習PSO(NPSO)，完全信息PSO算法(FIPSO-square)進行比較.引入3個常使用的Benchmark函數進行數值實驗，函數Sphere與Rosenbrock是連續(xù)單模態(tài)函數，Rastrigin與Griewank是典型的非線性多模態(tài)函數，二者具有廣泛的搜索空間，大量的局部最優(yōu)點和眾多尋優(yōu)障礙.表1為benchmark函數的定義和全局最優(yōu)解.實驗種群規(guī)模為30，函數維度為30，搜索范圍分別為：(-100,100)，(-2.048，2.048)，(-5.12,5.12)，(-600,600)，函數每次運行5 000代.

圖3～4為各種PSO處理單峰Benchmark函數的結果，由圖3～4可知，在單峰Benchmark函數中，經典PSO與SPSO算法收斂速度快、效果相對較好，MCPOS與其他算法在搜索前期都有一個下降的趨勢，5 000代的計算中與其他算法相比較優(yōu)勢并不明顯.圖5～6為多峰問題Rastrigin與Griewank函數的結果.由圖5～6可知，文中提出的算法具有明顯優(yōu)勢.這正是由于算法中粒子的各個維度采用了向不同粒子全面學習的策略，增加了粒子多樣性，從而增強跳出局部最優(yōu)的能力.

表1 Benchmark函數

圖3 30維Sphere函數收斂圖

圖4 30維Rosenbrock函數收斂圖

圖5 30維Rastrigin函數收斂圖

圖6 30維Griewank函數收斂圖

4 CLMPSO在離散型物流選址中的應用

4.1 模型相關參數

模型由1個工廠(I=1)、5個候選物流配送中心(J=5)與8個顧客需求點(K=8)組成.假設每備選物流中心建設成本都為1 000萬元，最大轉運量都為1 500 t.運輸產品的車輛的行駛速度服從均值為40 km/h、方差為10的正態(tài)分布，客戶要求配送時限都為8 h.其他相關數據見表2～7.

表2 客戶的需求期望值 t

表3 各個備選物流中心的處理費用 元/t

表4 工廠與備選物流中心的距離 km

表5 工廠與備選物流中心的單位運輸費用t·km/元

表6 備選物流中心與客戶的距離 km

4.2 選址規(guī)劃模型求解結果及分析

基于多目標粒子群算法的參數分別為：粒子種規(guī)模pSize=1 000；算法開始迭代慣性權重Wstart=0.95；算法開始迭代慣性權重Wend=0.4；PSO粒子自我認知加速系數c1=2；PSO粒子社會認知加速系數c2=2；MCPOS粒子社會學習概率Pc=0.5.

表7 備選物流中心與客戶的單位配送費用t·km/元

根據上述模型與算法進行求解，經過迭代能夠獲得穩(wěn)定的perato解，運算記錄的選址規(guī)劃方案的多目標非劣解見圖7.

圖7 多目標選址規(guī)劃實驗統(tǒng)計圖

由圖7可知，相對于傳統(tǒng)的PSO,采用合作學習的PSO在計算多目標物流選址問題時，在同樣的成本下能夠獲得服務滿意度更高尋優(yōu)結果.由于多目標離散型物流選址規(guī)劃屬于多峰值的NP-hard問題，傳統(tǒng)PSO粒子尋優(yōu)過程中很容易陷入局部最優(yōu)，在相同的服務滿意度下，獲得的最優(yōu)解花費的成本高于MCPOS.

采用MCPOS計算不同的物流規(guī)劃策略對其成本和服務滿意也會有所不同，表8為算法計算的其中兩種物流規(guī)劃方案.

表8 物流中心規(guī)劃模型計算結果

5 結 束 語

提出MCPOS解決物流選址規(guī)劃問題，從合作學習的角度對此類多目標離散型組合優(yōu)化問題提出解決方案，提出粒子的各個維度向不同的非劣解粒子進行學習，對于跳出局部最優(yōu)解具有很好的效果.與傳統(tǒng)的PSO相比，該算法增加了粒子多樣性，提高了解空間粒子的質量，能夠在滿足物流系統(tǒng)中客戶滿意度的前提下減少物流配送的距離及成本，從而提升物流的競爭力.

該算法采用在非劣解粒子中隨機選擇的方式，需要較長的計算時間和較大的收斂代數，因此采用何種粒子擇優(yōu)學習有待進一步研究.

[1]杜麗敬,李延暉.選址-庫存-路徑問題模型及其集成優(yōu)化算法[J].運籌與管理,2014(4):70-79.

[3]KUO M S. Optimal location selection for an international distribution center by using a new hybrid method[J]．Expert Systems with Applications,2011,38(6):720-724．

[4]PRODHON C, PRINS C. A survey of recent research on location-routing problems[J]. European Journal of Operational Research,2014,238(1):1-17.

[5]CAI Q, GONG M, MA L, et al. Greedy discrete particle swarm optimization for large-scale social network clustering[J]. Information Sciences,2015,316(41):503-516.

[6]EKSIOGLUA B, VURALB A V, REISMANC A. The vehicle routing problem: a taxonomic review[J]．Computers & Industrial Engineering，2009，57(4)：147-148．

[7]涂南,戴雯婧,麥合迪.基于進化算法的多目標閉環(huán)物流網絡設計[J].工業(yè)工程,2013,16(2):59-66.

[8]WANG N, LU J C, KVAM P. Reliability modeling in spatially distributed logistics systems[J]. Reliability, IEEE Transactions on,2006,55(3):525-534.

[9]胡丹丹,楊超,楊珺.設施數目不確定情況下的截流選址問題[J].工業(yè)工程與管理,2009,14(1):15-18.

[10]HAN W, YANG R H. Comparison study of several kinds of inertia weights for PSO[C]. Proc of 2010 IEEE IntConf on Informatics and Computing,Shanghai,2010.

[11]CHENG X U, HE X U, SUN L, et al. Feature selection for cancer classification based on neighborhood rough set and particle swarm optimization[J]. Journal of Chinese Computer Systems,2014,35(11)：252-258．

[12]THANGARAJ R, PANT M, ABRAHAM A, et al. Particle swarnq optimization: hybridization perspectives and experimental illustrations[J]．Applied Mathematics and Computation，2011,217(12)：520-525.

The Application on Multi-objective Logistics Location Based on Improved PSO

LONG Shengjie LIU Yanmin ZENGO Qingyu

(Zunyi Normal College, College of mathematics, Zunyi 563002, China)

Considering that the location of logistics center has great influence on the capacity of the logistics system, the logistics cost and logistics service capacity must therefore be considered when building a logistics location-allocation model. For the multi-objective location-allocation problem on logistics, this paper proposes a cooperative learning multi-objective particle swarm optimization algorithm of seeking for Perato dominant. The simulation result shows that the model is correct and effective, and the discrete multi-objective particle swarm optimization algorithm can effectively solve the multi-objective location-allocation problem.

logistics location; multi-objective optimization; Cooperative learning; particle swarm optimization; simulation

2017-03-29

*國家自然科學基金項目(71461027)、貴州省自然科學基金項目(KY[2014]295)、貴州省科技廳聯合基金項目(LH[2016]7028)、貴州省科技廳聯合基金項目(LH[2016]7029)、貴州省科學技術基金(LH[2015]7050)資助

TP301.4

10.3963/j.issn.2095-3844.2017.03.002

龍圣杰(1988—)：男，碩士，講師，主要研究領域為物流工程、系統(tǒng)仿真