变邻域人工蜂群算法求解配送中心选址问题*

姜 婷

(1.合肥工业大学管理学院，安徽 合肥 230009；2.中共安徽省委党校(安徽行政学院)，安徽 合肥 230022)

物流配送中心选址问题属于NP-hard问题，国内外学者尝试了多种方法进行求解，其中群智能优化算法因采用启发式求近似最优解的思路，在求解规模较大的配送中心选址问题中具有一定的优势.例如，蚁群(Ant Colony，AC)算法[1]、微粒群(Particle Swarm Optimization，PSO)算法[2]、遗传算法(Genetic Algorithm，GA)[3]等传统群智能算法和一些新型智能优化算法[4-13]广泛应用于求解配送中心选址问题，获得了较好的仿真实验结果.新型智能优化算法中的人工蜂群(Artificial Bee Colony，ABC)算法[13]，是Karboga受蜜蜂的觅食行为启发于2005年提出的，该算法起初是用来解决连续空间的多维数值计算问题，后来被拓展到离散和组合优化领域.仿真实验结果表明[14]，ABC算法的性能优于差分(Differential Evolution，DE)算法、GA和PSO算法等著名进化算法，可以有效地解决多模态和多维优化问题.

群智能优化算法在处理组合优化问题上具有寻优速度快、算法可移植性好等优点，但同时也存在一些亟需解决的普遍性问题，如避免早熟收敛与提高寻优速度难以平衡，探索和开发能力存在矛盾等.而且，实际问题多种多样，很难找到一个通用优化算法，不对其作任何改进就能解决所有问题.因此，笔者拟对ABC算法进行改进，引入变邻域搜索并优化搜索方程，以期更好求解物流配送中心选址问题.

1 配送中心选址问题求解描述

研究人员通常在几个简化的假设下描述配送中心选址问题.本研究的配送中心选址问题基于以下假设：(1)配送中心服务的需求总量不能超过配送中心的容量限制；(2)每个需求点只由1个配送中心提供服务；(3)物流网络的总费用由基础设施建设的固定费用和运输费用构成，其中运输费用取决于运输距离.在这些假设的基础上，笔者设计了如下数学模型：

(1)

(2)

(3)

(4)

模型的目标是在N个需求点中选出M个配送中心，使得整个物流网络的总费用最低.(1)式中：U为物流网络的总费用；Fi为在需求点i建设配送中心的固定费用；决策变量hi∈{0,1}，取1表示需求点i被选为配送中心，取0表示没有被选中；决策变量zij∈{0,1}，表示需求点i与配送中心j的服务关系，取1表示存在服务，取0表示没有服务；Wi为需求点i的需求量；dij为需求点i与配送中心j之间的距离；Tj为配送中心j的最大容量.约束条件(2)表示被选为配送中心的总数为p；约束条件(3)表示被服务需求点的需求总量不能超过对应配送中心的容量限制；约束条件(4)表示任意需求点对应的配送中心是唯一的.

2 基本人工蜂群算法

ABC算法有3个基本组成部分，即食物源、雇佣蜂和非雇佣蜂(包括跟随蜂和侦察蜂).食物源代表问题的可行解，解的质量由问题的适应度来表示，解的优化通过蜜蜂的搜索行为完成.搜索行为即为ABC算法的过程，其基本框架可简单描述为以下几个阶段：

过程1算法初始化阶段

过程2REPEAT

雇佣蜂阶段

跟随蜂阶段

侦察蜂阶段

存储最优解

UNTIL(达到最大迭代次数或其他终止条件)

设在D维空间中，有N只蜜蜂组成的蜂群.初始化阶段，通过侦察蜂初始化食物源(解决方案)的种群，并设置控制参数；雇佣蜂阶段，在初始解的邻域范围搜索新解并比较新旧解的适应度，采用贪婪法进行选择；跟随蜂阶段，根据解的适应度，按照公式

(5)

概率地选择是否跟随，并在邻域中搜索新解，同样采用贪婪法进行比较和选择.(5)式中fi为第i只蜜蜂的适应值.

(6)

2014年，Karaboga等[15]对ABC算法的优化及应用进行了全面梳理和系统总结，分析了算法存在的缺点并提出了未来可能的发展思路.他指出，ABC算法可以作为一个进化框架，将不同的传统或现代启发式算法组件集成于其中.为了提高ABC算法的收敛性，Karaboga建议围绕不同问题对原始结构进行相应修改，如采用新的邻域生成方法.

