我在一家快递公司工作。我们目前通过“手工”解决 50 多个地点路线。
我一直在考虑使用 Google Maps API 来解决这个问题，但我读到有 24 个点的限制。
目前我们在我们的服务器中使用rails，所以我正在考虑使用一个ruby脚本来获取50多个位置的坐标并输出一个合理的解决方案。
你会用什么算法来解决这个问题？
Ruby 是一种很好的编程语言来解决这类问题吗？
你知道任何现有的 ruby 脚本吗？
问问题
5038 次
6 回答
6
这可能是您正在寻找的：
警告：
该站点被 Firefox 标记为攻击站点 - 但我似乎没有。其实我以前用过没问题
[检查 URL 的修订历史记录]
rubyquiz 似乎已经关闭（已经关闭了一段时间）但是您仍然可以查看 WayBack 机器和 archive.org 以查看该页面： http://web.archive.org/web/20100105132957/http://rubyquiz。 com/quiz142.html
于 2010-11-24T00:29:17.037 回答
4
即使使用另一个答案中提到的 DP 解决方案，这也需要 O(10^15) 操作。因此，您将不得不查看近似解决方案，考虑到您目前手动完成它们，这可能是可以接受的。查看http://en.wikipedia.org/wiki/Travelling_salesman_problem#Heuristic_and_approximation_algorithms
于 2010-11-24T00:39:00.830 回答
2
这里有几个技巧：
1：将相对接近的位置集中到一个图中，并将这些位置变成主图中的单个节点。这使您无需太多工作就可以贪婪。
2：使用近似算法。
2a：我最喜欢的是双音之旅。他们很容易破解。
见更新
这是一个带有双音之旅的 py lib，这是另一个
让我去找一个 ruby 的。我很难找到不仅仅是RGL，它有效率问题....
更新
在您的情况下，最小生成树攻击应该是有效的。我想不出你的城市不会满足三角不等式的情况。这意味着应该有一种相对较快的近似值。特别是如果距离是欧几里得，我认为，再次，它必须是。
于 2010-11-24T00:36:04.333 回答
1
优化的解决方案之一是使用动态编程，但仍然非常昂贵 O(2**n)，这不是很可行，除非你使用一些集群和分布式计算，否则 ruby 或单服务器对你来说不是很有用。
我建议您提出一个贪婪的标准，而不是使用更容易实施的 DP 或蛮力。
一旦你的程序结束，你可以做一些记忆，并将结果存储在某个地方以供以后查找，这也可以为你节省一些周期。
就代码而言，您需要实现具有权重的顶点、边。
即：具有权重边的顶点类，递归。而不是将填充数据的图形类。
于 2010-11-23T22:20:41.167 回答
1
我致力于使用诸如 Ant Colony Optimazation 之类的元启发式算法来解决 Bays29（29 城市）问题的 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
请记住，我使用的是每个城市之间的欧几里得距离，即直线距离，考虑到道路和城市地图等，我认为这在现实生活中并不理想，但这可能是一个很好的起点:)
于 2017-02-02T05:23:56.167 回答
0
如果您希望算法产生的解决方案的成本在最优值的 3/2 以内，那么您需要 Christofides 算法。ACO 和 GA 没有保证费用。
于 2011-03-12T06:56:43.543 回答