The work proposed in this dissertation is the field of combinatorial optimization, which aims to find a solution to these types of problems at a low computational time and effectively. The combinatorial optimization studies a set of discrete solutions, which have a finite number of elements, to find the best viable solution to the problems of this magnitude. One of the main approaches that area is the Traveling Salesman Problem (TSP), mainly due to the size of possible solutions to the problem, so that is intractable computation by exhaustive search methods. Given all these features, this work is to study and develop evolutionary strategies for the resolution of the Problem of Traveling Salesman with Heterogeneous Demands (TSPHD), a variation of the classic TSP. The evolutionary strategies belong to the class of evolutionary computation, and methods of search based on the theory of the evolution of species, where the best individuals compete for survival. The evolutionary strategies differ from other optimization techniques, as the search is conducted in a population of solutions, not a single point. To solve the problem are proposed four evolutionary algorithms, using heuristics techniques and metaheurísticas for its implementation. The results were obtained from tests using instances of low density (low connection), and compared with the exact solution (optimal solution) and other progressive methods in the literature. These results are evaluated on the basis of their quality and time for its implementation. / O trabalho proposto nessa dissertação pertence à área de otimização combinatória, a qual visa encontrar uma solução para esses tipos de problema em um tempo computacional baixo e de forma eficaz. A otimização combinatória estuda um conjunto discreto de soluções, os quais possuem um número finito de elementos, para se poder encontrar a melhor solução viável para os problemas dessa grandeza. Uma das principais abordagens dessa área é o Problema do Caixeiro Viajante (PCV), principalmente devido à dimensão de possíveis soluções para o problema, fazendo com que seja intratável computacionalmente por métodos de buscas exaustivas. Face a todas essas características, este trabalho tem por objetivo estudar e desenvolver estratégias evolutivas para a resolução do Problema do Caixeiro Viajante com Demandas Heterogêneas (PCVDH), uma variação do PCV clássico. As estratégias evolutivas pertencem à classe da computação evolutiva, sendo métodos de busca inspirados na teoria da evolução das espécies, onde os melhores indivíduos competem pela sobrevivência. As estratégias evolutivas diferem das demais técnicas de otimização, pois a busca é realizada em uma população de soluções, não em um único ponto. Para a resolução do problema são propostos quatro algoritmos evolutivos, utilizando técnicas heurísticas e metaheurísticas para sua aplicação. Os resultados foram obtidos com testes utilizando instâncias de baixa densidade (baixa conexão), e comparados com a sua solução exata (solução ótima) e com outros métodos evolutivos encontrados na literatura. Esses resultados são avaliados com base na sua qualidade e tempo decorrido para sua execução.

Made available in DSpace on 2014-06-11T19:22:32Z (GMT). No. of bitstreams: 0 Previous issue date: 2009-02-18Bitstream added on 2014-06-13T18:49:30Z : No. of bitstreams: 1 biscaro_aap_me_ilha.pdf: 1057545 bytes, checksum: feb928c10ad58cb9fc7bef33003e6afc (MD5) / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / Neste trabalho é proposta uma técnica de otimização para alocar medidores dispersos de tensão em alimentadores radiais aéreos de distribuição baseada na metaheurística Greedy Randomized Adaptive Search Procedure (GRASP), com o objetivo de melhorar o desempenho de algoritmos de localização de faltas que utilizam informações esparsas de tensão e, simultaneamente, fazer o controle em tempo real do nível de tensão do alimentador operando sob diferentes cenários. No modelo de programação proposto para alocar os medidores considera-se a natureza estocástica das variáveis envolvidas no problema relacionado com o estudo de contingências em sistemas de energia elétrica, ou seja: carregamento dos transformadores da rede no instante de ocorrência da falta, impedância de falta, probabilidade de falhas e erros de medição dos medidores dispersos de tensão, probabilidade de ocorrer qualquer um dos tipos de faltas possíveis, entre outros. O modelo da função objetivo contempla a localização de faltas com boa precisão para qualquer algoritmo que utiliza medições esparsas de tensão e os menores valores de magnitudes de tensão no alimentador, operando em condições normais ou sob contingências. Apresentam-se resultados de testes com a metodologia proposta para dois alimentadores reais de distribuição de energia elétrica. O primeiro alimentador é de médio porte, tensão nominal de 13,8 kV e possui 134 barras. O segundo alimentador é de grande porte, tensão nominal de 11,4 kV e possui 3287 barras. / This work proposes an optimization technique to allocate voltage measurement devices on radial overhead electric power distribution feeders based on Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic, aiming at improving the performance of algorithms for fault location using sparse voltage information, while making the real time control of the feeder’s operating voltage under different scenarios. The proposed programming model to allocate the devices considers the nature of the stochastic variables involved in the problem with the study of contingencies in electric power systems: loading of the network transformers at time of occurrence of failure, fault impedance, probability of failures and errors of measurement of dispersed voltage devices, likelihood that any of the possible types of faults occur, among others. The model's objective function includes the faults location procedure with good precision for any algorithm that uses sparse measurements of voltage and the lowest values of the magnitudes of voltage feeder, operating under normal conditions or contingencies. Test results with the proposed methodology applied to simulated data of two real life feeders are presented. The first feeder is medium size, rated voltage of 13.8 kV and has 134 bars. The second feeder is large, rated voltage of 11.4 kV and has 3287 bars.

