数学软件TSP求解器 Concorde TSP Soler

Travelling Salesman Problem (TSP) 问题是一个经典的优化问题。标准的TSP问题就是输入一系列位置点，寻找最短环路径把所有的点串起来。如下图，左侧图是一堆散落的点，右侧是串起这些点的最短路径。

TSP属于组合优化中的NP-hard问题，TSP问题在最坏的情况下，复杂度会随城市的增多而成超多项式（可能是指数）级别增长。

在对称TSP问题中，两座城市之间来回的距离是相等的，形成一个无向图。这种对称性将解的数量减少了一半。在非对称TSP问题中，可能不是双向的路径都存在，或是来回的距离不同，形成了有向图。

TSP应用

TSP在很多领域有若干应用，如企划、物流、芯片制造。我们可以把“城市”的概念用来表示客户、焊接点或DNA片段，而“距离”的概念表示旅行时间或成本或DNA片段之间的相似性度量。TSP还用在天文学中，观察很多源的天文学家希望减少在源之间转动望远镜的时间。许多应用（如资源或时间窗口有限）中，可能会加入额外的约束。

Concorde

由于TSP的复杂性和应用广度，学界一直以来都在寻求开发更快更优的TSP求解器。

其中，比较著名的且赢得了很多TSP数据集上世界纪录的求解器就是Concorde。

Concorde由 David Applegate, Robert E. Bixby, Vašek Chvátal, and William J. Cook等众大神用ANSI C编写的精确解求解器，免费开放给学术界使用。它除了是专为TSP问题开发的求解器外，也用于求解生物信息中的基因映射(gene mapping)，蛋白质功能预测（protein function prediction)，调度船只等多种问题的利器。

这里主要介绍Concorde在对称TSP上的应用，也可以求解一些非对称问题，如两点双向权重不同等TSP问题。Concorde目前在公开TSP数据集中，获得了其中110个数据的最优解记录，其中最多的TSP位置点达到了85900个。

Concorde is a computer code for the symmetric traveling salesman problem (TSP) and some related network optimization problems. The code is written in the ANSI C programming language and it is available for academic research use; for other uses, contact William Cook for licensing options.
Concorde’s TSP solver has been used to obtain the optimal solutions to the full set of 110 TSPLIB instances, the largest having 85,900 cities.
The Concorde callable library includes over 700 functions permitting users to create specialized codes for TSP-like problems. All Concorde functions are thread-safe for programming in shared-memory parallel environments; the main TSP solver includes code for running over networks of UNIX workstations.
Concorde now supports the QSopt linear programming solver. Executable versions of concorde with qsopt for Linux and Solaris are available
Hans Mittelmann has created a NEOS Server for Concorde, allowing users to solve TSP instances online.
Pavel Striz wrote a nice package for creating LaTeX images from the solution files produced by Concorde.

官方网站：http://www.math.uwaterloo.ca/tsp/concorde/index.html

下载地址

数学软件TSP求解器 Concorde TSP Soler
百度网盘：https://pan.baidu.com/s/1smnPTWL

Executable Programs

Executable versions of Concorde and Linkern are available for Linux, Solaris, and Windows/Cygwin. Concorde is the cutting-plane-based exact TSP solver (using the QSopt LP solver) and Linkern is an implementation of the Chained-Lin-Kernighan heuristic for the TSP. The executable codes are given as gzipped files. The Windows/Cygwin codes will run under Windows 98/ME/NT/2000/XP if at least the minimal version of the Cygwin environment is installed.

concorde-linux  Concorde for Red Hat Linux 8.0
linkern-linux  Linkern for Red Hat Linux 8.0
concorde-solaris32  Concorde for Solaris 32-bit
linkern-solaris32  Linkern for Solaris 32-bit
concorde-solaris64  Concorde for Solaris 64-bit
linkern-solaris64  Linkern for Solaris 64-bit
concorde-cygwin  Concorde for Windows/Cygwin
linkern-cygwin  Linkern for Windows/Cygwin

Graphical User Interface for Windows

The graphical user interface to Concorde’s traveling salesman solver is available for Windows 98/ME/NT/2000/XP. Download and execute concorde installer to install the interface.