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 2016-06-01T14:43:08Z No. of bitstreams: 1 Valdemar Modolo Junior.pdf: 2802590 bytes, checksum: f3956818acd10efc3244abc007294827 (MD5) / Made available in DSpace on 2016-06-01T14:43:08Z (GMT). No. of bitstreams: 1 Valdemar Modolo Junior.pdf: 2802590 bytes, checksum: f3956818acd10efc3244abc007294827 (MD5) Previous issue date: 2015-06-10 / Among the optimization methods, the Genetic Algorithm (GA) has been producing good results in problems with high order of complexity, such as, for example, the production scheduling problem in job shop environment. The production sequencing problems must be translated into a mathematical representation, so that the AG can act. In this process we came up a problematic, the choice between different ways to represent the solution as some representations have limitations, how to present not feasible and / or redundant solutions. Therefore the aim of this study is to conduct a comparative study between different representations of the solution in the AG in production sequencing problems in job shop environments. Two representations of the solution were analyzed, the priority lists based and based on order of operations and compared with a binary representation, in the context of sequencing problem set defined by Lawrence (1984). The results were evaluated according to the total processing time (makespan), the computational cost and the proportion of generated feasible solutions. It was noticed that the representation of the solution based on order of operations, which produced 100% of feasible solutions, was the one that showed the best results although no convergence to the best known solution to every problem. / Dentre os métodos de otimização, o Algoritmo Genético (AG) vem produzindo bons resultados em problemas com ordem de complexidade elevada, como é o caso, por exemplo, do problema de sequenciamento da produção em ambiente job shop. Os problemas de sequenciamento da produção devem ser traduzidos para uma representação matemática, para que o AG possa atuar. Neste processo surgi uma problemática, a escolha entre as diferentes formas de se representar a solução visto que algumas representações apresentam limitações, como apresentar soluções não factíveis e/ou redundantes. Portanto o objetivo deste trabalho é realizar um estudo comparativo entre diferentes representações da solução no AG em problemas de sequenciamento da produção em ambientes job shop. Duas representações da solução foram analisadas, a baseada em listas de prioridades e a baseada em ordem de operações e comparada com uma representação binária, no contexto do conjunto de problemas de sequenciamento definidos por Lawrence (1984). Os resultados foram avaliados em função do tempo total de processamento (makespan), do custo computacional e da proporção de soluções factíveis geradas. Percebeu-se que, a representação da solução baseada em ordem de operações, a qual produziu 100% de soluções factíveis, foi a que mostrou os melhores resultados apesar de não apresentar convergência para a melhor solução conhecida em todos os problemas.