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 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.

• 저널Management Science · 43(7) · 908–921
• 토픽Vehicle Routing Optimization Methods · Industrial and Manufacturing Engineering
• DOI10.1287/mnsc.43.7.908
• 저자Buyang Cao, Fred Glover