Two matching based algorithm for tree network design

Two matching based algorithm for tree network design

0.00 Avg rating0 Votes
Article ID: iaor1995293
Country: India
Volume: 15
Issue: 2
Start Page Number: 213
End Page Number: 226
Publication Date: May 1994
Journal: Journal of Information & Optimization Sciences
Authors: ,
Keywords: heuristics
Abstract:

This paper introduces a new heuristic for the local access tree network design problem. A tree network is a collection of trees rooted at one of the backbone nodes. There is a capacity limit on each cluster tree which is a collection of nodes that share the same arc connecting them to the backbone node. The connection in each subtree forms a minimum spanning tree (MST), linking the backbone node. Such a design problem is NP-complete, and only small examples have been shown to be solved to optimality. This paper describes an efficient heuristic algorithm based on partitioning two-matching tours into small clusters that satisfy the capacity constraints, and then forming MSTs. This heuristic is compared wit the Parallel Saving Algorithm (PSA). PSA performs better than the partitioning of two-matching tours six to fifteen percent for the single center case. The two-matching based heuristic performs twenty to fifty three percent better than the PSA for the multi-center case.

Reviews

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