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

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

旅行商问题(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.