A content distribution network (CDN) is a system of computers networked together across the Internet that cooperate to deliver content to clients. It is an overlay network that maintains replicas of each content in its servers, with the goal of reducing delays, server load and network congestion, therefore improving the quality of the service provided. Due to server constraints and costs involved in the replication process, it is not reasonable, and many times not possible, to replicate the contents over the entire network. In this work, exact, heuristic and hybrid approaches are presented to solve a dynamic problem that appears in CDN management, known in the literature as Replica Placement and Request Distribution Problem. This problem consists of finding the best servers to place replicas and to handle requests so that the traffic cost in the network is minimized without violating server and clients' QoS constraints.

Este trabalho aborda o Problema de Roteamento de Veículos Periódico (PRVP), uma generalização do Problema de Roteamento de Veículos Clássico (PRV), em que um horizonte de planejamento de p períodos é considerado. O PRVP é definido como um grafo completo G = (N, A), com custos dos arcos conhecidos cij , ?(i, j) ? A; um período de planejamento de |P| períodos, indexado por p; um nó depósito, indexado por i = 0; um conjunto de nós clientes Nc = N \ {0}, onde cada nó i ? Nc tem uma demanda total qi para cada período do planejamento e requer um número fixo de visitas fi ; e um conjunto de K veículos, cada um com capacidade Q. Cada cliente i possui uma lista de opções por período (LOP), que representa em quais períodos o cliente pode estar simultaneamente, respeitando o fi . Caso o cliente esteja em períodos que não respeitem a LOP, esta solução é considerada inviável. Essa lista é um dado de entrada do problema. O objetivo do PRVP é minimizar a soma dos custos de transportes necessários para cada período p.

O problema de clusterização consiste em agrupar elementos em clusters, de forma a maximizar a similaridade entre os elementos de um mesmo cluster e minimizar a similaridade entre os elementos de outros clusters. Variações deste problema podem ser encontradas na literatura e quando um conjunto de elementos pode ser representado em um grafo, pode-se classicá-lo como problema de agrupamento de dados em grafo, podendo este problema ter outras nomenclaturas, tais como, problema de particionamento de grafos e problema de detecção de comunidades. Esta classe específica do problema consiste em encontrar clusters formados de vértices em um grafo que apresentem alta conectividade entre os nós. Nesta tese está sendo proposto a implementação da metaheuristica Iterated Local Search utilizando-se do paradigma multilevel para soluções deste tipo de problema. Este pararadigma é composto de três fases, contração, particionamento inicial e refinamento. Serão utilizados algoritmos de contração e refinamento em conjunto com a metaheuristica ILS para obter boas soluções em grafos já existentes e utilizados em outros trabalhos, com isso, podendo-se comparar os resultados que serão alcançados.

This work addresses the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD). This problem is of great importance in the field of reverse logistics and it has several applications including the planning of the distribution of the drinks industry and the postal logistics. The VRPSPD is NP-hard, since it can be reduced to the classical Vehicle Routing Problem when no client needs the pickup service. To solve it, we propose a hybrid heuristic algorithm, called GENILS, based on Iterated Local Search, Variable Neighborhood Descent, Cheapest Insertion and GENIUS. The proposed algorithm was tested on three well-known sets of instances found in literature and it was competitive with the best existing approaches. For the 72 instances tested, the GENILS was able to reach 49 best results of literature and was able to improve 9 best known solutions.

One important problem in computational biology is the determination of the threedimensional structure of proteins. Some information about the protein can be caught by the Nuclear magnetic resonance (NMR), but this technique provides only a sparse set of distances between atoms in a molecule. In this case, the problem is to determine the three-dimensional structure of a molecule using a set of distances between some atoms. In the literature, this problem is known as the Molecular Distance Geometry Problem which is generally expressed as a problem of continuous optimization. However, conditions for dealing with it as a combinatorial optimization problem using a discrete formulation were presented recently. In this dissertation, an approach for determine the whole protein structure, including the ramifications of the backbone. Three algorithms are proposed, one that deals only with the backbone and other two that consider the whole protein. In order to test the algorithms were used real and artificial instances and were obtained good results in relation to methods presented in the literature.