Traveling Salesman Problem (TSP) is one of the major problems in Operations Research from the last few decades. Given n pre-specified cities, the goal is to find the minimum length tour of the cities such that the salesman, starting from an original city, visits each city exactly once and returns to the origin [5]. During recent years, this problem has been extended to several specific variants such as Traveling Salesman Problems with profits [7], Clustered Traveling Salesman Problem [6], The Generalized Traveling Salesman Problem [10], and a lot of solution procedures have been suggested and analyzed for these objectives [7, 6, 10, 1, 8]. Current and Schilling [4] referred to some real world examples, such as routing of rural healthcare delivery teams where the assumption of visiting each village is not valid. According to their assumption, it is sufficient for all villages to be near to some stops on the tour, and for those villages which are not in the route, it is expected to go to their nearest stop. So, they defined Covering Salesman Problem as that in which the goal is to find the minimum length tour of a subset of n given cities, such that every city not on the tour is within a predefined covering distance, d, of a city that is on the tour [3]. If d = 0 or d < minijdist(i, j), where dist(i, j) is the shortest distance between nodes i and j, the CSP reduces to TSP. Current and Schilling [4] suggested a heuristic for the CSP which solves the Set Covering Problem (SCP) over the given cities and then finds the optimal TSP tour of the points generated by SCP solver [4]. Arkin and Hassin [2] introduced a geometric version of the Covering Salesman Problem. In this problem, each of the n customers specifies a neighborhood in which they are willing to meet the salesman. The authors presented simple heuristic procedures for constructing tours for a variety of neighborhood types. In their approaches, the length of the tour is guaranteed to be within a constant factor of the length of the optimal tour. In the current paper, we define some new variants of the problem and develop two heuristics to solve these problems

Keywords