使用 Google 地图实现最佳地图路线

Question

有没有办法使用 Google Maps API 来获取给定一组航路点的“优化”路线（换句话说，旅行推销员问题的“足够好”解决方案），或者它是否总是返回带有按指定顺序点？

Answer 1

它总是使他们在顺序。

所以，我认为你必须找到每对点，一次一个之间的距离（或时间），然后解决旅行商问题自己。或许你可以说服谷歌地图，虽然添加该功能。我想什么是“足够好”的解决方案取决于你在做什么，以及如何快速它需要。

Answer 2

有是在谷歌地图API的DirectionsRequest一个选项叫做optimizeWaypoints，它应该做你想做的。这只能处理高达8路点，虽然。

另外，还有一个开放源码（MIT许可证）库，你可以使用谷歌地图API的使用，以获得最佳的（最多15个位置）或非常接近最优的（最多100个位置）的路线。

请参阅 http://code.google.com/p/google-地图-TSP-求解器/

可以看到活动的库在 www.optimap.net

Answer 3

在一个典型的TSP问题，假设是一个可以直接任意两点之间行进。对于地面道路，这是从来没有的情况。当谷歌计算两个点之间的路线，但它确实启发式生成树优化，通常来了一个相当接近最优路径。

要计算一个TSP路线，一个首先必须询问谷歌来计算图中的每个节点之间的逐对距离。我想这需要n *（N-1）/ 2 Calcs（计算）。然后，可以把这些距离，对他们进行TSP优化。

OpenStreetMaps.org有的Java Webstart的应用程序，它可以做你想做的。当然，计算正在运行的客户端。该项目是开源的，并且可以是值得考虑。

您试图找到位置之间的最佳行驶路线的最佳直线路径，还是？如果你只是想订购的点，如果你能得到的GPS坐标，它成为一个非常简单的问题。

Answer 4

刚刚找到 http://gebweb.net/optimap/ 它看起来既美观又方便。使用谷歌地图在线版本。

Answer 5

谷歌已经为旅行推销员问题提供了现成的解决方案。您可以在这里找到 OR-Tools（Google 的运筹学工具）： https://developers.google.com/optimization/routing/tsp

你需要做的基本上是两件事：

• 使用 Google Maps API 获取每两点之间的距离： https://developers.google.com/maps/documentation/distance-matrix/start

• 然后您将数组中的距离提供给 OR-工具 它会为您找到一个非常好的解决方案（对于某些具有数百万个节点的实例，已发现解决方案保证在最佳游览的 1% 以内）。

您还可以注意到：

除了找到有关经典旅行人员问题的解决方案外，Or-Tool还提供了更多类型的TSP的方法，包括以下内容：

• 不对称成本问题——传统的 TSP 是对称的：从点A到B点的距离等于从点B到点A的距离。但是，从A点到B点运输项目的成本可能不等于将其从B点运送到点A的成本。OR-Tools 还可以处理具有不对称成本的问题。

• 收集奖品的 TSP，通过访问节点获得收益

• 具有时间窗口的 TSP

附加链接：

• Github 上的 OR 工具： https://github.com/google/or-tools
• 开始使用： https://developers.google.com/optimization/introduction/get_started