改進(jìn)的花朵授粉算法在物流配送中心選址問題中的應(yīng)用

劉 敏

(廣西外國語學(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]、差分進(jìn)化算法[5]、細(xì)菌覓食改進(jìn)的人工魚群算法[6]、基于多種群搜索的PSO的物流配送中心選址求解[7]、布谷鳥搜索算法求解物流配送中心選址問題[8]、狼群算法在物流配送中心供需優(yōu)化選址仿真[9]等。雖然這些算法取得了一定的成效，但普遍存在精度不高、收斂速度慢和求解的規(guī)劃較小等缺點(diǎn)。如文獻(xiàn)[6]研究了20個需求點(diǎn)3個配送中心求解的選址方案精度較差；文獻(xiàn)[7]僅研究了25個需求點(diǎn)12個配送中心求解的選址方案，規(guī)模較小難以驗(yàn)證算法的有效性；文獻(xiàn)[8]研究了20個需求點(diǎn)3個配送中心求解的選址方案精度較高，但對規(guī)模稍大的40個需求點(diǎn)6個配送中心求解的選址方案精度較差。

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

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

本文研究的是在給定的n個需求點(diǎn)中搜索m個配送中心，使得m個配送中心到其配送范圍的需求點(diǎn)運(yùn)輸成本(距離)最短。同時滿足一些約束條件：假設(shè)m個配送中心的貨物供應(yīng)量可以滿足其配送范圍貨物需求點(diǎn)的要求；每一個貨物需求點(diǎn)只能由一個配送中心負(fù)責(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表示需求點(diǎn)的數(shù)目，needj表示第j個需求點(diǎn)的需求量，distij表示配送中心i與需求點(diǎn)j之間的距離，uij為1時表示第j個需求點(diǎn)的貨物由第i個配送中心配送。式(2)-式(6)為約束條件，式(2)約束一個需求點(diǎn)的貨物只能由一個配送中心配送，式(3)約束了每個需求點(diǎn)必須有一個配送中心配送，式(4)表示配送中心選擇的貨物需求點(diǎn)數(shù)量。

2 基本的花朵授粉算法

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

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

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

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

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

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

(7)

(8)

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

(9)

3 改進(jìn)的花朵授粉算法求解選址問題

3.1 編碼與解碼

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

表1 花粉的編碼

3.2 改進(jìn)的花朵授粉算法

在基本的花朵授粉算法中，花粉的位置通過概率p由式(7)和式(9)進(jìn)行更新，種群中的個體并沒有進(jìn)行信息交互，針對花朵授粉算法的不足，結(jié)合遺傳算子的選擇、交叉和逆轉(zhuǎn)操作進(jìn)行局部搜索，提出如下改進(jì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)，隨機(jī)產(chǎn)生一個1到n之間的整數(shù)d將兩個花粉進(jìn)行交叉，得到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利用遺傳算子進(jìn)行局部搜索Nn次。重新評估每個花粉的值Fnew，如果Fnew

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

4 仿真實(shí)驗(yàn)與分析

為驗(yàn)證所提出的算法在求解物流配送中心選址的正確性及有效性，采用文獻(xiàn)[4]中的選址算例。所有的實(shí)驗(yàn)運(yùn)行在操作系統(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(對局部搜索進(jìn)行適當(dāng)?shù)膬A斜，故將其值適當(dāng)取大一些)，Nn=5，總迭代次數(shù)為20，pc=0.8(遺傳算法的交叉概率)。FPA和MFPA獨(dú)立運(yùn)行30次，所求的結(jié)果如表2所示。

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

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

圖1 FPA和MPFA運(yùn)行30次的平均進(jìn)化曲線對比圖

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

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

表4 MFPA的尋址方案

圖3 FPA和MPFA的尋址方案

圖4 FPA和MPFA運(yùn)行30次的平均進(jìn)化曲線對比圖

進(jìn)一步采用文獻(xiàn)[9]中50個需求點(diǎn)和10個配送中心，為了比較的公平性，參數(shù)與其設(shè)置相同：種群規(guī)模20，總迭代次數(shù)為50，其他參數(shù)設(shè)置與實(shí)驗(yàn)一相同。FPA和MFPA獨(dú)立運(yùn)行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é)果遠(yuǎn)不如MFPA，它們最優(yōu)值的進(jìn)化曲線如圖7所示?？梢娨?guī)模越大，MFPA的優(yōu)勢越明顯。

圖5 FPA求解50個需求點(diǎn)10個配送中心的尋址方案

圖6 MFPA求解50個需求點(diǎn)10個配送中心的尋址方案

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

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

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

續(xù)表6

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

圖8 MFPA求解100個需求點(diǎn)20個配送中心的尋址方案

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

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

5 結(jié) 語

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