Code optimisation on the example of an algorithm for solving the traveling salesman problem

This paper presents a comprehensive approach to optimizing the cycle merging algorithm applied to the Traveling Salesman Problem (TSP), a classic NP-hard problem that has challenged researchers and practitioners alike in logistics, manufacturing, and data-intensive applications. The TSP requires finding the shortest possible route that visits a list of cities and returns to the starting point. As the number of cities grows, finding an exact solution becomes computationally prohibitive, making approximation techniques both necessary and valuable in practical applications. The cycle merging algorithm is a well-established heuristic approach to solving TSP. It constructs an initial 2-factor solution that includes a set of cycles covering all vertices, and iteratively merges the cycles based on optimal edge replacement until only one cycle remains. Along with the choice of the solution algorithm, the quality of the application code plays an important role. In the process of work, a number of measures aimed at optimising the program code implementing the cycle merging algorithm have been performed. The approach includes optimising the algorithm, optimising the data storage structure and using parallel programming techniques. Experimental results show that the optimised algorithm significantly out-performs the baseline implementation, achieving a speedup factor proportional to the number of computational cores and nodes. Tests conducted on instances with up to 1000 nodes showed that our approach makes it possible to solve larger problems without a commensurate increase in computational resources. The study also observed a consistent performance gain in cache utilisation and a reduction in latency at key stages of the algorithm, which confirms the effectiveness of the chosen optimisations. This work provides a sound basis for solving large TSP instances by combining heuristic methods with advanced computational optimisations. The results highlight the importance of both algorithm efficiency and imple-mentation techniques when solving computationally intensive problems. The approach and results presented here are not only applicable to TSP, but also to a broader class of combinatorial optimisation problems where parallelism and memory efficiency are important. Future work may investigate additional optimisations through GPU acceleration or hybrid parallelism techniques, potentially providing even better performance.