一种解决VRP问题的混合蚁群算法研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇一种解决VRP问题的混合蚁群算法研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：在基本蚁群算法的基础上，该文对参数ρ和信息素更新规则进行了改进，提高了算法搜索最优解的能力，并将其和遗传算法进行了融合，应用到解决车辆路径的问题上，通过实例验证了这种混合蚁群算法可以有效求得VRP问题的最优解或近似最优解。

关键词：VRP；蚁群算法；遗传算法；混合蚁群算法

中图分类号：G642文献标识码：A文章编号：1009-3044(2012)08-1824-03

A Study of the Hybrid Ant Colony Optimization for Vehicle Routing Problem

LI Wei-wei

(School of Software Engineering,Dalian Jiaotong University,Dalian 116028,China)

Abstract: Based on the basic ant colony optimization，this paper improves the parameterρand pheromone update rules, and improves the ability of algorithm to search the optimal solution, and fuses this algorithm with Genetic Algorithms, and then applies the hybrid ant colony optimization to solve Vehicle Routing Problem. The hybrid algorithm which can be verified by example is effective to obtain the optimal solution or approximate optimal solution for Vehicle Routing Problem.

Key words: VRP; ant colony optimization; genetic algorithms; hybrid ant colony optimization

车辆路径问题（Vehicle Routing Problem）是一个经典的NP难组合优化问题，它的原型是旅行商问题，即给定n个城市和两个城市之间的路径，求一次访问各城市一次且只一次的最短路线。经典的VRP是由G.Dantzig和J.Rasmer提出，现在已经成为运输、物流管理以及运筹学领域的热点问题。

1 VRP问题描述及数学模型

一般情况下，VRP问题可描述为：由一个仓库的车辆向多个客户点进行配送服务，在已知待服务的客户和出发点的位置、客户需求及车辆的最大负荷的前提下，设计车辆配送路径，规划设计方案，使运输成本最小，即总代价最小。

设cij表示客户点i到客户点j的运输成本，其可以是距离、时间、费用等，根据实际情况而定。M为车辆总数，N为客户点数(结点数)，Q为每辆车的最大负荷量，qi为每个客户的需求量。结点集合为vi（i=1,2,…,n），其中v0表示仓库。定义变量：

