Combining Exact and Heuristic Approaches for the Covering Salesman Problem

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 ican cover a subset of vertices within its predetermined covering distance r ;. The goal is to construct a minimum lengthHamiltonian 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 ahybrid exact and heuristic approach which takes advantage of Integer Linear Programming (ILP) techniques and heuristicsearch 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.

Combining Exact and Heuristic Approaches for the Covering Salesman Problem Keywords:

Covering Salesman Problem , Integer Linear Programming , Column generation