Orientador: Cid Carvalho de Souza / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-15T11:41:44Z (GMT). No. of bitstreams: 1 Hoshino_EdnaAyako_D.pdf: 1434503 bytes, checksum: c1b32d8a6dc810d6d7ff6100d1a77c79 (MD5) Previous issue date: 2009 / Resumo: Nesta tese,dois problemas de otimização combinatória em grafos são modelados por programação linear inteira e resolvidos através de técnicas de geração de colunas. Os dois casos correspondem a generalizações de problemas clássicos em grafos e que ocorrem em muitas situações práticas. O primeiro, chamado problema dos anéis-estrelas capacitados, é uma generalização do problema de roteamento de veículos e modela situações reais encontradas nas áreas de logística de distribuição e de transporte. O segundo, conhecido por problema da coloração particionada, generaliza o problema da coloração de vértices em grafos e ocorre em aplicações no projeto de redes ópticas. As formulações de programação linear inteira desenvolvidas neste trabalho para modelar ambos os problemas estão relacionadas 'a técnica da decomposição de Dantzig-Wolfe e usam uma quantidade exponencialmente grande de variáveis de decisão . Nestas formulações, cada uma das variáveis representa uma estrutura específica do problema sendo estudado. No problema dos anéis-estrelas capacitados, cada variável está associada a um anel-estrela e, no problema da coloração particionada, a um conjunto independente. As relaxações lineares destes tipos de modelos, em geral, apresentam limitantes duais mais apertados que outros modelos compactos, isto é, definidos para um número polinomial de variáveis. Nesta tese, nós avaliamos estas novas formulações, comparando-as com outros modelos conhecidos para os problemas estudados. Além disso, nos dois casos, projetamos e implementamos algoritmos exatos do tipo branch-and-price e/ou branch-and-cut-and-price capazes de computar os modelos propostos. Experimentos computacionais foram realizados com estes algoritmos que confirmaram a adequação das técnicas aqui empregadas. Tanto para o problema dos anéis-estrelas capacitados quanto para o problema da coloração particionada, os resultados alcançados por nós foram comparados com aqueles reportados na literatura e mostraram que os algoritmos baseados em geração de colunas tiveram desempenho melhor que os algoritmos propostos anteriormente / Abstract: In this thesis, two combinatorial optimization problems are modeled by integer linear programming and solved using the column generation technique. Both cases correspond to generalizations of classical problems in graphs that occur in many practical situations. The first, called capacitated ring-star problem is a generalization of the vehicle routing problem and models real situations found in logistics and transportation. The second, known as the partition coloring problem, generalizes the vertex coloring problem in graphs and arises in design of fiber optics networks. The integer linear programming formulations developed in this work to model both problems are related to the Dantzing-Wolfe decomposition and use exponential number of decision variables. In these formulations, each decision variable represents a specific structure of the problem under study. For the capacitated ring-star problem, each variable is assigned to a ring-star and, for the partition coloring problem, to an independent set. The linear relaxation of this kind of model in general leads to tighter dual bounds than the ones obtained from compact models, i.e., defined over a polynomial number of variables. In this thesis, we evaluated both new formulations, comparing them to other known models for the respective problems. Moreover, in both cases, we designed and implemented exact branch-and-price and/or branch-and-cut-and-price algorithms that are able to solve the proposed models. Computational experiments were performed with these algorithms and showed that the used techniques were adequate. Both for the capacitated ring-star problem and for the partition coloring problem, we compared our results with those reported in the literature and showed that the algorithms based on column generation outperformed the previous ones / Doutorado / Otimização Combinatoria / Doutor em Ciência da Computação

