TSP问题的几种常用求解算法比较

摘要：本文介绍了tsp问题及其常见的解法，给出了计算实例，并结合计算实例对各求解算法进行了比较。本文对于各种算法的比较对于TSP问题的求解具有一定的参考价值。

关键词TSP问题 0-1规划 智能算法

中图分类号：O158 文献标识码：A 文章编号：1007-9416（2014）05-0139-02

旅行商问题（Traveling Salesman Problem， TSP）是典型的组合优化问题，很多优化问题都可以直接或间接的转为为TSP问题，而且TSP问题已被证明具有NPC计算复杂性，有很大的求解难度，因此研究TSP问题的求解方法有着很大的实际意义。本文旨在介绍求解TSP的几种常用解法，并结合实例比较这些算法的性能，为TSP的求解提供一些参考。

1 TSP问题描述

TSP问题的数学表述为：一个有穷的城市集合C={C1，C2，…，Cm}，对于每一对城市Ci，Cj∈C有距离d（Ci，Cj）∈R+。问：经过C中所有城市的旅行路线，记为序列，是否存在最小的正数B，对所有可能的序列都有

2 TSP问题几种常用求解方法

TSP问题有着很多求解算法，主要有。

2.1 贪婪算法

贪婪算法[2]（Greedy algorithm）是求解大规模TSP问题的常用算法之一，是一种求解优化问题的简单、迅速的求解办法。贪婪法有限考虑当前情况下最优的优化测度，自顶向下，逐步迭代，具有算法简单，耗时短的特点。但贪婪算法的求解结果往往不是最优的，甚至可能与全局最优解间有不小的差距。

2.2 模拟退火算法

模拟退火（Simulated Annealing，SA）算法是求解TSP问题的有效方法之一，容易编程实现，求解速度快。模拟退火是一种全局优化算法，加入了随机状态模型，使算法以概率选择的方式逼近最优状态，其收敛性可以得到严格的理论证明。模拟退火算法具有一整套完整的退火搜索计划，包括足够高的初始温度、缓慢的退火速度、大量的迭代次数及足够的概率扰动[3]。

2.3 遗传算法

遗传算法（Genetic Algorithm，GA）是一种常用的智能算法，具有全局搜索能力，对TSP问题有良好的效果。遗传算法是由Michigan大学的J.Holland教授于1975年提出，算法通常由编码、个体适应度评估和遗传运算三部分构成，其中遗传运算包括染色体复制、交叉、变异和倒位等[4]。

2.4 粒子群算法

粒子群算法（Particle Swarm Optimization，PSO）是依据鸟类觅食的群体性模型而发明的新型智能算法，是由美国电气工程师Eberhart和社会心理学家Kennedy于1995年提出，具有通用性强，参数少，容易实现，收敛速度快等优点，也是解决TSP问题的有效算法之一[5]。

2.5 蚁群算法

蚁群算法（Ant Colony Optimization，ACO）是根据蚂蚁发现路径的行为的而发明的用于寻求优化路径的机率型算法，由Marco Dorigo于1992年在他的博士论文中提出。蚁群算法是一种模拟进化算法，具有包括较强的鲁棒性在内的许多优良性质，在本质上是一种并行的分布式算法，容易实现，可以较好地求解TSP问题[6]。

3 实例计算

选取我国北京、天津、武汉、深圳、长沙、成都、杭州、西安、拉萨、南昌等十个城市，分别使用1-10对十个城市进行编号，获取十个城市的距离矩阵，使用上节所述算法进行求解。已知路径最小长度为12055，最优路径为2-1-8-9-6-3-5-4-10-7-2，求解结果如表1所示。

图1为四种智能算法的收敛状态。

4 各种求解算法的比较

根据本文的实例计算和相关文献[7]，可以给出各算法的比较。

5 结语

TSP问题有着很大的求解难度，但并不意味着无法进行有效的求解，使用一些比较成熟的智能化算法进行求解，可以获得较好的解答。当然各种近似求解算法还有着一些固有的缺陷，在不同情况下有着不同的性能表现，需要在使用时加以选择。

参考文献

[1]谢金星，薛毅.优化建模与Lindo/Lingo软件.北京：清华大学出版社，2005.

[2]黄辉，梁国宏等.求解一类线性规划问题的原始贪婪算法和对偶贪婪算法及其相互关系[J].兰州交通大学学报，2007，26（1）：149-152.

[3]田澎，王浣尘等.旅行商问题（TSP）的模拟退火求解[J].上海交通大学学报，1995，S1：111-116.

[4]胡玉兰.基于遗传算法的旅行商问题仿真实现[J].控制工程，2002，6：79-81.

[5]严露.粒子群算法研究与应用[D].电子科技大学硕士论文，2013.

[6]孙金香，高共革等.蚁群算法在邮路规划中应用研究[J].贵州大学学报，2008，35（2）：153-157.

[7]王敏.TSP问题及几种常见算法的比较研究[J].长安理工大学学报，2010，5（5）：184-185.