|
A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem R.K. Ahuja, J.B. Orlin, and D. Sharma, Operations Research Letters 31, 185-194, 2003 The capacitated minimum spanning tree (CMST) problem is to find a minimum cost spanning tree in a network where nodes have specified demands, with an additional capacity constraints on the subtrees incident to a given source node s. The capacitated minimum spanning tree problem arises as an important subproblem in many telecommunication network design problems. In a recent paper, Ahuja, Orlin and Sharma [2001] proposed two very large scale neighborhood search algorithms for the capacitated minimum spanning tree problem. The first node-based neighborhood structure is obtained by performing multi-exchanges involving several trees where each tree contributes a single node. The second tree-based neighborhood structure is obtained by performing multi-exchanges where each tree contributes a subtree. The computational investigations found that node-based multi-exchange neighborhood gives the best performance for the homogenous demand case (when all nodes have the same demand), and the tree-based multi-exchange neighborhood gives the best performance for the heterogeneous demand case (when nodes may have different demands). In this paper, we propose a composite neighborhood structure that subsumes both the node-based and tree-based neighborhoods, and outperforms both the previous neighborhood search algorithms for solving the capacitated minimum spanning tree problem on standard benchmark instances. We also develop improved techniques for searching the composite neighborhood. |