This thesis is concerned with topological design of two-level networks with hub-ring structure. The present large-scale communication networks take a two-level hierarchical network whose structure is composed of a hub network in the upper level and a family of local access networks in the lower level. This hubbing topology offers extensive integration and sharing of functions to reduce the overall network costs and operate the network with flexibility. The topological design is one of the most important problems that arise in connection with design of two-level hierarchical networks. Then we concentrate the research interest on network design with hubbing topology.
The objective of this thesis is to provide some mathematical formulations and efficient solution methods for topological design problems of a special type of two-level hierarchical network. Owing to the serious drawback of the conventional approach of partitioning the global design problem into two subproblems, one for design of the hub network and the other for design of local access networks, we adopt the unified approach which the whole design problem is directly dealt with in such an integrated framework that both a hub network and local access networks attached to it are to be simultaneously determined.
First, we focus on the design of a network with the two-level ring-star hierarchical structure where the upper-level hub network is ring-shaped, and the lower-level local access networks are of star type, which is commonly found in the LAN, MAN, WAN, and CATV network. The problem is modelled as a mixed 0-1 linear program, whose special sturcture is exploited for the development of an efficient dual-based lower bounding procedure. Because the ring-star design problem is NP-complete, we find the primal feasible solution heuristically through analyzing the dual solution. Despite the complexity inherent in the design problem, the performance of the proposed solution heuristic is shown to be satisfactory via the extensive computational experiments with large-scale test problems up to 20 hub nodes and 50 user nodes.
Secondly, as applications of the ring-star problem formulation and its dual-based solution method, the generalized traveling salesman problem (GTSP) and the generalized minimal spanning tree problem(GMSTP) are considered. These generalized models assume that the nodes have been grouped into mutually exclusive and exhaustive node sets. The GTSP is a generalization of the TSP where the salesman must pass through predefined sets of cities, visiting only one city in each set. Instead of preselecting the nodes to be connected, the GMSTP is to find a minimum cost tree which includes exactly one node form each node set. The GTSP is formulated as a mixed 0-1 linear programming problem embedding the multicommodity network flow problem. A modified dual-based solution method is developed and the performance of the solution procedure is tested on randomly generated problems appeared in a published paper. Our computational results are shown to be comparable with those in the above-mentioned papers. The GMSTP is also formulated as a mixed 0-1 linear programming problem embedding the multicommodity network flow problem. A modified dual-based solution method is developed. To our knowledge, our attempt is the first approach to formulate and analyze the GMSTP.
All these models suggested in this thesis can be extended to more realistic network design problems by augmenting some side constraints. As our discussions on modelling approaches have suggested, the general areas of two-level network design problems will continue to provide challenging opportunities for modelling and algorithmic development through our multicommodity flow formulation method and dual-based solution procedure.
