西安电子科技大学学报 ›› 2016, Vol. 43 ›› Issue (3): 185-189.doi: 10.3969/j.issn.1001-2400.2016.03.032

• 研究论文 • 上一篇    下一篇

改进蚁群算法的多约束质量最优路径选择

马荣贵;崔华;薛世焦;郭璐;袁超   

  1. (长安大学 信息工程学院,陕西 西安  710064)
  • 收稿日期:2015-08-24 出版日期:2016-06-20 发布日期:2016-07-16
  • 通讯作者: 马荣贵
  • 作者简介:马荣贵(1967-),男,教授,博士,E-mail: rgma@che.edu.cn.
  • 基金资助:

    国家“863”计划资助项目(2012AA112312);中央高校基本科研业务费专项资金重点资助项目(310824152009)

Improved ant colony algorithm for the optimal-quality-path routing problem with multi-constraints

MA Ronggui;CUI Hua;XUE Shijiao;GUO Lu;YUAN Chao   

  1. (School of Information Engineering, Chang'an Univ., Xi'an  710064, China)
  • Received:2015-08-24 Online:2016-06-20 Published:2016-07-16
  • Contact: MA Ronggui

摘要:

在交通拥堵日益严重的形势下,当今大众对行车过程中的道路质量评定标准发生了重大变化,如何避开拥堵,寻找最优的出行路径,已成为智慧城市建设大力推进背景下亟待解决的重要科学问题和社会问题.首先,定义了质量最优路径的概念,并构建了多约束质量最优路径模型;然后,为更有效求解该模型实现最优路径选择,在基本蚁群路径寻优算法的基础上,通过增加算法对道路通畅度、道路舒适度、道路费用等路径质量信息的实时感知,改进了状态转移规则中的启发函数和信息素更新算子,提高了算法自适应于路径质量信息的动态调整能力.实验结果表明:文中改进的蚁群算法与其他蚁群路径寻优算法相比,明显提高了路径寻优的正确率和收敛速度,能够更加快速、准确地进行路径选择.

关键词: 多约束路径选择, 质量最优路径, 蚁群算法, 信息素更新, 启发函数

Abstract:

As the traffic congestion becomes more and more serious, the public evaluation standard for the road quality during driving changes greatly. How to avoid congestion to find the best way to travel has become an important scientific issue and social issue urgent to address in the context of building a smart city. Thus this paper first defines the novel concept of optimal path with multi-constraints and models it. Then, in order to solve the proposed model more efficiently, we improve the state transition rules of the heuristic function and pheromone update operator based on the classical ant colony algorithm by increasing the path optimization algorithm's awareness of real-time path quality information, such as traffic conditions, resulting in the strong dynamic adjustment ability of our proposed path optimization algorithm to path information. Simulation results show that our proposed ant colony algorithm can find the optimal path with multi-constraints more accurately and more quickly than other ant colony algorithms.

Key words: multi-constraint path routing, optimal quality path, ant colony algorithm, pheromone update, heuristic function

中图分类号: 

  • TP751