TSP2024

TSP2024 implements 28 different sub-optimal methods for solving the symmetric Euclidean TSP problem as well as the 2-opt enhancing method.

The TSP2024 Matlab App implements 28 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

• Doubled-ended nearest and loneliest neighbour approach (DENLN)

• Multi-fragment heuristic

• Convex hull insertion

• Cheapest insertion

• Delaunay insertion

• Spanning tree

• Bitonic tour

• Sector based partition

• PTD approach

• Clarke-Wright heuristic

• Divide and conquer

• Karp's approach

• Pair-center algorithm

• Space-filling curve

• Metropolis algorithm

• Simulated annealing

• Kohonen map

• Bees algorithm

• Reinforcement learning

• Ant system

• Genetic algorithm

• Black hole algorithm

• Firefly algorithm

• Komodo mlipir algorithm

• Djaya 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). The processed data set is either random or read from a file in TSPLIB format. The user can choose this using the buttons on the right of the visualization window below “Choice of data set”. At launch, a random set of 20 points 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. The data set can also come from a file in TSPLIB format. In this case, press the “Load” button. A dialog window listing the files in the current directory will then appear. It enables a user to select the name of a *.tsp file. If the file is valid, the data set is then displayed.

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. For a given data set, the length of the best tour obtained (Best length) is stored and displayed at the bottom left 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). The switch below controls how the final result is displayed. If set to “Path”, the Hamiltonian cycle and the points are displayed. If set to “Patch”, the interior of the polygon defined by the Hamiltonian cycle is displayed. Be careful, this notion of interior can be poorly defined if the cycle has crossings (before using 2-opt optimization). This option is more suitable for large sets of points (or for abstract art lovers!).

A pdf file (included in the zip file to download) explains how the methods work and how they were implemented. The zip file contains also a folder with files in TSPLIB format.