Code covered by the BSD License

### Highlights from another TSP solver

4.5
4.5 | 2 ratings Rate this file 11 Downloads (last 30 days) File Size: 2.36 KB File ID: #24857 Version: 1.1

# another TSP solver

### Yonathan Nativ (view profile)

25 Jul 2009 (Updated )

a simple TSP local minimum solution. code is very short and simple.

File Information
Description

while I don't know much about TSP problems, I saw in Wikipedia (http://en.wikipedia.org/wiki/Travelling_salesman_problem) a method to find a local minimum solution based on flipping loops of cities in the overall path. The suggested solution sounded very simple to implement so I played with it a little.

Input:
Nx2 cities array sorted in the initial traveling path (a city is an x&y coordinate).

Output:
- cities arranged in a more effective route
- index vector of the visiting order
- total rout length.

a different starting order will yield a different result (will lead to a different local minimum solution) .

The program supports a display option which shows how the route rearrange at each iteration.

I sew there are few TSP solvers in the file exchange, I doubt if my code will find better solutions, it is just that this code is very short & simple (IMHO).

Algorithm method:
Each iteration the program searches for a different loop sizes which are better flipped around in the over all arrangement.
i.e.
cities: 0 1 5 4 3 2 6 7 8 10 9 11 13 12 14
when searching loops at size 2, [10 9] & [13 12] would be found as beneficial for flipping receiving:
0 1 5 4 3 2 6 7 8 9 1011 12 1314
when searching for loops of 3, [5 4 3] will be found as beneficial for flipping receiving:
0 1 2 3 4 5 6 7 8 9 10 11 12 13

to test the code:
cities = rand(100,2);
[sortedCities visitsInd routeLength] = solveTSP( cities, true );

Required Products Image Processing Toolbox
MATLAB release MATLAB 7.7 (R2008b)
10 Jul 2013 Liber Eleutherios

### Liber Eleutherios (view profile)

Hi Yonathan, apparently FE#35178 works better than your submission but maybe this is because your function doesn't consider the way back from the last visited city back to the first city, where the path initially began: in fact this one last trip is usually very inefficient while all others appear to be OK (see my example posted in FE#35178). I was wondering if there is a simple way to fix this.

Comment only
28 May 2013 Yonathan Nativ

### Yonathan Nativ (view profile)

thanks Francesco, glad to hear :)

Comment only
28 May 2013 Liber Eleutherios

### Liber Eleutherios (view profile)

Seems to be working fine for me - better than all other codes from the File Exchange both in terms of efficiency of the solution and in terms of running time. Well done!

29 Feb 2012 raman makhaik

### raman makhaik (view profile)

i get error in this code ..... i.e.
??? Maximum recursion limit of 500 reached. Use set(0,'RecursionLimit',N)
to change the limit. Be aware that exceeding your available stack space can

Error in ==> Node..

Comment only
01 Sep 2010 tingting

### tingting (view profile)

Is it possible that your route is not a complete loop? It seems that everything is from the first node to last node, but not looped back.