使用谷歌地图的最佳地图路由

有没有一种方法可以使用Google Maps API在给定一组航点的情况下获得“优化”路线（换句话说，就是旅行商问题的“足够好的”解决方案），或者它是否总是按照指定顺序返回路线？使用谷歌地图的最佳地图路由

2008-12-03 Soldarnal

看到活动的图书馆有这个想法在Slashdot整个讨论：http://ask.slashdot.org/article.pl?sid=08/ 01/09/2311215 – brianegge 2009-08-20 02:20:05

它总是给他们按顺序。

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

2009-05-02 21:25:49 MatrixFrog

你的答案现在不正确。 Google现在支持TSP问题。谷歌地图的免费版本包括开始，结束和8个中间点。（共10分）希望您再次编辑以供以后用户参考:) – hqt 2015-08-15 16:15:11

在典型的TSP问题中，假设是可以在任意两点之间直接传播的。对于地面道路而言，情况绝非如此。当Google计算两点之间的路线时，它会进行启发式生成树优化，并且通常会提供相当接近最佳路径。

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

OpenStreetMaps.org有一个Java WebStart应用程序，它可以做你想做的。当然，计算正在运行客户端。该项目是开源的，可能值得一看。

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

2009-08-10 06:32:10 brianegge

如何从API获取“相当接近最佳路径”？我只能按照我输入的顺序获得积分。 – Soldarnal 2009-08-10 13:27:21

Google不会订购积分。 Google计算的最佳路径是两点之间的距离。从纽约到加利福尼亚有多少种方式？接近无限。谷歌会找到一条很好的路线，可能接近最佳路线，但路线可能较短。 – brianegge 2009-08-10 22:55:27

刚刚找到http://gebweb.net/optimap/它看起来不错，很容易。使用谷歌地图的在线版本。

2012-01-16 11:26:28 mrhvid

Google Maps API DirectionsRequest中有一个名为optimizeWaypoints的选项，它应该按照您的要求进行操作。尽管如此，这最多只能处理8个航点。

另外，还有一个开源（MIT许可证）库，您可以使用Google Maps API来获得最佳（最多15个位置）或非常接近最佳（最多100个位置）的路线。

2012-02-01 14:29:11

回答