人工鱼群—蚁群算法的VRP优化研究综述

罗芃瑜++左敏

摘要：随着物流事业的蓬勃发展，物流运输配送问题也不断增加。路径优化问题作为物流运输配送的基础研究问题也一直受到学者们的重视。单一的智能优化算法已经不适合解决大规模，复杂度高的路径优化问题。在现有的混合智能算法中，基于人工鱼群算法与蚁群算法混合的研究相对来说较少，因此该文对学者们提出的混合人工鱼群-蚁群算法进行综合研究分析，对现实中路径优化问题的求解有较大的理论意义与现实价值。

关键词：VRP；鱼群蚁群算法；智能优化算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）11-0156-04

Review of VRP Optimization Based on AFSA-ACO

LUO Peng-yu， ZUO Min

（Depth of Computer and Information Engineering，Beijing Technology and Business University， Beijing 100048 China）

Abstract： With the vigorous development of the logistics industry， logistics distribution problems are increasing too. As the basis of logistics distribution， Path optimization problem have been brought to the attention of the scholars. A single intelligent optimization algorithm is not suitable for solving vehicle routing problems which of large-scale and high complexity. The research of VRP based on AFSA-ACO is relatively less nowadays. So in this paper， the author will research and analyze these optimization algorithms. This can create great theoretical and practical value on solving the vehicle routing problem.

Key words： VRP； AFSA-ACO； Intelligent optimization algorithms

在物流的配送优化等问题中，常见的问题就是：存在一批客户，并且已知客户的地理坐标，每个客户对货物的需求量，运输车辆的最大数量和运载能力等信息。在每辆运输车都从仓库出发，完成部分点的运输任务后返回仓库的前提下，寻求以最少车辆和最短总行程完成物流运输的最优解。此类问题统称为车辆运输路径问题，即Vehicle Routing Problem，VRP。

路径优化问题是现代物流供应链优化中的关键问题，车辆路径问题的理论与算法依然是学者们重视的问题与研究的重点。对算法进行系统的研究不仅为物流运输优化提供更好的思路和方法，更加为构建综合物流系统，发展智能交通运输系统等打下坚实的理论基础。

1 车辆路径问题

1.1 车辆路径问题分类

车辆路径的问题随着相关学科的发展从最初的静态的VRP、VRPTW、VRPPD等模型不断衍生出随机车辆路径问题、模糊车辆路径问题，到现在的动态车辆路径问题。所以可以将车辆路径问题归为两大类，一类是一般车辆路径问题，而另一类则是衍生车辆路径问题[1]，具体如下图1所示。

图1 车辆路径问题分类

1.2 车辆路径问题的一般模型

对于一般车辆运输问题的优化，为方便模型的建立，对货物的物流运输作以下几点假设：

（1）仅考虑位置已知的一个仓库，所有配送车辆起点和终点均是该仓库。

（2）只考虑单个品种货物的运输，且每个需求点所需要的货物剂不超过车辆的最大载重量。

（3）每个需求点的地理坐标位置和需求量都已知，其需求有且仅由一辆车辆一次送货满足。

（4）只有一种车辆，且车辆的载重量已知。

（5）车辆对每个需求点进行服务，途中只有卸货而无装货。

（6）车辆的平均行驶速度已知，并且确定，行驶的路程与车辆行驶时间成正比。

以上述假设为前提，以配送成本最小化为目标，构造出以下优化模型。

[minZ=i=0j=0k=1dij?xijk （1） ]

式中，仓库的编号为0，需求点的编号为[1，2，…，C]，[ xijk=1.0]取整数约束，1表示点i 到点 j由车辆 k来完成，否则为0；其中[yijk=1.0]取整数约束，1表示到点i由车辆 k来完成，否则为0。C为需求点的个数；m为车辆数；[dij（i，j=1，2，…，C）]为需求点i点与需求点j点之间的距离；[ ti]为车辆实际到达需求点的时间；[gi]为第i个医疗机构的需求量； [q]为车的最大载重量；[k（k=1，2，…，m）]为车辆的编号。

