基于群智能混合算法的物流配送路径研究

朱亚琪，方建安

0 引言

车辆路径问题（Vehicle Routing Problem, 简称VRP）是物流系统研究中的一项重要内容，根据车辆路径模型，可以将其转化为TSP问题。蚁群算法在解决旅行商（TSP）等著名问题时，已得到了卓有成效的应用，但解决大规模问题时，其收敛速度较慢且耗时较长[1]。

粒子群优化算法（PSO）[2,3]是一种全局优化算法，由Eberhart和Kennedy于1995年提出的。该算法的优点：1) 具有较大范围的全局搜索能力；2) 搜索从群体出发，具有稳定性；3) 搜索使用评价函数值启发；4) 收敛速度快，参数调整简单；5) 具有可扩展性, 容易与其他算法结合。存在的缺点是：在算法后期的局部搜索能力差，反馈信息利用不充分。

差分进化法可以解决不可微分非线性函数最优化问题，采用随机直接搜索法，利用上、下代问的竞争原理，收敛速度快，同时族群多样性大幅度减小，但存在收敛过早、易陷入局部最优等问题。文献[4]则提出改进差分进化法，称为混合差分进化法（hybrid differential evolution method），然而，混合差分进化法的突变操作共有5种方法，本文根据蚁群算法的特点，在混合算法中使用蚂蚁系统搜寻适当的突变操作，以利于加速算法搜索全局最优解。

本文提出一种双种群蚁群算法，在蚁群的基础上引入差分进化（DE）和粒子群算法（PSO）。通过在 PSOAS种群和 DEAS种群之间建立一种信息交流机制，使信息能够在两个种群中传递，以免某一方因错误的信息判断而陷入局部最优点。

1 物流配送的路径问题

为了降低服务商的运营成本，物流系统都会在车辆配送路径上做优化。选取合适的运输路线，可以加快对客户需求的响应速度，提高服务质量，增强客户对物流系统的满意度。车辆路径问题，一般定义为对一系列发货点和/或收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件下，达到一定的目标（如路程最短、费用最小、时间尽量少、使用车辆尽量少等）。

物流配送路径问题，实际上是旅行商(Traveling Sales-man Problem, TSP)的问题，对TSP的问题描述如下：一个货郎要走访 N个橙色，每个城市必须经过一次且只能经过一次，最后回到出发的城市，就算是完成了一次旅行，找到一条最短的路径。其相应数学描述如下：设有一城市集合，每对城市间的距离为。求一条经过C中每个城市正好一次的最短路径。

2 蚁群算法

蚁群算法（Ant Colony Algorithm, ACA）于20世纪90年代由Colony等提出，该算法模拟蚁群的群体协作觅食过程，由若干个蚂蚁共同构造解路径，通过在解路径上遗留并交换信息素提高解的质量，进而达到优化的目的。由于物流配送路径问题实际上是一个旅行商问题，下面以 TSP为例介绍算法内容：

设m是蚁群中蚂蚁的数量，dij是城市i与j之间的距离，ηij(t)=1/dij为启发函数；τij是t时刻路径(i,j)上的信息量；pijk(t) 表示在t时刻蚂蚁k由城市i转移到城市j的概率，公式（1）

其中，j是尚未访问的城市；allowedk={C-tabuk}表示蚂蚁k下一步允许选择的城市；α和β为启发式因子；tabuk(k=1,2,…,m)用以记录在t时刻蚂蚁k已走过的城市，不允许该蚂蚁在本次循环中重复经过，本次循环结束后清空禁忌表。

蚂蚁完成一次循环，更新各路径信息素，公式（2）

其中，ρ∈[0,1)表示信息素挥发系数；(1−ρ)表示信息素残留因子；△τij表示本次循环中路径ij上的信息量增量，初始时△τij(0)=0；△τijk表示蚂蚁k在本次循环中在城市i和j之间留下的信息量，公式（3）

其中，Lk表示蚂蚁k环游一周的路径长度；Q为常数。蚁群算法中，参数的选取方法与选取原则直接影响到蚁群算法的计算效率和收敛性[5]；另外，该算法存在着初始信息素缺乏、收敛速度慢、容易陷入局部最优等缺点。

本文采用双种群策略，种群一采用蚁群算法与差分演化结合，可以很好地解决参数优化问题。种群二采用蚁群混合粒子群算法，增强了大范围全局搜索能力，很好地解决了收敛速度慢、容易陷入局部最优问题。