3 基于改进邻域搜索方法的ABC算法

3.1 全局最优引导

群智能算法的探索和开发能力的平衡是各种优化算法的核心问题之一.一般来说，过度探索会导致算法收敛缓慢，而过度开发会抑制多样性并导致过早收敛，因此探索和开发能力达到适当平衡对有效解决问题非常重要.Zhu等[16]分析了ABC算法的搜索方程，认为该算法的探索能力较强，开发能力较弱，导致算法收敛性能较差.受PSO算法的启发，Zhu等提出了新的搜索方程.在此基础上，高卫峰等[17]结合DE算法，提出如下受全局最优解引导的搜索方程：

(7)

优化组合问题的求解通常初期需要具备较强的探索能力，循环后期需要具备较强的开发能力，而基本ABC算法在雇佣蜂和跟随蜂阶段采用同样的邻域搜索方程，是不能较好地满足这一要求的.为了解决这个问题，笔者设计出新的邻域生成方法：雇佣蜂阶段以当前解引导，即采用(6)式产生邻域；跟随蜂阶段以全局最优解引导，即采用(7)式产生邻域.本研究采用与文献[6]相同的编码形式，邻域操作算子有以下3个：

(1)邻域算子N1.在原始解的编码中随机选择2个不同的位置进行互换.

(2)邻域算子N2.在原始解的编码中随机选择1个位置，将此位置的编码移动到新的随机位置.

(3)邻域算子N3.在原始解的编码中随机选择2个位置，将这2个位置之间的所有编码进行翻转.

3.2 变邻域搜索

基本ABC算法的邻域搜索方程采用随机策略，使得算法的局部搜索能力较差.变邻域搜索(Variable Neighborhood Search，VNS)通过系统地改变邻域结构，可以增强局部搜索能力，在求解复杂的大规模组合优化问题中表现良好[18-20].

3.2.1局部搜索阶段 局部搜索阶段采用可变邻域下降(Variable Neighborhood Descent，VND)算法框架，通过顺序使用邻域算子Nk(k=1,2,3)来改进当前的解决方案.当不可能有更多的改进时，VND算法停止.为了缩短该阶段操作的运行时间，笔者将采用一种去重计算方法，即仅计算编码改变部分的费用而不重新计算新编码对应的总费用.

图1 抖动策略Fig. 1 Shaking Strategy

3.2.2抖动阶段 局部搜索阶段之后进入抖动阶段.传统的抖动阶段采用的邻域算子与局部搜索阶段相似，导致改变的程度较小，容易陷入局部最优，造成早熟收敛.为了避免这一问题，笔者通过在抖动阶段采用“分块—打乱—重组”模式来增加解的改变程度，即先将原始解的编码随机切割成n块连续的片段，再按块打乱顺序后重新组合在一起.以编码“347508126”为例，先将它分为4块，再打乱、重组，过程如图1所示.

3.3 求解配送中心选址问题的变邻域人工蜂群算法

变邻域人工蜂群(Variable Neighborhood Artificial Bee Colony，VNABC)算法求解配送中心选址问题的主要步骤如下：

Step1初始化蜂群.包括蜂群规模、最大迭代次数(Cmax)和无改进次数限制(l)等.

Step2评估每只蜜蜂对应解的适应度.

Step3雇佣蜂根据邻域搜索方程(6)，按照VNS进行局域搜索和抖动操作产生新解，然后进行贪婪选择.

Step4跟随蜂根据(5)式计算选择蜜源的概率，接着根据搜索方程(7)，按照VNS进行局域搜索和抖动操作产生新解，然后进行贪婪选择.

Step5评估并记录全局最优解.

Step6记录解未改进次数t，若t>l则侦察蜂随机产生新解.

Step7判断是否满足寻优结束条件，若满足则输出最优解，算法结束；若不满足则转step 3.

VNABC算法流程如图2所示.

图2 变邻域人工蜂群算法流程Fig. 2 Flow Chart of Variable Neighborhood Artificial Bee Colony Algorithm

4 仿真实验

