A tabu search heuristic for the undirected selective travelling salesman problem

The undirected Selective Travelling Salesman Problem (STSP) is defined on a graph G = (V,E) with positive profits associated with vertices, and distances associated with edges. The STSP consists of determining a maximal profit Hamiltonian cycle over a subset of V whose length does not exceed a preset limit L. We describe a tabu search (TS) heuristic for this problem. The algorithm iteratively inserts clusters of vertices in the current tour or removes a chain of vertices. Tests performed on randomly generated instances with up to 300 vertices show that the algorithm consistently yields near-optimal solutions.