I want to modify my current TSP program to be able to handle more vertices. Currently, I use a slightly modified Depth-first search to find the shortest path(s). It currently works, but it can only handle around 20-25 vertices. Any more than that, and the program takes too long to run.

I recently learned about a technique where you do the following:

1) Find any valid path.

2) Switch two nodes in the path.

3) Check to see if path is valid and is less costly than the previous.

4) Repeat steps 2-3 until every switch has been tested.

I tried this out on paper, and it seemed to work well. However, it would seem that in order to find an initial valid path, I would have to run my Depth-first search anyways. Once it found a path it could stop. However, if it never found one (no valid path exists), or if it found one on the next to last run through, it could take too long to run with many vertices. It also seems that since you are testing/switching for every permutation, that this algorithm would not be efficient (maybe i'm wrong?).

I would appreciate any suggestions. I'm just looking for a way (as simple as possible) to solve a TSP with a large amount of vertices (hundreds/thousands).

I've read that the only way to solve a TSP with a large number of vertices is to use an algorithm that finds anearoptimal solution. If this is the case, any recommendations for an algorithm?

Thanks.