# An Improvement to the 2-Opt Heuristic Algorithm for Approximation of Optimal TSP Tour
###### Abstract  
The travelling salesman problem (TSP) is perhaps the most researched problem in the field of Computer Science and Operations. It is a known NP-hard problem and has significant practical applications in a variety of areas, such as logistics, planning, and scheduling. Route optimisation not only improves the overall profitability of a logistic centre but also reduces greenhouse gas emissions by minimising the distance travelled. In this article, we propose a simple and improved heuristic algorithm named 2-Opt++, which solves symmetric TSP problems using an enhanced 2-Opt local search technique, to generate better results. As with 2-Opt, our proposed method can also be applied to the Vehicle Routing Problem (VRP), with minor modifications. We have compared our technique with six existing algorithms, namely ruin and recreate, nearest neighbour, genetic algorithm, simulated annealing, Tabu search, and ant colony optimisation. Furthermore, to allow for the complexity of larger TSP instances, we have used a graph compression/candidate list technique that helps in reducing the computational complexity and time. The comprehensive empirical evaluation carried out for this research work shows the efficacy of the 2-Opt++ algorithm as it outperforms the other well-known algorithms in terms of the error margin, execution time, and time of convergence. t 1 2023 13 2023 2  
solution [10]. The effort in finding the optimal result of any NP-hard problem can grow exponentially from huge to impossible, thus making the retrieval of a solution impractical for relatively larger-scale problem sizes [1]. Heuristics can minimise the complexity from exponential to polynomial time by sacrificing some accuracy [7]. Almost all real-world problems that rely on the effective results of TSP instances, such as network optimisation, logistics, postal, or any other industry that involves planning or logistics, can greatly benefit from the provided TSP algorithm [11; 12; 13]. Consider a complete graph as input to the algorithm: \(G=(V,E)\) where \(V\) represents the nodes and \(E\) represents the edges. Each edge \((u,\ v)\in E\) has a non-negative integer cost denoted as \(c(u,\ v)\). The problem is to find a Hamiltonian cycle (tour) of \(G\) with the minimum cost. The heuristic algorithm should solve symmetric TSP instances with a minimal error margin. It should effectively solve large-input problems in a reasonable amount of time. The TSP can be formulated as below. Given a set of vertices \(V\) = 0,1,2,..., \(n-1\), where the distance between a pair of vertices is given as \(d_{ij}\), the objective is to minimise  
\[\sum_{i}\sum_{j}d_{ij}X_{ij} \tag{1}\]  
where  
\[X_{ij}= \begin{cases}1&\text{the path goes from node $i$ to node $j$}\\ 0&\text{otherwise}\end{cases}  \tag{2}\]  
subject to  
\[\sum_{j}X_{ij}=1 \tag{3}\]  
and each vertex needs to be visited once. \[\sum_{i}X_{ij}=1 \tag{4}\]  
The salesman must come from only one vertex when visiting this vertex. \[X_{ii}=0 \tag{5}\]  
There should be no self-loop. \[\sum_{i}\sum_{j}X_{ij}\ \leqslant\ |S|\ -\ 1\ \ \,\qquad\forall S\subset V\ \,\ \ 2\leqslant\ |S|\ \leqslant\ n-2 \tag{6}\]  
We need to incorporate the global requirement that there is one tour that visits all vertices, as the local constraints defined above can lead to situations where there are multiple tours visiting only a subset of the total number \(n\) of vertices \(V\). Here, \(S\) is a set of all possible subtours of graph G. This constraint requires that the tour should proceed from a vertex in \(S\) to a vertex not in \(S\) (and vice versa). In this paper, an improved algorithm, 2 OPT++, is proposed using the 2-opt technique for the TSP problem. The algorithm performs considerably well in terms of the running time and approximation ratio, even for very large problem instances. It is proposed to use an optional graph compression step to improve the running time of the algorithm when dealing with large problem instances.