The Covering Salesman Problem (CSP) is to identify the minimum length tour of a subset of n given cities such that each city not on the tour is within a predetermined distance from the nodes 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 customer i needs to be covered at least k(i) times and there is a visiting cost associated with each customer. We define three variants of this new problem. In the first case, each city can be visited just once, while in the second version visiting a node more than once is possible but we are not allowed to stay overnight. So for revisiting a node, we have to visit another customer and come back again. Finally in the third variant, the salesman can visit each city more than once consecutively. In this paper, we develop two heuristics for solving CSP and GCSP variants and 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 that on these test bed. Overall results show that our suggested method is strong and fast enough

Keywords