The Cardinality Constrained Covering Travelling Salesman Problem

In this paper, we propose a new method for partitioning a graph into an unspecified number of Hamiltonian subgraphs with minimum and maximum size requirements on the subgraphs. We refer to this problem as the cardinality constrained covering traveling salesman problem (CCC-TSP). Special cases of this problem include the assignment problem and the traveling salesman problem (TSP). This paper proposes a heuristic solution methodology to a general class of problems that is important because by setting the parameters, one can obtain different important problems including the traveling salesman problem and the assignment problem. Although these specific problems have been studied extensively in the past, the generalized version proposed here and the solution methodology set forth, are new contributions. The solution methodology presented in this paper produces solutions within known error bounds of the optimal solution value. The computational results indicate an ability to obtain very high-quality solutions by expending a modest computational effort for problems in excess of 200 nodes