具有已知全局最优值的旅行推销员示例

Question

我用 Python 做了一个模因算法 旅行商问题。然而，我遇到的所有测试数据（城市之间的距离列表）都缺乏最佳解决方案的信息，因此我无法知道我的算法与全局最优有多接近。

有谁知道我在哪里可以找到一些具有已知最佳解决方案的 tsp 测试数据（最好是矩阵形式，但一切都很好）？

Answer 1

你谷歌吗？

http://www.tsp.gatech.edu/data/index.html

该页面提供了几个测试箱，其中16页具有最佳解决方案。

Answer 2

也许您可以生成自己的测试数据？

这绝对不是全面的测试，但可能会有所帮助。笔记：下面是关于哈密尔顿路径，如果你正在寻找循环，类似的东西会起作用。

您可以执行以下操作：

假设给你一个有 n 个节点的无向​​图 G。

现在，您创建一个加权图 G'，通过将 G 中的边的权重设置为 1，并添加不在 G 中的边，并给它们随机权重 > 1，即 G' 是一个完整的图，权重分配给所有它的边缘。

现在，如果您在 G' 上运行有效的 TSP 算法，并且它生成大小为 n-1 的路径，则 G 具有哈密顿路径。否则 G 不具有哈密顿路径。

所以现在你可以使用你的图表 知道 有/没有哈密尔顿路径（例如： 超立方体 具有哈密顿路径）并为您的 TSP 算法生成测试数据。

此页面有一些充分条件，可能在生成具有哈密顿路径的图时有用： http://www-math.cudenver.edu/~wcherowi/courses/m4408/gtln12.html

我想您在有/没有哈密顿路径的图表上查找数据不会很困难。

希望能帮助到你。祝你好运！

Answer 3

TSPLIB是来自各种来源和各种类型的TSP（以及相关问题）的示例实例库。

http://comopt.ifi.uni-heidelberg.de/software/tsplib95/