Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/60098
Type: | Tese |
Title: | Combining genetic local search into multi-population evolutionary algorithms for the capacitated vehicle routing problem |
Authors: | Babak Rezaei |
First Advisor: | Frederico Gadelha Guimarães |
First Co-advisor: | Pauline Catriona Haddow |
metadata.dc.contributor.advisor-co2: | Rasul Enayatifar |
First Referee: | Gilberto Reynoso Meza |
Second Referee: | Puca Huachi Vaz Penna |
Third Referee: | Roberto Gomes Ribeiro |
metadata.dc.contributor.referee4: | Lucas de Souza Batista |
Abstract: | The Vehicle Routing Problem (VRP) is one of the most significant problems in operational research today. VRP has a vast range of application fields such as transportation, logistics, manufacturing, relief systems and communication. To suit the needs of different real-world VRP scenarios, many models of VRP have been developed - CVRP (Capacitated VRP) being the classical form. In this study, at first a hybrid algorithm (ICAHGS) for solving CVRP is proposed, combining a refined ICA (Imperialist Competitive Algorithm) as the primary evolutionary and multi-population method, and a Hybrid Genetic Search (HGSCVRP) algorithm as an enhanced local search and population management strategy within the ICA framework. ICAHGS has been compared to several state-of-the-art algorithms from literature. The results of this comparison, which include both classical benchmark instances and real-world applications, demonstrate the competitive performance of the proposed algorithm. Afterwards, Dynamic Population Island GA and HGS (DPIGA-HGS) is introduced, which is a novel hybrid metaheuristic model. DPIGA-HGS integrates a specialized island model (DPIGA) and a refined HGS as its local search engine within each island. The primary objective of DPIGA-HGS is to contribute to the advancement of the field by proposing a new variant of Island GA and simultaneously achieving improved optimization results in comparison to ICAHGS. The results of the comparative analyses revealed the superior performance of DPIGA-HGS when pitted against other state-of-the art algorithms, including ICAHGS. Across multiple benchmark datasets, DPIGA-HGS showcased its prowess by achieving a significant number of BKS (Best Known Solution), outperforming its competitors in various instances. |
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. |
Subject: | Engenharia elétrica Veículos Algoritmos genéticos Genética Algoritmos Inteligência artificial Ciência da computação Cálculos numéricos |
language: | eng |
metadata.dc.publisher.country: | Brasil |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
metadata.dc.publisher.department: | ENG - DEPARTAMENTO DE ENGENHARIA ELÉTRICA |
metadata.dc.publisher.program: | Programa de Pós-Graduação em Engenharia Elétrica |
Rights: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/60098 |
Issue Date: | 30-Aug-2023 |
Appears in Collections: | Teses de Doutorado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Final Thesis - Babak Rezaei.pdf | 8.5 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.