Orientadores: Antonio Carlos Moretti, Margarida Pinheiro Mello / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-11T15:01:14Z (GMT). No. of bitstreams: 1 Oliveira_WashingtonAlvesde_M.pdf: 1986709 bytes, checksum: fa0dfb8c33d0fe5dd13eeced37d3b4ee (MD5) Previous issue date: 2008 / Resumo: Nesta dissertação estudamos um aspecto do problema de planejamento do pratulhamento urbano preventivo: a construção de rotas a serem percorridas pelos veículos da força policial no patrulhamento preventivo. De modo geral, a elaboração de rotas visa garantir uma boa visibilidade para o patrulhamento, de modo a proporcionar sensação de segurança para a população, permitir o atendimento rápido em caso de ocorrências, fazer vigilância de determinados estabelecimentos (hospitais, escolas, etc.). O planejamento deve levar em conta os recursos disponíveis, normalmente o número de veículos, visar agilidade e uma distribuição equânime de trabalho. O produto final é um módulo computacional capaz de automaticamente gerar rotas atendendo um dado conjunto de especificações, que possa ser utilizado pelos departamentos responsáveis pela segurança pública. Para tanto, fizemos uma adaptação do modelo para o Problema de Rotas de Cobertura multi-veículo (m-PRC). Este modelo consiste em um programa linear inteiro cujo tamanho e complexidade torna inviável a aplicação de métodos exatos para sua solução. Soluções subótimas são obtidas aplicando-se as heurísticas propostas por M. Hachicha et. al. (2000), e outras contribuídas por nós. Neste modelo alguns pontos geográficos devem ser obrigatoriamente visitados, enquanto outros devem ficar suficientemente próximos das rotas traçadas. Procuramos gerar rotas de tamanho menor possível, para que cada circuito seja percorrido um maior número de vezes durante o turno de serviço. As heurísticas foram implementadas em MATLAB e sua validação, assim como a do modelo, foi feita através da resolução de problemas gerados aleatoriamente. Além disso, obtivemos dados relativos à cidade de Vinhedo, S.P., e formulamos rotas para patrulhamento preventivo pela Guarda Civil Municipal. Os resultados são promissores, e a análise das soluções obtidas será utilizada para aprimorar o modelo / Abstract: In this text we study one aspect of the urban community policing: routine patrol route planning. We seek routes that guarantee visibility, as this has a sizable impact on the community's perceived safety and allows for quick emergency responses, and that provide surveillance of public buildings (e.g., hospitals, schools). The planning is restricted to the availability of vehides and strives to achieve balanced and short routes. We construct a computerized module, capable of automatic generation of routes for a given vehide fieet and lists of sites that must be visited. Such a module could be of interest to Police, Public Safety Departments, Municipal Service Agencies. The module implements an adaptation of the model for the multi-vehicle covering tour problem. It constitutes an integer program whose size and complexity makes the use of an exact method impractical. Suboptimal solutions are obtained with several heuristics, some by M. Hachicha et. al. (2000), and others of our own devising. In this model a set of locations must be visited, whereas another subset must be close enough to the planned routes. The heuristics aim to construct short routes so that one could make several rounds during a work shift. The implementation was done in MATLAB and its validation, as well as the model's, was based on the solution of randomly generated problems. Furthermore, data from the city of Vinhedo, SP, was obtained and tentative routes planned for the patroling of a choice of locations by the Municipal Guard. Their appraisal by the personnel in charge of the route planning will, without a doubt, help us improve the model and heuristics / Mestrado / Pesquisa Operacional / Mestre em Matemática Aplicada

