Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/RVMR-7CTQ2W
Type: | Tese de Doutorado |
Title: | Sistemas eixo-raio de múltipla atribuição: modelos e algoritmos |
Authors: | Ricardo Saraiva de Camargo |
First Advisor: | Henrique Pacca Loureiro Luna |
First Referee: | Geraldo Robson Mateus |
Second Referee: | Mauricio Cardoso de Souza |
Third Referee: | Reinaldo Morabito Neto |
metadata.dc.contributor.referee4: | Roberto Dieguez Galvão |
Abstract: | Em sistemas de telecomunicações e de transporte, o problema localização de concentradores com atriuição múltipla surge quando demandas entre muitos pares de origem-destino devem ser enviadas.Ao invés de servir cada demanda entre uma origem e um destino com uma conexão direta, os fluxos são reunidos a partir de concentradores (\textit{hubs}) e enviados, através de uma rede de concentradores, para serem então entregues aos respectivos destinos. Sistemas com esse tipo de topologia são chamados de sistemas do tipo eixo-raio ou redes do tipo eixo-raio. Essas redes são projetadas para usufruírem da economia de escala obtida ao se concentrar o fluxo durante o transporte e/ou transmissão entre concentradores. Portanto, o problema consiste em encontrar a configuração de rede eixo-raio com o menor custo possível selecionando quais locais a se instalar um concentrador e atribuindo o tráfego a cada um, dados os custos de instalação, de transporte e a demanda entre os pares de origem e destino. No presente trabalho, três versões diferentes do problema são estudadas: o problema clássico, a economia de escala dependente do fluxo e o congestionado. Algoritmos eficientes baseados no métodode Decomposição de Benders foram empregados na resolução dos problemas, resolvendo instâncias de grande porte, consideradas fora do alcance'' de métodos exatos, em um tempo aceitável. |
Abstract: | In telecommunication and transportation systems, the multiple allocation hub location problem arises when we must flow commodities or information between several origin-destination pairs. Instead of establishing a direct node to node connection from an origin to its destination, the flows are concentrated with others at facilities called hubs. These flows are transported on links established between hubs, being then splitted and delivered to its final destination. Systems with this sort of topology are named hub-and-spoke systems or hub-and-spoke networks. They are designed to exploit the scale economies attainable through theshared use of high capacity links between hubs. Therefore, the problem is to find the least expensive hub-and-spoke network, selecting hubs and assigning traffic to them, given the demands between each origin-destination pair and the respective transportation costs. In the present work, we study threedifferent versions of the problem: the classical, the flow dependent scale economies and the congestioned. Efficient Benders decomposition algorithms have been deployed to tackle the problems. We have been able to solve some large instances, considered out of reach' of other exact methods in reasonable time. |
Subject: | Sistemas de telecomunicações Computação Telecomunicações Tráfego |
language: | Português |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
Rights: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/RVMR-7CTQ2W |
Issue Date: | 13-Sep-2007 |
Appears in Collections: | Teses de Doutorado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
ricardosaraivacamargo.pdf | 943.26 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.