Methodological Aspects of Ring Network Design

We analyse ring network design problems, with the aim of satisfying at a minimum cost a given demand matrix. The network model considers link capacities ranging over a discrete set of values, and both fixed and linear costs, which pose severe limitations to the possibility of finding global optimum solutions. An approximated version of the problem — which neglects the discrete nature of link capacities — is here formulated as a multicommodity flow problem with linear cost function and fixed costs on a hypergraph. Such a problem is NP-hard. A greedy algorithm, which extends the one proposed by Minoux, is devised. A more general solution approach is also developed, which consists of a decomposition of the general problem into two major steps. Aim of the first is to design a partial network which satisfies a given percentage of the overall demand. This task is formulated as a pure combinatorial problem, in terms of 0–1 linear programming. The second step consists of finding a completion of the partial network, and can be formulated as a classical multicommodity graph-flow problem with fixed costs. Prior to both approaches, effective cluster analysis techniques are suggested for reducing the input size, according to demand, and/or to geographical, logical, and economic criteria.