Heuristic approaches for network problems

Abstract

In our highly connected world, new technologies provide continuous changes in the speed and efficiency of telecommunication and transportation networks. Many of these technologies come from research on network optimization problems with applications in different areas. In this thesis, we investigate three combinatorial optimization problems that arise from optimization on networks. First, traffic engineering problems in transportation networks are addressed. The main objective is to investigate the effects of changing the cost of some links in the network regarding some well-defined user behavior. The goal is to control the flow in the network and seek a better flow distribution over the network and then minimize the traffic congestion or maximize the flow on a subset of links over network conditions. The first problem considered is to install a fixed number of tollbooths and define the values of tariffs to minimize the average user travel time. The second problem considered is to define the values of tariffs to maximize the revenue collected in the tolled arcs. In both problems, users choose the routes based on the least cost paths from source to destination. From telecommunication networks, a placement problem subjected to network conditions is considered. The main objective is to place a set of resources minimizing the communication cost. An application from cloud computing is considered, where the resources are virtual machines that should be placed in a set of data centers. Network conditions, such as bandwidth and latency, are considered in order to ensure the service quality. For all these problems, mathematical models are presented and evaluated using a general-purpose commercial solver as an exact method. Furthermore, new heuristics approaches are proposed, including some based on biased random-key genetic algorithm (BRKGA). Experimental results demonstrate the good performance of the proposed heuristic approaches, showing that BRKGA is an efficient tool for solving different kinds of combinatorial optimization problems, especially over network structures.

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.