如何将旅行推销员问题 (TSP) 与 Haversine 距离列表一起使用？
How can I use the Traveling Salesperson Problem (TSP) with a List of Haversine Distances?
我有一个客户和他们各自的销售人员之间的正弦距离列表，我想应用 TSP 算法来优化每个销售人员在给定日期内的行进距离。在 R 或 Python 中解决此问题的最佳方法是什么？
注意：我不需要通过任何地图将其可视化，我只需要从销售人员位置开始和结束的每个客户之间的最短行进距离。
嗯，有很多策略可以用来解决这个问题，例如 (1) 近似算法，(2) 精确方法，当然还有 (3) heuristic/metaheuristic 方法。请注意，给定实例的最优解只能使用精确方法来保证。
关于每种策略，以下链接可能对您有所帮助：
- 近似算法：度量TSP有一个著名的近似算法，即当图形是度量时，称为Christofides algorithm. But for a general graph, there is no approximation algorithm, unless P = NP (you can check the proof of this theorem here，在第2节）；
- Exact approaches：对于TSP，这种策略通常分为两类（但不限于）：dynamic programming and integer programming；
- Heuristic/Metaheuristic 方法：TSP 有大量的启发式和元启发式算法，我就不详细介绍了（你可以自己查一下here）。
如您所见，我的回答很开放，因为您的问题很开放。所以，如果你想得到一个更精确的答案，你需要准确地指定你的内容 need/want.
我有一个客户和他们各自的销售人员之间的正弦距离列表，我想应用 TSP 算法来优化每个销售人员在给定日期内的行进距离。在 R 或 Python 中解决此问题的最佳方法是什么？
注意：我不需要通过任何地图将其可视化，我只需要从销售人员位置开始和结束的每个客户之间的最短行进距离。
嗯，有很多策略可以用来解决这个问题，例如 (1) 近似算法，(2) 精确方法，当然还有 (3) heuristic/metaheuristic 方法。请注意，给定实例的最优解只能使用精确方法来保证。 关于每种策略，以下链接可能对您有所帮助：
- 近似算法：度量TSP有一个著名的近似算法，即当图形是度量时，称为Christofides algorithm. But for a general graph, there is no approximation algorithm, unless P = NP (you can check the proof of this theorem here，在第2节）；
- Exact approaches：对于TSP，这种策略通常分为两类（但不限于）：dynamic programming and integer programming；
- Heuristic/Metaheuristic 方法：TSP 有大量的启发式和元启发式算法，我就不详细介绍了（你可以自己查一下here）。
如您所见，我的回答很开放，因为您的问题很开放。所以，如果你想得到一个更精确的答案，你需要准确地指定你的内容 need/want.