xijk={1,若车辆k从客户点i到客户点j 0，否则

yijk={1,客户点i的需求由车辆k来完成0，否则数学模型为：

minz=∑ xijk=yiki=0,1,?,n;k=1,2,?,m(5)

模型中式（1）是目标函数；式（2）是车辆载重量约束；式（3）是任务约束，保证每个客户的需求只由一辆车完成，所有的运输任务则由M辆车完成；式（4）和式（5）是路径约束，保证到达某一节点的车辆有且只有一辆。

2基本蚁群算法的原理及模型

2.1基本蚁群算法的原理

蚁群算法（Ant Colony Optimization,简称ACO）是意大利学者M.Dorigo等人提出的新型模拟进化算法，其从提出至今已陆续应用在一些不同的学科领域，取得了较好的成果。它通过模拟自然界中蚂蚁群的觅食过程来求解一些NP-Hard问题。蚁群在寻找食物时总能找到一条从巢穴到食物的最优路径，这是因为蚁群在运动时会在路径上释放出一种特殊的分泌物来寻找路径。当它们遇到一个还没走过的路口时，就会随机的选一个路径前行，同时释放出与路径长度有关的信息素，路径越长释放的信息素浓度越低。当

后来的蚂蚁再次碰到这个路口时，选择信息素较高路径的概率就相对较大。而当一定路径上通过蚂蚁越来越多时，其留下的信息素轨迹也越来越多，后来的蚂蚁选择这条路径的概率也会越大，从而增加了这条路径的信息素强度，强度大的信息素会吸引更多的蚂蚁，这样便形成了一种正反馈机制。最优路径上的信息量越来愈大，而其他路径上的信息量会随着时间流逝而逐渐消减，最终整个蚁群会找到最优路径。在整个寻径过程中，虽然单个蚂蚁的选择能力有限，但是通过信息素的作用，使整个蚁群相互协作，最终找出最优路径。同时，蚁群还能随环境的变化而变化，当路径上出现障碍物时，蚁群可以适应性的搜索新的路径，产生新的选择。

2.2基本蚁群算法的数学模型

以求解n个城市的TSP问题为例来说明基本蚁群算法的数学模型。设C={c1, c2,…,cn}是n个城市的集合，L={} lij|ci,cj?C是集合C中元素（城市）两两连接的集合，dij()

t时刻路径（i,j）上的信息量，n表示TSP规模，m为蚁群中蚂蚁的总数目，则m=∑

市）两两连接lij上残留信息量的集合。在初始时刻各条路径上信息量相等，并设τij( )

0 =const。

蚂蚁k（k=1,2,…,m）在运动过程中，根据各条路径上的信息量决定其转移的方向，用禁忌表tabuk() k=1,2,?,m来记录蚂蚁k当

前所走过的城市，集合tabuk随着进化过程动态调整。在搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。pkij( ) t表示在t时刻蚂蚁k由城市i转移到城市j的状态转移概率。上式中，allowedk={} C-tabuk表示蚂蚁k下一步允许选择的城市，α为信息启发式因子，表示残留信息素对路径的重要程度，β

为期望启发式因子，表示能见度的相对重要性；ηij( ) t为启发函数，表示蚂蚁从城市i转移到城市j的期望程度，表达式为：

dij，对蚂蚁k来说，dij越小，ηij( )

在每只蚂蚁走完一步或是完成一次循环之后，要对路径上的残留信息素进行更新，用参数ρ?[) 0,1表示信息素挥发程度，则

1-ρ表示信息素的残留因子，t+n时刻路径(i,j)上的信息量根据下式进行调整：

τij()

t表示本次循环中路径（i，j）上的信息增量，初始时刻Δτij( ) 0 =0，Δτkij(t)表示第k只蚂蚁在本次循环中留在路径（i，j）上的信

其中，Q是常数，表示信息素强度，Lk表示第k只蚂蚁在本次循环中所走路线的费用值（可以表示为长度）。

3求解VRP问题的混合蚁群算法 3

.1蚁群算法的改进策略

为了提高蚁群算法的全局搜索能力，提高其搜索速度，我们从以下两方面对蚁群算法进行了改进。

1）对参数ρ的改进：蚁群算法中信息素挥发因子ρ的大小直接关系到蚁群算法的全局搜索能力及其收敛速度。当ρ过大时，当解的信息量增大时，以前搜索过的解被选择的可能性过大，也会影响到算法的全局搜索能力；当ρ过小时，虽然可以提高算法的全局搜索能力，但又会使算法的收敛速度降低。因此，采用下式对ρ进行调整：式中μ为信息素挥发系数，ρmin为预先给定的ρ的最小值，可以防止ρ过小而降低算法的收敛速度，确保求的较优解。2）对信息素更新方式的改进：这里采用下列全局信息素更新方式来改变所求最优解的所有路径上的信息量值。

τij()（12）

其中，Lbest(t)为到t时刻为止所求得的最优解的路线长度。

蚁群算法中的Q、α、β、ρ、m等主要参数的选择也是影响算法求解性能的关键因素，但到目前为止还没有确定最优参数的一般方法。现在已经公布的参数设置成果都是针对利用不同蚁群算法模型所解决的特定问题而言的。以应用最多的Ant-Cycle模型为例，其最好的实验结果为:0≤α≤5;0≤β≤5;0.1≤ρ≤0.99;10≤Q≤10000。

3.2混合蚁群算法中的遗传算法

应用上述改进蚁群算法求解得到最优路线之后再运用遗传算法进行优化。

遗传算法中的交叉规则用顺序交叉方法。先进行常规的双点交叉，再进行维持原有相对访问顺序的巡回路线修改。具体方法如下：

1）随机在父串上选择一个区域，如两父串选择为

s1=1 2|3 4 5|6s2=6 5|4 3 2|1

2）将s2的区域加到s1的前面，将s1的区域加到s2的前面，即

s1′=4 3 2|1 2|3 4 5|6s2′=3 4 5|6 5|4 3 2|1

3）依次删除s1′和s2′中与区域相同的数码，得到最终的两子串为

new1=4 3 2 1 5 6new2=3 4 5 6 2 1

变异规则采用逆转变异方法，充分利用蚁群算法的并行性、正反馈性等特点，具体方法是：染色体（1-2-3-4-5-6-7）在区间3-4和区间6-7处发生断裂，断裂片段又以反向顺序插入，于是逆转后的染色体变为（1-2-3-6-5-4-7）。

4实例验证及分析

在一个区域内有8个客户点，一个仓库，仓库内有两辆车可派送，最大载重量都是8t，实验的基础数据如表1所示。要求合理安排车辆，使总运输费用最小，即总距离最小。

表1商店之间的距离及需求量

用混合蚁群算法求出最小运输距离为67.5km，最优路径为：04760,0135820。此方案既满足了车辆容量约束又满足了各客户点的需求，是上述车辆路径问题的一个可行解。用遗传算法和基本蚁群算法对同一问题进行求解，前者求得的最小运输距离为71.5km，后者求得的最小运输距离为79.5km。混合蚁群算法的实验结果明显优于遗传算法和基本蚁群算法，是车辆路径问题的一个较优的满意解。

5结束语

本文针对蚁群算法搜索时间过长，容易出现停滞现象等的缺点，对蚁群算法进行了改进，并且将遗传算法和蚁群算法结合求解vrp问题，最后对此混合蚁群算法进行了实验验证，证明了该算法的有效性。但是蚁群算法不是一个确定性的算法，特别是在参数选取方面，笔者以后将在参数选取对蚁群算法影响方面做进一步的研究。

参考文献：

[1]段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005:238-249.

[2]孙丽君,胡祥培,王征.车辆路径规划问题及其求解方法研究进展[J].系统工程,2006,24(11):31-37.

[3] Dorigo M,Maniezzo V,Colomi A.Ant System:Optimization by a Colony of Cooperating Agents[J].IEEE Transactions on Systems,Man,and Cybernetics-PART B.1996,26(11):29-41.

[4] Dorigo M,Gambardella L.AntColonies for the Traveling Salesman Problem[J]. Bio systems, 1997,43:73-81.

[5]张锦,李伟,费腾.交叉变异蚁群算法在VRP问题中的应用研究[J].计算机工程与应用,2009,45(34):201-203.

[6] Reimann M,Doerner K,Hartl R F.Insertion based ants for vehicle routing problems with backhauls and time windows[C]//Proceedings of the 3rd International Workshop on Ant Algorithms/ANTS2002,Lecture Notes in Computer Science, 2002,24(63):135-148.

[7]Tian Y,Song J Y,Yao D Y,et al.Dynamic vehicle routing problem using hybrid ant system[C].Proceedings of the 2003 IEEE Intelligent Transportation Systems,2003,2:970-974.

[8]Clarck G,Wright J W.Scheduling of vehicles form a central deport to a number of delivery points[J]. Operations Research,1964,12(4): 568-581.

[9] Bullnheimer B,Hartl R,Strass C.An improved ant system algorithm for the vehicle routing problem[J]. Annals of Operations Research, 1999, 89(13):319-328.

[10] Marius M,Solomon M.Algorithms for vehicle routing and scheduling problems with time window constraints[J].Operations Research,1987, 35(2): 763-781.