Orientador: Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T12:28:53Z (GMT). No. of bitstreams: 1 Lopes_MauroCardoso_M.pdf: 3797752 bytes, checksum: c82bee131ad99d747e42150908135190 (MD5) Previous issue date: 2014 / Resumo: Investigamos uma variante do problema de localização e roteamento com relação de muitos-para-muitos concentradores que consiste em particionar o conjunto de vértices de um grafo em ciclos contendo exatamente um concentrador cada e determinar um ciclo adicional interligando todos os concentradores. Qualquer vértice do grafo pode ser um concentrador; faz parte do problema determinar quais vértices devem ser concentradores. Esse problema tem aplicações práticas relevantes em áreas como transporte urbano e redes de computadores. Desenvolvemos uma heurística baseada em busca local com operações de inserção, remoção e troca de vértices. Soluções iniciais são geradas de maneira aleatória, e suas vizinhanças são exploradas a fim de obter melhores soluções. Além disso, elaboramos um algoritmo exato com estrutura de branch-and-cut para a formulação em Programação Linear Inteira proposta. Restrições de capacidade e eliminação de caminhos são adicionadas como planos de corte, com algoritmos de separação baseados em árvores de corte mínimo e nas componentes conexas de um grafo suporte. Diversos experimentos computacionais mostram a capacidade de resolução do algoritmo exato para instâncias pequenas e da heurística para instâncias pequenas e médias. São comparados também os desempenhos para outras variantes do problema / Abstract: We investigate a variant of the many-to-many hub location-routing problem which consists in partitioning the set of vertices of a graph into cycles containing exactly one hub each and determining an extra cycle interconnecting all hubs. Any vertex of the graph can be a hub; it is part of the problem to determine which vertices should be hubs. This problem has relevant practical applications in areas such as urban transportation and computer networks. A local search based heuristic that considers add/remove and swap operations is developed. Initial solutions can be generated at random, and their neighborhoods are explored in order to get better solutions. Also a branch-and-cut approach that solves an integer formulation is investigated. Capacity and path elimination constraints are added in a cutting plane way, so the separation algorithms are based on the computation of min-cut trees and in the connected components of a support graph. Many computational experiments over several instances adapted from literature show the problem-solving capability of the exact algorithm for small instances and of the heuristic for small to medium-sized instances. We also compare the performance of other variants of the problem / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Fernando José Von Zuben / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-25T22:55:48Z (GMT). No. of bitstreams: 1 Raimundo_MarcosMedeiros_M.pdf: 764820 bytes, checksum: 80ad4c20c482ad09b06c3e07d1b2c240 (MD5) Previous issue date: 2014 / Resumo: O gerenciamento de cadeias de suprimento no mundo corporativo é de grande relevância prática e uma de suas versões é conhecida como problema de roteamento e estoque. Este trabalho propõe uma formulação linear-inteira genérica e flexível para este problema de otimização, assim como uma metodologia de solução. Nesta nova formulação proposta, algumas peculiaridades da rede de suprimentos podem ser especificadas como parâmetros de entrada, permitindo assim que o usuário seja capaz de realizar modificações na estrutura, na hierarquia e no elenco de restrições da cadeia de suprimentos, sem precisar refazer a formulação matemática associada. Com isso, é possível resolver uma grande diversidade de configurações do problema, sem a necessidade de adaptações junto à metodologia de solução. A natureza genérica e flexível da formulação linear-inteira se deve às seguintes propriedades, todas elas passíveis de serem definidas como parâmetros de entrada: (1) Todo nó da rede pode produzir ou consumir produtos; (2) Todo nó da rede pode enviar e receber produtos; (3) Decorrente das propriedades (1) e (2), a hierarquia de entrega fica generalizada, com o produto podendo passar por vários nós antes de ser consumido; (4) Restrições presentes na formulação garantem consistência, por exemplo, entre quantidade de produto entregue pelos fornecedores e recebida pelos consumidores; (5) Restrições presentes na formulação estão associadas a especificações que podem ser ativadas, como intervalo de tempo entre entregas. Os resultados experimentais contemplam soluções para múltiplas configurações do problema, todas representáveis pela formulação proposta e, portanto, todas resolvidas pela mesma metodologia de solução. Essas múltiplas configurações trabalhadas nos experimentos evidenciam os benefícios do emprego de uma formulação estendida para o problema de roteamento e estoque. Além disso, visando comparação com propostas alternativas disponíveis na literatura, tomou-se uma configuração específica e bem-estabelecida do problema, para a qual existe uma formulação própria e uma metodologia de solução dedicada. Neste experimento comparativo, chegou-se às mesmas soluções e, em algumas parametrizações, até a soluções de melhor qualidade / Abstract: Managing supply chains in the corporate world is of great practical relevance and one of its versions is named inventory routing problem. This work proposes a more generic and flexible linear-integer formulation for this optimization problem, together with a solution methodology. In the novel formulation proposed here, some peculiarities of the supply network can be specified as input parameters, thus allowing the user to make modifications to the structure, the hierarchy and the set of constraints in the supply chain, without having to rebuild the associated mathematical formulation. Therefore, it is possible to solve a wide variety of configurations of the problem without the need for adjustments in the solution methodology. The generic and flexible nature of the linear-integer formulation is due to the following properties, all of them being definable as input parameters: (1) Every node of the network can produce or consume products; (2) Every node of the network can send and receive products; (3) Due to properties (1) and (2), the hierarchy of delivery is generalized, with the product being able to pass through several nodes before being consumed; (4) Some restrictions of the formulation ensure consistency, for example, between the amount of product delivered by the suppliers and received by the consumers; (5) Some restrictions of the formulation are associated with specifications that can be activated, as the time interval between deliveries. The experimental results include solutions for multiple configurations of the problem, all representable by the proposed formulation and, as a consequence, all able to be solved by the same solution methodology. Those multiple configurations considered in the experiments highlight the benefits of employing an extended formulation for the inventory routing problem. Aiming at comparing to alternative proposals available in the literature, it was considered a specific and well-established configuration of the problem, for which there are a proper formulation and a dedicated solution methodology. In this comparative experiment, we came to the same solutions and, in some parameterizations, even better solutions / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

