基于改進(jìn)煙花算法的物流配送中心選址研究

李小川+劉媛華

摘要：利用煙花算法求解物流配送中心選址問題，但存在早熟收斂、搜索精度低、魯棒性較差的缺陷，為此提出一種改進(jìn)煙花算法SOFWA用于求解該問題。將人群搜索算法中的利己行為、利他行為和預(yù)動(dòng)行為引入煙花算法，以加強(qiáng)各煙花與最優(yōu)煙花之間的信息交互，從而增大最優(yōu)煙花的搜索領(lǐng)域；對(duì)煙花爆炸和變異過程中產(chǎn)生的無效煙花進(jìn)行剔除操作，提升算法運(yùn)行效率。仿真實(shí)驗(yàn)證明，改進(jìn)煙花算法在求解物流配送中心選址問題時(shí)有效避免了以上缺陷，相對(duì)于其它算法具有一定的優(yōu)越性。

關(guān)鍵詞關(guān)鍵詞：物流配送中心選址；煙花算法；預(yù)動(dòng)行為；無效火花剔除

DOIDOI：10.11907/rjdk.171772

中圖分類號(hào)：TP319

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2017）011015304

0引言

隨著科技的迅速發(fā)展，物流業(yè)已經(jīng)成為促進(jìn)國家經(jīng)濟(jì)發(fā)展和提高國民幸福指數(shù)的重要基礎(chǔ)產(chǎn)業(yè)[1]。對(duì)于許多公司而言，物流配送中心選址都是物流環(huán)節(jié)至關(guān)重要的一環(huán)，合理的物流配送中心選址方案可以節(jié)約物流成本并提高公司整體運(yùn)行效率。物流配送中心選址問題具有非線性、非凸性、復(fù)雜性和約束條件多且相互之間難以協(xié)調(diào)的特點(diǎn)，是典型的非線性規(guī)劃模型，也被證明為NP-hard問題。物流配送中心的建設(shè)規(guī)模一般較大，一旦確定就很難改變。因此，對(duì)物流配送中心選址問題進(jìn)行研究具有重要的理論和現(xiàn)實(shí)意義。

物流中心選址問題由Weber和Friedrich[2]于1929年首次提出，其求解難度隨著問題規(guī)模的增大而急劇增加。智能優(yōu)化方法在求解大規(guī)模物流配送中心選址問題時(shí)具有明顯優(yōu)勢(shì)。文獻(xiàn)[35]分別采用遺傳算法（Genetic Algorithm，GA）、粒子群算法（Particle Swarm Optimization，PSO）和蟻群算法（Ant Colony Optimization，ACO）求解物流配送中心選址問題，但是這3種方法求解物流配送中心選址問題易陷入早熟收斂，魯棒性較差。Wang Y[6] 等將遺傳算法中的交叉變異思想引入粒子群算法求解物流配送中心選址問題；馬毓嚀[7]等將免疫算法中“抗體記憶能力”的思想引入粒子群算法，提出了免疫粒子群算法，提高了求解的有效性；費(fèi)騰[8]等將細(xì)菌覓食的“趨化思想”概念加入人工魚群算法，提出了BFOAFSA算法，在求解物流配送中心選址問題時(shí)比魚群算法更加穩(wěn)定可靠。

煙花算法（Fireworks Algorithm，F(xiàn)WA）是由北京大學(xué)學(xué)者Tan和Zhu[9]于2010年受到煙花爆炸過程中產(chǎn)生不同爆炸半徑和火花個(gè)數(shù)的啟發(fā)而提出的一種新型智能優(yōu)化算法。該算法原理簡單明確、參數(shù)少、搜索效率高且較易實(shí)現(xiàn)，受到許多學(xué)者關(guān)注。Pei等[10]基于煙花產(chǎn)生的火花和高斯火花的坐標(biāo)信息評(píng)估解空間形狀，將形狀凸點(diǎn)作為當(dāng)前最優(yōu)位，從而加快了種群的收斂速度。Ding 等[11]提出了GPUFWA算法，對(duì)煙花爆炸半徑進(jìn)行改進(jìn)，在間隔一定迭代次數(shù)后對(duì)爆炸半徑進(jìn)行交互計(jì)算，加快了收斂速度。朱啟兵等[12]利用適應(yīng)值計(jì)算各煙花質(zhì)量，提出了引力搜索機(jī)制，并通過Benchmark 函數(shù)測(cè)試求解效能。目前尚無可用煙花算法求解物流配送中心選址問題相關(guān)研究，本文嘗試用煙花算法求解物流配送中心選址問題，并根據(jù)前期實(shí)驗(yàn)結(jié)果對(duì)煙花算法進(jìn)行改進(jìn)，引入SOA變異策略，即用人群搜索算法（Seeker Optimization Algorithm，SOA）中的利己行為、利他行為和預(yù)動(dòng)行為對(duì)除最優(yōu)值之外的煙花（以下簡稱煙花*）進(jìn)行擾動(dòng)，以改善煙花算法求解物流配送中心選址問題時(shí)易陷入局部最優(yōu)的問題，并對(duì)煙花爆炸和變異產(chǎn)生的無效火花進(jìn)行剔除，加快收斂速度。通過實(shí)驗(yàn)仿真及與其它算法對(duì)比，證明了改進(jìn)煙花算法的有效性和優(yōu)越性。

