有没有办法使用 Google Maps API 在给定一组航点的情况下返回“优化”路线（换句话说，旅行商问题的“足够好”的解决方案），或者它总是返回带有按指定顺序点？
Soldarnal
问问题
30442 次
5 回答
31
Google Maps API DirectionsRequest 中有一个名为 optimizeWaypoints 的选项，它应该可以满足您的需求。不过，这最多只能处理 8 个航点。
或者，有一个开源（MIT 许可）库，您可以将其与 Google Maps API 一起使用，以获得最佳（最多 15 个位置）或非常接近最佳（最多 100 个位置）的路线。
于 2012-02-01T14:29:11.450 回答
6
它总是按顺序排列它们。
所以我认为你必须找到每对点之间的距离（或时间），一次一个，然后自己解决旅行商问题。不过，也许您可以说服 Google 地图添加该功能。我想什么构成“足够好”的解决方案取决于你在做什么以及它需要多快。
于 2009-05-02T21:25:49.310 回答
5
在典型的 TSP 问题中，假设可以直接在任意两点之间移动。对于地面道路，情况并非如此。当 Google 计算两点之间的路线时，它会进行启发式生成树优化，并且通常会得出一个相当接近最优路径的路径。
要计算 TSP 路线，首先必须让 Google 计算图中每个节点之间的成对距离。我认为这需要 n*(n-1) / 2 计算。然后可以采用这些距离并对它们执行 TSP 优化。
OpenStreetMaps.org 有一个Java WebStart应用程序，它可以做你想做的事。当然，计算是在客户端运行的。该项目是开源的，可能值得一看。
您是在寻找位置之间的最佳直线路径，还是最佳行驶路线？如果你只是想点点，如果你能得到 GPS 坐标，就变成了一个很容易的问题。
于 2009-08-10T06:32:10.127 回答
5
谷歌为旅行推销员问题提供了现成的解决方案。您可以在此处找到 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 点的成本可能不等于从 A 点运送到 B 点的成本从 B 点到 A 点。OR-Tools 还可以处理成本不对称的问题。
收集奖品的 TSP，通过访问节点获得收益
带时间窗的 TSP
附加链接：
于 2019-01-27T07:37:51.200 回答
4
刚刚发现http://gebweb.net/optimap/ 它看起来很简单。使用谷歌地图的在线版本。
于 2012-01-16T11:26:28.080 回答