劉 敏

(廣西外國語學(xué)院信息工程學(xué)院 廣西 南寧 530222)

0 引 言

Alfred Weber于1909年首次提出物流配送中心的選址理論[1]，隨著物流系統(tǒng)的發(fā)展，該問題受到眾多學(xué)者的關(guān)注和研究。配送中心的選址問題是物流系統(tǒng)中的重要環(huán)節(jié)，選址模型是非凸且?guī)в屑s束的非線性規(guī)劃模型。隨著對選址問題的研究，已出現(xiàn)多種求解方法，傳統(tǒng)的方法：層次分析法、非線性規(guī)劃、線性規(guī)劃和重心法等[2-3]，但傳統(tǒng)的方法在求解大規(guī)模選址問題時很難找到最佳的配送中心。隨著智能算法的發(fā)展，很多學(xué)者提出新的求解方式，如：遺傳算法[4]、差分進化算法[5]、細菌覓食改進的人工魚群算法[6]、基于多種群搜索的PSO的物流配送中心選址求解[7]、布谷鳥搜索算法求解物流配送中心選址問題[8]、狼群算法在物流配送中心供需優(yōu)化選址仿真[9]等。雖然這些算法取得了一定的成效，但普遍存在精度不高、收斂速度慢和求解的規(guī)劃較小等缺點。如文獻[6]研究了20個需求點3個配送中心求解的選址方案精度較差；文獻[7]僅研究了25個需求點12個配送中心求解的選址方案，規(guī)模較小難以驗證算法的有效性；文獻[8]研究了20個需求點3個配送中心求解的選址方案精度較高，但對規(guī)模稍大的40個需求點6個配送中心求解的選址方案精度較差。

針對這些缺點，本文提出一種改進的花朵授粉算法求解中等規(guī)模的物流配送中心選址問題。通過實驗仿真，驗證了所提出算法的求解精度及速度，對中等規(guī)模的物流選址問題提供了較好的解決方案。

1 物流配送中心選址問題的數(shù)學(xué)模型

本文研究的是在給定的n個需求點中搜索m個配送中心，使得m個配送中心到其配送范圍的需求點運輸成本(距離)最短。同時滿足一些約束條件：假設(shè)m個配送中心的貨物供應(yīng)量可以滿足其配送范圍貨物需求點的要求；每一個貨物需求點只能由一個配送中心負責(zé)配送。因此，物流配送中心選址問題的數(shù)學(xué)模型為：

(1)

(2)

uij≤hji∈M,j∈N

(3)

(4)

hj∈{0,1}uij∈{0,1}i∈Mj∈N

(5)

M={j|j=1,2,…,m},N={j|j=1,2,…,n}

(6)

式(1)為評價函數(shù)，cost表示代價函數(shù)，m表示配送中心的數(shù)目，n表示需求點的數(shù)目，needj表示第j個需求點的需求量，distij表示配送中心i與需求點j之間的距離，uij為1時表示第j個需求點的貨物由第i個配送中心配送。式(2)-式(6)為約束條件，式(2)約束一個需求點的貨物只能由一個配送中心配送，式(3)約束了每個需求點必須有一個配送中心配送，式(4)表示配送中心選擇的貨物需求點數(shù)量。

2 基本的花朵授粉算法

花朵授粉算法FPA(Flower Pollination Algorithm)由Yang于2012年提出[10]，該算法模擬自然界花朵傳粉的過程，其基于以下4個基本規(guī)則[11]：

1) 生物授粉和交叉授粉可以看作是全局授粉過程，攜帶花粉的授粉者服從Levy飛行的方式移動。

2) 非生物自花授粉是局部授粉過程。

3) 花的恒常性被認為繁值概率，它與涉及兩朵花的相似性成比例關(guān)系。

4) 轉(zhuǎn)換概率p∈[0,1]控制局部授粉與全局授粉的相互作用，轉(zhuǎn)換概率對局部授粉有輕微偏倚。

基于上述規(guī)則，花朵授粉算法的迭代公式為：

(7)

(8)

式中：λ=3/2，Γ(λ)是標(biāo)準(zhǔn)的伽馬函數(shù)。

(9)

3 改進的花朵授粉算法求解選址問題

3.1 編碼與解碼

物流配送中心選址問題是個離散問題，因此需要將花朵授粉算法進行相應(yīng)的修改，花粉的位置pollen=(x1,x2,…,xd)，其長度d為需求點的數(shù)量。然后對pollen中的元素進行升序或降序排序得到一組下標(biāo)值，再根據(jù)配送中心的數(shù)目進行相應(yīng)的選擇。例如，對于10個需求點3個配送中心的配送問題如表1所示。

表1 花粉的編碼

3.2 改進的花朵授粉算法

在基本的花朵授粉算法中，花粉的位置通過概率p由式(7)和式(9)進行更新，種群中的個體并沒有進行信息交互，針對花朵授粉算法的不足，結(jié)合遺傳算子的選擇、交叉和逆轉(zhuǎn)操作進行局部搜索，提出如下改進的花朵授粉算法MFPA(Modified Flower Pollination Algorithm)算法，遺傳算子操作如下：

1) 輪盤賭選擇，優(yōu)秀的花粉以較高的概率遺傳到下一代。

2) 交叉操作：設(shè)兩個花粉i和j的位置為polleni=(xi1,xi2,…,xid,xid+1,…,xie,…,xin)，pollenj=(xj1,xj2,…,xjd,xjd+1,…,xje,…,xjn)，隨機產(chǎn)生一個1到n之間的整數(shù)d將兩個花粉進行交叉，得到polleni=(xi1,xi2,…,xid,xjd+1,…,xje,…,xjn)與pollenj=(xj1,xj2,…,xjd,xid+1,…,xie,…,xin)。

