求解VRP问题的改进蚁群算法

第８卷第２期２００８年１月　１６７１—１８１９（２００８）２－０５６３—０３　科学技术与工程　Ｓｃｉｅｎｃｅ　Ｔｅｃｈｎｏｌｏｇｙ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｖｏ１．８　Ｎｏ．２　Ｊａｎ．２００８　⑥２００８　Ｓｅｉ．Ｔｅｅｈ．Ｅｎｇｎｇ．　

一种改进的蚁群算法及其在ＶＲＰ中的应用　

屈先锋左春荣　

（合肥工业大学管理学院，合肥２３０００９）　

摘要从基本的蚁群算法出发，讨论参数　、卢及Ｐ、Ｑ的改变对算法的影响，并通过遗传算法对　、卢和Ｑ进行遗传变异改变　其值，进而对算法进行改进。既提高了算法的收敛性，又避免了算法过早地陷入局部最优，提高了解的质量。通过实验证明　算法可行、有效。　关键词　车辆路径问题　蚁群算法　遗传算法　中图法分类号Ｕ４９２．３１２；　文献标志码Ｂ　

车辆路径问题（Ｖｅｈｉｃｌｅ　Ｒｏｕｔｉｎｇ　Ｐｒｏｂｌｅｍ，ＶＲＰ）　ｆ１，客户ｉ的需求由ｋ车完成；　是Ｇ．Ｄａｎｔｚｉｇ和Ｊ．Ｒａｓｍｅｒ于ｌ９５９年提出的运筹学　Ｙｌｊｋ　Ｉｏ，否则。　

领域的一大类重要问题，是现时效率化配送的重压　此问题的数学模型为：　支撑技术　。由于ＶＲＰ是ＮＰ一难题，精确算法只能　．　解决规模较小的问题。因此，对其算法的研究主要　ｍｌｎ　刍　。　

集中在备种启发式算法，如蚁群算法、遗传算法、禁　ｑ　≤Ｑ，　：１，２，…，Ｍ　忌搜索算法，以及模拟退火算法等。现代计算机通　信技术的发展也为求解ＶＲＰ提供的强大的工具。　：１，　，…，　＋　…　Ｌｍ．ｉ＝０　

１问题定义　

一般情况下，非满载车辆路径优化问题可以描　

述为：设某一配送中心有　辆车，需要对Ⅳ个客户　（结点数）进行运输配送，每个客户的需求量为ｑ　（ｉ　

＝１，２，…，ｎ），每辆车的最大载重量为Ｑ。设ｃ　表示　

客户　到客户　的运输成本，其中包括时间、行驶里　程及其它费用等。结点集合为　（ｉ＝０，１，２，…，ｎ，ｎ　＋１），其中　和　表示配送中心。定义变量　

如下：　ｆ１，车辆ｋ由　驶向　；　【０，否则。　（１）　

求解VRP问题的有效算法

在物流管理领域中，车辆路径规划问题（Vehicle Routing

Problem，简称VRP）一直是研究的热点。VRP是一种NP难问题，即难以求解的组合优化问题。该问题涉及到多个车辆在多个客户之间进行货物配送的路线规划，目标是使总配送成本最小化。尽管VRP是一个难题，但是研究者们已经开发出了一系列有效的算法来解决这个问题。

一、基础VRP问题

基础的VRP问题可以被归结为以下几个部分：客户集合S，客户之间的距离为d(i, j)，每个客户有需求量d(i)，每个车辆有容量Q，每个车辆的行驶路线长度不能超过车辆的行驶范围L。对于基础VRP问题，旅行商问题（Traveling Salesperson Problem，简称TSP）可以被视为特殊情况，即只有一个车辆和所有客户都要被服务。

二、求解VRP问题的算法

1.精确算法：精确算法利用数学模型来确切地解决基础VRP问题。其中最常用的算法是分支定界法和分支定价法。

分支定界法：分枝定界法将复杂的VRP问题分解成一个大问题和若干个小问题，并通过深度优先算法搜索可行解空间以确定最优解。在搜索枚举进程中，如果找到一个解，它会被与当前最优解比较，直到找到一个更优解。分支定界法的主要优点是可以得到最优解，但它的计算复杂度非常高，因此只适用于小规模问题。

分支定价法：分支定价法是对分支定边法的一种扩展，是一种动态决策技术，其目标是在可行解空间内找到最小成本解。该算法主要基于线性规划模型及其相应的分支定界技术，通过建立合适的线性规划模型，寻找可行解空间内的最优解。

2.启发式算法：为了有更好的效率解决VRP问题，启发式算法在实践中经常被使用。这些算法主要适用于大规模问题，其中包括模拟退火，遗传算法，蚁群算法，粒子群算法等。其中，蚁群算法是求解VRP问题的最常用的启发式算法之一。

