@MASTERSTHESIS{ 2015:1754963031,
 	title = {Otimização do problema de roteamento de veículos capacitado usando algoritmos genéticos com heurísticas e representações cromossômicas alternativas},
 	year = {2015},
 	url = "http://bibliotecatede.uninove.br/handle/tede/1124",
 	abstract = "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.",
 	publisher = {Universidade Nove de Julho},
 	scholl = {Programa de Pós-Graduação de Mestrado e Doutorado em Engenharia de Produção},
 	note = {Engenharia}
}