基于混沌扰动和邻域交换的蚁群算法求解车辆路径问题

doi:10.3724/SP.J.1087.2012.00444

计算机应用 ›› 2012, Vol. 32 ›› Issue (02): 444-447.DOI: 10.3724/SP.J.1087.2012.00444

基于混沌扰动和邻域交换的蚁群算法求解车辆路径问题

李娅,王东

佛山科学技术学院电子与信息工程学院，广东佛山 528000

收稿日期:2011-08-08 修回日期:2011-09-20 发布日期:2012-02-23 出版日期:2012-02-01
通讯作者: 李娅
作者简介:李娅(1978-)，女，湖北黄石人，讲师，硕士，主要研究方向：智能优化算法；
王东(1970-)，男，黑龙江甘南人，副教授，博士，主要研究方向：组合优化、智能计算。
基金资助:
广东省自然科学基金资助项目(10152800001000029);广东省科技计划工业攻关项目(2011B010200031)

Ant colony optimization algorithm based on chaotic disturbance and neighborhood exchange for vehicle routing problem

LI Ya,WANG Dong

College of Electronics and Information Engineering, Foshan University, Foshan Guangdong 528000, China

Received:2011-08-08 Revised:2011-09-20 Online:2012-02-23 Published:2012-02-01
Contact: LI Ya

摘要/Abstract

摘要： 为求解车辆路径问题，提出一种新的基于混沌扰动和邻域交换的蚁群算法。针对标准蚁群算法存在搜索时间长，容易出现早熟收敛，得到的解不是最优解等缺点，新算法利用混沌的随机性、遍历性及规律性，在算法陷入早熟时，对小部分路径的信息素采用混沌扰动策略进行调整；针对标准蚁群算法的贪心规则随机性缺点，新算法采用邻域交换策略对最优解进行调整。在用于求解不同规模车辆路径问题的仿真结果表明,新算法比标准蚁群算法和遗传算法具有更好的效果。

关键词: 蚁群算法, 车辆路径问题, 早熟, 混沌, 随机, 邻域交换

Abstract: A new ant colony algorithm based on chaotic disturbance and neighborhood exchange was proposed to solve the Vehicle Routing Problem (VRP). Concerning the standard ant colony algorithm's shortcomings such as long search time, being prone to premature convergence, non-optimal solution and so on, the new algorithm used the randomness, ergodicity and regularity of chaos to adjust the pheromone of a small part of the routes with the chaotic disturbance strategy when the algorithm was getting into a prematurity. For the standard ant colony algorithm has the greedy rule with randomness, the new algorithm used the neighborhood exchange strategy to adjust the optimal solution. The simulation results show that the new algorithm is better than the standard ant colony algorithm and genetic algorithm when solving the VRPs of different sizes.

Key words: Ant Colony Algorithm (ACA), vehicle routing problem, prematurity, chaos, randomness, neighbourhood exchange

中图分类号:

TP183

李娅王东. 基于混沌扰动和邻域交换的蚁群算法求解车辆路径问题[J]. 计算机应用, 2012, 32(02): 444-447.

LI Ya WANG Dong. Ant colony optimization algorithm based on chaotic disturbance and neighborhood exchange for vehicle routing problem[J]. Journal of Computer Applications, 2012, 32(02): 444-447.

参考文献

