以TSP为代表的组合优化问题研究现状与展望  

Study on Combinatorial Optimization Problem represented by TSP: Recent Research Work and Perspective

作　　者：严晨[1] 王直杰[1] 

机构地区：[1]东华大学信息科学与技术学院自动化系,上海201620

出　　处：《计算机仿真》2007年第6期171-174,247,共5页Computer Simulation

基　　金：上海市优秀青年教师后备人员基金(03yqhb074)

摘　　要：旅行商问题(TSP)是运筹学的著名命题,也是目前研究最为广泛的组合优化问题之一。对TSP的研究成果将对求解NP类问题产生重要影响。首先给出组合优化问题和TSP问题的基本概念。然后综述了以TSP为代表的组合优化问题的研究历史和现状,并着重对传统方法和启发式现代智能优化算法做了比较。最后对智能优化算法中的研究热点以及在TSP问题上的应用做了展望,预测了未来技术难点,并对今后可进一步研究的问题做了探讨。Traveling Salesman Problem is a famous proposition in operations research and one of the most widely investigated problems as a typical one of the combinatorial optimization problems. The research work on the TSP will be influential for solving the NP problems. In this article, the basic concepts of the combinatorial problem and TSP are firstly given. Then the research history and recent advances in finding the best solution to TSP are reviewed and the comparison between traditional method and modern intelligent heuristic optimization algorithm is made emphatically. Finally the future of the TSP research and hot topics in the field of intelligent optimization algorithm are previewed. Further more, bottlenecks of the future TSP research work and the further study in the future are also foreseen.

关 键 词：旅行商问题 组合优化 启发式算法 智能优化算法 综述 

分 类 号：TP183[自动化与计算机技术—控制理论与控制工程]