Models and algorithms for the phone network cabling problem

Orientador: Arnaldo Vieira MouraDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: O principal objetivo deste trabalho é a elaboração de heurísticas para auxiliar no projeto de cabeamento de redes telefônicas. O cabeamento será tratado desde os armários de distribuição até as caixas terminais. O auxílio de uma ferramenta computacional especializada no projeto de novas redes telefônicas abre caminhos para a minimização de custos e também reduz sensivelmente o tempo de planejamento. Inicialmente, estuda-se o problema para se obter uma especificação minuciosa, acompanhada de um modelo matemático. Com estas informações, desenvolve-se diferentes estratégias para algoritmos baseados na heurística GRASP, e compara-se os resultados experimentais obtidosAbstract: The main goal of these studies is the design of heuristics to support the planning of wire cabling on a phone network. The cabling will be handled from the central distribution point to terminal boxes. The assistance of a computational tool specialized in the design of phone networks raises new opportunities for cost reduction and decreases considerably the time spent designing the network. The problem is first studied in order to achieve a detailed specification with a mathematical model. Based on this information, several different strategies are laid out based on a heuristic called GRASP and the experimental results are compared.MestradoOtimização CombinatoriaMestre em Computaçã