六种TSP算法的对比试验

TSP问题相信大家已经不陌生了，它是指假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。

解决TSP问题的算法有很多，在本期推文中，小编将会比较贪心算法、动态规划、模拟退火、禁忌搜索、LKH算法以及Concorde求解器的求解效率。

前四种算法都是求解TSP问题中较常见的算法，在往期推文中都已做过介绍，小编就不再赘述啦，想要了解这些算法的小伙伴们可以参考以下推文：

什么是算法？从枚举到贪心再到启发式（上）

干货|十分钟教你用动态规划算法解Travelling Salesman Problem（TSP）问题，附代码……

干货 | 用模拟退火(SA, Simulated Annealing)算法解决旅行商问题

干货|十分钟快速复习禁忌搜索(c++版)

而LKH算法和Concorde求解器对于一些小伙伴来说可能就比较陌生了，小编简单介绍一下：

LKH算法是目前求解 TSP 问题的最有效的启发式算法。其创造者K. Helsgaun 在网站上发布了其算法的完整代码和他自己的研究论文。链接如下：

http://webhotel4.ruc.dk/~keld/research/LKH-3/

Concorde求解器使用的是concorde精确算法，可以求出TSP问题的最优解。它还可以用于求解生物信息中的基因映射，蛋白质功能预测，调度船只等多种问题。世界上能够求解出最优解的最大规模的TSP算例就是由它求解完成的。链接如下：

http://www.math.uwaterloo.ca/tsp/concorde/downloads/downloads.htm

01

LKH与concorde的调用

虽然LKH算法与Concorde求解器是免费开放的，想轻松调用它们也不一件容易的事哦。

Concorde求解器只能读取后缀为.tsp的文件。不过这可难不倒我们。只要新建一个文本文档，将tsp文件所需的相关数据输入，再改变文件后缀就可以生成tsp文件了。格式如下图：

用求解器打开新生成的tsp文件后，点击左上方的“Solve”，这就是concorde求解器求精确解的地方。

除此之外点击“Solve”旁边的“Heuristics”可以调用其他启发式算法求解问题，如LK算法、贪心算法等。

需要注意的是，concorde求解器只接受11个节点及以上的TSP问题的求解，在遇到小于等于10个节点的问题时则无法求解的。

结果如下：

LKH算法的调用可能更复杂一些：除了下载LKH算法以外，小编还找到了一位大神写的LKH的MATLAB接口才成功地调用该算法，接口下载地址（ntnu-arl/LKH_TSP: A set of tools to solve TSP problems using the LKH solver (github.com)）

根据指导，下载LKH.exe地址如下：LKH (Keld Helsgaun) (ruc.dk)，记住它的存储位置。

新建一个txt文档，填入相关内容后用改变文件后缀的方式转化为par文件（划线处填入读取的文件地址），格式如下：

MATLAB调用该接口的代码如下（将LKH.exe位置在MATLAB代码中赋值给变量LKHdir）：

需要注意的是，此接口读取地tsp文件与上文concorde求解器读取地文件格式有所不同，其读取的是节点之间地距离矩阵，详细格式如下图：

运行成功时结果如下图：

02

算法比较

好啦，准备工作基本完成，让我们进入正题。

由于concorde求解器对算例的节点数有一定要求，小编分别取含11、13、15、17、19、21、23、50、100个节点的算例进行试验。

随机生成各个节点的坐标，输出各节点坐标及贪心算法、动态规划、模拟退火和禁忌搜索对同一算例求解所用的时间，将各节点坐标整合并生成相应tsp文件，调用LKH算法和concorde求解器，输出它们解决相应问题所用的时间。（欲下载相关代码，请移步留言区）

对各个数据规模，各算法的求解消耗时间对比如下（纵轴单位：ms ）：

动态规划由于数据过大，所以小编单独列了一张图（纵轴单位：ms）:

可以发现,当数据规模较小时，六种算法的求解速度几乎没有差别，当数据规模增大时，算法之间的求解速度差别就显而易见了。

其中较为特殊的是贪心算法，它不从整体最优上加以考虑，其所做出的仅是在某种意义上的局部最优解，因此其速度虽然快，但求解正确率却实在不高。

撇开贪心算法不谈，其他算法中速度较优的也许就要数LKH算法了，真不愧是求解tsp问题最牛叉的算法。

Concorde求解器虽然看似花费时间较长，但它求出的是精确解，也就是说，它的正确率可以达到100%。

说到正确率，这里还有一张关于各算法求出最好解的表格：

其中较为特殊的是动态规划算法，由于Java平台限制了数组的最大长度，所以较大的数据动态规划算法就无法计算了。

细心的小伙伴可能已经发现了，此处禁忌搜索表现不佳，其实禁忌搜索是一种思想，算法的效率取决于代码编写者，此处禁忌搜索表现不佳并不意味着，禁忌搜索不如模拟退火等算法。

可以看到，在数据较小的时候动态规划和模拟退火的正确率还算可以接受，而当数据足够大时，LKH算法与concorde精确求解器的威力就显现出来了。

给小伙伴们展示一下500节点时，concorde求解器的求解情况，真的让小编有一种震撼的感觉：

需要说明的是，算法的运行效果与很多因素有关，如设计思路、实现过程、编写语言、计算机的性能等，小编这次只是大致比较了其中一种情况，并不是很严谨。感兴趣的小伙伴也可以自己尝试一下。

REFERENCE

动态规划代码来源：动态规划求解旅行商问题（java实现）_天阑Sir的博客-CSDN博客_java旅行商问题动态规划

禁忌搜索代码来源：禁忌搜索算法的实现_Python_ttphoon的博客-CSDN博客

MATLAB代码来源：用matlab调用迄今为止最强悍的求解旅行商（TSP）的算法-LKH算法 - 知乎 (zhihu.com)

matlab接口下载地址：：ntnu-arl/LKH_TSP: A set of tools to solve TSP problems using the LKH solver (github.com)

LKH.exe下载地址：LKH (Keld Helsgaun) (ruc.dk)

欲下载相关代码，请移步留言区

- END -