A composite very large-scale neighbourhood structure for the capacitated minimum spanning tree problem

A composite very large-scale neighbourhood structure for the capacitated minimum spanning tree problem

0.00 Avg rating0 Votes
Article ID: iaor2004375
Country: Netherlands
Volume: 31
Issue: 3
Start Page Number: 185
End Page Number: 194
Publication Date: May 2003
Journal: Operations Research Letters
Authors: , ,
Keywords: networks: path
Abstract:

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 et al. proposed two very large-scale neighborhood search algorithms for the capacitated minimum spanning tree problem. Their first node-based neighborhood structure is obtained by performing multi-exchanges involving several trees where each tree contributes a single node. Their 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 of the homogeneous demand case (when all nodes have the same demand), and the tree-based multi-exchange neighborhood gives the best performance of 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 dynamic programming based exact algorithms for searching the composite neighborhood.

Reviews

Required fields are marked *. Your email address will not be published.