algorithm - 在哪里可以找到一组困难的旅行商问题(具有已知的解决方案/近似值)？

Question

我想尝试寻找解决旅行商问题的启发式/近似方法，为了做到这一点，我正在寻找一些“硬”TSP 实例(连同它们最著名的解决方案)，以便我可以尝试解决它们，看看我能做多好。

理想情况下，它们只是基于文本的邻接矩阵列表或邻接列表(我不想处理解析，只处理算法)。
我所说的“难”是指它们几乎不可能用蛮力求解或近似。
(这样我就可以有理由相信，如果我找到一个接近最知名答案的答案，那么我实际上是在做正确的事情，而不仅仅是走运。)

是否有可用于此目的的列表？我四处搜索了一下，但没有找到任何东西。

Answer 1

Here is another question on SE partially answering your problem (它列出了问题，但其中大部分似乎都没有提供解决方案，但您最好还是检查链接 - 事情可能已经改变)。

如果找不到它们，如何随机生成一组节点以及连接它们的路径，将路径长度保存为“最小”(确保两个节点之间的最长连接永远不会> X)和然后添加一堆其他路径确保这些都是 > X?

这样(除非我遗漏了什么)你有一组连接的节点“尽可能复杂”并且从一开始就知道实际的最短连接路径......

---

附录 - 如果您真的想了解您与现有工具的比较情况，那么您必须在生成的问题上运行这些工具。一个免费且可访问(但我不知道它可能有多“高效”)的是 TSP Library for R .

维基百科有一个 list of other free sw packages for this .

也许您可以创建一个不同的 SE 问题，询问如何获得其他 TSP 工具。