Algoritmos para problemas de planejamento de redes

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.