Algoritmo híbrido para o problema do caixeiro viajante dinâmico: otimização por colônia de formigas + buscas locais

• Ano de defesa: 2018
• Autor(a) principal: Souza, Matheus Ricalde de
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Santa Maria; Brasil; Ciência da Computação; UFSM; Programa de Pós-Graduação em Ciência da Computação; Centro de Tecnologia
• Palavras-chave em Português: Meta-heurísticas; Busca local; Otimização de colônia de formigas; Lin-kernighan; Genius; Problema do caixeiro viajante; Meta-heuristics; Local search; Ant colony optimization; Traveling salesman problem; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://repositorio.ufsm.br/handle/1/15762

The present work deals with the resolution of the Dynamic Traveling Salesman Problem (DTSP), it has a great relevance within the literature, being able to be applied to real problems as problems of logistics and telecommunications. Ant colony algorithms are currently considered one of the most successful techniques for solving various combinatorial problems, among them the traveling salesman problem. To solve the problem we propose a hybrid algorithm that works with the meta-heuristic Ant Colony Optimization combined with local searches applied to the symmetric of the dynamic traveling salesman problem. The tests were carried out in five instances belonging to the traveling salesman problem library (TSPLIB). The proposed hybrid algorithm proved to be effective in the search for solutions, where in all tested instances it exceeded expectations, reaching superiority compared to the memetic algorithm compared