Travelling Salesman Problem

[majselx]

Hi guys.

I am learning about travelling salesman problem and I was wondering if any of you know a site where I could get source code for C++? I checked Google but found nothing useful.

Thanks

[JonAaron]

I'm not sure if this is what you want but it might help.

http://www.adaptivebox.net/CILib/code/tspcodes_link.html

[majselx]

I checked this site too, but I'm looking for some simple source code. :)

But thanks anyway. :)

[kev82]

The TSP is NP-Hard, exact methods for non-trival instances tend to involve column generation and cutting planes, which means you will need fairly good IP software as well (CPLEX/Gurobi/etc).

If you're looking for a heuristic solution, then again there are many options, are you looking for a construction heuristic, or an optimization metaheuristic such as simulated annealing?

I am of course assuming a you're interested in a deterministic Euclidean symmetric TSP. Which may not be the case?

What I'm trying to say is that there is no simple code to solve the TSP, and in a lot of cases, no code to solve the TSP at all. If you can be much more precise about what you're asking, I may be able to help you.

[majselx]

I have an algorithm for TSP.

procedure SALESMAN(C, N, R, l_path)
 begin
   INSERT_FIRST_NODES(stack);
   for numberOfLinks = 2 to N - 1 do
     begin
       for node = 2 to N do
         CREATE LIST(node, stack, list)
         NEW STACK ELEMENT(stack, list)
     end;
  end;
FINISH_LIST(stack, list);
NEW STACK ELEMENT(stack, list)
FIND_SOLUTION(R, stack, l_path)
RELEASE_STACK(stack)
end

This is an algorithm, now I'm searching source code for the implementation of this algorithm. :)

I hope you understand what I mean.

[kev82]

Well, if that's a full algorithm, then why don't you just translate it to C++ yourself?

To me it looks like a single pascal procedure. I don't think you'll get anywhere with it unless you have the definition of:

INSERT_FIRST_NODES
CREATE_LIST
NEW_STACK_ELEMENT
FINISH_LIST
FIND_SOLUTION
RELEASE_STACK

[majselx]

Yup, that's the problem. I've got problems with these functions as I do not have any pseudocode for them. What I've got is only this algorithm. :/

That is why I am asking if anyone has a simple implementation. :)

[exiledAussie]

The problem is:

FIND_SOLUTION

As Kev82 wrote: The TSP is NP-Hard. In effect this means that you cannot find the solution for problems that are not very small. So you can make a brute force method (look at all possible routes, pick the best), but this will be useless outside trivial (=very small) instances.

Alternatively you can use a heuristic method. But in this case there are many, many options to choose from - some easy, some hard, some good, some lousy.

So there is no definitive source code for the algorithm. You need to decide how you wish to approach a problem that even modern computing cannot solve definitively.

[kev82]

I could probably off the top of my head list 50 completely different methods of solving the TSP, and there will be many more than that.

What you've posted is a small part of a pascal implementation of one of them. I have no idea what the algorithm you've posted is, or how it is supposed to work, it doesn't sound to me like you do either, and I think it is very unlikely that anyone else will.

If you are looking for something simple, then the simplest you are going to get will be a greedy construction algorithm, such as nearest unvisited neighbour, algorithms like this are generally crap though. It depends on your data, but the simplest reasonable construction algorithm I can think of would be an angular sort algorithm.

The alternative is to go down the metaheuristic route, the simplest in this case would be a local neighbourhood search (based on a 2-swap neighbourhood) with random restart. This is actually surprisingly good for the effort it requires.

[majselx]

I'm reading the guide for the implementation and it says that it's needed to implement the problem of salesman by backtracing. The input is adjacency matrix which looks like this:

0 7 37 34 13 48 50 26 45 4 19 30 
36 0 2 21 16 3 17 2 5 9 34 49 
14 14 0 44 10 29 22 2 6 23 50 46 
22 6 5 0 4 11 15 8 43 31 9 19 
17 14 27 28 0 22 20 5 21 38 46 25 
38 33 34 41 49 0 33 27 32 16 8 5 
19 15 45 37 34 28 0 2 25 20 26 17 
40 28 36 18 45 23 27 0 28 2 1 15 
17 48 37 5 4 34 36 12 0 18 33 39 
26 6 49 11 26 10 11 21 41 0 34 9 
26 11 25 6 36 43 25 13 47 41 0 18 
17 18 36 45 14 24 43 21 28 16 8 0 


Solution
1 -> 10 -> 7 -> 8 -> 11 -> 4 -> 3 -> 9 -> 5 -> 2 -> 6 -> 12 -> 1

Price: 78 

There are also 2 structs:

struct path {
int from_node;
int to_node;
int price;
bool set[MAX_N];
path *next;
};

and

struct level {
path* list_of_paths
level* new_node
};

I'm not sure if we understand each other. All I need is a simple program in C++ which solves TSP.

[exiledAussie]

To restate: There is no simple program is C++ or any other language that solves the TSP for arbitrary size.

For small sizes, you can solve the problem by brute force (calculate every route and pick the best). But only for very small sizes. Otherwise, you need to make a choice in heuristics. Google to find implementations.

[majselx]

I need an implementation for up to 12 nodes(cities), so I believe there must be some program, but I couldn't find one on google.

[exiledAussie]

12 nodes is probably somewhere close to being brute force solvable on a good pc, but I would not recommend it!

Try looking at depth first search. With a proper implementation of the backtracking (ie end when it goes over the current maximum) you should be able to perfectly solve almost all 12 node problems in a reasonable timespan.

BTW I have never worked on the TSP problem, so the above claim that is should be quickly solveable is an intuition...

[majselx]

Yep, that's it, depth search. You check all the routes and their prices and the solution is the route with the lowest price...

But I'm in C++ only for a year, so I do not know exactly how to implementate this and that's the reason I'm searching for the source code. :)

[exiledAussie]

http://en.wikipedia.org/wiki/Depth-first_search

Implement the source code yourself.

[kev82]

I have solved a lot of TSPs and I would agree with exiledAussie that with backtracking, even with a naff starting solution, you should be able to solve any size 12 instance in under a second. An exhaustive search will solve up to 10, maybe 11 at a push, within a few minutes.

Do you understand the backtracking algorithm itsself? The code for this is very simple if you understand the algorithm.

But I'm in C++ only for a year, so I do not know exactly how to implementate this and that's the reason I'm searching for the source code. :)

Best way to learn is through trial and error.