Travelling Salesman - approximation online software?

Question

would any of you know of a solution to generate even a mediocre solution to the travelling salesman problem. I have 3 people meant to visit 31 destinations... I'm not sure how to approach that?

Thanks to all -

Maxim

Answer 1

I suppose you could try a greedy approach by picking an arbitrary point to start (if a starting point is not specified) and then on each step you travel to the closest point to your current point. Assuming that distance between points can be calculated in constant time you can then find a path in O(n^2) time.

To clarify, the following pseudo code should help (I haven't written this kind of thing in a while, so I hope this is clear enough)

Name: GreedyPath(C, p)
Input: C - a non-empty collection of points to visit
       p - a starting point in C
Output: S - a sequence of points covering C
Algorithm:
  Remove p from C
  If C is empty
    Return the sequence containing only p
  Else
    Let p1 be the closest point to p in C
    Let S = GreedyPath(C, p1)
    Append p to the start of S
    Return S

Obviously the time consuming part is finding the closest point to p every time, but for n points this should only require n(n-1)/2 distance calculations (unless I'm mistaken).

Answer 2

There are several options including: Nearest Neighbor, Christofides, and Lin–Kernighan.

If these fail, you can always use code from the experts (free for academic researchers).