Orientador: Francisco de Assis Magalhães Gomes Neto / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-12T23:12:18Z (GMT). No. of bitstreams: 1 Vieira_HeloisaPassarelli_M.pdf: 1211437 bytes, checksum: 312aded4a440d526d723ab88a2a23588 (MD5) Previous issue date: 2008 / Resumo: Nos últimos anos, diversas heurísticas e meta-heurísticas foram propostas para o Problema de Roteamento de Veículos com Janela de Tempo (PRVJT), cujo objetivo é determinar a rota a ser seguida por uma frota de veículos para servir um número de clientes em um dado intervalo de tempo, sem violar a capacidade dos veículos. Cada cliente é visitado por exatamente um veículo e somente uma vez. Esta disertação apresenta um estudo das técnicas utilizadas para o PRVJT, dando ênfase para os Algoritmos Genéticos. Diversos tipos de cruzamento e esquemas de mutação, além de outras técnicas avançadas, tal como o Hill-Climbing, são analisados. Para o algoritmo que implementamos, são apresentados vários resultados numéricos baseados em um conjunto de 56 problemas, cada qual com 100 clientes, proposto por Solomon. O desempenho do algoritmo que implementamos também é comparado aos melhores resultados publicados na literatura / Abstract: In recent years, several heuristic and metaheuristic methods were proposed for the Vehicle Routing Problem with Time Windows (VRPTW). The objective of the problem is to serve a set of customers within a given time interval, without violating the capacity of the vehicles. Each customer must be visited once and by only one vehicle. This dissertation presents a survey on the techniques used to solve the VRPTW, with emphasis on the genetic algorithms. Several crossover and mutation schemes, as well as other advanced techniques, such as the Hill-Climbing are analyzed. Numerical results based on Solomon's 56 VRPTW 100-customer instances are presented for the algorithm implemented here. The performance of our algorithm is also compared with the best results published in the specialized literature / Mestrado / Pesquisa Operacional / Mestre em Matemática Aplicada

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

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.

Submitted by Filipe dos Santos (fsantos@pucsp.br) on 2018-10-19T11:51:51Z No. of bitstreams: 1 Rafael Emídio Murata Rodrigues.pdf: 1071545 bytes, checksum: 468e0f7e27e278e12eed0dd52f4198cc (MD5) / Made available in DSpace on 2018-10-19T11:51:51Z (GMT). No. of bitstreams: 1 Rafael Emídio Murata Rodrigues.pdf: 1071545 bytes, checksum: 468e0f7e27e278e12eed0dd52f4198cc (MD5) Previous issue date: 2018-08-30 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In our lives, we constantly move in streets and neighborhoods. In general, we consider time and (or distance) when planning the route. However, their solutions may face complex problems arising from the different possibilities of solutions. Similar to route planning, the Vehicle Routing Problem was introduced by George B. Dantzig and John H. Ramser in 1959 and consists of delivering gasoline to several fuel stations; at first a mathematical proposal, later became an algorithmic approach, for planning of routes of delivery of products in an optimized way (searching the "shortest path"). Although, during the search of shortest path, they are limited to the use of the streets. In this context emerges the Human Routing Problem, such an approach is not limited to streets, but makes use of all possible paths, by vehicles and humans. Such a problem can be observed in route planning at airports, museums and a supply chain company that wants to optimize the route of delivery of its products and increase customer satisfaction. Based on the Vehicle Routing Problem, the Human Routing Problem will be proposed. Its problematic will be demonstrated in a prototype, capable of assisting in the planning of human routes and three use cases. Ideas of Human Routing Problem had inspiration in the collective foraging insects / Na nossa vida, nos locomovemos constantemente em ruas e bairros. Em geral, consideramos o tempo e (ou a distância), ao planejar a rota. Contudo, suas soluções podem enfrentar problemas complexos, decorrentes das diversas possibilidades de soluções. Semelhante a planejamento de rotas, o Problema de Roteamento de Veículos foi introduzido por George B. Dantzig, e John H. Ramser em 1959 e consiste em entregar gasolina diversos postos de combustível; a princípio uma proposta matemática, mais tarde tornou-se uma abordagem algorítmica, para planejamento de rotas de entrega de produtos de forma otimizada (buscando o “menor caminho”). Embora, durante a busca de menor caminho, limitam-se ao uso de ruas. Neste contexto emerge o Problema de Roteamento Humano, tal abordagem não se limita a ruas, mas faz uso de todos os caminhos possíveis, por veículos e humanos. Tal problemática, pode ser observada nos planejamentos de rotas em aeroportos, museus e em uma empresa de supply chain que deseja otimizar a rota de entrega dos seus produtos, e aumentar a satisfação dos seus clientes. Tomando como base central, o Problema de Roteamento de Veículos será proposto o Problema de Roteamento Humano. Sua problemática, será demonstrado em um protótipo, capaz de auxiliar no planejamento de rotas humanas e três casos de uso. As ideias do Problema de Roteamento Humano tiveram inspiração no forrageamento dos insetos coletivos