约束条件为：

每次为需求点运输货物的运输量不能超过车辆的最大载重量；

[i=0giyki≤qi k∈1，m （2）]

任意需求点只有1辆车辆来访；

[k=1yki =1 i∈0，C，k∈1，m （3）]

[i=0k=1xijk =1 j∈0，C，k∈1，m （4）]

[j=0k=1xijk =1 i∈0，C，k∈1，m （5）]

车辆行驶路线为闭合线路；

[i=0xijk=yki i∈0，C，k∈1，m （6）]

[j=0xijk=yki j∈0，C，k∈1，m （7）]

2 智能优化算法的分类与比较

解决车辆路径算法的种类很多从20世纪50年代起的精确算法开始，到之后的启发式算法，以及现在学者们研究的最多的智能优化算法。其中精确算法有：分支界定法（Branch and Bound Approach）、割平面法（Cutting Planes Approach）等，启发式算法有：节约算法（C-W）、扫描算法（Sweep Algorithm）等，应用最多的智能优化算法有：禁忌搜索算法（Tabu Search）、模拟退火算法（Simulated Annealing）、遗传算法（Genetic Algorithm）、蚁群算法（Ant Colony Optimization）、粒子群算法（Particle Swarm Optimization），另外还有人工鱼群算法（Artificial Fish School Algorithm）、人工神经网络算法（Artificial Neural Networks）等智能优化算法，都在车辆路径问题的研究中有应用。

随着物流业的不断发展，物流运输配送遇到的问题范围不断的扩大，实际问题的规模与复杂性也不断的增大，仅仅靠单一的算法来优化解决问题的效果已经越来越不理想，每个算法都有各自的缺陷，都面临着时间性能和优化性能等挑战。如下表1是目前运用最多的智能优化算法思想和优缺点[2]。

表1 常见智能优化算法及其特点

[智能优化算法＼&基本思想＼&优点＼&缺点＼&禁忌搜索优化算法＼&通过建立Tuba表，记录选择已经优化的过程，逐步在全局领域内寻找最优解＼&分别通过禁忌准则和特赦准则避免迂回搜索与赦免部分被禁忌的优良状态保证搜索多样性和实现全局最优＼&对初始解依赖性强，初始解的选定会影响收敛速度＼&遗传算法＼&模拟生物界优胜劣汰、适者生存的遗传和变异的进化机制＼&能全局并行搜索，有自适应能力，可处理大量信息，对局部性能高的重点搜索，不易陷入局部最小＼&收敛性差，容易“早熟”，处理约束优化问题较困难＼&模拟退火算法＼&基于物理中固体物质退火过程，从高初温出发，伴随温度下降，结合概率突跳特性，随机寻找目标函数的全局最优解＼&简单、通用、易实现、运行效率高＼&对初值有依赖性，搜索速度受串行影响，对不同状态下的抽样有较高的要求＼&蚁群算法＼&模仿自然界蚂蚁群体觅食过程中蚂蚁间互相传递信息素在较短的时间内通过最短的路程找到食物＼&分布式计算，并行性，全局搜索能力，自组织，正反馈＼&收敛速度慢，易早熟，容易陷入局部最优解＼&粒子群算法＼&模仿鸟群捕食的行为，人工建立以有向图为拓扑结构的动态系统，对连续或断续的输入状态做状态相应而进行的信息处理＼&操作简单，快速收敛，适合实值型处理＼&容易陷入局部最优解＼&人工鱼群算法＼&通过一片水域中鱼群聚集的数量判断食物多少的特点，构造人工鱼，模仿鱼群的觅食、聚群、追尾等行为，实现寻优。＼&对初值敏感性小，并行性，简单性，全局性，快速性，跟踪性＼&计算量较大，后期收敛逐渐减慢，容易陷入局部最优＼&]

基于上述现象及出发点，可将各种单一的算法取长补短，利用各算法的优势进行融合，构造出新的优化效率更高的混合算法。

3 鱼群-蚁群算法

3.1 人工鱼群算法