[1]吴洁明.物流配送车辆路径优化问题的仿真研究[J].计算机仿真, 2011,28(7): 357-360. [2]巩固，胡晓婷，卫开夏，等.物流配送车辆路径问题的优化研究[J].计算机工程与科学, 2011, 33(5): 106-111. [3]COLORNI A, DORIGO M, MANIEZZO V. An investigation of some properties of an "Ant algorithm"[C]// PPSN'92: Proceedings of the Parallel Problem Solving from Nature Conference. Brussels: Elsevier Publishing, 1992: 509-520. [4]李兵, 蒋慰孙. 混沌优化方法及其应用[J].控制理论与应用, 1997, 14(4): 613-615. [5]张国平, 王正欧, 袁国林.求解一类组合优化问题的混沌搜索法[J].系统工程理论与实践, 2001, 21(5): 102-105. [6]LI LIXIANG，YANG YIXIAN， PENG HAIPENG, et al. An optimization method inspired by "chaotic" ant behavior[J]．International Journal of Bifurcation and Chaos，2006， 16(8): 2351-2364． [7]杨进, 马良.蜂群优化算法在车辆路径问题中的应用[J].计算机工程与应用, 2010, 46(5): 214-216. [8]高尚, 杨静宇. 混沌粒子群优化算法研究[J]. 模式识别与人工智能, 2006,19(2): 266-270. [9]朱绍伟, 徐夫田，滕兆明. 一种改进蚁群算法求解最短路径的应用[J].计算机技术与发展, 2011,21(7): 202-205. [10]陈萍, 黄厚宽, 董兴业.基于多邻域的车辆路径优化迭代局部搜索算法[J].北京交通大学学报, 2009, 33(2):1-5. [11]孟红记, 郑鹏, 梅国晖. 基于混沌序列的粒子群优化算法[J].控制与决策,2006,21(3):263-266. [12]段海滨.蚁群算法原理及其应用[M].北京：科学出版社，2005：35,42,126. [13](意)DORIGO M,(德)STUTZLE T. 蚁群优化[M].张军,胡晓敏,罗旭耀,等译.北京：清华大学出版社，2007:31. [14]朱锦新.基于空间聚类和蚁群算法的车辆路径问题的研究[J].盐城工学院学报:自然科学版，2009,22(4):46-47. [15]刘长明，叶春平.基于逻辑自映射的变尺度混沌粒子群优化算法[J].计算机应用研究，2011,28(8):2825-2827.

基于混沌扰动和邻域交换的蚁群算法求解车辆路径问题

Ant colony optimization algorithm based on chaotic disturbance and neighborhood exchange for vehicle routing problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	刘晓光, 靳少康, 韦子辉, 梁铁, 王洪瑞, 刘秀玲. 基于阈值和极端随机树的实时跌倒检测方法[J]. 计算机应用, 2021, 41(9): 2761-2766.
[2]	徐丽云, 闫涛, 钱宇华. 基于级联混沌系统的分数域语音加密算法[J]. 计算机应用, 2021, 41(9): 2623-2630.
[3]	杨瑞, 钱晓军, 孙振强, 许振. 自然场景下多区域特征融合的混合航拍图像分割算法[J]. 计算机应用, 2021, 41(8): 2445-2452.
[4]	汤安迪, 韩统, 徐登武, 谢磊. 混沌精英哈里斯鹰优化算法[J]. 计算机应用, 2021, 41(8): 2265-2272.
[5]	黄少伟, 黄婉琳, 雷闰龙, 毛雪松. 基于脉冲位置幅度调制的距离速度同时测量[J]. 计算机应用, 2021, 41(7): 2145-2149.
[6]	余敦辉, 张蕗怡, 张笑笑, 毛亮. 基于知识图谱和重启随机游走的跨平台用户推荐方法[J]. 计算机应用, 2021, 41(7): 1871-1877.
[7]	陆国庆, 孙昊. 基于随机行走的群机器人二维地图构建[J]. 计算机应用, 2021, 41(7): 2121-2127.
[8]	汤安迪, 韩统, 徐登武, 谢磊. 基于混沌麻雀搜索算法的无人机航迹规划方法[J]. 计算机应用, 2021, 41(7): 2128-2136.
[9]	谢雨, 蒋瑜, 龙超奇. 基于随机子空间的扩展隔离林算法[J]. 计算机应用, 2021, 41(6): 1679-1685.
[10]	李进, 王凤, 杨沈宇. 换电模式下电动车货运路径优化模型与算法[J]. 计算机应用, 2021, 41(6): 1792-1798.
[11]	张杨, 董士程. 面向并发程序中锁机制的智能化推荐方法[J]. 计算机应用, 2021, 41(6): 1597-1603.
[12]	王家瑞, 谭国平, 周思源. 高速车联网场景下分簇式无线联邦学习算法[J]. 计算机应用, 2021, 41(6): 1546-1550.
[13]	韦铭燕, 陈彧, 张亮. 针对混合变量优化问题的协同进化蚁群优化算法[J]. 计算机应用, 2021, 41(5): 1412-1418.
[14]	贾鹤鸣, 姜子超, 李瑶, 孙康健. 基于改进斑点鬣狗优化算法的同步优化特征选择[J]. 计算机应用, 2021, 41(5): 1290-1298.
[15]	张康, 陈建平. 复杂环境下基于采样空间自调整的航迹规划算法[J]. 计算机应用, 2021, 41(4): 1207-1213.