Made available in DSpace on 2014-06-11T19:22:33Z (GMT). No. of bitstreams: 0 Previous issue date: 2008-04-18Bitstream added on 2014-06-13T18:08:30Z : No. of bitstreams: 1 taglialenha_sls_dr_ilha.pdf: 776756 bytes, checksum: ee3e13f4456bb0d2f6f5faaf48d8309f (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / O Problema de Planejamento da Expansão de Sistemas de Transmissão de Energia Elétrica consiste em se escolher, entre um conjunto pré-definido de circuitos candidatos, aqueles que devem ser incorporados ao sistema de forma a minimizar os custos de investimento e operação ao e atender a demanda de energia futura ao longo de um horizonte de planejamento com confiabilidade, assumindo como conhecido o plano de geração. É considerado um problema muito complexo e difícil por se tratar de um problema não linear inteiro misto, não convexo, multimodal e altamente combinatório. Este problema tem sido solucionado usando técnicas clássicas como Decomposição ao de Benders e Branch and Bound, assim como também algoritmos heurísticos e metaheurísticas obtendo diversos resultados, mais com uma série de problemas como, por exemplo, alto esforço computacional e problemas de convergência. Neste trabalho apresentam-se duas novas técnicas de solução para o problema, a saber, as metaheurísticas Busca em Vizinhança Variável e a Busca Dispersa. A Busca em Vizinhança Variável é uma técnica baseada em trocas de estruturas de vizinhança dentro de um algoritmo de busca local, e a metaheurística Busca Dispersa, um método evolutivo que combina sistematicamente conjuntos de soluções para se obter solucões melhores. Essas técnicas de solução oferecem novas alternativas de solução que oferecem solução aos problemas encontrados com outros métodos, como é um baixo esforço computacional é uma melhor convergência, sendo este o principal aporte do trabalho. Os algoritmos são apresentados sistematicamente, explicando os seus algoritmos e a forma como são adaptados para resolver o problema do planejamento da expansão de sistemas de transmissão considerando-se a modelagem matemática conhecida com o modelo de transporte e o modelo DC. São realizados testes com os sistemas... / Electric Energy Transmission Network Expansion Problem consist in choose among a set of pre-defined circuits candidates, who must be incorporated into the system so as to minimize the investment costs and operation and meet the future energy demand over a planning horizon with reliability, assuming the generation plan is known. It is a very complex and difficult problem because it is non linear, non convex, multimodal and highly combinatorial. This problem has been solved using traditional techniques such as Benders decomposition and Branch and Bound, as well as heuristic algorithms and metaheuristics getting different results, but with a series of problems such as high computational effort and convergence problems. This paper tests out two new techniques for solving the problem as are the metaheuristics Variable Neighborhood Search and Scatter Search. The Variable Neighborhood Search is a technique based on trading structures within a neighborhood of a local search algorithm, and the Scatter Search metaheuristic is a method which combines systematically sets of solutions in an evolutionary way to achieve better solutions. These solution techniques offer new alternatives to solve the problems encountered with other methods, such as a low computational effort and better convergence, which is the main contribution of this work. The techniques are presented systematically, explaining their algorithms and the way they are adapted to solve the network expansion planning problem based on the mathematical model known as the transportation model and the DC model. They are tested with the systems Southern Brazilian with 46 buses and the IEEE 24 buses system, results are compared with those obtained with other metaheuristics, obtaining excellent results with a best performance both in processing speed as in computational effort.

Submitted by Livia Mello (liviacmello@yahoo.com.br) on 2016-09-16T12:55:52Z No. of bitstreams: 1 DissAAAD.pdf: 1563807 bytes, checksum: cd9db1180896a8d853b8d7cd4c694860 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-09-21T18:31:23Z (GMT) No. of bitstreams: 1 DissAAAD.pdf: 1563807 bytes, checksum: cd9db1180896a8d853b8d7cd4c694860 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-09-21T18:31:28Z (GMT) No. of bitstreams: 1 DissAAAD.pdf: 1563807 bytes, checksum: cd9db1180896a8d853b8d7cd4c694860 (MD5) / Made available in DSpace on 2016-09-21T18:31:33Z (GMT). No. of bitstreams: 1 DissAAAD.pdf: 1563807 bytes, checksum: cd9db1180896a8d853b8d7cd4c694860 (MD5) Previous issue date: 2016-02-29 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / In this dissertation we address the vehicle routing problem with time windows and multiple deliverymen, a variant of the vehicle routing problem that involves the additional decision of the crew size definition of the vehicles, besides scheduling and routing decisions. This problem arises in the distribution of goods in highly congested urban areas, where due to the relatively long service times, it may be difficult to serve all clients during regular working hours. Given this difficulty, an alternative consists in including the deliverymen assignment decision, which leads to extra costs in addition to travel and vehicle costs. The objective is to define routes to serve customer clusters minimizing the number of vehicles used, the number of allocated deliverymen and the traveled distance. In this study, we develop different solution methods to solve this problem. Initially, we present two metaheuristic approaches, which are based on Iterated Local Search and Large Neighborhood Search. Then we propose hybrid methods, combining these metaheuristics with a branch-price-and-cut method. Computational experiments using instances from the literature confirm the efficiency of the solution methods developed for the problem. / Nesta dissertação aborda-se o problema de roteamento de veículos com janelas de tempo e múltiplos entregadores, uma variante do problema de roteamento de veículos recentemente proposta na literatura que, além das decisões de programação e roteamento, envolve a determinação do tamanho da tripulação de cada veículo. Esse problema surge na distribuição de bens em centros urbanos congestionados em que, devido aos tempos de serviço relativamente longos, pode ser difícil atender a todos os clientes durante o horário normal de trabalho. Diante dessa dificuldade, uma alternativa consiste em incluir a designação de entregadores extras, o que gera custos adicionais aos custos tradicionais de deslocamento e utilização de veículos. Neste problema, o objetivo é definir rotas para atender grupos de clientes minimizando o número de veículos usados, o número total de entregadores designados e a distância total percorrida. Para tratar o problema, são desenvolvidos diferentes métodos de solução. Inicialmente, são apresentadas duas abordagens metaheurísticas baseadas em Busca Local Iterada e Busca em Vizinhança Grande. Posteriormente, são propostos métodos híbridos de solução a partir da combinação dessas metaheurísticas com um método branch-price-and-cut. Experimentos computacionais usando instâncias encontradas na literatura confirmam a eficiência dos métodos de solução desenvolvidos para o problema.

Submitted by Fernando Souza (fernandoafsou@gmail.com) on 2017-08-21T11:30:58Z No. of bitstreams: 1 arquivototal.pdf: 1795088 bytes, checksum: fb7c00f2437bd31139648401e67e1ad9 (MD5) / Made available in DSpace on 2017-08-21T11:30:58Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 1795088 bytes, checksum: fb7c00f2437bd31139648401e67e1ad9 (MD5) Previous issue date: 2014-07-31 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In this work the problem of routing and route allocation (RSA) for elastic optical networks has been studied. This is similar to the problem of routing and wavelength allocation problem, the latter being characteristic routed optical networks in wavelengths. The problem RSA aims to allocate the least amount of resources to elastic optical network so it can cater to the maximum number of demands set out in customer traffic matrix. Besides the study of the problem, in this paper, two metaheuristics were implemented, which were the Iterated Local Search (ILS) and the Greedy Randomized Adaptive Search Procedure (GRASP), which use SSA and LP-CA mathematical models in the local search phase. To implement metaheuristics and mathematical models, we used IBM ILOG CPLEX IDE. The results are presented in graphs, which showed that metaheuristics able to be efficient and competitive, with good quality solutions in an acceptable and even lower than the results presented by accurate modeling computational time. Finally, this paper presents a discussion of the advantages and limitations of this study, and presents directions for future work in this field of study. / Neste trabalho foi estudado o problema de roteamento e alocação de rota (RSA) em redes ópticas elásticas. Este é um problema similar ao problema de roteamento e alocação de comprimentos de onda, este último sendo característico em redes ópticas roteadas em comprimentos de onda. O problema RSA tem como objetivo atribuir a menor quantidade de recursos de uma rede óptica elástica de tal forma que consiga atender ao máximo número de demandas definidas na matriz de tráfego cliente. Além do estudo sobre o problema, neste trabalho foram implementadas duas metaheurísticas, sendo elas o Iterated Local Search (ILS) e o Greedy Randomized Adaptative Search Procedure (GRASP), as quais utilizam os modelos matemáticos SSA e LP-CA na fase de busca local. Para implementar os modelos matemáticos e metaheurísticas, foi utilizada a IDE IBM iLOG CPLEX. Os resultados obtidos são apresentados através de gráficos, os quais demonstraram que as metaheurísticas conseguiram ser eficientes e competitivas, apresentando soluções de boa qualidade em um tempo computacional aceitável e até menor que os resultados apresentados pelos modelos exatos. Por fim, este texto apresenta uma discussão sobre os diferenciais e limitações deste trabalho, e apresenta direcionamentos para trabalhos futuros neste campo de estudo.

Made available in DSpace on 2015-05-14T12:36:41Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 13060370 bytes, checksum: d278616bda56ec354853e6497ba88f41 (MD5) Previous issue date: 2012-08-31 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The arrival of Digital TV has brought the possibility to broadcasters create interactive programs. For this, applications should be sent to the TV station via the standard DSMCC carousel. This standard enables data to be sent cyclically, so that any time you turn on the TV, it can receive all data transmitted. However, the way each interactive application will be available on the carousel has an impact on the users waiting time. The carousel can be modified to prioritize some applications, and so give more satisfaction to most users and also increase the profits of the station. It is not been defined yet a model of how to handle the priority of applications. Current work suggests an innovative business model, seeking to satisfy users, the broadcaster and the contractor.With the priorities of the applications, a new problem arises, termed here as the Download Time Variability Problem (DTVP). It defines the way that the carousel should be created to minimize the users waiting times. This is a difficult problem, which makes the use of exact techniques unapplicable for large instances. The paper proposes the use of GRASP and ILS metaheuristics to solve the problem. / A chegada da TV Digital trouxe consigo a possibilidade de criação de programas interativos por parte das emissoras. Para isso, aplicativos para TV devem ser enviados pela emissora através do padrão Carrossel DSM-CC. Esse padrão permite que os dados sejam enviados de forma cíclica, a fim de que a qualquer momento que o usuário ligue a TV, o mesmo possa receber todos os dados transmitidos. Porém, a forma com que cada aplicativo interativo vai estar disponível no carrossel tem um impacto no tempo de espera do usuário. O carrossel pode ser modificado de forma a priorizar algumas aplicações, e assim dar maior satisfação a maioria dos usuários e também aumentar o lucro da emissora. Ainda não existe um modelo definido de como tratar a prioridade das aplicações. O trabalho corrente sugere um modelo de negócio inovador, buscando satisfazer os usuários, a emissora e a empresa contratante. Com as prioridades das aplicações, surge um novo problema, denominado neste trabalho como o Problema da Variabilidade do Tempo de Download (PVTD). Ele trata da forma com que o carrossel deve ser gerado para minimizar o atraso no download das aplicações. Isso é um problema difícil, o que inviabiliza a utilização de técnicas exatas para grandes instâncias. O trabalho propõe a utilização das metaheurísticas GRASP e ILS para solucionar o problema.

Vários problemas do mundo real podem ser modelados como problemas de otimização global, os quais são comuns em diversos campos da Engenharia e Ciência. Em geral, problemas complexos e de larga-escala não podem ser resolvidos de forma eficiente por técnicas determinísticas. Desse modo, algoritmos probabilísticos, como as metaheurísticas, têm sido amplamente empregados para otimização global. Duas das principais dificuldades nesses problemas são escapar de regiões sub-ótimas e evitar convergência prematura do algoritmo. À medida que a complexidade do problema aumenta, devido a um grande número de variáveis ou de regiões sub-ótimas, o tempo computacional torna-se grande e a possibilidade de que o algoritmo encontre o ótimo global diminui consideravelmente. Para solucionar esses problemas, propõe-se o uso de técnicas de aumento ou melhoria de eficiência. Com essas técnicas, buscase desenvolver estratégias que sejam aplicáveis a diversos algoritmos de otimização global, ao invés de criar um novo algoritmo de otimização ou um algoritmo híbrido. No contexto de problemas contínuos, foram desenvolvidas técnicas para determinação de uma ou mais regiões promissoras do espaço de busca, que contenham uma grande quantidade de soluções de alta qualidade, com maior chance de conterem o ótimo global. Duas das principais técnicas propostas, o Algoritmo de Otimização de Domínio (DOA) e a arquitetura de Amostragem Inteligente (SS), foram testadas com sucesso significativo em vários problemas de otimização global utilizados para benchmark na literatura. A aplicação do DOA para metaheurísticas produziu melhoria de desempenho em 50% dos problemas testados. Por outro lado, a aplicação da SS produziu reduções de 80% da quantidade de avaliações da função objetivo, bem como aumentou a taxa de sucesso em encontrar o ótimo global. Em relação a problemas discretos (binários), foram abordados problemas nos quais existem correlações entre as variáveis, que devem ser identificadas por um modelo probabilístico. Das duas técnicas de aumento de eficiência propostas para esses problemas, a técnica denominada Gerenciamento do Tamanho da População (PSM) possibilita a construção de modelos probabilísticos mais representativos. Com o PSM foi possível atingir uma redução de cerca de 50% na quantidade de avaliações, mantendo a taxa de sucesso em 100%. Em resumo, as técnicas de aumento de eficiência propostas mostramse capazes de aumentar significativamente o desempenho de metaheurísticas, tanto para problemas contínuos quanto para discretos / Several real-world problems from various fields of Science and Engineering can be modeled as global optimization problems. In general, complex and large-scale problems can not be solved eficiently by exact techniques. In this context, Probabilistic algorithms, such as metaheuristics, have shown relevant results. Nevertheless, as the complexity of the problem increases, due to a large number of variables or several regions of the search space with sub-optimal solutions, the running time augments and the probability that the metaheuristics will find the global optimum is significantly reduced. To improve the performance of metaheuristics applied to these problems, new eficiency-enhancement techniques (EETs) are proposed in this thesis. These EETs can be applied to different types of global optimization algorithms, rather than creating a new or a hybrid optimization algorithm. For continuous problems, the proposed EETs are the Domain Optimization Algorithm (DOA) and the Smart Sampling (SS) architecture. In fact, they are pre-processing algorithms that determine one or more promising regions of the search-space, containing a large amount of high-quality solutions, with higher chance of containing the global optimum. The DOA and SS were tested with signicant success in several global optimization problems used as benchmark in the literature. The application of DOA to metaheuristics produced a performance improvement in 50% of problems tested. On the other hand, the application of SS have produced reductions of 80% of the evaluations of the objective function, as well as increased the success rate of finding the global optimum. For discrete problems (binary), we focused on metaheuristics that use probabilistic models to identify correlations among variables that are frequent in complex problems. The main EET proposed for discrete problems is called Population Size Management (PSM), which improves the probabilistic models constructed by such algorithms. The PSM produced a reduction of 50% of function evaluations maintaining the success rate of 100%. In summary, the results show that the proposed EETs can significantly increase the performance of metaheuristics for both discrete and continuous problems

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This work presents three evolutionary strategies to solve the problem of scheduling a given set of n jobs to m identical parallel machines with the objective of minimizing makespan. There is a sequence dependent setup times. We also compares our method with two other well succeeded heuristics, one is a tabu search based heuristic and the second is a memetic approach, which combines a population-based method with local search procedures. As benchmarks for smallsized instances, optimal values are used provide by a dichotomous search. For larger instances, the comparisons try to show the robust behavior in solution quality as well as in computational effort of our evolutionary strategy. / Este trabalho propõe três estratégias evolutivas para resolver o problema de seqüenciamento de n tarefas em m máquinas paralelas idênticas, buscando minimizar o tempo máximo de finalização (makespan). São considerados tempos de preparação dependentes da seqüência. Os métodos propostos são comparados com outras duas heurísticas de qualidade comprovada, uma baseada em Busca Tabu e outra baseada em Algoritmos Meméticos. Para algumas instâncias de pequeno porte, comparações são feitas com o valor ótimo obtido através de uma busca dicotômica. Para instâncias maiores, as comparações demonstram a robustez e a boa qualidade das soluções encontradas pelas estratégias evolutivas através da comparação com as outras heurísticas.

Submitted by Maicon Juliano Schmidt (maicons) on 2015-03-23T14:28:22Z No. of bitstreams: 1 Luan Carlos Nesi.pdf: 100100607 bytes, checksum: 6012e0f177d7b8f3807de72ff7d98315 (MD5) / Made available in DSpace on 2015-03-23T14:28:22Z (GMT). No. of bitstreams: 1 Luan Carlos Nesi.pdf: 100100607 bytes, checksum: 6012e0f177d7b8f3807de72ff7d98315 (MD5) Previous issue date: 2014-03-27 / Milton Valente / Nesse trabalho foi desenvolvido um modelo computacional de Hipermídia Adaptativa para geração de layouts de interface de aplicações. A pesquisa partiu de uma revisão sobre Hipermídia Adaptativa, com um apanhado sobre os conceitos e características dos métodos e técnicas de adaptação a fim de embasar seu desenvolvimento. Após, avaliou-se o uso das metaheurísticas Algoritmo Genético, Busca Tabu e Algoritmo Memético como as ferramentas de apoio no desenvolvimento do modelo. Na sequência, as Redes de Autômatos Estocásticos nortearam a modelagem do formalismo utilizado para a retenção de conhecimento. Dessas bases, foi desenvolvida a prova de conceito. Conseguinte, apresentam-se os experimentos realizados para validação. Os resultados obtidos pelo modelo foram de boa qualidade, indo ao encontro dos objetivos da pesquisa. Como decorrência deste trabalho, obteve-se um sistema capaz de gerar layouts, contemplando as características dos usuários e seus dispositivos, sendo capaz de acompanhar uma tendência de consumo de conteúdos não só mercadológica, mas também, social. / In this paper was developed a computational model of Adaptive Hypermedia for generation of interface layouts of applications. The research began with a review of Adaptive Hypermedia, with an overview of the concepts and characteristics of the methods and adaptation techniques in order to base its development. After, we evaluated the use of metaheuristic Genetic Algorithm, Tabu Search, and Memetic Algorithm as support tools in the development of the model. Following, the Stochastic Automata Networks guided the modeling of the formalism used for knowledge retention. These bases, the proof of concept were developed. Therefore, we present the experiments to validate. The obtained results by the model were of good quality, meeting the research objectives. As results of this work, we obtained a system capable to generate layouts, considering the characteristics of the users and their devices, being able to follow a trend of content consumption not only marketing, but also social.

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.