Orientador: Eduardo Candido Xavier / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-24T00:15:42Z (GMT). No. of bitstreams: 1 Silveira_JeffersonLuizMoisesda_D.pdf: 2236708 bytes, checksum: 8e569408c2f068347058e36031689c3a (MD5) Previous issue date: 2013 / Resumo: Neste trabalho estamos interessados em problemas de empacotamento e roteamento. Assumindo a hipótese de que P ? NP, sabemos que não existem algoritmos eficientes para resolver tais problemas. Além de algoritmos exatos, duas das abordagens para resolver tais problemas são Algoritmos Aproximados e Heurísticas. Nesta tese mostramos algoritmos baseados nestas três abordagens para ambos os problemas, de empacotamento e roteamento. Os dois primeiros problemas atacados foram generalizações de problemas clássicos de empacotamento: O problema da mochila bidimensional e o problema de empacotamento em faixas. Estes foram generalizados adicionando restrições na forma de carregamento e descarregamento dos itens no recipiente (restrições estas, que aparecem no contexto de problemas de roteamento). O terceiro problema é uma combinação de problemas de empacotamento e roteamento. Neste caso, atacamos uma generalização do clássico Pickup and Delivery Problem. Propomos os primeiros resultados de aproximação para algumas versões dos problemas de empacotamento supracitados. Além disto, apresentamos algumas abordagens práticas para o terceiro problema. As heurísticas foram avaliadas através de experimentos computacionais comparando os seus resultados com algoritmos exatos / Abstract: In this work we are interested in packing and routing problems. Assuming P ? NP, we have that there are no efficient algorithms to deal with such problems. Besides exact algorithms, two approaches to solve such problems are Approximation Algorithms and Heuristics. In this thesis we show algorithms using these three approaches for both packing and routing problems. The first two addressed problems are generalizations of classical packing problems: The Two Dimensional Knapsack problem and the Strip Packing problem. These problems were generalized by adding constraints on the way the items can be inserted/removed into/from the bin (These constraints appear in the context of routing problems). The third problem is combination of packing and routing problems. It is a generalization of the classical Pickup and Delivery problem. We propose the first approximation results for some packing problems. Besides that, we present some practical algorithms for the third problem. The heuristics were assessed through computational experiments by comparing their results with exact algorithms / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

