使用 Google 地图解决旅行商问题的实用方法是什么？
使用 Google 地图/地理定位/路线查找来解决旅行商问题的实用解决方案是什么？
我不需要最好的解决方案，5%以内就可以了。
例如，我在英国有 20 个地点可供参观，顺序不限。这可能需要扩展到数百个位置。
鉴于我可以查找距离（但不想查找数百个距离），我可以使用哪种算法？
What is a practical solution to the Travelling Salesman problem, using Google Maps / geolocation / route finding?
I don't need the best solution, within 5% would be fine.
For example, I have 20 locations in the UK to visit, in any order. This may need to scale to hundreds of locations.
What sort of algorithm can I use, given that I can lookup distances (but don't want to lookup hundreds of distances)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
有一个用 JS http://code.google.com/ 实现的 TSP 项目p/google-maps-tsp-solver/
您可以在此处观看现场演示http://gebweb.net/优化图/
There is this TSP project implemented in JS http://code.google.com/p/google-maps-tsp-solver/
You can see live demo here http://gebweb.net/optimap/
Google 的路线 API 上确实有一个参数，可以优化旅行推销员问题的路线：
来自文档（关键部分是
&waypoints=optimize:true|...）：对于一次性使用 @Kunukn 推荐的 OptiMap 可能更容易
Google does have a parameter on their directions API which will optimize the route as a travelling salesman problem:
From the documentation (the key part is
&waypoints=optimize:true|...):For a one-off it's probably easier to use OptiMap as recommended by @Kunukn
您可以使用长纬度来粗略估计位置之间的距离，然后进行一些查找以查找彼此附近的位置。
一个更简单的替代方法是将地图分成 3 x 3 部分。仅查找相邻路段位置的路线。
但这些技术并不是 100% 准确。
即使您查找所有路径，最终的查找次数也不会超过 190 次。
you can use long lat to estimated roughly how far apart the locations are, then make a few lookups for those that are nearby each other.
a simpler alternative is to separate your map into 3 x 3 sections. Only look up routes for locations in adjacent sections.
these techniques aren't 100% accurate though.
And even if you look up all the paths, you should end up with no more than 190 lookups.
如果您正在寻找欧几里得 TSP 的多项式近似，已经建议了几种算法。请查看此处。
I you are looking for a polynomial approximation for the Euclidean TSP, several algorithms have been suggested. Have a look here.