6

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

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

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

鉴于我可以查找距离（但不想查找数百个距离），我可以使用哪种算法？

4

4 回答 4

7

在 JS http://code.google.com/p/google-maps-tsp-solver/中实现了这个 TSP 项目

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

于 2011-10-12T11:36:41.170 回答
4

Google 在他们的路线 API 上确实有一个参数，它将优化路线作为旅行推销员问题：

从文档（关键部分是&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推荐的 OptiMap可能更容易

于 2013-01-24T00:27:45.517 回答
2

您可以使用 long lat 粗略估计位置之间的距离，然后查找彼此附近的位置。

一个更简单的替代方法是将您的地图分成 3 x 3 部分。仅查找相邻部分中位置的路线。

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

即使您查找所有路径，最终也应该不会超过 190 次查找。

于 2011-10-12T07:46:34.933 回答
1

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

于 2011-10-12T07:55:32.683 回答