我如何将旅行销售员问题（TSP）与Haversine距离列表一起使用？

Question

我有一个列表，列出了客户与其销售人员之间的距离，我希望应用TSP算法来优化每个销售人员在给定日期内的行进距离。用R或Python解决此问题的最佳方法是什么？

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

Answer 1

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

1. 近似算法：有一个著名的度量TSP近似算法，即当图形是度量时，称为Christofides algorithm。但是对于一般图形，没有逼近算法，除非P = NP（您可以在第2节中查看此定理here的证明）；
2. [精确方法：对于TSP，此策略通常将自身分为两类（但不限于）：dynamic programming和integer programming；]]
3. 启发式/元启发式方法：由于TSP有大量启发式方法和元启发式方法（您可以自己检查here，因此我将不对其进行详细说明。

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