谷歌地圖如何「優化旅遊景點」解決旅行商問題？

我想解決一個旅遊推銷員問題，如Google地圖在DirectionsRequest與request.setOptimizeWaypoints(true);。它在一條路線上訂購一些航點，以便旅行成本最小。谷歌地圖如何「優化旅遊景點」解決旅行商問題？

我的問題：有人知道背後有哪個算法嗎？任何啓發式？到目前爲止，Google找不到任何信息。

我告訴自己，發現了很多插入啓發式算法，最近鄰居，等等...或者它是一個確切的解決方案過程？

來源

2013-08-21 Gary Klasen

Travelling Salesman Problem上的維基百科頁面引用了許多用於查找解決方案的算法。（！但是，除非N小，避免了「精確」的算法）

根據this post從谷歌員工，對於谷歌路線計算算法的源代碼可以在這裏找到：

...但這並不完全清楚這是否是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.

這是一般的問題（谷歌地圖VS TSP）也在其他各種做題討論。

參考文獻：

來源

2013-08-21 04:44:56

所以在我看來，使用某種算法，如模擬退火/禁忌搜索它涉及本地搜索G-地圖。謝謝Stephen。 –

谷歌地圖如何「優化旅遊景點」解決旅行商問題？

回答

相關問題