[1]王占锋,杜海莲,安素芳,等.求解车辆路径问题的改进蚁群算法[J].华侨大学学报(自然科学版),2013,34(1):36-39.[doi:10.11830/ISSN.1000-5013.2013.01.0036]
　WANG Zhan-feng,DU Hai-lian,AN Su-fang,et al.An Improved Ant Colony Algorithm Based on Vehicle Routing Problem[J].Journal of Huaqiao University(Natural Science),2013,34(1):36-39.[doi:10.11830/ISSN.1000-5013.2013.01.0036]
点击复制

求解车辆路径问题的改进蚁群算法()
分享到：

《华侨大学学报（自然科学版）》[ISSN:1000-5013/CN:35-1079/N]

卷:
第34卷
期数:
2013年第1期
页码:
36-39
栏目:
出版日期:
2013-01-20

文章信息/Info

Title:
An Improved Ant Colony Algorithm Based on Vehicle Routing Problem
文章编号:
1000-5013(2013)01-0036-04
作者:
王占锋1;  杜海莲2;  安素芳1;  张翠军1
1. 石家庄经济学院 信息工程学院, 河北 石家庄 050031;2. 河北师范大学 电子系, 河北 石家庄 050023
Author(s):
WANG Zhan-feng1;  DU Hai-lian2;  AN Su-fang1;  ZHANG Cui-jun1
1. College of Information and Engineering, Shijiazhuang University of Economics, Shijiazhuang 050031, China; 2. Electronic Department, Hebei Normal University, Shijiazhuang 050023, China
关键词:
车辆路径问题;  蚁群算法;  遗传算法;  变异算子;  优化问题;  收敛
Keywords:
vehicle routing problem;  ant colony algorithm;  genetic operator;  mutation operator;  optimization problem;  convergence
分类号:
TP301.6;U116.2
DOI:
10.11830/ISSN.1000-5013.2013.01.0036
文献标志码:
A
摘要:
为解决基本蚁群算法的过早收敛的缺陷,提出一种将遗传算法和蚁群算法融合的改进的蚁群算法.即使用蚁群算法求解出完成所有配送任务的车辆行驶路径,并将其作为局部最优解;然后,使用遗传算法的交叉变异算子对第一步搜索出来的局部最优解进行优化,筛选出全局更优解.仿真实验证明:改进后的蚁群算法与现有的求解车辆路径优化问题的蚁群算法相比,具有更快的运行速度,找到最优解的概率更高,且避免了基本蚁群算法的过早收敛.
Abstract:
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.

参考文献/References:

[1] 潘正君,康立山,陈毓屏.演化计算[M].北京:清华大学出版社,1998.
[2] 段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005.
[3] DORIGO M,MANIEZZO V,COLOMI A.The ant system: Optimization by a colony of cooperating agents[J].IEEE Transactions on Systems, Man, and Cybernetics: Part B,1996,26(1):29-41.
[4] 姜大立,杨西龙,杜文,等.车辆路径问题的遗传算法研究[J].系统工程理论与实践,1999,19(6):40-44.
[5] 王占锋,张翠军,许冀伟,等.求解非满载车辆调度问题的改进遗传算法[J].计算机工程与设计,2008,29(15):3991-3993.
[6] WANG Zhan-feng, DU Hai-lian, HU Ji-chao, et al. An improved genetic algorithm for vehicle routing problem of non-full load[C]//3rd International Symposium on Intelligent Information Technology Application. Washington
　　 D C:IEEE Computer Society,2009:173-175.
[7] 樊建华,王秀峰.基于免疫算法的车辆路径优化问题[J].计算机工程与应用,2006,42(4):210-212,217.
[8] 张翠军,刘坤起.求解一般车辆优化调度问题的一种改进遗传算法[J].计算机工程与应用,2004,40(33):207-208,211.
[9] 戴树贵,陈文兰,潘荫荣,等.多配送中心车辆路径安排问题混合蚁群算法[J].四川大学学报:工程科学版,2008,40(6):154-158.
[10] BULLNHEIMER B,HARTL R,STRAUSS C.An improved ant system algorithm for the vehicle routing problem[J].Annals of Operation Research,1999,89(13):319- 328.
[11] BRYSY O,DULLAERT W.A fast evolutionary metaheuristic for the vehicle routing problem with time windows[J].International Journal of Artifical Intelligence Tools,2002,12(2):143-157.
[12] 柳林,朱建荣.基于混合蚂蚁算法的物流配送路径优化问题研究[J].计算机工程与应用,2006,42(13):203-205.
[13] GLOVER F.Tabu search: a tutorial[J].Interfaces,1990,20(4):74-94.
[14] 丁建立,陈增强,袁著祉.遗传算法与蚂蚁算法的融合[J].计算机研究与发展,2003,40(9):1351-1356.
[15] 陈陵,沈洁,秦玲,等.基于分布均匀度的自适应蚁群算法[J].软件学报,2003,14(8):1379-1387.
[16] 张翠军,张敬敏,王占锋.基于车辆路径问题的蚁群遗传融合优化算法[J].计算机工程与应用,2008,44(4):233-235.
[17] 刘志硕,申金升,柴跃廷.基于自适应蚁群算法的车辆路径问题研究[J].控制与决策,2005,20(5):562-566.
[18] 唐连生,程文明,张则强,等.基于改进蚁群算法的车辆路径仿真研究[J].计算机仿真,2007,24(4):262-264.
[19] 徐强,宋海洲,田朝薇.解TSP问题的蚁群算法及其收敛性分析[J].华侨大学学报:自然科学版,2011,32(5):587-591.
[20] 杨四海.TSP的等价解及其对免疫遗传算法的干扰[J].华侨大学学报:自然科学版,2007,28(1):27-29.

相似文献/References:

[1]徐强,宋海洲,田朝薇.解TSP问题的蚁群算法及其收敛性分析[J].华侨大学学报(自然科学版),2011,32(5):588.[doi:10.11830/ISSN.1000-5013.2011.05.0588]
　XU Qiang,SONG Hai-zhou,TIAN Zhao-wei.Convergence Analysis of the Ant Colony Algorithm for Solving TSP[J].Journal of Huaqiao University(Natural Science),2011,32(1):588.[doi:10.11830/ISSN.1000-5013.2011.05.0588]
[2]彭臻,王田,李晨阳,等.采用蚁群算法的移动摄像头探访规划[J].华侨大学学报(自然科学版),2014,35(5):533.[doi:10.11830/ISSN.1000-5013.2014.05.0533]
　PENG Zhen,WANG Tian,LI Chen-yang,et al.Visit Schedule of Mobile Cameras Base on Ant Colony Optimization[J].Journal of Huaqiao University(Natural Science),2014,35(1):533.[doi:10.11830/ISSN.1000-5013.2014.05.0533]

备注/Memo

备注/Memo:
收稿日期: 2012-06-15
通信作者: 杜海莲(1978-),女, 讲师,主要从事故障诊断的研究.E-mail:duhailian@126.com.
基金项目: 石家庄经济学院自然科学基金资助项目(ZR201101); 河北师范大学科研基金资助项目(L2011Q10)
更新日期/Last Update: 2013-01-20