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

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorOchi, Luiz Satoru-
Autor(es): dc.contributorCPF:31609080822-
Autor(es): dc.contributorhttp://lattes.cnpq.br/9171815778534257-
Autor(es): dc.contributorMartinhon, Carlos Alberto de Jesus-
Autor(es): dc.contributorCPF:31790806422-
Autor(es): dc.contributorhttp://lattes.cnpq.br/2822582595834942-
Autor(es): dc.contributorLavor, Carlile Campos-
Autor(es): dc.contributorCPF:31870800722-
Autor(es): dc.contributorhttp://lattes.cnpq.br/2019624495480547-
Autor(es): dc.contributorBarboza, Eduardo Uchoa-
Autor(es): dc.contributorCPF:85462487922-
Autor(es): dc.contributorhttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4721785E2-
Autor(es): dc.contributorArroyo, José Elias Claudio-
Autor(es): dc.contributorCPF:32009945122-
Autor(es): dc.contributorhttp://lattes.cnpq.br/6685448343335507-
Autor(es): dc.creatorMaciel, André Cordeiro Macedo-
Data de aceite: dc.date.accessioned2024-07-11T17:29:20Z-
Data de disponibilização: dc.date.available2024-07-11T17:29:20Z-
Data de envio: dc.date.issued2021-03-10-
Data de envio: dc.date.issued2008-03-04-
Data de envio: dc.date.issued2021-03-10-
Data de envio: dc.date.issued2005-08-26-
Fonte completa do material: dc.identifierhttps://app.uff.br/riuff/handle/1/17815-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/751333-
Descrição: dc.descriptionThis 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.-
Descrição: dc.descriptionEste trabalho aborda uma extensão do Problema do Caixeiro Viajante - PCV denominado Problema do Caixeiro Viajante Branco e Preto-PCVBP. O PCV BP é definido sobre um grafo G (orientado ou não), de maneira que o conjunto de vértices associado está particionado em vértices brancos e pretos. O objetivo é encontrar um caminho hamiltoniano de custo mínimo sujeito a restrições adicionais de Cardinalidade e Comprimento. Estas restrições estão relacionadas respectivamente, ao número de vértices brancos (cardinalidade) e a distância total percorrida (comprimento) entre dois vértices pretos consecutivos em uma solução viável. As principais aplicações deste problema estão nas áreas de telecomunicação e escalonamento de operações aéreas que necessitam de manutenção de conexões. Neste trabalho introduzimos formulações matemáticas para o PCV BP assimétrico e simétrico, propomos novas heurísticas de construção e busca local que são utilizadas junto as metaheurísticas GRASP, V NS e V ND. Resultados computacionais comprovam a viabilidade dos métodos propostos.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherPrograma de Pós-Graduação em Computação-
Publicador: dc.publisherComputação-
Direitos: dc.rightsAcesso Aberto-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectMetaheurística GRASP-
Palavras-chave: dc.subjectHeurística-
Palavras-chave: dc.subjectCaixeiro-viajante-
Palavras-chave: dc.subjectGRASP-
Palavras-chave: dc.subjectRegras de Redução-
Palavras-chave: dc.subjectV ND-
Palavras-chave: dc.subjectV NS-
Palavras-chave: dc.subjectHeuristics-
Palavras-chave: dc.subjectMetaheuristics-
Palavras-chave: dc.subjectThe traveling salesman problem-
Palavras-chave: dc.subjectReduction rules-
Palavras-chave: dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::COMPUTABILIDADE E MODELOS DE COMPUTACAO-
Título: dc.titleHeurísticas para o problema do caixeiro viajante branco e preto-
Tipo de arquivo: dc.typeDissertação-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.