TSP2024

版本 2.2 (5.5 MB) 作者: Didier Maquin
TSP2024 implements 28 different sub-optimal methods for solving the symmetric Euclidean TSP problem as well as the 2-opt enhancing method.
0.0
(0)
180.0 次下载
更新时间 2025/7/24

查看许可证

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.

引用格式

Didier Maquin (2025). TSP2024 (https://www.mathworks.com/matlabcentral/fileexchange/158496-tsp2024), MATLAB Central File Exchange. 检索时间: .

MATLAB 版本兼容性
创建方式 R2021a
与 R2021a 及更高版本兼容
平台兼容性
Windows macOS Linux

Community Treasure Hunt

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

Start Hunting!

版本 已发布 发行说明
2.2

Three new methods have been added: a naive geometric one, the sector based partition, and two population based algorithms, komodo mlipir and Djaya algorithms.
2.1

- A firefly algorithm has been added
2.0

- The UI was modified to reading files in TSPLIB format.
- A new switch controls how the final result is displayed.
- A new method "Doubled-ended nearest and loneliest neighbour approach (DENLN)" was added.
- Code for Karp's approach was modified.
1.11

A new method entitled Polynomial-Time Deterministic (PTD) approach has been added.
1.10

A new geometric method has been added: pair-center algorithm recently proposed by Arno Formella.
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