python - 如何将旅行推销员问题 (TSP) 与 Haversine 距离列表一起使用？

Question

我有一个客户和他们各自的销售人员之间的差距列表，我想应用 TSP 算法来优化每个销售人员在给定一天的行程距离。在 R 或 Python 中解决这个问题的最佳方法是什么？

注意：我不需要通过任何地图将其可视化，我只需要从销售人员位置开始和结束每个客户之间的最短距离。

标签： pythonrgeospatialtraveling-salesmanhaversine

Answer 1

嗯，有很多策略可以用来解决这个问题，例如 (1) 近似算法，(2) 精确方法，当然还有 (3) 启发式/元启发式方法。请注意，只有使用精确方法才能保证给定实例的最优解。关于每种策略，下面是一些可能对您有所帮助的链接：

1. 逼近算法：度量TSP有一个著名的逼近算法，即当图是度量时，称为Christofides算法。但是对于一般图，没有近似算法，除非 P = NP（您可以在此处查看该定理的证明，在第 2 节）；
2. 精确方法：对于 TSP，这种策略通常分为两类（但不限于）：动态规划和整数规划；
3. 启发式/元启发式方法：我不会详细介绍它，因为 TSP 有大量可用的启发式和元启发式方法（您可以在此处自行检查）。

如您所见，我的回答非常开放，因为您的问题非常开放。因此，如果您想获得更准确的答案，您需要准确指定您需要/想要的内容。