Abstract: Based on the basic concepts of traditional Tabu search algorithm，a meliorative Tabu search algorithm for solving TSP has been proposed.This algorithm has great improvement in initial solution’s production，neighbor structure and taboo strategy. Furthermore，it makes full use of heuristic information and Tabu search algorithm’s advantages.At first，this algorithm divides the cities into certain areas.Then，it connects these areas into a path，so that，we can get the initial solution.Meanwhile，we produce the cities k-neighbor list and use them with the improved taboo strategies to break through the local optimum.In this paper，we apply the algorithm to solve the CHN144 problem and some problems in TSP library（TSPLIB）.The result shows that the novel algorithm can achieve satisfied solution with satisfied speed.

Key words: Tabu search algorithm, heuristic algorithm, Traveling Salesman Problem

摘要： 利用传统的禁忌算法的基本思想，针对TSP问题，提出了一种改进的禁忌算法（MTS）。该算法在初始解的生成，邻域结构及禁忌策略方面进行了大的改进，充分地利用了问题本身的启发式信息与禁忌算法的优点。算法首先通过对城市分区，然后对区域连接，生成初始解；同时生成每个城市的k邻居列表，利用k邻居列表和改进的禁忌策略来突破局部最优。通过对CHN144问题及若干TSPLIB中问题的求解，结果表明所提算法能够以较快速度求得较好的满意解。

关键词: 禁忌算法, 启发式算法, 旅行商问题