Abstract: This paper proposes a novel method，which combines the problem-independent evolution algorithm and problem-
dependent local search，to solve TSP.This method adopts an improved ant colony algorithm based on the cloud model to generate high-quality solutions，and improves the traditional LK algorithm by addition of 5 new criterions to refine the element searching in the deletion set and the addition set.Experiments on different types and city numbers ranged from 48 to 33，810 show that the proposed method is superior to algorithms not only within this school but also among other schools in respect of the gap and computation time.Besides，the application to asymmetric TSP and Hamilton cycle problem also demonstrate the efficacy and efficiency of the proposed method.

Key words: membership cloud, ant colony algorithm, Lin and Kernighan’s algorithm, traveling salesmen problem, asymmetric traveling salesman problem, Hamiltonian cycle problem

摘要： 提出一种求解TSP的算法，采用“问题无关的进化算法与问题相关的局部搜索相结合”的策略。采用基于云模型的蚁群算法来产生足够好的解；改进传统的LK算法，新加入5种搜索删除集与添加集元素的准则，以此细化搜索。将该算法用于求解TSPLIB中不同类型、城市数从48到33 810内变化的TSP，比较该学派与其他学派算法的偏离率与运行时间，结果均显示该算法更优，有效求解了TSPLIB中的非对称TSP、哈密尔顿圈问题。

关键词: 隶属云, 蚁群算法, LK算法, 旅行商问题, 非对称旅行商问题, 哈密尔顿圈问题