Google Maps的"optimizeWaypoints"如何解决旅行推销员？

Question

我要解决像谷歌地图旅行商问题确实在其DirectionsRequest与request.setOptimizeWaypoints(true);.它在一条路线中命令一些航路点,以便减少旅行费用.

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

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

Answer 1

旅行商问题的维基百科页面引用了许多用于寻找解决方案的算法.(但除非N很小,否则请避免使用"精确"算法!)

根据谷歌员工的这篇文章,谷歌路线计算算法的源代码可在此处获得:

• 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问题中进行了讨论.

参考文献:

• 使用Google地图优化地图路线
• 使用Google Maps API或任何其他人旅行推销员
• 使用谷歌地图,旅行商的问题有什么实际的解决方案？