Heurísticas para o problema do caixeiro viajante branco e preto

• Ano de defesa: 2005
• Autor(a) principal: Maciel, André Cordeiro Macedo
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Programa de Pós-Graduação em Computação; Computação
• Palavras-chave em Português: Metaheurística GRASP; Heurística; Caixeiro-viajante; GRASP; Regras de Redução; V ND; V NS; Heuristics; Metaheuristics; The traveling salesman problem; Reduction rules; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::COMPUTABILIDADE E MODELOS DE COMPUTACAO
• Link de acesso: https://app.uff.br/riuff/handle/1/17815

This work describes a generalization of the Traveling Salesman Problem - TSP called Black and White Traveling Salesman Problem - BWTSP. The BWTSP is defined in a graph G (oriented or not), in a such way that the associated vertex set is partitioned into black and white vertices. The objective is to find a shortest hamiltonian tour subject to Cardinality and Length constraints. These constraints are related to the number of white vertices (cardinality) and the total distance (length) between two consecutive black vertices in a feasible solution. The main applications of this problem are found in the telecomunication area and the scheduling of airline operations that incorporate maintenance conections. In this work we introduce mathematical formulations for asymmetrical and symmetrical BWTSP, we propose news construction and local search algorithms that are used in the metaheuristics GRASP, V NS and V ND. Computational results show the viability of the proposed methods.