Submitted by CARLA MARIA GOULART DE MORAES (carlagm) on 2015-04-01T18:43:13Z No. of bitstreams: 1 CristianoGalafassi.pdf: 2977122 bytes, checksum: 5d851dbaf2aea5f9599c6ce44fa55ba0 (MD5) / Made available in DSpace on 2015-04-01T18:43:13Z (GMT). No. of bitstreams: 1 CristianoGalafassi.pdf: 2977122 bytes, checksum: 5d851dbaf2aea5f9599c6ce44fa55ba0 (MD5) Previous issue date: 2011 / CNPQ – Conselho Nacional de Desenvolvimento Científico e Tecnológico / Este trabalho aborda o Problema de Roteamento de Veículos Capacitado com Janelas de Tempo, onde devem ser atendidas as restrições de capacidade do veículo e as janelas de tempo de atendimento do cliente. Para resolver tal problema serão utilizadas as metaheurísticas Busca Tabu e Algoritmos Genéticos, além do desenvolvimento de um Algoritmo Híbrido baseado nas duas metaheurísticas. Busca-se contribuir com o desenvolvimento de um Algoritmo Híbrido focado no Problema de Roteamento de Veículos que utilize o poder de intensificação da Busca Tabu e o poder de diversificação do Algoritmo Genético, objetivando a obtenção de soluções de boa qualidade sem comprometer o tempo computacional. Nos experimentos, no que tange a Busca Tabu, analisa-se o processo de busca da através da variação do tamanho da Lista Tabu e do número máximo de iterações sem melhora do valor da função objetivo, como critério de parada, aplicados a uma política de intensificação. Para o Algoritmo Genético, é analisada a influência e o comportamento da busca com base em três operadores de cruzamento aplicados a duas políticas de elitismo. Ainda assim, para o Algoritmo Híbrido, analisa-se o impacto do tamanho da Lista Tabu e das taxas de Mutação e Cruzamento. Por fim, os resultados obtidos são comparados com os melhores métodos heurísticos encontrados na literatura e com métodos exatos, onde o Algoritmo Híbrido mostra-se robusto, obtendo soluções ótimas para diversas instancias de problemas. / This paper approaches the Capacitated Vehicle Routing Problem with Time Windows, which must obey the restrictions on vehicle capacity and time windows for customer service. To solve this problem will be used two metaheuristics, Tabu Search and Genetic Algorithms, and are developed an hybrid algorithm based on this two metaheuristics. The aim is to contribute with the development of a Hybrid Algorithm focused on Vehicle Routing Problem that uses the Tabu Search intensification power and the Genetic Algorithms diversification power, in order to obtain good quality solutions without compromising the computational time. In the experiments, with respect to Tabu Search, we analyze the search process by varying the size of the Tabu List and the maximum number of iterations without improvement in objective function value, such as stopping criterion, applied to an intensification policy. For the genetic algorithm are analyzed the influence and the search behavior on the basis of three crossover operators, applied to two elitism policies. Still, for the hybrid algorithm, we analyze the impact of the Tabu List size and rates of mutation and crossover. Finally, the results are compared with the best heuristics in the literature and with exact methods, where the Hybrid Algorithm shows robust, getting several optimal solutions.

Orientador: Prof. Dr. Cláudio Nogueira de Meneses / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2016. / Beyond a complex real world system composed by a set of sophisticated machines and qualied human resources distributed around manufacturing environment, the Auto In- dustry needs a little more to allow their products to reach the nal costumers. Loading vehicles like cars, trucks and vans into auto-carriers and designing routes to delivery sub- sets of vehicles to auto dealers according to their orders are relevant tasks in automotive value chain performed by transportation companies. Given the set of complex constraints related to diferent vehicle models (with diferent dimensions) to be feasibly loaded into dierent auto-carrier models plus the auto-carrier eet routing task, transportation com- panies must explore strong computational alternatives to address this optimization prob- lem. In fact, we explore in this dissertation a real world complex problem composed by two sub-problems, both belonging to NP-hard class: routing and loading. After formally dening the tackled problem, we adopt, in this dissertation, a previously studied procedure based on enumeration techniques for loading task and we propose an alternative approach employing Asynchronous Teams concept, which combines local search algorithms in order to cooperate to each other to try to resolve the routing sub-problem. Setting the results provided by our implementation of Iterated Local Search (ILS) approach (already proposed in literature for solving the routing sub-problem) as benchmark, we propose computational experiments considering real-world instances, to compare performance of ILS to ve vari- ants of our Asynchronous Teams implementations. Final results evidence the power of this proposed alternative approach for founding quality solutions and its exibility to easily assume diferent configurations.