The Covering Salesman Problem

Abstract

The primary purpose of this paper is to introduce and mathematically formulate the covering salesman problem (CSP). The CSP may be stated as follows: identify the minimum cost tour of a subset of n given cities such that every city not on the tour is within some predetermined covering distance standard, S, of a city that is on the tour. The CSP may be viewed as a generalization of the traveling salesman problem. A heuristic procedure for solving the CSP is presented and demonstrated with a sample problem.