Submitted by Nadir Basilio (nadirsb@uninove.br) on 2015-07-17T16:00:19Z No. of bitstreams: 1 Stanley Jefferson de Araujo Lima.pdf: 1500605 bytes, checksum: 2aec7d5c11c9781ce7f70eb2019c01f4 (MD5) / Made available in DSpace on 2015-07-17T16:00:19Z (GMT). No. of bitstreams: 1 Stanley Jefferson de Araujo Lima.pdf: 1500605 bytes, checksum: 2aec7d5c11c9781ce7f70eb2019c01f4 (MD5) Previous issue date: 2015-01-27 / In recent years, the Vehicle Routing Problem (VRP) has attracted an increasing attention from researchers due to the great difficulty of its solution and its presence in various practical situations. As consequence, there has been great effort to develop more robust, agile and flexible algorithms that can be modeled according to the scenario that describes the problem. The Capacitated Vehicle Routing Problem (CVRP) is a version of VRP and consists in determining a set of routes to be followed by a fleet of homogeneous vehicles, which must serve a set of customers. The objective is to minimize the total cost of the routes subject to the following restrictions: i) routes must start and end in the same distribution center; ii) each customer must be visited once and its demand must be met in full by only one vehicle and iii) the sum of customers' demands included in a route cannot exceed the vehicle capacity. The CVRP belongs to the class of NP-hard problems, that is, problems whose the solution usually requires non-polynomial complexity time algorithms and because of this are usually resolved with the use of heuristic and metaheuristics algorithms. In this work, it was investigated the optimization of CVRP using Genetic Algorithm (GA) with alternative chromosome representations and heuristics. To this end, three strategies, each one employing a different model of chromosome representation for encoding solution in AG were proposed. In addition, the heuristics of Gillett and Miller to generate solutions that are included in the initial population of GA and Hill-climbing for refinement of GA solutions, after a number of generations without improvement, were adopted. In the performed experiments, the results obtained by the proposed strategies were compared with each other and also with the best results found in the literature for a set of known instances. These experiments showed that the proposed strategies provided good results with respect to quality of solutions well as the computational cost. In addition, it was possible to evaluate the viability of each employed chromosome representation and the contribution of the heuristics in the convergence process of GA. / Nos últimos anos o Problema de Roteamento de Veículos (PRV) tem atraído cada vez mais a atenção de pesquisadores devido à grande dificuldade de solução e sua presença em várias situações do cotidiano. Em decorrência disso, tem havido um grande esforço para desenvolver algoritmos cada vez mais robustos, ágeis e flexíveis e que possam ser modelados com base no cenário que descreve o problema. O Problema de Roteamento de Veículos Capacitado (PRVC) é uma versão do PRV e consiste em encontrar um conjunto de rotas a serem seguidas por uma frota de veículos homogêneos, os quais devem atender a um conjunto de clientes. O objetivo é minimizar o custo total das rotas respeitando as seguintes restrições: i) as rotas devem iniciar e terminar no mesmo centro de distribuição; ii) cada cliente deve ser visitado uma única vez e sua demanda deve ser atendida integralmente por apenas um veículo e iii) a soma das demandas dos clientes incluídos em uma rota não pode exceder a capacidade do veículo. Problemas desta natureza podem ser classificados como NP-Hard, ou seja, possuem ordem de complexidade não polinomial e normalmente são resolvidos com uso de algoritmos heurísticos e meta-heurísticos. Neste trabalho investigou-se a otimização do PRVC usando Algoritmo Genético (AG) com representações cromossômicas e heurísticas alternativas. Para tanto, foram propostas três estratégias, cada uma delas empregando um modelo diferente de representação cromossômica para codificação da solução no AG. Além disso, foram empregadas as heurísticas de Gillett e Miller para gerar soluções que são incluídas na população inicial do AG e Subida/Descida de Encosta para refinamento das soluções, após um certo número de gerações sem melhoria. Nos experimentos realizados, os resultados obtidos pelas estratégias propostas foram comparados entre si e também com os melhores resultados encontrados na literatura para um conjunto de instâncias conhecidas. Pode-se constatar, a partir desses experimentos, que as estratégias apresentaram bons resultados tanto no que tange a qualidade das soluções quanto ao tempo computacional dispendido. Em adição, foi possível avaliar a viabilidade de cada uma das representações cromossômicas empregadas, além da contribuição das heurísticas no processo de convergência do ag.

