Modeling and Heuristic Worst-Case Performance Analysis of the Two-Level Network Design Problem

Abstract

This paper studies a multi-facility network synthesis problem, called the Two-level Network Design (TLND) problem, that arises in the topological design of hierarchical communication, transportation, and electric power distribution networks. We are given an undirected ne twork containing two types of nodes-primary and secondary-and fixed costs for installing either a primary or a secondary facility on each edge. Primary nodes require higher grade interconnections than secondary nodes, using the more expensive primary facilities.