使用Google地图优化地图路线

Question

有没有办法使用Google Maps API在给定一组航路点(换句话说,对旅行商问题的"足够好的"解决方案)的情况下取回"优化"路线,或者它是否始终返回路线按指定顺序分？

Answer 1

Google Maps API DirectionsRequest中有一个名为optimizeWaypoints的选项,可以执行您想要的操作.但是,这只能处理多达8个航路点.

或者,有一个开源(MIT许可证)库,您可以使用Google Maps API来获得最佳(最多15个位置)或非常接近最佳(最多100个位置)路线.

请参阅http://code.google.com/p/google-maps-tsp-solver/

您可以在www.optimap.net上查看该库

Answer 2

它总是按顺序给它们.

所以我认为你必须找到每对点之间的距离(或时间),一次一个,然后自己解决旅行商问题.也许您可以说服谷歌地图添加该功能.我想什么构成了"足够好"的解决方案取决于你正在做什么以及它需要多快.

Answer 3

在一个典型的TSP问题中，假设是可以直接在任意两点之间传播。对于平地公路，情况并非如此。Google计算两点之间的路线时，会进行启发式生成树优化，通常会得出相当接近的最佳路径。

要计算TSP路线，首先必须要求Google计算图中每个节点之间的成对距离。我认为这需要n *（n-1）/ 2个计算。然后可以采用这些距离并对它们执行TSP优化。

OpenStreetMaps.org具有Java WebStart应用程序，可以执行您想要的操作。当然，计算是在客户端进行的。该项目是开源的，可能值得一看。

您是否在寻找位置之间的最佳直线路径或最佳行驶路线？如果您只想订购点，则可以获取GPS坐标，这是一个非常简单的问题。

Answer 4

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

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

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

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

您还可以注意到：

除了寻找经典旅行商问题的解决方案外，OR-Tools 还为更一般类型的 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