蚁群算法：蚁群算法是指模拟蚂蚁在寻找食物时的追踪行为的算法。该算法模拟了一组人工蚂蚁在一个基础VRP问题中服务所有客户的过程。蚂蚁在某个节点上释放信息素，并选择下一个节点的概率是基于其周围信息素水平和节点的距离，从而使具有更高信息素水平的路径更有可能被选择。从而，蚂蚁在搜索图中尝试多个方向移动，最终得到VRP问题的最优解。

第３０卷第１１期　计算机仿真　２０１．３年１１月　

文章编号：１００６—９３４８（２０１３）１１—０３１７—０４　

改进的蚁群遗传算法求解旅行商问题　

于莹莹，陈燕，李桃迎　

（大连海事大学交通运输管理学院，辽宁大连１１６０２６）　

摘要：在改进蚁群算法优化问题的研究中，针对遗传算法收敛速度过慢的问题，将蚁群算法与遗传算法相结合，首先利用信　息素的蚁群算法的快速收敛特性，得到一次寻优结果作为遗传算法的初始种群，同时对传统遗传算法的基本遗传算子做出　改进，结合形成一种新的算法模型，应用于求解旅行商问题。对三种模型分别设计程序实现仿真，采用两组实验数据，对三　种算法求解旅行商问题的结果进行模拟与对比分析。实验结果表明改进的蚁群遗传结合算法可以有效地解决旅行商问题，　在求解效率和求解质量上都取得很好的效果。　关键词：蚁群算法；遗传算法；组合算法；旅行商问题　中图分类号：ＴＰ＇３０１．６；ＴＰ１８　文献标识码：Ｂ　

Ｉｍｐｒｏｖｅｄ　Ａｎｔ　Ｃｏｌｏｎｙ－Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｓｏｌｖｉｎｇ　ＴＳＰ　

ＹＵ　Ｙｉｎｇ－ｙｉｎｇ，ＣＨＥＮ　Ｙａｎ，ＬＩ　Ｔａｏ—ｙｉｎｇ　

（Ｃｏｌｌｅｇｅ　ｏｔＴｒａｎｓｐｏｒｔａｔｉｏｎ　Ｍａｎａｇｅｍｅｎｔ，Ｄａｌｉａｎ　Ｍａｒｉｔｉｍｅ　Ｕｎｉｖｅｒｓｉｔｙ，Ｄａｌｉａｎ　Ｌｉａｏｎｉｎｇ　１　１６０２６，Ｃｈｉｎａ）　

ＡＢＳＴＲＡＣＴ：Ａｓ　ｔｈｅ　ｃｏｎｖｅｒｇｅｎｃｅ　ｓｐｅｅｄ　ｏｆ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　ｉｓ　ｓｌｏｗ，ａ　ｎｅｗ　ｃｏｍｂｉｎａｔｉｏｎ　ｍｅｔｈｏｄ　ｂａｓｅｄ　ｏｎ　Ａｎｔ　Ｃｏｌｏ—　

ｎｙ　Ａｌｇｏｒｉｔｈｍ　ａｎｄ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｓｏｌｖｉｎｇ　ＴＳＰ　ｗａｓ　ｐｒｏｐｏｓｅｄ．Ｔｈｅ　ｎｅｗ　ｍｅｔｈｏｄ　ｔｏｏｋ　ｔｈｅ　ｒｅｓｕｌｔ　ｏｆ　Ａｎｔ　Ｃｏｌｏｎｙ　Ａ１一　

ｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｐｈｅｒｏｍｏｎｅ　ａｓ　ｔｈｅ　ｉｎｉｔｉａｌ　ｐｏｐｕｌａｔｉｏｎ　ｏｆ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ，ａｎｄ　ｍａｋｅｓ　ａ　ｆｅｗ　ｉｍｐｒｏｖｅｍｅｎｔｓ　ａｂｏｕｔ　ｔｈｅ　

改进的蚁群算法求解VRP问题

Improved Ant Colony Algorithm for VRP

SANG Guo-zhen1, WANG Feng2, YANG Rui-chen2

(1.Weinan Teachers University, Weinan 714000, China;

2.Chengde Petroleum College, Chengde 067000, China)

:A mutation is applied to the ant colony algorithm and the

mutation probability is given for solving the VRP problem more

efficiently. The formula of visibility and pheromone updating

method are set reasonably. Combined with swap local search, a

more stable ant colony algorithm for VRP is gained. Experiments

show that the algorithm is stable and effective.

Keywords:VRP; ant colony algorithm; mutation; local search

车辆路径问题 [1] (vehicle routing problem,VRP) 是组合 优化领域中著名的 NP-hard 问题之一 , 一般需使用启发式搜索算 法求解。蚁群算法是模拟蚂蚁觅食原理的一种仿生学启发算法 , 其应用于VRP问题的求解具有更为明显的优势，很多人对此进行 了研究。

1 VRP问题

采用赋权有向图 G=(V,A,d) 来表示配送路径问题。其

中,V={vO,v1,v2,…,vn}为点的集合;v0表示配送中