Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/36226
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor1 | Geraldo Robson Mateus | pt_BR |
dc.contributor.advisor1Lattes | http://lattes.cnpq.br/6289602045034353 | pt_BR |
dc.contributor.referee1 | Henrique Pacca Loureiro Luna | pt_BR |
dc.contributor.referee2 | Nívio Ziviani | pt_BR |
dc.contributor.referee3 | Nelson Maculan Filho | pt_BR |
dc.contributor.referee4 | James MacGregor Smith | pt_BR |
dc.creator | Frederico Rodrigues Borges da Cruz | pt_BR |
dc.creator.Lattes | http://lattes.cnpq.br/9309934981626540 | pt_BR |
dc.date.accessioned | 2021-06-01T12:50:20Z | - |
dc.date.available | 2021-06-01T12:50:20Z | - |
dc.date.issued | 1997-02-04 | - |
dc.identifier.uri | http://hdl.handle.net/1843/36226 | - |
dc.description.abstract | In this thesis, a special class of network design problems representing an important collection of mixed-integer programming problems is studied. The problems are defined on a digraph, where an optimal subset of arcs and nodes fulfilling a special set of constraints is sought. The uncapacitated fixed-charge network flow (UFNF) problem is presented along with a comprehensive review of the research advances in the field. An original solution algorithm is developed and its practical efficiency is demonstrated through a comprehensive set of computational experiments. The multi-level network design (MLND) problem is next developed and a review of the research efforts on similar problems is presented showing the increasing attention such models have recently received. The methods developed for the UFNF problem are extended to the MLND problem, achieving encouraging computational results. Also, parallel implementations for the algorithms are developed, demonstrating that this is a promising area for future investigations. Some possible research directions for further study on the MLND problem are proposed and briefly outlined. Finally, it is noteworthy to point out that the main results in this thesis may be extended to many other network design problems. | pt_BR |
dc.description.resumo | Nessa tese, estudamos alguns problemas de planejamento de redes (network design problems), uma denominação genérica que agrupa muitos problemas importantes. São problemas definidos em grafos, onde é procurado um sub-conjunto de arcos e de nós, cumprindo certos requisitos. Apresentamos o problema não-capacitado de fluxos com custos fixos (NCFCF), com uma revisão bibliográfica atualizada sobre os avanços no estudo do problema, e desenvolvemos um método de solução original. Mostramos resultados computacionais, onde são resolvidos problemas conhecidos na literatura. Introduzimos um novo modelo, o problema de planejamento de redes em multi-níveis (PRMN), apresentando uma revisão bibliográfica sobre problemas correlatos e mostrando o crescente interesse nesse tipo de modelo. Os métodos desenvolvidos para o problema NCFCF foram então estendidos a esse novo modelo, o problema PRMN, com resultados promissores, conforme atestam os resultados computacionais que apresentamos. Elaboramos um estudo comparativo entre diversas implementações paralelas para os algoritmos desenvolvidos, com resultados práticos encorajadores, em termos de speedup. Fazemos uma revisão bibliográfica e discutimos possíveis extensões para a nossa pesquisa. Finalmente, é importante reforçar que os principais resultados dessa tese podem ser estendidos a muitos outros problemas de planejamento de redes. | pt_BR |
dc.description.sponsorship | CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior | pt_BR |
dc.language | por | pt_BR |
dc.publisher | Universidade Federal de Minas Gerais | pt_BR |
dc.publisher.country | Brasil | pt_BR |
dc.publisher.department | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO | pt_BR |
dc.publisher.program | Programa de Pós-Graduação em Ciência da Computação | pt_BR |
dc.publisher.initials | UFMG | pt_BR |
dc.rights | Acesso Aberto | pt_BR |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/pt/ | * |
dc.subject | Planejamento de redes | pt_BR |
dc.subject | Programação inteira-mista | pt_BR |
dc.subject | Localização | pt_BR |
dc.subject | Fluxo em redes | pt_BR |
dc.subject.other | Redes de computadores | pt_BR |
dc.subject.other | Algoritmos de computador | pt_BR |
dc.subject.other | Otimização matemática | pt_BR |
dc.subject.other | Computação | pt_BR |
dc.title | Algoritmos para problemas de planejamento de redes | pt_BR |
dc.type | Tese | pt_BR |
dc.identifier.orcid | https://orcid.org/0000-0001-5842-5544 | pt_BR |
Appears in Collections: | Teses de Doutorado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
DScFRBCruz.pdf | Tese de doutorado de F. R. B. Cruz | 968.37 kB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License