基于禁忌表的定位算法求解TSP问题  

Position-Fixed Based on Tabu List Algorithm to TSP

作　　者：雷开友[1] 邱玉辉[1] 刘光远[2] 贺一[1] 

机构地区：[1]西南师范大学计算机与信息科学学院,重庆400715 [2]西南师范大学电子信息工程学院,重庆400715

出　　处：《计算机科学》2005年第12期210-212,共3页Computer Science

基　　金：教育部科学技术重点项目(NO.104262;重庆市科委基金项目2003-7881)

摘　　要：本文提出了一种基于禁忌表的定位算法求解TSP问题的快速、高效近似算法。这种算法结合了禁忌搜索算法中禁忌表及大规模构造算法和定位改进算法求解规模较大的TSP问题。计算机实例仿真证明,算法在求解质量和求解速度两方面高于著名的启发式算法的解。该算法针对TSP问题提出,是非常有效的。This paper proposes a fast and effective approximate algorithm-positiomfixed based on tabu list algorithm,With incorporates the tabu list in tabu search algoritym,Size Scale-construction algorithm and position-fixed improvement algorithm to solv the large-scale traveling salesman problem.Position-fixed based on tabu list algorithm is specially devised for TSP,the experimental reults show that the algorithm outperforms the known best ones inquality of solution and running speed compared to the famous heuristic algorithm

关 键 词：禁忌搜索 禁忌表 TSP问题 大规模构造算法 定位改进算法 

分 类 号：O224[理学—运筹学与控制论] P228[理学—数学]