基于DNA-蚁群算法的车辆路径优化问题求解

doi:10.3969/j.issn.1000-3428.2014.12.038

计算机工程 ›› 2014, Vol. 40 ›› Issue (12): 205-208,213. doi: 10.3969/j.issn.1000-3428.2014.12.038

基于DNA-蚁群算法的车辆路径优化问题求解

费腾^1,2,张立毅^1,2,孙云山²

1.天津大学电子信息工程学院,天津 300072; 2.天津商业大学信息工程学院,天津 300134

收稿日期:2013-11-12 修回日期:2014-01-23 出版日期:2014-12-15 发布日期:2015-01-16
作者简介:费腾(1983-),女,实验师、博士研究生,主研方向:智能计算;张立毅(通讯作者),教授、博士;孙云山,副教授、博士。
基金资助:
中国物流学会基金资助项目(2012CSLKT027)。

Solution of Vehicle Routing Optimization Problem Based on DNA-ant Colony Algorithm

FEI Teng^1,2,ZHANG Liyi^1,2,SUN Yunshan²

1.School of Electronic Information Engineering,Tianjin University,Tianjin 300072,China;
2.College of Information Engineering,Tianjin University of Commerce,Tianjin 300134,China

Received:2013-11-12 Revised:2014-01-23 Online:2014-12-15 Published:2015-01-16

摘要/Abstract

摘要： 蚁群算法在解决车辆路径问题(VRP)时存在过早收敛于局部最优解、收敛速度慢等问题,并且由于蚁群算法的参数选择没有严格规定,如果参数选择不当,将影响其寻找最优解的效率。为解决上述问题,将DNA算法中的交叉变异思想应用于基本蚁群算法中,提出一种新的DNA-蚁群算法,将基本蚁群算法中的参数进行DNA交叉变异,有效控制蚁群算法的参数选择,从而得到一组最优参数来求解VRP模型。实验结果表明,DNA-蚁群算法能有效解决车辆路径优化问题,更快寻找到全局最优解或较优解,提高了基本蚁群算法的寻优能力和效率。

关键词: DNA-蚁群算法, 基本蚁群算法, 车辆路径优化问题, 交叉变异, 信息素更新

Abstract: The ant colony algorithm for solving the Vehicle Routing Problem(VRP) has the problem of premature convergence to local optimal solution rather than the global optimal solution and slow convergence speed are still exist.The parameter selection of the ant colony algorithm is not strictly required,and it affects the efficiency of its search for the optimal solution if improper parameter selection.In order to solve these problems,this paper proposes a new DNA-ant colony algorithm.The parameters of basic ant colony algorithm are optimized by the crossover and mutation in DNA algorithm to effectively control the parameters of the ant colony algorithm.It chooses the best parameters to solve the VRP model.Experimental results show the algorithm can find the optimum solution or the optimal solution of VRP model,solve the vehicle routing optimization problem effectively,and improve optimization ability and efficiency of the basic ant colony algorithm.

Key words: DNA-ant colony algorithm, basic ant colony algorithm, vehicle routing optimization problem, crossover variation, pheromone update

中图分类号:

TP301.6

费腾,张立毅,孙云山. 基于DNA-蚁群算法的车辆路径优化问题求解[J]. 计算机工程, 2014, 40(12): 205-208,213.

FEI Teng,ZHANG Liyi,SUN Yunshan. Solution of Vehicle Routing Optimization Problem Based on DNA-ant Colony Algorithm[J]. Computer Engineering, 2014, 40(12): 205-208,213.

https://www.ecice06.com/CN/Y2014/V40/I12/205

参考文献

[1] Dantizig G,Ramser J.The Truck Dispatching Problem[J].Management Science,1959,6(1):80-91.
[2] 刘士新,宋建海,唐加福.蚁群最优化模型、算法及应用综述[J].系统工程学报,2004,19(5):496-502.
[3] 王凌.智能优化算法及其应用[M].北京:清华大学出版社,2009.
[4] Lee C G,Cho D H,Jung H K.Niching Genetic Algorithm with Restricted Competition Selection for Multimodal Function Optimization[J].IEEE Transactions on Magnetics,1999,35(3):1722-1725.
[5] Eberhart R C,Shi Yuhui.Particle Swarm Optimization:Developments,Application and Resources[C]//Proceedings of 2001 Congress on Evolutionary Computation.Seoul,Korea:IEEE Press,2001:81-86.
[6] 冯宝华.蚁群优化算法的原理及改进[J].科技信息,2007,(31):94-95.
[7] 王占锋,杜海莲,安素芳,等.求解车辆路径问题的改进蚁群算法[J].华侨大学学报:自然科学版,2013,34(1):36-39.
[8] 范小宁,徐格宁,杨瑞刚.车辆配送路径优化的新型蚁群算法[J].计算机工程与应用,2011,47(26):232-233.
[9] 费腾.基于蚁群算法的医疗器械物流配送路径优化算法研究[D].太原:太原理工大学,2010.
[10] 李娅,王东.多策略优化的蚁群算法求解带时间窗车辆路径问题[J].计算机数字工程,2013,41(4):152-515.
[11] 陈霄.DNA遗传算法及其应用研究[D].杭州:浙江大学,1996.
[12] Lipton R J.DNA Solution of Hard Computational Problems[J].Science,1995,268(5210):542-545.
[13] 宋晓琳,于德介,金耀,等.基于DNA免疫算法的汽车主动悬架模糊规则优化[J].振动与冲击,2007,26(9):63-66.
[14] 李仁厚,余文.关于DNA计算的基本原理与探讨[J].计算机学报,2001,24(9):972-978.
[15] 费腾,韩应征,张立毅,等.免疫蚁群算法在常规医疗器械配送路径优化中的应用[J].天津商业大学学报,2010,30(2):50-53.
[16] 张立毅,费腾,刘婷,等.基于混沌蚁群算法的应急物流路径优化算法[J].中国民航大学学报,2011,29(3):61-64.
[17] 于连伯.蚁群算法的研究[J].江苏科技信息,2010,(9):43-45.
[18] 刘诚,陈治亚,封全喜.带软时间窗物流配送车辆路径问题的并行遗传算法[J].系统工程,2005,23(10):7-11

选择文件类型/文献管理软件名称

选择包含的内容

基于DNA-蚁群算法的车辆路径优化问题求解

Solution of Vehicle Routing Optimization Problem Based on DNA-ant Colony Algorithm

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

本文评价

[1]	葛非, 闵珊, 邱含, 代振阳, 杨智敏. 求解时间依赖型绿色车辆路径问题的算法研究[J]. 计算机工程, 2024, 50(4): 1-10.
[2]	马震远,梁钰彬,李俊. 最优切割与全路径匹配交叉的2E-VRP优化算法[J]. 计算机工程, 2015, 41(8): 279-285.
[3]	曲艳峰, 蒋丹. 基于八叉树建模和ACA的三维管路路径规划[J]. 计算机工程, 2011, 37(23): 4-7.
[4]	曹炬, 李婷婷, 贾红. 带有遗传算子的烟花爆炸优化算法[J]. 计算机工程, 2010, 36(23): 149-151,154.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于DNA-蚁群算法的车辆路径优化问题求解

Solution of Vehicle Routing Optimization Problem Based on DNA-ant Colony Algorithm

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

本文评价