OPTIMAL-DESIGN OF A 2-LEVEL HIERARCHICAL NETWORK WITH TREE-STAR CONFIGURATION

Abstract

This paper deals with the topological design problem of a hierarchical two-level network where the upper-level backbone network is of tree type and the lower-level local access networks are of star-type. As a means to widen the real-world applicability over the existing network design studies, a backbone node not opened is allowed to be included in the backbone tree for transhipment purpose. The problem is modelled as a mixed 0-1 integer programming, whose special structure is exploited for the development of a dual-based lower bounding procedure. The procedure is incorporated in the branch and bound solution method, whose effectiveness is well demonstrated by the computational experiments conducted with a variety of problems ranging up to 50 backbone nodes and 200 demand points.