解决ruby中的旅行商问题（50多个地点）
我在一家快递公司工作。 我们目前通过“手”解决了50多个地点的路线。
我一直在考虑使用谷歌地图API解决这个问题，但我已经读到有24点的限制。
目前我们在服务器中使用rails，所以我正在考虑使用ruby脚本来获取50多个位置的坐标并输出合理的解决方案。
你会用什么算法来解决这个问题？
Ruby是一种很好的编程语言来解决这类问题吗？
你知道任何现有的ruby脚本吗？
这可能是您正在寻找的：
警告：
这个网站被firefox标记为攻击网站 – 但我似乎并不是。 事实上，我以前使用它没有问题
[检查URL的修订历史记录]
rubyquiz似乎失败了（已经有所下降）但是你仍然可以查看WayBack机器和archive.org以查看该页面： http ：//web.archive.org/web/20100105132957/http://rubyquiz 。 COM / quiz142.html
即使使用另一个答案中提到的DP解决方案，也需要进行O（10 ^ 15）操作。 因此，您将不得不考虑近似解决方案，这些解决方案可能是可接受的，因为您目前手动执行这些解决方案。 请查看http://en.wikipedia.org/wiki/Travelling_salesman_problem#Heuristic_and_approximation_algorithms
这里有几个技巧：
1：相对靠近一个图形的块位置，并将这些位置转换为主图形中的单个节点。 这可以让你在没有太多工作的情况下贪婪。
2：使用近似算法。
2a：我最喜欢的是比特游。 他们很容易被破解。
请参阅更新
这是一个带有bitonic游览的py lib， 这是另一个
让我去寻找一个ruby。 我找不到更多只有效率问题的RGL ……
更新
在您的情况下，最小生成树攻击应该是有效的。 我想不出你的城市不会遇到三角不等式的情况。 这意味着应该有一种相对类似的几乎快速相当不错的近似值。 特别是如果距离是欧几里德，我认为，它必须是。
其中一个优化的解决方案是使用动态编程但仍然非常昂贵的O（2 ** n），这是不太可行的，除非你使用一些集群和分布计算，ruby或单个服务器对你来说不是很有用。
我建议你提出一个贪婪的标准，而不是使用更容易实现的DP或蛮力。
程序结束后，您可以执行一些memoization，并将结果存储在某处以供以后查找，这样可以节省一些周期。
就代码而言，您需要实现具有权重的顶点，边。
ie：顶点类，其边缘具有权重，递归。 而不是将填充数据的图表类。
我致力于使用诸如Ant Colony Optimazation之类的meta-heurestic算法来解决Bays29（29-city）问题的TSP问题，并且它在很短的时间内使我接近最优解。 您可以使用相同的。
我用Java编写它，但我会在这里链接它，因为我目前正在开发一个ruby端口：Java： https ： //github.com/mohammedri/ant_colony_java_TSP Ruby： https ： //github.com/mohammedri/ aco-ruby （不完整）这是它解决的数据集： https ： //github.com/jorik041/osmsharp/blob/master/Core/OsmSharp.Tools/Benchmark/TSPLIB/Problems/TSP/bays29.tsp
请记住，我使用的是每个城市之间的欧几里德距离，即直线距离，我不认为在考虑道路和城市地图等的现实生活中这是理想的，但它可能是一个很好的起点:)
如果您希望算法产生的解决方案的成本在最佳值的3/2之内，那么您需要Christofides算法。 ACO和GA没有保证的费用。