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

• 人工智能及识别技术 • 上一篇    下一篇

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

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

  1. 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 Teng1,2,ZHANG Liyi1,2,SUN Yunshan2   

  1. 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

摘要: 蚁群算法在解决车辆路径问题(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

中图分类号: