用基于蚂蚁算法的混合方法求解不确定TSP问题

用基于蚂蚁算法的混合方法求解不确定TSP问题

胡平, 常晓宇, 王康平, 郭东伟, 周春光

吉林大学计算机科学与技术学院, 长春 130012

收稿日期:2006-05-30 修回日期:1900-01-01 出版日期:2007-03-26 发布日期:2007-03-26
通讯作者: 胡平

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

College of Computer Science and Technology, Jilin University, Changchun 130012, China

Received:2006-05-30 Revised:1900-01-01 Online:2007-03-26 Published:2007-03-26
Contact: HU Ping

摘要/Abstract

摘要： 首次提出不确定旅行商问题模型, 此模型将路径长度看作动态可变的, 并考虑了交通运行中的不确定因素, 比经典旅行商(TSP)问题更具有灵活性及实用价值, 利用此模型得到的结果更适于指导车辆对运行路线的选择. 同时使用一种基于蚂蚁算法的混合方法求解不确定旅行商问题, 即引入3-opt方法对问题求解进行局部优化. 实验结果显示, 该方法能够加速蚂蚁算法的收敛性.

关键词: 不确定规划, 不确定TSP问题, 蚂蚁算法

Abstract: his 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 mo del 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 app roach 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.

Key words: uncertain programming, uncertain traveling salesman problem, ant algorithm

中图分类号:

TP31

胡平, 常晓宇, 王康平, 郭东伟, 周春光. 用基于蚂蚁算法的混合方法求解不确定TSP问题[J]. J4, 2007, 45(02): 221-224.

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]. J4, 2007, 45(02): 221-224.

[1]	袁华, 李文辉, 常欣. 用IAA求解约束模型多解问题[J]. J4, 2010, 07(4): 636-640.
[2]	黄岚　王康平　周春光　原媛　庞巍. 基于蚂蚁算法的混合方法求解旅行商问题[J]. J4, 2002, 40(04): 369-373.