Computational experience of improvement heuristics for the Sparse Travelling Salesman problem

The Sparse Travelling Salesman Problem (Sparse TSP) is a variant of the Travelling Salesman Problem (TSP), which is one of the major success stories in optimization. The TSP can be described as the problem of finding a route of a salesman starting from his home city, visiting each city in a particular region exactly once and returning home at the end while minimizing the tour length. The Sparse TSP which is studied in this paper is a problem of finding the shortest route of the salesman when visiting cities in a region making sure that each city is visited at least once and returning home at the end. In the Sparse TSP, the distance between cities may not obey the triangle inequality (i.e., the shortest distance between any two cities may not be a direct road joining the two cities; it may be cheaper to go via other cities). In this paper we design and implement improved versions of 2-opt and 3-opt heuristic algorithms, which are specifically designed to take advantage of sparsity in the Sparse TSP. These improvement heuristic algorithms incorporate the use of large neighbourhood structure, enabling them to produce results which are much better than existing ones. In our implementation we use several, speed-up techniques to make our algorithms run faster. We test our improvement heuristic algorithms using problems taken from road network in rural Ireland and the TSP Library (TSPLIB).