Tabu Search and Ejection Chains—Application to a Node Weighted Version of the Cardinality-Constrained TSP
Management Science · 1997 · Volume 43 · Issue 7
Abstract
A cardinality-constrained TSP (CC-TSP) problem 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.
Keywords
heuristic, tabu search, ejection chain, traveling salesman
Enable JavaScript for citation tools and additional paper interactions.