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

• 成果类型: Article
• 署名作者: Cao, BY; Glover, F
• 署名单位: University of Colorado System; University of Colorado Boulder
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.43.7.908
• 发表日期: 1997
• 页码: 908-921
• 关键词: heuristic; tabu search; ejection chain; TRAVELING SALESMAN

摘要

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.