Dissertação
Solving Large Scale Arc Routing Problems EVALUATED
O Capacitated Arc Routing Problem (CARP) é um problema de otimização combinatória muito importante com uma vasta gama de aplicações tais como recolha de resíduos, manutenção de estradas e espalhamento de sal para prevenir neve. Nesta tese, propomos um Algoritmo Memético com Mutação por Divisão e Conquista (MADCoM) para resolver o Mixed Capacitated Arc Routing Problem (MCARP), uma variante do CARP mais adequada às redes de estradas do mundo real. É dada ênfase à resolução de instâncias de grande escala, uma vez que a maioria das aplicações abrange uma cidade inteira. MADCoM é um algoritmo genético com controlo de diversidade adaptativo hibridizado com procura local eficiente. Introduzimos um novo operador de mutação que consiste em aplicar a uma solução duas heurísticas de dividir para conquistar, Route Cutting Off Decomposition e Hierarchical Decomposition. Demonstramos que conduz a um melhor desempenho do algoritmo quando combinado com procura local, principalmente para instâncias maiores. Além disso, Hierarchical Decomposition é utilizado como um método de inicialização. Mostramos que gera uma população diversificada com soluções de qualidade. Definimos um dos seus parâmetros como dependente da dimensão do problema, o que leva a uma redução do tempo computacional sem afectar a qualidade das soluções. Testamos o desempenho do MADCoM nas referências clássicas para CARP e MCARP, bem como nas referências mais recentes de grande dimensão. Encontramos novas melhores soluções para 8 instâncias de MCARP, 2 das quais são soluções ótimas, e novas melhores soluções para 12 instâncias de grande dimensão do CARP.
dezembro 7, 2021, 15:0
Publicação
Obra sujeita a Direitos de Autor
Orientação
ORIENTADOR
Departamento de Engenharia Mecânica (DEM)
Professor Catedrático