混合蚁群算法在车辆路径问题中的应用

计 算 机 工 程 第 37 卷 第24期

V ol.37 No.24 Computer Engineering

文章编号：1000—3428(2011)24—0190—03·人工智能及识别技术·

2011年12月

December 2011

文献标识码：A

中图分类号：TP301

混合蚁群算法在车辆路径问题中的应用

张 潇，王江晴

(中南民族大学计算机科学学院，武汉 430074)

摘 要：蚁群算法在求解车辆路径问题过程中存在搜索时间长、易于陷入局部最优解的问题。为此，设计并实现一种混合蚁群算法。引入变异算子增强算法的全局搜索能力，采用2-opt法优化阶段最优解的子路径。通过对信息素的挥发因子进行动态调整，从而有效控制信息量的变化速度。实例仿真结果表明，该算法具有较好的求解效率和寻优效果。 关键词：车辆路径问题；混合蚁群算法；变异算子；线路改进；动态规划

Application of Hybrid Ant Colony Algorithm

in Vehicle Routing Problem

ZHANG Xiao, WANG Jiang-qing

(School of Computer Science, South-central University for Nationalities, Wuhan 430074, China)

【Abstract】Ant Colony Algorithm(ACA) has some short-comings such as its slow computing speed, and it is easy to fall in a local optimal. Based on the idea of ACA, a hybrid optimization algorithm for solving Vehicle Routing Problem(VRP) is proposed. The algorithm expands the scope of solution space and improves the global ability of the algorithm by importing mutation operator, optimizes the stage optimal solution further by combining 2-opt, and controls the rate of change in pheromone by adjusting configuration of parameters dynamically. Example simulation results show that this algorithm can get optimal resolution of VRP effectively and quickly.

【Key words】Vehicle Routing Problem(VRP); hybrid Ant Colony Algorithm(ACA); mutation operator; line improvement; dynamic programming DOI: 10.3969/j.issn.1000-3428.2011.24.063

1 概述

车辆路径问题(Vehicle Routing Problem, VRP)自提出以来，已引起了研究者们的广泛兴趣，设计了多种求解算法。这些算法主要分为精确算法和近似算法。精确算法包括分支定界方法、动态规划方法等，这类算法引入了严格的数学方法，在求解中小规模VRP时优于近似算法，但无法避免组合爆炸问题。最近邻算法、r-opt算法，以及禁忌搜索法、模拟退火算法[1-2]及蚁群算法(Ant Colony Algorithm, ACA)等都属于近似算法。

在求解大规模VRP时，这类算法通常可以在有限的时间里找到满意解或可行解，这是精确算法难以达到的。蚁群算法是一种源于大自然的新型仿生类算法[3]，它是受蚂蚁觅食行为的启发，根据蚂蚁寻找从蚁巢到食物的最短路径时的搜索机制设计而成的一种算法。近年来，许多国内外专家学者在蚁群算法的改进以及与其他算法混合等方面做了大量的研究工作[4-5]，进一步提高了该算法的寻优能力、全局收敛性并拓宽了它的应用领域，但仍存在容易陷入局部优化、搜索速度较慢等问题。

本文引入遗传算法中的变异算子，结合线路改进算法中的邻域局部改进机制及MAX-MIN蚂蚁系统局部改进机制，同时对算法参数进行分析与研究，进一步改善了算法性能。

同时保证每条路径上的各客户的总需求量不超过此条路径配送车辆的容量。

数学模型如下：

minZ=∑∑∑cijxijk (1)

i

jk

s.t.

i

∑giyki≤qk k (2)

ki

i=L,L (3) ∑yki=1 1,2,

j=0,1,L,L; k (4) ∑xijk=yki i,

3 混合蚁群算法

3.1 变异算子的引入

3.1.1 交叉变异算子

在阶段解中随机选择2条子路径ri和rj，在ri中随机选择一个客户点m，同理在rj中随机选择一个客户点n，交叉互换m、n在ri和rj中的位置，形成2个新的子路径。若新的子路径不满足车载容量限制，则重新选择。

3.1.2 插入变异算子

在阶段解中随机选择2条子路径ri和rj，在ri中随机选

在rj中随机选择一个位置点s，将客户点m择一个客户点m，

插入到s位置，形成2个新的子路径。若新的子路径不满足车载容量限制，则重新选择。

基金项目：国家自然科学基金资助项目“复杂环境下动态车辆路径问题的建模与优化”(60842004)

作者简介：张 潇(1986－)，男，硕士研究生，主研方向：蚁群算法，人工智能；王江晴，教授、博士

收稿日期：2011-03-23 E-mail：zx156996098@126.com

2 数学模型

有一个中心仓库，拥有K辆车，容量分别为qk(k=1,

2,…,K)；现有L个客户有运输任务；第i个客户点的货运量为gi(i=0,1,2,…,L，其中，0为中心仓库编号；max(gi)≤max(qk))；从客户i到j的运输成本为cij。要求每个客户都得到车辆的服务，并且每个客户的需求仅能由某一辆车完成，