运筹学教学|三种TSP问题算法的对比试验及分配问题和TSP问题求解速度对比

· 内容摘要 ·

一、三种求解TSP问题的算法的对比试验

二、分配问题和TSP问题的求解速度对比试验

· 三种求解TSP问题的算法的对比试验·

关于这三种算法的详细步骤，小编在这里就不再赘述啦，让我们直接进入正题~想要了解这些算法的同学可参考以下推文：

分支定界算法求解TSP问题：https://mp.weixin.qq.com/s/ogkN5mP8snQBQeIBRkiupw

动态规划求解TSP问题：https://mp.weixin.qq.com/s/17cAi89KLr81t1yyR3G84Q

Cplex求解TSP问题：https://mp.weixin.qq.com/s/6s_REEoPyTUT3KAqzwznjA

小编使用同一算例，并分别取前3、5、7、9、11、13、15、17、19、21、23、25个点进行试验。

值得一提的是，小编利用Cplex求解TSP问题时使用的是以下模型，与上述推文有所不同，需要以下模型的代码和算例的同学可以在文末进行下载噢~

对各个数据规模，三种算法的求解消耗时间对比如下：

可以发现，当数据规模逐渐增大时，求解所消耗时间越长（用Cplex求解TSP问题时，数据规模为23个点时反而消耗时间比21个点要少，这属于特殊情况。一般来说，数据规模越大，求解所需时间越长）。

当数据规模较小时，三种算法的求解速度几乎没有差别，当数据规模增大时，算法之间的求解速度差别就显而易见了。需要说明的是，求解所花费的时间会因使用的计算机的性能而异，也与问题本身有关。

当数据规模达到20个点左右时，即使是计算机也需要一定的求解时间。当数据点越来越多，所需时间的增加幅度也越来越大。可见虽然tsp的模型看上去不复杂 但是求解起来很复杂，人工求解所耗费的时间精力更是成倍增加。这说明一个优化问题求解是不是复杂 不能通过模型复不复杂来简单判断，简单的模型求解起来也可能十分复杂。

· 分配问题和TSP问题的求解速度对比 ·

相信很多同学对分配问题也不陌生，小编就不再赘述啦，想要详细了解的同学可以参考以下推文：

分配问题：https://mp.weixin.qq.com/s/O5Im65SAOmpxuExx9TizMQ

TSP求解的方法在上面已经介绍过了，我们可以借助Cplex来帮助我们完成这个过程。我们再用相同的算例来求解分配问题以进行对比，小编是在Eclipse上用Java语言调用的接口，需要代码或具体操作说明的同学同样可以在上述推文中找到。

我们同样不断增加数据规模，并对两种问题使用同样的算例进行求解。

求解所消耗时间如下：

通过以上实验我们可以发现，分配问题的求解速度一般要快于TSP问题，且这个差别在数据规模不断增大时变得越来越明显（当然，具体快多少还是要看问题本身和计算机性能）。

· 原因分析 ·

为什么分配问题的求解速度要更快一些呢？

分配问题的要求一般是给n个人分配n项任务，一个人只能分配一项任务，一项任务只能分配给一个人，将一项任务分配给一个人是需要支付报酬，如何分配任务，保证支付的报酬总数最小。

旅行商问题的要求一般是一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

乍一看，这两个问题之间毫无关联。但从本质上来看，分配问题其实是TSP问题的松弛问题。

分配问题模型：

TSP问题模型：

可见当分配问题的分配方式成环且不包括子环时，它的最优解即是TSP问题的最优解。简单说来，TSP问题要比分配问题约束更多。

参考文献：

1.Operations Research Applications and Algorithms, Wayne L. Winston

2.运筹学 《运筹学》教材编写组，清华大学出版社

- END -

文案&代码：胡心瑶（华中科技大学管理学院本科二年级）

指导老师：秦虎老师（华中科技大学管理学院）

排版：程欣悦（荆楚理工学院本科三年级）

如对文中内容有疑问，欢迎交流。PS：部分资料来自网络。

如有需求，可以联系：

秦虎老师（华中科技大学管理学院：professor.qin@qq.com）

胡心瑶（华中科技大学管理学院本科二年级：1603945923@qq.com）

程欣悦 （荆楚理工学院本科三年级：1293900389@qq.com）