人工鱼群算法（AFSA）是基于模仿鱼群觅食、聚群和追尾等行为而衍生出的一种较新型智能优化算法。这种算法具有并行性、快速性、较强的搜索全局性等特点。在人工鱼群算法中，设人工鱼当前所在的位置是[Xi=xi1，xi2，…，xiN]，[Xv=xv1，xv2，…，xvN]，其中N表示维数，Visual表示人工鱼的视野范围，[Xv]表示视野范围内的一个状态。人工鱼的步长用Step表示，人工鱼要从当前状态到一个更优的状态过程可以表示为：

[Xv=Xi+Visual*rand（）] （8）

[Xnext=Xv-XiXv-Xi*Step*rand（）] （9）

人工鱼群算法还包括了一下几个行为：（1）觅食行为。在人工鱼的视野范围内选择位置[Xv]，若[Xv]的适应度[Yv]大于[Xi]的适应度[Yi]，则该人工鱼向[Xv]的方向移动一步，反之，则从新选择一个位置。（2）聚群行为。在避免拥挤和逐步中心的规则下，执行觅食行为或随机游动。其中一个重要的参数叫做拥挤因子，用[σ表示]。

若[Ycnf>σYi]（其中），表示中心食物较多且不拥挤，人工鱼向[Xc]方向移动一步，反之，则执行觅食行为或随机游动。（3）追尾行为。在优化过程中，若[Yvnf>σYi]，表示在视野范围内，最优状态的伙伴位置为[Xv]，且食物浓度高，不拥挤，则[Xi]向[Xv]的方向移动一步，反之，则执行觅食行为。（4）随机移动。即人工鱼在其视野范围内随机移动一步。人工鱼群算法的基本流程如下图2所示。

图2 人工鱼群算法的基本流程

3.2 蚁群算法

蚁群算法（ACO）是一种在图中寻找优化路径的随机搜索型算法。它最开始是由Marco Dorigo于1992年提出的，后来由Bernd Bullnheimer等[3]率先应用于解决VRP问题，即先通过蚁群算法搜索最优路径，再运用2-Opt法对其进行优化，最后找出最优解。蚁群算法的基本思想是模仿蚂蚁觅食发现最优路径的行为，并以下面三个假设为前提：（1）蚂蚁之间通过产生信息素进行相互通信；（2）蚂蚁对环境的反应由内部的模式决定；（3）每只蚂蚁的行为是随机的且仅依照环境做独立选择，蚁群可以通过自组织形成高度有序的群体行为。

蚁群算法中关键的因素有以下几个：

（1）信息素用[τijt]表示t时刻路径上信息素的含量，随着时间的推移信息素的含量不断应新旧信息素的加入和挥发而改变，当时刻变为t+n后，各个路径上的信息素变为：（其中[ρ]信息素的挥发系数）

[τijt+n=1-ρ?τijt+?τijt （10）]

[τijt=k=1m?τijt （11）]

（2）启发函数用来表示蚂蚁从节点i转移到节点j的期望程度，其计算公式为：

[ηijt=1dij （12）]

（3）状态转移概率，这里以[Pkijt]表示，其计算公式为：（其中[α]为启发因子表示蚂蚁在路径中积累的信息的作用，值越大则意味着蚂蚁间的协作性越强。[β]为期望启发因子表示启发信息在蚂蚁路径选择中的重要程度，值越大则意味着该状态下的转移率越接近贪心规则。）

[Pkijt=τijtα?ηiktβs?allowedkτijtα?ηiktβ，若j∈allowedk0，若j?allowedk （13）]

蚁群算法求解VRP的基本流程，如下图所示：

图3 蚁群算法求解VRP基本流程

3.3 鱼群蚁群混合算法

在解决VRP问题中，对鱼群蚁群混合算法的研究还不是很多，现有的两种算法可结合的方法主要分为加入改变拥挤因子，改变信息素更新机制两种形式：

