Optimal use of hub facilities: A two-hub model with fixed arc costs

Summary We introduce a model of a communication network design problem involving the utilization of hub facilities. That is, for a problem with two sets of customers and no intraset demand we seek to determine how the hub node associated with each set should be utilized. We assume that the only costs are the fixed costs associated with creating each of the three types of connecting arcs. A key parameter is the “group” size which is the number of communication circuits which can be bundled together in an arc. The optimal design depends strongly on how closely the arcs can be filled to capacity. The general demand problem is shown to be NP-Hard. However, for unit demand, we derive an almost “all or nothing” result which specifies that all flow should be direct node-to-node or, on the other hand, all or almost all flow should go via the hubs. Research supported in part by Grant SAB-94-0115 from the Spanish Interministerial Commission of Science and Technology while this author was on sabbatical leave at the Polytechnic University of Catalonia in Barcelona.