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

A cardinality-constrained TSP (CC-TSP) problem requires the salesman to visit at. least L and at most U cities, represented toy 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.