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.

Methodological Aspects of Ring Network Design

ARBIB, CLAUDIO;
1992-01-01

Abstract

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/25354
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 0
social impact