为了验证VNABC算法的有效性，笔者利用Matlab R2018a软件进行了2组对比实验：一是利用VNABC算法、GA、基本PSO算法、混合PSO算法[2]、基本ABC算法[4]、改进ABC算法[5]等对算例分别进行仿真求解；二是将VNABC算法与基本ABC算法进行比较.实验采用文献[3]中的算例，从12个需求点中选择3个配送中心，使得总费用最小.已知每个配送中心的容量均为13个单位，各需求点的建设费用和需求量见表1.为了简化计算，表1中的数据已经过规范化处理，无实际计量单位.

表1 各需求点的建设费用和需求量

(1)仿真实验1：VNABC算法与GA、基本PSO算法、混合PSO算法、基本ABC算法、改进ABC算法等进行比较.

设置种群规模为80，最大迭代次数为2 000，无改进次数限制次数为50.所有算法在相同的基本参数设置下各自运行20次，仿真结果见表2，VNABC算法的最优解结果见表3.

表2 各算法仿真结果对比

表3 VNABC算法的最优解

结合表2和表3可知，VNABC算法运行20次均得到已知最优解，物流网络为最小费用161个单位，此时可选择需求点1，4，8号作为配送中心(不是唯一最优解).由此可见，VNABC算法相比其他算法在稳定性和收敛速度方面都具有一定优势.

采用基本ABC算法、改进ABC算法和VNABC算法得到的最优解迭代次数的对比结果如图3所示.

图3 3种ABC算法得到最优解迭代次数的比较Fig. 3 Comparison of Iteration Times of Optimal Solution Obtained Through Three ABC Algorithms

由图4可见，VNABC算法的迭代次数相比其他2种ABC算法的明显要小，且算法稳定性更强.这说明，该算法能较好地平衡探索与开发能力，寻优速度更快.

(2)仿真实验2：VNABC算法与基本ABC算法进行比较.

笔者对基本ABC算法的改进主要是：(1)基本ABC算法的雇佣蜂和跟随蜂阶段均是在当前解附近进行局部搜索，而VNABC算法的跟随蜂阶段是在全局最优解附近进行局部搜索；(2)在基本ABC算法的基础上设计了3个邻域算子，重构了新的邻域，采用变邻域搜索方法；(3)在局部搜索之后加入抖动环节，增强解空间的多样性.为了验证改进方法的有效性，笔者设计了4个方案进行比较实验.方案具体如下：

方案1雇佣蜂在当前解附近搜索，跟随蜂在当前解附近搜索.采用基本邻域结构和局部搜索方法.

方案2雇佣蜂在当前解附近搜索，跟随蜂在全局最优解附近搜索.采用基本邻域结构和局部搜索方法.

方案3雇佣蜂在当前解附近搜索，跟随蜂在全局最优解附近搜索.采用3.1节的邻域结构和3.2.1节的局部搜索方法.

方案4采用VNABC算法.

设置种群规模为80，最大迭代次数为200，无改进次数限制为50，实验结果见表4.

表4 VNABC算法与基本ABC算法的比较结果

比较方案1和方案2可知，采用最优解引导可以提升算法的局部搜索能力和开发能力，加快寻优速度，但稳定性较差，容易早熟收敛；方案3在方案2的基础上改变了邻域结构，采用变邻域搜索方法，寻优速度和稳定性均有明显改善；方案4即VNABC算法，相比方案3进一步增加了解空间的多样性，可以有效平衡算法的探索和开发能力，改进全局和局部搜索能力.

结合表 2 和表4可知，VNABC算法的解的质量、收敛速度及稳定性均表现良好，相比其他算法在性能上有一定程度的提升.

5 结语

为了避免物流配送中心问题求解陷入早熟，提高收敛速度，平衡优化算法的探索和开发能力，笔者对基本ABC算法作了改进，设计出VNABC算法.首先，将雇佣蜂与跟随蜂的邻域搜索方程进行区别化处理，即雇佣蜂采用当前解引导，跟随蜂采用全局最优解引导，以加快向最优解靠近的速度及提升算法的开发能力；其次，引入变邻域搜索，在抖动阶段采用新颖的“分块—打乱—重组”模式，以增加解的多样性及提升算法的探索能力；最后，采用3个邻域算子，使算法具有较强的扰动能力.仿真实验结果表明，VNABC算法在有效性、稳定性、收敛速度上均有一定的优势，较好地平衡了探索和开发能力.本研究是将VNABC算法应用于配送中心选址问题求解，但该算法是否适用于更大规模的问题求解，是否具备解决其他问题的可移植性，这是未来的研究方向.