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

Abstract

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.