Submitted by Nadir Basilio (nadirsb@uninove.br) on 2017-08-04T21:26:50Z No. of bitstreams: 1 Renato Alessandro Rocha Santos.PDF: 5054326 bytes, checksum: 739f1115bab9b157f48eb56ca44d4c34 (MD5) / Made available in DSpace on 2017-08-04T21:26:50Z (GMT). No. of bitstreams: 1 Renato Alessandro Rocha Santos.PDF: 5054326 bytes, checksum: 739f1115bab9b157f48eb56ca44d4c34 (MD5) Previous issue date: 2017-03-02 / Over the last decades the Vehicle Routing Problem (VRP) has been subject of research of several authors, mainly because of difficulties found in its optimization as well as its application in real-world situations. In the scientific literature there are several proposed solutions for the PRV using different optimization techniques. However, such solutions are rarely transformed into software tools that can be used by end users, for example, micro enterprises. Thus, the focus of the present work was to develop a Web computational tool for vehicle routing, called “SGRV  Sistema de Gestão de Roteamento de Veículos”, which uses Google Maps features and aims to meet the needs of micro enterprises. Therefore, initially it was conducted a literature search about solution methods for VRP, to support the choice of strategy based on genetic algorithms employed in SGRV. Then, a new bibliographic research was made with the purpose of finding free softwares for the VRP solution, which were object of analysis to mark out the development of the SGRV. For the development of this research was used the methodology Design Science Research. A qualitative evaluation of the SGRV was carried out by four microenterprises from different branches, that used the tool for a certain period and, in the end, answered six questions opened from semi-structured interviews. The experiences of these microenterprises were transcribed and the data obtained reveal the effectiveness of the SGRV in the management of its tasks related to the orders and deliveries of products. / Nas últimas décadas o Problema de Roteamento de Veículos (PRV) tem sido temática de pesquisas de diversos autores, principalmente por causa de dificuldades encontradas para sua resolução, bem como sua aplicabilidade em situações reais do cotidiano. Na literatura científica há diversas propostas de soluções para o PRV empregando diferentes técnicas de otimização. No entanto, tais soluções raramente são transformadas em ferramentas computacionais que possam ser utilizadas por usuários finais como, por exemplo, as microempresas. Assim, o foco do presente trabalho foi desenvolver uma ferramenta computacional Web para roteamento de veículos, denominada SGRV  Sistema de Gestão de Roteamento de Veículos, que emprega recursos do Google Maps e visa suprir as necessidades de microempresas. Para tanto, inicialmente realizou-se uma pesquisa bibliográfica acerca de métodos de solução para o PRV, a fim de subsidiar a escolha de uma estratégia baseada em Algoritmos Genéticos empregada no SGRV. Em seguida, foi feito um novo levantamento bibliográfico com intuito de encontrar softwares de uso livre para a solução do PRV, os quais foram objeto de uma análise que visou balizar a implementação do SGRV. Para o desenvolvimento dessa pesquisa foi empregada a metodologia Design Science Research. Uma avaliação qualitativa do SGRV foi realizada por quatro microempresas de diferentes ramos, as quais utilizaram a ferramenta por um determinado período e, ao final, responderam seis questões abertas a partir de entrevistas semiestruturadas. As experiências dessas microempresas foram transcritas e os dados obtidos revelam a efetividade do SGRV no gerenciamento de suas tarefas relacionadas aos pedidos e entregas de produtos.

Uma hiper-heurística é uma heurística que pode ser utilizada para lidar com qualquer problema de otimização, desde que a ela sejam fornecidos alguns parâmetros, como estruturas e abstrações, relacionados ao problema considerado. As hiper-heurísticas têm sido aplicadas a alguns problemas práticos e apresentadas como métodos de grande potencial, no que diz respeito à capacidade de possibilitar o desenvolvimento, em tempo bastante reduzido, de algoritmos capazes de lidar satisfatoriamente, do ponto de vista prático, com problemas de otimização complexos e pouco conhecidos. No entanto, é difícil situar as hiper-heurísticas em algum nível de qualidade e avaliar a robustez dessas abordagens caso não as apliquemos a problemas para os quais existam diversas instâncias disponíveis publicamente e já experimentadas por algoritmos relevantes. Este trabalho procura dar alguns passos importantes rumo a essas avaliações, além de ampliar o conjunto das hiper-heurísticas, compreender o impacto de algumas alternativas naturais de desenvolvimento e estabelecer comparações entre os resultados obtidos por diferentes métodos, o que ainda nos permite confrontar as duas diferentes classes de hiper-heurísticas que identificamos. Com essas finalidades em mente, desenvolvemos 3 novas hiper-heurísticas e implementamos 2 das hiper-heurísticas mais importantes criadas por outros autores. Para estas últimas, experimentamos ainda algumas extensões e modificações. Os dois métodos hiper-heurísticos selecionados podem ser vistos como respectivos representantes de duas classes distintas, que aparentemente englobam todas as hiper-heurísticas já desenvolvidas e nos permitem denominar cada um desses métodos como \"hiper-heurística de busca direta por entornos\" ou como \"hiper-heurística evolutiva indireta\". Implementamos cada hiper-heurística como uma biblioteca (em linguagem C), de forma a evidenciar e estimular a independência entre o nível em que se encontra a hiper-heurística e aquele onde se apresentam as estruturas e abstrações diretamente relacionadas ao problema considerado. Naturalmente, essa separação é de ingente importância para possibilitar a reutilização imediata das hiper-heurísticas e garantir que nelas haja total ausência de informações relativas a um problema de otimização específico. / A hyperheuristic is a heuristic that can be used to handle any optimization problem, provided that the algorithm is fed with some parameters, as structures and abstractions, related to the problem at hand. Hyperheuristics have been applied to some practical problems and presented as methods with great potential to allow the quick development of algorithms that are able to successfully deal, from a practical standpoint, with complex ill-known optimization problems. However, it\'s difficult to position hyperheuristics at some quality level and evaluate their robustness without applying them to problems for which there are many instances available in the public domain and already attacked by worthy algorithms. This work aims to give some important steps towards that process of evaluation, additionally increasing the number of available hyperheuristics, studying the impact of some natural development alternatives and comparing the results obtained by different methods, what also enables us to confront the two classes of hyperheuristics that we have identified. With those purposes in mind, we have developed 3 original hyperheuristics and implemented 2 of the most important hyperheuristics created by other authors. For those latter two approaches, we have also experimented with some modifications and extensions. The two methods we have chosen for implementation may be seen as respectively representing two distinct classes, which seem to contain all hyperheuristics developed so far and that allow us to classify any of these methods as either being a \"direct neighbourhood search hyperheuristic\" or an \"indirect evolutive hyperheuristic\". We have implemented each hyperheuristic as a library (in the C language), so as to clearly show and estimulate the independence between the level where the hyperheuristic is and that to which the structures and abstractions directly related to the problem at hand belong. Obviously, this separation of concerns is extremely important to make the immediate reuse of hyperheuristics possible and enforce in them the complete absence of information from a specific optimization problem.

