Two Matching Based Algorithm for Tree Network Design

Abstract

This paper introduces a new heuristic for the local access three 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 with 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.