Solving the Travelling Salesman Problem in ruby (50+ locations)

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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 :)

Answer 6

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.