Heuristic approaches for network problems

• Ano de defesa: 2015
• Autor(a) principal: Stefanello, Fernando
• Orientador(a): Buriol, Luciana Salete
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Palavras-chave em Português: Computação em nuvem; Redes : Computadores
• Palavras-chave em Inglês: Heuristic; Network problems; BRKGA; Cloud computing
• Link de acesso: http://hdl.handle.net/10183/134424

Em nosso mundo altamente conectado, novas tecnologias provêm contínuas mudanças na velocidade e eficiência das redes de telecomunicações e de transporte. Muitas dessas tecnologias são originárias de pesquisas em problemas de otimização em redes aplicadas a diferentes áreas. Nesta tese, investigamos três problemas de otimização combinatória que podem ser abordados como estruturas de redes. Primeiramente, são abordados problemas de engenharia de tráfego em redes de transporte. O objetivo principal é investigar os efeitos de alterar o custo de um subconjunto de arcos da rede, considerando que os clientes desta rede agem com um comportamento bem definido. O objetivo é controlar o fluxo na rede de modo a obter uma melhor distribuição do fluxo, minimizando o congestionamento ou maximizando o fluxo em um subconjunto de arestas. No primeiro problema considerase instalar um número fixo de postos de pedágios e definir os valores das tarifas para minimizar o tempo médio de viagem dos usuários. No segundo problema abordado, o objetivo é definir os valores das tarifas para maximizar a receita arrecadada nos arcos com pedágios. Em ambos os problemas, os usuários escolhem as rotas com base nos caminhos de menor custo da origem para o destino. Em redes de telecomunicações, um problema de alocação sujeito às condições da rede é considerado. O objetivo é alocar um conjunto de recursos, minimizando o custo de comunicação. Uma aplicação de computação em nuvem é considerada, onde os recursos são máquinas virtuais que devem ser alocadas em um conjunto de centros de dados. Condições da rede como largura de banda e latência são consideradas de modo a garantir a qualidade dos serviços. Para todos estes problemas, os modelos matemáticos são apresentados e avaliados usando um solver comercial de propósito geral como um método exato. Além disso, abordagens heurísticas são propostas, incluindo uma classe de algoritmo genético de chaves aleatórias viciadas (BRKGA). Resultados experimentais demonstram o bom desempenho das abordagens heurísticas propostas, mostrando que o BRKGA é uma ferramenta eficiente para resolver diferentes tipos de problemas de otimização combinatória, especialmente sobre estruturas de rede.