2-Optimization Based Local Search Approaches to Solving Symmetric Traveling Salesman Problem

In combinatorial optimization, the traveling salesman problem (TSP) is an NP-hard problem that has been widely studied in theoretical computer science and operations research. Actually, it is very easy to understand but often very complex to solve. The TSP problem can be solved by using both exact and non-exact solvers. An exact solver can give an optimal solution but consumes a lot of time. Therefore, they are not suitable for solving large-scale TSP problems. On the other hand, a non-exact solver can give an acceptable approximation within a very short time period. As a result, these solvers have been extensively used to solve the large-scale TSP problem. One of the most famous non-exact metaheuristic approaches for solving TSP is the local search algorithm. Indeed, 2-optimization is a basic local search algorithm in optimization that has been demonstrated to be a successful methodology and applied to a number of combinatorial optimization problems. It is considered one of the high-performance computing solutions for the TSP. A complete 2-optimization local search is compared to every possible valid combination of the swapping mechanism. In this project thesis, we study on 2-optimization local search approaches to solving symmetric TSP problems. In fact, a first improvement based 2-optimization and best improvement based 2-optimization are adopted to find out the best possible solutions of the symmetric TSP problem. The algorithms are tested on benchmark problems from TSPLIB. Each data is tested 500 times and test results are presented as best results, worst results and average results with the time taken for the execution in both cases. Finally, the obtained results are compared with each other both in the aspect of results and elapsed time. It is observed from experimental results that, the first improvement based 2-optimization approach performs better than best improvement based 2-optimization approach in terms of both solution quality as well as computational time.

• Supervision