The TSP2024 Matlab App implements 18 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
• Convex hull insertion
• Cheapest insertion
• Spanning tree
• Bitonic tour
• Clarke-Wright heuristic
• Divide and conquer
• Karp's approach
• 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.