A solution procedure for the Generalized Covering Salesman Problem

Given n nodes, the covering salesman problem is to identify the minimum length tour covering all the nodes, i.e. the minimum length tour visiting a subset of then nodes and such that each node not on the tour is within a predetermined distance from the nodes on the tour. In the Generalized Covering Salesman Problem (GCSP) each node i needs to be covered at least k, times and there is avisiting cost associated with each node. This problem has three variants; in the first case, each node can be visited by the tour at most once, in the second version visiting a node more than once is possible but it is not allowed to stay overnight, and finally, in the third variant the tour can visit each node more than once consecutively. We propose an improvement procedure based on Integer Linear Programming (ILP) techniques. Computational results on benchmark instances from the literature show the effectiveness of the proposed approach.

Keywords:

Covering Salesman Problem , Generalized Covering Salesman Problem , HeuristicProcedures , Integer Linear Programming