我想解决像谷歌地图那样的旅行推销员DirectionsRequest问题request.setOptimizeWaypoints(true);。它在路线中订购一些航点，以便将旅行成本降至最低。
我的问题：有人知道它背后的算法是什么吗？任何启发式？到目前为止，谷歌找不到任何信息。
我告诉自己，发现了很多插入启发式、最近邻居等等......或者它是一个精确的解决方案过程？
问问题
4367 次
1 回答
7
Traveling Salesman Problem的 Wikipedia 页面引用了许多用于寻找解决方案的算法。（但除非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
...但尚不清楚这是否是 Google 地图的“生产”代码。
从源代码中的评论：
// 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 问题中讨论。
参考：
于 2013-08-21T04:44:56.603 回答