Tree network design avoiding congestion |
| |
Authors: | G. Miranda H.P. Luna R.S. de Camargo L.R. Pinto |
| |
Affiliation: | 1. Universidade Federal de Minas Gerais, Departamento de Engenharia de Produção, Av. Antônio Carlos, 6627, Pavilhão Central de Aulas, Pampulha, Zip 30161-010, Belo Horizonte, Minas Gerais, Brazil;2. Universidade Federal de Alagoas, Instituto de Computação, Campus A. C. Simões, BR 104, Km 14, Tabuleiro dos Martins, Zip 57072-970, Maceió, Alagoas, Brazil |
| |
Abstract: | We introduce in this paper an optimal method for tree network design avoiding congestion. We see this problem arising in telecommunication and transportation networks as a flow extension of the Steiner problem in directed graphs, thus including as a particular case any alternative approach based on the minimum spanning tree problem. Our multi-commodity formulation is able to cope with the design of centralized computer networks, modern multi-cast multi-party or hub-based transportation trees. The objective in such cases is the minimization of the sum of the fixed (structural) and variable (operational) costs of all the arcs composing an arborescence that links the origin node (switching center, server, station) to every demand node (multi-cast participants, users in general). The non-linear multi-commodity flow model is solved by a generalized Benders decomposition approach. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|