求解车辆路径问题的改进蚁群算法  

An Improved Ant Colony Algorithm Based on Vehicle Routing Problem

作　　者：王占锋[1] 杜海莲[2] 安素芳[1] 张翠军[1] 

机构地区：[1]石家庄经济学院信息工程学院,河北石家庄050031 [2]河北师范大学电子系,河北石家庄050023

出　　处：《华侨大学学报（自然科学版）》2013年第1期36-39,共4页Journal of Huaqiao University(Natural Science)

基　　金：石家庄经济学院自然科学基金资助项目(ZR201101);河北师范大学科研基金资助项目(L2011Q10)

摘　　要：为解决基本蚁群算法的过早收敛的缺陷,提出一种将遗传算法和蚁群算法融合的改进的蚁群算法.即使用蚁群算法求解出完成所有配送任务的车辆行驶路径,并将其作为局部最优解;然后,使用遗传算法的交叉变异算子对第一步搜索出来的局部最优解进行优化,筛选出全局更优解.仿真实验证明:改进后的蚁群算法与现有的求解车辆路径优化问题的蚁群算法相比,具有更快的运行速度,找到最优解的概率更高,且避免了基本蚁群算法的过早收敛.The basic ant colony algorithm has the defects of premature convergence.In order to solve the problem,a fusion algorithm of a genetic algorithm and ant colony algorithm is put forward.First of all,the basic ant colony algorithm is adopted to produce a vehicle path solution of all the task of distribution,the vehicle path solution is processed as a local optimal solution.Furthermore,the crossover and mutation operator of genetic algorithm is used to optimize the local optimal solution,thus a global optimal solution is obtained.Simulated experimental result shows that the improved ant algorithm has faster operation speed and higher probability to obtain the global optimal solution than that of the basic ant colony algorithm,it also avoid the premature convergence of the basic ant colony algorithm.

关 键 词：车辆路径问题 蚁群算法 遗传算法 变异算子 优化问题 收敛 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] U116.2[自动化与计算机技术—计算机科学与技术]