another TSP solver

a simple TSP local minimum solution. code is very short and simple.
6,1K Downloads
Aktualisiert 28. Jul 2009

Lizenz anzeigen

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

Zitieren als

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

Kompatibilität der MATLAB-Version
Erstellt mit R2008b
Kompatibel mit allen Versionen
Plattform-Kompatibilität
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Veröffentlicht Versionshinweise
1.1.0.0

edited text

1.0.0.0