| 用基于蚂蚁算法的混合方法求解不确定TSP问题 |
| |
| 引用本文： | 胡平,常晓宇,王康平,郭东伟,周春光.用基于蚂蚁算法的混合方法求解不确定TSP问题[J].吉林大学学报(理学版),2007,45(2):221-224. |
| |
| 作者姓名： | 胡平 常晓宇 王康平 郭东伟 周春光 |
| |
| 作者单位： | 吉林大学,计算机科学与技术学院,长春,130012;吉林大学,计算机科学与技术学院,长春,130012;吉林大学,计算机科学与技术学院,长春,130012;吉林大学,计算机科学与技术学院,长春,130012;吉林大学,计算机科学与技术学院,长春,130012 |
| |
| 基金项目： | 国家自然科学基金
,
教育部重点实验室基金
,
985工程计算与软件科学科技创新平台项目 |
| |
| 摘 要： | 首次提出不确定旅行商问题模型, 此模型将路径长度看作动态可变的, 并考虑了交通运行中的不确定因素, 比经典旅行商(TSP)问题更具有灵活性及实用价值, 利用此模型得到的结果更适于指导车辆对运行路线的选择. 同时使用一种基于蚂蚁算法的混合方法求解不确定旅行商问题, 即引入3-opt方法对问题求解进行局部优化. 实验结果显示, 该方法能够加速蚂蚁算法的收敛性.
|
| 关 键 词： | 不确定规划 不确定TSP问题 蚂蚁算法 |
| 文章编号： | 1671-5489(2007)02-0221-04 |
| 收稿时间： | 2006-05-30 |
| 修稿时间： | 2006年5月30日 |
Solve Uncertain TSP Problems by Hybrid Approach Based on Ant Algorithm |
| |
| HU Ping,CHANG Xiao-yu,WANG Kang-ping,GUO Dong-wei,ZHOU Chun-guang.Solve Uncertain TSP Problems by Hybrid Approach Based on Ant Algorithm[J].Journal of Jilin University: Sci Ed,2007,45(2):221-224. |
| |
| Authors: | HU Ping CHANG Xiao-yu WANG Kang-ping GUO Dong-wei ZHOU Chun-guang |
| |
| Institution: | College of Computer Science and Technology, Jilin University, Changchun 130012, China |
| |
| Abstract: | This paper firstly proposes a uncertain traveling salesman problem(TSP) model.This model assumes that the distance between two vertices is dynamic.With the view of application,this model considers the uncertain situations in the traffic system.Compared to the classical TSP problem,this model is more flexible and also has more application value.This mode is more properly for vehicle to choose the best route.This paper also proposes a hybrid approach which is based on the ant system to solve the problem of uncertain TSP,namely,a 3-opt method is used to do the local optimization.Experiment results show that this approach can accelerate the convergence. |
| |
| Keywords: | uncertain programming uncertain traveling salesman problem ant algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《吉林大学学报(理学版)》浏览原始摘要信息 |
| 点击此处可从《吉林大学学报(理学版)》下载免费的PDF全文 |
|
