TSP问题，即旅行商问题，是公认的NP-Hard问题，解空间随着问题规模指数级上升。
求解此类问题的方法分为两大类：求最优解，求可行的次优解。
这里介绍其中的三种方法：
MIP ：Mixed Integer Program，混合整数规划，最优解SOM：Self-Organizing Map，自组织(神经)网络，次优解RL：Reinforcement Learning, 强化学习，次优解另外，有个标准数据集，是实际的城市坐标数据，规模由小到大，且给出了经过计算的最优解。方便大家学习、研究、比较。
TSPLIB数据集
1、MIP
利用混合整数规划的方法建模，再利用求解器求解，能得到TSP问题的最优解。
牛逼的求解器groubi中就有这个例子，详细代码可以去examples里看。
其大致思路是，
变量：每个节点的所有边（0/1变量）
约束：
一般约束：从每个节点发出的边的数量和为 2
lazy constraint：没有遍历所有城市的最短路线。
同样，google也有个OR-Tools（组合优化工具包），开源的，可以求解包括MIP的一些组合优化模型，里边也有TSP的例子，建模应该类似（我没深入看呢还 ==）
2、SOM
这个是现在GitHub上看到一个印度大学老师上传的代码，他还有配套的博客介绍（写的比较简单）。
然后我对照着相关的论文看，才搞懂，有时间再详细写一下我的理解。这儿先把这些资料放这儿。
GitHub地址
博文地址
论文名：Kohonen Self-Organizing Map for the Traveling Salesperson Problem
3、RL
是一个强化学习的方法求解组合优化的尝试，来自近期的一篇论文 Learning Combinatorial Optimization Algorithms over Graphs。 实际上是应用了强化学习和图嵌入的方式来解决三类问题：Minimum Vertex Cover，Maximum Cut 和 Traveling Salesman problems。
具体的思路我还没研究，不过针对TSP问题的结果和SOM方法的精度类似，或者略逊之（亲测）。
这个文章的作者是包括来自达摩院的宋乐和佐治亚理工Hanjun Dai，（貌似是师徒），鉴于人家名头这么大，所以他们的更复杂而效果没有更好但是听起来牛逼 的算法，只能认为是开创性的探索咯~