（1）改变拥挤因子。文献[4]在研究特殊医疗器械物流配送路径优化时，将鱼群算法与基本蚁群算法相结合，把鱼群算法中的拥挤因子概念引入到基本蚁群算法中，是算法整体增强寻优能力，减少基本蚁群算法陷入局部最优的可能性。其中设拥挤因子[σij]和拥挤度门限[δt]的计算公式分别如式（14）和式（15），其中[γ]为极值接近水平，[b]为阈值变化系数。其改进方法可以控制蚂蚁集数量的多少，以此抑制蚂蚁过早的聚集在高信息素的路径上，从而减少早熟现象的发生几率。但是该方法也存在不足，特别是在算法的后期会影响收敛速度。

[σijt=1-τijti≠jτij （14）]

[δt=γe-bt （15）]

文献[5][6]也是研究人工鱼群算法拥挤度的引入。部分区别在于拥挤因子的设置上如式（16）所示。同样在算法的初期设置较强的门限，但是随着迭代次数的增加，拥挤度阈值逐渐增大，信息素的浓度在指导蚁群选择路径的作用逐渐增强，最后蚁群完全由信息素和启发因子来指导寻优从而保证了算法能够快速地收敛到最优解上。

[σijt=2τijti≠jτijt （16）]

（2）改变信息素更新机制。文献[7]在运用鱼群蚁群混合算法解决模块化产品配置问题中，提出了两种算法动态融合策略。不是通过改变拥挤因子来进行优化，而是通过设置鱼群算法的迭代范围，统计满意的更新率，选择鱼群与蚁群融合的最佳转换时机来进行寻优。当人工鱼群算法的优化速度明显减慢时便终止人工鱼群算法，开始蚁群算法。同时文献中改变了蚁群算法的信息素更新方程，将基本方程如式（10）改为式（16）。方程中[τijtmin]，[τijtmax]分别为信息素强度的上下限，寻求最优解。

[τijt+n=τijtmax ，若τijt>τijtmax1-ρ?+?τijt，若τijtmin≤τijt≤τijtmin，若τijt>τijtmin τijtmax（17）]

文献[8] 应用人工鱼群算法的追尾行为对蚁群在可行域上搜索到的可行解进行改进，将微分进化算法引入信息素的更新机制中，改变人工鱼群算法的追尾公式，如式（18），其中[Xbest]表示当前最优解，[Xki]表示蚂蚁k的状态[Xk]的第i个元素。之后再对修改过的新解进行信息素更新，从而加快收敛速度，快速达到全局最优。

[Xnewkj=Xkj+randStepXbest-Xki/Xbest-Xk] （18）

4 结束语

本文总结了在物流业发展的大背景下，不断衍生出的一系列路径优化问题，比较了各种智能优化算法的优缺点，得出改进单一智能优化算法的重要性。进而研究了现今学者们在人工鱼群蚁群混合算法求解VRP问题时的思路与方法。对混合鱼群蚁群算法进行了整理归类，对于完善路径优化问题的求解算法具有重要意义。

参考文献：

[1] 吴斌. 物流配送车辆路径问题及其智能优化算法[M]. 北京：经济管理出版社，2013.

[2] 张建林. MATLAB&Excel定量预测与决策：运作案例精编[M]. 北京：电子工业出版社，2012.

[3] B. Bullnheimer，R.F. Hartl，C. Strauss. An improved Ant System algorithm for theVehicle Routing Problem[J]. Annals of Operations Research，1999，890.

[4] 费腾. 基于蚁群算法的医疗器械物流配送路径优化算法研究[D].太原：太原理工大学，2010.

[5] 修春波，张雨虹. 基于蚁群与鱼群的混合优化算法[J]. 计算机工程，2008，14：206-207，218.

[6] 邹挺. 基于蚁群和人工鱼群混合群智能算法在物流配送路径优化问题中的应用研究[D].苏州：苏州大学，2011.

[7] 高德芳，赵勇，郭杨，赵海涛. 基于混合鱼群-蚁群算法的模块化产品配置设计[J]. 机械，2007（1）：7-10.

[8] 韩芳，邢晓哲，方婷婷，王成儒. 融合鱼群和微分进化的蚁群算法的无功优化[J]. 黑龙江电力，2011（2）：125-128.