Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem

被引:94
作者
Ahuja, RK [1 ]
Orlin, JB
Sharma, D
机构
[1] Univ Florida, Dept Ind & Syst Engn, Gainesville, FL 32611 USA
[2] MIT, Alfred P Sloan Sch Management, Cambridge, MA 02139 USA
[3] MIT, Ctr Operat Res, Cambridge, MA 02139 USA
关键词
D O I
10.1007/s101070100234
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
The capacitated minimum spanning tree (CMST) problem is to find a minimum cost spanning tree with an additional cardinality constraint on the sizes of the subtrees incident to a given root node. The CMST problem is an NP-complete problem. and existing exact algorithms can solve only small size problems. Currently, the best available heuristic procedures for the CMST problem are tabu search algorithms due to Amberg et al. and Sharaiha et al. These algorithms use two-exchange neighborhood structures that are based on exchanging a single node or a set of nodes between two subtrees. In this paper. we generalize their neighborhood structures to allow exchanges of nodes among multiple subtrees simultaneously we refer to such neighborhood structures as multi-exchange neighborhood structures. Our first multi-exchange neighborhood structure allows exchanges of single nodes among several subtrees. Our second multi-exchange neighborhood structure allows exchanges that involve multiple subtrees. The size of each of these neighborhood structures grows exponentially with the problem size without any substantial increase in the computational times needed to find improved neighbors. Our approach, which is based on the cyclic transfer neighborhood structure due to Thompson and Psaraftis and Thompson and Orlin transforms a profitable exchange into a negative cost subset-disjoint cycle in a graph. called an improvement graph. and identifies these cycles using variants of shortest path label-correcting algorithms. Our computational results with GRASP and tabu search algorithms based on these neighborhood structures reveal that (i) for the unit demand case our algorithms obtained the best available solutions for all benchmark instances and improved some: and (ii) for the heterogeneous demand case our algorithms improved the best available solutions for most of the benchmark instances with improvements by as much as 18%. The running times our multi-exchange neighborhood search algorithms are comparable to those taken by two-exchange neighborhood search algorithms.
引用
收藏
页码:71 / 97
页数:27
相关论文
共 27 条
[1]  
Ahuja RK, 1993, NETWORK FLOWS THEORY
[2]  
Amberg A, 1996, Combinatorial Optimization, V1, P9
[3]  
[Anonymous], 1997, TABU SEARCH
[4]  
Bresina JL, 1996, PROCEEDINGS OF THE THIRTEENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND THE EIGHTH INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE, VOLS 1 AND 2, P271
[5]   ON TELEPROCESSING SYSTEM DESIGN .2. A METHOD FOR APPROXIMATING OPTIMAL NETWORK [J].
ESAU, LR ;
WILLIAMS, KC .
IBM SYSTEMS JOURNAL, 1966, 5 (03) :142-+
[6]   GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURES [J].
FEO, TA ;
RESENDE, MGC .
JOURNAL OF GLOBAL OPTIMIZATION, 1995, 6 (02) :109-133
[7]  
FESTA P, 2000, ESSAYS SURVEY METAHE
[8]  
Gavish B., 1991, Annals of Operations Research, V33, P17, DOI 10.1007/BF02061657
[9]  
GENDREAU M, 1998, CRT9810 U MONT
[10]  
Glover F., 1989, ORSA Journal on Computing, V1, P190, DOI [10.1287/ijoc.2.1.4, 10.1287/ijoc.1.3.190]