3.3無效煙花剔除

煙花算法相對(duì)其它智能算法具有爆發(fā)性的特點(diǎn)，通常具有較快的收斂速度。然而采用隨機(jī)鍵編碼時(shí)煙花爆炸也極易產(chǎn)生無效火花，從而降低收斂速度。比如某煙花爆炸產(chǎn)生的兩個(gè)火花為X1=[8，2，12，4，7，19]和X2=[8，4，12，2，7，19]，兩個(gè)火花粒子排序不同，但實(shí)際選址相同，其中一個(gè)火花對(duì)算法收斂沒有作出任何貢獻(xiàn)，為無效煙花，在實(shí)際運(yùn)算中往往會(huì)產(chǎn)生更多無效煙花。本文將無效煙花直接剔除以降低單次迭代運(yùn)行時(shí)間，在有限時(shí)間內(nèi)給予了更多煙花爆炸機(jī)會(huì)，從而加快收斂速度。

3.4改進(jìn)算法步驟

算法步驟如下：

Step1：初始化各參數(shù)，設(shè)置煙花個(gè)數(shù)N，基本爆炸半徑A，基本火花個(gè)數(shù)S，火花個(gè)數(shù)約束常數(shù)a和b，高斯變異煙花數(shù)l，最大迭代次數(shù)G，當(dāng)前迭代t=1。

Step2：初始化N個(gè)煙花。

Step3：由式（9）-（11）計(jì)算煙花爆炸半徑和火花個(gè)數(shù)，由式（7）計(jì)算爆炸火花，對(duì)超出邊界的維度根據(jù)式（8）有效映射。

Step4：由式（12）計(jì)算高斯變異火花，根據(jù)式（8）將超出邊界的維度映射到可行域。

Step5：由式（15）-（18）對(duì)煙花*進(jìn)行SOA變異，根據(jù)式（8）將超出邊界的維度映射到可行域。

Step6：剔除以上火花中的無效火花。

Step7：計(jì)算火花粒子的適應(yīng)度值，將所有煙花和火花粒子按適應(yīng)度值進(jìn)行升序排列，第一個(gè)粒子直接保留至下一代，根據(jù)式（13）、（14）選擇剩余的N-1個(gè)粒子，更新下一代煙花。

Step8：若t

4仿真實(shí)驗(yàn)結(jié)果及分析

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

為了驗(yàn)證本文所提改進(jìn)煙花算法求解物流配送中心選址問題的效能，本文利用MatLab R2012a軟件，以文獻(xiàn)[7]中的全國31個(gè)城市的位置坐標(biāo)和貨物需求量（見表1）為例進(jìn)行仿真實(shí)驗(yàn)，以運(yùn)輸距離和需求量的乘積作為適應(yīng)度函數(shù)，并對(duì)煙花算法、改進(jìn)煙花算法和文獻(xiàn)[7]中所提的免疫粒子群算法IMPSO求得的結(jié)果進(jìn)行對(duì)比。算法參數(shù)為：SOFWA，煙花個(gè)數(shù)為5，基本爆炸半徑A=2，基本爆炸火花數(shù)S=50，高斯變異煙花數(shù)l=5，a=0.04，b=0.6；免疫粒子群算法IMPSO參數(shù)參考文獻(xiàn)[7]。3種算法最大迭代次數(shù)均為100，每種算法獨(dú)立運(yùn)行20次。

4.2實(shí)驗(yàn)結(jié)果分析

3種算法求解物流配送中心選址問題的統(tǒng)計(jì)結(jié)果如表2所示，F(xiàn)WA、IMPSO和SOFWA求得的最優(yōu)物流配送中心選址方案如圖1、圖2所示，F(xiàn)WA和SOFWA分別運(yùn)行20次所得最優(yōu)選址結(jié)果對(duì)比如圖3所示。FWA求得的最優(yōu)值為555 333.30，收斂代數(shù)為34，SOFWA求得的最優(yōu)值為549 125.23，收斂代數(shù)為21，可見SOFWA在求解物流配送中心選址問題的尋優(yōu)精度及運(yùn)行效率方面都明顯優(yōu)于FWA。在平均最優(yōu)值、平均收斂次數(shù)方面，SOFWA的結(jié)果也明顯優(yōu)于FWA；在方差方面，SOFWA的結(jié)果則比FWA低一個(gè)數(shù)量級(jí)，說明SOFWA的穩(wěn)定性較FWA明顯提高?？傮w而言，改進(jìn)煙花算法較煙花算法在求解物流中心選址問題時(shí)的性能有較大提升。

