We consider a generalized version of the well known Traveling Salesman Problem called Covering Salesman problem. In this problem, we are given a set of vertices while each vertex i can cover a subset of vertices within its predetermined covering distance ri. The goal is to construct a minimum length Hamiltonian cycle over a subset of vertices in which those vertices not visited on the tour has to be within the covering distance of at least one vertex visited on the tour. We propose a hybrid exact and heuristic approach which takes advantage of Integer Linear Programming (ILP) techniques and heuristic search to improve the quality of the solutions. Extensive computational tests on the standard benchmark instances and on a new set of large sized datasets show the effectiveness of the proposed approach.

Keywords