什么是一个实用的解决方案，旅行推销员的问题，使用谷歌地图

Question

使用谷歌地图/地理定位/路线查找，旅行推销员问题的实际解决方案是什么?

我不需要最好的解决方案，5%以内就可以了。

例如，我在英国有20个地方要参观，以任何顺序。这可能需要扩展到数百个位置。

如果我可以查找距离(但不想查找数百个距离)，我可以使用哪种算法?

Answer 1

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

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

Answer 2

Google在他们的方向API中确实有一个参数，可以将路线优化为旅行推销员问题:

• API文档:在Routes
中使用路点
• 介绍和演示博客文章

从文档(关键部分是&waypoints=optimize:true|...):

下面的例子计算从阿德莱德出发的公路旅行路线，南澳各主要葡萄酒产区使用路线优化。

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

对计算出的路由进行检查，会发现该路由为使用以下航路点顺序计算:

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

对于一次性使用，使用@Kunukn

Answer 3

您可以使用long - late来大致估计位置之间的距离，然后查找彼此附近的位置。

一个更简单的选择是将你的地图分成3 x 3个部分。只在相邻路段查找路线。

这些技术不是100%准确的。

即使你查找了所有的路径，你也应该不超过190次查找。

Answer 4

如果您正在寻找欧几里得TSP的多项式近似，则建议使用几种算法。