Use este identificador para citar ou linkar para este item: https://locus.ufv.br//handle/123456789/7558
Tipo: Dissertação
Título: Abordagens heurísticas para tratar o problema do Caixeiro Viajante Preto e Branco
Heuristics approaches for the Black and White Traveling Salesman problem
Autor(es): Cazetta, Paôla Pinto
Abstract: O Problema do Caixeiro Viajante Preto e Branco (PCV-PB) é uma generalização do Problema do Caixeiro Viajante (PCV), definido sobre um grafo onde os vértices são classificados como pretos ou brancos. Assim como o clássico PCV, o objetivo do PCV-PB é encontrar um ciclo hamiltoniano de custo mínimo, entretanto, duas restrições adicionais são consideradas. Enquanto que a restrição de cardinalidade restringe o número de vértices brancos entre dois vértices pretos consecutivos, a restrição de comprimento restringe a distância máxima entre os mesmos. Apli- cações do PCV-PB podem ser observadas no escalonamento de aeronaves e em configurações de redes de telecomunicações. A proposta deste estudo é analisar diferentes estratégias heurísticas aplicadas para o PCV-PB. Heurísticas construtivas da literatura foram aperfeiçoadas e uma nova estratégia para a construção da solução foi apresentada. Neste contexto foi utilizado métodos como Lin kernighan e Inserção Específica de Brancos. Além disso, foram propostas abordagens heurísticas baseadas nas metaheurísticas GRASP, VND, ILS e SA. Diversos experimentos computacionais foram realizados para comparar a eficácia das abordagens. Os resultados garantem a aplicabilidade dos algoritmos propostos para o problema.
The Black and White Traveling Salesman Problem (TSP-BW) is a generalization of the Travelling Salesman Problem (TSP), set on a graph where the vertices are classified as black or white. As in the classical PCV, a solution of the TSP-BW is a Hamiltonian cycle of minimal cost. However, two additional constraints are considered. While the cardinality constraint limits the number of white vertices between two consecutive black vertices, the length constraint restricts the maximum distance therebetween. Applications of TSP-BW can be observed in aircraft scheduling and telecommunications network settings. The purpose of this study is to analyze different heuristic strategies applied to TSP-BW. Literature constructive heuristics have been improved and a new strategy for building the solution was presented. In this context it used methods such as Lin Kernighan and Inserção Específica de Brancos. Also, it has been proposed heuristic approaches based on metaheuristics GRASP, VND, ILS and SA. Several computational experiments were performed to compare effectiveness of approa- ches. The results ensure the applicability of the proposed algorithms to the problem.
Palavras-chave: Inteligência artificial
Programação heurística
Algorítmos computacionais
CNPq: Ciência da Computação
Editor: Universidade Federal de Viçosa
Citação: CAZETTA, Paôla Pinto. Abordagens heurísticas para tratar o problema do Caixeiro Viajante Preto e Branco. 2015. 134f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Viçosa, Viçosa. 2015.
Tipo de Acesso: Acesso Aberto
URI: http://www.locus.ufv.br/handle/123456789/7558
Data do documento: 8-Dez-2015
Aparece nas coleções:Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
texto completo.pdftexto completo6,25 MBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.