IMPSO和SOFWA分別運(yùn)行20次所得最優(yōu)選址結(jié)果對(duì)比如圖4所示，兩種算法求得最優(yōu)值均為549 125.23，但是在20次運(yùn)行中，SOFWA擊中最優(yōu)值17次，而IMPSO僅擊中12次。在平均最優(yōu)值和方差方面，IMPSO求得結(jié)果分別為554 125.22和93.25，SOFWA求得結(jié)果分別為550 993.26和17.40，均小于IMPSO所得結(jié)果。說明SOFWA在求解物流中心選址問題時(shí)比IMPSO具有更好的魯棒性。另外，SOFWA的平均收斂代數(shù)要比IMPSO少5.6。在平均收斂時(shí)間方面，SOFWA比IMPSO節(jié)省了11.14s，說明SOFWA的求解效率更高。以上分析表明，SOFWA可以作為一種求解物流配送中心選址問題的有效方法。

5結(jié)語

本文首次嘗試用煙花算法求解物流配送中心選址問題，并在煙花算法中引入人群搜索算法中的利己行為、利他行為和預(yù)動(dòng)行為，以改進(jìn)基本煙花算法求解物流中心選址問題時(shí)存在的早熟收斂、搜索精度低、魯棒性差的不足。對(duì)無效火花進(jìn)行剔除以提升煙花算法運(yùn)行效率，節(jié)省單代運(yùn)行時(shí)間，從而節(jié)省收斂時(shí)間。通過實(shí)驗(yàn)仿真驗(yàn)證了改進(jìn)煙花算法求解物流配送中心選址問題的有效性，進(jìn)一步與相關(guān)文獻(xiàn)中的其它算法進(jìn)行比較，表明改進(jìn)煙花算法具有更好的穩(wěn)定性。下一步的研究目標(biāo)是，更合理地設(shè)置改進(jìn)煙花算法的參數(shù)，并且嘗試將其應(yīng)用于物流配送車輛路徑優(yōu)化問題求解中。

參考文獻(xiàn)參考文獻(xiàn)：

[1]馬祥麗，張惠珍，馬良.帶時(shí)間窗物流配送車輛路徑問題的蝙蝠算法[J].計(jì)算機(jī)工程與應(yīng)用，2016（11）：254258，264.

[2]WEBER A，F(xiàn)RIEDRICH C J.Alfred weber′s theory of the location of industries[M].University of Chicago Press，1929.

[3]禤文怡，汪波，袁建強(qiáng).基于遺傳算法和指標(biāo)滿意度求解的第三方物流企業(yè)物流配送中心選址方法[J].運(yùn)籌與管理，2004，13（2）：139144.

[4]黃敏鎂.粒子群算法在物流配送中心選址中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（4）：212214.

[5]李文超.用蟻群算法求解物流配送中心選址優(yōu)化問題[J].物流技術(shù)，2014，33（9）：276277，295.

[6]WANG YONG，MA XIAOLEI，XU MAOZENG.Twoechelon logistics distribution region partitioning problem based on a hybrid particle swarm optimizationgenetic algorithm[J].Expert Systems With Applications，2015，42（12）：50195031.

[7]馬毓嚀，許峰.免疫粒子群算法及其在物流配送中心選址問題中的應(yīng)用研究[J].軟件導(dǎo)刊，2013，12（12）：7174.

[8]費(fèi)騰，張立毅，陳雷.配送中心選址問題的BFOAFSA算法研究[J].計(jì)算機(jī)工程與應(yīng)用，2015，51（23）：15，10.

[9]TAN YING，ZHU YUANCHUN.Fireworks algorithm for optimization[C].Berlin：Springer，2010：355364.

[10]YAN PEI，ZHENG SAOQIU，TAN YING，et al.An empirical study on influence of approximation approaches on enhancing fireworks algorithm[C].IEEE International Conference on Systems，Man，and Cybernetics. Seoul，South Korea，2012：13221327.

[11]DING KE，ZHENG SHAOQIU，TAN YING.A GPUbased parallel fireworks algorithm for optimization[C].Proceedings of the Fifteenth Annual Conference on Genetic and Evolutionary Computation Conference，2013：916.

[12]朱啟兵，王震宇，黃敏.帶有引力搜索算子的煙花算法[J].控制與決策，2016，31（10）：18531859.

[13]杜振鑫.基于種群進(jìn)化速度的動(dòng)態(tài)煙花算法[J].微電子學(xué)與計(jì)算機(jī)，2016，33（10）：2427.

責(zé)任編輯（責(zé)任編輯：孫娟）endprint