使用Google地图，解决旅行商问题的实际方案是什么？

Question

如何使用Google Maps / 地理定位 / 路线查找解决旅行推销员问题？

我不需要最佳解决方案，误差在5%以内即可。

例如，我有20个要访问的英国地点，顺序任意。这可能需要扩展到数百个位置。

在能够查找距离（但不想查找数百个距离）的情况下，可以使用什么样的算法？

- fadedbee

---

谷歌地图与此有什么关系？ - Lior Kogan

@Lior - 他们可能有我不知道的API。 - fadedbee

@Bart - 在我编辑时你刚好评论了 - 我最初的尝试是它是O(N^2)，但O(N^2) != N^2。 - fadedbee

@chrisdew，是的，我刚看到你的编辑。 :) - Bart Kiers

@chrisdew，你已经尝试搜索关键词“tsp快速近似”了吗？我搜索到了一些很好的文章。 - Bart Kiers

@Bart，不，我没有。让我帮你谷歌一下。 - fadedbee

Answer 1

这是一个使用JS实现的TSP项目 http://code.google.com/p/google-maps-tsp-solver/

你可以在这里看到实时演示 http://gebweb.net/optimap/

- Kunukn

Answer 2

谷歌确实在其路线规划API中有一个参数，可以将路线优化为旅行推销员问题：

• API文档：在路线中使用途径点
• 介绍和演示博客文章

根据文档（关键部分为&waypoints=optimize:true|...）：

The following example calculates a road trip route from Adelaide, South Australia to each of South Australia's main wine regions using route optimization.

http://maps.googleapis.com/maps/api/directions/json?origin=Adelaide,SA
  &destination=Adelaide,SA
  &waypoints=optimize:true|Barossa+Valley,SA|Clare,SA|Connawarra,SA|McLaren+Vale,SA
  &sensor=false

Inspection of the calculated route will indicate that the route is calculated using the following waypoint order:

"waypoint_order": [ 1, 0, 2, 3 ]

如果只需要一次性的使用，建议使用@Kunukn推荐的OptiMap。

- rcoup

Answer 3

你可以使用经纬度大致估算两个位置之间的距离，然后查找附近的一些地点。一个更简单的替代方案是将你的地图分为3 x 3的区域，只查找相邻区域内的路径。尽管这些技术并不是100%准确的。即使您查找了所有路径，应该也不会超过190个查找。

- Fun Mun Pieng

---

我应该补充一下，这可能需要随着时间的推移扩展到几百个位置。 - fadedbee

在这种情况下，根据您想要的结果精度，您可以将地图分成更多的部分...或者基于经纬度估算距离。 - Fun Mun Pieng

Answer 4

如果你正在寻找欧几里得TSP的多项式逼近，有几种算法被提出。可以在这里看一下。

- Lior Kogan

---

谢谢，这看起来很有用。我的问题可以被认为是欧几里得的吗？正方形中的四个点：对角线之间的旅行时间可能比沿两侧行驶的旅行时间更长。（例如，在这两条边沿着高速公路。） - fadedbee

既然您只是在寻找一个近似值，我认为这些考虑通常可以忽略不计。如果不行的话，可以考虑非对称TSP。 - Lior Kogan

谢谢，我将首先选择http://en.wikipedia.org/wiki/Travelling_salesman_problem#Ant_colony_optimization，如果效果不够好，我会考虑更加学术（令人生畏）的方法。 - fadedbee