我想通过request.setOptimizeWaypoints(true);解决Google Maps在DirectionsRequest中所做的旅行推销员问题.它在一条路线中命令一些航路点,以便减少旅行费用.

我的问题：有人知道它背后的算法吗？任何启发式？到目前为止,无法通过谷歌找到任何信息.

我告诉自己,发现了很多插入 – 启发式,最近邻居等等……或者它是一个精确的解决方案程序？

解决方法:

Travelling Salesman Problem上的*页面引用了许多用于查找解决方案的算法. (但除非N很小,否则请避免使用“精确”算法！)

根据Google员工的this post,Googles路线计算算法的源代码可在此处获得：

> http://code.google.com/p/or-tools/source/browse/trunk/examples/cpp/tsp.cc
> http://code.google.com/p/or-tools/source/browse/trunk/src/constraint_solver/routing.h

…但这还不完全清楚这是否是谷歌地图的“生产”代码.

来自源代码中的评论：

// Solving the vehicle routing problems is mainly done using approximate methods
// (namely local search,
// cf. http://en.wikipedia.org/wiki/Local_search_(optimization)), potentially
// combined with exact techniques based on dynamic programming and exhaustive
// tree search.

这个一般性问题(Google Maps vs TSP)也在其他各种SO问题中进行了讨论.

参考文献：

> Optimal map routing with Google Maps
> Travelling Salesman with Google Maps API or any other
> What is a practical solution to the Travelling Salesman prblem, using Google Maps?