我应该采用哪种TSP启发式算法？

Question

与TSP启发式算法相关的论文很多，而且每一篇论文都可能关注不同类型的TSP问题。谁能推荐几个性能很好的TSP启发式算法，其性质如下: TSP问题的“城市大小”等于30。

Answer 1

禁忌搜索，模拟退火和延迟接受对我来说都很好，for example。

Answer 2

空间填充曲线可以非常快地解决它。然后你可以使用k-opt或其他东西来改善边缘。还有蚁群优化，例如Gebweb tsp求解器。它还具有蛮力和动态解决方案。

Answer 3

如果旅行推销员是公制的(尊重三角不等式)，那么你可以考虑使用多项式的近似算法，并且总是返回一个解，这最多比最优解差X倍。例如，Christofides algorithm保证路径最多比最优路径长1.5。