使用Google Maps API是否有一种方式可以返回一个“优化”的路线，给定一组途径点（换句话说，是旅行商问题的“足够好”的解决方案），或者它总是按指定顺序返回路线？
谷歌地图的最佳地图路线规划
23
- Soldarnal
1
2这个想法在Slashdot上有一个完整的讨论：http://ask.slashdot.org/article.pl?sid=08/01/09/2311215 - brianegge
5个回答
35
在Google Maps API的DirectionsRequest选项中有一个叫做optimizeWaypoints的选项，这个选项可以实现你想要的功能。然而它只能处理最多8个途经点。
或者，你可以使用一个开源（MIT许可证）的库与Google Maps API配合使用，以获得最优解（最多15个位置）或接近最优解（最多100个位置）的路线。
请查看http://code.google.com/p/google-maps-tsp-solver/
你可以在www.optimap.net上看到该库的运作过程。
- Geir Engdahl
1
很遗憾，只能接受不超过50个位置。 - Geremia
7
谷歌为旅行商问题提供了一种成熟的解决方案，那就是OR-Tools（谷歌运营研究工具），您可以在此处找到它：https://developers.google.com/optimization/routing/tsp
基本上，您需要做两件事：
1. 使用Google Maps API获取每两个点之间的距离：https://developers.google.com/maps/documentation/distance-matrix/start 2. 然后将距离数据存入数组中，并传递给OR-Tools，它会为您找到一个非常好的解决方案（对于数百万个节点的某些实例，已经保证找到的解决方案在最优旅游路线的1%范围内）。
您还可以注意到：
除了解决传统的旅行商问题外，OR-Tools还提供了更一般类型的TSP的方法，包括以下内容：
- 非对称成本问题——传统的TSP是对称的：从A点到B点的距离等于从B点到A点的距离。但是，从A点到B点运输物品的成本可能不等于从B点到A点运输物品的成本。OR-Tools还可以处理具有不对称成本的问题。 - 收集奖励的TSP，其中访问节点会产生收益 - 具有时间窗口的TSP
附加链接：
- OR-Tools在Github上的链接：https://github.com/google/or-tools - 入门指南：https://developers.google.com/optimization/introduction/get_started
1. 使用Google Maps API获取每两个点之间的距离：https://developers.google.com/maps/documentation/distance-matrix/start 2. 然后将距离数据存入数组中，并传递给OR-Tools，它会为您找到一个非常好的解决方案（对于数百万个节点的某些实例，已经保证找到的解决方案在最优旅游路线的1%范围内）。
您还可以注意到：
除了解决传统的旅行商问题外，OR-Tools还提供了更一般类型的TSP的方法，包括以下内容：
- 非对称成本问题——传统的TSP是对称的：从A点到B点的距离等于从B点到A点的距离。但是，从A点到B点运输物品的成本可能不等于从B点到A点运输物品的成本。OR-Tools还可以处理具有不对称成本的问题。 - 收集奖励的TSP，其中访问节点会产生收益 - 具有时间窗口的TSP
附加链接：
- OR-Tools在Github上的链接：https://github.com/google/or-tools - 入门指南：https://developers.google.com/optimization/introduction/get_started
- Muhammad Altabba
6
它始终按顺序给出它们。
因此，我认为您需要逐个找到每对点之间的距离（或时间），然后自己解决旅行商问题。也许您可以说服 Google 地图添加该功能。我想，什么样的“足够好”的解决方案取决于您正在做什么以及需要多快。
因此，我认为您需要逐个找到每对点之间的距离（或时间），然后自己解决旅行商问题。也许您可以说服 Google 地图添加该功能。我想，什么样的“足够好”的解决方案取决于您正在做什么以及需要多快。
- Tyler
1
你的答案现在不正确。谷歌现在支持TSP问题。免费版的谷歌地图包括起点、终点和8个中间点（共10个点）。希望您再次编辑以供后来的用户参考 :) - hqt
5
在典型的TSP问题中，假设可以直接在任意两点之间旅行。但对于地面道路来说，这从未发生过。当Google计算两点之间的路径时，它会进行一种启发式生成树优化，并通常得出一个非常接近最优路径的结果。
要计算TSP路线，首先必须要求Google计算图中每个节点之间的两两距离。我认为这需要n*(n-1) / 2个计算。然后可以拿这些距离进行TSP优化。
OpenStreetMaps.org有一个Java WebStart应用程序，可能可以满足您的需求。当然，这些计算是在客户端运行的。该项目是开源的，值得一看。
您是想找到位置之间的最佳直线路径还是最佳驾驶路线？如果您只想排序这些点，如果您可以获得GPS坐标，这将成为一个非常简单的问题。
要计算TSP路线，首先必须要求Google计算图中每个节点之间的两两距离。我认为这需要n*(n-1) / 2个计算。然后可以拿这些距离进行TSP优化。
OpenStreetMaps.org有一个Java WebStart应用程序，可能可以满足您的需求。当然，这些计算是在客户端运行的。该项目是开源的，值得一看。
您是想找到位置之间的最佳直线路径还是最佳驾驶路线？如果您只想排序这些点，如果您可以获得GPS坐标，这将成为一个非常简单的问题。
- brianegge
2
你如何从API中获取“相当接近最优路径”？我只能按照输入顺序返回点。 - Soldarnal
1谷歌不会排序点。谷歌计算的最优路径是两点之间的距离。从纽约到加利福尼亚有多少种方式？近乎无限。谷歌会为您找到一条好的路线，可能接近最优，但可能存在更短的路线。 - brianegge
4
刚发现了http://gebweb.net/optimap/，看起来很不错且易于使用。在线版本使用Google地图。
- mrhvid
1
1哇，这个网站太棒了，很高兴它已经上线这么久了——这将对我的一个朋友非常有用！！！ - DPSSpatial
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接