震惊！史上已获得最优解的旅行商问题(TSP)的算例有八万五千九百个节点

很愉快的，我们又见到了我们的老朋友，旅行商问题(Travelling salesman problem, TSP)，在之前的一期推送中，我们利用团队的高配置服务器计算了利用动态规划求解旅行商问题的时间和空间消耗。看过的朋友应该还对之前的那两个增长曲线记忆犹新吧，如果还没有看过，那赶紧去看一下哦，下面给出上一篇文章的链接：

利用动态规划求解旅行商问题(Travelling Salesman Problem)时空复杂度分析以及相关实验验证

不过，这个时候就有一些读者会比较好奇旅行商问题这么难解，全球最领先的技术在可接受的时间范围内能解决多大规模的算例呢？为了帮助大家解决这个问题小编特地Google了一下相关的资料，竟然发现了这样一个网站？！网站的链接如下：

http://www.math.uwaterloo.ca/tsp/index.html

不看不知道，一看吓一跳，世界上能够求解出最优解的最大规模的TSP算例规模竟然已经到达了85900个节点。这个大算例是上世纪80年代中期在贝尔实验室生成的，而求解的过程是Concorde在2005年6月公布的。随着这个算例被成功解决，Gerd Reinelt的TSPLIB中的所有算例均被成功求解。TSPLIB的网址如下：

https://wwwproxy.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/

Concorde使用的是分支切平面算法(branch and cut)，求解花费的时间是相当之久的，在这个网站上面也列出了这个算例具体求解的时间进度如下图。

Improvements in pla85900 Lower Bound

(来源：http://www.math.uwaterloo.ca/tsp/pla85900/heur/heur.htm）

在原网站中还给出每一个的搜索树的情况，在这里，我们把最后的搜索树tree20展示给大家，如果想查看之前的搜索树情况，请自行前往网站查看。

这个团队所使用的机器的硬件为Intel Xeon计算服务器和AMD Athlon计算服务器，尽管在实验进行的过程中这些服务器也进行了其他任务，但是一旦机器空闲下来就进行计算，计算时间花费了136个CPU年，在AMD的250个计算节点上面完成。

使用的软件是Concorde的TSP求解器，这个求解器可以在上面给出的网站进行下载，使用方法也是非常简单，既支持直接求解TSPLIB的标准TSP算例，也支持用户自行设计算例进行求解，可以说是非常方便了。下面是这个软件求解标准算例KroA100.tsp的使用截图。

concorde求解器使用截图

用户在使用这个软件的时候可以自行设置local cut size和最大运行时间等参数。当然，求解问题的规模除了与节点数目有关之外，和节点的分布以及问题结构等也有很大关系，因此求解的规模不可一概而论。

说完了这个求解的算法，我们再来聊聊这个算例吧，这个算例是1986年贝尔实验室为了最小化激光器的总进行时间而设置的，因为激光器需要在待切割点之间互相移动，因此我们假设节点对应互连的位置，两个节点之间的旅行成本就是激光器移动的时间。因此旅行商问题模型的解就是激光切割器的行进顺序。

照片来自贝尔实验室新闻，1986年3月3日

有关这个算例的求解过程不可谓不精彩，这个算例的目标值也历经了15年的更新，事实上，在本文给出的精确解算法求解成功之前，已经有人利用启发式算法求解到了最优解。下图给出自1991年开始到2004年为止的近15年对于这个算例求解的进展。

（来源：http://www.math.uwaterloo.ca/tsp/pla85900/heur/heur.htm)

可以看出，在Concorde给出精确解算法之前，Keld Helsgaun已经利用LKH算法找到了最优解，但是并没有办法验证该解就是最优解。说了这么多，我们具体看看这个算例长什么样子吧，这个算例的最优解是142382641，画出图就是下面这样：

pla85900最优解图示

（来源：http://www.math.uwaterloo.ca/tsp/pla85900/data/data.htm）

-The End-

文案 / 贺兴（大四）

排版 / 贺兴（大四）

代码 / 贺兴（大四）

审核 / 贺兴（大四）

指导老师 / 秦时明岳

如对代码有疑问，可联系小编，可以提供有偿辅导服务。PS:部分资料来自网络。

贺兴（华中科技大学管理学院本科四年级、hexing15@gmail.com)