TSP2024

Version 1.9 (3.97 MB) by Didier Maquin
TSP2024 implements 21 different sub-optimal methods for solving the symmetric Euclidean TSP problem as well as the 2-opt enhancing method.
0.0
(0)
97 Downloads
Updated 13 Sep 2024

View License

The TSP2024 Matlab App implements 21 different sub-optimal methods for solving the symmetric Euclidean TSP problem as well as the 2-opt enhancing method. The proposed methods are (Method frame):
• Random tour
• Nearest neighbour
• Multi-fragment heuristic
• Convex hull insertion
• Cheapest insertion
• Delaunay insertion
• Spanning tree
• Bitonic tour
• Clarke-Wright heuristic
• Divide and conquer
• Karp's approach
• Space-filling curve
• Metropolis algorithm
• Simulated annealing
• Kohonen map
• Bees algorithm
• Reinforcement learning
• Ant system
• Genetic algorithm
• Black hole algorithm
• Tabu search
each of these methods can be followed by a 2-opt optimization (Enhancing method frame) when necessary.
The application was not designed with a performance objective. However, it can work with a hundred points (or vertices). In order to be able to compare the results obtained (essentially through the length of the cycle: Tour length, displayed at the top of the figure), each method can be tested on the same data set: just select a method and press the ``Run'' button. At launch, the number of points to connect is set to 20 and a random dataset is produced and visualized. To change the number of points, simply indicate it in the ``Number of points" box and press the ``New data set" button. For a given data set, the length of the best tour obtained (Best length) is stored and displayed at the bottom right of the window as the name of the corresponding method.
The application has been designed to visualize the method in action. For this purpose, the on/off switch at the top left of the window allows the slowing down of the graphic animation to observe each step of the implemented algorithms (particularly for the geometric ones and the Kohonen map).
A pdf file (included in the zip file to download) explains how the methods work and how they were implemented.

Cite As

Didier Maquin (2024). TSP2024 (https://www.mathworks.com/matlabcentral/fileexchange/158496-tsp2024), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2021a
Compatible with R2021a and later releases
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

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

Start Hunting!

Version Published Release Notes
1.9

3 new methods have been added: Multi-fragment heuristic, Delaunay insertion and space-filling curve.
1.8

- Two new methods have been added: Metropolis algorithm and Reinforcement learning
- Minor code changes were made
- The user interface has been arranged to take into account the number of methods
1.7.1

- The uploaded zip file was incorrect
1.7

- Two new geometric divide and conquer approaches have been added
- The accompanying document has been revised and updated
- An mlappinstall file is now provided
1.6

- Two new geometric methods have been added (Bitonic tour and Clarke-Wright heuristic).
- The GUI has been slightly modified. To facilitate comparison of results, the length of the best tour obtained is stored and displayed at the bottom right.
1.5

- Two new methods have been added (Black hole algorithm and Tabu search).
- A bug in the crossover function of the Genetic Algorithm method was corrected.
- .m files implemeting each method separately are now provided.
1.4

Three new methods have been added
1.3