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