In this Dissertation, the Vehicle Routing Problem with Drones (VRPD), motivated by the growing interest on Unmanned Aerial Vehicles (UAVs, or Drones) by the industry and their applications in logistics is studied. A pioneer work by (MURRAY; CHU, 2015) shows a combination between UAV and a truck to deliver products, presenting an adaptation to the Traveling Salesman Problem (TSP). After a literature review, an extension of the model from Murray and Chu (2015) we present a model for the problem with multiple vehicles. This model is developed as a Mixed Integer Linear Programming (MILP) problem and solved with the solver CPLEX. A heuristic based on a Hybrid Genetic Algorithm (HGA) is also developed and presented. Our results show that the use of drones reduces the total mileage of the trucks by a significant percentage. / Nessa monografia estuda-se o Problema do Roteamento de Veículos com Drones (PRVD), motivado pelo crescente interesse da indústria em Veículos Aéreos Não Tripulados (VANTs) e suas aplicações em logística. O trabalho pioneiro de (MURRAY; CHU, 2015) mostra uma combinação entre VANT e um caminhão para realização de entregas de produtos, no qual foi proposta uma adaptação do Problema do Caixeiro Viajante (PCV). Após uma revisão de literatura, apresenta-se uma extensão do modelo de Murray and Chu (2015) para o problema com múltiplos veículos. Desenvolveu-se um modelo de Programação Linear Inteira Mista que foi resolvido com o solver CPLEX. Uma heurística basead em um Algoritmo Genético Híbrido também foi desenvolvido e é apresentada. Resultados mostram que a utilização dos VANTs reduzem a quilometragem dos caminhões significativamente.

Este trabalho apresenta um estudo teórico da Técnica de Geração de Colunas (GC) aplicada em alguns Problemas de Roteamento de Veículo (PRV). Essa técnica foi inicialmente utilizada para tratar problemas de otimização de grande porte com estruturas especiais[Dantzig & Wolfe, 1960]. Dentre as diversas classes de problemas de roteamento; revisamos a aplicação dessa técnica a dois casos particulares: O problema de roteamento de helicópteros em plataformas marítimas, cujo objetivo minimizar o custo total do transporte; O problema de roteamento com janela de tempo, onde a função objetivo é descrita pelo tamanho da frota e o custo do percurso. Revisamos e implementamos um algoritmo de caminho mínimo com janela de tempo (CMJT). Esse algoritmo surge como um sub-problema do algoritmo Primai Simplex para resolver o problema de partição de conjunto, utilizado para modelar o problema de roteamento com janela de tempo. / This work presents a study about the Column Generation Technique (CG) applied to some Vehicle Ftouting Problems. The technique was first used to deal with optimization problems having special structures. Among the vaa-ious classes of routing problems, we review the use of the technique in two specific cases: Ftouting helicopters for crew exchanges on off-shore locations, where the objective is to minimize the total transportation cost; Ftouting with time windows, where the objective function is composed by the size of the fleet and the cost of route. We review and implement a shortest path algorithm with time windows. This algorithm aa-ises as a sub-problem in the Primai Simplex algorithm to solve the linear relaxation of the set partitioning problem used to model the routing problem with time windows.