使用Google地图优化地图路线

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

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

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

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

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

它总是按顺序给它们.

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

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

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

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

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