Tabu Search and Ejection Chains---Application to a Node Weighted Version of the Cardinality-Constrained TSP

Buyang Cao and Fred Glover
Additional contact information
Buyang Cao: Department of Transportation/Logistics Service, ESRI, Inc., 380 New York Street, Redlands, California 92373
Fred Glover: Graduate School of Business and Administration, Campus Box 419, University of Colorado at Boulder, Boulder, Colorado 80309-0419

Management Science, 1997, vol. 43, issue 7, 908-921

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 (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.43.7.908 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:43:y:1997:i:7:p:908-921

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().