3 蚁群算法与差分演化结合（DEAS）

差分演化算法擅长连续问题的优化，并且已成功应用于很多算法的参数控制中。由于蚁群算法的控制参数是连续变化的，因此可以利用DE 对其进行参数优化，进而改善蚁群算法的性能。

DEAS 将蚁群算法的参数（包括种群大小m、启发式因子α和β，信息素挥发系数ρ）作为DE 解空间向量的元素，每个个体是一个四维向量。以DE 解空间中个体为参数组合的蚁群，搜寻最优路径Iter代中得到的最优解作为 DE 的适应评价函数。以解决TSP 问题为例对DEAS 作具体应用说明，参数设置按文献[6]所示。F=0.5，CR=0.9；NP∈[3D,8D]，本文中取 5D，算法的终止条件为满足优化要求或达到最大迭代数。步骤如下：

步骤1：差分演化算法初始化：

设置目前进化代数t=1，差分演化算法的F、CR、NP以及迭代次数MAX_G，随机选择NP个个体，每个个体包含4 个参数，是一个NP×4 的随机数组。其中每一维各代表m、α、β、ρ，分别在[0,2N]、[0,5]、[0,10]、[0,1]随机取值。

步骤2：若t≥MAX_G，跳转到Step5；否则：

蚁群算法初始化：在每个参数向量下的蚁群运行的代数Iter；对每条路径设定初始信息量，τij=τo，将M只包含各自参数的蚂蚁随机地放置在N个节点上(N为城市数)，将第k只蚂蚁的出发城市加入tabuk；根据各自的参数向量值，求Iter迭代后的最优解，即求参数向量对应的适应值。

完成对每只蚂蚁的一次路径搜索，并找出本次搜索得到的最优解：

1、根据公式（1）的计算方法，求所有城市作为下一个城市的概率，使用轮盘赌的方法随机确定下一个要走向的城市，循环进行公式（1）直到只剩下一个城市未走时，直接到达那个城市，此时，表示一只蚂蚁已经完成了一次路径求解；

2、计算得到这只蚂蚁此次路径的长度；

根据公式（2）对全局信息素进行更新，并找到本次求解所找到的最优解，记录最优解对应的参数向量；将本次迭代产生最优解，即得到参数向量对应的适应值，与历史记录最优解进行比较，选取较小的一个解来更新历史最优解；

步骤3：将寻径后的每个蚁群的最短路径作为相应参数向量的适应函数值。根据公式（4）～公式（6）进行差分运算的变异、交叉和选择运算（在选择操作中的求解适应值函数即以新的解向量为参数，进行步骤2 中的内两层循环），生成新一代种群。t值加1，跳转至步骤2；在执行公式（6）进行选择的时候，如果发现出现比历史最优解好的解，也要进行历史最优值的更新。

其中：j∈[1,D],randb(j) ≥[0,1]是同一随机数发生器的第 j个值；CR∈[0,1]是变异概率；randr(j)∈[1,2,…,D]是随机选择指数，它确保能从中得到至少一个参数。

（c）选择操作，采用贪婪策略，得公式（6）

其中Φ(x)代表适应函数。

步骤 4：最后输出全局最优 TSP 路径值以及全局最优参数向量[m,α,β,ρ]。

4 蚁群算法与粒子群算法结合（PSOAS）

蚁群算法利用了信息素进行传递信息，而粒子群优化算法利用了本身信息、个体极值信息和全局极值3个信息，来指导粒子下一步迭代位置。蚁群算法利用正反馈原理和某种启发式算法的有机结合，容易出现早熟现象以及陷入局部最优解。混合的思路是让蚂蚁也具有“粒子”的特性，首先蚂蚁按照蚁群算法，完成一次遍历后，再让蚂蚁根据局部最优解和全局最优解进行调整。

解TPS问题的混合算法如下：

步骤 1：nc←0，（nc为迭代步数或搜索次数），初始化，产生大量的路径（如100条），从中选择比较优的（如30条），使这些路径留下信息素，将m个蚂蚁置于n个顶点上；

步骤2：根据当前位置计算适应值（各路径的长度）ltsp0，设置当前适应值为个体极值Ptbest，当前位置为个体极值位置pbcest，根据各个粒子的个体极值Ptbest找出全局极值bgtest和全局极值位置gcbest；

步骤3：将各蚂蚁的初始出发点置于当前解集中，对每个蚂蚁k(k=1，2，…，m)，按概率移至下一顶点j，将顶点j置于当前解集；

