Solving the problem with the seller in ruby ​​(more than 50 places)

Question

I work for a shipping company. We currently allow 50 manual location routes.

I decided to use the Google Maps API to solve this problem, but I read that there is a limit of 24 points.

We are currently using rails on our server, so I’m thinking about using a ruby ​​script that will get the coordinates of 50+ locations and produce a reasonable solution.

What algorithm would you use to solve this problem?

Is Ruby a good programming language to solve this problem?

Do you know about existing ruby ​​script?

Answer 1

This may be what you are looking for:

Attention:

this site receives the firefox flag as an attack site, but I don't seem to be. I actually used it without any problems

[Check change history for URL]

rubyquiz doesn't seem to work (got a little shorter), however you can still check the WayBack system and archive.org to see this page: http://web.archive.org/web/20100105132957/http://rubyquiz.com /quiz142.html

Answer 2

Even with the DP solution mentioned in another answer, O operations (10 ^ 15) will be required. Therefore, you will have to look for approximate solutions that are likely to be acceptable, given that you are currently doing this manually. Take a look at http://en.wikipedia.org/wiki/Travelling_salesman_problem#Heuristic_and_approximation_algorithms

Answer 3

Here are a few tricks:
1: Broken locations relatively close to one plot, and turn these locations into a single node in your main plot. This allows you to be greedy without extra effort.
2: Use the approximation algorithm.
2a: My favorite is biton tours. They are pretty easy to crack.
See Update

Here is py lib with a bitonic tour and here is another
Let me search for ruby. I am having trouble finding more than RGL that has performance issues ....

Update
In your case, a minimal spanning-tree attack should be effective. I cannot think of a case where your cities will not correspond to the inequality of the triangle. This means that there must be a relatively peculiar, almost quick, pretty decent approximation. In particular, if the distance is Euclidean, which, I think, should again be.

Answer 4

One of the optimized solutions is the use of dynamic programming, but still very expensive O (2 ** n), which is not very possible if you do not use any clustering and distribution of calculations, a ruby ​​or one server will not be very useful for you.

I would recommend that you come up with greedy criteria instead of using DP or brute force, which would be easier to implement.

Once your program is finished, you can take a note and save the results somewhere for later searches, which can also save you a few cycles.

in terms of code, you will need to implement vertices, edges that have weight.

i.e.: a vertex class having edges with weights, recursive. than the class of the graph that will fill the data.

Answer 5

I worked on using meta-heuristic algorithms such as Ant Colony Optimazation to solve TSP problems for the Bays29 (29-city) problem, and this gave me optimal solutions in a very short time. You can use the same.

I wrote this in Java, although I will still bundle it here because I'm currently working on a port for ruby: Java: https://github.com/mohammedri/ant_colony_java_TSP Ruby: https://github.com/mohammedri / aco-ruby (incomplete) This is the dataset that it solves for: https://github.com/jorik041/osmsharp/blob/master/Core/OsmSharp.Tools/Benchmark/TSPLIB/Problems/TSP/bays29.tsp

Keep in mind that I use the Euclidean distance between each city, that is, the direct distance, I do not think this is ideal in real life, given the roads and the city map, etc., but this can be a good starting point :)

Answer 6

If you want the cost of the solution created by the algorithm to be within 3/2 of the optimal, you need the Christofides algorithm. ACO and GA do not have guaranteed costs.