旅行商问题(TSP)的几种求解方法  

Several Methods for Solving Traveling Salesman Problem

作　　者：田贵超[1] 黎明[1] 韦雪洁[1] 

机构地区：[1]南昌航空工业学院测试技术与控制工程系,江西南昌330034

出　　处：《计算机仿真》2006年第8期153-157,共5页Computer Simulation

基　　金：国家自然基金(60475002)

摘　　要：旅行商问题(TSP)是组合优化领域里的一个典型的、易于描述却难以处理的NP完全难题,其可能的路径数目与城市数目是呈指数型增长的,求解非常困难。而快速、有效地解决TSP有着重要的理论价值和极高的实际应用价值。该文首先介绍了什么是TSP,接着论述了六种目前针对TSP比较有效的解决方法(模拟退火算法、禁忌搜索算法、Hopfie ld神经网络优化算法、蚁群算法、遗传算法和混合优化策略)的基本思想,并且简单阐述了它们的求解过程,最后分别指出了各自的优缺点并对解决TSP的前景提出了展望。The Traveling Salesman Problem （TSP） is one of the typical NP - Complete hard problems in combinatorial optimization, which is easy to he described hut hard to he solved. Its possible amounts of path increase exponentially with the amounts of city,so it is very difficult to solve. But to solve TSP quickly and effectively has important theoretical values and high practical application values. TSP is first introduced in this paper. Then the basic thoughts of six effective methods （simulated annealing algorithm, taboo search algorithm, Hopfield neural networks optimization algorithm, ant colony algorithm, genetic algorithms and hybrid optimization strategy） for solving TSP and their processes are discussed. At last, theadvantages and disadvantages of the six main solving methods are respectively indicated, and the prospect for the future of solving TSP is provided.

关 键 词：旅行商问题 组合优化 路径 展望 

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