| Abstract [eng] |
During this study, a synthetic dataset generation tool for the Travelling Salesman Problem with known optimal solutions, as well as a benchmarking system for evaluating solution algorithms, was developed. Using these tools, four algorithms for solving the Travelling Salesman Problem were investigated: the Genetic Algorithm, Ant Colony Optimization algorithm, Lin–Kernighan–Helsgaun algorithm, and Google OR-Tools algorithm. First, a literature review was conducted to gather information about Travelling Salesman Problem solution algorithms, including their operating principles, advantages, and disadvantages. Subsequently, four methods frequently identified in recent literature as the most suitable for handling large-scale datasets were selected for further analysis. The experimental phase began with the use of the dataset generation tool to create 120 datasets with varying numbers of nodes (100, 1000, and 10000) and different spatial scales (from city-level to continent-level). Afterwards, 480 experiments were carried out (total execution time – 9 h 53 min 14 s) using the initial parameter configurations identified in the literature. The OR-Tools method found the highest number of optimal solutions (92.50 %) but was also the slowest, requiring an average of 118.8 s per experiment. Meanwhile, the LKH method demonstrated the best balance between solution quality (77.50 %) and execution speed (45.9 s). The ACO method achieved accuracy results close to LKH (75.80 %) but was slightly slower (68.7 s). The Genetic Algorithm performed particularly poorly on datasets containing 1000 and 10000 nodes due to the imposed time limit, achieving only 46.70 % optimal solutions with an average execution time of 63.3 s per experiment. Finally, a stability analysis of the methods was performed by conducting 480 additional experiments (12 datasets with 10 repetitions for all 4 methods, total execution time – 7 h 34 min 21 s) using the same parameter settings. The results demonstrated that the initial random seed had no significant impact on either the solution quality or the execution time. |
