改進的花朵授粉算法在物流配送中心選址問題中的應用

劉 敏

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

0 引 言

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

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

1 物流配送中心選址問題的數學模型

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

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

2 基本的花朵授粉算法

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

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

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

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

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

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

(7)

(8)

式中：λ=3/2，Γ(λ)是標準的伽馬函數。

(9)

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

3.1 編碼與解碼

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

表1 花粉的編碼

3.2 改進的花朵授粉算法

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

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

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

MFPA整個算法的流程如下：

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

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

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

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

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

4 仿真實驗與分析

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

表2 各種算法的比較結果

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

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

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

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

表4 MFPA的尋址方案

圖3 FPA和MPFA的尋址方案

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

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

表5 各種算法的比較結果

由表5可知，MFPA比FPA、PSO、GA、DEA、BWPA的最優值好，比IWPA的最優值稍差，但MFPA的平均值比IWPA略低，說明MFPA魯棒性較好。FPA與MFPA的尋址方案如圖5和圖6所示，對于規模稍大的尋址問題，FPA求解的結果遠不如MFPA，它們最優值的進化曲線如圖7所示。可見規模越大，MFPA的優勢越明顯。

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

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

圖7 FPA和MFPA最優值的進化曲線對比圖

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

表6 100個城市的坐標及需求量

續表6

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

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

圖9 FPA和MFPA最優值的進化曲線對比圖

表7 兩種算法的比較結果

5 結 語

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