改進(jìn)粒子群算法在多目標(biāo)物流選址中的應(yīng)用*

龍圣杰 劉衍民 曾慶雨

(遵義師范學(xué)院數(shù)學(xué)學(xué)院 遵義 563002)

改進(jìn)粒子群算法在多目標(biāo)物流選址中的應(yīng)用*

龍圣杰 劉衍民 曾慶雨

(遵義師范學(xué)院數(shù)學(xué)學(xué)院 遵義 563002)

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

物流選址規(guī)劃；多目標(biāo)；合作學(xué)習(xí)；粒子群算法；仿真

0 引 言

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

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

1 多目標(biāo)物流規(guī)劃模型構(gòu)建

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

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

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

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

1.2 客戶滿意度函數(shù)

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

Pij=P(tij≤ti)=

(1)

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

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

(2)

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

1.3 多目標(biāo)物流選址模型數(shù)學(xué)表達(dá)式

物流選址-分派模型的目的是實現(xiàn)總成本最小及服務(wù)滿意度最高.建立的多目標(biāo)物流選址模型為

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īng)過物流中心j到達(dá)客戶k的速度分布函數(shù)，服從正態(tài)分布；Qj為備選物流中心j的物流容量；Qk為客戶k的產(chǎn)品需求量；φi為0-1變量，選擇物流中心j則為1，否則為0；φij為0-1變量，產(chǎn)品由工廠i經(jīng)過物流中心j為1，否則為0；φjk為0-1變量，產(chǎn)品由物流中心j送達(dá)客戶k則為1，否則為0；cij為工廠i到物流中心j單位運輸費用；cjk為物流中心j到客戶k單位運輸費用；dij為工廠i到物流中心j的距離；djk為物流中心j到客戶k的距離；tk為客戶k要求的物流時間；xij為由工廠i送達(dá)物流中心j的產(chǎn)品量；xjk為物流中心j送達(dá)客戶k的產(chǎn)品量.

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

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

2 粒子群算法編碼及改進(jìn)

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

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

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

(12)

(13)

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

2.2 粒子群編碼設(shè)計

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

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

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

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

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

表示1號與3號備選物流中心被選中.其中1號物流中心為1,3號客戶服務(wù)，3號物流中心為2,4號客戶服務(wù).此時A，B粒子對應(yīng)的物流配送網(wǎng)絡(luò)結(jié)構(gòu)圖見圖1.

圖1 物流選址規(guī)劃結(jié)構(gòu)圖

2.3 算法改進(jìn)及設(shè)計

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

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

(14)

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

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

圖2 PSO與MCPSO搜尋范圍圖

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

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

3 仿真實驗與算例分析

3.1 收斂特性仿真實驗

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

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

表1 Benchmark函數(shù)

圖3 30維Sphere函數(shù)收斂圖

圖4 30維Rosenbrock函數(shù)收斂圖

圖5 30維Rastrigin函數(shù)收斂圖

圖6 30維Griewank函數(shù)收斂圖

4 CLMPSO在離散型物流選址中的應(yīng)用

4.1 模型相關(guān)參數(shù)

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

表2 客戶的需求期望值 t

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 束 語

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

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

[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]涂南,戴雯婧,麥合迪.基于進(jìn)化算法的多目標(biāo)閉環(huán)物流網(wǎng)絡(luò)設(shè)計[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]胡丹丹,楊超,楊珺.設(shè)施數(shù)目不確定情況下的截流選址問題[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

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

TP301.4

10.3963/j.issn.2095-3844.2017.03.002

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