求解TSP问题算法综述  

A Survey of Solving the Traveling Salesman Problem

作　　者：王剑文[1] 戴光明[1] 谢柏桥[1] 张全元[1] 

机构地区：[1]中国地质大学(武汉)计算机学院,湖北武汉430074

出　　处：《计算机工程与科学》2008年第2期72-74,155,共4页Computer Engineering & Science

基　　金：湖北省自然科学基金资助项目(2003ABA045)

摘　　要：TSP问题(旅行商问题)是一个典型的组合优化问题,具有重要实际应用价值。对于大规模TSP问题,至今尚未找到非常有效的求解方法。为此,本文讨论了传统的确定性算法和流行的智能算法,并指出各种方法的优缺点,提出了未来求解TSP问题的发展趋势。The traveling salesman problem （TSP） is a typical combination optimization problem, and possesses a practical application value. However, there is no effective corresponding solution to it today. So, in this paper, the traditionally affirmative methods and popular meta-heuristic methods are discussed. The advantages and disadvantages of each method are discussed. The future research direction of the TSP problem is also given.

关 键 词：旅行商问题 动态规划法 分枝限界法 遗传算法 郭涛算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]