步骤4：对每个蚂蚁进行如下操作，第j个蚂蚁路径Co(j)与gcbest交叉得到与pbcest交叉得到，对产生变异得到，根据当前位置计算路径长度ltsp1，若新的目标函数变好，接受新值，否则就拒绝，第j个粒子路径仍然为Co(j)。重新找出各个蚂蚁子的个体极值ptbest和极值位置pbcest，找出全局极值gtbest和全局极值位置gcbest；

步骤5：计算各蚂蚁的路径长度Lk(k=1,2,…,m)，记录当前的最好解；

步骤6：对路径长度Lk小于给定值的路径，按公式（2）中的更新方程修改轨迹强度：

步骤7：nc←nc＋1；

步骤8：若nc< 预定的迭代次数且无退化行为（即找到的都是相同解）则转步骤2；

步骤9：输出目前最好解。

5 双种群混合算法

对比分析 PSO 和 DE 两种算法的特点可以发现，DE算法具备的记忆能力使其可以跟踪当前的搜索情况，以调整其搜索策略，具有较强的全局收敛能力和鲁棒性；PSO 算法简单，具有运算速度快、搜索能力强等特点。本文提出基于蚁群算法的差分进化混合粒子群算法的本质，是基于一种双种群策略，其中一个种群中的个体按照 PSOAS 操作进化，另一个种群中的个体按照 DEAS操作进化，在进化过程中，通过引入一种信息交流机制，使信息能够在两个种群中传递，有助于个体避免错误的信息判断而陷入局部最优点。采用非线性动态自适应惯性权重策略，以提高算法的性能，其更新状态如公式（7）

其中，k为控制因子，控制w与t变化曲线的平滑度。

6 算法仿真

利用实例对双种群混合算法性能进行测试，并将结果与单一的DEAS算法、单一的PSOAS算法的结果进行对比。实验独立进行30次，统计结果，如表1所示：

表1 独立试验30次的统计结果

结果表明，虽然蚁群算法与粒子群算法结合能够提高收敛速度，但是PSOAS算法得到的最差解较多，表明算法极易收敛到局部最小解。而蚁群算法与差分进化相结合能够改善算法全局优化能力，能得到较解且相对稳定。双蚁群混合算法则吸收了两种算法的优点，该算法达到最好解的次数最多，增加了最优解的概率；另外，由于两个种群中的通信机制，PSOAS种群提高了DEAS种群的搜索效率。

图1和图2分别为PSOAS种群与DEAS种群得到的最优路径，其中种群2的解优于种群1，因此最终解为种群2的运算结果。由图3，图4可以看出，原本收敛较慢的DEAS算法由于通信机制，收敛速度与PSOAS算法比较接近。

图1 种群1(PSOAS混合算法)计算结果

图2 种群2(DEAS混合算法)计算结果

图3 种群1中最佳路径随迭代的变化

图4 种群2中最佳路径随迭代的变化

7 结束语

本文针对物流过程中配送路径最优问题，设计了基于蚁群算法的双种群混合算法，种群一采用蚁群算法与差分演化结合，种群二采用蚁群混合粒子群算法，在进化过程中通过引入一种信息交流机制使信息能够在两个种群中传递，提高了蚂蚁在选路时的协同合作能力。仿真实验表明，该算法能较好地发现全局最优解，并且有较快的收敛速度和较高的稳定性，在综合性能上远远高于 DEAS算法，并在计算效率上优于PSOAS算法。

[1]Colorni A, Dorigo M, Theraulaz G. Swarm intelligence:From natural to artificial systems[M]. New York: Oxford University Press, 1999.

[2]KENNEDY J, EBERHART R C. Particle Swarm optimization[C]//IEEE International Conference on Neural Network. Perth, Australia:[s.n.], 1995.

[3]SHI Y, EBERHART R C. A modified swarm optimizer[C]//IEEE International Conference of Evolutionary Computation. Anchorage, Alaska:[s.n.], 1998.

[4]CHIOU J P, WANG F S, A Hybrid method of differential evolution with application to optimal control problems of a bioprocess system[J]．Proc l 998 IEEE on Evolutionary Computation Conf, 1998, l：627—632．

[5]崔娇，黄少荣．基于差分演化的自适应参数控制蚁群算法[J]．计算机工程，2011,37(6):190-193．

[6]KENNEDY J，EBERHART R． Particle swarm optimization［C］/ /Proc of IEEE International Conference on Neural Networks． 1995:1942-1948．