java谷歌地图“优化路径点”如何解决旅行推销员的问题？

Question

我想解决一个旅行推销员的问题，就像谷歌地图在它的DirectionsRequest和request.setOptimizeWaypoints(true);中所做的那样。它在一条路线上订购了一些航路点，这样旅行成本就最小化了

我的问题：有人知道它背后的算法吗？有什么启发吗？到目前为止，谷歌找不到任何信息

我告诉自己，发现了很多插入启发法、最近邻法等等。。。还是一个精确的求解过程

Answer 1

Travelling Salesman Problem上的维基百科页面引用了许多寻找解决方案的算法。（除非N很小，否则要避免使用“精确”算法！）

根据谷歌员工this post的说法，谷歌路线计算算法的源代码可以在这里找到：

• 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.

---

这个一般性问题（谷歌地图与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?