用 ruby​​ 解决旅行商问题（50 多个位置）

Question

我在一家快递公司工作。目前，我们“手动”解决了 50 多个位置路线。

我一直在考虑使用 Google Maps API 来解决这个问题，但我读到有 24 点的限制。

目前我们在服务器中使用 Rails，因此我正在考虑使用 ruby​​ 脚本来获取 50 多个位置的坐标并输出合理的解决方案。

您会使用什么算法来解决这个问题？

Ruby 是解决此类问题的良好编程语言吗？

您知道现有的 ruby​​ 脚本吗？

Answer 1

这可能是你在找什么:

警告:

这个网站获取标记的火狐作为攻击的网站-但我不会出现。事实上我用了它之前没有问题

[检查，修订历史URL]

rubyquiz似乎是下(已经下一点)，但是你仍然可以检查出韦巴克机和archive.org 见网页：http://web.archive.org/web/20100105132957/http://rubyquiz.com/quiz142.html

Answer 2

即使在DP溶液在另一个答案，那将需要O（10 ^ 15）操作提及。所以，你不得不看近似解，这或许是可以接受的因为你现在手工做出来。看 http://en.wikipedia.org/wiki/Travelling_salesman_problem#Heuristic_and_approximation_algorithms

Answer 3

这里有一些技巧：
1：将相对接近的位置集中到一个图中，并将这些位置转变为主图中的单个节点。这让你贪婪而无需做太多工作。
2：使用近似算法。
2a：我最喜欢的是双音之旅。它们很容易被破解。
查看更新

这是一个带有双调之旅的 py lib 和 这是另一个
让我去找一颗红宝石吧。我无法找到更多的东西 RGL, ，这有效率问题......

更新
在你的情况下，最小生成树攻击应该是有效的。我想不出你们的城市不满足三角不等式的情况。这意味着应该有一种相对快速且相当不错的近似。特别是如果距离是欧几里德距离，我再次认为它一定是。

Answer 4

一的优化方案的使用动态规划，但仍然非常昂贵O（2 ** N），这是不很不可行的，除非使用一些聚类和分配计算，红宝石或单个服务器不会成为非常有用的你。

我会建议你拿出一个贪婪的标准，而不是使用DP或蛮力这将是更容易实现。

在你的程序结束，你可以做一些记忆化，并在一些地方保存结果供以后查询，这能以及为您节省一些周期。

在代码方面，你就需要实现的顶点，有重物的边缘。

即：顶点类具有配重块的边缘，递归的。比将填充数据的图表类。

Answer 5

我致力于使用蚁群优化等元启发式算法来解决 Bays29（29 个城市）问题的 TSP 问题，它让我在很短的时间内接近最优解决方案。您也可以使用相同的。

虽然我是用 Java 编写的，但无论如何我都会将其链接到这里，因为我目前正在开发 ruby​​ 的端口：爪哇： https://github.com/mohammedri/ant_colony_java_TSP红宝石： https://github.com/mohammedri/aco-ruby （不完整）这是它解决的数据集： https://github.com/jorik041/osmsharp/blob/master/Core/OsmSharp.Tools/Benchmark/TSPLIB/Problems/TSP/bays29.tsp

请记住，我使用的是每个城市之间的欧几里得距离，即直线距离，考虑到道路和城市地图等，我认为这在现实生活中并不理想。但这可能是一个很好的起点:)

Answer 6

如果要由算法产生的解决方案的成本是内的最佳的3/2，那么您想要的赫里斯托菲算法。 ACO和GA不具有保成本。