MFPA整個算法的流程如下：

Step1初始化各參數(shù)及花粉Sol的位置，計算目標(biāo)函數(shù)值Fitness、[fmin,I]=min(Fitness)最佳位置best=Sol(I,:)。

Step2開始循環(huán)迭代，對每一個花粉，如果rand>p，則按式(7)搜索，否則按式(9)搜索。

Step3評估每個花粉的值Fnew，如果Fnew

Step4利用遺傳算子進行局部搜索Nn次。重新評估每個花粉的值Fnew，如果Fnew

Step5如果滿足終止條件，算法結(jié)束，否則跳到Step 2。

4 仿真實驗與分析

為驗證所提出的算法在求解物流配送中心選址的正確性及有效性，采用文獻[4]中的選址算例。所有的實驗運行在操作系統(tǒng)Windows 7，處理器為Celeron(R)雙核CPU T3100, 1.90 GHZ 、內(nèi)存為2 GB的PC上，以MATLAB R2010a編寫代碼。參數(shù)設(shè)置為：種群規(guī)模20，p=0.8(對局部搜索進行適當(dāng)?shù)膬A斜，故將其值適當(dāng)取大一些)，Nn=5，總迭代次數(shù)為20，pc=0.8(遺傳算法的交叉概率)。FPA和MFPA獨立運行30次，所求的結(jié)果如表2所示。

表2 各種算法的比較結(jié)果

由表2可知，F(xiàn)PA求解物流選址問題的正確性，與文獻[6]和文獻[8]結(jié)果相符，由于問題的規(guī)模較小，F(xiàn)PA與MFPA求解的精度相同，MFPA在求解精度上的優(yōu)勢難以突顯，將其各自運行30次的平均進化曲線比較圖如圖1所示，可見MFPA收斂速度較快，尋址方案如圖2所示。

圖1 FPA和MPFA運行30次的平均進化曲線對比圖

再采用文獻[8]中40個需求點和6個配送中心，為了比較的公平性，參數(shù)與其設(shè)置相同：種群規(guī)模200，總迭代次數(shù)為50，其他參數(shù)設(shè)置與實驗一相同。FPA和MFPA獨立運行30次所求結(jié)果如表3所示。

由表3可知，本文算法求解的尋址方案比文獻[8]優(yōu)越很多，F(xiàn)PA和MFPA都找到了該問題的最優(yōu)配送方案。費用(距離)比文獻[8]減少了1 492.37，配送中心及配送的范圍發(fā)生了變化，配送中心及配送范圍如表4所示，尋址方案如圖3所示。雖然FPA和MFPA求解的最優(yōu)值一樣，但從最差值、平均值和方差幾個數(shù)據(jù)可知MFPA的魯棒性較好。兩種算法運行30次的平均收斂曲線如圖4所示，可見MFPA效果較好。

表4 MFPA的尋址方案

圖3 FPA和MPFA的尋址方案

圖4 FPA和MPFA運行30次的平均進化曲線對比圖

進一步采用文獻[9]中50個需求點和10個配送中心，為了比較的公平性，參數(shù)與其設(shè)置相同：種群規(guī)模20，總迭代次數(shù)為50，其他參數(shù)設(shè)置與實驗一相同。FPA和MFPA獨立運行30次所求結(jié)果如表5所示。

表5 各種算法的比較結(jié)果

由表5可知，MFPA比FPA、PSO、GA、DEA、BWPA的最優(yōu)值好，比IWPA的最優(yōu)值稍差，但MFPA的平均值比IWPA略低，說明MFPA魯棒性較好。FPA與MFPA的尋址方案如圖5和圖6所示，對于規(guī)模稍大的尋址問題，F(xiàn)PA求解的結(jié)果遠不如MFPA，它們最優(yōu)值的進化曲線如圖7所示?？梢娨?guī)模越大，MFPA的優(yōu)勢越明顯。

圖5 FPA求解50個需求點10個配送中心的尋址方案

圖6 MFPA求解50個需求點10個配送中心的尋址方案

圖7 FPA和MFPA最優(yōu)值的進化曲線對比圖

最后將該算法應(yīng)用到100個需求點20個配送中心的選址問題。城市坐標(biāo)及對應(yīng)的需求如表6所示。參數(shù)設(shè)置：種群規(guī)模20，總迭代次數(shù)為50，其他參數(shù)設(shè)置與實驗一相同。

表6 100個城市的坐標(biāo)及需求量

續(xù)表6

FPA與MFPA獨立運行20次，兩種算法的比較結(jié)果如表7所示，無論從最優(yōu)值、最差值還是平均值和方差，MFPA結(jié)果比FPA好。再次驗證對于選址規(guī)模越大，MFPA性能越優(yōu)越。MFPA的配送方案如圖8所示，F(xiàn)PA和MFPA最優(yōu)值的進化曲線如圖9所示。通過上述4組實驗表明了所提出的MFPA的可行性及有效性。

圖8 MFPA求解100個需求點20個配送中心的尋址方案

圖9 FPA和MFPA最優(yōu)值的進化曲線對比圖

表7 兩種算法的比較結(jié)果

5 結(jié) 語

本文針對當(dāng)前算法求解物流配送中心選址問題時，普遍存在求解精度低、收斂速度慢及規(guī)模較小等缺陷，提出了一種改進的花朵授粉算法求解物流配送中心選址問題，將花朵授粉算法進行全局搜索的同時融合遺傳算子進行局部搜索。通過兩者的結(jié)合及多組不同規(guī)模的仿真實驗表明了改進的花朵授粉算法在求解物流配送中心選址問題的有效性。