# another TSP solver

Version 1.1.0.0 (2.36 KB) by
a simple TSP local minimum solution. code is very short and simple.
Updated 28 Jul 2009

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

### Cite As

Yonathan Nativ (2024). another TSP solver (https://www.mathworks.com/matlabcentral/fileexchange/24857-another-tsp-solver), MATLAB Central File Exchange. Retrieved .

##### MATLAB Release Compatibility
Created with R2008b
Compatible with any release
##### Platform Compatibility
Windows macOS Linux