another TSP solver

a simple TSP local minimum solution. code is very short and simple.
6,1K téléchargements
Mise à jour 28 juil. 2009

Afficher la licence

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

Citation pour cette source

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

Compatibilité avec les versions de MATLAB
Créé avec R2008b
Compatible avec toutes les versions
Plateformes compatibles
Windows macOS Linux

Community Treasure Hunt

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

Start Hunting!
Version Publié le Notes de version
1.1.0.0

edited text

1.0.0.0