基于改進煙花算法的物流配送中心選址研究

李小川+劉媛華

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

關鍵詞關鍵詞：物流配送中心選址；煙花算法；預動行為；無效火花剔除

DOIDOI：10.11907/rjdk.171772

中圖分類號：TP319

文獻標識碼：A文章編號文章編號：16727800（2017）011015304

0引言

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

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

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

3.3無效煙花剔除

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

3.4改進算法步驟

算法步驟如下：

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

Step2：初始化N個煙花。

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

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

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

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

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

Step8：若t

4仿真實驗結果及分析

4.1實驗仿真

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

4.2實驗結果分析

3種算法求解物流配送中心選址問題的統計結果如表2所示，FWA、IMPSO和SOFWA求得的最優物流配送中心選址方案如圖1、圖2所示，FWA和SOFWA分別運行20次所得最優選址結果對比如圖3所示。FWA求得的最優值為555 333.30，收斂代數為34，SOFWA求得的最優值為549 125.23，收斂代數為21，可見SOFWA在求解物流配送中心選址問題的尋優精度及運行效率方面都明顯優于FWA。在平均最優值、平均收斂次數方面，SOFWA的結果也明顯優于FWA；在方差方面，SOFWA的結果則比FWA低一個數量級，說明SOFWA的穩定性較FWA明顯提高。總體而言，改進煙花算法較煙花算法在求解物流中心選址問題時的性能有較大提升。

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

5結語

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

參考文獻參考文獻：

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

[2]WEBER A，FRIEDRICH C J.Alfred weber′s theory of the location of industries[M].University of Chicago Press，1929.

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

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

[5]李文超.用蟻群算法求解物流配送中心選址優化問題[J].物流技術，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]馬毓嚀，許峰.免疫粒子群算法及其在物流配送中心選址問題中的應用研究[J].軟件導刊，2013，12（12）：7174.

[8]費騰，張立毅，陳雷.配送中心選址問題的BFOAFSA算法研究[J].計算機工程與應用，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].微電子學與計算機，2016，33（10）：2427.

責任編輯（責任編輯：孫娟）endprint