Given n cities, the Covering Salesman Problem (CSP) is to identify the minimum length tour “covering” all the nodes, i.e. the minimum length tour visiting a subset of the n cities and such that each city not on the tour is within a predetermined distance from the cities on the tour. In this paper we define and develop a generalized version of this problem, and name it Generalized Covering Salesman Problem (GCSP), in which each city i needs to be covered at least times and there is a visiting cost associated with each city. We define three variants of this new problem. In the first case, each city can be visited by the tour at most once. In the second version visiting a node i more than once is possible but it is not allowed to stay overnight, i.e. for revisiting a city i the tour has to visit at least another city before to return to i. Finally, in the third variant the tour can visit each city more than once consecutively. In this paper, we develop two heuristics for solving CSP and the three GCSP variants. For testing the proposed algorithms, we generate some datasets based on TSP Library instances. Moreover, we define some regular datasets, whose good solutions can be estimated virtually, and demonstrate the quality of our best heuristic, by examining it on these test bed. Overall results show that our suggested method is strong and fast enough

Keywords