改进的花朵授粉算法在物流配送中心选址问题中的应用

刘 敏

(广西外国语学院信息工程学院 广西 南宁 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 结 语

本文针对当前算法求解物流配送中心选址问题时，普遍存在求解精度低、收敛速度慢及规模较小等缺陷，提出了一种改进的花朵授粉算法求解物流配送中心选址问题，将花朵授粉算法进行全局搜索的同时融合遗传算子进行局部搜索。通过两者的结合及多组不同规模的仿真实验表明了改进的花朵授粉算法在求解物流配送中心选址问题的有效性。