{pt_PT=Solving Large Scale Arc Routing Problems} {} EVALUATED

Detalhes: {pt=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., en=The Capacitated Arc Routing Problem (CARP) is a very important combinatorial optimization problem with a wide range of applications such as waste collection, road maintenance and winter gritting. In this thesis, we propose an algorithm called Memetic Algorithm with Divide-and-Conquer Mutation (MADCoM) to solve the Mixed Capacitated Arc Routing Problem (MCARP), a variant of CARP more suited to real-world street networks. An emphasis is placed on solving large-scale instances, as most applications span an entire city. MADCoM is a genetic algorithm with adaptive diversity control hybridized with efficient local search. We introduce a novel mutation operator which consists of applying to a solution two state-of-the-art divide-and-conquer heuristics, Route Cutting Off Decomposition and Hierarchical Decomposition. We demonstrate that it leads to improved performance of the algorithm when coupled with local search, particularly for larger instances. Furthermore, Hierarchical Decomposition is used as an initialization method. We show that it generates a diverse population with quality solutions. We define one of its parameters to be dependent on the problem size, which leads to reduced computational time without affecting solution quality. We test the performance of MADCoM on the classical benchmarks for CARP and MCARP, as well as the more recent large-scale benchmarks. We find new best solutions for 8 instances of MCARP, 2 of which are optimal solutions, and new best solutions for 12 large-scale CARP instances.}

Discussão: dezembro 7, 2021, 15:0

Publicação

Obra sujeita a Direitos de Autor

Orientação

AUTOR

Diogo Miguel Ferreira de Oliveira (ist187176)

ORIENTADOR

João Miguel Da Costa Sousa

Departamento de Engenharia Mecânica (DEM)

Professor Catedrático