Combining genetic local search into multi-population evolutionary algorithms for the capacitated vehicle routing problem

• Ano de defesa: 2023
• Autor(a) principal: Babak Rezaei
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Universidade Federal de Minas Gerais; Brasil; ENG - DEPARTAMENTO DE ENGENHARIA ELÉTRICA; Programa de Pós-Graduação em Engenharia Elétrica; UFMG
• Palavras-chave em Português: Vehicle routing problem; Evolutionary computation; Imperialist competitive algorithm; Hybrid genetic search; Island genetic algorithm; Multi-population genetic algorithm; Engenharia elétrica; Veículos; Algoritmos genéticos; Genética; Algoritmos; Inteligência artificial; Ciência da computação; Cálculos numéricos
• Link de acesso: http://hdl.handle.net/1843/60098

O Problema de Roteamento de Veículos (VRP) é um dos problemas mais significativos na pesquisa operacional atualmente. O VRP tem uma ampla gama de campos de aplicação, como transporte, logística, manufatura, sistemas de auxílio e comunicação. Para atender às necessidades de diferentes cenários do VRP no mundo real, muitos modelos de VRP foram desenvolvidos - sendo o CVRP (VRP capacitado) a forma clássica. Neste estudo, é proposto inicialmente um algoritmo híbrido (ICAHGS) para resolver o CVRP, combinando um ICA (Algoritmo Competitivo Imperialista) refinado como o método evolucionário primário e de múltiplas populações, e um algoritmo de Busca Genética Híbrida (HGS-CVRP) como uma estratégia aprimorada de busca local e gerenciamento de população dentro do framework do ICA. O ICAHGS foi comparado com diversos algoritmos de ponta da literatura. Os resultados dessa comparação, que incluem tanto instâncias de referência clássicas quanto aplicações do mundo real, demonstram o desempenho competitivo do algoritmo proposto. Posteriormente, é introduzido o Algoritmo Genético de Ilhas com População Dinâmica e HGS (DPIGA-HGS), que é um novo modelo híbrido de metaheurística. O DPIGA-HGS integra um modelo de ilhas especializado (DPIGA) e um HGS refinado como seu mecanismo de busca local dentro de cada ilha. O objetivo principal do DPIGA-HGS é contribuir para o avanço do campo, propondo uma nova variante do Algoritmo Genético de Ilhas e, simultaneamente, alcançando resultados de otimização aprimorados em comparação com o ICAHGS. Os resultados das análises comparativas revelaram o desempenho superior do DPIGA-HGS quando comparado a outros algoritmos de ponta, incluindo o ICAHGS. Através de múltiplos conjuntos de dados de referência, o DPIGA-HGS demonstrou sua habilidade ao alcançar um número significativo de solução mais conhecida (BKS), superando seus concorrentes em várias instâncias.