Tabu search and ejection chains – application to a node weighted version of the cardinality-constrained TSP

A cardinality-constrained travelling salesman problem (CC-TSP) requires the salesman to visit at least L and at most U cities, represented by nodes of a graph. The objective of this problem is to maximize the sum of weights of nodes visited. In this paper we propose a tabu search method based on ejection chain procedures, which have proved effective for many kinds of combinatorial optimization problems. Computational results on a set of randomly generated test problems with various implementations of the algorithm are reported.