解决 ruby 中的旅行商问题（50+ 位置）
我在一家快递公司工作。目前，我们“手动”解决了 50 多个位置路线。
我一直在考虑使用 Google Maps API 来解决这个问题，但我读到有 24 点的限制。
目前我们在服务器中使用 Rails，因此我正在考虑使用 ruby 脚本来获取 50 多个位置的坐标并输出合理的解决方案。
您会使用什么算法来解决这个问题？
Ruby 是解决此类问题的良好编程语言吗？
您知道现有的 ruby 脚本吗？
I am working in a delivery company. We currently solve 50+ locations routes by "hand".
I have been thinking about using Google Maps API to solve this problem, but I have read that there is a 24 points limit.
Currently we are using rails in our server so I am thinking about using a ruby script that would get the coordinates of the 50+ locations and output a reasonable solution.
What algorithm would you use to approach this problem?
Is Ruby a good programming language to solve this type of problem?
Do you know of any existing ruby script?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
这可能就是您正在寻找的内容：
警告：
此站点被 Firefox 标记为攻击站点 - 但我似乎没有。事实上，我之前使用过它，没有出现任何问题
[检查 URL 的修订历史记录]
rubyquiz 似乎已关闭（已经关闭了一段时间），但是您仍然可以查看 WayBack machine 和 archive.org 来查看该页面：
http://web.archive.org/web/20100105132957 /http://rubyquiz.com/quiz142.html
This might be what you are looking for:
Warning:
this site gets flagged by firefox as attack site - but I doesn't appear to be. In fact I used it before without a problem
[Check revision history for URL]
rubyquiz seems to be down ( has been down for a bit) however you can still check out WayBack machine and archive.org to see that page:
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
Even with the DP solution mentioned in another answer, that's going to require O(10^15) operations. So you're going to have to look at approximate solutions, which are probably acceptable given that you currently do them by hand. Look at http://en.wikipedia.org/wiki/Travelling_salesman_problem#Heuristic_and_approximation_algorithms
这里有一些技巧：
1：将相对较近的位置集中到一个图中，并将这些位置变成主图中的单个节点。这让你贪婪而无需太多工作。
2：使用近似算法。
2a：我最喜欢的是双音之旅。它们很容易被破解。请参阅更新
这是一个带有双调之旅的 py 库 和这是另一个
让我去找一颗红宝石吧。我找不到的不仅仅是 RGL，它存在效率问题......
更新
在您的情况下，最小生成树攻击应该是有效的。我想不出你们的城市不满足三角不等式的情况。这意味着应该有一种相对快速且相当不错的近似。特别是如果距离是欧几里德距离，我再次认为，它一定是。
Here are a couple of tricks:
1: Lump locations that are relatively close into one graph, and turn those locations into a single node in your main graph. This lets you be greedy without too much work.
2: Use an approximation algorithm.
2a: My favorite is bitonic tours. They're pretty easy to hack up.See Update
Here's a py lib with a bitonic tour and here's another
Let me go look for a ruby one. I'm having trouble finding more than just the RGL, which has efficiency issues....
Update
In your case, the minimum spanning tree attack should be effective. I can't think of a case where your cities wouldn't meet the triangle inequality. This means that there should be a relatively sort of kind of almost fast rather decent approximation. Particularly if the distance is euclidean, which I think, again, it must be.
一种优化的解决方案是使用动态编程，但仍然非常昂贵的 O(2**n)，这不太可行，除非您使用一些集群和分布式计算，否则 ruby 或单服务器对您来说不是很有用。
我建议你提出一个贪婪的标准，而不是使用 DP 或蛮力，这样更容易实现。
程序结束后，您可以进行一些记忆，并将结果存储在某处以供以后查找，这也可以节省一些周期。
就代码而言，您需要实现具有权重的顶点、边。
即：具有带权重的边的顶点类，递归。而不是将填充数据的图形类。
One of the optimized solution is using Dynamic Programming but still very expensive O(2**n), which is not very feasible, unless you use some clustering and distributing computing, ruby or single server won't be very useful for you.
I would recommend you to come up with a greedy criteria instead of using DP or brute force which would be easier to implement.
Once your program ends you can do some memoization, and store the results somewhere for later lookups, which can as well save you some cycles.
in terms of the code, you ll need to implement vertices, edges that have weights.
ie: vertex class which have edges with weights, recursive. than a graph class that will populate the data.
我致力于使用蚁群优化等元启发式算法来解决 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
请记住，我正在使用欧几里得距离每个城市之间的直线距离，考虑到道路和城市地图等，我认为这在现实生活中并不理想。但这可能是一个很好的起点:)
I worked on using meta-heurestic algorithms such as Ant Colony Optimazation to solve TSP problems for the Bays29 (29-city) problem, and it gave me close to optimal solutions in very short time. You can potentially use the same.
I wrote it in Java though, I will link it here anyways, because I am currently working on a port to ruby:
Java: https://github.com/mohammedri/ant_colony_java_TSP
Ruby: https://github.com/mohammedri/aco-ruby (incomplete)
This is the dataset it solves for: https://github.com/jorik041/osmsharp/blob/master/Core/OsmSharp.Tools/Benchmark/TSPLIB/Problems/TSP/bays29.tsp
Keep in mind I am using the Euclidean distance between each city i.e. the straight line distance, I don't think that is ideal in a real life situation considering roads and a city map etc. but it may be a good starting point :)
如果您希望算法生成的解决方案的成本在最优值的 3/2 以内，那么您需要 Christofides 算法。 ACO 和 GA 没有保证成本。
If you want the cost of the solution produced by the algorithm is within 3/2 of the optimum then you want the Christofides algorithm. ACO and GA don't have a guaranteed cost.