Uma abordagem híbrida para a solução do problema de roteamento de veículos com múltiplos depósitos e frota heterogênea: algoritmo genético e busca tabu

• Ano de defesa: 2017
• Autor(a) principal: Araujo, Roberto da Silva
• Orientador(a): Gómez, Arthur Tórgo
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade do Vale do Rio dos Sinos
• Programa de Pós-Graduação: Programa de Pós-Graduação em Computação Aplicada
• Departamento: Escola Politécnica
• País: Brasil
• Palavras-chave em Português: Informática; Algoritmo genético; Busca Tabu; Problema de roteamento de veículo; Múltiplos depósitos; Frota heterogênea
• Palavras-chave em Inglês: Computer; Genetic algorithm; Tabu search; Vehicle routing problem; Multidepot; Heterogeneous fleet
• Área do conhecimento CNPq: ACCNPQ::Ciências Exatas e da Terra::Ciência da Computação
• Link de acesso: http://www.repositorio.jesuita.org.br/handle/UNISINOS/6864

Neste trabalho é apresentado um Algoritmo Híbrido (AH) aplicado ao Problema de Roteamento de Veículos com Múltiplos Depósitos e Frota Heterogênea (PRVMDFH). Um conjunto de clientes é atendido por um número fixo de veículos de diferentes tamanhos, por múltiplos depósitos, sujeito a restrições da capacidade do veículo. As meta-heurísticas utilizadas na construção do AH são o Algoritmo Genético (AG) e a Busca Tabu (BT). O AG usa operadores de cruzamento Mapeado Parcialmente (PMX), Cromossomo de Duas Partes (TCX) e de Ordem (OX), o operador de mutação Troca e o Algoritmo de Busca Local (ABL). A BT usa os métodos de Troca, Retirada e Inserção e Deslocamento. São analisadas as políticas de diversificação no ABL e a intensificação com as estratégias de geração de vizinhança na BT. São utilizados conjuntos de dados padrões de problemas testes, para executar os algoritmos propostos. Os resultados obtidos, comparados a outros autores, apresentaram boas soluções para diferentes tamanhos de problemas testes.