求解旅行商问题的几种算法的比较研究  

Comparative study of several algorithms for traveling salesman problem

作　　者：李敏[1] 吴浪[1] 张开碧[1] 

机构地区：[1]重庆邮电大学自动化学院,重庆400065

出　　处：《重庆邮电大学学报（自然科学版）》2008年第5期624-626,630,共4页Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition)

摘　　要：旅行商问题具有重要的理论和实际研究价值,在工程实践中应用广泛。采用遗传算法、蚁群算法和模拟退火算法对旅行商问题进行求解,并选取中国旅行商问题进行仿真,比较了3种算法的优劣,得出了它们各自不同的适用范围:蚁群算法适用于缓慢地较精确的求解场合;模拟退火算法适用于快速精确的求解;遗传算法适用于快速求解,但结果准备度要求不高的情况。Traveling salesman problem （TSP） is of important theoretical and practical significance and applied widely in engineering practice. The genetic algorithm, ant colony algorithm and simulated annealing were adopted to solve the traveling salesman problem, and the Chinese traveling salesman problem was chosen to simulate. Through the comparison of these three algorithms＇advantages and disadvantages, their different applications were gained： the ant colony algorithm is suitable for slow and accurate solving, the simulated annealing applies to quick and accurate solving, and the genetic algorithm is for quick but low accurate solving.

关 键 词：旅行商问题 遗传算法 蚁群算法 模拟退火算法 中国旅行商问题 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]